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) {|self| ... } ⇒ Container

Creates a new trie.

Parameters:

  • root (Nodes::Node) —

    the root node for the trie

  • compressor (Compressor) —

    responsible for compressing the trie

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

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



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

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



147
148
149
 
# File 'lib/rambling/trie/container.rb', line 147

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:



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

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:



57
58
59
60
61
 
# File 'lib/rambling/trie/container.rb', line 57

def compress
  return self if root.compressed?

  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) 


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

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.



161
162
163
 
# File 'lib/rambling/trie/container.rb', line 161

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| ... } ⇒ self

Iterates over the words contained in the trie.

Yields:

  • (String) —

    the words contained in this trie node.

Returns:

  • (self) 


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

def each
  return enum_for :each unless block_given?

  root.each { |word| yield word }
end

#inspect ⇒ String

Returns a string representation of the container.

Returns:

  • (String) —

    a string representation of the container.



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

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:



176
177
178
 
# File 'lib/rambling/trie/container.rb', line 176

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:



67
68
69
 
# File 'lib/rambling/trie/container.rb', line 67

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

#push(*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:



78
79
80
 
# File 'lib/rambling/trie/container.rb', line 78

def push *words
  concat words
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:



95
96
97
 
# File 'lib/rambling/trie/container.rb', line 95

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.



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

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:



168
169
170
 
# File 'lib/rambling/trie/container.rb', line 168

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:



87
88
89
 
# File 'lib/rambling/trie/container.rb', line 87

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

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

Yields:

  • (String) —

    each word found in phrase.

Returns:

  • (Array<String>) —

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



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

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