import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;

/*
 classinvariants are valid for every method (except constructor) and therefor not mentioned again!
 classinvariant 1: Every nodename is unique.
 classinvariant 2: Every edgename is unique between two nodes and his direction.
 classinvariant 3: After instance is created, nodesList and edgelist are never null (but can be empty)
 classinvariant 4: Nodes with edges cannot be deleted.
 */
public class GenGraph<Knotenname, Kantenname> {

	private Collection<Knoten<Knotenname>> nodeslist;

	private Collection<Kante<Kantenname>> edgelist;

	/*
	 * postcondition: New graph is created. The nodeslist and edgelist are not
	 * null, but empty.
	 */
	public GenGraph() {
		this.nodeslist = new HashSet<Knoten<Knotenname>>();
		this.edgelist = new HashSet<Kante<Kantenname>>();
	}

	/*
	 * precondition: The parameter nodename is not null. postcondition: Return
	 * value is true, if the GenGraph contains the nodename, otherwise false.
	 */
	private boolean containsNode(Knotenname nodename) {
		try {
			getNode(nodename);
			return true;
		} catch (NodeNotFoundException nnf) {
			return false;
		}
	}

	/*
	 * 
	 * precondition: The parameter nodename is not null postcondition: The node
	 * for the given nodename is returned or a NodeNotFoundException is thrown.
	 */
	protected Knoten<Knotenname> getNode(Knotenname nodename)
			throws NodeNotFoundException {
		Iterator<Knoten<Knotenname>> nodeiter = this.nodeslist.iterator();
		while (nodeiter.hasNext()) {
			Knoten<Knotenname> node = nodeiter.next();
			if (node.getName().equals(nodename))
				return node;
		}
		throw new NodeNotFoundException();
	}

	/*
	 * precondition: The parameter start, end and caption are not null.
	 * postcondition: Return value is true, if the GenGraph contains the edge,
	 * otherwise false.
	 */
	private boolean containsEdge(Knotenname start, Knotenname end,
			Kantenname caption) throws NodeNotFoundException {
		try {
			if (getEdge(start, end, caption) != null)
				return true;
		} catch (NodeNotFoundException nnf) {
		}
		return false;
	}

	/*
	 * precondition: The parameters start, end and caption are not null.
	 * postcondition: The specified edge or null is returned or a
	 * NodeNotFoundException is thrown.
	 */
	private Kante<Kantenname> getEdge(Knotenname start, Knotenname end,
			Kantenname caption) throws NodeNotFoundException {
		Knoten<Knotenname> startnode = this.getNode(start);
		Knoten<Knotenname> endnode = this.getNode(end);
		Kante<Kantenname> edgetofind = new Kante<Kantenname>(caption,
				startnode, endnode);
		Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator();
		while (edgeiter.hasNext()) {
			Kante<Kantenname> edge = edgeiter.next();
			if (edge.equals(edgetofind))
				return edge;
		}
		return null;
	}

	/*
	 * precondition: The parameters start and end are not null. postcondition:
	 * The edge or null is returned or a NodeNotFoundException is thrown.
	 */
	private Collection<Kante<Kantenname>> getEdges(Knotenname start,
			Knotenname end) throws NodeNotFoundException {
		Collection<Kante<Kantenname>> result = new HashSet<Kante<Kantenname>>();
		Knoten<Knotenname> startnode = this.getNode(start);
		Knoten<Knotenname> endnode = this.getNode(end);

		Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator();
		while (edgeiter.hasNext()) {
			Kante<Kantenname> edge = edgeiter.next();
			if ((edge.getStart().equals(startnode))
					&& (edge.getEnd().equals(endnode)))
				result.add(edge);
		}
		return result;
	}

	/*
	 * postcondition: returns the Collection of edges for manipulation
	 */
	protected Collection<Kante<Kantenname>> getEdgeslist() {
		return this.edgelist;
	}

	/*
	 * precondition: The parameter a is not null. postcondition: Return value is
	 * a Collection with all outbound edges of a.
	 */
	protected Collection<Kante<Kantenname>> getOutboundEdges(Knoten<Knotenname> a) {
		Collection<Kante<Kantenname>> result = new HashSet<Kante<Kantenname>>();
		Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator();
		while (edgeiter.hasNext()) {
			Kante<Kantenname> edge = edgeiter.next();
			if (edge.getStart().equals(a))
				result.add(edge);
		}
		return result;
	}

	/*
	 * precondition: The parameter a is not null. postcondition: Return value is
	 * a Collection with all inbound edges of a.
	 */
	protected Collection<Kante<Kantenname>> getInboundEdges(Knoten<Knotenname> a) {
		Collection<Kante<Kantenname>> result = new HashSet<Kante<Kantenname>>();
		Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator();
		while (edgeiter.hasNext()) {
			Kante<Kantenname> edge = edgeiter.next();
			if (edge.getEnd().equals(a))
				result.add(edge);
		}
		return result;
	}

	/*
	 * precondition: The parameter a is not null. postcondition: Return value is
	 * true, if node a has successor nodes, otherwise false, or throws a
	 * NodeNotFoundException, if a is not contained in the nodeslist.
	 */
	protected boolean nodeHasSuccessors(Knoten<Knotenname> a)
			throws NodeNotFoundException {
		if (!this.containsNode(a.getName())) {
			throw new NodeNotFoundException();
		}

		Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator();
		while (edgeiter.hasNext()) {
			Kante edge = edgeiter.next();
			if (edge.getStart().equals(a))
				return true;
		}
		return false;
	}

	/*
	 * precondition: The parameter a is not null. postcondition: Return value is
	 * true, if node a has predecessor nodes, otherwise false, or throws a
	 * NodeNotFoundException, if a is not contained in the nodeslist.
	 */
	protected boolean nodeHasPredecessors(Knoten<Knotenname> a)
			throws NodeNotFoundException {
		if (!this.containsNode(a.getName())) {
			throw new NodeNotFoundException();
		}
		Iterator<Kante<Kantenname>> edgeiter = this.edgelist.iterator();
		while (edgeiter.hasNext()) {
			Kante edge = edgeiter.next();
			if (edge.getEnd().equals(a))
				return true;
		}
		return false;
	}

	/*
	 * precondition: The parameter nodename is not null and postcondition: The
	 * node is added to the nodeslist.
	 */
	public boolean addNode(Knotenname nodename) {
		if (containsNode(nodename)) {
			return false;
		}
		return this.nodeslist.add(new Knoten<Knotenname>(nodename));
	}

	/*
	 * precondition: The parameter nodename is not null and postcondition: The
	 * node is deleted from the nodeslist.
	 */
	public boolean deleteNode(Knotenname nodename) throws NodeNotFoundException {
		Knoten<Knotenname> node = getNode(nodename);
		if ((!nodeHasPredecessors(node)) && (!nodeHasSuccessors(node)))
			return this.nodeslist.remove(node);
		else
			return false;
	}

	/*
	 * precondition: The parameters are not null. postcondition: A new edge is
	 * addet to the edgelist.
	 */
	public boolean addEdge(Knotenname start, Knotenname end, Kantenname caption)
			throws NodeNotFoundException {
		if (containsEdge(start, end, caption)) {
			return false;
		}

		Knoten<Knotenname> startnode = this.getNode(start);
		Knoten<Knotenname> endnode = this.getNode(end);
		Kante<Kantenname> newEdge = new Kante<Kantenname>(caption, startnode,
				endnode);

		return this.edgelist.add(newEdge);
	}

	/*
	 * precondition: The parameters are not null. postcondition: The edge is
	 * deleted from the edgelist.
	 */
	public boolean deleteEdge(Knotenname start, Knotenname end,
			Kantenname caption) throws NodeNotFoundException {
		return this.edgelist.remove(this.getEdge(start, end, caption));
	}

	/*
	 * precondition: The parameter nodename is not null. postcondition: Return
	 * value is a Iterator with all successor nodes.
	 */
	public Iterator<Knotenname> getSuccessors(Knotenname nodename)
			throws NodeNotFoundException {
		Knoten<Knotenname> node = this.getNode(nodename);
		Collection<Kante<Kantenname>> outboundEdges = this
				.getOutboundEdges(node);
		Collection<Knotenname> successors = new HashSet<Knotenname>();
		Iterator<Kante<Kantenname>> edgeiter = outboundEdges.iterator();
		while (edgeiter.hasNext()) {
			successors.add(edgeiter.next().getEnd().getName());
		}
		return successors.iterator();
	}

	/*
	 * precondition: The parameter nodename is not null. postcondition: Return
	 * value is a Iterator with all predecessor nodes.
	 */
	public Iterator<Knotenname> getPredecessors(Knotenname nodename)
			throws NodeNotFoundException {
		Knoten<Knotenname> node = this.getNode(nodename);
		Collection<Kante<Kantenname>> inboundEdges = this.getInboundEdges(node);
		Collection<Knotenname> predecessors = new HashSet<Knotenname>();
		Iterator<Kante<Kantenname>> edgeiter = inboundEdges.iterator();
		while (edgeiter.hasNext()) {
			predecessors.add(edgeiter.next().getStart().getName());
		}
		return predecessors.iterator();
	}

	/*
	 * postcondition: Return value is a Iterator with all nodes of the GenGraph.
	 */

	public Iterator<Knotenname> getNodenames() {
		Collection<Knotenname> nodenames = new HashSet<Knotenname>();
		Iterator<Knoten<Knotenname>> nodeiter = this.nodeslist.iterator();
		while (nodeiter.hasNext()) {
			nodenames.add(nodeiter.next().getName());
		}
		return nodenames.iterator();
	}

	/*
	 * precondition: The parameter start and end are not null. postcondition:
	 * Return value is a Iterator with all edges, between start and end node.
	 */
	public Iterator<Kantenname> getEdgeNames(Knotenname start, Knotenname end)
			throws NodeNotFoundException {
		Collection<Kantenname> result = new HashSet<Kantenname>();
		Iterator<Kante<Kantenname>> edgeiter = this.getEdges(start, end)
				.iterator();
		while (edgeiter.hasNext()) {
			result.add(edgeiter.next().getName());
		}
		return result.iterator();
	}

	/*
	 * A nested class to represent nodes. A node is identified by its name.
	 * 
	 * classinvariant 1: Every node has a name, which is not null.
	 */
	@SuppressWarnings("hiding")
	protected class Knoten<Knotenname> {
		private Knotenname name;

		/*
		 * precondition: The parameter name is not null . postcondition: A new
		 * node is created.
		 */
		public Knoten(Knotenname name) {
			this.name = name;
		}

		/*
		 * postcondition: Returns a nodes nameobject.
		 */
		public Knotenname getName() {
			return this.name;
		}

		/*
		 * precondition: The parameter node a is not null. postcondition: Return
		 * value is true, if the node names are equal, otherwise false.
		 */
		public boolean equals(Knoten a) {
			return this.name.equals(((Knoten) a).getName());
		}

	}

	/*
	 * A nested class to represent edges between nodes. A edge is identified by
	 * its name, the start and the end node.
	 * 
	 * classinvariant 1: Every edge has a name, a start and a end node, which
	 * are not null.
	 */
	@SuppressWarnings("hiding")
	protected class Kante<Kantenname> {
		private Kantenname name;

		private Knoten<Knotenname> start;

		private Knoten<Knotenname> end;

		/*
		 * precondition: The paramters name, start and end are not null.
		 * postcondition: A new edge is created.
		 */
		protected Kante(Kantenname name, Knoten<Knotenname> start,
				Knoten<Knotenname> end) {
			this.name = name;
			this.start = start;
			this.end = end;
		}

		/*
		 * postcondition: Return value is the edge name.
		 */
		protected Kantenname getName() {
			return name;
		}

		/*
		 * postcondition: Return value is the start node of the edge.
		 */
		protected Knoten<Knotenname> getStart() {
			return start;
		}

		/*
		 * postcondition: Return value is the end node of the edge.
		 */
		protected Knoten<Knotenname> getEnd() {
			return end;
		}

		/*
		 * precondition: The paramter edge a is not null. postcondition: Return
		 * value is true, if the edge names, the start and end nodes are equal.
		 */
		protected boolean equals(Kante a) {
			if ((a.getName().equals(this.name))
					&& (a.getStart().equals(this.start))
					&& (a.getEnd().equals(this.end)))
				return true;
			else
				return false;
		}
	}

}