Class: Attentive::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/attentive/trie.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(depth: 0) ⇒ Trie

Returns a new instance of Trie.



5
6
7
8
 
# File 'lib/attentive/trie.rb', line 5

def initialize(depth: 0)
  @depth = depth
  @children = {}
end

Instance Attribute Details

#depth ⇒ Object (readonly)

Returns the value of attribute depth.



3
4
5
 
# File 'lib/attentive/trie.rb', line 3

def depth
  @depth
end

Class Method Details

.of_substitutions(substitutions) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
 
# File 'lib/attentive/trie.rb', line 33

def self.of_substitutions(substitutions)
  substitutions.each_with_object(self.new) do |(tokens, substitution), trie|
    leaf = trie
    tokens.each_with_index do |token, i|
      raise "#{tokens.join} contains #{tokens[0...i].join}" if leaf.fin?
      leaf = leaf.add token
    end
    leaf.fin! substitution
  end
end

Instance Method Details

#[](token) ⇒ Object 



10
11
12
 
# File 'lib/attentive/trie.rb', line 10

def [](token)
  @children[token]
end

#add(token) ⇒ Object 



14
15
16
17
 
# File 'lib/attentive/trie.rb', line 14

def add(token)
  raise "Can't add #{token.inspect} to trie because this leaf is a terminus" if fin?
  @children[token] ||= self.class.new(depth: depth + 1)
end

#fin ⇒ Object 



23
24
25
 
# File 'lib/attentive/trie.rb', line 23

def fin
  @children[:fin]
end

#fin!(finish) ⇒ Object 



27
28
29
 
# File 'lib/attentive/trie.rb', line 27

def fin!(finish)
  @children[:fin] = finish
end

#fin? ⇒ Boolean

Returns:

  • (Boolean) 


19
20
21
 
# File 'lib/attentive/trie.rb', line 19

def fin?
  @children.key?(:fin)
end