package fha.inf3.graph;

import java.util.*;

public final class AdjListGraph extends AbstractGraph implements GraphAlgorithms.TopSort, GraphAlgorithms.DFS {

	private Map vertices;
	private int numberOfVertices;
	private int numberOfEdges;

	public AdjListGraph() { // default constructor
		this(false);
	}

	public AdjListGraph(boolean directed) {
		super(directed);
		vertices = new HashMap();
	}

	public AdjListGraph(AdjListGraph orig) { // copy constructor
		this(orig.isDirected());
		Iterator it = orig.getVertices().iterator();
		while(it.hasNext()) {
			addVertex(it.next());
		}
		it = orig.getVertices().iterator();
		while(it.hasNext()) {
			Vertex tmp = ((Vertex)orig.vertices.get(it.next())); 
			Iterator it2 = tmp.adjList.iterator();
			while(it2.hasNext()) {
				addEdge(tmp.data, ((Vertex)it2.next()).data);
			}
		}
	}

	public Graph traverse(Object startVertex) {
		AdjListGraph g = new AdjListGraph(isDirected());
		g.addVertex(startVertex);
		traverse(g, (Vertex)vertices.get(startVertex));
		return g;
	}

	private void traverse(AdjListGraph g, Vertex v) {
		Iterator it = v.adjList.iterator();
		while(it.hasNext()) {
			Vertex w = (Vertex)it.next();
			if(!g.vertices.containsKey(w.data)) {
				g.addVertex(w.data);
				g.addEdge(v.data, w.data);
				traverse(g,w);
			}
		}
	}

	public void sort() {
		AdjListGraph alg = new AdjListGraph(this);
		int counter = 0;

		if(alg.isDirected()) {
			Stack s = new Stack();
			Vertex v, w;

			Iterator it = alg.getVertices().iterator();
			while(it.hasNext()) {
				v = ((Vertex)alg.vertices.get(it.next()));
				if(v.indegree == 0) {
					s.push(v);
				}
			}
			while(!s.empty()) {
				v = (Vertex)s.pop();
				System.out.println(v);
				counter++;
				it = v.adjList.iterator();
				while(it.hasNext()) {
					w = (Vertex)it.next();
					if(--w.indegree == 0) {
						s.push(w);
					}
				}
			}
		}
		else {
			System.out.println("Der Graph ist nicht gerichtet");
			if (!alg.isDirected()) {
				System.out.println("Der Graph ist nicht gerichtet");
			}
			else if(counter != alg.getNofVertices()) {
				System.out.println("Der Graph beinhaltet einen Zyklus");
			}
		}
	}

	public boolean addVertex(Object vertex) {
		if (vertex != null && !vertices.containsKey(vertex)) {
			vertices.put(vertex, new Vertex(vertex));
			numberOfVertices++;
			return true;
		}
		else {
			return false;
		}
	}

	public boolean addEdge(Object from, Object to) {
		Vertex vf = (Vertex)vertices.get(from);
		Vertex vt = (Vertex)vertices.get(to);
		if (vf != null && vt != null) {
			vf.addEdgeTo(vt);
			numberOfEdges++;
			vt.indegree++;
			if(!isDirected()) {
				vf.indegree++;
				vt.addEdgeTo(vf);
			}
			return true;
		}
		else {
			return false;
		}
	}

	public boolean removeEdge(Object from, Object to) {
		Vertex vf = (Vertex)vertices.get(from);
		Vertex vt = (Vertex)vertices.get(to);
		if (vf != null && vt != null && vf.adjList.contains(vt)) {
			vf.adjList.remove(vt);
			numberOfEdges--;
			vt.indegree--;
			if(!isDirected()) {
				vf.indegree--;
				vt.adjList.remove(vf);
			}
			return true;
		}
		else {
			return false;
		}
	}

	public int getNofVertices() {
		return numberOfVertices;
	}

	public int getNofEdges() {
		return numberOfEdges;
	}

	public Set getVertices() {
		return vertices.keySet();
	}

	public Set getAdjacentVertices(Object vertex) {
		Set set = new TreeSet();
		Iterator it = ((Vertex)vertices.get(vertex)).adjList.iterator();
		while(it.hasNext()) {
			set.add(((Vertex)it.next()).data);
		}
		return set;
	}

	public Object clone() {
		return new AdjListGraph(this);
	}
}

class Vertex {
	Object data;
	List adjList = new LinkedList();
	int indegree;

	Vertex(Object vertex) {
		data = vertex;
	}

	boolean addEdgeTo(Vertex to) {
		return (adjList.contains(to)) ? false : adjList.add(to);
	}

	public String toString() {
		return data.toString();
	}
}