Class: Rambling::Trie::Container

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/rambling/trie/container.rb

Overview

Wrapper on top of trie data structure.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

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

Creates a new trie.

Parameters:

  • root (Nodes::Node) —

    the root node for the trie

  • compressor (Compressor) —

    responsible for compressing the trie

Yields:



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

#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:

  • other (Container) —

    the trie to compare against.

Returns:

  • (Boolean) —

    ‘true` if the tries are equal, `false` otherwise.



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

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.

Returns:

  • (Nodes::Node) —

    the node corresponding to that letter.

See Also:



141
142
143
 
# File 'lib/rambling/trie/container.rb', line 141

def [] letter
  root[letter]
end

#add(word) ⇒ Nodes::Node Also known as: <<

Adds a word to the trie.

Parameters:

  • word (String) —

    the word to add the branch from.

Returns:

  • (Nodes::Node) —

    the just added branch’s root node.

Raises:

See Also:



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

def add word
  root.add char_symbols word
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:



149
150
151
 
# File 'lib/rambling/trie/container.rb', line 149

def children
  root.children
end

#children_tree ⇒ Array<Nodes::Node>

Root node’s children tree.

Returns:

  • (Array<Nodes::Node>) —

    the array of children nodes contained in the root node.

See Also:



157
158
159
 
# File 'lib/rambling/trie/container.rb', line 157

def children_tree
  root.children_tree
end

#compress ⇒ Container

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

Returns:



60
61
62
63
 
# File 'lib/rambling/trie/container.rb', line 60

def compress
  return self if root.compressed?
  Rambling::Trie::Container.new compress_root, compressor
end

#compress! ⇒ Container

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:



50
51
52
53
 
# File 'lib/rambling/trie/container.rb', line 50

def compress!
  self.root = compress_root unless root.compressed?
  self
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.



165
166
167
 
# File 'lib/rambling/trie/container.rb', line 165

def compressed?
  root.compressed?
end

#concat(words) ⇒ Array<Nodes::Node>

Adds all provided words to the trie.

Parameters:

  • words (Array<String>) —

    the words to add the branch from.

Returns:

  • (Array<Nodes::Node>) —

    the collection of nodes added.

Raises:

See Also:



40
41
42
 
# File 'lib/rambling/trie/container.rb', line 40

def concat words
  words.map { |word| add word }
end

#each {|String| ... } ⇒ Object

Iterates over the words contained in the trie.

Yields:

  • (String) —

    the words contained in this trie node.



124
125
126
127
128
129
130
 
# File 'lib/rambling/trie/container.rb', line 124

def each
  return enum_for :each unless block_given?

  root.each do |word|
    yield word
  end
end

#inspect ⇒ String

Returns a string representation of the container.

Returns:

  • (String) —

    a string representation of the container.



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

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.

Returns:

  • (Boolean) —

    whether the letter is contained or not.

See Also:



181
182
183
 
# File 'lib/rambling/trie/container.rb', line 181

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.

Returns:

  • (Boolean) —

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

See Also:



71
72
73
 
# File 'lib/rambling/trie/container.rb', line 71

def partial_word? word = ''
  root.partial_word? word.chars
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.

Returns:

  • (Array<String>) —

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

See Also:



91
92
93
 
# File 'lib/rambling/trie/container.rb', line 91

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

#size ⇒ Integer

Size of the Root Node‘s children tree.

Returns:

  • (Integer) —

    the number of letters in the root node.



187
188
189
 
# File 'lib/rambling/trie/container.rb', line 187

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:



173
174
175
 
# File 'lib/rambling/trie/container.rb', line 173

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.

Returns:

  • (Boolean) —

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

See Also:



81
82
83
 
# File 'lib/rambling/trie/container.rb', line 81

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

#words_within(phrase) {|String| ... } ⇒ Enumerator<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.

Yields:

  • (String) —

    each word found in phrase.

Returns:

  • (Enumerator<String>) —

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

See Also:

  • Nodes::Node#words_within


102
103
104
 
# File 'lib/rambling/trie/container.rb', line 102

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.

Returns:

  • (Boolean) —

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

See Also:



111
112
113
 
# File 'lib/rambling/trie/container.rb', line 111

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