#ifndef RTS_GRAPH_H
#define RTS_GRAPH_H

#include <list>
#include <algorithm>

using namespace std;

template<typename T>
class rtsGraph
{
	unsigned int current_id;
public:
	class rtsGraphNode;
	typedef typename list<rtsGraphNode>::iterator rtsGraphNodePtr;
	
	class rtsGraphNode
	{
	public:
		list<rtsGraphNodePtr> ConnectionList;
		unsigned int ID;
		T Data;
	};

	list<rtsGraphNode> NodeList;

	rtsGraphNodePtr addNode(T data)
	{
		//Adds a node to the graph.  This node is unconnected by default.

		//create the new node
		rtsGraphNode new_node;
		//set the data to the data provided
		new_node.Data = data;
		//set the id
		new_node.ID = current_id++;

		//add the node to the node list
		NodeList.push_back(new_node);
		rtsGraphNodePtr result = NodeList.end();
		result--;
		return result;
	}
	bool cmpPtr(const rtsGraphNodePtr a, const rtsGraphNodePtr b)
	{
		return (*a).ID < (*b).ID;
	}

	void addConnection(rtsGraphNodePtr n0, rtsGraphNodePtr n1)
	{
		//adds a connection between two nodes
		//connect n0 to n1
		(*n0).ConnectionList.push_back(n1);
		(*n1).ConnectionList.push_back(n0);

	}

	void removeNode(rtsGraphNodePtr n)
	{
		
		typename list<rtsGraphNodePtr>::iterator i;
		typename list<rtsGraphNodePtr>::iterator j;
		typename list<rtsGraphNodePtr>::iterator temp;
		rtsGraphNodePtr m;
		rtsGraphNodePtr k;
		/*Remove all of the connections TO n*/

		//for each node m connected to n
		for(i = (*n).ConnectionList.begin(); i != (*n).ConnectionList.end(); i++)
		{
			m = (*i);
			//for each node k connected to m
			j = (*m).ConnectionList.begin();
			while(j != (*m).ConnectionList.end())
			{
				k = (*j);
				//if k is the same as n, remove it
				if(k == n)
				{
					temp = j;
					j++;
					(*m).ConnectionList.erase(temp);
				}
				else
					j++;

			}
		}

		/*Add all connections to neighboring nodes*/

		//for each node m connected to n
		for(i = (*n).ConnectionList.begin(); i != (*n).ConnectionList.end(); i++)
		{
			m = (*i);
			//for each node k connected to n
			for(j = (*n).ConnectionList.begin(); j != (*n).ConnectionList.end(); j++) 
			{
				k = (*j);
				if(k != m)
					(*m).ConnectionList.push_back(k);				

			}
			//(*m).ConnectionList.sort(&rtsGraph<T>::cmpPtr);
			//sort((*m).ConnectionList.begin(), (*m).ConnectionList.end(), rtsGraph<T>::cmpPtr);
			(*m).ConnectionList.unique();
		}







	}


	void PrintGraph()
	{
		rtsGraphNodePtr i;
		typename list<rtsGraphNodePtr>::iterator c;
		for(i = NodeList.begin(); i != NodeList.end(); i++)
		{
			cout<<(*i).Data<<": ";
			for(c = (*i).ConnectionList.begin(); c != (*i).ConnectionList.end(); c++)
			{
				if(c != (*i).ConnectionList.begin())
					cout<<"--";
				cout<<(*(*c)).Data;
			}
			cout<<endl;		

		}

	}
	
	


};

#endif