/**
 * Graph represented an an adjacency list. 
 * 
 * @author ggtowell
 * Created: dec 4: 2021
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class AdjList<G> {
    /** 
     * Nodes in the array
     */
    private class Node<H> {
        // Node content
        public H payload;
        // hold the list
        public ArrayList<Edge<G>> edges;
        // the currently best known path to the node
        public ArrayList<Node<H>> path;
        // true if there is a path
        public boolean visited;
        // the cost to traverse the path
        double cost = 0;

        public void doVisit(Node<H> pp) {
            doVisit(pp, 1);
        }

        @SuppressWarnings("unchecked")
        /**
         * "Visit the node".  This sets the cost of visiting and 
         * the path of the visit.
         * @param pp the node that the visit originated at
         * @param cost the cost of the visit
         */
        public void doVisit(Node<H> pp, double cost) {
            visited = true;
            path = (ArrayList<Node<H>>) pp.path.clone(); // copy  the path fromt he source node
            path.add(pp); // add the source node to the path
            this.cost = cost;
        }

        public Node(H payl) {
            this.payload = payl;
            this.edges = new ArrayList<Edge<G>>();
        }

        public void addEdge(Node<G> n, double w) {
            edges.add(new Edge<G>(n, w));
        }

        public String toString() {
            StringBuffer sb = new StringBuffer();
            for (Edge<G> eg : edges) {
                sb.append(String.format("[%s->%s:%.3f]", payload, eg.too.payload, eg.weight));
            }
            return sb.toString();
        }
    }
    
    //Edges in the graph
    private class Edge<J> {
        Node<J> too;
        double weight;
        public Edge(Node<J> t2, double w) {
            this.too = t2;
            this.weight = w;
        }

    }
    // nodes are stored in a hashmap so they are quickly and easily found
    private HashMap<G, Node<G>> nodeHash;

    public AdjList() {
        nodeHash = new HashMap<G, Node<G>>();
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        for (Node<G> gn : nodeHash.values()) {
            sb.append(gn.toString());
        }
        return sb.toString();
    }

    public ArrayList<G> pathTo(G g) {
        Node<G> n = nodeHash.get(g);
        if (n == null)
            return null;
        ArrayList<Node<G>> pth = n.path;
        ArrayList<G>  rtn = new ArrayList<>();
        for (Node<G> p : pth) {
            rtn.add(p.payload);
        }
        rtn.add(g);
        return rtn;
    }
    public static void main(String[] args) {
        AdjList<String> adjl = new AdjList<>();
        adjl.addNode("A");
        adjl.addNode("B");
        adjl.addNode("C");
        adjl.addNode("D");
        adjl.addNode("E");
        adjl.addNode("F");
        adjl.addEdge("A", "B");
        adjl.addEdge("A", "F");
        adjl.addEdge("A", "D", 100);
        adjl.addEdge("B", "C");
        adjl.addEdge("C", "A");
        adjl.addEdge("C", "D");
        adjl.addEdge("C", "E");
        adjl.addEdge("E", "A");
        adjl.addEdge("E", "D");
        adjl.addEdge("F", "E");
        adjl.addEdge("F", "B");
        System.out.println(adjl);
        System.out.println(adjl.shortestUnweightedPath("A", "D"));
        adjl.shortestWeightedPathFrom("A");
        System.out.println(adjl.pathTo("D"));
    }
    
    /**
     *  Add a node to the Graph
    * Note that initially the node my be unconnected
    * @param g == the payload of the node
    **/
    public void addNode(G g) {
        nodeHash.put(g, new Node<G>(g));
    }

    /**
     * Add an edge with a weight of 1
     * @param fr the payload of the node from
     * @param t2 the payload of the node too
     */
    public void addEdge(G fr, G t2) {
        addEdge(fr, t2, 1.0);
    }
    
    /**
     * Add an edge with a weight
     * @param fr the payload of the node from
     * @param t2 the payload of the node too
     * @param w the weight of the edge
     */
    public void addEdge(G fr, G t2, double w) {
        Node<G> frn = nodeHash.get(fr);
        Node<G> t2n = nodeHash.get(t2);
        if (frn == null || t2n == null)
            return;
        frn.addEdge(t2n, w);
    }
    
    /**
     * Remove all path information from the graph. 
     */
    private void cleanPaths() {
        for (Node<G> gn : nodeHash.values()) {
            gn.visited = false;
            gn.path = new ArrayList<>();
            gn.cost = 100000d;
        }
    }

    /**
     * Determine if a path exists between two nodes
     * @param fr the starting node
     * @param t2 the ending node
     * @return
     */
    public boolean pathExists(G fr, G t2) {
        cleanPaths();
        Stack<Node<G>> q = new Stack<Node<G>>();
        Node<G> ng = nodeHash.get(fr);
        ng.visited = true;
        ng.path = new ArrayList<>();
        q.push(ng);
        while (!q.isEmpty()) {
            Node<G> curr = q.pop();
            for (Edge<G> linked : curr.edges) {
                Node<G> ln = linked.too;
                if (ln.payload.equals(t2))
                    return true;
                if (!ln.visited) {
                    ln.doVisit(curr);
                    q.push(ln);
                }
            }
        }
        return false;
    }

    /**
     * Find shorted path between node, irrespective of weights
     * @param fr the starting node
     * @param t2 the ending node
     * @return an array list containing the nodes in the path
     */
    public ArrayList<G> shortestUnweightedPath(G fr, G t2) {
        cleanPaths();
        Queue<Node<G>> q = new LinkedList<Node<G>>();
        {
            Node<G> ng = nodeHash.get(fr);
            ng.visited = true;
            ng.path = new ArrayList<>();
            q.offer(ng);
        }
        while (!q.isEmpty()) {
            Node<G> curr = q.poll();
            for (Edge<G> linked : curr.edges) {
                Node<G> ln = linked.too;
                if (ln.payload.equals(t2)) {
                    ArrayList<G> rtn = new ArrayList<>();
                    rtn.add(fr);
                    for (Node<G> ng : curr.path)
                        rtn.add(ng.payload);
                    rtn.add(t2);
                    return rtn;
                }
                if (!ln.visited) {
                    ln.doVisit(curr);
                    q.offer(ln);
                }
            }
        }
        return null;
    }

    /**
     * Find shorted wighted path between nodes
     * @param fr the starting node
     * @param t2 the ending node
     * @return an array list containing the nodes in the path
     */
    public void shortestWeightedPathFrom(G fr) {
        cleanPaths();
        PriorityQHeap<Double, Node<G>> pq = new PriorityQHeap<>();
        {
            Node<G> ng = nodeHash.get(fr);
            ng.visited = true;
            ng.path = new ArrayList<>();
            ng.cost = 0;
            pq.offer(0d, ng);
        }
        while (!pq.isEmpty()) {
            Node<G> curr = pq.poll();
            for (Edge<G> linked : curr.edges) {
                Node<G> ln = linked.too;
                if ((curr.cost+linked.weight) < ln.cost) {
                    ln.doVisit(curr, curr.cost+linked.weight);
                    pq.offer(ln.cost, ln);
                }
            }
        }
    }

}