import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Searcher {
	private Queue<State> openSet;
	private List<State> closedSet;

	public Searcher(){
		this.openSet = new PriorityQueue<State>(10, new Comparator<State>(){

			@Override
			public int compare(State o1, State o2){
				if (o1.getDistance() < o2.getDistance()){
					return -1;
				} if (o1.getDistance() > o2.getDistance()){
					return 1;
				} else {
					return 0;
				}
			}
		});

		this.closedSet = new LinkedList<State>();
	}

	public void aStarSearch(Goal goal, Graph g){
		int totalCost = 0;
		int nodesExpanded = 0;

		State prevTrip = null;

		State start = new State("London", 0);
		openSet.add(start);


		while (!openSet.isEmpty()){
			prevTrip = openSet.poll();
			closedSet.add(prevTrip);
			nodesExpanded++;
			checkNeighbour(prevTrip, g);
			goal.setGoalReached(checkGoalReached(goal, closedSet.get(closedSet.size()-1)));

			if (goal.getGoalReached() == true){
				totalCost = closedSet.get(closedSet.size()-1).getDistance() + getTransferTime(g, closedSet.get(closedSet.size()-1));
				break;
			}
			System.out.println(closedSet.get(closedSet.size()-1).getCurrCity());
			System.out.println(closedSet.get(closedSet.size()-1).getDistance());
		}
		getPath(nodesExpanded, totalCost, closedSet.get(closedSet.size()-1));
	}

	public boolean checkGoalReached(Goal g, State n){
		boolean goalReached = true;
		Iterator<GoalData> itr = g.getTripData().iterator();

		while (itr.hasNext()){
			if (stateLooper(itr.next(), n)== false){
				goalReached = false;
				break;
			}
		}

		return goalReached;
	}

	public boolean stateLooper(GoalData g, State n){
		boolean check = false;
		Iterator<State> itrN = n.getPrevState().iterator();

		while (itrN.hasNext()){
			if (itrN.next().getCurrCity().equals(g.from) && itrN.next().getCurrCity().equals(g.to)){
				check = true;
			}
		}

		return check;
	}

	public int getTransferTime(Graph g, State s){
		int transferCost = 0;
		int i = 1;
		while (i < s.getPrevState().size()){
			transferCost += g.getNode(s.getPrevState().get(i).getCurrCity()).getTransferTime();
			i++;
		}
		return transferCost;
	}

	public void checkNeighbour(State curr, Graph g){
		State neighbours = null;
		Node currentCity = g.getNode(curr.getCurrCity());
		ArrayList<Edge> edges = currentCity.getEdges();

		int i = 0;
		while (i < edges.size()){
			neighbours = new State(edges.get(i).getTo(), edges.get(i).getWeight() + curr.getDistance());
			neighbours.addPrevState(curr);
			openSet.add(neighbours);
			i++;
		}
	}

	public void getPath(int nodesExpanded, int cost, State fullTrip){
		System.out.println(nodesExpanded + " nodes expanded");
		System.out.println("cost = " + cost);
		int i = 0;
		int j = 0;
		while (i < fullTrip.getPrevState().size()){
			j = i + 1;
			if (j >= fullTrip.getPrevState().size()){
				System.out.println("Trip " + fullTrip.getPrevState().get(i).getCurrCity() + " to " + fullTrip.getCurrCity());
			} else {
			System.out.println("Trip " + fullTrip.getPrevState().get(i).getCurrCity() + " to " + fullTrip.getPrevState().get(j).getCurrCity());
			}
		}
	}
}