package DataStructures;

import java.util.Enumeration;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * <p>A class implementing shortest path algorithms for positively
 * weighted directed graphs. </p>
 *
 * @author Peter Williams */

public class PositiveWeightedGraph extends WeightedGraph {

    private Node source;        // source when Dijkstra was last called
    private int version;        // for detecting changes to parent graph

    /**
     * Constructs an empty positive weighted graph
     */
    public PositiveWeightedGraph() {
        source = null;
        version = super.version - 1;
    }

    /**
     * Tests whether a path exists between two given nodes.
     * @param <code>origin</code> the node at which to begin,
     * @param <code>destination</code> the node at which to end.
     * @return <code>true</code> if a path exists, <code>false</code> otherwise.
     * @exception NoSuchElementException if either node does not exist.
     * @exception ArithmeticException if a negatively weighted arc is
     *            encountered in the search.
     */
    public boolean pathExists(Object origin, Object destination) {
        Node source = (Node) nodeMap.lookup(origin);
        Node target = (Node) nodeMap.lookup(destination);
        dijkstra(source);
        return ((WorkSpace) target.work).settled;
    }

    /**
     * Returns the length of a shortest path between two given nodes.
     * @param <code>origin</code> the node at which to begin,
     * @param <code>destination</code> the node at which to end.
     * @return the shortest path length.
     * @exception NoSuchElementException if either node does not exist,
     *            or if there is no path between them.
     * @exception ArithmeticException if a negatively weighted arc is
     *            encountered in the search.
     */
    public int shortestPathLength(Object origin, Object destination) {
        Node source = (Node) nodeMap.lookup(origin);
        Node target = (Node) nodeMap.lookup(destination);
        dijkstra(source);
        if (((WorkSpace) target.work).settled) {
            return ((WorkSpace) target.work).distance;
        } else {
            throw new NoSuchElementException();
        }
    }

    /**
     * Enumerates the nodes in a shortest path between two given nodes.
     * @param <code>origin</code> the node at which to begin,
     * @param <code>destination</code> the node at which to end.
     * @return the enumeration.
     * @exception NoSuchElementException if either node does not exist,
     *            or if there is no path between them.
     * @exception ArithmeticException if a negatively weighted arc is
     *            encountered in the search.
     */
    public Enumeration shortestPath(Object origin, Object destination) {
        final Node source = (Node) nodeMap.lookup(origin);
        final Node target = (Node) nodeMap.lookup(destination);
        dijkstra(source);
        if (!((WorkSpace) target.work).settled) {
            throw new NoSuchElementException();
        }
        return new Enumeration() {
            // use a stack to reverse the order
            private Stack s = new StackArray();
            private Node current = target;
            { // load the stack
                while (current != source) {
                    s.push(current);
                    current = ((WorkSpace) current.work).previous;
                }
                s.push(source);
            }
            public boolean hasMoreElements() {
                return !s.isEmpty();
            }
            public Object nextElement() {
                if (!s.isEmpty()) {
                    return ((Node) s.pop()).label;
                } else {
                    throw new NoSuchElementException();
                }
            }
        };
    }

    // workspace for each node for single-source shortest path algorithm
    private class WorkSpace {
        boolean settled;  // whether the shortest route to this node is known
        boolean visited;  // true if a settled node or adjacent to a settled node
        int distance;     // shortest known distance to this node from source
        Node previous;    // previous node on shortest path
    }

    // items for the binary heap used in Dijkstra's algorithm
    private class HeapItem implements Comparable {
        Node node;
        int distance;
        HeapItem(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
        // highest priority given to lowest weight
        public int compareTo(Object other) {
            return ((HeapItem) other).distance - distance;
        }
    }

    // the basic algorithm
    private void dijkstra(Node origin) {

        // don't run if nothing has changed
        if (version == super.version && origin == source) {
            return;
        }

        // allocate new work space if necessary
        if (version != super.version) {
            Iterator i = nodeMap.iterator();
            while (i.hasNext()) {
                Node n = (Node) ((LookupTable.Entry) i.next()).value();
                if (n.work == null) {
                    n.work = new WorkSpace();
                }
            }
        }

        // solve the single-source all-paths problem

        // initialise
        Iterator i = nodeMap.iterator();
        while (i.hasNext()) {
            Node n = (Node) ((LookupTable.Entry) i.next()).value();
            ((WorkSpace) n.work).visited = false;
            ((WorkSpace) n.work).settled = false;
        }
        ((WorkSpace) origin.work).visited = true;
        ((WorkSpace) origin.work).distance = 0;

        // find the shortest paths
        PriorityQueue q = new BinaryHeap();
        q.add(new HeapItem(origin, 0));
        while (!q.isEmpty()) {
            Node v = ((HeapItem) q.remove()).node;
            WorkSpace vv = (WorkSpace) v.work;
            if (!vv.settled) {
                vv.settled = true;
                Iterator tips = v.adjacent.iterator();
                while (tips.hasNext()) {
                    Tip t = (Tip) tips.next();
                    Node w = t.head;
                    int c = t.weight;
                    if (c < 0) {
                        throw new ArithmeticException("Negative weight in graph");
                    }
                    int d = vv.distance + c;
                    WorkSpace ww = (WorkSpace) w.work;
                    if (!ww.visited || ww.distance > d) {
                        ww.visited = true;
                        ww.distance = d;
                        ww.previous = v;
                        q.add(new HeapItem(w, d));
                    }
                }
            }
        }
        version = super.version;
        source = origin;
    }

}