import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * The Component class keeps track of a connected component of a random graph.
 * It keeps a list of all of the vertices and edges in the component.
 */
public class Component implements Comparable {
	private static int NumComponents = 0;
	private List<Vertex> vertexList;
	private List<Edge> edgeList;
	private int edges;

	// Create an empty component.
	public Component() {
		vertexList = new LinkedList<Vertex>();
		edgeList = new LinkedList<Edge>();
	}
	
	// Create a new component consisting of just Vertex v.
	public Component(Vertex v) {
		vertexList = new LinkedList<Vertex>();
		vertexList.add(v);
		edgeList = new LinkedList<Edge>();
		NumComponents++;
	}

	// Return the number of vertices in this component.
	public int getNumVerts() {
		return vertexList.size();
	}

	// Merges another component into this one, unless the other has more vertices.
	public void mergeComponents(Component other) {
		if (other.getNumVerts() > this.vertexList.size()) {
			other.mergeComponents(this);
		} else {
			vertexList.addAll(other.vertexList);
			edgeList.addAll(other.edgeList);
			for (Vertex v : other.vertexList) {
				v.changeComponent(this);
			}
			NumComponents--;
		}

	}

	// Add a vertex to this component.
	public void addVertex(Vertex v) {
		vertexList.add(v);
	}

	// Add an edge to this component.
	public void addEdge(Edge e) {
		edgeList.add(e);
	}

	/**
	 *  Returns the excess of this component, which is defined to be the
	 *  difference between the number of edges and the number of vertices.
	 *  The smallest possible value is -1 (for a tree).
	 */
	public int excess() {
		return edges - vertexList.size();
	}

	// This keeps track of the total number of components in existence during this run.
	public static int getNumComponents() {
		return NumComponents;
	}

	// Counts the number of edges in this component.
	public void countEdges() {
		int sum = 0;
		for (Vertex v : vertexList) {
			sum += v.getLocalVertices().size();
		}
		edges = sum / 2;
	}

	// When printed, this displays the number of vertices and the excess as a pair.
	@Override
	public String toString() {
		return "(" + vertexList.size() + ", " + excess() + ")";
	}

	// Returns the distance between two randomly chosen vertices.
	public int randomDistance() {
		int size = vertexList.size();
		if (size == 1) {
			return 0;
		}
		Random r = new Random();
		int index1 = r.nextInt(size);
		int index2 = r.nextInt(size);
		while (index1 == index2) {
			index2 = r.nextInt(size);
		}
		return distance(vertexList.get(index1), vertexList.get(index2));
	}

	/**
	 *  Finds the distance between two vertices, defined as the minimum number of edges
	 *  in a path between vertices v1 and v2.
	 */
	public int distance(Vertex v1, Vertex v2) {
		return singleSourceSP(v1).get(v2.getId());
	}

	/**
	 *  For a vertex s, this finds the distance from s to any vertex v and places it
	 *  in a hash map.  This uses the standard algorithm for single source shortest path.
	 */
	private HashMap<Integer, Integer> singleSourceSP(Vertex s) {
		HashMap<Integer, Integer> distances = new HashMap<Integer, Integer>();
		HashMap<Integer, Boolean> discovered = new HashMap<Integer, Boolean>();
		int INF = vertexList.size();
		for (Vertex v : vertexList) {
			distances.put(v.getId(), INF);
			discovered.put(v.getId(), false);
		}
		distances.put(s.getId(), 0);
		discovered.put(s.getId(), true);

		ArrayDeque<Vertex> queue = new ArrayDeque<Vertex>();
		queue.offer(s);
		Vertex c = null;
		int d = 0;
		while ((c = queue.poll()) != null) {
			d = distances.get(c.getId());
			for (Vertex v : c.getLocalVertices()) {
				if (!discovered.get(v.getId())) {
					distances.put(v.getId(), d + 1);
					discovered.put(v.getId(), true);
					queue.offer(v);
				}
			}
		}
		return distances;
	}

	// Returns the average distance between vertices in this component.
	public double averageDistance() {
		HashMap<Integer, HashMap<Integer, Integer>> distances = allSourcesShortestPath();
		int totalDistance = 0;
		for (Vertex v : vertexList) {
			for (Vertex w : vertexList) {
				totalDistance += distances.get(v.getId()).get(w.getId());
			}
		}
		int n = vertexList.size();
		return ((double) totalDistance) / (n * n);
	}

	/**
	 * Finds the shortest distance between all pairs of vertices and places it in a hash map
	 * indexed by the pairs of vertices.
	 */
	public HashMap<Integer, HashMap<Integer, Integer>> allSourcesShortestPath() {
		HashMap<Integer, HashMap<Integer, Integer>> distances = new HashMap<Integer, HashMap<Integer, Integer>>();
		int INF = vertexList.size();
		for (Vertex v : vertexList) {
			HashMap<Integer, Integer> vDistances = new HashMap<Integer, Integer>();
			for (Vertex w : vertexList) {
				if (v.getId() == w.getId()) {
					vDistances.put(w.getId(), 0);
				} else {
					vDistances.put(w.getId(), INF);
				}
			}
			distances.put(v.getId(), vDistances);
		}
		distances.put(-1, new HashMap<Integer, Integer>());
		distances.get(-1).put(0, -1);
		int i = 0;
		while (i < INF && distances.get(-1).get(0) != 0) {
			distances = extendPaths(distances);
			i++;
		}
		return distances;
	}

	public HashMap<Integer, HashMap<Integer, Integer>> extendPaths(
			HashMap<Integer, HashMap<Integer, Integer>> distances) {
		HashMap<Integer, HashMap<Integer, Integer>> newDistances = new HashMap<Integer, HashMap<Integer, Integer>>();
		newDistances.put(-1, new HashMap<Integer, Integer>());
		newDistances.get(-1).put(0, -1);
		int INF = vertexList.size();
		int d = 0;
		boolean allFinite = true;
		for (Vertex v : vertexList) {
			int vId = v.getId();
			HashMap<Integer, Integer> newVDistances = new HashMap<Integer, Integer>();
			for (Vertex w : vertexList) {
				int wId = w.getId();
				boolean wFinite = false;

				int currDistance = distances.get(vId).get(wId);
				if (currDistance == INF) {
					for (Vertex k : w.getLocalVertices()) {
						if ((currDistance - 1) > (d = distances.get(v.getId())
								.get(k.getId()))) {
							currDistance = d + 1;
							wFinite = true;
						}
					}
				} else {
					wFinite = true;
				}
				newVDistances.put(wId, currDistance);
				allFinite = allFinite && wFinite;
			}
			newDistances.put(vId, newVDistances);
		}
		if (allFinite) {
			newDistances.get(-1).put(0, 0);
		}
		return newDistances;
	}

	// For sorting component lists, this component is greater than another if it
	// has more vertices.
	@Override
	public int compareTo(Object o) {
		Component other = (Component) o;

		return this.getNumVerts() - other.getNumVerts();
	}
}
