function getInterpolatorFunc(interpolatorObj)
{
    return function(x)
    {
        var myx = interpolatorObj.f(x);
        return myx
    }
}

function HermiteInterpolation(data)
{
    this.f = data.f //array 
    this.fp = data.fp
    this.x = data.x
    this.QLIST = new Array()
    if((this.f.length != this.fp.length) && this.f.length != this.x.length)
    {
        alert("domain, range, and derivative did not have length")
        return null
    }
    
    this.interpolate = function()
    {
        var z = new Array()
        var q = new Array()
        var x = this.x
        var n = this.x.length
        for(var i = 0; i < 2*n+1;i++)
        {
            q[i] = new Array()
            for(var j = 0; j < 2*n+1;j++)
                q[i][j] = 0
        }
        for(var i = 0; i < n;i++)
        {
            z[2*i] = this.x[i]
            z[2*i+1] = this.x[i]
            q[0][2*i] = this.f[i]
            q[0][2*i+1] = this.f[i]
            q[1][2*i+1] = this.fp[i]
            
            if(i != 0)
            {
                q[1][2*i] =  (q[0][2*i] - q[0][2*i-1])/(z[2*i]-z[2*i-1])
            }
            
        }
        
        for(var i = 2; i < 2*n+1;i++)
        {
            for(var j = 2; j <= i; j++)
            {
                q[j][i] = (q[j-1][i] - q[j-1][i-1])/(z[i]-z[i-j])
                
            }
        }
        
        for(var i = 0; i < n*2;i++)
        {
            this.QLIST[i] = q[i][i]
        }
        
        var funcStr = String(this.QLIST[0])
        var count = 0
        var xvar = 0
        var polyStr = ""
        for(var i = 1; i < this.QLIST.length;i++)
        {
            if(count == 2)
            {
                count = 0
                //change xvar
                xvar += 1
            }
            if(count == 1)
            {
                polyStr += "*(x-"+String(x[xvar])+")"
                funcStr += "+"+String(this.QLIST[i])+polyStr
            }
            if(count == 0)
            {
                polyStr += "*(x-"+String(x[xvar])+")"
                funcStr += "+"+String(this.QLIST[i])+polyStr
            }
            count += 1
        }
        return new Function("x","return"+" "+funcStr)
        //return the function needed to calculate the interpolated values
    }
}

function CubicSplineInterpolation(data)
{
    this.isClamped = false
    this.f = data.f
    this.x = data.x
    this.n = data.x.length
    this.splines = new Array() //holds the splines for the intervals
    if(this.x.length != this.f.length){alert("domain input length != range output length");return null}
    if(this.n <= 1){alert("Need at least 2 points for interpolation");return null}
    
    this.interpolate = interpolate
    
    if(CubicSplineInterpolation.arguments[1])
    {
        this.isClamped = CubicSplineInterpolation.arguments[1]
        this.FPO = data.FPO
        this.FPN = data.FPN
        if(this.isClamped)
        {
            this.interpolate = clampedInterpolate;
        }
    }
    
    function interpolate()
    {
        
        //creates an array with the constansts corresponding to the
        //cubic spline in the range of [xj to xj+1] over all points
        //the function returned will use a binary search to determine
        //which interval the x is in, then reference into an array
        //to get the cooresponding spline function.
        
        var h = new Array()
        var alpha = new Array()
        var x = this.x
        var a = this.f
        var n = this.n
        for(var i  = 0; i < this.n-1; i++)
        {
            h[i] = x[i+1] - x[i]
        }
        for(var i = 1; i < this.n-1; i++)
        {
            alpha[i] = (3.0/h[i])*(a[i+1] - a[i]) - (3.0/h[i-1])*(a[i]-a[i-1])
        }
        //solve a system of equations
        var l = new Array()
        var u = new Array()
        var z = new Array()
        l[0] = 1
        u[0] = 0
        z[0] = 0
        
        for(var i = 1; i < n-1;i++)
        {
            l[i] = 2*(x[i+1]-x[i-1]) - h[i-1]*u[i-1]
            u[i] = h[i]/l[i]
            z[i] = (alpha[i] - h[i-1]*z[i-1])/l[i]
        }
        
        var c = new Array()
        var b = new Array()
        var d = new Array()
        l[n-1] = 1
        z[n-1] = 0
        c[n-1] = 0
        
        for(var j = n-2; j >= 0; j--)
        {
            c[j] = z[j] - u[j]*c[j+1]
            b[j] = (a[j+1] - a[j])/h[j] - h[j]*(c[j+1]+2.0*c[j])/3.0
            d[j] = (c[j+1] - c[j])/(3*h[j])
            var funcStr = ""
            funcStr = a[j] + " + " + b[j]+"*(x-"+x[j]+")+"+c[j]+"*(x-"+x[j]+")*(x-"+x[j]+")+"+d[j]+"*(x-"+x[j]+")*(x-"+x[j]+")*(x-"+x[j]+");"
            //alert(funcStr)
            this.splines[j] = new Function("x","return " + funcStr)
        }
        return this.splines
    }
    
    function clampedInterpolate()
    {
        var h = new Array()
        var alpha = new Array()
        var x = this.x
        var a = this.f
        var n = this.n
        var FPO = this.FPO
        var FPN = this.FPN
        for(var i  = 0; i < this.n-1; i++)
        {
            h[i] = x[i+1] - x[i]
        }
        
        alpha[0] = 3*(a[1] - a[0])/h[0] - 3*FPO
        alpha[n-1] = 3*FPN - 3*(a[n-1] - a[n-2])/h[n-2]
        
        for(var i = 1; i < this.n-1; i++)
        {
            alpha[i] = (3.0/h[i])*(a[i+1] - a[i]) - (3.0/h[i-1])*(a[i]-a[i-1])
        }
        
        var l = new Array()
        var u = new Array()
        var z = new Array()
        l[0] = 2*h[0]
        u[0] = 0.5
        z[0] = alpha[0]/l[0]
        
        for(var i = 1; i < n-1;i++)
        {
            l[i] = 2*(x[i+1]-x[i-1]) - h[i-1]*u[i-1]
            u[i] = h[i]/l[i]
            z[i] = (alpha[i] - h[i-1]*z[i-1])/l[i]
        }
        
        
        var c = new Array()
        var b = new Array()
        var d = new Array()
        l[n-1] = h[n-2]*(2-u[n-2])
        z[n-1] = (alpha[n-1] - h[n-2]*z[n-2])/l[n-1]
        c[n-1] = z[n-1]
        
        for(var j = n-2; j >= 0; j--)
        {
            c[j] = z[j] - u[j]*c[j+1]
            b[j] = (a[j+1] - a[j])/h[j] - h[j]*(c[j+1]+2.0*c[j])/3.0
            d[j] = (c[j+1] - c[j])/(3*h[j])
            var funcStr = ""
            funcStr = a[j] + " + " + b[j]+"*(x-"+x[j]+")+"+c[j]+"*(x-"+x[j]+")*(x-"+x[j]+")+"+d[j]+"*(x-"+x[j]+")*(x-"+x[j]+")*(x-"+x[j]+");"
            //alert(funcStr)
            this.splines[j] = new Function("x","return " + funcStr)
        }
        return this.splines
    }
}

function BezierCurveInterpolator(data)
{
    //data = {x:Array,y:Array,leftGuides:{x:Array,y:Array},rightGuides:{x:Array,y:Array}}
    //a points is {x:value,y:value}
    this.x = data.x
    this.y = data.y
    this.n = data.x.length
    //did not do camel notation, so that writing would be easier
    this.xleft = data.xleft;
    this.xright = data.xright;
    this.curves = new Array()
    this.yleft = data.yleft;
    this.yright = data.yright
    
    this.getFX = function(params)
    {
         funcstr = "var x = "+ params.a0 + "+" +
                      params.a1 + "*t+"+
                      params.a2 + "*t*t+"+
                      params.a3 + "*t*t*t; return x"
        return new Function("t",funcstr)
    }
    
    this.getFY = function(params)
    {
         funcstr = "var y = "+ params.b0 + "+" +
                      params.b1 + "*t+"+
                      params.b2 + "*t*t+"+
                      params.b3 + "*t*t*t; return y"
        return new Function("t",funcstr)
    }
    
    this.interpolate = function()
    {
        var x = this.x
        var y = this.y
        var xleft = this.xleft
        var yleft = this.yleft
        var xright = this.xright
        var yright = this.yright
        var n = this.n
        
        for(var i = 0; i < n-1; i++)
        {
            var a0 = x[i]
            var b0 = y[i]
            var a1 = 3*(xleft[i] - x[i])
            var b1 = 3*(yleft[i] - y[i])
            var a2 = 3*(x[i] + xright[i+1] - 2*xleft[i])
            var b2 = 3*(y[i] + yright[i+1] - 2*yleft[i])
            var a3 = x[i+1] - x[i] + 3*xleft[i] - 3*xright[i+1]
            var b3 = y[i+1] - y[i] + 3*yleft[i] - 3*yright[i+1]
            
            //form the function array of objects
            //reason for this is, for animation, need to solve t in terms of x
            //and in path movements, just need t
            funcstr = "var x = "+ a0 + "+" +
                      a1 + "*t+"+
                      a2 + "*t*t+"+
                      a3 + "*t*t*t;"+
                      "var y = " + b0 + "+" +
                      b1 + "*t+"+
                      b2 + "*t*t+"+
                      b3 + "*t*t*t;"+
                      "return {x:x,y:y};"
            var obj = copy({a0:a0,a1:a1,a2:a2,a3:a3,b0:b0,b1:b1,b2:b2,b3:b3,ft:new Function("t",funcstr)})
            this.curves.push(obj)
        }
        return this.curves
    }
}


function Interpolater(type,data)
{
    this.method = null
    this.returned = null
    this.f = null
    this.type = type
    this.intervalSearch = intervalSearch //returns index for the required function
    if(this.type == "HERMITE")
    {
        //HERMITE
        this.method = new HermiteInterpolation(data);
    }
    else if (this.type == "CUBIC")
    {
        //cubic spline
        if(Interpolater.arguments[2])
        {
            //clamped
            this.method = new CubicSplineInterpolation(data,Interpolater.arguments[2])
        }
        else
        {
            //not clamped
            this.method = new CubicSplineInterpolation(data)
        }
    }
    else
    {
        //assumed type is the bezier curve
        this.method = new BezierCurveInterpolator(data)
    }
    
    this.returned = this.method.interpolate()
    
    if(this.type == "CUBIC")
    {
        //its a composite array of interval functions
        //use iterative binary search to find the interval
        this.f = function(x)
        {
            var i = this.intervalSearch(x)
            return this.returned[i](x);
        }
        
    }
    else if(this.type == "HERMITE")
    {
        this.f = this.returned
    }
    else
    {
        this.f = function(x)
        {
            var i = this.intervalSearch(x)
            return this.returned[i](x);
        }
    }
    
    function intervalSearch(x)
    {
        if(this.returned.push)
        {
            //it is assumed that the method object has a "x" member
            var min = 1;
            var max = this.method.x.length; 
            do
            {
              mid = parseInt((min + max) / 2);
              if(x > this.method.x[mid])
                min = mid + 1
              else 
                max = mid - 1;
            }
            while (!((this.method.x[mid] == x) || (min > max)))
            //interval

            return Math.min(max,min)
        }
        else
        {
            return null
        }
    }
    
    return getInterpolatorFunc(this);
}


function RootFinder(type,data)
{
    this.iterations = 1000
    this.TOL = 0.00001
    this.method = null
    this.f = null
    this.fp = null
    if(type == "NEWTON")
    {
        //data{f:function(x){},fp:function(x)}
        this.f = data.f
        this.fp = data.fp
        this.method = newton
    }
    else
    {
        this.f = data.f
        this.method = bisection
    }
    function newton(p0)
    {
        var i = 0;
        var p = null;
        var f = this.f
        var fp = this.fp
        while(i < this.iterations)
        {
            p = p0 + f(p0)/fp(p0)
            if(Math.abs(p-p0) < this.TOL)
            {
                return p
            }
            i += 1
            p0 = p
        }
        return -1
    }
    
    function bisection(a,b)
    {
        
        var i = 1
        var FA = this.f(a)
        var FP = 0
        while(i <= this.iterations)
        {
            var p = a+(b-a)/2
            FP = this.f(p)
            if(FP == 0 || (b-a)/2 < this.TOL)
            {
                return p
            }
            i += 1
            if(FA*FP > 0)
                {
                    a = p
                    FA = FP
                }
                else
                    b = p
        }
        return -1
    }
}