/*
 * visitor.cpp
 *
 *  Created on: 19.12.2012
 *      Author: trifon
 */

#include "graph.cpp"
#include "lstack.cpp"

template <typename T=int>
class Visitor
{
public:
	virtual void enterVertex(T const&) {}
	virtual void exitVertex(T const&) {}
	virtual void enterEdge(T const&, T const&) {}
	virtual void exitEdge(T const&, T const&) {}
};

template <typename T=int>
class PrintVisitor : public Visitor<T>
{
public:
	void enterVertex(T const& v) {
		cout << "Влизаме във " << v << endl;
	}

	void exitVertex(T const& v) {
		cout << "Излизаме от " << v << endl;
	}

	void enterEdge(T const& u, T const& v) {
		cout << "Минаваме по (" << u << ',' << v << ")\n";
	}

	void exitEdge(T const& u, T const& v) {
		cout << "Връщаме се по (" << u << ',' << v << ")\n";
	}
};

template <typename T>
void DFSrec(Graph<T> const& g, T const& a,
		     Visitor<T>& visitor, LinkedList<T>& visited)
{
	visitor.enterVertex(a);
	visited.toEnd(a);
	for(LinkedListIterator<T> it = g.successors(a); it; ++it)
	{
		visitor.enterEdge(a, *it);
		if (!member(*it, visited))
			DFSrec(g, *it, visitor, visited);
		visitor.exitEdge(a, *it);
	}
	visitor.exitVertex(a);
}

template <typename T>
void DFS(Graph<T> const& g, T const& a, Visitor<T>& visitor)
{
	LinkedList<T> visited;
	DFSrec(g, a, visitor, visited);
}

template <typename T>
void BFS(Graph<T> const& g, T const& a, Visitor<T>& visitor)
{
	LinkedList<T> visited;
	visited.toEnd(a);
	LinkedListIterator<T> it = visited.iteratorBegin();
	while (it)
	{
		visitor.enterVertex(*it);
		for(LinkedListIterator<T> sit = g.successors(*it); sit; ++sit)
		{
			visitor.enterEdge(*it, *sit);
			if (!member(*sit, visited))
				visited.toEnd(*sit);
		}
		++it;
	}
}

template <typename T=int>
class FindPathVisitor : public Visitor<T>
{
private:
	LStack<T> path;
	T target;
	bool found;
public:

	FindPathVisitor(T const& b) :
			target(b), found(false) {}

	void enterVertex(T const& v)
	{
		if (!found)
		{
			path.push(v);
			if (v == target)
				found = true;
		}
	}

	void exitVertex(T const& v)
	{
		if (!found)
		{
			T tmp;
			path.pop(tmp);
		}
	}

	void printPath()
	{
		if (!found)
			cout << "Не е намерен път!";
		else
		{
			cout << "Намерен е път:" << endl;
			path.print();
		}
	}
};

template <typename T=int>
class FindPathVisitor2 : public Visitor<T>
{
private:
	T target;
	bool found;
public:
	FindPathVisitor2(T const& b) :
				target(b), found(false) {}

	void enterVertex(T const& v)
	{
		// TODO: как да избегнем върховете, в
		// които влизаме СЛЕД като сме намерили път?
		if (v == target)
			found = true;
	}

	void exitVertex(T const& v)
	{
		if (found)
			cout << v << endl;
	}
};

template <typename T=int>
class FindShortestPathVisitor : public Visitor<T>
{
	struct Edge {
		T start, end;
	};
	LStack<Edge> visitedEdges;
	LinkedList<T> visitedVertices;
	T target;
public:
	FindShortestPathVisitor(T const& b) :
		target(b) {}

	void enterEdge(T const& u, T const& v)
	{
		Edge e = { u, v };
		if (!member(v, visitedVertices))
			// запазваме само реброто при първото срещане на върха
		{
			visitedVertices.toEnd(v);
			visitedEdges.push(e);
		}
	}

	void enterVertex(T const& v)
	{
		// отбелязваме върха за обходен
		if (v == target)
		{
			// намерихме най-краткия (първия) път!
			Edge e;
			while (!visitedEdges.empty())
			{
				while (visitedEdges.pop(e) && e.end != target);
				if (e.end == target){
			       		cout << target << endl;
					target = e.start;
				}
			}
			cout << target << endl;
		}
	}
};

template <typename T=int>
class SpanningTreeVisitor : public Visitor<T>
{
private:
	Graph<T> stree;

public:

	void enterVertex(T const& u)
	{
		if (!stree.hasVertex(u))
			stree.addVertex(u);
	}

	void enterEdge(T const& u, T const& v)
	{
		if (!stree.hasVertex(v))
		{
			stree.addVertex(v);
			stree.addEdge(u, v);
		}
	}

	void printTree() {
		stree.print();
	}
};