Class: Containers::PrefixTree

Inherits:
Object
  • Object
show all
Defined in:
lib/containers/prefix_tree.rb

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PrefixTree

Returns a new instance of PrefixTree.



12
13
14
 
# File 'lib/containers/prefix_tree.rb', line 12

def initialize
  @root = Node.new
end

Instance Method Details

#<<(str, value = true) ⇒ Object 



16
17
18
 
# File 'lib/containers/prefix_tree.rb', line 16

def <<(str, value = true)
  insert(str, value)
end

#[](str) ⇒ Object 



29
30
31
 
# File 'lib/containers/prefix_tree.rb', line 29

def [](str)
  find(str)
end

#count_partial(str) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/containers/prefix_tree.rb', line 43

def count_partial(str)
  current = @root
  str.each_char do |c|
    return 0 if current.children[c].nil?

    current = current.children[c]
  end
  stack = List.new
  count = 0
  current.children.each_value(&stack.method(:push))
  until stack.empty?
    current = stack.pop
    count += 1 unless current.data.nil?
    current.children.each_value(&stack.method(:push))
  end
  count
end

#find(str) ⇒ Object 



33
34
35
36
37
38
39
40
41
 
# File 'lib/containers/prefix_tree.rb', line 33

def find(str)
  current = @root
  str.each_char do |c|
    return nil if current.children[c].nil?

    current = current.children[c]
  end
  current.data
end

#insert(str, value = true) ⇒ Object 



20
21
22
23
24
25
26
27
 
# File 'lib/containers/prefix_tree.rb', line 20

def insert(str, value = true)
  current = @root
  str.each_char do |c|
    current.children[c] = Node.new if current.children[c].nil?
    current = current.children[c]
  end
  current.data = value
end