// © Copyright 1997. Joseph Bergin. All rights reserved.

#ifndef Graph_H
#define Graph_h

#include <pair.h>
#include "ExpandableArray.h"

template <class T>
class GraphNode
{	public:	
		T value;
		GraphNode(const T& t = T()):value(t), _index(-1), _mark(false){}
		T operator*(){ return value; }
		
	private:
		int _index;
		bool _mark;
		
		void mark(){_mark = true;}
		void unmark(){_mark = false;}
		bool marked(){return _mark;}
		
		GraphNode(const T& t, int index):value(t), _index(index), _mark(false){}

	friend class DiGraph<T>;
	friend class pair<GraphNode<T>, ExpandableArray<DiGraph<T>::iterator> >; 
		// To initialize an array.
};

template <class T>
ostream& operator<<(ostream& os, const GraphNode<T>& gn)
{	os << gn.value;
	return os;
}

template <class T>
class GraphIterator // Forward Iterator. Could be RandomAccess. 
{	public:
		GraphNode<T>& operator*()
		{	return _here->first;
		}
		
		bool operator==(const GraphIterator<T>& gi)const
		{	return _here == gi._here;
		}
		
		GraphNode<T>& operator++()
		{	_here++;
			return _here->first;
		}
		
		GraphNode<T>& operator++(int)
		{	GraphNode<T>& result = _here->first;
			_here++;
			return result;
		}
	private:
		DiGraph<T>::storagePair* _here;
		
		GraphIterator(DiGraph<T>::storagePair* where = NULL)
		:	_here(where)
		{
		}
		
		DiGraph<T>::storagePair* operator()()
		{	return _here;
		}
		
	friend class DiGraph<T>;		
	friend class pair<GraphNode<T>, ExpandableArray<DiGraph<T>::iterator> >; 
		// To initialize an array.
	friend class ExpandableArray<GraphIterator<T> >;
};

template <class T>
class DiGraph
{	public:
		typedef GraphIterator<T> iterator;
		typedef  pair<GraphNode<T>, ExpandableArray<iterator> > storagePair;
		
		DiGraph():_vertices(){}
		
		GraphNode<T>& newGraphNode(const T& t)
		{	_vertices.push_back
				(	pair <GraphNode<T>, ExpandableArray<iterator> >
					(	GraphNode<T>(t, _vertices.size()), ExpandableArray<iterator>() 
					) 
				);
			return _vertices.back().first;
		}
		
		void arc(const GraphNode<T>& from, const GraphNode<T>& to)
		{	_vertices[from._index].second.push_back(GraphIterator<T>(&_vertices[to._index]));
		}

		iterator begin()const { return GraphIterator<T>(_vertices.begin());}
		iterator end ()const { return GraphIterator<T>(_vertices.end());}
		
		ExpandableArray< iterator > depthFirst(GraphNode<T>& gn)
		{	ExpandableArray<  iterator > result;
			unmark();
			_depthFirst(GraphIterator<T>(&_vertices[gn._index]), result);
			return result;
		}
		
	private:
		ExpandableArray< storagePair > _vertices;
		void unmark()
		{	for(iterator i = begin(); i != end(); ++i)
				(*i).unmark();
		}
		
		void _depthFirst(iterator gn, ExpandableArray< iterator >& A)
		{	if(! (*gn).marked())
			{	(*gn).mark();
				A.push_back(gn);
			//	for(int i = 0; i < gn()->second.size(); ++i)
			//		_depthFirst(gn()->second[i], A);
				for
				(	ExpandableArray<iterator>::iterator i = gn()->second.begin();
					i != gn()->second.end();
					++i
				)
					_depthFirst(*i,A);
			}
		}
		
};

// notes: could use an ExpandableArray<T>::iterator here, but then get a pointer to a
// pair and user doesn't know about pairs.  Here you get a pointer to a vertex, for all
// practical purposes.  
#endif