/*
 * graph.cpp
 *
 *  Created on: 09.01.2014
 *      Author: trifon
 */

#include "linked_list.cpp"

template <typename V>
class Graph {
private:
	LinkedList<LinkedList<V> > graph;
	typedef LinkedListIterator<LinkedList<V> > I;

	// O(n)
	LinkedList<V>& findVertexList(V const& v) const {
		I it = graph.begin();
		while(it && *(*it).begin() != v)
			++it;
		// не би трябвало да се случва върха да го няма!
		return *it;
	}

public:
	typedef LinkedListIterator<V> VI;

	// O(n)
	LinkedList<V> vertices() const {
		LinkedList<V> result;
		for(I it = graph.begin(); it; ++it)
			result.toEnd(*(*it).begin());
		return result;
	}

	// O(1)
	void addVertex(V const& v) {
		// няма да правим проверка за коректност
		// т.е. разчитаме, че няма да добавяме повтарящи се върхове и ребра
		LinkedList<V> vlist;
		vlist.toEnd(v);
		graph.toEnd(vlist);
	}

	// O(n)
	void addEdge(V const& u, V const& v) {
		findVertexList(u).toEnd(v);
	}

	// O(n)
	VI successors(V const& v) const {
		return (VI&)++(findVertexList(v).begin());
	}

	// O(n+m)
	void removeEdge(V const& u, V const& v) {
		LinkedList<V>& us = findVertexList(u);
		VI vit = us.begin();
		while (vit && *vit != v)
			++vit;
		V tmp;
		us.deleteAt(tmp, vit);
	}

	// O(n + m)
	void removeVertex(V const& v) {
		LinkedList<V> tmp;
		V tmp2;
		for(I it = graph.begin(); it; ) {
			LinkedList<V>& vlist = *it;
			VI vit = vlist.begin();
			if (*vit == v) {
				I pit = it;
				++pit;
				graph.deleteAt(tmp, it);
				it = pit;
			}
			else {
				while (vit && *vit != v)
					++vit;
				if (vit)
					// има ребро, влизащо във v
					vlist.deleteAt(tmp2, vit);
				++it;
			}
		}

	}

	template <typename T>
	friend ostream& operator<<(ostream& os, Graph<T> const& g) {
		return os << g.graph;
	}

};