<?php

function DTW_sign() {$obj_DTW=new DTW();return($obj_DTW);} ;

class DTW {
    private $reference;
    private $check;
    private $n;
    private $m;
    private $result = Array();
    private $distance = Array();
    private $DTWResult;
    private $transformResult;
    private $step;
    public function __construct() {}

    public function setReference(Array $data) {
        $this->reference = $data;
        $this->m = count($this->reference);
        return $this;
    }
    public function setCheck(Array $data) {
        $this->check = $data;
        $this->n = count($this->check);
        return $this;
    }
    public function getReference() {
        return $this->reference;
    }
    public function getCheck() {
        return $this->check;
    }
    public function getDTWResult() {
        return $this->DTWResult;
    }
    public function getTransformResult() {
        return $this->transformResult;
    }
    public function getStep() {
        return $this->step;
    }

    public function getMinCost() {
        $this->result = Array();
        for($i = 1; $i <= $this->n; $i++) {
            $this->result[$i][0] = INF;
        }
        for($i = 1; $i <= $this->m; $i++) {
            $this->result[0][$i] = INF;
        }
        $this->result[0][0] = 0;
        for($i = 1; $i <= $this->n; $i++) {
            for($j = 1; $j <= $this->m; $j++) {
                $this->distance[$i][$j] = $this->d($i, $j);
                $this->result[$i][$j] = $this->distance[$i][$j] + min($this->result[$i-1][$j],
                                                    $this->result[$i][$j-1],
                                                    $this->result[$i-1][$j-1]);
            }
        }

        return $this->result[$this->n][$this->m] / ($this->n + $this->m);
        //return $this->getMaxPath();
    }
    
    public function getMinCost2($w) {
        $this->result = Array();
        
        $w = max($w, abs($this->n-$this->m)); 
                
        for($i = 0; $i <= $this->n; $i++) {
            $this->result[$i][0] = INF;
        }
        for($i = 0; $i <= $this->m; $i++) {
            $this->result[0][$i] = INF;
        }
        $this->result[0][0] = 0;
        for($i = 1; $i <= $this->n; $i++) {
            for($j = max(1, $i-$w); $j <= min($this->m, $i+$w); $j++) {
                $this->distance[$i][$j] = $this->d($i, $j);
                $this->result[$i][$j] = $this->distance[$i][$j] + min($this->result[$i-1][$j],
                                                    $this->result[$i][$j-1],
                                                    $this->result[$i-1][$j-1]);
            }
        }
        
        print_r($this->getMinPath());
        echo "<br />";
        echo "<br />";
        print_r($this->result[$this->n][$this->m]);
        
        echo "<br />";
        echo "<br />";
        
        print_r($this->n);
        echo "<br />";
        echo "<br />";
        
        print_r($this->m);
        echo "<br />";
        echo "<br />";

        for ($i =0; $i < $this->n; $i++) {
            for ($j =0; $j < $this->m; $j++) {
                echo $this->distance[$i][$j];
                echo ' ';
            }
            echo "<br />";
        }
        echo "<br />";echo "<br />";echo "<br />";
        for ($i =0; $i < $this->n; $i++) {
            for ($j =0; $j < $this->m; $j++) {
                echo $this->result[$i][$j];
                echo ' ';
            }
            echo "<br />";
        }
        return $this->result[$this->n][$this->m] / ($this->n + $this->m);

    }

    public function getMinPath() {
        $i = $j = 1;
        $this->step = 0;
        $this->DTWResult = 0;
        while($i != $this->n || $j != $this->m) {
            $this->DTWResult += $this->distance[$i][$j];
            $this->transformResult += $this->result[$i][$j];
            $right = $down = $diag = INF;
            if(isset($this->result[$i][$j+1])) {
                $right = $this->result[$i][$j + 1];
            }
            if(isset($this->result[$i+1][$j])) {
                $down = $this->result[$i+1][$j];
            }
            if(isset($this->result[$i+1][$j+1])) {
                $diag = $this->result[$i + 1][$j + 1];
            }
            $min = min($right, $down, $diag);
            if($diag == $min) {
                $i++;
                $j++;
            } elseif($down == $min) {
                $i++;
            } else {
                $j++;
            }
            $this->step++;
        }

        return $this->DTWResult / $this->step;
    }

    private function d($i, $j) {
        $sum1 = $this->reference[$j]['x'] - $this->check[$i]['x'];
        $sum2 = $this->reference[$j]['y'] - $this->check[$i]['y'];
        return sqrt(pow($sum1, 2) + pow($sum2, 2));
    }
}