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

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

Raises:

See Also:


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

def add word
  root.add char_symbols word
end

#childrenArray<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_treeArray<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

#compressContainer

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

#inspectString

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

#sizeInteger

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_aArray<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