import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.NoSuchElementException;
import java.util.Set;

public class UndirectedGraph<V> {
	private ArrayList<V> vertices;
	private HashMap<V,LinkedHashSet<V>> neighbors;
	private HashMap<V,Set<V>> neighborsView;
	private int edgeCount;

	/** Constructs an undirected graph, initially with no edges and no
	 * vertices. */
	public UndirectedGraph() {
		vertices = new ArrayList<V>();
		neighbors = new HashMap<V,LinkedHashSet<V>>();
		neighborsView = new HashMap<V,Set<V>>();
	}

	/** Adds the specified vertex, initially with no adjacent edges. */
	public void addVertex(V vid) {
		vertices.add(vid);
		LinkedHashSet<V> vneighb = new LinkedHashSet<V>();
		neighbors.put(vid, vneighb);
		neighborsView.put(vid, Collections.unmodifiableSet(vneighb));
	}

	/** Removes the specified vertex with all incident edges. */
	public void removeVertex(V vid) {
		if(vertices.remove(vid)) {
			LinkedHashSet<V> vneighb = neighbors.remove(vid);
			for(V uid : vneighb) {
				LinkedHashSet<V> uneighb = neighbors.get(uid);
				uneighb.remove(vid);
				--edgeCount;
			}
			neighborsView.remove(vid);
		} else {
			throw new NoSuchElementException("no such vertex");
		}
	}

	/** Adds an undirected edge between the two vertices. Throws
	 * NoSuchElementException if either vertex isn't part of graph. */
	public void addEdge(V uid, V vid) {
		LinkedHashSet<V> uneighb = neighbors.get(uid);
		LinkedHashSet<V> vneighb = neighbors.get(vid);
		if(uneighb == null) throw new NoSuchElementException("first argument not in graph");
		if(vneighb == null) throw new NoSuchElementException("second argument not in graph");
		if(uneighb.add(vid) && vneighb.add(uid)) {
			++edgeCount;
		}
	}

	/** Removes an undirected edge between the two vertices. Throws
	 * NoSuchElementException if either vertex isn't part of graph or
	 * there is no edge between them. */
	public void removeEdge(V uid, V vid) {
		LinkedHashSet<V> uneighb = neighbors.get(uid);
		LinkedHashSet<V> vneighb = neighbors.get(vid);
		if(uneighb == null) throw new NoSuchElementException("first argument not in graph");
		if(vneighb == null) throw new NoSuchElementException("second argument not in graph");
		if(uneighb.remove(vid) && vneighb.remove(uid)) {
			--edgeCount;
		} else {
			throw new NoSuchElementException("no edge between vertices");
		}
	}

	/** Returns the number of vertices in this graph. */
	public int getVertexCount() {
		return vertices.size();
	}

	/** Returns the number of edges in this graph. */
	public int getEdgeCount() {
		return edgeCount;
	}

	/** Returns the vertex at the specified index of this graph. */
	public V getVertex(int index) {
		return vertices.get(index);
	}

	/** Returns the number of vertices of the specified vertex. */
	public int getNeighborCount(V vid) {
		LinkedHashSet<V> vneighb = neighbors.get(vid);
		if(vneighb == null) throw new NoSuchElementException("no such vertex");
		return vneighb == null ? 0 : vneighb.size();
	}

	/** Returns the set of vertices that are adjacent to the
	 * specified vertex. */
	public Set<V> getNeighbors(V vid) {
		Set<V> vneighb = neighborsView.get(vid);
		if(vneighb == null) throw new NoSuchElementException("no such vertex");
		return vneighb;
	}

	/** Returns true if the two specified vertices have an edge
	 * between them. */
	public boolean isConnected(V uid, V vid) {
		LinkedHashSet<V> uneighb = neighbors.get(uid);
		if(uneighb == null) throw new NoSuchElementException("first argument not in graph");
		if(!neighbors.containsKey(vid)) throw new NoSuchElementException("second argument not in graph");
		return uneighb.contains(vid);
	}
}