class Rambling::Trie::Container

Wrapper on top of trie data structure.

Attributes

compressor[R]
root[RW]

The root node of this trie. @return [Nodes::Node] the root node of this trie.

Public Class Methods

new(root, compressor) { |self| ... } click to toggle source

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

<<(word)
Alias for: add
==(other) click to toggle source

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
[](letter) click to toggle source

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
add(word) click to toggle source

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
Also aliased as: <<
children() click to toggle source

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
children_tree() click to toggle source

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
compress() click to toggle source

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
compress!() click to toggle source

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
compressed?() click to toggle source

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
concat(words) click to toggle source

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
each() { |word| ... } click to toggle source

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
has_key?(letter)
Alias for: key?
has_letter?(letter)
Alias for: key?
include?(word = '')
Alias for: word?
inspect() click to toggle source

@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
key?(letter) click to toggle source

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
Also aliased as: has_key?, has_letter?
match?(word = '')
Alias for: partial_word?
partial_word?(word = '') click to toggle source

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
Also aliased as: match?
scan(word = '') click to toggle source

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
Also aliased as: words
size() click to toggle source

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
to_a() click to toggle source

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
word?(word = '') click to toggle source

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
Also aliased as: include?
words(word = '')
Alias for: scan
words_within(phrase) click to toggle source

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
words_within?(phrase) click to toggle source

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.

@see Container#words_within

# File lib/rambling/trie/container.rb, line 108
def words_within? phrase
  words_within_root(phrase).any?
end

Private Instance Methods

char_symbols(word) click to toggle source
# File lib/rambling/trie/container.rb, line 217
def char_symbols word
  symbols = []
  word.reverse.each_char { |c| symbols << c.to_sym }
  symbols
end
compress_root() click to toggle source
# File lib/rambling/trie/container.rb, line 213
def compress_root
  compressor.compress root
end
words_within_root(phrase) { |word| ... } click to toggle source
# 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