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.



107
108
109
 
# File 'lib/rambling/trie/container.rb', line 107

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:



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

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:



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

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:



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

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.



152
153
154
 
# File 'lib/rambling/trie/container.rb', line 152

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) 


114
115
116
117
118
119
120
 
# File 'lib/rambling/trie/container.rb', line 114

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.



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

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:



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

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

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



84
85
86
 
# File 'lib/rambling/trie/container.rb', line 84

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.



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

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:



159
160
161
 
# File 'lib/rambling/trie/container.rb', line 159

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:



76
77
78
 
# File 'lib/rambling/trie/container.rb', line 76

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.



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

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:



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

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