class Containers::PrefixTree

Public Class Methods

new() click to toggle source
# File lib/containers/prefix_tree.rb, line 12
def initialize
  @root = Node.new
end

Public Instance Methods

<<(str, value = true) click to toggle source
# File lib/containers/prefix_tree.rb, line 16
def <<(str, value = true)
  insert(str, value)
end
[](str) click to toggle source
# File lib/containers/prefix_tree.rb, line 29
def [](str)
  find(str)
end
count_partial(str) click to toggle source
# File lib/containers/prefix_tree.rb, line 43
def count_partial(str)
  current = @root
  str.each_char do |c|
    return 0 if current.children[c].nil?

    current = current.children[c]
  end
  stack = List.new
  count = 0
  current.children.each_value(&stack.method(:push))
  until stack.empty?
    current = stack.pop
    count += 1 unless current.data.nil?
    current.children.each_value(&stack.method(:push))
  end
  count
end
find(str) click to toggle source
# File lib/containers/prefix_tree.rb, line 33
def find(str)
  current = @root
  str.each_char do |c|
    return nil if current.children[c].nil?

    current = current.children[c]
  end
  current.data
end
insert(str, value = true) click to toggle source
# File lib/containers/prefix_tree.rb, line 20
def insert(str, value = true)
  current = @root
  str.each_char do |c|
    current.children[c] = Node.new if current.children[c].nil?
    current = current.children[c]
  end
  current.data = value
end