Class: CompSci::NaryTree

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

Direct Known Subclasses

BinaryTree

Instance Attribute Summary collapse

Attributes inherited from Tree

#root

Instance Method Summary collapse

Methods inherited from Tree

#bf_search, #df_search, #df_search_generic

Constructor Details

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

Returns a new instance of NaryTree.



99
100
101
102
103
 
# File 'lib/compsci/tree.rb', line 99

def initialize(klass, val, child_slots:)
  super(klass, val)
  raise "#{klass}#parent required" unless @root.respond_to? :parent
  @child_slots = child_slots
end

Instance Attribute Details

#child_slots ⇒ Object (readonly)

Returns the value of attribute child_slots.



97
98
99
 
# File 'lib/compsci/tree.rb', line 97

def child_slots
  @child_slots
end

Instance Method Details

#open_parent ⇒ Object 



109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/compsci/tree.rb', line 109

def open_parent
  @open_parent ||= @root
  return @open_parent if self.open_parent?(@open_parent)

  # TODO: ugh, there must be a better way, this is O(n)

  # try siblings first
  if @open_parent.parent
    @open_parent.parent.children.each { |c|
      return @open_parent = c if self.open_parent?(c)
    }
  end
  @open_parent = self.bf_search { |n| self.open_parent?(n) }
end

#open_parent?(node) ⇒ Boolean

Returns:

  • (Boolean) 


105
106
107
 
# File 'lib/compsci/tree.rb', line 105

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

#push(value) ⇒ Object 



124
125
126
 
# File 'lib/compsci/tree.rb', line 124

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