Class: Hipe::SimpleBTree::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/hipe-simplebtree.rb

Overview

just to be incendiary, we don’t distinguish among leaf nodes, branch nodes, and root nodes.

Instance Method Summary collapse

Constructor Details

#initialize(ary, start_index, end_index, depth = 0) ⇒ Tree

Returns a new instance of Tree.



363
364
365
366
367
368
369
370
371
372
 
# File 'lib/hipe-simplebtree.rb', line 363

def initialize(ary, start_index, end_index, depth=0)
  @depth = depth
  width = end_index - start_index + 1
  value_index = start_index + width / 2 
  value_index -= 1 if depth % 2 == 0 and width % 2 == 0 and width != 1
  @key = ary[value_index]
  @index = value_index # careful to keep it synced with key!
  @left = (value_index == start_index) ? nil : Tree.new(ary, start_index, value_index-1, depth + 1)
  @right = (value_index == end_index)  ? nil : Tree.new(ary, value_index + 1, end_index, depth + 1)       
end

Instance Method Details

#lower_bound_index(key) ⇒ Object

(inside of lower boundary). If there is no such key, returns nil.



396
397
398
 
# File 'lib/hipe-simplebtree.rb', line 396

def lower_bound_index key
  (@key >= key) ?  ((@left && @left.lower_bound_index(key)) || @index) : (@right && @right.lower_bound_index(key))
end

#stats ⇒ Object 



374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/hipe-simplebtree.rb', line 374

def stats
  heights = [1]
  mins = [] 
  num_nodes = 1
  ['@left','@right'].each do |name|
    child = instance_variable_get(name)
    if (child)
      stats = child.stats
      heights << stats[:height] + 1
      mins    << stats[:min_height]
      num_nodes += stats[:num_nodes] 
    end
  end
  {
    :height => heights.max,
    :min_height => (mins.size==0) ? 1 : (mins.min + 1),
    :num_nodes => num_nodes
  } 
end

#upper_bound_index(key) ⇒ Object

(inside of upper boundary). If there is no such key, returns nil.

Returns:

  • the index of the greatest key that is equal to or lower than the given key



402
403
404
 
# File 'lib/hipe-simplebtree.rb', line 402

def upper_bound_index key
  (@key <= key) ?  ((@right && @right.upper_bound_index(key)) || @index) : (@left && @left.upper_bound_index(key))
end