var EMPTY = 0;
var BLACK = 1;
var WHITE = 2;

function Board(size) {
	this.size = size;
	
	//intersections
	this._ints = new Array(size);
	for(var x = 0; x < size; x++) {
		this._ints[x] = new Array(size);
		for(var y = 0; y < size; y++) {
			this._ints[x][y] = new Intersection(x, y);
		}
	}
	this.stateHistory = [];
	
	//the following require update to be accurate
	this.capturedCountsByStone = [null, 0, 0];
	this.scoreByStone = [null, 0, 0];
	this.libertiesByStone = [null, 0, 0];
	
	this.eyesByStone = [null, 0, 0];
	this.aliveCountByStone = [null, 0, 0];
	
	//this.chainLengthsByChainId;
	//this.touchingChainIdsByChainId;
	//this.chainTouchingCountsByChainIdAndStone;
	//this.eyeCountByChainId;
	//this.chainColorByChainId;//todo
}

Board.prototype.clone = function() {
	var cloneBoard = new Board(this.size);
	//copy the Intersections
	this.eachInt(function(i) {
		cloneBoard.setInt(i.pos.x, i.pos.y, i.clone());
	});
	//copy the state history
	for(var i = 0; i <this.stateHistory.length; i++)
		cloneBoard.stateHistory[i] = this.stateHistory[i];
	//copy capture log
	cloneBoard.capturedCountsByStone = [
		null,
		this.capturedCountsByStone[1],
		this.capturedCountsByStone[2]
	];

	//the close will require an update for the meta-data to be valid
	return cloneBoard;
};

Board.prototype.toStoneString = function() {
	var sb = [];
	this.eachInt(function(i) {
		sb.push(i.stone);
	});
	return sb.join('');
};

Board.prototype.getInt = function(x, y) {
	if(typeof(x) == "number" && typeof(y) == "number") {
		return this._ints[x][y];
	} else if(x.constructor == Position) {
		return this._ints[x.x][x.y];
	}
};

Board.prototype.setInt = function(x, y, intersection) {
	this._ints[x][y] = intersection;
};

Board.prototype.eachInt = function(func) {
	for(var y = 0; y < this.size; y++) {
		for(var x = 0; x < this.size; x++) {
			func(this.getInt(x, y));
		}
	}  
};

Board.prototype.render = function() {
	var canvas = jQuery('canvas#board').get(0);
	if(!canvas || !canvas.getContext) {
		log("Canvas Error!");
		return;
	}
	var myBoard = this;
	var w = canvas.width, h = canvas.height;
	var cellSize = w / this.size;
	var halfCellSize = cellSize / 2;
	var ctx = canvas.getContext('2d');
	
	//board background
	ctx.fillStyle = "#fc1";
	ctx.fillRect (0, 0, w, h);
	
	//grid
	ctx.beginPath();
	ctx.strokeStyle = '#555';
	for(var i = 0; i < this.size; i++) {
		//vertical lines
		var x = halfCellSize + (cellSize * i);
		ctx.moveTo(x, halfCellSize);
		ctx.lineTo(x, h - halfCellSize);
		//horizontal lines
		var y = halfCellSize + (cellSize * i);
		ctx.moveTo(halfCellSize, y);
		ctx.lineTo(h - halfCellSize, y);
	}
	ctx.closePath();
	ctx.stroke();
	
	//draw stones
	this.eachInt(function(i) {
		if(i.stone == 0) return;
		var x = halfCellSize + (cellSize * i.pos.x);
		var y = halfCellSize + (cellSize * i.pos.y);
		ctx.beginPath();
		//if it's live, use a green edge instead of gray
		if(i.isAlive) {
			ctx.strokeStyle = 'green';
		} else {
			ctx.strokeStyle = '#555';
		}
		
		if(i.stone == 1) {//black
			ctx.fillStyle = "black";
		} else if (i.stone == 2) {//white
			ctx.fillStyle = "white";
		}
		
		ctx.arc(x, y, 0.9 * halfCellSize, 0, 2*Math.PI, false);
		ctx.fill();
		ctx.stroke();
	});
	ctx.closePath();
	//draw territory as little squares
	//and eyes as little green dots
	var rectSize = 0.2 * halfCellSize;
	this.eachInt(function(i) {
		if(i.stone == 0 && i.territory != 0) {
			var x = halfCellSize + (cellSize * i.pos.x);
			var y = halfCellSize + (cellSize * i.pos.y);
			ctx.beginPath();
			if(i.territory == 1) {//black
				ctx.fillStyle = "black";
			} else if (i.territory == 2) {//white
				ctx.fillStyle = "white";
			}
			ctx.fillRect(x - rectSize / 2, y - rectSize / 2, rectSize, rectSize);
			ctx.strokeStyle = '#555';
			ctx.strokeRect(x - rectSize / 2, y - rectSize / 2, rectSize, rectSize);
			if(i.eye != 0) {
				ctx.fillStyle = "green";
				ctx.arc(x, y, 0.05 * halfCellSize, 0, 2*Math.PI, false);
				ctx.fill();
			}
		}
	});
	ctx.closePath();
	
	//score
	jQuery('#score').html(this.scoreByStone[1] + " - " + this.scoreByStone[2]);
	//show turn
	if(turn == 1) jQuery('#turn').html("Black's turn.");
	else jQuery('#turn').html("White's turn.");
};

//really, this just finds the captures
Board.prototype.doCaptures = function(turn) {
	var myBoard = this;
	
	this.findChains();
	this.findChainTouchingCountsByChainIdAndStone();
	
	var captured = [];
	this.eachInt(function(i) {
		if(i.stone != 0) {//if not empty
			//can't be captured on your own turn, otherwise, captured if not touching empty
			if(i.stone != turn && myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][0] == 0) {
				captured.push(i);
			}
		}
	});
	for(var x in captured) {
		var i = captured[x];
		myBoard.capturedCountsByStone[i.stone] += 1;
		i.stone = 0;
	}
}

Board.prototype.makeMove = function(pos, turn) {
	var isValid = this.isValidMove(pos, turn);
	if(isValid) {
		this.getInt(pos).stone = turn;
		this.updateState(turn);
		this.stateHistory.push(this.toStoneString());
    }
    return isValid;
};

//only call from makeMove (why??)
Board.prototype.isValidMove = function(pos, turn) {
	if(this.getInt(pos).stone != 0) {
		//log("taken! " + pos);
		return false;//space isn't empty (panic!!)
	}
	
	var nextBoard = this.clone();
	//place stone on board
	nextBoard.getInt(pos).stone = turn;
	//chance to capture others
	nextBoard.doCaptures(turn);
	//chance for others to capture
	nextBoard.doCaptures(getNextTurn(turn));
	
	if(nextBoard.getInt(pos).stone == 0) {
		//log("suicide! " + pos);
		return false;//captured right away!
	}
	
	//write the current state for ko checks
    nextBoard.stateHistory.push(nextBoard.toStoneString());
    
	//check for ko
	if(nextBoard.stateHistory.length > 2) {
		var nextState = nextBoard.stateHistory[nextBoard.stateHistory.length - 1];
		
		if(nextBoard.stateHistory[nextBoard.stateHistory.length - 3] == nextState) {
			//log("ko! " + pos);
			return false;
		}
	
		//check for superko
		for(var i = 0; i < nextBoard.stateHistory.length - 2; i++) {
			if(nextBoard.stateHistory[i] == nextState) {
				//log("superko! " + pos);
				return false;
			}
		}
	}
	
	return true;
};

Board.prototype.updateState = function(turn) {
	var myBoard = this;
	
	this.doCaptures(turn);
	
	this.findChains();
	this.findChainTouchingCountsByChainIdAndStone();
	this.findChainLengthsByChainId();
	this.findTouchingChainIdsByChainId();
	this.findEyes();
	this.findEyeCountByChainId();
	
	//find territory and score
	this.scoreByStone = [null, this.capturedCountsByStone[2], this.capturedCountsByStone[1]];
	this.libertiesByStone = [null, 0, 0];
	this.eachInt(function(i) {
		i.territory = 0;//default (not a territory)
		if(i.stone == 0) {//is empty
			//if it touches only black, it's a black territory
			if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][1] != 0
					&& myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][2] == 0) {
				i.territory = 1;
				myBoard.scoreByStone[1] += 1;
			}//if it touches only white, it's a white territory
			else if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][1] == 0
					&& myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][2] != 0) {
				i.territory = 2;
				myBoard.scoreByStone[2] += 1;
			}
			
			//if it touches black, it's a black liberty
			var touchingBlack = false;
			var touchingWhite = false;
			var touching = myBoard.getTouching(i);
			for(var t in touching) {
				if(touching[t].stone == 1) touchingBlack = true;
				if(touching[t].stone == 2) touchingWhite = true;
			}
			if(touchingBlack) myBoard.libertiesByStone[1] += 1;
			if(touchingWhite) myBoard.libertiesByStone[2] += 1;
		}
	});  
};//updateState

Board.prototype.findChains = function() {
	var myBoard = this;
	//find chains
	//init each intersection with no chainId
	this.eachInt(function(i) {
		i.chainId = null;
	});
	var nextChainId = 1;
	this.eachInt(function(i) {
		//skip if this has already been chained
		if(i.chainId === null) {
			var chainStone = i.stone;
			
			var todoList = [i];
			var todoHash = {i:1};
			while(i = todoList.shift()) {
				//if this intersection (i) has the same kind of stone
				//and it's not already part of a chain
				//continue the chain
				if(i.stone == chainStone && i.chainId == null) {
					//mark the membership
					i.chainId = nextChainId;
					//add touching points to todo list
					var touching = myBoard.getTouching(i);
					todoList = todoList.concat(touching);
				}
			}//end while
			nextChainId += 1;
		}
	});
};

//given an intersection
//returns a list of the touching intersections (not walls)
//if nonEmpty is true, then only get the non-empty touching intersections
Board.prototype.getTouching = function(int, nonEmpty) {
	var touching = [];
	if(int.pos.x > 0)
		touching.push(this.getInt(int.pos.x-1, int.pos.y));
	if(int.pos.x < this.size - 1)
		touching.push(this.getInt(int.pos.x+1, int.pos.y));
	if(int.pos.y > 0)
		touching.push(this.getInt(int.pos.x, int.pos.y-1));
	if(int.pos.y < this.size - 1)
		touching.push(this.getInt(int.pos.x, int.pos.y+1));
	if(nonEmpty) {
		for(var i = 0; i < touching.length; i++) {
			if(touching[i].stone == 0) {
				touching.splice(i, 1);
				i--;
			}
		}
	}
	return touching;
};

//finds a hash indexed by chainId with values of chain length
Board.prototype.findChainLengthsByChainId = function() {
	var chainLengthsByChainId = {};
	this.eachInt(function(i) {
		if(!chainLengthsByChainId[i.chainId])
			chainLengthsByChainId[i.chainId] = 0;
		chainLengthsByChainId[i.chainId]++;
	});
	this.chainLengthsByChainId = chainLengthsByChainId;
};

//finds hash of arrays of other chainIds that touch the key chainId
Board.prototype.findTouchingChainIdsByChainId = function() {
	var touchingChainIdsByChainId = {};
	var myBoard = this;
	this.eachInt(function(i) {
		if(!touchingChainIdsByChainId[i.chainId])
			touchingChainIdsByChainId[i.chainId] = [];
		var touching = myBoard.getTouching(i);
    	for(var j = 0; j < touching.length; j++) {
			if(i.chainId != touching[j].chainId && touchingChainIdsByChainId[i.chainId].indexOf(touching[j].chainId) == -1)
				touchingChainIdsByChainId[i.chainId].push(touching[j].chainId);
    	}
	});
	this.touchingChainIdsByChainId = touchingChainIdsByChainId;
};

//finds a two dimensional array, first indexed by chainId, then by stone
//the value is the number of stones of the given color the given chainId is touching
Board.prototype.findChainTouchingCountsByChainIdAndStone = function() {
	var counts = [];
	var myBoard = this;
	this.eachInt(function(i) {
		//init if needed
		if(counts[i.chainId] == undefined) {
			counts[i.chainId] = [0, 0, 0];
		}
		//get chainIds touching this intersection
		//(unique, and not chained with this intersection)
		var touchingUniqueChainIds = [];//weird array, chainIds are keys
		var touching = myBoard.getTouching(i);
		for(var j = 0; j < touching.length; j++) {
			if(touching[j].chainId != i.chainId) {
				touchingUniqueChainIds[touching[j].chainId] = true;
			}
		}
		//for each chainId, increment the cound of this intersection's stone
		for(var chainId in touchingUniqueChainIds) {
			//init if needed
			if(counts[chainId] == undefined) {
				counts[chainId] = [0, 0, 0];
			}
			counts[chainId][i.stone] += 1;
		}
	});
	this.chainTouchingCountsByChainIdAndStone = counts;
};

Board.prototype.findEyes = function() {
	this.findEyes4();
};

//find eyes (method 1.  looks for small empty areas surrounded by a single chain)
Board.prototype.findEyes1 = function() {
	var myBoard = this;
	this.eyesByStone = [null, 0, 0];
	this.eachInt(function(i) {
		i.eye = 0;//default (not an eye)
		if(i.stone == 0) {//is empty
			//check for eye (this doesn't find all eyes, but what it does find are eyes)
			if(myBoard.touchingChainIdsByChainId[i.chainId].length == 1 //only touching 1 other chain
				&& myBoard.chainLengthsByChainId[i.chainId] < 3)//and chain length < 3
			{
				if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][1] > 0) {//if touching black
					i.eye = 1;
					myBoard.eyesByStone[1]++;
				}
				else if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][2] > 0) {//if touching white
					i.eye = 2;
					myBoard.eyesByStone[2]++;
				}
			}
		}
	});
};

/*
//find eyes (method 2.  looks for empty spaces with surrounding chains with other liberty/ies - not good)
Board.prototype.findEyes2 = function() {
	var myBoard = this;
	this.eyesByStone = [null, 0, 0];
	this.eachInt(function(i) {
		i.eye = 0;//default (not an eye)
		if(i.stone == 0  && myBoard.chainLengthsByChainId[i.chainId] == 1) {//is empty and size 1
			//determine color for eye
			var eyeColor = null;
			if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][1] > 0
				&& myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][2] == 0)
				eyeColor = 1;
			else if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][1] > 0
				&& myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][2] == 0)
				eyeColor = 2;
			
			if(eyeColor != null) {
				i.eye = 1;//assume it's an eye for now
				
				//for each touching chain id
				for(var j = 0; j < myBoard.touchingChainIdsByChainId[i.chainId].length; j++) {
					var touchingChainId = myBoard.touchingChainIdsByChainId[i.chainId][j];
					//alert(i.pos + ' is touching chains:' + myBoard.touchingChainIdsByChainId[i.chainId]);
					//does that chain have >1 liberty (basically, something other than this intersection)
					if(myBoard.chainTouchingCountsByChainIdAndStone[touchingChainId][0] < 2) {//problem
						i.eye = 0;
						break;
					}
				}
				
				if(i.eye) {
					myBoard.eyesByStone[eyeColor]++;
				}
			}
		}
	});
};

//find eyes (method 3.  is it NOT capturable by the opponent? (in one turn?))
Board.prototype.findEyes3 = function() {
	var myBoard = this;
	this.eyesByStone = [null, 0, 0];
	this.eachInt(function(i) {
		i.eye = 0;//default (not an eye)
		if(i.stone == 0 && myBoard.chainLengthsByChainId[i.chainId] == 1) {//is empty and size 1
			//determine color for eye
			var eyeColor = null;
			if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][1] > 0
				&& myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][2] == 0)
				eyeColor = 1;
			else if(myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][1] > 0
				&& myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][2] == 0)
				eyeColor = 2;
			
			if(eyeColor != null) {
				var opponent = (eyeColor == 1) ? 2 : 1;
				//if(console && console.log) console.log(i.pos + ' eyeColor: ' + eyeColor + ' opponent: ' + opponent);
				if(myBoard.isValidMove(i.pos, opponent) == false) {
				//if(console && console.log) console.log("It's an eye!");
					i.eye = eyeColor;
					myBoard.eyesByStone[eyeColor]++;
				}
			} 
		}
	});
};
*/


//find eyes (method 4.  looks for unplayable positions of opponent)
//http://senseis.xmp.net/?RecognizingAnEye
Board.prototype.findEyes4 = function() {
	var myBoard = this;
	this.eyesByStone = [null, 0, 0];
	var diagonals;
	var owner, opponent;
	var opponentValidDiagonalPositionCount;
	
	this.eachInt(function(i) {
		i.eye = 0;//default (not an eye)
		if (i.stone == EMPTY && myBoard.chainLengthsByChainId[i.chainId] == 1) {//is empty and size 1
			owner = null;
			opponent = null;
			opponentValidDiagonalPositionCount = 0;
			
			if (myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][WHITE] == 0) {
				owner = BLACK;
				opponent = WHITE;
			} else if (myBoard.chainTouchingCountsByChainIdAndStone[i.chainId][BLACK] == 0) {
				owner = WHITE;
				opponent = BLACK;
			}
			
			if(owner !== null) {
				//count how many diagonals opponent can move in
				diagonals = myBoard.getDiagonals(i);
				for(var d in diagonals) {
					if(myBoard.getInt(diagonals[d]).stone == opponent 
							|| myBoard.isValidMove(diagonals[d], opponent))
						opponentValidDiagonalPositionCount++;
				}
				// opponent must NOT be able to take 3/4 for normal cases or x/x for edge cases
				// middle area = 4 diagonals, edge = 2, corner = 1
				if((diagonals.length == 4 && opponentValidDiagonalPositionCount < 2)
						|| (diagonals.length < 4 && opponentValidDiagonalPositionCount == 0)) {
					i.eye = owner;
					myBoard.eyesByStone[owner]++;
				}
			}
		}
	});
};

//given an intersection
//returns a list of the diagonal positions (walls are not returned)
Board.prototype.getDiagonals = function(i) {
	var diagonals = [];
	
	if(i.pos.x > 0 && i.pos.y > 0)//UL
		diagonals.push(new Position(i.pos.x-1, i.pos.y-1));
	if(i.pos.x > 0 && i.pos.y < this.size - 1)//UR
		diagonals.push(new Position(i.pos.x-1, i.pos.y+1));
	if(i.pos.x < this.size - 1 && i.pos.y > 0)//DL
		diagonals.push(new Position(i.pos.x+1, i.pos.y-1));
	if(i.pos.x < this.size - 1 && i.pos.y < this.size - 1)//DR
		diagonals.push(new Position(i.pos.x+1, i.pos.y+1));
		
	return diagonals;
};

//find eye count by ChainId
Board.prototype.findEyeCountByChainId = function() {
	var myBoard = this;
	var touchingEyeChainIdsByChainId = {};
	this.eachInt(function(i) {
		var touching = myBoard.getTouching(i);
		if(!touchingEyeChainIdsByChainId[i.chainId])
			touchingEyeChainIdsByChainId[i.chainId] = [];//make sure that every chain is counted (even if count is 0)
		for(var j = 0; j < touching.length; j++) {
			if(touching[j].eye != 0) {
				if(touchingEyeChainIdsByChainId[i.chainId].indexOf(touching[j].chainId) == -1)
					touchingEyeChainIdsByChainId[i.chainId].push(touching[j].chainId);
			}
		}
	});
	
	var eyeCountByChainId = {};
	for(var chainId in touchingEyeChainIdsByChainId)
		eyeCountByChainId[chainId] = touchingEyeChainIdsByChainId[chainId].length;
	
	//find isAlive and aliveCountByStone
	this.aliveCountByStone = [null, 0, 0];
	this.eachInt(function(i) {
		if(i.stone != 0 && eyeCountByChainId[i.chainId] > 1) {
			i.isAlive = true;
			myBoard.aliveCountByStone[i.stone]++;
		}
	});
	this.eyeCountByChainId = eyeCountByChainId;
};


function Position(x, y) {
	this.x = x;
	this.y = y;
}

Position.prototype.toString = function() {
	return "{'x':" + this.x + ",'y':" + this.y + "}"; 
};

function Intersection(x, y) {
	this.pos = new Position(x, y);
	this.stone = 0;//0 = empty, 1 = black, 2 = while
	this.chainId = null;
	this.territory = 0;//0 = not a territory
	this.eye = 0;//0 = non an eye
	this.isAlive = false;
	this.rating = -1;
}

Intersection.prototype.toString = function() {
	var str = "{\n";
	for(var prop in this) {
		if(typeof this[prop] != "function") {
			if(str.length > 2)
				str += "\n,";
			str += "'" + prop + "':" + this[prop];
		}
	}
	str += "\n}";
	return str;
};

Intersection.prototype.clone = function() {
	var cloneIntersection = new Intersection();
	for(var prop in this) {
		if(typeof prop != "function") {
			cloneIntersection[prop] = this[prop];
		}
	}
	return cloneIntersection;
};