package DataStructures;

import java.util.Enumeration;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;
import java.io.*;

/**
 * <p>A class implementing a weighted directed graph and shortest path
 * algorithms for a positively weighted graph. </p>
 *
 * <p>Graphs are created empty
 * <pre>
 *   WeightedGraph g = new WeightedGraph();
 * </pre>
 * after which weighted directed arcs can be added by
 * <pre>
 *   g.addArc(tail, head, weight) 
 * </pre>
 * where <tt>tail</tt> is the <tt>String</tt> label of the source node of the arc, 
 * <tt>head</tt> is the <tt>String</tt> label of the destination node of the arc 
 * and <tt>weight</tt> is an integer.</p>
 *
 * Weighted arcs can iterated over, for example by
 * <pre>
 *   for (WeightedGraph.Arc a : g) {
 *       System.out.println(a);
 *   }
 * </pre>
 * Nodes can be iterated over, for example by
 * <pre>
 *   for (Iterator<String> i = g.nodes(); i.hasNext();) {
 *       System.out.println(i.next());
 *   }
 * </pre>
 * 
 * <p> Graph descriptions can be read from and written to files.</p>
 *
 * @see DataStructures.WeightedGraph.Arc
 *
 * @author Peter Williams
 */

public class WeightedGraph implements Iterable<WeightedGraph.Arc> {

    protected LookupTable<String,Node> nodeMap; // for mapping node labels to nodes
    protected int version;      // changes whenever the graph changes
    private int nrArcs;         // the number of arcs in the graph

    /**
     * Constructs an empty weighted graph
     */
    public WeightedGraph() {
        nodeMap = new DoubleHashingTable<String,Node>();
        nrArcs = 0;
        version = 0;
    }                           

    /**
     * Tests whether a node is present in the graph.
     * @param label the label of the node to be searched for.
     * @return true if the node is present,
     * <tt>false</tt> otherwise
     */
    public boolean contains(String label) {
        return nodeMap.contains(label);
    }

    /**
     * Returns the number of nodes in the graph
     * @return the number of nodes
     */
    public int nrNodes() {
        return nodeMap.size();
    }

    /**
     * Returns the number of arcs in the graph
     * @return the number of arcs
     */
    public int nrArcs() {
        return nrArcs;
    }
    
    // the basic container for a node
    protected static class Node {
        String label;               // the label of this node
        LinkedList<Edge> adjacent; // list of arcs from here to adjacent nodes
        Object work;                // for workspace in applications
        Node(String label) {
            this.label = label;
            adjacent = new LinkedList<Edge>();
            work = null;
        }
    }

    // represents an arc out of a given unspecified node
    protected static class Edge {
        Node tail;           // the source node
        Node head;           // the destination node
        int weight;          // the weight on this arc
        Edge(Node tail, Node head, int weight) {
            this.tail = tail;
            this.head = head;
            this.weight = weight;
        }
    }

    /**
     * Adds a node into the graph.
     * @param label the label of the node
     */
    public void addNode(String label) {
        try {
            nodeMap.lookup(label);
        } catch (NoSuchElementException e) {
            nodeMap.add(label, new Node(label));
            ++version;
        }
    }

    // returns the node if it already exists, otherwise a new node with this label
    private Node getNode(String label) {
        Node node;
        try {
            node = nodeMap.lookup(label);
        } catch (NoSuchElementException e) {
            node = new Node(label);
            nodeMap.add(label, node);
            ++version;
        }
        return node;
    }

    /**
     * Adds a weighted directed arc into the graph.
     * @param tail the label of the source node
     * @param head the label of the destination node and
     * @param weight the weight attached to the arc.
     */
    public void addArc(String tail, String head, int weight) {
        Node t = getNode(tail);
        Node h = getNode(head);
        t.adjacent.addFirst(new Edge(t, h, weight));
        ++nrArcs;
        ++version;
    }

    // protected iterator over edges
    protected Iterator<Edge> edges() {
        return new Iterator<Edge> () {
            private Iterator<LookupTable.Entry<String,Node>> 
                nodes = nodeMap.iterator();
            private final int n = nrArcs; // a copy in case we remove some arcs
            private int count = 0;      // to test whether we have finished
            public boolean hasNext() {
                return count < n;
            }
            private Iterator<Edge> i = new EmptyIterator<Edge>();
            public Edge next() {
                if (count < n) {
                    // skip to the next node with outgoing arcs
                    while (!i.hasNext()) {
                        i  = nodes.next().value().adjacent.iterator();
                    }
                    ++count;
                    return i.next();
                } else {
                    throw new NoSuchElementException();
                }
            }
            public void remove() {
                i.remove();
                --nrArcs;
                ++version;
            }
        };
    }

    /**
     * Returns an iteration over the nodes in the graph.
     * @return an iteration over the nodes in the graph
     */
    public Iterator<String> nodes() {
        return new Iterator<String> () {
            private Iterator<LookupTable.Entry<String,Node>> 
                i = nodeMap.iterator();
            private Node current = null; // saved in case of removal
            public boolean hasNext() {
                return i.hasNext();
            }
            public String next() {
                current = i.next().value();
                return current.label;
            }
            public void remove() {
                // remove all incoming arcs
                Iterator<Edge> e = edges();
                while (e.hasNext()) {
                    if (e.next().head == current) {
                        e.remove();
                    }
                }
                // remove the node and all outgoing arcs
                nrArcs -= current.adjacent.size();
                i.remove();
                ++version;
            }
        };
    }

    /**
     * A public class returned by <tt>WeightedGraph.arcs()</tt>.
     * An arc is represented as a 
     * (<tt>tail</tt>, <tt>head</tt>, <tt>weight</tt>) triple,
     * where <tt>tail</tt> and <tt>head</tt> are string node labels and
     * <tt>weight</tt> is an integer.
     * @see WeightedGraph#arcs
     */
    public static class Arc {
        private String tail;
        private String head;
        private int weight;
    
        private Arc(String tail, String head, int weight) {
            this.tail = tail;
            this.head = head;
            this.weight = weight;
        }
    
        /**
         * Returns the tail or source of this arc.
         * @return the tail of the arc.
         */
        public String tail() {
            return tail;
        }
    
        /**
         * Returns the head or destination of this arc.
         * @return the head of the arc.
         */
        public String head() {
            return head;
        }
    
        /**
         * Returns the weight attached to this arc.
         * @return the weight of the arc.
         */
        public int weight() {
            return weight;
        }

        /**
         * Represents the arc as a string.
         * @return the string representation.
         */
        public String toString() {
            return tail + " " + head + " " + weight;
        }
    }

    /**
     * Returns an iteration over the arcs in the graph.  The <tt>next</tt> method
     * returns an element of the <tt>WeightedGraph.Arc</tt> class.
     * @see Arc
     * @return an iteration over the arcs in the graph
     */
    public Iterator<Arc> arcs() {
        return new Iterator<Arc> () {
            private Iterator<Edge> i = edges();
            public boolean hasNext() {
                return i.hasNext();
            }
            public Arc next() {
                Edge e = i.next();
                return new Arc(e.tail.label, e.head.label, e.weight);
            }
            public void remove() {
                i.remove();
            }
        };
    }

    /**
     * Returns the <tt>arcs</tt> iterator
     * @see WeightedGraph#arcs
     * @return the iterator.
     */
    public Iterator<Arc> iterator() {
        return arcs();
    }

    // workspace for each node for single-source shortest path algorithm
    private static 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
    }

    /**
     * Tests whether a path exists between two given nodes.
     * @param origin the node at which to begin,
     * @param destination 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(String origin, String destination) {
        Node source = nodeMap.lookup(origin);
        Node target = nodeMap.lookup(destination);
        dijkstra(source);
        return ((WorkSpace) target.work).settled;
    }

    /**
     * Returns the length of a shortest path between two given nodes.
     * @param origin the node at which to begin,
     * @param destination 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(String origin, String destination) {
        Node source = nodeMap.lookup(origin);
        Node target = 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 origin the node at which to begin,
     * @param destination 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(String origin, String destination) {
        final Node source = nodeMap.lookup(origin);
        final Node target = 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<Node> s = new StackArray<Node>();
                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 String nextElement() {
                    if (!s.isEmpty()) {
                        return s.pop().label;
                    } else {
                        throw new NoSuchElementException();
                    }
                }
            };
    }

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

    private Node lastSource = null; // source when dijkstra was last called
    private int lastVersion = 0; // version when dijkstra was last called

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

        // don't run if nothing has changed
        if (version == lastVersion && source == lastSource) {
            return;
        }

        // allocate new work space if necessary
        if (version != lastVersion) {
            for (LookupTable.Entry<String,Node> e : nodeMap) {
                Node v = e.value();
                if (v.work == null) {
                    v.work = new WorkSpace();
                }
            }
        }

        // solve the single-source all-paths problem

        // initialise
        for (LookupTable.Entry<String,Node> e : nodeMap) {
            Node v = e.value();
            ((WorkSpace) v.work).visited = false;
            ((WorkSpace) v.work).settled = false;
        }
        ((WorkSpace) source.work).visited = true;
        ((WorkSpace) source.work).distance = 0;

        // find the shortest paths
        PriorityQueue<HeapItem> q = new BinaryHeap<HeapItem>();
        q.add(new HeapItem(source, 0));
        while (!q.isEmpty()) {
            Node v = q.remove().node;
            WorkSpace vv = (WorkSpace) v.work;
            if (!vv.settled) {
                vv.settled = true;
                for (Edge e : v.adjacent) {
                    Node w = e.head;
                    int c = e.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));
                    }
                }
            }
        }
        lastVersion = version;
        lastSource = source;
    }

    /**
     * <p>Reads a graph description from a text file.
     * Entries read from the file are added to the graph.</p>
     * <p>File entries must be of form 
     * <pre>
     *        T H W
     * </pre>
     * where T and H are strings and W is an integer.  Each entry
     * represents a weighted arc where T is the tail or source node,
     * H is the head or destination node and W is the weight.</p>
     * <p>All entries must be on separate lines.  Empty lines are skipped.</p>
     */
    public void readGraphTxtFile(String fileName) {
        try {
            BufferedReader inStream =
                new BufferedReader(new FileReader(fileName));
            String line;
            while ((line = inStream.readLine()) != null) {
                if (line.length() > 0) {
                    StringTokenizer s = new StringTokenizer(line);
                    try {
                        if (s.countTokens() == 3) {
                            String tail = s.nextToken();
                            String head = s.nextToken();
                            int weight = Integer.parseInt(s.nextToken());
                            addArc(tail, head, weight);
                        } else {
                            throw new Exception();
                        }
                    } catch (Exception e) {
                        System.err.println("error in graph file entry: " + line);
                        System.exit(1);
                    }
                }
            }
            inStream.close();
        } catch (FileNotFoundException e) {
            System.err.println("cannot open " + fileName);
            System.exit(1);
        } catch (IOException e) {
            System.err.println("error: " + e);
            System.exit(1);
        }
    }

    /**
     * <p>Writes a graph description to a text file.</p>
     * <p>Files are written in the same form in which
     * <tt>readGraphTxtFile</tt> expects to read them.</p>
     * <p>Note: it is the applications's responsibility to protect files
     * which ought not to be overwritten.</p>
     */
    public void writeGraphTxtFile(String fileName) {
        try {
            BufferedWriter outStream =
                new BufferedWriter(new FileWriter(fileName));
            for (Arc a : this) {
                outStream.write(a.toString());
                outStream.newLine();
            }
            outStream.close();
        } catch (FileNotFoundException e) {
            System.err.println("cannot open " + fileName);
            System.exit(1);
        } catch (IOException e) {
            System.err.println("error: " + e);
        }
    }

}