Class: Helium::Trie

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/helium/trie.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value = nil) ⇒ Trie

Returns a new instance of Trie.



6
7
8
9
 
# File 'lib/helium/trie.rb', line 6

def initialize(value = nil)
  @value = value
  @children = {}
end

Instance Attribute Details

#value ⇒ Object

Returns the value of attribute value.



4
5
6
 
# File 'lib/helium/trie.rb', line 4

def value
  @value
end

Instance Method Details

#[](key) ⇒ Object 



25
26
27
28
 
# File 'lib/helium/trie.rb', line 25

def [](key)
  trie = traverse(key)
  trie ? trie.value : nil
end

#[]=(key, value) ⇒ Object 



30
31
32
 
# File 'lib/helium/trie.rb', line 30

def []=(key, value)
  traverse(key, true).value = value
end

#each(key = [], &block) ⇒ Object 



15
16
17
18
 
# File 'lib/helium/trie.rb', line 15

def each(key = [], &block)
  each_child { |prefix, trie| trie.each(key + [prefix], &block) }
  block.call(key, @value) unless @value.nil?
end

#each_child(&block) ⇒ Object 



11
12
13
 
# File 'lib/helium/trie.rb', line 11

def each_child(&block)
  @children.keys.sort.each { |key| block.call(key, @children[key]) }
end

#has_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


20
21
22
23
 
# File 'lib/helium/trie.rb', line 20

def has_key?(key)
  trie = traverse(key)
  trie and not trie.value.nil?
end

#inspect ⇒ Object 



43
44
45
 
# File 'lib/helium/trie.rb', line 43

def inspect
  @children.inspect
end

#traverse(key, create_if_absent = false) ⇒ Object 



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

def traverse(key, create_if_absent = false)
  key = convert_key(key)
  return self if key.empty?
  trie = @children[key.first]
  return nil if trie.nil? and not create_if_absent
  trie = @children[key.first] = Trie.new if trie.nil?
  trie.traverse(key[1..-1], create_if_absent)
end