var COEFFICIENT = [0, 1, 100, 10000, 10000000];

function Cluster(color) {
  this.color = color;
  this.start = [new Rational(1000, 1), new Rational(1000, 1)];
  this.end = [ZERO, ZERO];
  this.numPieces = 0;
  this.linkToBorder = [false, false, false, false];
  this.numLinksToBorders = 0;
  this.value = 0;
}

Cluster.prototype.add = function(piece) {
  assert(piece.color == this.color);
  piece.cluster = this;
  if (this.start[HORIZONTAL].bigger(piece.start[HORIZONTAL])) {
    this.start[HORIZONTAL] = piece.start[HORIZONTAL];
  }
  if (this.start[VERTICAL].bigger(piece.start[VERTICAL])) {
    this.start[VERTICAL] = piece.start[VERTICAL];
  }
  if (this.end[HORIZONTAL].smaller(piece.end[HORIZONTAL])) {
    this.end[HORIZONTAL] = piece.end[HORIZONTAL];
  }
  if (this.end[VERTICAL].smaller(piece.end[VERTICAL])) {
    this.end[VERTICAL] = piece.end[VERTICAL];
  }
  this.numPieces += 1;
  for (var side = 0; side < 4; side ++) {
    if (!this.linkToBorder[side] && piece.connections[side].length == 0) {
      this.linkToBorder[side] = true;
      this.numLinksToBorders += 1;
    }
  }
}

Cluster.prototype.getLength = function(dir) {
 return this.end[dir].subtract(this.start[dir]).float();
}

Cluster.prototype.evaluate = function() {
  
  this.value = COEFFICIENT[this.numLinksToBorders] 
              + 10 * (this.getLength(HORIZONTAL)*this.getLength(HORIZONTAL) + 
					    this.getLength(VERTICAL) * this.getLength(VERTICAL)) 
			  + 7 * this.numPieces * this.numPieces;
  return this.value;
}

function Evaluator(board, mycolor) {
  this.board = board;
  this.mycolor = mycolor;
  this.clusters = [new Array(), new Array()];
  this.score = 0;
}

Evaluator.prototype.doit = function() {
  for (var i = 0; i < this.board.pieces.length; i++) {
    this.board.pieces[i].cluster = null;
  }
  for (var i = 0; i < this.board.pieces.length; i++) {
    if (this.board.pieces[i].cluster == null) {
      var cluster = new Cluster(this.board.pieces[i].color);
      this._discoverCluster(this.board.pieces[i], cluster);
      cluster.evaluate();
      this.clusters[cluster.color].push(cluster);
    }
  }
  this.clusters[BLACK].sort(Algorithm.prototype._byValue);
  this.clusters[WHITE].sort(Algorithm.prototype._byValue);
     
  for (var i = 0; i < this.board.pieces.length; i++) {
      if (this.mycolor == this.board.pieces[i].color) {
        this.score += this.board.pieces[i].area() * this.board.pieces[i].cluster.value;
      } else {
        this.score -= this.board.pieces[i].area() * this.board.pieces[i].cluster.value;
      }
  }
  return this.score;  
}

Evaluator.prototype._discoverCluster = function(piece, cluster) {
  cluster.add(piece);
  for (var side = 0; side < 4; side ++) {
     for (var c = 0; c < piece.connections[side].length; c++) {
       var neighbor = piece.connections[side][c];
       if (neighbor.cluster == null) {
         if (neighbor.color == piece.color) {
           this._discoverCluster(neighbor, cluster);
         }
       }
     }
   }
}        

function AlgCluster () {
  this._evaluate = this._evaluate2;
  this._evaluateFast = this._evaluateFast2;
  this.PIECE_VALUE_THRESHOLD = 0.3;
  this.PIECE_VALUE_MAX = 15;
  
}

AlgCluster.prototype = Algorithm.prototype;

AlgCluster.prototype._evaluateFast2 = function(board, mycolor) {
  var evaluator = new Evaluator(board, mycolor);
  evaluator.doit();
  return evaluator.score;
}



AlgCluster.prototype._evaluate2 = function(board, mycolor) {
  var evaluator = new Evaluator(board, mycolor);
  evaluator.doit();
  var b2 = board.clone();
  for (var i = 0; i < board.pieces.length; i++) {
    if (board.pieces[i].color != mycolor) {
      var b2Piece = b2.equivalent(board.pieces[i]);
      b2Piece.swap();
      var ev = new Evaluator(b2, mycolor);
      ev.doit();
      board.pieces[i].value = this._evaluateClusterDifferences(board.pieces[i], b2Piece);
      b2Piece.swap();
    } else {
      board.pieces[i].value = 0;
    }
  }
  return evaluator.score;
}
      
      
      
AlgCluster.prototype._evaluateClusterDifferences = function(original, swapped) {
  var pieces = [original, swapped];
  var clustersBefore = AlgCluster.prototype._populateClusters(original);
  clustersBefore[swapped.color].sort(Algorithm.prototype._byValue);
  var clustersAfter = AlgCluster.prototype._populateClusters(swapped);
  clustersAfter[original.color].sort(Algorithm.prototype._byValue);
  var score = 0;
  if (clustersAfter[original.color].length == 0) {
     score += clustersBefore[original.color][0].value;
  } else {
     score += clustersBefore[original.color][0].value - clustersAfter[original.color][0].value;
  }
  if (clustersBefore[swapped.color].length == 0) {
    score += clustersAfter[swapped.color][0].value;
  } else {
    score += clustersAfter[swapped.color][0].value - clustersBefore[swapped.color][0].value; 
  }
    
  return score;
}

AlgCluster.prototype._populateClusters = function(piece) {
  var clusters = [[],[]];
  AlgCluster.prototype._addClusterIfNotFound(clusters[piece.color], piece.cluster); 
  for (var side = 0; side < 4; side ++) {
    for (var c = 0; c < piece.connections[side].length; c++) {
      var neighbor = piece.connections[side][c];
      AlgCluster.prototype._addClusterIfNotFound(clusters[neighbor.color], neighbor.cluster);
    }
  }
  return clusters;
} 

AlgCluster.prototype._addClusterIfNotFound = function(clusters, cluster) {
  for(var i = 0; i < clusters.length; i++) {
    if (clusters[i] == cluster) return;
  }
  clusters.push(cluster);
}
      
  
toTest.push(AlgCluster);

AlgCluster.prototype.test = function() {
}