import java.util.ArrayList;
import java.util.List;

public class ShortestPath {

	private CityMap cityMap;

	public ShortestPath(CityMap cityMap) {
		super();
		this.cityMap = cityMap;
	}

	private boolean isValidUpPath(MapCell cell) {
		if (cell.isNorthRoad() || cell.isDestination() ||cell.isIntersection()) {
			return true;
		}

		return false;

	}

	private boolean isValidDownPath(MapCell cell) {
		if (cell.isSouthRoad() || cell.isDestination() ||cell.isIntersection()) {
			return true;
		}

		return false;

	}

	private boolean isValidLeftPath(MapCell cell) {
		if (cell.isWestRoad() || cell.isDestination() ||cell.isIntersection()) {
			return true;
		}

		return false;

	}

	private boolean isValidRightPath(MapCell cell) {
		if (cell.isEastRoad() || cell.isDestination() ||cell.isIntersection()) {
			return true;
		}

		return false;

	}

	private boolean isValidPath(MapCell cell) {
		if (cell.isNorthRoad() || cell.isEastRoad() || cell.isSouthRoad() || cell.isWestRoad() || cell.isDestination() ||
				cell.isIntersection()) {
			return true;
		}

		return false;

	}

	public void findShortestPath() {
		OrderedCircularArray orderedList = new OrderedCircularArray();
		MapCell  theCell = cityMap.getStart();
		orderedList.insert(theCell, 0);
		theCell.markInList();
		int distanceToStart = 0;
		boolean destFound = false;
		MapCell currentCell = null;


		while (!orderedList.isEmpty()) {

			 currentCell = (MapCell) orderedList.getSmallest();

				if (currentCell.isDestination()) {
					destFound = true;
					currentCell.markOutList();
					break;
				}

				currentCell.markOutList();

			    ArrayList neibourCells = this.nextCells(currentCell);
			    if (neibourCells != null) {
			    for (int i = 0; i < neibourCells.size(); i++) {
			        MapCell neibourCell = (MapCell) neibourCells.get(i);
			   		distanceToStart = currentCell.getDistanceToStart() + 1;
					int nerbourDistance = neibourCell.getDistanceToStart();
					if(distanceToStart < nerbourDistance) {
						nerbourDistance =  distanceToStart;
						neibourCell.setDistanceToStart(distanceToStart);
						neibourCell.setPredecessor(currentCell);
					}

					if(neibourCell.isMarkedInList()) {
						int existingDistance = orderedList.getValue(neibourCell);
						if (nerbourDistance < existingDistance) {
							orderedList.changeValue(neibourCell, nerbourDistance);
						}
					}
					else {
						orderedList.insert(neibourCell, nerbourDistance);
						neibourCell.markInList();
					}


				}
		}

	    }

		if(destFound) {
			System.out.println("Destination reached.");
			System.out.println("The number of cells in the path from the starting cell to the destination = "+(currentCell.getDistanceToStart()));
			}
		else {
				System.out.println("Destination cannot be reached.");
		}


	}


	private MapCell nextCell(MapCell cell) {
		MapCell bestCell = null;
		int destIndex = -1;
		int crossIndex = -1;
		int roadIndex = -1;

	    if  (cell.isNorthRoad() && cell.getNeighbour(0) != null
	    			) {
			if(isValidUpPath(cell.getNeighbour(0))&& !cell.getNeighbour(0).isMarked())
				return cell.getNeighbour(0);
			else
				return null;
		}

	    else if (cell.isEastRoad() && cell.getNeighbour(1) != null ) {

	    	if(isValidRightPath(cell.getNeighbour(1))&& !cell.getNeighbour(1).isMarked())
				return cell.getNeighbour(1);
			else
				return null;
		}


	    else if  (cell.isSouthRoad() && cell.getNeighbour(2) != null ) {
	    	if(isValidDownPath(cell.getNeighbour(2))&& !cell.getNeighbour(2).isMarked())
				return cell.getNeighbour(2);
			else
				return null;
		}

	    else if (cell.isWestRoad() && cell.getNeighbour(3) != null ) {

	    	if(isValidLeftPath(cell.getNeighbour(3))&& !cell.getNeighbour(3).isMarked())
				return cell.getNeighbour(3);
			else
				return null;
		}

	    else {
				for (int i = 0;  i < 4; i ++) {

					// if cell exists
					if (cell.getNeighbour(i) != null) {

						// if cell is NOT marked
						if (!cell.getNeighbour(i).isMarked()) {

							if (cell.getNeighbour(i).isDestination()) {

								destIndex = i;
							}

							else if (cell.getNeighbour(i).isIntersection()) {
								 if (crossIndex == -1)crossIndex = i;
								//bestCell = cell.getNeighbour(i);
							}

							else if ((cell.getNeighbour(i).isNorthRoad() && i == 0) || (cell.getNeighbour(i).isSouthRoad() && i == 2) ||
									(cell.getNeighbour(i).isWestRoad() && i == 3) || (cell.getNeighbour(i).isEastRoad() && i == 1)) {
								if (roadIndex == -1)roadIndex = i;
								//bestCell = cell.getNeighbour(i);
							}


						}
					}
				}

				if (destIndex > -1)
					return cell.getNeighbour(destIndex);
				else if (crossIndex > -1)
					return cell.getNeighbour(crossIndex);
				else if (roadIndex > -1)
					return cell.getNeighbour(roadIndex);
	    }
				return bestCell;
	}

	private ArrayList<MapCell> nextCells(MapCell cell) {
		ArrayList<MapCell> bestCells = new ArrayList<MapCell>();

	if  (cell.isNorthRoad() && cell.getNeighbour(0) != null ) {
		if(isValidUpPath(cell.getNeighbour(0))&& !cell.getNeighbour(0).isMarked()) {
			bestCells.add(cell.getNeighbour(0));
			return bestCells;
		}
		else
			return null;
	}

    else if (cell.isEastRoad() && cell.getNeighbour(1) != null ) {

    	if(isValidRightPath(cell.getNeighbour(1))&& !cell.getNeighbour(1).isMarked()) {
    		bestCells.add(cell.getNeighbour(1));
			return bestCells;
    	}
		else
			return null;
	}


    else if  (cell.isSouthRoad() && cell.getNeighbour(2) != null ) {
    	if(isValidDownPath(cell.getNeighbour(2))&& !cell.getNeighbour(2).isMarked()) {
    		bestCells.add(cell.getNeighbour(2));
			return bestCells;
    	}
		else
			return null;
	}

    else if (cell.isWestRoad() && cell.getNeighbour(3) != null ) {

    	if(isValidLeftPath(cell.getNeighbour(3))&& !cell.getNeighbour(3).isMarked()) {
    		bestCells.add(cell.getNeighbour(3));
			return bestCells;
    	}

		else
			return null;
	}
    else {
		for (int i = 0;  i < 4; i ++) {

			// if cell exists
			if (cell.getNeighbour(i) != null && !cell.getNeighbour(i).isMarked()) {

					if (cell.getNeighbour(i).isDestination() || cell.getNeighbour(i).isIntersection()) {

						bestCells.add(cell.getNeighbour(i));

					}

					else if ((cell.getNeighbour(i).isNorthRoad() && i == 0) || (cell.getNeighbour(i).isSouthRoad() && i == 2) ||
							(cell.getNeighbour(i).isWestRoad() && i == 3) || (cell.getNeighbour(i).isEastRoad() && i == 1)) {

						bestCells.add(cell.getNeighbour(i));
					}

			}
		}
  }

		return  bestCells;
	}
}