Class: TwitterCldr::Collation::Trie
- Inherits:
-
Object
- Object
- TwitterCldr::Collation::Trie
- Defined in:
- lib/twitter_cldr/collation/trie.rb
Overview
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).
Direct Known Subclasses
Defined Under Namespace
Classes: Node
Instance Method Summary collapse
- #add(key, value) ⇒ Object
- #each_starting_with(starter, &block) ⇒ Object
- #empty? ⇒ Boolean
-
#find_prefix(key) ⇒ Object
Finds the longest substring of the ‘key` that matches, as a key, a node in the trie.
- #get(key) ⇒ Object
-
#initialize(root = Node.new) ⇒ Trie
constructor
Initializes a new trie.
- #lock ⇒ Object
- #locked? ⇒ Boolean
- #marshal_dump ⇒ Object
- #marshal_load(root) ⇒ Object
- #set(key, value) ⇒ Object
- #starters ⇒ Object
- #to_hash ⇒ Object
Constructor Details
#initialize(root = Node.new) ⇒ Trie
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.
22 23 24 25 |
# File 'lib/twitter_cldr/collation/trie.rb', line 22 def initialize(root = Node.new) @root = root @locked = false end |
Instance Method Details
#add(key, value) ⇒ Object
49 50 51 |
# File 'lib/twitter_cldr/collation/trie.rb', line 49 def add(key, value) store(key, value, false) end |
#each_starting_with(starter, &block) ⇒ Object
40 41 42 43 |
# File 'lib/twitter_cldr/collation/trie.rb', line 40 def each_starting_with(starter, &block) starting_node = @root.child(starter) each_pair(starting_node, [starter], &block) if starting_node end |
#empty? ⇒ Boolean
45 46 47 |
# File 'lib/twitter_cldr/collation/trie.rb', line 45 def empty? !@root.has_children? end |
#find_prefix(key) ⇒ Object
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
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
# File 'lib/twitter_cldr/collation/trie.rb', line 74 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) ⇒ Object
57 58 59 60 61 62 63 64 |
# File 'lib/twitter_cldr/collation/trie.rb', line 57 def get(key) final = key.inject(@root) do |node, key_element| return unless node node.child(key_element) end final && final.value end |
#lock ⇒ Object
27 28 29 30 |
# File 'lib/twitter_cldr/collation/trie.rb', line 27 def lock @locked = true self end |
#locked? ⇒ Boolean
32 33 34 |
# File 'lib/twitter_cldr/collation/trie.rb', line 32 def locked? @locked end |
#marshal_dump ⇒ Object
94 95 96 |
# File 'lib/twitter_cldr/collation/trie.rb', line 94 def marshal_dump @root end |
#marshal_load(root) ⇒ Object
98 99 100 |
# File 'lib/twitter_cldr/collation/trie.rb', line 98 def marshal_load(root) @root = root end |
#set(key, value) ⇒ Object
53 54 55 |
# File 'lib/twitter_cldr/collation/trie.rb', line 53 def set(key, value) store(key, value) end |
#starters ⇒ Object
36 37 38 |
# File 'lib/twitter_cldr/collation/trie.rb', line 36 def starters @root.keys end |
#to_hash ⇒ Object
102 103 104 |
# File 'lib/twitter_cldr/collation/trie.rb', line 102 def to_hash @root.subtrie_hash end |