class TwitterCldr::Utils::Trie

This class represents a trie - a tree data structure, also known as a prefix tree.

Every node corresponds to a single character of the key. To find the value by key one goes down the trie starting from the root and descending one character at a time. If at some level current node doesn't have a child corresponding to the next character of the key, then the trie doesn't contain a value with the given key. Otherwise, the final node, corresponding to the last character of the key, should contain the value. If it's nil, then the trie doesn't contain a value with the given key (or the value itself is nil).

Attributes

root[R]

Public Class Methods

new(root = Node.new) click to toggle source

Initializes a new trie. If `trie_hash` value is passed it's used as the initial data for the trie. Usually, `trie_hash` is extracted from other trie and represents its subtrie.

# File lib/twitter_cldr/utils/trie.rb, line 23
def initialize(root = Node.new)
  @root = root
  @locked = false
end

Public Instance Methods

add(key, value) click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 50
def add(key, value)
  store(key, value, false)
end
each_starting_with(starter, &block) click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 41
def each_starting_with(starter, &block)
  starting_node = @root.child(starter)
  each_pair(starting_node, [starter], &block) if starting_node
end
empty?() click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 46
def empty?
  !@root.has_children?
end
find_prefix(key) click to toggle source

Finds the longest substring of the `key` that matches, as a key, a node in the trie.

Returns a three elements array:

1. value in the last node that was visited and has non-nil value
2. size of the `key` prefix that matches this node
3. subtrie for which that node is a root
# File lib/twitter_cldr/utils/trie.rb, line 75
def find_prefix(key)
  last_prefix_size = 0
  last_with_value  = @root

  key.each_with_index.inject(@root) do |node, (key_element, index)|
    child = node.child(key_element)

    break unless child

    if child.value
      last_prefix_size = index + 1
      last_with_value  = child
    end

    child
  end

  [last_with_value.value, last_prefix_size, last_with_value.to_trie]
end
get(key) click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 58
def get(key)
  final = key.inject(@root) do |node, key_element|
    return unless node
    node.child(key_element)
  end

  final && final.value
end
lock() click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 28
def lock
  @locked = true
  self
end
locked?() click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 33
def locked?
  @locked
end
marshal_dump() click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 95
def marshal_dump
  @root
end
marshal_load(root) click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 99
def marshal_load(root)
  @root = root
end
set(key, value) click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 54
def set(key, value)
  store(key, value)
end
starters() click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 37
def starters
  @root.keys
end
to_hash() click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 103
def to_hash
  @root.subtrie_hash
end

Private Instance Methods

each_pair(node, key) { |key, value| ... } click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 121
def each_pair(node, key, &block)
  yield [key, node.value] if node.value

  node.each_key_and_child do |key_element, child|
    each_pair(child, key + [key_element], &block)
  end
end
store(key, value, override = true) click to toggle source
# File lib/twitter_cldr/utils/trie.rb, line 111
def store(key, value, override = true)
  raise RuntimeError, "can't store value in a locked trie" if locked?

  final = key.inject(@root) do |node, key_element|
    node.child(key_element) || node.set_child(key_element, Node.new)
  end

  final.value = value unless final.value && !override
end