Class: TwitterCldr::Utils::Trie

Inherits:
Object
  • Object
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).

Direct Known Subclasses

Collation::TrieWithFallback

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

#rootObject (readonly)

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

Returns:

  • (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

#lockObject



28
29
30
31
# File 'lib/twitter_cldr/utils/trie.rb', line 28

def lock
  @locked = true
  self
end

#locked?Boolean

Returns:

  • (Boolean)


33
34
35
# File 'lib/twitter_cldr/utils/trie.rb', line 33

def locked?
  @locked
end

#marshal_dumpObject



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

#startersObject



37
38
39
# File 'lib/twitter_cldr/utils/trie.rb', line 37

def starters
  @root.keys
end

#to_hashObject



103
104
105
# File 'lib/twitter_cldr/utils/trie.rb', line 103

def to_hash
  @root.subtrie_hash
end