/*Graph class to construct a graph of edges and nodes
 * VERY useful for graph theory courses :)
 * Chris LaPointe
 * April 2008
 * Licence: GPLv3

graph.h is a member of the project GraphClass.

GraphClass is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

GraphClass is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GraphClass. If not, see <http://www.gnu.org/licenses/>.

 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <iostream>
#include <vector>
#include <queue>

namespace GraphTheory{
	template <typename T, typename S> class Graph;



	//The actual graph=========================================
	template <typename T=int, typename S=int > class Graph{
	public:
		//============================================
		//NODES AND EDGES=============================
		//============================================
		//Nodes or pointers in a given graph
		class Node;
		class Edge;
		class NodeIterator;
		class EdgeIterator;

		class Node{
		public:
			Node(): e_first(NULL), e_last(NULL), size_edges(0), next(NULL), prev(NULL){}
			Node(const T &ident_){
				e_first = e_last = NULL;
				next = prev = NULL;
				size_edges = 0;
				ident = ident_;
			}

			~Node(){
				Edge *temp;
				Edge *edge = e_first;

				while(edge){
					temp = edge->next;
					delete edge;
					edge = temp;
				}

				e_first = e_last = NULL;
				size_edges = 0;
			}

			const T &getIdent()const{
				return ident;
			}

			//Add an edge pointing to something, at the end
			Edge *AddEdge(Node *to){
				if (EdgeExists(to))	//Check if it exists
					return NULL;
				Edge *nedge = new Edge(this,to);	//Create new edge

				nedge->prev = e_last;				//set the prev to point here
				if (e_last) e_last->next = nedge;	//and the e_last to point to new one
				e_last = nedge;						//Set e_last to new last
				if (!e_first) e_first = nedge;		//If this is the only one, set it to first, too

				size_edges++;						//iterate
				return nedge;
			}
			Edge *AddEdge(Node *to, const S &value){
				Edge *nedge = AddEdge(to);			//Make edge
				nedge->evalue = value;				//Set initial value
				return nedge;
			}


			//Deletes an edge out of existance (MUST BELONG TO US!)
			bool DelEdge(Edge *e){
				if (!e) return false;

				//Set new pointers
				if (e->prev)
					e->prev->next = e->next;
				if (e->next)
					e->next->prev = e->prev;

				//Change e_first or e_last if needed
				if (e == e_first) e_first = e->next;
				if (e == e_last) e_last = e->prev;

				delete e;

				//decrement
				size_edges--;
				return true;
			}

			//Delete an edge based on a pointer to another node
			bool DelEdge(Node *to){
				return DelEdge(FindEdge(to));
			}


			//Check if an edge exists that points to another node
			Edge *FindEdge(Node *to)const{
				for (Edge *i = e_first; i != NULL; i=i->next){
					if (i->dst == to)
						return i;
				}
				return NULL;
			}

			bool EdgeExists(Node *to)const{
				return FindEdge(to) ? true : false;
			}

			//Iterators----
			EdgeIterator begin_edge()const{
				return EdgeIterator(e_first);
			}
			EdgeIterator end_edge()const{
				return EdgeIterator();
			}

			//Number of edges
			int EdgeCount()const{
				return size_edges;
			}

			//Public variables
			T ident;		//Identification name or number, or whatever

			//Friendships :)
			friend class Graph;
			friend class EdgeIterator;
			friend class NodeIterator;
		private:
			Edge *e_first;				//Head of edge list
			Edge *e_last;				//Last edge contained
			int size_edges;				//Number of edges contained
			Node *next;					//Next in the list of nodes
			Node *prev;					//The previous node
		};


		//Edges various nodes can point to
		class Edge{
		public:
			Edge(): dst(NULL), owner(NULL), next(NULL), prev(NULL){}
			Edge(Node *own_, Node *pt_): owner(own_), dst(pt_), next(NULL), prev(NULL){}

			Node *owner;		//The owner node of this edge
			Node *dst;			//Destination node

			S evalue;			//Edge identification value

			friend class Node;
			friend class EdgeIterator;
			friend class NodeIterator;
		private:
			Edge *next;		//Next edge in sequence
			Edge *prev;		//The previous edge
		};

		//=======================================
		//Iterators==============================
		//=======================================

		//The fancy iterators!!
		//The below iterator is more of a wrapper to navigate accross edges
		//Has capabilities to navigate across edges in only a single node, or across all nodes
		class EdgeIterator{
		public:
			//Constructors
			EdgeIterator(): e(0), n(0){}
			EdgeIterator(Edge *start){
				e = start;
				n = NULL;
			}
			EdgeIterator(Node *start){
				if (start){
					n = start;
					e = n->e_first;
					while(!e){
						n = n->next;
						if (n) e = n->e_first;
						else break;
					}
				}else{
					e = NULL;
					n = NULL;
				}
			}


			EdgeIterator &operator++(){
				this->next();
				return *this;
			}
			EdgeIterator &operator++(int){
				this->next();
				return *this;
			}


			void next(){
				if (e){				//if have e
					e = e->next;	//iterator e
					if (!e && n){	//if e=NULL, but node exists
						while(!e){
							n = n-> next;
							if (n) e = n->e_first;
							else break;
						}
					}
				}//e
			}

			//Accessors
			Edge &operator*(){
				return *e;
			}
			const Edge &operator*()const{
				return *e;
			}

			Edge *operator->()const{
				return e;
			}

			Edge *ptr()const{
				return e;
			}

			//comparisons
			//NOTE: Because this is an edge iterator, only edges need to be compared
			bool operator==(const EdgeIterator &a)const{
				return a.e == e;
			}
			bool operator!=(const EdgeIterator &a)const{
				return a.e != e;
			}

		private:
			Edge *e;
			Node *n;
		};

		class NodeIterator{
		public:
			NodeIterator(): n(0){}
			NodeIterator(Node *start): n(start){}

			//Iterations
			NodeIterator &operator++(){
				if (n) n = n->next;
				return *this;
			}
			NodeIterator &operator++(int){
				if (n) n = n->next;
				return *this;
			}

			//Accessors
			Node &operator*(){
				return *n;
			}
			const Node &operator*()const{
				return *n;
			}

			Node *operator->()const{
				return n;
			}

			Node *ptr(){
				return n;
			}

			//Comparisons
			bool operator==(const NodeIterator &a)const{
				return a.n == n;
			}
			bool operator!=(const NodeIterator &a)const{
				return a.n != n;
			}


		private:
			Node *n;
		};




		//============================================
		//The graph class=============================
		//============================================
		Graph(){
			size_nodes = 0;
			n_first = n_last = NULL;
		}
		Graph(const Graph &a): n_first(NULL), n_last(NULL), size_nodes(0){
			Copy(a);
		}
		~Graph(){
			Destroy();
		}

		//Memory==============================
		//Copy a graph
		void Copy(const Graph &from){
		    Destroy();    //clear us

		    //start copying
            for (NodeIterator i = from.begin(); i != from.end(); ++i)
                AddNode(i->ident);

            for (EdgeIterator i = from.begin_edge(); i != from.end_edge(); ++i)
                AddEdge(i->owner->ident, i->dst->ident, i->evalue);
		}

		void Destroy(){
			Node *node = n_first;
			Node *temp;

			while(node){
				temp = node->next;
				delete node;
				node = temp;
			}
			n_first = n_last = NULL;
			size_nodes = 0;
		}

		void Clear(){
			Destroy();
		}

		//Operators============================

		//overloaded operators
		Graph &operator=(const Graph &a){
			Copy(a);
			return *this;
		}

		Node &operator[](const T &i){
			return *FindNode(i);
		}


		//Counters================================================

		//The size of the graph is the number of nodes
		int size()const{
			return size_nodes;
		}
		int NodeCount()const{
			return size_nodes;
		}
		int EdgeCount()const{
			int sum = 0;
			for (Node *i = n_first; i != NULL; i=i->next)
				sum += i->size_edges;
			return sum;
		}


		//Adding=====================================================

		//Add node to graph checking for duplicate nodes
		Node *AddNode(const T &id){
			if (NodeExists(id)) return NULL;
			Node *nnode = new Node(id);

			nnode->prev = n_last;
			if (n_last) n_last->next = nnode;
			n_last = nnode;
			if (!n_first) n_first = nnode;

			size_nodes++;
			return nnode;
		}

		//Add an edge connecting two nodes
		Edge *AddEdge(Node *from, Node *to){
			return from->AddEdge(to);
		}

		Edge *AddEdge(const T &from, const T &to){
			Node *n_from = FindNode(from);
			Node *n_to = FindNode(to);
			if (!n_from || !n_to)
				return NULL;
			return n_from->AddEdge(n_to);
		}

		Edge *AddEdge(Node *from, Node *to, const S &value){
			Edge *nedge = AddEdge(from,to);
			if (nedge) nedge->evalue = value;
			return nedge;
		}

		Edge *AddEdge(const T &from, const T &to, const S &value){
			Edge *nedge = AddEdge(from,to);
			if (nedge) nedge->evalue = value;
			return nedge;
		}

		//Removal==========================================
		bool RemoveNode(Node *node){
			if (!node) return false;

			//Destroy all edges pointing to it..
			for (Node *i = n_first; i != NULL; i = i->next)
				i->DelEdge(node);

			//Delete me
			if (node->prev) node->prev->next = node->next;
			if (node->next) node->next->prev = node->prev;
			if (node == n_first) n_first = node->next;
			if (node == n_last) n_last = node->prev;

			//Remove
			delete node;
			size_nodes--;

			return true;
		}

		bool RemoveNode(const T &id){
			return RemoveNode(FindNode(id));
		}

		//Finding==========================================

		//Looking for an edge
		Edge *FindEdge(Node *from, Node *to)const{
			if (!from || !to) return NULL;
			for (Node *i = n_first; i != NULL; i=i->next){
				Edge *e = i->FindEdge(to);
				if (e) return e;
			}
			return NULL;
		}

		Edge *FindEdge(const T &from, const T &to)const{
			return FindEdge(FindNode(from), FindNode(to));
		}


		//Look for a node based on the ident
		Node *FindNode(const T &id)const{
			for (Node *i = n_first; i != NULL; i=i->next){
				if ( i->getIdent() == id)
					return i;
			}
			return NULL;
		}

		//Check if a node exists
		bool NodeExists(const T &id)const{
			return FindNode(id) ? true : false;
		}


		//Accessor operators=======================================


		//Used with node iterators
		NodeIterator begin()const{
			return NodeIterator(n_first);
		}
		NodeIterator end()const{
			return NodeIterator();
		}

		EdgeIterator begin_edge()const{
			return EdgeIterator(n_first);
		}
		EdgeIterator end_edge()const{
			return EdgeIterator();
		}


	private:
		Node *n_first;	//Nodes contained in this graph
		Node *n_last;	//Last node contained in graph
		int size_nodes;	//Number of containg nodes
	};



	//=================================================================
	//GRAPH DATA STRUCTURES
	//=================================================================
	//NOTE:
	//Edge data structures need streaming operator <<
	//Node operators need streaming operator<< as well as operator==

	//T can be anything (with comparison and streaming ops), S must be some numerical value to compare distances
	template <typename T, typename S> class WeightedNode{
	public:
		WeightedNode(){}
		WeightedNode(const T n): name(n){}
		WeightedNode(const T n, const S d): name(n), dist(d){}

		bool operator==(const WeightedNode &a)const{return a.name == name;}

		T name;
		S dist;
	};
	template <typename T, typename S> std::ostream &operator<<(std::ostream &os, const WeightedNode<T,S> &ewd){
		os << "{" << ewd.name << ", dist: " << ewd.dist << "}";
		return os;
	}

	//=================================================================
	//=========ALGORITHMS==============================================
	//=================================================================
	template <typename T> class PQ_CompareVertex{
	public:
		bool operator()(const T &n1, const T &n2){
			return n1->ident.dist < n2->ident.dist;
		}
	};

	//Shortest path algorithm when S  is WeightedNode<M,N> and S is a numerical type, matching N
	template <typename T, typename S> void Dijkstra(const GraphTheory::Graph<T,S> &input, const T &source){

		//Create the priority queue
		std::priority_queue<typename Graph<T,S>::Node*, std::vector<typename Graph<T,S>::Node* >, PQ_CompareVertex<typename Graph<T,S>::Node*> > vqueue;

		//Set all distances to -1
		for (typename Graph<T,S>::NodeIterator i = input.begin(); i != input.end(); ++i)
			i->ident.dist = -1;

		//Get the source
		typename Graph<T,S>::Node *first = input.FindNode(source);
		first->ident.dist = 0;
		vqueue.push( first );

		//loop through queue until empty
		while (!vqueue.empty()){
			typename Graph<T,S>::Node *curr = vqueue.top();
			vqueue.pop();

			//Go through each edge connecting curr
			for (typename Graph<T,S>::EdgeIterator e = curr->begin_edge(); e != curr->end_edge(); ++e){
				if (e->dst->ident.dist == -1 || e->dst->ident.dist > curr->ident.dist + e->evalue){
					e->dst->ident.dist = curr->ident.dist + e->evalue;
					vqueue.push(e->dst);
				}
			}
		}

		//DONE
	}


	//=================================================================
	//=================================================================
};

template <typename T, typename S> std::ostream &operator<< (std::ostream &os, const GraphTheory::Graph<T,S> &graph){
	unsigned int nodecount = graph.NodeCount();
	unsigned int edgecount = graph.EdgeCount();
	os << "Graph has " << nodecount << " node" << (nodecount != 1 ? "s" : "") << " and " << edgecount << " edge" << (edgecount != 1 ? "s" : "") << "." << std::endl;
	for (typename GraphTheory::Graph<T,S>::NodeIterator i = graph.begin(); i != graph.end(); ++i){
		os << "  Node " << i->getIdent() << ":" << std::endl;
		for (typename GraphTheory::Graph<T, S>::EdgeIterator j = i->begin_edge(); j != i->end_edge(); ++j){
			os << "    Edge to " << j->dst->getIdent() << " with value " << j->evalue << std::endl;
		}
	}
	return os;
}

#endif /*GRAPH_H_*/