package graph;

import java.util.*;

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

	private Map vertices;


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

	private AdjListGraph traverse(Vertex lastvertex, Vertex vertex, AdjListGraph newGraph)
	{
		Iterator it=vertex.adjList.iterator();
		System.out.println(vertex.data);
		newGraph.addVertex(vertex.data);
		newGraph.addEdge(lastvertex.data, vertex.data);
		vertex.visited=true;

		while(it.hasNext())
		{
			Vertex temp=(Vertex)it.next();
			if(!temp.visited)
			{
				newGraph=traverse(vertex, temp, newGraph);
			}
		}

		return newGraph;
	}






	/*
		AdjListGraph newGraph=new AdjListGraph(isDirected());
		Stack visited=new Stack();
		Stack itOfVisited=new Stack();
		Vertex thisVertex=(Vertex)vertices.get(startVertex);
		Iterator thisVertexIt=thisVertex.adjList.iterator();
		visited.push(thisVertex);
		itOfVisited.push(thisVertexIt);
		newGraph.addVertex(thisVertex.data);
		System.out.println(thisVertex.data);
		//System.out.println(thisVertex.data);
		//thisVertex.visited=true;
		//nofVertices--;
		Vertex tempVertex;

		while(!visited.isEmpty())
		{
			if(thisVertexIt.hasNext())
			{
				tempVertex=(Vertex)thisVertexIt.next();
				if(!tempVertex.visited)
				{
					thisVertex.visited=true;
					visited.push(thisVertex);
					itOfVisited.push(thisVertexIt);
					thisVertex=tempVertex;
					thisVertexIt=tempVertex.adjList.iterator();
					newGraph.addVertex(thisVertex.data);
					System.out.println(thisVertex.data);
					newGraph.addEdge(((Vertex)visited.peek()).data, thisVertex.data);
				}
			}
			else
			{
				thisVertex=(Vertex)visited.pop();
				thisVertexIt=(Iterator)itOfVisited.pop();
			}
		}
		System.out.println(thisVertex.data);
		newGraph.addVertex(thisVertex.data);
		return newGraph;
	}
*/
	public void sort()
	{
		if(!isDirected())
		{
			System.out.println("Graph ist nicht gerichtet!");
			return;
		}

		AdjListGraph tempGraph=new AdjListGraph(this);
		int nofVertices=tempGraph.getNofVertices();

		while(nofVertices>0)
		{
			boolean found=false;
			Vertex tempVertex;
			Collection tempCollection=tempGraph.vertices.values();
			Iterator tempIterator=tempCollection.iterator();
			while(tempIterator.hasNext()&&!found)
			{
				tempVertex=(Vertex)tempIterator.next();
				if(tempVertex.inGrade==0)
				{
					found=true;
					nofVertices--;
					tempVertex.inGrade--;
					Iterator adjListIterator=tempVertex.adjList.iterator();
					while(adjListIterator.hasNext())
					{
						((Vertex)adjListIterator.next()).inGrade--;
					}
					System.out.println(tempVertex.data);
				}
			}
			if(!found&&nofVertices>0)
			{
				System.out.println("Loop gefunden");
				return;
			}
		}
	}


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

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

	public AdjListGraph(AdjListGraph orig) { // copy constructor
		// TODO Loeschen Sie folgende Zeile und programmieren Sie
		// einen Konstruktor, der eine Kopie von orig erstellt.
		//this(false);
		super(orig.isDirected());
		this.vertices = new HashMap(orig.vertices);
	}

	public boolean addVertex(Object vertex) {
		if (vertex != null && !vertices.containsKey(vertex)) {
			// TODO Einfuegen des neuen Knotens in HashMap
			vertices.put(vertex, new Vertex(vertex));
			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) {
			// TODO Kante einfuegen, es muss dabei unterschieden werden, ob der
			// Graph gerichtet ist oder nicht.

			if(!vf.adjList.contains(vt))
			{
				vf.adjList.add(vt);

				if(this.isDirected())
				{
					vt.inGrade++;
				}
				else
				{
					vt.adjList.add(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)) {
			// TODO Kante loeschen, es muss dabei unterschieden werden, ob der
			// Graph gerichtet ist oder nicht.

			vf.adjList.remove(vt);

			if(!this.isDirected())
			vt.adjList.remove(vf);
			else
			vt.inGrade--;

			return true;
		}
		else {
			return false;
		}
	}

	public int getNofVertices() {
		// TODO Ersetzen Sie die folgende Zeile durch eine effizientere Implementation
		//return super.getNofVertices();
		return vertices.size();
	}

	public int getNofEdges() {
		// TODO Ersetzen Sie die folgende Zeile durch eine effizientere Implementation
		//return super.getNofEdges();
		Set set=vertices.entrySet();
		Iterator it=set.iterator();
		int counter=0;
		while(it.hasNext())
		{
			counter+= ((Vertex)it.next()).adjList.size();

		}
		return counter;
	}

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

	public Set getAdjacentVertices(Object vertex) {
		Set set = new TreeSet();
		// TODO Alle data-Objekte, die in den benachbarten
		// Knoten gespeichert sind, in set einfügen

		Vertex v;

		if(vertex!=null)
		{
			v=(Vertex)vertices.get(vertex);

			if(!v.adjList.isEmpty())
			{
				ListIterator it=v.adjList.listIterator(0);

				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 inGrade;
	boolean visited=false;

	Vertex(Object vertex) {
		data = vertex;
	}

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