import java.util.*;

/**
 * Graph class with adjacent lists
 * @author Peter Barth
 */
public class Graph {

	private class Edge {
		int dest, value;
		Edge(int d, int v) {
			dest = d;
			value = v;
		}
	}
	
	private TreeMap<String, Integer> labels;  // mapping from Node description to node number (0 to n-1) 
	private TreeMap<Integer, String> rlabels; // and back 
	private ArrayList<LinkedList<Edge>> nodes; // nodes from 0 to n-1
	private int nextfree; // next free entry (no reuse when deleted)
	
	/**
	 * new empty graph
	 */
	public Graph() {
		labels = new TreeMap<String, Integer>();
		rlabels = new TreeMap<Integer, String>();
		nodes = new ArrayList<LinkedList<Edge>>();
		nextfree = 0;
	}

	/**
	 * @param label node description
	 * @return true gdw node is contained in graph
	 */
	public boolean containsNode(String label) {
		return labels.containsKey(label);
	}
	
	/**
	 * Adds a new node to the available nodes. 
	 * If node alreay exists throw Exception.
	 * @param label unique node description
	 */
	public void addNode(String label) {
		if (containsNode(label))
			throw new GraphException("Graph::addNode: " + label + " already present.");
		labels.put(label, nextfree);
		rlabels.put(nextfree, label);
		nodes.add(nextfree, new LinkedList<Edge>());
		nextfree += 1;
	}
	
	/**
	 * Deletes a node from the available nodes. Also deletes all
	 * Edges, where node is either start or end node. 
	 * @param label unique node description
	 */
	public void removeNode(String label) {
		if (!labels.containsKey(label))
			throw new GraphException("Graph::removeNode: " + label + " not present.");
		int node = labels.get(label);
		labels.remove(label);
		rlabels.remove(node);
		nodes.set(node, null);
		for (Iterator<String> it = labels.keySet().iterator(); it.hasNext(); ) {
			String l = it.next();
			LinkedList<Edge> el = nodes.get(labels.get(l));
			for (Iterator<Edge> eit = el.iterator(); eit.hasNext(); ) {
				Edge e = eit.next();
				if (e.dest == node) {
					eit.remove();
				}
			}
		}
	}
	
	/**
	 * @param from node description
	 * @param to node description
	 * @return true iff Edge alreay present
	 */
	public boolean containsEdge(String from, String to) {
		if (!containsNode(from) || !containsNode(to))
			return false;
		LinkedList<Edge> l = nodes.get(labels.get(from));			
		int t = labels.get(to);
		for (Iterator<Edge> eit = l.iterator(); eit.hasNext(); ) {
			Edge e = eit.next();
			if (e.dest == t)
				return true;
		}
		return false;
	}

	/**
	 * @param from node description from node
	 * @param to node description to node
	 * @return value of edge iff present, throws GraphException otherwise
	 */
	public int getEdgeValue(String from, String to) {
		// similar implementation as containsEdge for speed
		if (!containsNode(from) || !containsNode(to)) {
			throw new GraphException("Graph::getEdgeValue: " + from + " -> " + to + " not present");
		}
		LinkedList<Edge> l = nodes.get(labels.get(from));			
		int t = labels.get(to);
		for (Iterator<Edge> eit = l.iterator(); eit.hasNext(); ) {
			Edge e = eit.next();
			if (e.dest == t)
				return e.value;
		}
		throw new GraphException("Graph::getEdgeValue: " + from + " -> " + to + " not present");
	}
	
	/**
	 * @param from node description
	 * @param to node description
	 */
	public void addEdge(String from, String to) {
		addEdge(from, to, 1);
	}
	
	/**
	 * @param from node description
	 * @param to node description
	 * @param value value of edge
	 */
	public void addEdge(String from, String to, int value) {
		if (containsEdge(from, to)) {
			throw new GraphException("Graph::addEdge: " + from + " -> " + to + " already present");
		}
		if (!containsNode(from))
			throw new GraphException("Graph::addEdge: " + from + " -> " + to + ", node " + from + " missing");
		if (!containsNode(to))
			throw new GraphException("Graph::addEdge: " + from + " -> " + to + ", node " + to + " missing");
		LinkedList<Edge> l = nodes.get(labels.get(from));
		int t = labels.get(to);
		for (Iterator<Edge> eit = l.iterator(); eit.hasNext(); ) {
			Edge e = eit.next();
			if (e.dest == t) { // already there, update
				throw new GraphException("Graph::addEdge: " + from + " -> " + to + "already present");
			}
		}
		l.add(new Edge(t, value));
	}
	
	/**
	 * adds both from -> to and to -> from
	 * @param from node description
	 * @param to node description
	 */
	public void addDoubleEdge(String from, String to) {
		addEdge(from, to, 1);
		addEdge(to, from, 1);
	}

	/**
	 * adds both from -> to and to -> from
	 * @param from node description
	 * @param to node description
	 * @param value 
	 */
	public void addDoubleEdge(String from, String to, int value) {
		if (containsEdge(from, to) || containsEdge(to, from)) {
			throw new GraphException("Graph::addDoubleEdge: " + from + "-" + to + " already present");
		}
		addEdge(from, to, value);
		addEdge(to, from, value);
	}
	
	/**
	 * @param from node description
	 * @param to node description
	 */
	public void removeEdge(String from, String to) {
		if (!containsNode(from) || !containsNode(to))
			throw new GraphException("Graph::removeEdge: " + from + " -> " + to + " not present");
		LinkedList<Edge> l = nodes.get(labels.get(from));
		int t = labels.get(to);
		for (Iterator<Edge> eit = l.iterator(); eit.hasNext(); ) {
			Edge e = eit.next();
			if (e.dest == t) {
				eit.remove();
				return; // can only be there once
			}
		}
		throw new GraphException("Graph::removeEdge: " + from + " -> " + to + " not present");
	}
	
	/**
	 * @return Iterator to iterate through the nodes
	 */
	public Iterator<String> nodeIterator() {
		return labels.keySet().iterator();
	}
	
	
	private class EdgeIterator implements Iterator<String> {
		Iterator<Edge> it;
		EdgeIterator(String from) {
			it = nodes.get(labels.get(from)).iterator();
		}
		public boolean hasNext() { return it.hasNext(); }
		public String next() { return rlabels.get(it.next().dest); }
		public void remove() { throw new UnsupportedOperationException(); }
	}
	
	/**
	 * @param from node description 
	 * @return Iterator to iterate through the nodes going out from from
	 */
	public Iterator<String> edgeIterator(String from) {
		if (!containsNode(from))
			throw new GraphException("Graph::edgeIterator: " + from + " not present");
		return new EdgeIterator(from); 
	}
	
	/**
	 * show the adjacent list of the graph
	 */
	public void show() {
		System.out.println(">>> Graph");
		for (Iterator<String> sit = labels.keySet().iterator(); sit.hasNext(); ) {
			String label = sit.next();
			System.out.print(label + " :");
			LinkedList<Edge> l = nodes.get(labels.get(label));
			for (Iterator<Edge> eit = l.iterator(); eit.hasNext(); ) {
				Edge e = eit.next();
				System.out.print("  " + rlabels.get(e.dest) + "," + e.value);
			}
			System.out.println();
		}
		System.out.println("<<<");
	}
	
}