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 [self] the trie just initialized.
# 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 115 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 139 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 147 def children root.children end
Root node’s children tree. @return [Hash<Symbol, Nodes::Node
>] the children tree hash contained in
the root node, consisting of +:letter => node+.
@see Nodes::Node#children_tree
# File lib/rambling/trie/container.rb, line 155 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 [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 163 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. @return [self]
# File lib/rambling/trie/container.rb, line 122 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 131 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 179 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::Node#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::Node#scan
# File lib/rambling/trie/container.rb, line 89 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 185 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.7.0/Enumerable.html#method-i-to_a
Enumerable#to_a
# File lib/rambling/trie/container.rb, line 171 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::Node#word?
# File lib/rambling/trie/container.rb, line 80 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.
# File lib/rambling/trie/container.rb, line 99 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 108 def words_within? phrase words_within_root(phrase).any? end
Private Instance Methods
# File lib/rambling/trie/container.rb, line 217 def char_symbols word symbols = [] word.reverse.each_char { |c| symbols << c.to_sym } symbols end
# File lib/rambling/trie/container.rb, line 213 def compress_root compressor.compress root end
# File lib/rambling/trie/container.rb, line 201 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