Class: DcUtil::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/dc_util/node.rb

Overview

a data structure used in tree-like operations.

Direct Known Subclasses

BinaryNode

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}) ⇒ Node

Returns a new instance of Node.



6
7
8
9
 
# File 'lib/dc_util/node.rb', line 6

def initialize(options={})
  self.data = options[:data]
  self.children = []
end

Instance Attribute Details

#children ⇒ Object

Returns the value of attribute children.



4
5
6
 
# File 'lib/dc_util/node.rb', line 4

def children
  @children
end

#data ⇒ Object

Returns the value of attribute data.



4
5
6
 
# File 'lib/dc_util/node.rb', line 4

def data
  @data
end

#parent ⇒ Object

Returns the value of attribute parent.



4
5
6
 
# File 'lib/dc_util/node.rb', line 4

def parent
  @parent
end

Class Method Details

.bfs(node, queue, exclude_root, &block) ⇒ Object

breath first search



13
14
15
16
17
18
19
 
# File 'lib/dc_util/node.rb', line 13

def bfs(node, queue, exclude_root, &block)
  return if node.nil?
  block.call(node) unless exclude_root

  node.children.each{|x| queue.push(x)}
  bfs(queue.shift, queue, false, &block)
end

.bfs_non_recursive(node, queue, exclude_root, &block) ⇒ Object

breath first search, non recursive style to prevent stack overflow



22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/dc_util/node.rb', line 22

def bfs_non_recursive(node, queue, exclude_root, &block)
  return if node.nil?
  queue.push(node)
  
  while not queue.empty?
    node = queue.shift
    block.call(node) unless exclude_root
    node.children.each{|x| queue.push(x)}
    exclude_root = false
  end
end

.dfs(node, exclude_root, &block) ⇒ Object

depth first search



35
36
37
38
 
# File 'lib/dc_util/node.rb', line 35

def dfs(node, exclude_root, &block)
  block.call(node) unless exclude_root
  node.children.each{|x| dfs(x, false, &block)}
end

Instance Method Details

#add(node) ⇒ Object

add a child node.

Raises:

  • (ArgumentError) 


42
43
44
45
46
 
# File 'lib/dc_util/node.rb', line 42

def add(node)
  raise ArgumentError.new("not a valid node class") unless node.kind_of? self.class
  children << node
  node.parent = self
end

#bfs(exclude_root = false, &block) ⇒ Object

breath first search

root.bfs{|node| puts node.inspect}

root.bfs(true){|node| puts node.inspect}  # skip first node



56
57
58
59
 
# File 'lib/dc_util/node.rb', line 56

def bfs(exclude_root=false, &block)
  # self.class.bfs(self, [], exclude_root, &block)
  self.class.bfs_non_recursive(self, [], exclude_root, &block)
end

#dfs(exclude_root = false, &block) ⇒ Object

depth first search

root.dfs{|node| puts node.inspect}

root.dfs(true){|node| puts node.inspect}  # skip first node



65
66
67
 
# File 'lib/dc_util/node.rb', line 65

def dfs(exclude_root=false, &block)
  self.class.dfs(self, exclude_root, &block)
end

#leaves ⇒ Object

return all nodes that has no children



70
71
72
73
74
75
76
 
# File 'lib/dc_util/node.rb', line 70

def leaves
  arr = []
  self.dfs do |node|
    arr << node if node.children.empty?
  end
  arr
end

#parents ⇒ Object 



48
49
50
 
# File 'lib/dc_util/node.rb', line 48

def parents
  parent ? [parent] + parent.parents : []
end

#tree_size ⇒ Object

return all nodes count



79
80
81
82
83
 
# File 'lib/dc_util/node.rb', line 79

def tree_size
  n = 0
  dfs{|x| n += 1}
  n
end