Class: TwitterCldr::Utils::Trie
- Inherits:
-
Object
- Object
- TwitterCldr::Utils::Trie
show all
- Defined in:
- lib/twitter_cldr/utils/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).
Defined Under Namespace
Classes: Node
Instance Attribute Summary collapse
Instance Method Summary
collapse
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.
23
24
25
26
|
# File 'lib/twitter_cldr/utils/trie.rb', line 23
def initialize(root = Node.new)
@root = root
@locked = false
end
|
Instance Attribute Details
#root ⇒ Object
Returns the value of attribute root.
18
19
20
|
# File 'lib/twitter_cldr/utils/trie.rb', line 18
def root
@root
end
|
Instance Method Details
#add(key, value) ⇒ Object
50
51
52
|
# File 'lib/twitter_cldr/utils/trie.rb', line 50
def add(key, value)
store(key, value, false)
end
|
#each_starting_with(starter, &block) ⇒ Object
41
42
43
44
|
# 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? ⇒ Boolean
46
47
48
|
# File 'lib/twitter_cldr/utils/trie.rb', line 46
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
# 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) ⇒ Object
58
59
60
61
62
63
64
65
|
# 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 ⇒ Object
28
29
30
31
|
# File 'lib/twitter_cldr/utils/trie.rb', line 28
def lock
@locked = true
self
end
|
#locked? ⇒ Boolean
33
34
35
|
# File 'lib/twitter_cldr/utils/trie.rb', line 33
def locked?
@locked
end
|
#marshal_dump ⇒ Object
95
96
97
|
# File 'lib/twitter_cldr/utils/trie.rb', line 95
def marshal_dump
@root
end
|
#marshal_load(root) ⇒ Object
99
100
101
|
# File 'lib/twitter_cldr/utils/trie.rb', line 99
def marshal_load(root)
@root = root
end
|
#set(key, value) ⇒ Object
54
55
56
|
# File 'lib/twitter_cldr/utils/trie.rb', line 54
def set(key, value)
store(key, value)
end
|
#starters ⇒ Object
37
38
39
|
# File 'lib/twitter_cldr/utils/trie.rb', line 37
def starters
@root.keys
end
|
#to_hash ⇒ Object
103
104
105
|
# File 'lib/twitter_cldr/utils/trie.rb', line 103
def to_hash
@root.subtrie_hash
end
|