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

#ifndef __GRAPH_CPP
#define __GRAPH_CPP

#include "linked_list.cpp"
#include <iostream>
using namespace std;

template <typename T=int>
class Graph
{
private:
	LinkedList<LinkedList<T> > g;

	LinkedList<T>* findVertexList(T const& v) const
	{
		for(LinkedListIterator<LinkedList<T> > it = g.iteratorBegin();
				it; ++it)
		{
			LinkedListIterator<T> it2 = (*it).iteratorBegin();
			if (*it2 == v)
				return &*it;
		}
		return NULL;
	}

	bool findAndRemoveEdge(T const& u, T const& v, bool shouldRemove = true)
	{
		LinkedList<T>* l = findVertexList(u);
		if (l == NULL)
			return false;
		LinkedListIterator<T> it = l->iteratorBegin(), itp = it++;
		while (it && *it != v)
		{
			itp = it++;
		} // !it || *it == v
		// itp е една стъпка назад от it
		if (!it)
			return false;
		if (shouldRemove)
		{
			T w;
			l->deleteAfter(w, itp);
		}
		return true;
	}


public:
	void addVertex(T const& v)
	{
		LinkedList<T> l;
		l.toEnd(v);
		g.toEnd(l);
	}

	void removeVertex(T const& v)
	{
		for(LinkedListIterator<LinkedList<T> > it = g.iteratorBegin(); it; ++it)
		{
			LinkedListIterator<T> it2 = (*it).iteratorBegin();
			if (*it2 == v)
			{
				// това е списъкът на върха, който изтриваме
				LinkedList<T> l;
				LinkedListIterator<LinkedList<T> > tmp = it;
				++tmp;
				g.deleteAt(l, it);
				it = tmp;
				// отиваме на следващия връх
			}
			if (it)
			{
				it2 = (*it).iteratorBegin();
				// това е друг връх, трябва да изтрием всички входящи във v ребра
				LinkedListIterator<T> it2p = it2++;
				while(it2 && *it2 != v)
				{
					it2p = it2++;
				}
				if (it2)
				{
					T w;
					(*it).deleteAfter(w, it2p);
				}
			}
		}
	}

	bool hasVertex(T const& v) const
	{
		return findVertexList(v) != NULL;
	}
	LinkedList<T> vertices() const
	{
		LinkedList<T> vert;
		for(LinkedListIterator<LinkedList<T> > it = g.iteratorBegin(); it; ++it)
		{
			LinkedListIterator<T> it2 = (*it).iteratorBegin();
			vert.toEnd(*it2);
		}
		return vert;
	}

	bool addEdge(T const& u, T const& v)
	{
		LinkedList<T>* l = findVertexList(u);
		if (l == NULL)
			return false;
		l->toEnd(v); // TODO: check if v is already an edge
		return true;
	}

	bool removeEdge(T const& u, T const& v)
	{
		return findAndRemoveEdge(u,v);
	}

	bool hasEdge(T const& u, T const& v)
	{
		return findAndRemoveEdge(u,v,false);
	}

	LinkedListIterator<T> successors(T const& v) const
	{
		LinkedList<T>* l = findVertexList(v);
		if (l == NULL)
			return LinkedListIterator<T>();
		LinkedListIterator<T> it = l->iteratorBegin();
		++it;
		return it;
	}

	LinkedListIterator<LinkedList<T> > graph() const
	{
		return g.iteratorBegin();
	}

	void print() const { g.print(); }
};

#endif