Class: CompSci::NaryTree

Inherits:
Tree
  • Object
show all
Defined in:
lib/compsci/tree.rb

Direct Known Subclasses

BinaryTree, QuaternaryTree, TernaryTree

Instance Attribute Summary collapse

Attributes inherited from Tree

#root

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Tree

#bf_search, #df_search, #df_search_generic

Constructor Details

#initialize(node_class, val, child_slots:) ⇒ NaryTree

Returns a new instance of NaryTree.



56
57
58
59
 
# File 'lib/compsci/tree.rb', line 56

def initialize(node_class, val, child_slots:)
  super(node_class, val)
  @child_slots = child_slots
end

Instance Attribute Details

#child_slots ⇒ Object (readonly)

Returns the value of attribute child_slots.



54
55
56
 
# File 'lib/compsci/tree.rb', line 54

def child_slots
  @child_slots
end

Class Method Details

.power_of?(num, base) ⇒ Boolean

thanks apeiros gist.github.com/rickhull/d0b579aa08c85430b0dc82a791ff12d6

Returns:

  • (Boolean) 


47
48
49
50
51
52
 
# File 'lib/compsci/tree.rb', line 47

def self.power_of?(num, base)
  return false if base <= 1
  mod = 0
  num, mod = num.divmod(base) until num == 1 || mod > 0
  mod == 0
end

Instance Method Details

#display(width: nil) ⇒ Object Also known as: to_s 



84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/compsci/tree.rb', line 84

def display(width: nil)
  str = ''
  old_level = 0
  width ||= @child_slots * 40
  self.bf_search { |node|
    raise "#{node.class} not yet supported" unless node.respond_to? :gen
    level = node.gen
    if old_level != level
      str += "\n"
      old_level = level
    end
    # center in block_width
    slots = @child_slots**level
    block_width = width / slots
    val = node.to_s
    space = [(block_width + val.size) / 2, val.size + 1].max
    str += val.ljust(space, ' ').rjust(block_width, ' ')
    false
  }
  str
end

#open_parent ⇒ Object 



72
73
74
75
76
77
78
 
# File 'lib/compsci/tree.rb', line 72

def open_parent
  @open_parent ||= @root
  return @open_parent if self.open_parent?(@open_parent)
  open_sibling = self.open_sibling
  return @open_parent = open_sibling if open_sibling
  @open_parent = self.bf_search { |n| self.open_parent?(n) }
end

#open_parent?(node) ⇒ Boolean

Returns:

  • (Boolean) 


61
62
63
 
# File 'lib/compsci/tree.rb', line 61

def open_parent?(node)
  node.children.size < @child_slots
end

#open_sibling ⇒ Object 



65
66
67
68
69
70
 
# File 'lib/compsci/tree.rb', line 65

def open_sibling
  # try siblings first, only possible with Node#parent
  if @open_parent.respond_to?(:siblings)
    @open_parent.siblings.find { |s| self.open_parent?(s) }
  end
end

#push(value) ⇒ Object 



80
81
82
 
# File 'lib/compsci/tree.rb', line 80

def push(value)
  self.open_parent.new_child value
end