Class: DS::Trie::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/ds/trees/trie/node.rb

Overview

Trie node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value = nil) ⇒ Node

Returns a new instance of Node.



8
9
10
11
 
# File 'lib/ds/trees/trie/node.rb', line 8

def initialize(value = nil)
  @children = []
  @data = value
end

Instance Attribute Details

#children ⇒ Object (readonly)

Returns the value of attribute children.



6
7
8
 
# File 'lib/ds/trees/trie/node.rb', line 6

def children
  @children
end

#data ⇒ Object (readonly)

Returns the value of attribute data.



6
7
8
 
# File 'lib/ds/trees/trie/node.rb', line 6

def data
  @data
end

Instance Method Details

#delete(s, trie) ⇒ Object 



32
33
34
35
36
37
38
39
 
# File 'lib/ds/trees/trie/node.rb', line 32

def delete(s, trie)
  return true if s.empty?
  index = trie.key(s.first)
  flag = @children[index].delete(s[1..-1], trie)
  flag &&= one_child?
  @children[index] = nil if flag
  s.size < 2 ? true : flag && @data.nil?
end

#get(s, trie) ⇒ Object 



23
24
25
26
27
28
29
30
 
# File 'lib/ds/trees/trie/node.rb', line 23

def get(s, trie)
  if s.empty?
    self
  else
    index = trie.key(s.first)
    @children[index].get(s[1..-1], trie) if @children[index]
  end
end

#put(s, value, trie) ⇒ Object 



13
14
15
16
17
18
19
20
21
 
# File 'lib/ds/trees/trie/node.rb', line 13

def put(s, value, trie)
  if s.empty?
    @data = value
  else
    index = trie.key(s.first)
    @children[index] ||= Node.new
    @children[index].put(s[1..-1], value, trie)
  end
end