Class: XRVG::BinaryTree

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

Overview

BinaryTree class

Intro

Optim class to look for predefine ranges for a value. Is actually a binary tree data structure, but used as unlinear space partitioner.

Example

quad = BinaryTree.new( [0.0,1.0, 0.2,0.0, 0.6,1.0,  0.8,0.0, 1.0,1.0]  )
quad.range( 0.5 ); #=> [0.2,0.0,0.6,1.0]

Instance Method Summary collapse

Constructor Details

#initialize(samplelist) ⇒ BinaryTree

:nodoc:



112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/interpolation.rb', line 112

def initialize( samplelist ) #:nodoc:
  quads = []
  ends  = []
  samplelist.foreach(2).pairs do |ppair, pair|
    pindex, pvalue = ppair
    index, value   = pair
    quads << BinaryTreeRange.new( nil, nil, nil, [pindex, pvalue, index, value] )
    ends  << index
  end
  @root = build_quads( quads, ends )
end

Instance Method Details

#build_quads(quads, ends) ⇒ Object

:nodoc:



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/interpolation.rb', line 124

def build_quads( quads, ends ) #:nodoc:
  newquads = []
  newends  = []
  index = 0
  quads.foreach do |quad1, quad2|
    newquads << BinaryTreeRange.new( ends[2*index], quad1, quad2, nil)
    newends  << ends[2*index + 1]
    index += 1
  end
  if newquads.size == 1
    return newquads[0]
  else
    return build_quads( newquads, newends )
  end
end

#range(index) ⇒ Object

utilitary method to retrieve range of index

BinaryTree.new( [0.0,1.0, 0.2,0.0, 0.6,1.0,  0.8,0.0, 1.0,1.0]  ).range( 0.5 ); #=> [0.2,0.0,0.6,1.0]



142
143
144
 
# File 'lib/interpolation.rb', line 142

def range( index )
  return @root.range( index )
end