Class: CompSci::CompleteTree
- Inherits:
-
Object
- Object
- CompSci::CompleteTree
- 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.
Direct Known Subclasses
CompleteBinaryTree, CompleteQuaternaryTree, CompleteTernaryTree, Heap
Instance Attribute Summary collapse
-
#array ⇒ Object
readonly
Returns the value of attribute array.
Class Method Summary collapse
- .children_idx(idx, n) ⇒ Object
- .gen(idx, n) ⇒ Object
-
.parent_idx(idx, n) ⇒ Object
integer math maps several children to one parent.
Instance Method Summary collapse
-
#bf_search(&blk) ⇒ Object
or, ya know, just iterate @array.
- #df_search(&blk) ⇒ Object
-
#display(width: 80) ⇒ Object
(also: #to_s)
TODO: fixme.
-
#initialize(array: [], child_slots: 2) ⇒ CompleteTree
constructor
A new instance of CompleteTree.
- #last_idx ⇒ Object
- #pop ⇒ Object
- #push(val) ⇒ Object
- #size ⇒ Object
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 |