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
Public Class Methods
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
# File lib/twitter_cldr/utils/trie.rb, line 50 def add(key, value) store(key, value, false) end
# 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
# File lib/twitter_cldr/utils/trie.rb, line 46 def empty? !@root.has_children? end
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
# 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
# File lib/twitter_cldr/utils/trie.rb, line 28 def lock @locked = true self end
# File lib/twitter_cldr/utils/trie.rb, line 33 def locked? @locked end
# File lib/twitter_cldr/utils/trie.rb, line 95 def marshal_dump @root end
# File lib/twitter_cldr/utils/trie.rb, line 99 def marshal_load(root) @root = root end
# File lib/twitter_cldr/utils/trie.rb, line 54 def set(key, value) store(key, value) end
# File lib/twitter_cldr/utils/trie.rb, line 37 def starters @root.keys end
# File lib/twitter_cldr/utils/trie.rb, line 103 def to_hash @root.subtrie_hash end
Private Instance Methods
# 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
# 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