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

Returns the value of attribute array.

Class Method Summary collapse

• integer math maps several children to one parent.

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

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) ⇒ ObjectAlso 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```