Class: Rambling::Trie::Container

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Enumerable[String]
Defined in:
lib/rambling/trie/container.rb,
sig/lib/rambling/trie/container.rbs

Overview

Wrapper on top of trie data structure.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root, compressor) {|self| ... } ⇒ Container

Creates a new trie.

Parameters:

Yields:

  • (self) —

    the trie just initialized.



17
18
19
20
21
22
 
# File 'lib/rambling/trie/container.rb', line 17

def initialize root, compressor
  @root = root
  @compressor = compressor

  yield self if block_given?
end

Instance Attribute Details

#compressor ⇒ Compressor[TValue] (readonly)

Returns the value of attribute compressor.

Returns:



218
219
220
 
# File 'lib/rambling/trie/container.rb', line 218

def compressor
  @compressor
end

#root ⇒ Nodes::Node

The root node of this trie.

Returns:



11
12
13
 
# File 'lib/rambling/trie/container.rb', line 11

def root
  @root
end

Instance Method Details

#==(other) ⇒ Boolean

Compares two trie data structures.

Parameters:

Returns:

  • (Boolean) —

    true if the tries are equal, false otherwise.



139
140
141
 
# File 'lib/rambling/trie/container.rb', line 139

def == other
  root == other.root
end

#[](letter) ⇒ Nodes::Node

Get Node corresponding to a given letter.

Parameters:

  • letter (Symbol) —

    the letter to search for in the root node.

  • (Symbol)

Returns:

  • (Nodes::Node) —

    the node corresponding to that letter.

See Also:



163
164
165
 
# File 'lib/rambling/trie/container.rb', line 163

def [] letter
  root[letter]
end

#add(word, value = nil) ⇒ Nodes::Node Also known as: <<

Adds a word to the trie.

Parameters:

  • word (String) —

    the word to add to the trie.

  • value (Object, nil) (defaults to: nil) —

    the value to associate with the word.

  • (String)
  • (TValue, nil)

Returns:

Raises:

See Also:



31
32
33
 
# File 'lib/rambling/trie/container.rb', line 31

def add word, value = nil
  root.add reversed_char_symbols(word), value
end

#children ⇒ Array<Nodes::Node>

Root node's child nodes.

Returns:

  • (Array<Nodes::Node>) —

    the array of children nodes contained in the root node.

See Also:



170
171
172
 
# File 'lib/rambling/trie/container.rb', line 170

def children
  root.children
end

#children_tree ⇒ Hash<Symbol, Nodes::Node>

Root node's children tree.

Returns:

  • (Hash<Symbol, Nodes::Node>) —

    the children tree hash contained in the root node, consisting of :letter => node.

See Also:



178
179
180
 
# File 'lib/rambling/trie/container.rb', line 178

def children_tree
  root.children_tree
end

#compress ⇒ Container

Deprecated.

Calling #compress on an already-compressed trie is deprecated and will raise InvalidOperation in the next major version. Use #compressed? to guard if needed.

Compresses the existing trie using redundant node elimination. Returns a new trie with the compressed root.

Returns:



72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/rambling/trie/container.rb', line 72

def compress
  if root.compressed?
    warn <<~WARN.chomp.tr("\n", ' ')
      [DEPRECATED] Calling `compress` on an already-compressed trie is deprecated
      and will raise `InvalidOperation` in the next major version.
      Called from #{caller_locations(1, 1)&.first}
    WARN
    return Rambling::Trie::Container.new root, compressor
  end

  Rambling::Trie::Container.new compress_root, compressor
end

#compress! ⇒ self

Note:

This method replaces the root Raw node with a Compressed version of it.

Compresses the existing trie using redundant node elimination. Marks the trie as compressed. Does nothing if the trie has already been compressed.

Returns:

  • (self) 


63
64
65
66
 
# File 'lib/rambling/trie/container.rb', line 63

def compress!
  self.root = compress_root unless root.compressed?
  self
end

#compress_root ⇒ Nodes::Compressed[TValue]

Returns:



233
234
235
 
# File 'lib/rambling/trie/container.rb', line 233

def compress_root
  compressor.compress(root) || raise
end

#compressed? ⇒ Boolean

Indicates if the root Node can be compressed or not.

Returns:

  • (Boolean) —

    true for non-terminal nodes with one child, false otherwise.



184
185
186
 
# File 'lib/rambling/trie/container.rb', line 184

def compressed?
  root.compressed?
end

#concat(words, values = nil) ⇒ Array<Nodes::Node>

Adds all provided words to the trie.

Parameters:

  • words (Array<String>) —

    the words to add to the trie.

  • values (Array<Object>, nil) (defaults to: nil) —

    the values to associate with each word, in the same order.

  • (Array[String])
  • (Array[TValue?], nil)

Returns:

  • (Array<Nodes::Node>) —

    the collection of nodes added.

Raises:

  • (InvalidOperation) —

    if the trie is already compressed.

  • (ArgumentError) —

    if words and values are given but differ in size.

See Also:



43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/rambling/trie/container.rb', line 43

def concat words, values = nil
  if values
    words_size = words.size
    values_size = values.size
    unless words_size == values_size
      raise ArgumentError,
        "words and values must have the same size (words: #{words_size}, values: #{values_size})"
    end

    words.each_with_index.map { |word, index| add(word, values[index]) }
  else
    words.map { |word| add word }
  end
end

#each ⇒ Container[TValue] #each ⇒ Enumerator[String, void]

Iterates over the words contained in the trie.

Overloads:

  • #each ⇒ Container[TValue]

    Returns:

  • #each ⇒ Enumerator[String, void]

    Returns:

    • (Enumerator[String, void])

Yields:

  • (String) —

    the words contained in this trie node.

Yield Parameters:

  • arg0 (String)

Yield Returns:

  • (void)

Returns:

  • (self) 


146
147
148
149
150
151
152
 
# File 'lib/rambling/trie/container.rb', line 146

def each
  return enum_for :each unless block_given?

  root.each { |word| yield word }

  self
end

#inspect ⇒ String

Returns a string representation of the container.

Returns:

  • (String) —

    a string representation of the container.



155
156
157
 
# File 'lib/rambling/trie/container.rb', line 155

def inspect
  "#<#{self.class.name} root: #{root.inspect}>"
end

#key?(letter) ⇒ Boolean Also known as: has_key?, has_letter?

Check if a letter is part of the root Nodes::Node's children tree.

Parameters:

  • letter (Symbol) —

    the letter to search for in the root node.

  • (Symbol)

Returns:

  • (Boolean) —

    whether the letter is contained or not.

See Also:



199
200
201
 
# File 'lib/rambling/trie/container.rb', line 199

def key? letter
  root.key? letter
end

#partial_word?(word = '') ⇒ Boolean Also known as: match?

Checks if a path for a word or partial word exists in the trie.

Parameters:

  • word (String) (defaults to: '') —

    the word or partial word to look for in the trie.

  • (String)

Returns:

  • (Boolean) —

    true if the word or partial word is found, false otherwise.

See Also:



89
90
91
 
# File 'lib/rambling/trie/container.rb', line 89

def partial_word? word = ''
  root.partial_word? word.chars
end

#push(*words) ⇒ Array<Nodes::Node>

Adds all provided words to the trie.

Parameters:

  • words (String) —

    the words to add to the trie.

  • (String)

Returns:

  • (Array<Nodes::Node>) —

    the collection of nodes added.

Raises:

See Also:



100
101
102
 
# File 'lib/rambling/trie/container.rb', line 100

def push *words
  concat words
end

#reversed_char_symbols(word) ⇒ Array[Symbol]

Parameters:

  • (String)

Returns:

  • (Array[Symbol]) 


237
238
239
240
241
242
 
# File 'lib/rambling/trie/container.rb', line 237

def reversed_char_symbols word
  # @type var chars: Array[String]
  chars = word.chars
  chars.reverse!
  chars.map(&:to_sym)
end

#scan(word = '') ⇒ Array<String> Also known as: words

Returns all words that start with the specified characters.

Parameters:

  • word (String) (defaults to: '') —

    the word to look for in the trie.

  • (String)

Returns:

  • (Array<String>) —

    all the words contained in the trie that start with the specified characters.

See Also:



117
118
119
 
# File 'lib/rambling/trie/container.rb', line 117

def scan word = ''
  root.scan(word.chars).to_a
end

#size ⇒ Integer

Number of words contained in the trie.

Returns:

  • (Integer) —

    the number of words stored in the trie.



205
206
207
 
# File 'lib/rambling/trie/container.rb', line 205

def size
  root.size
end

#to_a ⇒ Array<String>

Array of words contained in the root Node.

Returns:

  • (Array<String>) —

    all words contained in this trie.

See Also:



191
192
193
 
# File 'lib/rambling/trie/container.rb', line 191

def to_a
  root.to_a
end

#word?(word = '') ⇒ Boolean Also known as: include?

Checks if a whole word exists in the trie.

Parameters:

  • word (String) (defaults to: '') —

    the word to look for in the trie.

  • (String)

Returns:

  • (Boolean) —

    true only if the word is found and the last character corresponds to a terminal node, false otherwise.

See Also:



109
110
111
 
# File 'lib/rambling/trie/container.rb', line 109

def word? word = ''
  root.word? word.chars
end

#words_within(phrase) ⇒ Array<String>

Returns all words within a string that match a word contained in the trie.

Parameters:

  • phrase (String) —

    the string to look for matching words in.

  • (String)

Returns:

  • (Array<String>) —

    all the words in the given string that match a word in the trie.



124
125
126
 
# File 'lib/rambling/trie/container.rb', line 124

def words_within phrase
  words_within_root(phrase).to_a
end

#words_within?(phrase) ⇒ Boolean

Checks if there are any valid words in a given string.

Parameters:

  • phrase (String) —

    the string to look for matching words in.

  • (String)

Returns:

  • (Boolean) —

    true if any word within phrase is contained in the trie, false otherwise.

See Also:



132
133
134
 
# File 'lib/rambling/trie/container.rb', line 132

def words_within? phrase
  words_within_root(phrase).any?
end

#words_within_root(phrase) ⇒ void

This method returns an undefined value.

Parameters:

  • (String) 


221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/rambling/trie/container.rb', line 221

def words_within_root phrase
  return enum_for :words_within_root, phrase unless block_given?

  chars = phrase.chars
  chars.each_index do |starting_index|
    new_phrase = chars[starting_index..] || raise
    root.match_prefix(new_phrase) { |word| yield word }
  end

  self
end