package graph;

import java.util.*;

public final class AdjListGraph extends AbstractGraph {

	private Map vertices;

	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);
	}

	public boolean addVertex(Object vertex) {
		if (vertex != null && !vertices.containsKey(vertex)) {
			// TODO Einfuegen des neuen Knotens in HashMap
			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.
			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.
			return true;
		}
		else {
			return false;
		}
	}

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

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

	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
		return set;
	}

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

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

	Vertex(Object vertex) {
		data = vertex;
	}

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