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;

    /**
     * Constructor
     * Sets up the OpenSet and CloseSet
     */
    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>();
    }

    /**
     * Perform the AStarSearch
     * @param goal
     * @param g
     */
    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 = closedSet.size();
            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;
            }
        }
        getPath(nodesExpanded, totalCost, closedSet.get(closedSet.size()-1));
    }

    /**
     * checks whether goal has been reached
     * @param g
     * @param n
     * @return
     */
    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;
    }

    /**
     * loops through the state
     * @param g
     * @param n
     * @return
     */
    private boolean stateLooper(GoalData g, State n){
        boolean check = false;
        int i = 0;
        int j = 1;
        if (n.getPrevState() == null){
            return check;
        }
        while (j < n.getPrevState().size()){
            if (n.getPrevState().get(i).equals(g.getFrom()) && n.getPrevState().get(j).equals(g.getTo())){
                check = true;
                break;
            }
            i++;
            j++;
        }
        if (check == false){
            if (n.getCurrCity().equals(g.getTo()) && n.getPrevState().get(n.getPrevState().size()-1).equals(g.getFrom())){
                check = true;
            }
        }
        return check;
    }

    /**
     * Gets Transfer Time and add it together
     * @param g
     * @param s
     * @return
     */
    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)).getTransferTime();
            i++;
        }
        return transferCost;
    }

    /**
     * Loops through the edges and create states and add it to the openSet
     * @param curr
     * @param g
     */
    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() + g.getNode(curr.getCurrCity()).getTransferTime());
            openSet.add(neighbours);
            neighbours.clone(curr.getPrevState());
            neighbours.getPrevState().add(curr.getCurrCity());
            i++;
        }
    }

    /**
     * Takes the last State and create a path out of it
     * @param nodesExpanded
     * @param cost
     * @param fullTrip
     */
    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 = 1;

        while (j < fullTrip.getPrevState().size()){
            System.out.println("Trip " + fullTrip.getPrevState().get(i) + " to " + fullTrip.getPrevState().get(j));
            i++;
            j++;
        }

        System.out.println("Trip " + fullTrip.getPrevState().get(fullTrip.getPrevState().size()-1) + " to " + fullTrip.getCurrCity());
    }
}