/*
 * author: Bjoern Guenzel guenzel@blinker.net
 * Copyright © 2009 Bjoern Guenzel
 */

var Utils = {};
Utils.stringToArray = function(s){
	var a = new Array(s.length);
	for(var i = 0; i < s.length;i++){
		a[i] = s.charAt(i);
	}
	return a;
}

function Player(name) {
 	this.name = name;
}

/*
 * main class
 */
function Halma(boardTypeName, playerConstellation){//numberOfPlayers, setsPerPlayer) {
	//this.numberOfPlayers = numberOfPlayers;
        this.boardTypeName = boardTypeName;
	this.boardType = Halma[boardTypeName];
	//this.setsPerPlayer = setsPerPlayer;
	this.playerConstellation = playerConstellation;
	this.distance = this.boardType.distance;//OPTIMIZE might save some time, or maybe not?
	this.playersCount = this.playerConstellation.length;

	this.piece2playersMap = new Array(playerConstellation[0].length*this.playersCount);
	for(var k = 0; k < playerConstellation.length;k++){
		for(var l = 0; l < playerConstellation.length;l++){
			this.piece2playersMap[playerConstellation[k][l]] = k;
		}
	}	
	this.maxScore = this.boardType.clearedScore*playerConstellation[0].length;
	
	this.activePlayer = 0;

	this.history = [];//history of moves

	//array of array of piece coordinates: [[[p00_x,p00_y],[p01_x,p01_y],...],...,[[pi0_x,pi0_y],[pi1_x,pi1_y],...],...]
	this.pieceCoordinates = map(function(){return [];},range(this.boardType.maxPlayers));

	this.scores = map(function(){return 0;}, range(this.playersCount));//init scores with 0
	
	this.winner = null;

	// use board to represent player stones, rather than list of coordinates. 
	// Think will be faster for AI
	// copy board prototype to active board
	this.board = new Array(this.boardType.board.length);
	
	for(var i = 0;i<this.boardType.board.length;i++){
		this.board[i] = new Array(this.boardType.board[i].length);
		
		for(var j = 0; j < this.boardType.board[i].length;j++){
			var tile = this.tileType(j,i);//boardType.board[i][j];
			var isPieceInPlay = this.isPieceInPlay(tile);
			if(!(Halma.TILE_ILLEGAL == tile || isPieceInPlay)){
				//copy only pieces that are used in the game  
				tile = Halma.TILE_EMPTY;
			}			
			this.board[i][j] = tile;
			//log("write tile "+tile+" to "+j+", "+i+", isPlayerTile: "+Halma.isPlayerTile(tile));
			//update initial score

			if(isPieceInPlay) {
				//prepare initial score
				this.scores[this.piece2playersMap[tile]] += this.getDistanceToDestination(j,i, tile);

				//save piece coordinates
				this.pieceCoordinates[tile].push([j,i]);
			}
			
		}	
	}

}

Halma.prototype.getDistanceToDestination = function(x,y, piece) {
	var opposing = this.boardType.opposing[piece];
	var corner = this.boardType.corners[opposing];
	return this.distance(x,y,corner[0],corner[1]);
}

//TODO quick hack to make it accessible with Web Workers. Make more elegant some time
Halma.prototype.getSerializableGameStateWithoutHistory = function() {
    var board = new Array(this.boardType.board.length);
    //log("board dimension i: "+board.length+", type: "+this.boardType);
    //copy board
    for(var j = 0;j<this.boardType.board.length;j++){
	board[j] = new Array(this.boardType.board[j].length);
	for(var i = 0; i < this.boardType.board[j].length;i++){
	    board[j][i] = this.getPosition(i,j);
	}
    }

    var scores = map(operator.identity, this.scores);
    var activePlayer = this.activePlayer;
    var pieceCoordinates = map(function(coords){return coords ? map(operator.identity, coords) : null},this.pieceCoordinates);
    var winner = this.winner;

    return {
        boardTypeName: this.boardTypeName,
        playerConstellation: this.playerConstellation,//FIXME should only copy the key
        board: board,
        scores: scores,
        activePlayer: activePlayer,
        pieceCoordinates: pieceCoordinates,
        winner: winner
    };
};

Halma.createFromSerializableGameState = function(gameState) {
    var clone = new Halma(gameState.boardTypeName, gameState.playerConstellation);//FIXME remove wasteful stuff in constructor
    clone.board = gameState.board;
    clone.scores = gameState.scores;
    clone.activePlayer = gameState.activePlayer;
    clone.pieceCoordinates = gameState.pieceCoordinates;
    clone.winner = gameState.winner;
    return clone;
};

Halma.prototype.cloneWithoutHistory = function(){
    return Halma.createFromSerializableGameState(this.getSerializableGameStateWithoutHistory());
};

Halma.prototype.isPieceInPlay = function(piece) {
	return some(this.playerConstellation, function(constellation){return some(flattenArray(constellation), partial(operator.eq, piece));});
}

Halma.prototype.getPosition = function(x, y) {
	//log("get position "+x+", "+y);
	if(x < 0 || y < 0 || y >= this.board.length || x >= this.board[y].length){
		//log("tile type for "+x+", "+y+": illegal");
		return Halma.TILE_ILLEGAL;
	} 
	return this.board[y][x];
}

Halma.prototype.setPosition = function(x, y, newPiece) {
	this.board[y][x] = newPiece;
}

Halma.prototype.isStarted = function() {
	return history.length > 0;
}

//move consists of list of coordinates, first coordinate is piece to be moved, last is target, jumps in between
//isNotValidating skips validation, useful if we know the move is correct.
Halma.prototype.doMove = function(move, isNotValidating) {
	//log("doMove: "+move);
	
	
	if(move.length > 0) {
		//TODO check can not move if length == 0, otherwise illegal move
		
		// sometimes skip validation, for example to speed up the AI
		if(!isNotValidating) {
			this.validateMove(move, 0);
		}
	

		//move piece
		this.movePiece(move[0], move[move.length-1]);

	}
	
	this.history.push(move);

	//update active player
	this.activePlayer = (this.activePlayer+1)%this.playersCount;

	//log("move done, next player: "+this.activePlayer);

	return true;
}

Halma.prototype.movePiece = function(go_from, go_to) {
	var toX = go_to[0];
	var toY = go_to[1];
	
	var fromX = go_from[0];
	var fromY = go_from[1];

	var piece = this.getPosition(fromX, fromY);

	this.setPosition(toX, toY, this.getPosition(fromX, fromY));
	this.setPosition(fromX, fromY, Halma.TILE_EMPTY);

	//update pieceCoordinates
	var index = findValue(this.pieceCoordinates[piece], [fromX, fromY]);
	this.pieceCoordinates[piece][index][0] = toX;
	this.pieceCoordinates[piece][index][1] = toY;	

	//logDebug("new pieceCoordinates: "+repr(this.pieceCoordinates));

	//update score and check victory conditions

	this.scores[this.activePlayer] += (this.getDistanceToDestination(toX,toY, piece)-this.getDistanceToDestination(fromX, fromY, piece));

	//update victory condition 
	if(this.scores[this.activePlayer] == this.maxScore && !this.winner){
		this.winner = this.activePlayer;
	} else if(this.scores[this.activePlayer] != this.maxScore && this.winner == this.activePlayer) {
		this.winner = null;		
	}
}

Halma.prototype.undoLastMove = function(){
	var move = this.history.pop();
	//log("undoMove: "+move);
	//update active player
	this.activePlayer = (this.activePlayer-1+this.playersCount)%this.playersCount;

	if(move.length > 0) {
		this.movePiece(move[move.length-1], move[0]);
	}
	//logDebug("move undone");
}

/* add all allowed moves starting from the given moves, up to a maximum length
 * possibleMoves = [[target, move],...] 
 * possibleTargets = [target1,...]
 * maxDepth == 0 is infinite depth
 */
Halma.prototype.collectPossibleMoves = function(moves, step, maxDepth, possibleMoves, fieldsToUnmark) {
	//log("collect possible moves step "+step);

	if(maxDepth > 0 && step > maxDepth) {
		return moves;
	}

	var lastPosition = moves[moves.length-1];
	var piece = this.getPosition(moves[0][0],moves[0][1]);//OPTIMIZE
	var sourceTile = this.tileType(moves[0][0],moves[0][1]);
	
	forEach(this.boardType.directions, method(this, function(dir){
		var x = dir[0]+lastPosition[0];
		var y = dir[1]+lastPosition[1];

		var targetPiece = this.getPosition(x,y);
		var tile = this.tileType(x,y);
		
		var isPossible = false;
		var isJump = false;		

		var isTargetForbiddenTerritory = this.isForbiddenTerritoryForPiece(tile, piece);
		var isStartFromDestination = this.isDestinationForPiece(this.tileType(lastPosition[0],lastPosition[1]), piece);

		if(Halma.isPlayerTile(targetPiece)) {
			//evaluate jumps
			isJump = true;

			var isStartFromEnemyTerritory = this.isForbiddenTerritoryForPiece(sourceTile, piece);
			
			x = x+dir[0];
			y = y+dir[1];

			tile = this.tileType(x,y);
			targetPiece = this.getPosition(x,y);

			isTargetForbiddenTerritory = this.isForbiddenTerritoryForPiece(tile, piece);

			if(targetPiece == Halma.TILE_EMPTY 			
			   && !(isStartFromEnemyTerritory && isTargetForbiddenTerritory)
			   && !(isStartFromDestination && !this.isDestinationForPiece(tile, piece))){
				isPossible = true;		
			}
			
		} else if(step == 0 && targetPiece == Halma.TILE_EMPTY && !isTargetForbiddenTerritory 
				&& !(isStartFromDestination && !this.isDestinationForPiece(tile, piece))) {//check don't enter enemy ground and don't leave destination base
			//possible one field move
			isPossible = true;
		}

		if(isPossible) {
			//add target to list of possible targets
			var target = [x,y];
			moves.push(target);
			fieldsToUnmark.push(target);

			if(!isTargetForbiddenTerritory) {//can't stop on enemy territory, so don't record that step
				possibleMoves.push([target, map(operator.identity, moves)]);//copy move
			} 

			//mark board as visited
			this.setPosition(x,y, Halma.TILE_MARKED);

			//recurse if jump
			if(isJump) {
				this.collectPossibleMoves(moves, step+1, maxDepth, possibleMoves, fieldsToUnmark);
			}
			moves.pop();
		}
	}));

	//OPTIMIZE
	//unmark fields if not within recursion
	if(step == 0) {
		forEach(fieldsToUnmark, method(this, function(marked) {
			this.setPosition(marked[0],marked[1],Halma.TILE_EMPTY);
		}));
	}
}

//throw Exception if move invalid
Halma.prototype.validateMove = function(move, step, allowEnemyBase, piece) {
	
	//TODO replace with collectPossibleMoves -> look if target is in possible moves...
	//but then no error messages, so keep old code for the time being

	if(!move || move.length - step < 2) {//TODO check booleans in Javascript
		throw new Error("invalid move, undefined move or too short: "+repr(move)+", !move: "+!move+", length-step: "+(move.length - step)+", length: "+move.length+", step: "+step);
	}

	var source = move[step];
	var target = move[step+1];

	if(!piece){
		piece = this.getPosition(move[0][0], move[0][1]);
	
		//check source is piece of active player
		if(!this.isActivePlayPiece(piece)) {
			throw new Error("move invalid, stone does not belong to active player: "+repr(move));
		}
	};

	//check target is empty field
	if(!this.isEmptyTile(target[0], target[1])) {
		throw new Error("invalid move, target not empty: "+repr(move));
	}
	
	//check is 1 step move or jump - if step > 0, only jumps allowed

	var dx = target[0]-source[0];
	var dy = target[1]-source[1];

	var factor = Math.abs(dx != 0 ? dx : dy);//assume one step coordinate always size 1

	if(factor > 2 || factor < 1 || (factor == 1 && (step > 0 || move.length > 2))) {
		throw new Error("invalid move, jump farther than two steps or move 1 field after first step or continue after intial move: "+repr(move));
	}

	var direction = null;

	loop: for(var i = 0; i < this.boardType.directions.length; i++){
		var dir = this.boardType.directions[i];
		if(dx == factor * dir[0] && dy == factor * dir[1]) {
			direction = dir;
			break loop;
		}	
	}

	if(direction == null) {
		throw new Error("invalid move, no valid direction found: "+repr(move));
	}

	if(factor == 2 && !Halma.isPlayerTile(this.getPosition(source[0]+direction[0], source[1]+direction[1]))){
		throw new Error("invalid move, can't jump over empty space: "+repr(move));
	}

	//check must not leave destination base if has been reached
	
	var sourceTileType = this.tileType(source[0], source[1]);
	var targetTileType = this.tileType(target[0], target[1]);

	if(sourceTileType != targetTileType && this.isDestinationForPiece(sourceTileType, piece)) {
		throw new Error("invalid move, can't leave destination: "+repr(move));
	}

	//check must leave enemy base in next step
	
	if(!allowEnemyBase && this.isForbiddenTerritoryForPiece(targetTileType, piece)
		&& (step == move.length-2 || this.isForbiddenTerritoryForPiece(sourceTileType, piece))) {
		throw new Error("invalid move, must leave enemy base: "+repr(move));
	}
	
	//TODO maybe check long jumps for "fast paced" Hong Kong version

	//recursively check following moves
	if(step+2 < move.length){
		return this.validateMove(move, step+1);//OPTIMIZE allowEnemyBase and Piece
	} else {
		return true;
	}
}

Halma.prototype.isActivePlayPiece = function(piece) {
	var isActivePiece = some(this.playerConstellation[this.activePlayer], partial(operator.eq,piece));	
	//log("isActivePlayPiece: "+piece+", player: "+this.activePlayer+", result: "+isActivePiece);
	
	return isActivePiece;
}	

Halma.prototype.isInBoardBoundaries = function(x, y) {
	return x >= 0 && y >= 0 && y < this.board.length && x < this.board[0].length;
}

Halma.prototype.isEmptyTile = function(x, y){
	return this.isInBoardBoundaries(x, y) && Halma.TILE_EMPTY == this.getPosition(x, y);
}

Halma.prototype.isForbiddenTerritoryForPiece = function(tileType, piece) {
	if(!Halma.isPlayerTile(tileType) || this.isDestinationForPiece(tileType, piece)){
		return false;
	}
	for(var i = 0; i < this.playerConstellation.length;i++){
		var hasTile = false; hasPiece = false;
		for(var j = 0;j< this.playerConstellation[i].length;j++){
			if(this.playerConstellation[i][j] == tileType) {
				hasTile = true;
			}
			if(this.playerConstellation[i][j] == piece) {
				hasPiece = true;
			}
		}
		if(hasTile || hasPiece) {
			return !(hasTile && hasPiece);
		}
		
	}
	return false;
}

Halma.prototype.isDestinationForPiece = function(tileType, piece){
	if(!Halma.isPlayerTile(tileType)){
		return false;
	}

	return this.boardType.opposing[piece] == tileType;
}


/* return tile type, if it is a number n, it designates the homebase of the n-th player */
Halma.prototype.tileType = function(x, y){
	var type;
	
	if(x < 0 || y < 0 || y >= this.boardType.board.length || x >= this.boardType.board[y].length){
		//log("tile type for "+x+", "+y+": illegal");
		return Halma.TILE_ILLEGAL;
	} else {
		var type = this.boardType.board[y][x];
		//log("tile type for "+x+", "+y+": "+type+" isEmpty: "+Halma.isEmptyTile(type)+", is illegal: "+(type == Halma.TILE_ILLEGAL));		
		return Halma.isEmptyTile(type) ? type : (type == Halma.TILE_ILLEGAL ? type : parseInt(type)); 		
	}
}


/*
 * Tile types: empty, or 0-n for homebase of player
 */
Halma.TILE_EMPTY = 'w';
Halma.TILE_MARKED = 'm';
Halma.TILE_ILLEGAL = '#';//coordinates not on board

Halma.isEmptyTile = function(t) {
	return t == Halma.TILE_EMPTY || t == Halma.TILE_MARKED;
}

Halma.isPlayerTile = function(t) {
	return !Halma.isEmptyTile(t) && t != Halma.TILE_ILLEGAL;
}



Halma.BOARD_STAR_HALMA = { /* top point has coordinates 5,0, leftmost coordinates 0,5, some fields illegal 
		  * x coordinates 60°: /
		  */
		dimension : 17,
		maxPlayers : 6,
		playerConstellations: [[[0],[3]], [[0,1],[3,4]],[[0,3],[1,4]],[[0,1,2],[3,4,5]],//two players constellations
					[[0,3],[1,4],[2,5]],[[0],[2],[4]],//3 players constellations
					[[0],[1],[3],[4]],//4 players 
					[[0],[1],[2],[3],[4]],//5 players consteallation
					[[0],[1],[2],[3],[4],[5]]],//6 players constellation
		directions : [[-1,-1], /* top left */
				[0,-1], /* top right */
				[-1,0],/* left */	
				[1,0], /* right */
				[0,1], /* bottom left*/
				[1,1] /* bottom right */		
		],
		distance : function(x1,y1,x2,y2){
			//if top right or bottom left
			if((x1 < x2 && y1 > y2) || (x1 > x2 && y1 < y2)){
				return Math.abs(x2-x1)+Math.abs(y2-y1);
			} else {
				return Math.max(Math.abs(x2-x1), Math.abs(y2-y1));
			}
		},
		opposing : [3,4,5,0,1,2],//opposing[i] = opposing corner of i [[0,3],[1,4],[2,5]],
		corners : [[4,0], [12,4], [16,12], [12,16], [4,12], [0,4]],//used to calculate "score" for AI
		clearedScore : 20,//sum of distances of stones from the corner, when they are all "homed"
		piecesPerCorner : 10,
		board : [/* # = outside of board, w = white fields in middle, number n = homebase of player n */ 
			Utils.stringToArray("####0############"),
			Utils.stringToArray("####00###########"),
			Utils.stringToArray("####000##########"),
			Utils.stringToArray("####0000#########"),
			Utils.stringToArray("5555wwwww1111####"),
			Utils.stringToArray("#555wwwwww111####"),
			Utils.stringToArray("##55wwwwwww11####"),
			Utils.stringToArray("###5wwwwwwww1####"),
			Utils.stringToArray("####wwwwwwwww####"),
			Utils.stringToArray("####4wwwwwwww2###"),
			Utils.stringToArray("####44wwwwwww22##"),
			Utils.stringToArray("####444wwwwww222#"),
			Utils.stringToArray("####4444wwwww2222"),
			Utils.stringToArray("#########3333####"),
			Utils.stringToArray("##########333####"),
			Utils.stringToArray("###########33####"),
			Utils.stringToArray("############3####")]


};

Halma.BOARD_STAR_HALMA_2_PLAYERS = { /* top point has coordinates 5,0, leftmost coordinates 0,5, some fields illegal 
		  * x coordinates 60°: /
		  */
		dimension : 17,
		maxPlayers : 6,
		playerConstellations: [[[5],[2]]],//6 players constellation
		directions : [[-1,-1], /* top left */
				[0,-1], /* top right */
				[-1,0],/* left */	
				[1,0], /* right */
				[0,1], /* bottom left*/
				[1,1] /* bottom right */		
		],
		distance : function(x1,y1,x2,y2){
			//if top right or bottom left
			if((x1 < x2 && y1 > y2) || (x1 > x2 && y1 < y2)){
				return Math.abs(x2-x1)+Math.abs(y2-y1);
			} else {
				return Math.max(Math.abs(x2-x1), Math.abs(y2-y1));
			}
		},
		opposing : [3,4,5,0,1,2],//opposing[i] = opposing corner of i [[0,3],[1,4],[2,5]],
		corners : [[4,0], [12,4], [16,12], [12,16], [4,12], [0,4]],//used to calculate "score" for AI
		clearedScore : 40,//sum of distances of stones from the corner, when they are all "homed"
		piecesPerCorner : 15,
		board : [/* # = outside of board, w = white fields in middle, number n = homebase of player n */ 
			Utils.stringToArray("####0############"),
			Utils.stringToArray("####00###########"),
			Utils.stringToArray("####000##########"),
			Utils.stringToArray("####0000#########"),
			Utils.stringToArray("55555wwww1111####"),
			Utils.stringToArray("#5555wwwww111####"),
			Utils.stringToArray("##555wwwwww11####"),
			Utils.stringToArray("###55wwwwwww1####"),
			Utils.stringToArray("####5wwwwwww2####"),
			Utils.stringToArray("####4wwwwwww22###"),
			Utils.stringToArray("####44wwwwww222##"),
			Utils.stringToArray("####444wwwww2222#"),
			Utils.stringToArray("####4444wwww22222"),
			Utils.stringToArray("#########3333####"),
			Utils.stringToArray("##########333####"),
			Utils.stringToArray("###########33####"),
			Utils.stringToArray("############3####")]


};


Halma.BOARD_SQUARE_2_PLAYERS = {
	dimension : 16,
	maxPlayers : 2,
	playerConstellations: [[[0],[1]]], 
	directions : [[-1,-1], /* top left */
			[0,-1], /* top */
			[1,-1], /* top right */
			[-1,0],/* left */	
			[1,0], /* right */
			[-1,1], /* bottom left*/
			[0,1], /* bottom */
			[1,1] /* bottom right */		
		],
	distance : function(x1,y1,x2,y2){
		return Math.max(Math.abs(x2-x1), Math.abs(y2-y1));
	},
	opposing : [1,0],//opposing[i] = opposing corner of i[[0,1]],
	corners : [[0,0], [15,15]],//used to calculate "score" for AI
	clearedScore : 47,//sum of distances of stones from the corner, when they are all "homed"
	piecesPerCorner : 19,
	board : [
		Utils.stringToArray("00000###########"),
		Utils.stringToArray("00000###########"),
		Utils.stringToArray("0000############"),
		Utils.stringToArray("000#############"),
		Utils.stringToArray("00##############"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("##############11"),
		Utils.stringToArray("#############111"),
		Utils.stringToArray("############1111"),
		Utils.stringToArray("###########11111"),
		Utils.stringToArray("###########11111")
	]
};

	
Halma.BOARD_SQUARE_4_PLAYERS = {
	dimension : 16,
	maxPlayers : 4,
	playerConstellations : [[[0],[1],[2],[3]]],
	directions : [[-1,-1], /* top left */
			[0,-1], /* top */
			[1,-1], /* top right */
			[-1,0],/* left */	
			[1,0], /* right */
			[-1,1], /* bottom left*/
			[0,1], /* bottom */
			[1,1] /* bottom right */		
		],
	distance : function(x1,y1,x2,y2){
		return Math.max(Math.abs(x2-x1), Math.abs(y2-y1));
	},
	opposing : [2,3,0,1],//opposing[i] = opposing corner of i[[0,2],[1,3]],
	piecesPerCorner : 13,
	corners : [[0,0], [15,0], [15,15], [0,15]],//used to calculate "score" for AI
	clearedScore : 25,//sum of distances of stones from the corner, when they are all "homed"
	board : [
		Utils.stringToArray("0000########1111"),
		Utils.stringToArray("0000########1111"),
		Utils.stringToArray("000##########111"),
		Utils.stringToArray("00############11"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("################"),
		Utils.stringToArray("33############22"),
		Utils.stringToArray("333##########222"),
		Utils.stringToArray("3333########2222"),
		Utils.stringToArray("3333########2222")
	]
};