Class: TwitterCldr::Collation::Trie

Inherits:
Object
  • Object
show all
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

TrieWithFallback

Defined Under Namespace

Classes: Node

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.



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

Returns:

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

Returns:

  • (Boolean) 


32
33
34
 
# File 'lib/twitter_cldr/collation/trie.rb', line 32

def locked?
  @locked
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 



94
95
96
 
# File 'lib/twitter_cldr/collation/trie.rb', line 94

def to_hash
  @root.subtrie_hash
end