<?php
//Structure pour les points du graph
class Point
{
    public $x;
    public $y;
    function __construct($x, $y)
    {
        $this->x = $x;
        $this->y = $y;
    }
}
//Affichage des polynomes
class Number
{
    public static function show_sign($n)
    {
        return ($n >= 0) ? '+ ' : '- ';
    }
    public static function show($n, $var = '', $pow = 1, $first_element = false)
    {
        if($pow > 1)
            $var .= '<sup>'.$pow.'</sup>';
        elseif($pow == 0)
            $var = '';
        $var .= ' ';
        if($n == 0)
            return '';
        elseif($pow != 0 && ($n == 1 || $n == -1))
            $s = self::show_sign($n);
        else//if($n != 0)
            $s = self::show_sign($n).abs($n);
        if($first_element && $n >= 0)
            return ($n==1) ? $var : $n.$var;
        return $s.$var;
    }
}
//Structure et fonctions des polynomes
class Polynom implements ArrayAccess
{
    private $coef = Array();//coeficients
    private $degree;
    function __construct($coeficients)
    {
        if(!is_array($coeficients))
            $coeficients = func_get_args();
        $this->degree = count($coeficients)-1;
        for($d=0; $d<=$this->degree; $d++)
            $this->coef[$d] = $coeficients[$this->degree-$d];
    }
    function __toString()
    {
        $return = Number::show($this[$this->degree], 'x', $this->degree, true);
        for($d=$this->degree-1; $d>=0; $d--)
            $return .= Number::show($this[$d], 'x', $d);
        return $return;
    }
    //ArrayAccess
    public function offsetGet($offset)
        { return $this->coef[$offset]; }
    public function offsetSet($offset, $value)
        { $this->coef[$offset] = $value; }
    public function offsetUnset($offset) {}
    public function offsetExists($offset)
        { return array_key_exists($offset, $this->coef); }
    public function add(Polynom $p)
    {
        $max = ($this->degree > $p->degree) ? $this : $p;
        $min = ($this->degree > $p->degree) ? $p : $this;
        for($d=0; $d<=$min->degree; $d++)
            $max[$d] += $min[$d];
        return $max;
    }
    public function product(Polynom $p)
    {
        $result = new Polynom(array_fill(0, $this->degree+$p->degree+1, 0));
        for($d=0; $d<=$this->degree; $d++)
        {
            for($e=0; $e<=$p->degree; $e++)
                $result[$d+$e] += $this[$d]*$p[$e];
        }
        return $result;
    }
}
class Interpolation
{
    public static function Lagrange($p)
    {//Interpolation polynomiale de Lagrange(Array(Point) $points)
        $n = count($p);
        $result = new Polynom(0);
        for($k=0; $k<$n; $k++)
        {
            $t = new Polynom($p[$k]->y);
            for($i=0; $i<$n; $i++)
            {
                if($i != $k)
                {
                    $poly[$k][$i] = new Polynom(
                    1/($p[$k]->x - $p[$i]->x) ,
                    -$p[$i]->x/($p[$k]->x-$p[$i]->x) );
                    $t = $t->product($poly[$k][$i]);
                }
            }
            $result = $result->add($t);
        }
        return $result;
    }
}
//TEST\\
//Points : (−9, 5), (−4, 2), (−1, −2), (7, 9)
$a = new Point(-9, 5);
$b = new Point(-4, 2);
$c = new Point(-1, -2);
$d = new Point(7, 9);
echo $polynom = Interpolation::Lagrange(Array($a, $b, $c, $d));
?>