class MazeSolver {
	constructor(startingCell, targetCell, searchedColor = [210, 180, 140]){
		this.frontier = [];
		this.explored = [];
		
		this.targetCell = targetCell;
		this.searchedColor = searchedColor;
		this.currentCell = startingCell;
		this.frontier.push(startingCell);
		this.statesExplored = 0;
	}
	
	clearState(){
		this.frontier = [];
		this.explored = [];
		this.statesExplored = 0;
	}
	
	highlightFinalPath(maze, finalPathColor = [173, 216, 230], startingCellColor = [255, 0, 0], endingCellColor = [0, 0, 255]){
		let tmp = this.explored.pop();
		
		tmp.color = endingCellColor;
		
		tmp = tmp.parent;
		
		while(tmp != undefined){
			tmp.color = finalPathColor;
			
			if(tmp.parent == undefined)
				tmp.color = startingCellColor;

			tmp = tmp.parent;
		}
		
	    maze.updateMazeDisplay();
	}
}

class DepthFirstSolver extends MazeSolver {
	solve(maze) {
		this.currentCell.color = this.searchedColor;
		
		this.currentCell = this.frontier.pop();
		
		this.currentCell.visited = true;
		
		let moves = maze.getLegalMoves(this.currentCell);
		
		for (let i = 0; i < moves.length; i++){
			this.frontier.push(moves[i]);
			moves[i].parent = this.currentCell;
		}
		
		this.explored.push(this.currentCell);
		this.statesExplored++;
		
		if(this.currentCell.x == this.targetCell.x && this.currentCell.y == this.targetCell.y) {
			this.frontier = [];
			this.currentCell.color = this.searchedColor;
			
		}
	}
}

class BreadthFirstSolver extends MazeSolver {
	solve(maze) {
		this.currentCell.color = this.searchedColor;
		
		this.currentCell = this.frontier.shift();
		
		this.currentCell.visited = true;
		
		let moves = maze.getLegalMoves(this.currentCell);
		
		for (let i = 0; i < moves.length; i++){
			this.frontier.push(moves[i]);
			moves[i].parent = this.currentCell;
		}
		
		this.explored.push(this.currentCell);
		this.statesExplored++;
		
		if(this.currentCell.x == this.targetCell.x && this.currentCell.y == this.targetCell.y)
			this.frontier = [];
			this.currentCell.color = this.searchedColor;
	}	
}

class GreedyDepthFirstSolver extends MazeSolver {
	solve(maze) {
		let lowest = Infinity;
		
		this.currentCell.color = this.searchedColor;
		
		this.currentCell = this.frontier.pop();
		
		this.currentCell.visited = true;
		
		let moves = maze.getLegalMoves(this.currentCell);
		print(moves);
		this.sortFrontier(moves);
		print(moves);
		for (let i = 0; i < moves.length; i++){
			this.frontier.push(moves[i]);
			moves[i].parent = this.currentCell;
		}
		
		this.explored.push(this.currentCell);
		this.statesExplored++;
		
		if(this.currentCell.x == this.targetCell.x && this.currentCell.y == this.targetCell.y)
			this.frontier = [];
			this.currentCell.color = this.searchedColor;
	}
	// Quick and dirty bubble sort
	sortFrontier(list){
		if(list.length == 1) return;
		
		let swapped = true;
		
		while(swapped){
			for(let i = 0; i < list.length - 1; i++){
				var current = this.calcDistance(this.targetCell, list[i]);
				var next = this.calcDistance(this.targetCell, list[i + 1]);
				
				if(current < next){
					let tmp = list[i];
					let tmp2 = list[i+1];
					list[i + 1] = tmp2;
					list[i] = tmp;
					swapped = true;
				}
				else swapped = false;
			}
		}
	}
	
	calcDistance(target, current){
		let x = target.x - current.x;
		let y = target.y - current.y;
		
		return x + y;
	}
}