/*
James O' Connor 50703338
31/10/2002

dijkstra.cpp

This is my original work. No part of this has been copied.
Remember, plagerism is a serious offence, so don't even THINK of using
this code in your college project :)

This program implements Dijkstra's routing algorithm.
Usage: program fileName startNode endNode
where fileName is a txt file with node info in the following format:
a	b	10
b	c	12


*/

//for file access
#include <fstream>

#include <iostream>
using namespace std;

//global constants
const int infinity = 100000000;
const int maxNodes = 1024;

class Node
{   
	private:
		char name;	//this nodes name
		int numLinks;	//number of links it has
		Node * links[4];	//store links
		int link_lengths[4];	//store link distances 
		bool permanent;		//permanent, or not permanent(tentative)
		Node * prevNode;	//previous node
		int dist2Start;		//distance from start node
	
	public:
		Node(char);//constructor
		bool addLink(Node *, int);	//add a link to the node

		//get a link, (retuning Node, returning dist, passing link number)
		void getLink(Node **, int *, int); 
		
		char getName();	//get the node's name
		int getNumLinks();	//get number of links
		int getDist2Start();	//get distance to start node
		void setDist2Start(int dist);	//set distance to start node
		Node * getPrevNode();	//get previous node
		void setPrevNode(Node *);	//set previous node
		bool isPermanent();		//get wether node is permanent or not
		void setPermanent(bool state);	//set node to permanent

		//get wether a link exists with the supplied node
		bool existsLink(Node *);
};

Node::Node(char myName)
{
	name = myName;	//set name
	numLinks =0;
	permanent = false;	//set node tentative
	dist2Start = infinity;
	prevNode = 0;	//no previous node until set

	//initialise pointers to null for safety
	for(int i=0; i<4; i++)
	{	links[i]=0;
		link_lengths[i]=0;
	}
}

bool Node::addLink(Node * newNode, int length)
{
	if(numLinks >=0 && numLinks <4)//max 4 links, min 0
	{
		links[numLinks] = newNode;	//add new node to links
		link_lengths[numLinks] = length;//add corresponding distance
		numLinks++;
		return true;		
	}

	else
		return false;
}

void Node::getLink(Node ** linkNode, int * dist, int linkNumber)
{	
	*linkNode = links[linkNumber];//pass back a pointer to the linked node
	*dist = link_lengths[linkNumber];//pass back distance to linked node

}

char Node::getName()
{
	return name;
}

int Node::getNumLinks()
{
	return numLinks;
}


int Node::getDist2Start()
{
	return dist2Start;
}

void Node::setDist2Start(int dist)
{
	dist2Start = dist; //set distance to startnode to 'dist'
}

Node * Node::getPrevNode()
{
	return prevNode;
}

void Node::setPrevNode(Node * prev)
{
	prevNode = prev; //set previous node to that supplied 'prev'
}

bool Node::isPermanent()
{
	return permanent;
}

void Node::setPermanent(bool state)
{
	permanent = state; //make node permanent
}

bool Node::existsLink(Node * n)
{
//test each link to see if it matches supplied node 'n'
	for(int i=0; i< numLinks; i++)
		if(links[i]->getName() == n->getName())
			return true;

	return false;
}

//a network contains nodes, is initialised from input file
class Network
{
	private:
		Node * nodes[maxNodes];  //main node array
		int numNodes;			//number of nodes
		int minPathDist;		//shortest path found so far
			

	public:
		Network();//constructor
		~Network();//destructor

		// does this network contain supplied node?
		bool exists(char nodeName); 

		//add a node to the network
		bool addNode(char nodeName);

		//return a node given its name
		Node * getNode(char nodeName);

		//return a node given its index in the nodes array
		Node * getNode(int nodeNum);

		//find the shortest path from one node to another
		void getShortestPath(char path[], int * dist, char startNodeName, char endNodeName);

};

Network::Network()
{
	numNodes =0;
	minPathDist = infinity;

	// set nodes to null pointers for safety
	for(int i=0; i<maxNodes; i++)
		nodes[i] = 0;
}

Network::~Network()
{
	// delete all nodes
	for(int i=0; i<numNodes; i++)
		delete nodes[i];
}

bool Network::exists(char nodeName)
{
	//check nodes array for supplied node
	for(int i=0; i<numNodes; i++)
		if(nodes[i]->getName()==nodeName)
			return true;

	return false;
}

bool Network::addNode(char nodeName)
{
	if(numNodes<maxNodes)
	{
		//add node to array
		nodes[numNodes] = new Node(nodeName);
		//increment number of nodes
		numNodes++;
		return true;
	}

	return false;
}

Node * Network::getNode(char nodeName)
{
	//if node is in array, return it
	for(int i=0; i<numNodes; i++)
		if(nodes[i]->getName()==nodeName)
			return nodes[i];

	//if node not in array return null pointer
    Node * bad =0;
	return bad;
}

Node * Network::getNode(int nodeNum)
{
	//return node of index 'nodeNum'
	if(nodeNum>=0 && nodeNum<numNodes)
		return nodes[nodeNum];

	//if not a valid index, return null pointer
    Node * bad =0;
	return bad;
}

/*important method, implements dijkstra's algorithm
'path[]' is the resultant path, 'dist' is the resultant distance,
'startNodeName' and 'endNodeName' are names of start and end node*/
void Network::getShortestPath(char path[], int * dist, char startNodeName, char endNodeName)
{
	//in case someone gets tricky ;-)
	if(startNodeName == endNodeName)
	{
		path[0] = endNodeName;
		path[1] = ' ';
		path[2] = '\0';
		*dist =0;
		return;
	}


	Node * startNode = getNode(startNodeName);
	Node * endNode = getNode(endNodeName);

	//make sure nodes exist!!
	if(startNode ==0 || endNode == 0)
	{
		cout << "Bad Input!"<<endl;
		exit(1);
	}

	//some basic initialisation
	Node * currentNode = startNode;
	Node * nextNode = startNode;
	startNode->setDist2Start(0);
    startNode->setPrevNode(startNode);
	startNode->setPermanent(true);
	int i=0;

	//do until at end node
	while(currentNode->getName() != endNode->getName())
	{

		cout << "Current Node: " << currentNode->getName() <<endl;

		//visit each connection
		for(i=0; i<currentNode->getNumLinks(); i++)
		{
			/*set 'nextNode' to one of the links, 
			set dist to corresponding distance,
			i is the link number to get*/
            currentNode->getLink(&nextNode, dist, i);
			
			//only test tentative nodes
			if(!nextNode->isPermanent())
			{
				cout << nextNode->getName() << " is tentative" <<endl;
             	//if you found a shorter path to 'nextNode', update 'nextNode' with new path
				if(currentNode->getDist2Start() + *dist < nextNode->getDist2Start())
				{
					nextNode->setPrevNode(currentNode);
					nextNode->setDist2Start((currentNode->getDist2Start() + *dist));
				}
			}
			
		}//end for


		//all links of'currentNode' have been visited, make 'currentNode' permanent
		currentNode->setPermanent(true);
		cout << currentNode->getName() << " is permanent" <<endl;
		
		int temp =0;
		minPathDist = infinity;

		//find the tentative node with the minimum distance from start
		for(i=0; i<numNodes; i++)
		{
			if(!getNode(i)->isPermanent() && getNode(i)->getDist2Start()<minPathDist)
			{
				//found new minimum, use it as currentNode in next round
				minPathDist = getNode(i)->getDist2Start();
				currentNode = getNode(i);
				
			} 
		}
			
	}//end while
	
	//set path distance
	*dist = minPathDist;

	Node * tempNode = endNode;
	int k=0;
	char tempChars[2 * maxNodes + 1];// *2 for the spaces, add one for the null

	//copy path into array. will be backwards
	while(tempNode->getName() != startNode->getName())
	{
		tempChars[k] = tempNode->getName();
		tempNode = tempNode->getPrevNode();
		k++;
	
	}
	tempChars[k] =  tempNode->getName() ;
	
	//copy path into 'path[]'. make it the right way around
	for(i=0; i<=k*2; i=i+2)
	{	
		path[i] = tempChars[k - (i / 2)]; //copy char
		path[i + 1] = ' '; //add a space
	}

	//add a null so it can be printed as a string
	path[i] = '\0';
	

		
}

//opens file, initialises network with nodes.
bool readNodes(char *, Network *);//fileHandle, Network object to fill


int main(int argc, char **argv)
{

	char * fileName;
	char startNode;
	char endNode; 
	
	//make sure the program was called correctly
	if( argc == 4)
	{
		fileName = argv[1];
		startNode = *argv[2];
		endNode = *argv[3];
	}

    else	//program not called correctly
	{
		cout << "Incorrect number of parameters! \n Usage: program fileName startNode endNode"<< endl;
		exit(0);
	}

	//construct new network
	Network * net1 = new Network();	

	//read info from file into network
	if(readNodes(fileName, net1))
	{
		int * resultDist = new int;

		//resultant path stored here
		char resultPath[2 * maxNodes + 1]; // *2 for the spaces, add one for the null

		//find the shortest path
		net1->getShortestPath(resultPath, resultDist, startNode, endNode);
	
		//print out results
		cout << "solution " << resultPath << *resultDist << endl;

		//free memory
		delete resultDist;
		net1->~Network();
	}

	else //readNodes failed
		cout << "Couldn't open file!"<<endl;
 return 0;
}

//read file, construct network
bool readNodes(char * fileName, Network * net1)
{
	char node1;
	char node2;
	char dist;

	//open file for reading
	ifstream fin(fileName);

	if(!fin.fail())
	{
		while(fin.get(node1))//get startNode
		{
			fin.get();			//consume tab
			fin.get(node2);		//get endNode
			fin.get();			//consume tab
			fin.get(dist);		//get distance
			fin.get();			//consume newline

			//add node to network if its new
			if(!net1->exists(node1))
				net1->addNode(node1);
			
			//add node to network if its new
			if(!net1->exists(node2))
				net1->addNode(node2);

			//add link to node if its new. The '-48' below converts char to int
			if(! net1->getNode(node1)->existsLink(net1->getNode(node2)) )
				net1->getNode(node1)->addLink(net1->getNode(node2), (dist - 48));
			
			//add link to node if its new
			if(! net1->getNode(node2)->existsLink(net1->getNode(node1)) )
				net1->getNode(node2)->addLink(net1->getNode(node1), (dist - 48));

		}
		
	}//end if

	else //file open failed
	{	
		fin.close();
		return false;
	}
	
	fin.close();
	return true;
}