public class ListGraph implements UndirectedGraph
{    
    private int numVertices; // Number of vertices in the graph
    private int numEdges; // Number of edges in the graph
       
    // All vertices adjacent to v are stored in adjacentVertices[v].
    // No set is allocated if there are no adjacent vertices.
    private Set<Integer>[] adjacentVertices; // HashSet<Integer>[]
    
    // Edge costs are stored in a hash map. The key is an
    // Edge(v, w)-object and the cost is an Integer object.
    private Map<Edge, Integer> edgeCosts; // HashMap<Edge, Integer>
    
    /**
     * Constructs a graph with v vertices and v edges
     * 
     */
    public ListGraph(int v) {
        adjacentVertices = new HashSet[v];
        Random randomizer = new Random();
        numVertices = v;
        numEdges = v;
        //Creates a vector with hashset elements
        int i;
        for(i = 0; i<numVertices; i++) {
            adjacentVertices[i] = new HashSet<Integer>();
        }
        
        for(i = 0; i < numVertices; ) {
            int a = randomizer.nextInt(v);
            int b = randomizer.nextInt(v);
            if(!adjacentVertices[a].contains(b)) {
                adjacentVertices[a].add(b);
                adjacentVertices[b].add(a);
                i++;
            }
        }       
    }
        
    private static class Edge
    {
        private int v; // v <= w
        private int w;
        
        Edge(int v, int w) {
            if (v <= w) {
                this.v = v;
                this.w = w;
            } else {
                this.v = w;
                this.w = v;
            }
        }
        
        public boolean equals(Object o) {
            if (o == null)
                return false;
            Edge e = (Edge) o;
            return (v == e.v && w == e.w);
        }
        
        public int hashCode() {
            return v<<16 + w;
        }
    }

    /**
     * Returns the number of vertices in this graph.
     * Time complexity: O(1).
     * 
     * @return the number of vertices in this graph.
     */
    public int numVertices() {
        return numVertices;
    }
    
    /**
     * Returns the number of edges in this graph.
     * Time complexity: O(1).
     * 
     * @return the number of edges in this graph.
     */
    public int numEdges() {
        return numEdges;
    }

    /**
     * Returns the degree of vertex v.
     * Time complexity: O(1).
     * 
     * @param  v vertex.
     * @return the degree of vertex v.
     * @throws IllegalArgumentException if v is out of range.
     */
    public int degree(int v) throws IllegalArgumentException {
        if (v < 0 || v >= numVertices) {
            throw new IllegalArgumentException ("Out of range");
        }        
        int grad = adjacentVertices[v].size();        
        return grad;
    }
    
    /**
     * Returns an iterator of vertices adjacent to v.
     * Time complexity for iterating over all vertices: O(n),
     * where n is the number of adjacent vertices.
     * 
     * @param  v vertex.
     * @return an iterator of vertices adjacent to v.
     * @throws IllegalArgumentException if v is out of range.
     */
    public VertexIterator adjacentVertices(int v) {
        if(v < 0  || v >= numVertices) {
            throw new IllegalArgumentException("Out of range");
        }
        return new AdjacentVerticesIterator(v);    
    }
    
    /**
     * Testar iteratorn
     */
    public void test(int v) {
        VertexIterator test = adjacentVertices(v);
        System.out.println(test.next());
    }
        
    private class AdjacentVerticesIterator implements VertexIterator {
        int nextPos = 0;
        int vertex;
        
        AdjacentVerticesIterator(int v) {
            vertex = v;
            
         }
         
//         private void findNext() {
//             nextPos++;
//             while (nextPos < numVertices && adjacentVertices[vertex] == null)
//                 nextPos++;
//         }        
        
        public boolean hasNext() {
            return nextPos < adjacentVertices[vertex].size();
        }
        
        public int next() {
            int pos = nextPos;
            if (pos >= adjacentVertices[vertex].size()) {
                throw new NoSuchElementException("This iterator has no more elements.");
            }
            pos++;
            return pos; //return the element at this position. but how ?
        }
    }