//
// Math Util
//

Math.sinh = function(x){
  return (Math.exp(x)-Math.exp(-x))/2;
};

Math.cosh = function(x){
  return (Math.exp(x)+Math.exp(-x))/2;
};

Math.tanh = function(x){
  return Math.sinh(x)/Math.cosh(x);
};

//
// Kernel
//

var LinearKernel = Class.create({
  initialize: Prototype.K,
  k: function(a,b){
		var n = a.length;
		var res = 0.0;

		for(var i = 0; i < n; i++)
			res += a[i] * b[i];

		return res;
  }
});

var GaussianKernel = Class.create({
  initialize: function(s){
    this.s = s;
  },
  k: function(a,b){
		var n = a.length;
		var norm = 0.0;

		for(var i = 0; i < n; i++)
			norm += (a[i] - b[i]) * (a[i] - b[i]);

		return Math.exp(-1 * norm / (2 * this.s * this.s));
  }
});

var PolynomialKernel = Class.create({
  initialize: function(p){
    this.p = p;
  },
  k: function(a,b){
		var n = a.length;
		var dot = 0.0;

		for(var i = 0; i < n; i++)
			dot += a[i] * b[i];
		
		return Math.pow(1 + dot, this.p);
  }
});


var SigmoidKernel = Class.create({
  initialize: function(pa,pb){
		this.pa = pa;
		this.pb = pb;
  },
  k: function(a,b){
		var n = a.length;
		var dot = 0.0;
		for(var i = 0; i < n; i++)
			dot += a[i] * b[i];
		
		return Math.tanh(this.pa * dot - this.pb);
  }
});

//
// Model
//

var Model = Class.create({
  initialize: function(supportVectors,rho,kernel){
		this.supportVectors = supportVectors;
		this.rho = rho;
		this.kernel = kernel;
  },
  predict: function(x){

		var f = 0;
    this.supportVectors.each(function(e){
			f += e.y * this.kernel.k(e.x, x);
    }.bind(this));

		return (f > this.rho ? 1 : -1);
  }
});

//
// SVM Optimizer
//


var SVMOptimizer = Class.create({
  initialize: function(){
    this.eps = 1.0e-10;
    this.criterion = 1.0e-5;
    this.capacity = 1.0;
    this.minIteration = 0;
    this.maxIteration = 0;
    this.kernel = new LinearKernel();

    this.n;
    this.samples = [];
    this.lamdas = [];
    this.kernel_cache = [];
  },
  optimize: function(samples){
		this.n = samples.length;
		this.samples = samples;

		for(var i = 0; i < this.n; i++)
			this.lamdas[i] = 0;

		for(var i = 0; i < this.n; i++){
      this.kernel_cache[i] = [];
    }
		
		for(var i = 0; i < this.n; i++)
			for(var j = i; j < this.n; j++)
				this.kernel_cache[i][j] = this.kernel_cache[j][i] = this.kernel.k(this.samples[i].x, this.samples[j].x);

		this.optimizeSMO();
		return this.getModel();
  },
  optimizeSMO: function(){
		var  nIterations = 0;
		while(true) {

			var entire = true;
		  while(true) {
				var delta = 0;

				for(var i = 0; i < this.n; i++) {
					if (entire || (this.eps < this.lamdas[i] && this.lamdas[i] < this.capacity-this.eps)) {
						var origin = Math.floor( Math.random() * this.n );

						for(var k = 0; k < this.n; k++) {
							var j = (origin + k) % this.n;
							var d = this.optimizeLocal(i, j);

							if (d > this.eps) {
								delta += d;
								break;
							}
						}
					}
				}
			
				nIterations++;

				if (delta < this.criterion)
					break;
				
				if (nIterations == this.maxIteration)
					return;

				entire = false;
			}

			if (entire && nIterations > this.minIteration)
				break;
			
		}
  },
  optimizeLocal: function(a,b){
		var s = -1 * this.samples[a].y * this.samples[b].y;

		var denom = this.kernel_cache[a][a] + this.kernel_cache[b][b] - 2 * this.kernel_cache[a][b];
		
		if (Math.abs(denom) < this.eps)
			return 0;

		var num = 0;
		for(var i = 0; i < this.n; i++)
			num += this.lamdas[i] * this.samples[i].y * (this.kernel_cache[a][i] - this.kernel_cache[b][i]);
		num = (1 + s) - this.samples[a].y * num;
		
		var d = num / denom;

		d = Math.max(d, -1 * this.lamdas[a]);
		d = Math.min(d, this.capacity-this.lamdas[a]);
		d = s * Math.max(s*d, - this.lamdas[b]);
		d = s * Math.min(s*d, this.capacity-this.lamdas[b]);
		
		this.lamdas[a] += d;
		this.lamdas[b] += s * d;
		
		return Math.abs(d);
  },
  getModel: function(){

		var supportVectors = []; 
		var rho;

		var free = -1;
		for(var i = 0; i < this.n; i++) {
			if (this.eps < this.lamdas[i]) {
        supportVectors.push({
          x: this.samples[i].x,
          y: this.lamdas[i] * this.samples[i].y
        });

				if (free < 0 || this.lamdas[i] < this.lamdas[free])
					free = i;
			}
		}

		if (free < 0) {
			rho = 0;
			console.log("SVM: No support vectors.");
		}
		else {
			rho = -1 * this.samples[free].y;

      supportVectors.each(function(e){
				rho += e.y * this.kernel.k(e.x, this.samples[free].x);
      }.bind(this));

		}

		return new Model(supportVectors, rho, this.kernel);

  }
});

// add sample 

var Demo = Class.create({
  initialize: function(mapID){

    this.map = $(mapID);

    this.RANGER_MAX = 200;
    this.RANGER_DEFAULT = 58;

    this.samples = [];  
    this.model = null;
    this.currentClass = 1;
    this.range_value = this.RANGER_DEFAULT;

		this.svm = new SVMOptimizer();
		this.svm.minIteration = 0;
		this.svm.maxIteration = 5000;
  },
  addSample: function(x,y){
    this.samples.push({
      x:[x,y],
      y:this.currentClass
    });

    this.addPint(x,y,this.currentClass);
  },
  learn: function(){
    this.model = this.svm.optimize(this.samples);
    this.paintClassfication();
  },
  setKernel: function(name){
    this.current_kernel_name = name;
    switch(name){
      case 'linear':
        this.svm.criterion = 1.0e-5;
        this.svm.kernel = new LinearKernel();
        break;
      case 'gaussian':
        this.svm.criterion = 1.0e-10;
        this.svm.kernel = new GaussianKernel(Math.pow(10.0, this.range_value/this.RANGER_MAX * 5.0));
        break;
      case 'sigmoid':
        this.svm.criterion = 1.0e-10;
        this.svm.kernel = new SigmoidKernel(Math.pow(10.0, this.range_value / this.RANGER_MAX * 50.0, 0.0));
        break;
      case 'polynomial':
        this.svm.criterion = 1.0e-10;
        this.svm.kernel = new PolynomialKernel(this.range_value);
        break;
    }
  },
  clear: function(){
		this.samples = [];
		this.model = null;
    $A(this.map.childNodes).each(function(node){
      this.map.removeChild(node);
    }.bind(this));

  },
  paintClassfication: function(){
    for(var y = 0; y < 200; y += 10) {
     for(var x = 0; x < 200; x += 10) {
        var s = this.model.predict([x+5,y+5]);

        var div = document.createElement("div");

        if(s == 1){
          div.className = 'draw skyblue';
        }else{
          div.className = 'draw pink';
        }

        div.style.left = x + 'px'
        div.style.top = y + 'px'
        this.map.appendChild(div);
      }
    }

  },
  addPint: function(x,y,class){
    var div = document.createElement("div");
    if(class== 1){
      div.className = 'blue point';
    }else{
      div.className = 'red point';
    }

    div.style.left = x + 'px'
    div.style.top = y + 'px'

    this.map.appendChild(div);
  }

});