class Rambling::Trie::Container
Wrapper on top of trie data structure.
Attributes
The root node of this trie. @return [Nodes::Node] the root node of this trie.
Public Class Methods
Creates a new trie. @param [Nodes::Node] root the root node for the trie @param [Compressor] compressor responsible for compressing the trie @yield [Container] the trie just created.
# File lib/rambling/trie/container.rb, line 17 def initialize root, compressor @root = root @compressor = compressor yield self if block_given? end
Public Instance Methods
Compares two trie data structures. @param [Container] other the trie to compare against. @return [Boolean] `true` if the tries are equal, `false` otherwise.
# File lib/rambling/trie/container.rb, line 118 def == other root == other.root end
Get {Nodes::Node Node} corresponding to a given letter. @param [Symbol] letter the letter to search for in the root node. @return [Nodes::Node] the node corresponding to that letter. @see Nodes::Node#[]
# File lib/rambling/trie/container.rb, line 141 def [] letter root[letter] end
Adds a word to the trie. @param [String] word the word to add the branch from. @return [Nodes::Node] the just added branch's root node. @raise [InvalidOperation] if the trie is already compressed. @see Nodes::Raw#add
@see Nodes::Compressed#add
# File lib/rambling/trie/container.rb, line 30 def add word root.add char_symbols word end
Root node's child nodes. @return [Array<Nodes::Node>] the array of children nodes contained in
the root node.
@see Nodes::Node#children
# File lib/rambling/trie/container.rb, line 149 def children root.children end
Root node's children tree. @return [Array<Nodes::Node>] the array of children nodes contained in
the root node.
@see Nodes::Node#children_tree
# File lib/rambling/trie/container.rb, line 157 def children_tree root.children_tree end
Compresses the existing trie using redundant node elimination. Returns a new trie with the compressed root. @return [Container] A new {Container} with the {Nodes::Compressed
Compressed} root node or self if the trie has already been compressed.
# File lib/rambling/trie/container.rb, line 60 def compress return self if root.compressed? Rambling::Trie::Container.new compress_root, compressor end
Compresses the existing trie using redundant node elimination. Marks the trie as compressed. Does nothing if the trie has already been compressed. @return [Container] self @note This method replaces the root {Nodes::Raw Raw} node with a
{Nodes::Compressed Compressed} version of it.
# File lib/rambling/trie/container.rb, line 50 def compress! self.root = compress_root unless root.compressed? self end
Indicates if the root {Nodes::Node Node} can be compressed or not. @return [Boolean] `true` for non-{Nodes::Node#terminal? terminal}
nodes with one child, `false` otherwise.
# File lib/rambling/trie/container.rb, line 165 def compressed? root.compressed? end
Adds all provided words to the trie. @param [Array<String>] words the words to add the branch from. @return [Array<Nodes::Node>] the collection of nodes added. @raise [InvalidOperation] if the trie is already compressed. @see Nodes::Raw#add
@see Nodes::Compressed#add
# File lib/rambling/trie/container.rb, line 40 def concat words words.map { |word| add word } end
Iterates over the words contained in the trie. @yield [String] the words contained in this trie node.
# 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
@return [String] a string representation of the container.
# File lib/rambling/trie/container.rb, line 133 def inspect "#<#{self.class.name} root: #{root.inspect}>" end
Check if a letter is part of the root {Nodes::Node}'s children tree. @param [Symbol] letter the letter to search for in the root node. @return [Boolean] whether the letter is contained or not. @see Nodes::Node#key?
# File lib/rambling/trie/container.rb, line 181 def key? letter root.key? letter end
Checks if a path for a word or partial word exists in the trie. @param [String] word the word or partial word to look for in the trie. @return [Boolean] `true` if the word or partial word is found, `false`
otherwise.
@see Nodes::Raw#partial_word?
@see Nodes::Compressed#partial_word?
# File lib/rambling/trie/container.rb, line 71 def partial_word? word = '' root.partial_word? word.chars end
Returns all words that start with the specified characters. @param [String] word the word to look for in the trie. @return [Array<String>] all the words contained in the trie that start
with the specified characters.
@see Nodes::Raw#scan
@see Nodes::Compressed#scan
# File lib/rambling/trie/container.rb, line 91 def scan word = '' root.scan(word.chars).to_a end
Size of the Root {Nodes::Node Node}'s children tree. @return [Integer] the number of letters in the root node.
# File lib/rambling/trie/container.rb, line 187 def size root.size end
Array of words contained in the root {Nodes::Node Node}. @return [Array<String>] all words contained in this trie. @see ruby-doc.org/core-2.5.0/Enumerable.html#method-i-to_a
Enumerable#to_a
# File lib/rambling/trie/container.rb, line 173 def to_a root.to_a end
Checks if a whole word exists in the trie. @param [String] word the word to look for in the trie. @return [Boolean] `true` only if the word is found and the last
character corresponds to a terminal node, `false` otherwise.
@see Nodes::Raw#word?
@see Nodes::Compressed#word?
# File lib/rambling/trie/container.rb, line 81 def word? word = '' root.word? word.chars end
Returns all words within a string that match a word contained in the trie. @param [String] phrase the string to look for matching words in. @return [Enumerator<String>] all the words in the given string that
match a word in the trie.
@yield [String] each word found in phrase. @see Nodes::Node#words_within
# File lib/rambling/trie/container.rb, line 102 def words_within phrase words_within_root(phrase).to_a end
Checks if there are any valid words in a given string. @param [String] phrase the string to look for matching words in. @return [Boolean] `true` if any word within phrase is contained in the
trie, `false` otherwise.
# File lib/rambling/trie/container.rb, line 111 def words_within? phrase words_within_root(phrase).any? end
Private Instance Methods
# File lib/rambling/trie/container.rb, line 219 def char_symbols word symbols = [] word.reverse.each_char { |c| symbols << c.to_sym } symbols end
# File lib/rambling/trie/container.rb, line 215 def compress_root compressor.compress root end
# File lib/rambling/trie/container.rb, line 203 def words_within_root phrase return enum_for :words_within_root, phrase unless block_given? chars = phrase.chars 0.upto(chars.length - 1).each do |starting_index| new_phrase = chars.slice starting_index..(chars.length - 1) root.match_prefix new_phrase do |word| yield word end end end