Class: CompSci::CompleteTree

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

Overview

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

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

Returns a new instance of CompleteTree.



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

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.



26
27
28
 
# File 'lib/compsci/complete_tree.rb', line 26

def array
  @array
end

Class Method Details

.children_idx(idx, n) ⇒ Object 



11
12
13
 
# File 'lib/compsci/complete_tree.rb', line 11

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

.gen(idx, n) ⇒ Object 



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

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



7
8
9
 
# File 'lib/compsci/complete_tree.rb', line 7

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

Instance Method Details

#bf_search(&blk) ⇒ Object

or, ya know, just iterate @array



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

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 



64
65
66
 
# File 'lib/compsci/complete_tree.rb', line 64

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

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

TODO: fixme



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

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 



45
46
47
 
# File 'lib/compsci/complete_tree.rb', line 45

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

#pop ⇒ Object 



37
38
39
 
# File 'lib/compsci/complete_tree.rb', line 37

def pop
  @array.pop
end

#push(val) ⇒ Object 



33
34
35
 
# File 'lib/compsci/complete_tree.rb', line 33

def push val
  @array.push val
end

#size ⇒ Object 



41
42
43
 
# File 'lib/compsci/complete_tree.rb', line 41

def size
  @array.size
end