# Interpolation file.
#
# See
# - +Interpolation+
# - +Interpolator+
# - +InterpolatorBinaryTree+

require 'utils'

module XRVG
# Interpolation module
# = Intro
# Defines an interpolation service from a samplelist that must be a list [value1, index1, value2, index2, ..., valueN, indexN],
# with index between 0.0 and 1.0 and in increasing order.
# value must be an object with + and * scalar operators defined
# = Uses
# Used for example by Palette
# = Future
# Must be extended for all kinds of interpolation (bezier, ...)
module Interpolation
  
  # must be the overloaded method to adapt Interpolation
  #
  # for example, Palette redefines samplelist as
  #  alias samplelist colorlist
  def samplelist()
    raise NotImplementedError.new("#{self.class.name}#samplelist is an abstract method.")
  end

  # must be the overloaded method to adapt Interpolation
  #
  # is usually provided by a side-effect of a :attribute declaration in including class
  def interpoltype()
    return :linear
  end

  # overall computation method
  #
  # from an input between 0.0 and 1.0, returns an interpolated value computed by interpolation method deduced from interpoltype
  def interpolate( dindex )
    return method( self.interpoltype ).call( dindex )
  end

  # computing method
  #
  # from an input between 0.0 and 1.0, returns linear interpolated value
  #
  # interpolate uses + and * scalar operators on interpolation values
  def linear( dindex )
    result = nil
    pindex, pvalue = self.samplelist[0..1]
    self.samplelist.foreach do |index, value|
      if dindex <= index
	if dindex == index
	  return value
	end
	result = pvalue + ((value + (pvalue * (-1.0)) ) * ((dindex - pindex) / (index - pindex )))
	# Trace("pindex #{pindex} pvalue #{pvalue.inspect} index #{index} value #{value.inspect} dindex #{dindex} result #{result.inspect}")
	break
      end
      pvalue, pindex = value, index
    end
    if not result
      result = self.samplelist[-1]
    end
    return result
  end
end

# Buildable interpolator
# 
# Simply instanciated module in a class
class Interpolator
  include Attributable
  attribute :samplelist
  attribute :interpoltype, :linear
  include Interpolation
  include Samplable
  alias apply_sample interpolate
end

class BinaryTreeRange

  def initialize( limit, quadleft, quadright, range=nil )
    @limit     = limit
    @quadleft  = quadleft
    @quadright = quadright
    @range     = range
  end

  def range( index )
    if @limit
      if index < @limit
	return @quadleft.range( index )
      else
	return @quadright.range( index )
      end
    else
      return @range
    end
  end
end

# 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]
class BinaryTree

  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

  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

  # 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]  
  def range( index )
    return @root.range( index )
  end
end
  
# Binary tree interpolator
# 
# Use BinaryTree to retrieve range of values between linear interpolation.
#
# Used in BezierSpline to compute parameter from length.
class InterpolatorBinaryTree < Interpolator

  def compute_quad #:nodoc:
    @quad = BinaryTree.new( self.samplelist )
  end
  
  # - first use BinaryTree range to retrieve range of dindex, 
  # - then linearly interpolate
  def interpolate( dindex )
    if not @quad
      compute_quad
    end
    pindex, pvalue, index, value = @quad.range( dindex )
    if pindex.fequal?(index)
      result = value
    else
      result = pvalue + ((value + pvalue * (-1.0) ) * ((dindex - pindex) / (index - pindex )))
    end
    return result
  end
end
end