import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;

/**
 * An implementation of the Weighted Graph ADT.  This class can
 * represent both directed and undirected graphs, but the choice must be made
 * at construction time, and is final.
 *   Another choice that must be made at construction time is that of the
 * "sentinel" value for weights.  This is the value that getWeight() returns for
 * edges that are not in the graph.  The default is Double.POSITIVE_INFINITY,
 * but other common choices are negative infinity, zero, or NaN.
 *   Technically, this implementation supports self-loops; it makes no effort to
 * prevent these.
 *   Any method that takes one or more vertex IDs as arguments may throw an
 * IndexOutOfBoundsException if any input ID is out of bounds.
 * 
 * @author Jadrian Miles
 * @author Anna Rafferty
 * @author Jed Yang
 */
public class CarlWeightedGraph implements WeightedGraph {
    private static class Edge {
        public int end;
        public double weight;
        public Edge(int e, double w) { end = e; weight = w; }
    }
    private List<List<Edge>> adj;
    private final boolean undirected;
    private final double sentinel;
    
    /** Default constructor: an empty directed graph.
     * Creates an empty directed graph, with a sentinel value of
     * Double.POSITIVE_INFINITY.
     */
    public CarlWeightedGraph() {
        this(true, 0, Double.POSITIVE_INFINITY);
    }
    
    /**
     * Constructs an empty graph with the specified directedness, with a
     * sentinel value of Double.POSITIVE_INFINITY.
     */
    public CarlWeightedGraph(boolean directed) {
        this(directed, 0, Double.POSITIVE_INFINITY);
    }
    
    /**
     * Constructs a graph with N vertices and the specified directedness, with a
     * sentinel value of Double.POSITIVE_INFINITY.
     */
    public CarlWeightedGraph(boolean directed, int N) {
        this(directed, N, Double.POSITIVE_INFINITY);
    }
    
    /**
     * Constructs a graph with N vertices and the specified directedness and
     * sentinel value.
     */
    public CarlWeightedGraph(boolean directed,
                                              int N,
                                              double sentinel) {
        adj = new ArrayList<List<Edge>>();
        undirected = !directed;
        this.sentinel = sentinel;
        for(int i = 0; i < N; i++) {
            adj.add(new ArrayList<Edge>());
        }
    }
    
    /** Adds a new vertex.
     * @return the ID of the added vertex.
     */
    public int addVertex() {
        adj.add(new ArrayList<Edge>());
        return adj.size() - 1;
    }
    
    // The return value, which we'll call i, indicates the presence or absence
    // of an edge in the list "edges" whose endpoint is "goal".
    //   If i >= 0, edges.get(i) is the desired edge.
    //   If i < 0, j = (-i - 1) is the index in edges at which the edge
    //     should be inserted in order to keep the edge list sorted.
    private static int findEdge(List<Edge> edges, int goal) {
        // Search using iterative binary search, essentially copied from the JDK
        // java.util.Arrays (specifically: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html )
        int l = 0;
        int r = edges.size() - 1;
        while(l <= r) {
            int m = l + (r-l)/2;
            int v = edges.get(m).end;
            if(v < goal) {
                l = m + 1;
            } else if(v > goal) {
                r = m - 1;
            } else {
                return m;
            }
        }
        return -(l + 1);
    }
    
    /** Adds a weighted edge between two vertices.
     * In an undirected graph, this has the same effect as
     * addEdge(end, begin, weight).
     * @return false if the edge was already in the graph.
     */
    public boolean addEdge(int begin, int end, double weight) {
        List<Edge> edges = adj.get(begin);
        if(edges == null || end < 0 || end >= adj.size()) {
            throw new IndexOutOfBoundsException();
        }
        int i = findEdge(edges, end);
        if(i >= 0) {
            // This edge is already in the graph.
            return false;
        }
        edges.add(-i-1, new Edge(end, weight));
        if(undirected && (begin != end)) {
            // We have to add the edge in the other direction too.
            //   The (begin == end) case is a self-loop; we there's no "other
            // direction in this case.
            //   Since (begin != end) and we assured above the (begin, end) was
            // not already in the graph, we know that (end, begin) is also not
            // already in the graph.  So we know i will be negative; we don't
            // have to check.
            i = findEdge(adj.get(end), begin);
            adj.get(end).add(-i-1, new Edge(begin, weight));
        }
        return true;
    }
    
    /** Checks whether an edge exists between two vertices.
     * In an undirected graph, this returns the same as hasEdge(end, begin).
     * @return true if there is an edge from begin to end.
     */
    public boolean hasEdge(int begin, int end) {
        List<Edge> edges = adj.get(begin);
        if(edges == null || end < 0 || end >= adj.size()) {
            throw new IndexOutOfBoundsException();
        }
        return (findEdge(edges, end) >= 0);
    }
    
    /** Sets the weight of an edge already in the graph.
     * @return false if the edge is not in the graph.
     */
    public boolean setWeight(int begin, int end, double weight) {
        List<Edge> edges = adj.get(begin);
        if(edges == null || end < 0 || end >= adj.size()) {
            throw new IndexOutOfBoundsException();
        }
        int i = findEdge(edges, end);
        if(i < 0) {
            // This edge is not in the graph.
            return false;
        }
        edges.get(i).weight = weight;
        if(undirected && (begin != end)) {
            // We have to change the record of this edge with the endpoints
            // flipped.
            i = findEdge(adj.get(end), begin);
            adj.get(end).get(i).weight = weight;
        }
        return true;
    }
    
    /** Gets the weight of the edge between two vertices.
     * In an undirected graph, this returns the same as getWeight(end, begin).
     * @return the weight of the edge from begin to end, or the sentinel value
     *   if no such edge exists.
     */
    public double getWeight(int begin, int end) {
        List<Edge> edges = adj.get(begin);
        if(edges == null || end < 0 || end >= adj.size()) {
            throw new IndexOutOfBoundsException();
        }
        int i = findEdge(edges, end);
        if(i < 0) {
            // This edge is not in the graph.
            return sentinel;
        }
        return edges.get(i).weight;
    }
    
    /** Returns the out-degree of the specified vertex. */
    public int getDegree(int v) {
        List<Edge> edges = adj.get(v);
        if(edges == null) {
            throw new IndexOutOfBoundsException();
        }
        return edges.size();
    }
    
    /** Returns the in-degree of the specified vertex. */
    public int getInDegree(int v) {
        if(v < 0 || v >= adj.size()) {
            throw new IndexOutOfBoundsException();
        }
        // To count the in-degree, we have to look for edges to v from *all*
        // vertices.  (Including v!  Self-loops are allowed.)
        int d = 0;
        for(List<Edge> edges : adj) {
            for(Edge e : edges) {
                if(e.end == v) {
                    d++;
                }
            }
        }
        return d;
    }
    
    // Wrapper class around List<Edge>, to provide a read-only iterator.
    private class NeighborCollection implements Iterable<Integer> {
        private List<Edge> neighbors;
        public NeighborCollection(List<Edge> edges) {
            neighbors = edges;
        }
        public Iterator<Integer> iterator() {
            return new NeighborIterator(neighbors);
        }
        
        // Read only iterator.
        private class NeighborIterator implements Iterator<Integer> {
            private Iterator<Edge> it;
            public NeighborIterator(List<Edge> edges) {
                it = edges.iterator();
            }
            public boolean hasNext() {
                return it.hasNext();
            }
            public Integer next() {
                return it.next().end;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        }
    }
    
    /** Returns an iterator over the neighbors of the specified vertex.
     * In particular, the vertex u is included in the returned iterator's
     * sequence if and only if there is an edge from v to u in the graph.
     */
    public Iterable<Integer> getNeighbors(int v) {
        List<Edge> neighbors = adj.get(v);
        if(neighbors == null) {
            throw new IndexOutOfBoundsException();
        }
        return new NeighborCollection(neighbors);
    }
    
    /** Returns the number of vertices in the graph. */
    public int numVerts() {
        return adj.size();
    }
    
    /** Returns the number of edges in the graph.
     * The result does *not* double-count edges in undirected graphs.
     */
    public int numEdges() {
        int m = 0;
        for(List<Edge> edges : adj) {
            m += edges.size();
        }
        if(undirected) {
            return m/2;
        }
        return m;
    }
    
    /** Returns true if the graph is directed. */
    public boolean isDirected() {
        return !undirected;
    }
    
    /** Returns true if there are no vertices in the graph. */
    public boolean isEmpty() {
        return adj.isEmpty();
    }
    
    /** Removes all vertices and edges from the graph. */
    public void clear() {
        adj.clear();
    }
    
    /** Returns the "sentinel" weight value for edges not in the graph. */
    public double missingEdgeSentinel() {
        return sentinel;
    }
}