function Board (x, y) {
  this.x = x;
  this.y = y;
  this.pieces = new Array();
  this.lookup = {};
  this.sideLookup = [{},{},{},{}];
}


Board.prototype._removeFromArray = function(a, p) {
  for (var i = 0; i < a.length; i++) {
    if (a[i] == p) {
      a[i] = null;
      return;
    }
  }
  assert(false);
}

Board.prototype._updateLookup = function(p) { 
  this.lookup[p.start.toString()] = p;
  var startXPieces = this.sideLookup[START_X][p.start[HORIZONTAL].toString()];
  if (!startXPieces) {
     this.sideLookup[START_X][p.start[HORIZONTAL].toString()] = [p];
  } else {
    startXPieces.push(p);
  }
  var startYPieces = this.sideLookup[START_Y][p.start[VERTICAL].toString()];
  if (!startYPieces) {
    this.sideLookup[START_Y][p.start[VERTICAL].toString()] = [p];
  } else {
    startYPieces.push(p);
  }
  var endXPieces = this.sideLookup[END_X][p.end[HORIZONTAL].toString()]; 
  if (!endXPieces) {
    this.sideLookup[END_X][p.end[HORIZONTAL].toString()] = [p];
  } else {
    endXPieces.push(p);
  }
  var endYPieces = this.sideLookup[END_Y][p.end[VERTICAL].toString()];
  if (!endYPieces) {
    this.sideLookup[END_Y][p.end[VERTICAL].toString()] = [p];
  } else {
    endYPieces.push(p);
  }
}


Board.prototype._removeLookup = function(p) { 
  this.lookup[p.start.toString()] = null;
  Board.prototype._removeFromArray(this.sideLookup[START_X][p.start[HORIZONTAL].toString()], p);
  Board.prototype._removeFromArray(this.sideLookup[START_Y][p.start[VERTICAL].toString()], p)
  Board.prototype._removeFromArray(this.sideLookup[END_X][p.end[HORIZONTAL].toString()], p);
  Board.prototype._removeFromArray(this.sideLookup[END_Y][p.end[VERTICAL].toString()], p);
}


Board.prototype._addPiece = function(p) {
  this.pieces.push(p);
  this._updateLookup(p);
}

Board.prototype._replacePieces = function(newPieces) {
  this.lookup = {};
  this.sideLookup = [{},{},{},{}];
  
  this.pieces = newPieces;
  for(var i = 0; i < this.pieces.length; i++) {
    this._updateLookup(this.pieces[i]);
  }
}

Board.prototype._replacePiece = function(pOld, pNew) {
  for (var i = 0; i < this.pieces.length; i++) {
    if (this.pieces[i] === pOld) {
      this._removeLookup(pOld);
      this.pieces[i] = pNew;
      this._updateLookup(pNew);
      return true;
    }
  }
  return false;
}

Board.prototype._lookup = function(start) {
  var p = this.lookup[start.toString()];
  assert(p);
  return p;
}

Board.prototype._resetPieces = function() {
  this.lookup = {};
  this.pieces = new Array();
}

Board.prototype.build = function() {
  this._resetPieces();
  // create pieces
  for (var j = 0; j < this.y; j++) {
    for (var i = 0; i < this.x; i++) {
      var piece = new ConnectedPiece(new Rational(i, 1), new Rational(j, 1), ONE, ONE, (i+j)%2?WHITE:BLACK);
      this._addPiece(piece);
    }
  }
  // connect them
  for (var j = 0; j < this.y; j++) {
  	for (var i = 0; i < this.x; i++) {
      if (i > 0) {
        this.pieces[j * this.x + i].connections[LEFT] = [this.pieces[j * this.x + i - 1]];
      }
      if (i < this.x - 1) {
        this.pieces[j * this.x + i].connections[RIGHT] = [this.pieces[j * this.x + i + 1]];
      }
      if (j > 0) {
        this.pieces[j * this.x + i].connections[TOP] = [this.pieces[(j - 1) * this.x + i]];
      }
      if (j < this.y - 1) {
        this.pieces[j * this.x + i].connections[BOTTOM] = [this.pieces[(j + 1) * this.x + i]];
      }
    }
  }
};

Board.prototype._buildFrom = function(b, callback) {
  for (var i = 0; i < b.pieces.length; i++) {
    var p = new ConnectedPiece(b.pieces[i].start[HORIZONTAL], b.pieces[i].start[VERTICAL], b.pieces[i].x, b.pieces[i].y, b.pieces[i].color);
    if (callback) {
      callback(b.pieces[i], p);
    }
    this._addPiece(p);
  }
  this._createConnections();
  this._assertValid();
  
}
Board.prototype._createConnections = function() {
  for (var i = 0; i < this.pieces.length; i++) {
    var p = this.pieces[i];
    var xExact = p.start[HORIZONTAL];
    var y = p.start[VERTICAL].float() + TINY;
    var end = p.end[VERTICAL].float();
    do {
      var n = this.getPieceEndX(xExact, y);
      if (n) {
        p.connections[LEFT].push(n);
        y = n.end[VERTICAL].float() + TINY;
      } else break;
    } while (y < end);
    var x = p.start[HORIZONTAL].float() + TINY;
    var yExact = p.start[VERTICAL];
    var end = p.end[HORIZONTAL].float();
    do {
      var n = this.getPieceEndY(x, yExact);
      if (n) {
        p.connections[TOP].push(n);
        x = n.end[HORIZONTAL].float() + TINY;
      } else break;
    } while (x < end);
    var xExact = p.end[HORIZONTAL];
    var y = p.start[VERTICAL].float() + TINY;
    var end = p.end[VERTICAL].float();
    do {
      var n = this.getPieceStartX(xExact, y);
      if (n) {
        p.connections[RIGHT].push(n);
        y = n.end[VERTICAL].float() + TINY;
      } else break;
    } while (y < end);
    var x = p.start[HORIZONTAL].float() + TINY;
    var yExact = p.end[VERTICAL];
    var end = p.end[HORIZONTAL].float(); 
    do {
      var n = this.getPieceStartY(x, yExact);
      if (n) {
        p.connections[BOTTOM].push(n);
        x = n.end[HORIZONTAL].float() + TINY;
      } else break;
    } while (x < end);
  }
}

/*
Board.prototype._createConnections = function() {
  for (var i = 0; i < this.pieces.length; i++) {
    var p = this.pieces[i];
    var x = p.start[HORIZONTAL].float() - TINY;
    var y = p.start[VERTICAL].float() + TINY;
    var end = p.end[VERTICAL].float();
    do {
      var n = this.getPiece(x, y);
      if (n) {
        p.connections[LEFT].push(n);
        y = n.end[VERTICAL].float() + TINY;
      } else break;
    } while (y < end);
    var x = p.start[HORIZONTAL].float() + TINY;
    var y = p.start[VERTICAL].float() - TINY;
    var end = p.end[HORIZONTAL].float();
    do {
      var n = this.getPiece(x, y);
      if (n) {
        p.connections[TOP].push(n);
        x = n.end[HORIZONTAL].float() + TINY;
      } else break;
    } while (x < end);
    var x = p.end[HORIZONTAL].float() + TINY;
    var y = p.start[VERTICAL].float() + TINY;
    var end = p.end[VERTICAL].float();
    do {
      var n = this.getPiece(x, y);
      if (n) {
        p.connections[RIGHT].push(n);
        y = n.end[VERTICAL].float() + TINY;
      } else break;
    } while (y < end);
    var x = p.start[HORIZONTAL].float() + TINY;
    var y = p.end[VERTICAL].float() + TINY;
    var end = p.end[HORIZONTAL].float(); 
    do {
      var n = this.getPiece(x, y);
      if (n) {
        p.connections[BOTTOM].push(n);
        x = n.end[HORIZONTAL].float() + TINY;
      } else break;
    } while (x < end);
  }
}
*/

Board.prototype.clone = function(callback) {
  var b = new Board(this.x, this.y);
  b._buildFrom(this, callback);
  return b;
}

Board.prototype.material = function(color) {
  var material = 0.0;
  for (var i = 0; i < this.pieces.length; i++) {
	if (this.pieces[i].color === color) {
	  material += this.pieces[i].x.top * this.pieces[i].y.top / (this.pieces[i].x.bot * this.pieces[i].y.bot);
	} 	
  }
  return material;
}

Board.prototype.getPiece = function(realX, realY) {
  for (var i = 0; i < this.pieces.length; i++) {
    if (this.pieces[i].start[HORIZONTAL].smallerFloat(realX) && this.pieces[i].end[HORIZONTAL].biggerFloat(realX) && 
        this.pieces[i].start[VERTICAL].smallerFloat(realY) && this.pieces[i].end[VERTICAL].biggerFloat(realY)) {
           return this.pieces[i];
    } 
  }
  return null;
}

Board.prototype.getPieceStartX = function(exactX, realY) {
  var pieces = this.sideLookup[START_X][exactX.toString()];
  if (pieces == null) {
    return null;
  }
  for (var i = 0; i < pieces.length; i++) {
    if (pieces[i] != null) {
      if (pieces[i].start[VERTICAL].smallerFloat(realY) && pieces[i].end[VERTICAL].biggerFloat(realY)) {
        return pieces[i];
      }
    } 
  }
  return null;
}

Board.prototype.getPieceEndX = function(exactX, realY) {
  var pieces = this.sideLookup[END_X][exactX.toString()];
  if (pieces == null) {
    return null;
  }
  for (var i = 0; i < pieces.length; i++) {
    if (pieces[i] != null) {
      if (pieces[i].start[VERTICAL].smallerFloat(realY) && pieces[i].end[VERTICAL].biggerFloat(realY)) {
        return pieces[i];
      }
    } 
  }
  return null;
}

Board.prototype.getPieceStartY = function(realX, exactY) {
  var pieces = this.sideLookup[START_Y][exactY.toString()];
  if (pieces == null) {
    return null;
  }
  for (var i = 0; i < pieces.length; i++) {
    if (pieces[i] != null) {
      if (pieces[i].start[HORIZONTAL].smallerFloat(realX) && pieces[i].end[HORIZONTAL].biggerFloat(realX)) {
        return pieces[i];
      }
    } 
  }
  return null;
}

Board.prototype.getPieceEndY = function(realX, exactY) {
  var pieces = this.sideLookup[END_Y][exactY.toString()];
  if (pieces == null) {
    return null;
  }
  for (var i = 0; i < pieces.length; i++) {
    if (pieces[i] != null) {
      if (pieces[i].start[HORIZONTAL].smallerFloat(realX) && pieces[i].end[HORIZONTAL].biggerFloat(realX)) {
        return pieces[i];
      }
    } 
  }
  return null;
}


Board.prototype.isAligned = function(pFirst, pLast, side) {
  return this._sizeBetween(pFirst, pLast, side).bigger(ZERO);
}

Board.prototype.assertAligned = function(pieces, side) {
  var color = pieces[pieces.length-1].color; 
  var horizontalAligned = true;
  var verticalAligned = true;
  for (var i = 0; i < pieces.length - 1; i++) {
    if (side == TOP) {
      assert(pieces[i].start[VERTICAL].equals(pieces[i+1].start[VERTICAL]));
    } else if (side == BOTTOM) {
      assert(pieces[i].end[VERTICAL].equals(pieces[i+1].end[VERTICAL]));
    } else if (side == LEFT) {
      assert(pieces[i].start[HORIZONTAL].equals(pieces[i+1].start[HORIZONTAL]));
    } else {
      assert(pieces[i].end[HORIZONTAL].equals(pieces[i+1].end[HORIZONTAL]));
    } 
    assert(pieces[i].color == pieces[i+1].color);
  }
}

Board.prototype._assertValid = function() {
  if (!DBG_MODE) {
    return;
  }
  for (var i = 0; i < this.pieces.length; i++) {
    if (this.pieces[i].connections[LEFT].length === 0) {
      assert(this.pieces[i].start[HORIZONTAL].equals(ZERO));
    }
    if (this.pieces[i].connections[TOP].length === 0) {
      assert(this.pieces[i].start[VERTICAL].equals(ZERO));
    }
    if (this.pieces[i].connections[RIGHT].length === 0) {
      assert(this.pieces[i].end[HORIZONTAL].equals(new Rational(this.x, 1)));
    }
    if (this.pieces[i].connections[BOTTOM].length === 0) {
      assert(this.pieces[i].end[VERTICAL].equals(new Rational(this.y, 1)));
    }
    // make sure connections point to each other
    var sides = [TOP, LEFT];
    for (var c = 0; c < sides.length; c++) {
      for (var n = 0; n < this.pieces[i].connections[sides[c]].length; n++) {
        var neighbor = this.pieces[i].connections[sides[c]][n];
        assert(this._findPiece(neighbor.connections[OPPOSITE_SIDE[sides[c]]], this.pieces[i]));
      } 
    }
    for (var side = 0; side < 4; side++) {
      for (var n = 0; n < this.pieces[i].connections[side].length; n++) {
        var neighbor = this.pieces[i].connections[side][n];
        if (n < this.pieces[i].connections[side].length-1) {
          var nextNeighbor = this.pieces[i].connections[side][n+1];
          assert(neighbor.end[DIR[side]].equals(nextNeighbor.start[DIR[side]]));
        }
        assert(this.pieces[i].start[DIR[side]].smaller(neighbor.end[DIR[side]]));
        assert(this.pieces[i].end[DIR[side]].bigger(neighbor.start[DIR[side]]));
      }
    }
  }  
}

Board.prototype._reconnect = function(fromPieces, toPieces, side) {
  assert(fromPieces.length == 1 || toPieces.length == 1);
  this.assertAligned(fromPieces, side);
  this.assertAligned(toPieces, side);
  
  var connections = this._mergeConnections(fromPieces, side);
  this._distributeConnections(toPieces, connections, side);
  
}  

Board.prototype._mergeConnections = function(adjacentPieces, side) { 
  var connections = new Array();
  for (var i = 0; i < adjacentPieces.length; i++) {
    for (var j = 0; j < adjacentPieces[i].connections[side].length; j++) {
      var neighbor = adjacentPieces[i].connections[side][j];
      // if last neighbor is the same, don't push it
      if (connections.length == 0 || connections[connections.length-1] != neighbor) {
        connections.push(neighbor);
      }
    }
  }
  return connections;
}

Board.prototype._distributeConnections = function(adjacentPieces, connections, side) { 
  for (var i = 0; i < adjacentPieces.length; i++) {
    var c = 0;
    adjacentPieces[i].connections[side] = new Array();
    while (c < connections.length) {
      if (connections[c].end[DIR[side]].bigger(adjacentPieces[i].start[DIR[side]]) &&
          connections[c].start[DIR[side]].smaller(adjacentPieces[i].end[DIR[side]])) {
      
	      adjacentPieces[i].connections[side].push(connections[c]);
	  }
	  c += 1;
	}
  }
}

Board.prototype._updateNeighborConnectionsSplit = function(fromPiece, toPieces, side) {
  this.assertAligned(toPieces, side);
  for (var j = 0; j < fromPiece.connections[side].length; j++) {
      var neighbor = fromPiece.connections[side][j];
      var newConnections = new Array();
      for (var nc = 0; nc < neighbor.connections[OPPOSITE_SIDE[side]].length; nc++) {
        var neighborsNeighbor = neighbor.connections[OPPOSITE_SIDE[side]][nc]; 
	    if (neighborsNeighbor == fromPiece) {
	      var to = 0;
	      do {
	        // skip the pieces if after the split they no longer should be connected
	        if (neighbor.start[DIR[side]].smaller(toPieces[to].end[DIR[side]]) &&
	            neighbor.end[DIR[side]].bigger(toPieces[to].start[DIR[side]])) {
	           newConnections.push(toPieces[to]);
		    }
		    to += 1;
		  } while (to < toPieces.length);	          
	    } else {
	      newConnections.push(neighborsNeighbor);
	    }
	  }
	  neighbor.connections[OPPOSITE_SIDE[side]] = newConnections;
  }
}

Board.prototype._findPiece = function(pieces, piece) {
  for (var t = 0; t < pieces.length; t++) {
      if (piece == pieces[t]) {
        return true;
      }
  }
  return false;
}
 	    
Board.prototype._updateNeighborConnectionsMerge = function(fromPieces, toPiece, side) {
  var to = 0;
  var neighbors = new Array();
  for (var i = 0; i < fromPieces.length; i++) {
    for (var j = 0; j < fromPieces[i].connections[side].length; j++) {
      var next = fromPieces[i].connections[side][j];
      if (neighbors.length == 0 || neighbors[neighbors.length-1] != next) {
        neighbors.push(next);
      }
    }
  }
  for (var n = 0; n < neighbors.length; n++) {
    var neighbor = neighbors[n];
    var replaced = false;
    var newConnections = new Array();
      
    for (var nc = 0; nc < neighbor.connections[OPPOSITE_SIDE[side]].length; nc++) {
      var neighborsNeighbor = neighbor.connections[OPPOSITE_SIDE[side]][nc];
      if (!this._findPiece(fromPieces, neighborsNeighbor)) {
          newConnections.push(neighborsNeighbor);
      } else if (! replaced) {
          newConnections.push(toPiece);
          replaced = true;
      }
   	}
	neighbor.connections[OPPOSITE_SIDE[side]] = newConnections;
  }
}


Board.prototype.split = function(piece, direction) {
  assert(piece.canSplit(direction));
  var x = piece.x;
  var y = piece.y;
  var startOfSecondPieceX = piece.getStart(HORIZONTAL);
  var startOfSecondPieceY = piece.getStart(VERTICAL);
  if (direction === HORIZONTAL) {
    y = y.half();
    startOfSecondPieceY = startOfSecondPieceY.add(y);
  } else {
    x = x.half();
    startOfSecondPieceX = startOfSecondPieceX.add(x);
  }
 var p1 = new ConnectedPiece(piece.getStart(HORIZONTAL), piece.getStart(VERTICAL), x, y, piece.color);
  var p2 = new ConnectedPiece(startOfSecondPieceX, startOfSecondPieceY, x, y, piece.color);  
  var fromPieces = [piece];
  var toPieces = [p1, p2];
  if (direction == HORIZONTAL) { 
  	p1.connections[BOTTOM] = [p2];
  	p1.connections[TOP] = piece.connections[TOP];
  	p2.connections[TOP] = [p1];
  	p2.connections[BOTTOM] = piece.connections[BOTTOM];
    this._reconnect(fromPieces, toPieces, LEFT);
    this._reconnect(fromPieces, toPieces, RIGHT);    
  	this._updateNeighborConnectionsSplit(piece, toPieces, LEFT);
  	this._updateNeighborConnectionsSplit(piece, toPieces, RIGHT);
  	this._updateNeighborConnectionsSplit(piece, [p1], TOP);
  	this._updateNeighborConnectionsSplit(piece, [p2], BOTTOM);
  	
  } else {
  	p1.connections[RIGHT] = [p2];
  	p1.connections[LEFT] = piece.connections[LEFT];
  	p2.connections[LEFT] = [p1];
  	p2.connections[RIGHT] = piece.connections[RIGHT];
    this._reconnect(fromPieces, toPieces, TOP);
    this._reconnect(fromPieces, toPieces, BOTTOM);
  	this._updateNeighborConnectionsSplit(piece, toPieces, TOP);
  	this._updateNeighborConnectionsSplit(piece, toPieces, BOTTOM);
  	this._updateNeighborConnectionsSplit(piece, [p1], LEFT);
  	this._updateNeighborConnectionsSplit(piece, [p2], RIGHT);
  }
  
  var succeeded = this._replacePiece(piece, p1);
  
  assert(succeeded);
  this._addPiece(p2); // p1 replaced original piece
  return [p1, p2];  
}

Board.prototype.getAllAvailableLongSplitCandidates = function(pFirst, dir) {
  assert(pFirst.canSplit(dir));
  var pNext = pFirst;
  
  var middle = pFirst.getMiddle(dir);
  var color = pFirst.color;
  
  var sides = (dir == HORIZONTAL) ? [LEFT,RIGHT] : [TOP,BOTTOM];
  
  var candidates = [[],[]];
  for (var s = 0; s < 2; s++) {
    candidates[s] = this._getCandidatesFrom(pNext, sides[s], dir);
  }
  return candidates;
}

Board.prototype._getCandidatesFrom = function(pNext, side, dir) {
  var candidates = [];
  var middle = pNext.getMiddle(dir); 
  while (pNext.connections[side].length > 0) {
    for (var i = 0; i < pNext.connections[side].length; i++) {
      var neighbor = pNext.connections[side][i];
      if (neighbor.start[OPPOSITE_DIR[dir]].equals(middle) ||
          neighbor.end[OPPOSITE_DIR[dir]].equals(middle)) {
          pNext = neighbor;
          break;
      } else if (neighbor.start[OPPOSITE_DIR[dir]].smaller(middle) &&
                 neighbor.end[OPPOSITE_DIR[dir]].bigger(middle)) {
          if (neighbor.color != pNext.color) {
            return candidates;
          }
          if (!neighbor.canSplit(dir)) {
            return candidates;
          } 
          var newMiddle = neighbor.getMiddle(dir);
          if (!newMiddle.equals(middle)) {
            return candidates;
          }
          candidates.push(neighbor);
          pNext = neighbor;
          break;
      }
    }
  }    
  return candidates;
}

Board.prototype._getLongSplitCandidates = function(pFirst, pLast, dir) {  
  var pNext = pFirst;
  if (!pFirst.canSplit(dir)) {
    return [];
  }
  var middle = pFirst.getMiddle(dir);
  var color = pFirst.color;
  var side = (dir == HORIZONTAL) ? RIGHT : BOTTOM;
  var candidates = [pFirst];
  while (pNext.end[dir].smaller(pLast.end[dir])) {
    var foundNext = false;
    for (var i = 0; i < pNext.connections[side].length; i++) {
      var neighbor = pNext.connections[side][i];
      if (neighbor.start[OPPOSITE_DIR[dir]].equals(middle) ||
          neighbor.end[OPPOSITE_DIR[dir]].equals(middle)) {
          pNext = neighbor;
          foundNext = true;
          break;
      } else if (neighbor.start[OPPOSITE_DIR[dir]].smaller(middle) &&
                 neighbor.end[OPPOSITE_DIR[dir]].bigger(middle)) {
          if (neighbor.color != color) {
            return [];
          }
          if (!neighbor.canSplit(dir)) {
            return [];
          } 
          var newMiddle = neighbor.getMiddle(dir);
          if (!newMiddle.equals(middle)) {
            return [];
          }
          candidates.push(neighbor);
          pNext = neighbor;
          foundNext = true;
          break;
      }
    }
    assert(foundNext);
  }    
  return candidates;
}  


Board.prototype.longSplit = function(pFirst, pLast, dir) {
  var splitPieces = [];
  var pieces = this._getLongSplitCandidates(pFirst, pLast, dir);
  if (pieces.length) {
    for (var i = 0; i < pieces.length; i++) {
      var newPieces = this.split(pieces[i], dir);
      for (var j = 0; j < newPieces.length; j++) {
        splitPieces.push(newPieces[j]);
      }
    }
  }
  return splitPieces;
}


Board.prototype.canMerge = function (pLeftTop, pRightTop, pLeftBottom, pRightBottom) {
  assertParams(arguments, [Piece, Piece, Piece, Piece]);
  var topPieces = new Stripe(pLeftTop, pRightTop, TOP);
  var leftPieces = new Stripe(pLeftTop, pLeftBottom, LEFT);
  var rightPieces = new Stripe(pRightTop, pRightBottom, RIGHT);
  var bottomPieces = new Stripe(pLeftBottom, pRightBottom, BOTTOM);
  return (topPieces.isValid() && 
          leftPieces.isValid() &&
          rightPieces.isValid() &&
          bottomPieces.isValid() && 
          Piece.prototype.isValid(topPieces.getSize(), leftPieces.getSize()));
}
 

Board.prototype.merge = function (pLeftTop, pRightTop, pLeftBottom, pRightBottom) {
	assert(this.canMerge(pLeftTop, pRightTop, pLeftBottom, pRightBottom));
    var topPieces = new Stripe(pLeftTop, pRightTop, TOP);
    var leftPieces = new Stripe(pLeftTop, pLeftBottom, LEFT);
    var rightPieces = new Stripe(pRightTop, pRightBottom, RIGHT);
    var bottomPieces = new Stripe(pLeftBottom, pRightBottom, BOTTOM);
	var x = topPieces.getSize();
	var y = leftPieces.getSize();
	assert(topPieces.size.equals(bottomPieces.getSize()));
	assert(leftPieces.size.equals(rightPieces.getSize()));
	var newPiece = new ConnectedPiece(topPieces.getStart(), leftPieces.getStart(), topPieces.getSize(), leftPieces.getSize(), pLeftTop.color);
	
	this._reconnect(topPieces.pieces, [newPiece], TOP);
	this._reconnect(bottomPieces.pieces, [newPiece], BOTTOM);
	this._reconnect(leftPieces.pieces, [newPiece], LEFT);
	this._reconnect(rightPieces.pieces, [newPiece], RIGHT);
	
	this._updateNeighborConnectionsMerge(topPieces.pieces, newPiece, TOP);
  	this._updateNeighborConnectionsMerge(bottomPieces.pieces, newPiece, BOTTOM);
	this._updateNeighborConnectionsMerge(leftPieces.pieces, newPiece, LEFT);
  	this._updateNeighborConnectionsMerge(rightPieces.pieces, newPiece, RIGHT);
  
    var newPieces = new Array();
    var numSkipped = 0;
    for (var i = 0; i < this.pieces.length; i++) {
      if (this.pieces[i].start[HORIZONTAL].smaller(newPiece.start[HORIZONTAL]) ||
          this.pieces[i].start[VERTICAL].smaller(newPiece.start[VERTICAL]) ||
          this.pieces[i].end[HORIZONTAL].bigger(newPiece.end[HORIZONTAL]) ||
          this.pieces[i].end[VERTICAL].bigger(newPiece.end[VERTICAL])) {
        newPieces.push(this.pieces[i]);
      } else {
        numSkipped += 1;
      }
    }
    newPieces.push(newPiece);
    this._replacePieces(newPieces);
    return [newPiece];
}


Board.prototype.isPieceCaptured = function(piece, color) {
  assertParams(arguments, [Piece, Number]);
  var includingCorners = true;
  var connectedToBorder = this._foundPathToBorder(piece, includingCorners, color);
  for (var i = 0; i < this.pieces.length; i++) {
    this.pieces[i].markedConnected = false;
  }
  return !connectedToBorder;
}

Board.prototype.aligned = function(p1, p2) {
  for (var dir = 0; dir < 2; dir++) {
    if (p1.start[dir].equals(p2.start[dir]) && p1.end[dir].equals(p2.end[dir]) &&
        (p1.start[OPPOSITE_DIR[dir]].equals(p2.end[OPPOSITE_DIR[dir]]) ||
         p1.end[OPPOSITE_DIR[dir]].equals(p2.start[OPPOSITE_DIR[dir]]))) {
          return true;
    }
  }         
  return false;
}


Board.prototype._foundPathToBorder = function(piece, includingCorners, color) {
  if (piece.markedConnected) {
    return false;
  }
  piece.markedConnected = true;
  for (var i = 0; i < 4; i++) {
    if (piece.connections[i].length == 0) {
      return true;
    }
  }
  for (var i = 0; i < 4; i++) {
    for (var j = 0; j < piece.connections[i].length; j++) {
      var neighbor = piece.connections[i][j];
      if (neighbor.color != color && this._foundPathToBorder(neighbor, includingCorners, color)) {
          return true;
      }
    }
  }
  if (includingCorners) {
	  var corners = this._getCorners(piece);
	  for (var j = 0; j < 4; j++) {
	    if (corners[j].color != color && this._foundPathToBorder(corners[j], includingCorners, color)) {
	      return true;
	    }
	  }
  }
  return false;
}

Board.prototype._getCorners = function(piece) {
  var topLeft =     this.getPieceEndX  (piece.start[HORIZONTAL],                piece.start[VERTICAL].float() - TINY) ||
                    this.getPieceEndY  (piece.start[HORIZONTAL].float() - TINY, piece.start[VERTICAL]);
  var topRight =    this.getPieceStartX(piece.end  [HORIZONTAL],                piece.start[VERTICAL].float() - TINY) ||
                    this.getPieceEndY  (piece.end  [HORIZONTAL].float() + TINY, piece.start[VERTICAL]);
  var bottomLeft =  this.getPieceEndX  (piece.start[HORIZONTAL],                piece.end[VERTICAL].float() + TINY) ||
                    this.getPieceStartY(piece.start[HORIZONTAL].float() - TINY, piece.end[VERTICAL]);
  var bottomRight = this.getPieceStartX(piece.end  [HORIZONTAL],                piece.end[VERTICAL].float() + TINY) ||
                    this.getPieceStartY(piece.end  [HORIZONTAL].float() + TINY, piece.end[VERTICAL]);
  return [topLeft, topRight, bottomLeft, bottomRight];
  
}


Board.prototype.evaluate = function() {
  for (var i = 0; i < this.pieces.length; i++) {
    this.pieces[i].linkToBorder = [false, false, false, false];
    this.pieces[i].marked = [false, false, false, false];
    this.pieces[i].isolated = true;
    this.pieces[i].numLinksToBorders = 0;
  }
  
  // matched to the beginning of sides
  var corners = [[TINY, TINY], [TINY, this.y-TINY], [TINY, TINY], [this.x-TINY, TINY]];
  for (var side = 0; side < 4; side++) {  
    var piece = this.getPiece(corners[side][0], corners[side][1]);
    do {
      if (!piece.marked[side]) {
        this._deepLink(piece, side);
      }
      if (piece.connections[ORTHOGONAL_SIDE[side]].length > 0) {
        var k = (side == TOP || side == LEFT) ? 0 : piece.connections[ORTHOGONAL_SIDE[side]].length - 1;
        piece = piece.connections[ORTHOGONAL_SIDE[side]][k];
      } else {
        piece = null;
      }
    } while (piece);
  }
  for (var i = 0; i < this.pieces.length; i++) {
    this.pieces[i].marked = [false, false, false, false];
  }
 
}


Board.prototype.getWinningColor = function() {
  for (var i = 0; i < this.pieces.length; i++) {
    if (this.pieces[i].numLinksToBorders == 4) {
       return this.pieces[i].color;
    }
  }
  return NULL_COLOR;
}
      

Board.prototype._deepLink = function(piece, side) {
  piece.marked[side] = true;
  this._linkPieceToSide(piece, side);
  for (var i = 0; i < 4; i++) {
    for (var j = 0; j < piece.connections[i].length; j++) {
      var neighbor = piece.connections[i][j];
      if (neighbor.color == piece.color) {
        if (!neighbor.marked[side]) {
          this._deepLink(neighbor, side);
        }
      }
    }
  }
  if (piece.isolated) {
    this._deepLinkCorners(piece);
  }
}

Board.prototype._deepLinkCorners = function(piece) {
  piece.isolated = false;
  var corners = this._getCorners(piece);
  for (var i = 0; i < 4; i++) {
    var neighbor = corners[i];
    if (neighbor && neighbor.color == piece.color && neighbor.isolated) {
      this._deepLinkCorners(neighbor);
    }
  }
  for (var i = 0; i < 4; i++) {
    for (var j = 0; j < piece.connections[i].length; j++) {
      var neighbor = piece.connections[i][j];
      if (neighbor.color == piece.color && neighbor.isolated) {
        this._deepLinkCorners(neighbor);
      }
    }
  }
}


Board.prototype._linkPieceToSide = function(piece, side) {
  piece.linkToBorder[side] = true;
  piece.numLinksToBorders += 1;
}


Board.prototype.resetCapturedPieces = function(idAndAfter) {
  for (var i = 0; i < this.pieces.length; i++) {
    if (this.pieces[i].captured > idAndAfter) {
      this.pieces[i].captured = 0;
    }
  }
}

Board.prototype.captureIsolatedPieces = function(doCapture, id) {
  for (var i = 0; i < this.pieces.length; i++) {
    if (doCapture && this.pieces[i].captured > 0) {
	      this.pieces[i].swap();
	      this.pieces[i].isolated = false;
    } else if (this.pieces[i].isolated && this.pieces[i].numLinksToBorders == 0) {
        this.pieces[i].captured = id;
    }
  }
}

Board.prototype.equivalent = function(piece) {
  return this._lookup(piece.start);
  //return this.getPiece(piece.start[HORIZONTAL].float() + TINY, piece.start[VERTICAL].float() + TINY);
}

Board.prototype.equiStart = function(start) {
  var x = new Rational(start[0].top, start[0].bot);
  var y = new Rational(start[1].top, start[1].bot);
  
  return this._lookup([x, y]);
  //return this.getPiece(
  //   new Rational(start[HORIZONTAL].top, start[HORIZONTAL].bot).float() + TINY, new Rational(start[VERTICAL].top, start[VERTICAL].bot).float() + TINY);
}

toTest.push(Board);

Board.prototype.test = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  assert(board.pieces.length === side * side);
  assert(board.material(BLACK) === side * side / 2);
  var numConn = 0;
  for (var i = 0; i < board.pieces.length; i++) {
    for (var j = 0; j < 4; j++) {
      if (board.pieces[i].connections[j].length > 0) {
        numConn += 1;
        assert(board.pieces[i].connections[j].length === 1);
        assert(board.pieces[i].connections[j][0].color !== board.pieces[i].color);
      }
    }
  }
  assert(numConn === (side - 1) * side * 4);
  
  board = new Board (5, 3);
  board.build();
  assert(board.pieces.length === 15);
  assert(board.material(BLACK) === board.material(WHITE) + 1);
  Board.prototype.testMergeConnections();
  Board.prototype.testDistributeConnections();
  //Board.prototype.testUpdateNeighborConnectionsSplit();
  //Board.prototype.testUpdateNeighborConnectionsMerge();
  Board.prototype.testSplit();
  Board.prototype.testMerge2();
  Board.prototype.testMerge4();
  Board.prototype.testMergeUnaligned();
  Board.prototype.testSplitAndMerge();
  Board.prototype.testSplitAndMultiMerge();
  Board.prototype.testPieceCaptured();
  Board.prototype.testEvaluate();
  Board.prototype.testCapture();
  Board.prototype.testClone();
};

Board.prototype._getCornersOld = function(piece) {
  return [this.getPiece(piece.start[HORIZONTAL].float() - TINY, piece.start[VERTICAL].float() - TINY),
          this.getPiece(piece.end[HORIZONTAL].float() + TINY, piece.start[VERTICAL].float() - TINY),
          this.getPiece(piece.start[HORIZONTAL].float() - TINY, piece.end[VERTICAL].float()+ TINY),
          this.getPiece(piece.end[HORIZONTAL].float() + TINY, piece.end[VERTICAL].float() + TINY),
         ];
}


Board.prototype._assertCornersValid = function(piece) {
  var cornersNew = this._getCorners(piece);
  var cornersOld = this._getCornersOld(piece);
  for (var i = 0; i < 4; i++) {
    if (cornersNew[i] == null) {
      assert(cornersOld[i] == null);
    } else {
      assert(cornersNew[i].start[HORIZONTAL].equals(cornersOld[i].start[HORIZONTAL]));
      assert(cornersNew[i].start[VERTICAL].equals(cornersOld[i].start[VERTICAL]));
      assert(cornersNew[i].x.equals(cornersOld[i].x));
      assert(cornersNew[i].y.equals(cornersOld[i].y));
    }
  }
}

Board.prototype.testSplit = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var piece = board.pieces[8];
  var fromPieces = [piece];
  board.split(piece, HORIZONTAL);
  assert(board.pieces.length = side * side + 1);
  assert(board.material(WHITE) == board.material(BLACK));
  board._assertPieceFound(piece, false);
  var connectedToTwoPieces = board._getNumConnectionsToNPieces(2);
  var numSmallPieces = board._getNumPiecesOfSize(ONE, ONE.half());
  assert(connectedToTwoPieces === 2);
  assert(numSmallPieces === 2);
  board._assertValid();
}

Board.prototype.testSplitAndMerge = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var piece = board.pieces[8];
  var fromPieces = [piece];
  board.split(piece, HORIZONTAL);
  var topNeighbor = piece.connections[TOP][0];
  var p1 = topNeighbor.connections[BOTTOM][0];
  assert(p1.x.half().equals(p1.y));
  var p2 = p1.connections[BOTTOM][0];
  assert(p2.x.half().equals(p2.y));
  board.merge(p1, p1, p2, p2);
  board._assertValid();
  
  
  assert(board.pieces.length = side * side);
  assert(board.material(WHITE) == board.material(BLACK));
  board._assertPieceFound(piece, false);
  board._assertPieceFound(p1, false);
  board._assertPieceFound(p2, false);
  var connectedToOnePiece = board._getNumConnectionsToNPieces(1);
  var numSmallPieces = board._getNumPiecesOfSize(ONE, ONE.half());
  assert(connectedToOnePiece === side * (side - 1) * 4);
  assert(numSmallPieces === 0);
  board._assertValid();
}

Board.prototype.testSplitAndMultiMerge = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var piece = board.getPiece(5.1, 5.1);
  board.split(piece, HORIZONTAL);
  var next = board.getPiece(4.1, 4.1);
  board.split(next, HORIZONTAL);
  var top = board.getPiece(4.1, 4.1);
  var bottom = board.getPiece(4.1, 4.6);
  board.split(bottom, VERTICAL);
  var leftBottom = board.getPiece(4.1, 4.6);
  var rightBottom = board.getPiece(4.6, 4.6);
  board.merge(top, top, leftBottom, rightBottom);
  board._assertValid();
}


Board.prototype.testMerge2 = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var x = 3;
  var y = 3;
  
  var pLeft = board.pieces[y * side + x];
  var pRight = board.pieces[y * side + x + 1];
  
  pRight.color = pLeft.color;
  board.merge(pLeft, pRight, pLeft, pRight);
  assert(board.pieces.length == side * side - 2 + 1);
  board._assertPieceFound(pLeft, false);
  board._assertPieceFound(pRight, false);
  var connectedToTwoPieces = board._getNumConnectionsToNPieces(2);
  assert(connectedToTwoPieces === 2);
  board._assertValid();
}


Board.prototype.testMergeUnaligned = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var p1 = board.getPiece(TINY, TINY);
  var p2 = board.getPiece(TINY, 1.0+TINY);
  pieces1 = board.split(p1, HORIZONTAL);
  assert(pieces1.length == 2 && pieces1[0].start[VERTICAL].smaller(pieces1[1].start[VERTICAL]));
  pieces2 = board.split(p2, HORIZONTAL);
  assert(pieces2.length == 2 && pieces2[0].start[VERTICAL].smaller(pieces2[1].start[VERTICAL]));
  pieces2[0].swap();
  var merged = board.merge(pieces1[1],pieces1[1],pieces2[0], pieces2[0])[0];
  board._assertCornersValid(merged);
  board._assertValid();
  return board;
}

Board.prototype.testClone = function() {
  var board = this.testMergeUnaligned();
  var newBoard = board.clone();
  newBoard._assertValid();
}


Board.prototype.testMerge4 = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var x = 3;
  var y = 3;
  
  var pLeftTop = board.pieces[y * side + x];
  var pRightTop = board.pieces[y * side + x + 1];
  var pLeftBottom = board.pieces[(y + 1 ) * side + x];
  var pRightBottom = board.pieces[(y + 1 ) * side + x+1];
  
  pRightTop.color = pLeftTop.color;
  pLeftBottom.color = pLeftTop.color;
  pRightBottom.color = pLeftTop.color;
  var merged = board.merge(pLeftTop, pRightTop, pLeftBottom, pRightBottom)[0];
  board._assertCornersValid(merged);
  assert(board.pieces.length == side * side - 4 + 1);
  board._assertPieceFound(pLeftTop, false);
  board._assertPieceFound(pRightTop, false);
  board._assertPieceFound(pLeftBottom, false);
  board._assertPieceFound(pRightBottom, false);
  var connectedToTwoPieces = board._getNumConnectionsToNPieces(2);
  assert(connectedToTwoPieces === 4);
  board._assertValid();
}

Board.prototype._getNumConnectionsToNPieces = function(n) {
  var numConnections = 0;
  for (var i = 0; i < this.pieces.length; i++) {
    for (var j = 0; j < 4; j++) {
      if (this.pieces[i].connections[j].length === n) {
        numConnections += 1;
      }
    }
  }
  return numConnections;
}

Board.prototype._getNumPiecesOfSize = function(x, y) {
  var num = 0;
  for (var i = 0; i < this.pieces.length; i++) {
    if (this.pieces[i].x.equals(x) && this.pieces[i].y.equals(y)) {
      num += 1;
    }
  }
  return num;
}

Board.prototype.testMergeConnections = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var connections = board._mergeConnections([board.pieces[side + 1], board.pieces[side + 2]], BOTTOM);
  assert(connections.length === 2);
  assert(connections[0] === board.pieces[side * 2 + 1]);
  assert(connections[1] === board.pieces[side * 2 + 2]);
}

Board.prototype.testDistributeConnections = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var p1 = board.pieces[side + 1];
  var c1 = p1.connections[BOTTOM][0];
  var p2 = board.pieces[side + 2];
  var c2 = p2.connections[BOTTOM][0];
  var pieces = [p1, p2];
  var connections = board._mergeConnections(pieces, BOTTOM);
  this._distributeConnections(pieces, connections, BOTTOM);
  assert(p1.connections[BOTTOM].length == 1);
  assert(p2.connections[BOTTOM].length == 1);
  assert(p1.connections[BOTTOM][0] == c1);  // new object is created
  assert(p2.connections[BOTTOM][0] == c2);
}


Board.prototype.testWrongCaptureOnMerge = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var p0 = board.pieces[0];
  var p1 = board.pieces[1];
  p1.swap();
  var p2 = board.pieces[7];
  p2.swap();
  small = board.split(p2, HORIZONTAL);
  var large = board.merge(small[0], small[0], small[1], small[1]);
  board._assertCornersValid(p0);
}
  
  
Board.prototype.testReconnect = function() {
  var side = 6;
  var board = new Board(side, side);
  board.build();
  var p1 = board.piece[side + 1];
  var p2 = board.piece[side + 2];
  p2.color = p1.color;
  var p = new ConnectionPiece(p1.x.add(p2.x), p1.y.add(p2.y), p1.color);
  var fromConnections = [p1, p2];
  var toConnections = [p];
  board.reconnect(fromConnections, toConnections, BOTTOM);
  assert(board.piece[side * 2 + 1].connections[TOP] === p);
  assert(board.piece[side * 2 + 2].connections[TOP] === p);
  
  
  var connections = board._mergeConnections(pieces, BOTTOM);
  this._distributeConnections(pieces, connections, BOTTOM);
  assert(p1.connections[BOTTOM].length == 1);
  assert(p2.connections[BOTTOM].length == 1);
  assert(p1.connections[BOTTOM][0] !== c1);  // new object is created
  assert(p2.connections[BOTTOM][0] !== c2);
}


Board.prototype._assertPieceFound = function(piece, find) {
  if (find === undefined) find = false;
  for (var i = 0; i < this.pieces.length; i++) {
    if (this.pieces[i] === piece) {
      if (find) return true;
      else assert(false);
    }
    for (var j = 0; j < 4; j++) {
      for (var c = 0; c < this.pieces[i].connections[j].length; c++) {
        if (this.pieces[i].connections[j][c] === piece) {
          if (find) return true;
          else assert(false);
        }
      }
    }
  }
  if (find) {
    assert(false);
  }
}

Board.prototype.testPieceCaptured = function() {
  var s = 6;
  var board = new Board(s, s);
  board.build();
  assert(!board.isPieceCaptured(board.pieces[15], BLACK));
  assert(!board.isPieceCaptured(board.pieces[15], WHITE));
  var i = 9;
  var p = board.pieces[i];
  board.pieces[i-s-1].swap();
  board.pieces[i-s+1].swap();
  board.pieces[i+s-1].swap();
  assert(!board.isPieceCaptured(p, OPPOSITE_COLOR[p.color]));
  board.pieces[i+s+1].swap();
  assert(board.isPieceCaptured(p, OPPOSITE_COLOR[p.color]));
  assert(!board.isPieceCaptured(p, p.color));
}

Board.prototype.testEvaluate = function() {
  var s = 3;
  var board = new Board(s, s);
  board.build();
  // win
  board.pieces[4].swap();
  board.evaluate();
  var counts = [0, 0, 0, 0, 0];
  for (var i = 0; i < board.pieces.length; i++) {
    counts[board.pieces[i].numLinksToBorders]++;
  }
  assert(counts[0] == 0);
  assert(counts[1] == 0);
  assert(counts[2] == 4); // corners
  assert(counts[3] == 0);
  assert(counts[4] == 5); // cross
  
  board.build();
  // capture - swap corners
  board.pieces[0].swap();
  board.pieces[2].swap();
  board.pieces[6].swap();
  board.pieces[8].swap();
  board.evaluate();
  var counts = [0, 0, 0, 0, 0];
  var numIsolated = 0;
  for (var i = 0; i < board.pieces.length; i++) {
    counts[board.pieces[i].numLinksToBorders]++;
    if (board.pieces[i].isolated) {
      numIsolated += 1;
    }
  }
  assert(numIsolated == 1);
  assert(counts[0] == 1); // center
  assert(counts[1] == 0);
  assert(counts[2] == 0);
  assert(counts[3] == 0);
  assert(counts[4] == 8); // all around
}

Board.prototype.testCapture = function() {
  var board = new Board(5,5);
  board.build();
  var i = 12;
  var prevColor = board.pieces[i].color;
  board.pieces[i].swap();
  board.evaluate();
  board.captureIsolatedPieces();
  assert(board.pieces[i].color != prevColor); //no capture
}