Class: CompSci::CompleteNaryTree

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

Overview

A CompleteNaryTree can very efficiently use an array for storage using simple arithmetic to determine parent child relationships.

It is kept separate from compsci/tree as it does not require compsci/node

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(array: [], child_slots: 2) ⇒ CompleteNaryTree

Returns a new instance of CompleteNaryTree.



30
31
32
33
 
# File 'lib/compsci/complete_tree.rb', line 30

def initialize(array: [], child_slots: 2)
  @array = array
  @child_slots = child_slots
end

Instance Attribute Details

#array ⇒ Object (readonly)

Returns the value of attribute array.



28
29
30
 
# File 'lib/compsci/complete_tree.rb', line 28

def array
  @array
end

Class Method Details

.children_idx(idx, n) ⇒ Object 



13
14
15
 
# File 'lib/compsci/complete_tree.rb', line 13

def self.children_idx(idx, n)
  Array.new(n) { |i| n*idx + i + 1 }
end

.gen(idx, n) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
 
# File 'lib/compsci/complete_tree.rb', line 17

def self.gen(idx, n)
  count = 0
  loop {
    pidx = self.parent_idx(idx, n)
    break if pidx < 0
    count += 1
    idx = pidx
  }
  count
end

.parent_idx(idx, n) ⇒ Object

integer math maps several children to one parent



9
10
11
 
# File 'lib/compsci/complete_tree.rb', line 9

def self.parent_idx(idx, n)
  (idx-1) / n
end

Instance Method Details

#bf_search(&blk) ⇒ Object

or, ya know, just iterate @array



52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/compsci/complete_tree.rb', line 52

def bf_search(&blk)
  destinations = [0]
  while !destinations.empty?
    idx = destinations.shift
    return idx if yield @array[idx]

    # idx has a val and the block is false
    # add existent children to destinations
    self.class.children_idx(idx, @child_slots).each { |cidx|
      destinations.push(cidx) if cidx < @array.size
    }
  end
end

#df_search(&blk) ⇒ Object 



66
67
68
 
# File 'lib/compsci/complete_tree.rb', line 66

def df_search(&blk)
  puts "not yet"
end

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



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/compsci/complete_tree.rb', line 70

def display(width: 80)
  str = ''
  old_level = 0
  @array.each_with_index { |val, i|
    val = val.to_s
    level = self.class.gen(i, @child_slots)
    if old_level != level
      str += "\n"
      old_level = level
    end

    # center in block_width
    slots = @child_slots**level
    block_width = width / slots
    space = [(block_width + val.size) / 2, val.size + 1].max
    str += val.ljust(space, ' ').rjust(block_width, ' ')
  }
  str
end

#last_idx ⇒ Object 



47
48
49
 
# File 'lib/compsci/complete_tree.rb', line 47

def last_idx
  @array.size - 1 unless @array.empty?
end

#pop ⇒ Object 



39
40
41
 
# File 'lib/compsci/complete_tree.rb', line 39

def pop
  @array.pop
end

#push(val) ⇒ Object 



35
36
37
 
# File 'lib/compsci/complete_tree.rb', line 35

def push val
  @array.push val
end

#size ⇒ Object 



43
44
45
 
# File 'lib/compsci/complete_tree.rb', line 43

def size
  @array.size
end