#include <stdlib.h>
#include <fstream>
#include <string.h>
#include <vector>
#include <iostream>
//#include "FibonacciHeap.h"

enum State
{
	LABELED, UNLABELED, SCANNED
};
class Edge;
class Node
{
private:
public:
	Node * parent;
	Node * leftSibling, * rightSibling;
	Node * children; 
	Node * pred;

	Node(int data, double key)
	{	
		this->key = key;
		this->data = data;
		parent = NULL;
		children = NULL;
		leftSibling = NULL;
		rightSibling = NULL;
		pred = NULL;
		rank = 0;
		state = UNLABELED;
	}

	Node()
	{
		parent = NULL;
		children = NULL;
		leftSibling = NULL;
		rightSibling = NULL;
		pred = NULL;
		rank = 0;
		state = UNLABELED;
	}

	int data;
	double key;
	int rank;

	std::vector<Edge*> incomingEdges;
	std::vector<Edge*> outgoingEdges;

	State state;

	bool addChild(Node * node)
	{
		if(children != NULL)
			children->addSibling(node);
		else
		{
			children = node;
			node->parent = this;
			rank = 1;
		}

		return true;
	}

	bool addSibling(Node * node)
	{
		Node* temp = rightMostSibling();
		if(temp == NULL)
			return false;

		temp->rightSibling = node;
		node->leftSibling = temp;
		node->parent = this->parent;
		node->rightSibling = NULL;

		if(parent)
			parent->rank++;

		return true;
	}

	bool remove()
	{
		if(parent)
		{
			parent->rank--;
			if(leftSibling)
				parent->children = leftSibling;
			else if(rightSibling)
				parent->children = rightSibling;
			else
				parent->children = NULL;
		}	
		
		if(leftSibling)
			leftSibling->rightSibling = rightSibling;
		if(rightSibling)
			rightSibling->leftSibling = leftSibling;
		
		leftSibling = NULL;
		rightSibling = NULL;
		parent = NULL;

		return true;
	}



	Node* leftMostSibling()
	{
		if(this == NULL)
			return NULL;

		Node* temp = this;
		while(temp->leftSibling)
			temp = temp->leftSibling;
		return temp;
	}

	Node* rightMostSibling()
	{
		if(this == NULL)
			return NULL;

		Node* temp = this;
		while(temp->rightSibling)
			temp = temp->rightSibling;
		return temp;
	}
	
	void addIncomingEdge(Edge * edge)
	{
		incomingEdges.push_back(edge);
	}

	void addOutgoingEdge(Edge * edge)
	{
		outgoingEdges.push_back(edge);
	}

};


class Edge
{
private:
public:
	Node* tail;
	Node* head;
	double length;
	double delta;

	Edge(Node* tail, Node* head, double length)
	{
		this->tail = tail;
		this->head = head;
		this->length = length;
	}
};



class FibonacciHeap
{
private:
	Node* rootListByRank[100];
	Node * minRoot;

public:

	FibonacciHeap()
	{
		minRoot = NULL;
	}

	FibonacciHeap(Node *root)
	{
		this->minRoot = root;
		minRoot->parent = NULL;
		minRoot->children = NULL;
		minRoot->leftSibling = NULL;
		minRoot->rightSibling = NULL;
		minRoot->rank = 0;
	}

	~FibonacciHeap()
	{
		delete[] rootListByRank;
	}

	bool isEmpty()
	{
		return (minRoot == NULL);
	}

	bool insertVertex(Node * node)
	{
		if(node == NULL)
			return false;

		if(minRoot == NULL)
			minRoot = node;
		else
		{
			minRoot->addSibling(node);
			if(minRoot->key > node->key)
				minRoot = node;
		}
		return true;
	}

	Node* findMin()
	{
		return minRoot;
	}

	Node* deleteMin()
	{
		Node *temp = minRoot->children->leftMostSibling();
		Node *nextTemp = NULL;

		// Adding Children to root list		
		while(temp != NULL)
		{
			nextTemp = temp->rightSibling; // Save next Sibling
			temp->remove();
			minRoot->addSibling(temp);
			temp = nextTemp;
		}

		// Select the left-most sibling of minRoot
		temp = minRoot->leftMostSibling();

		// Remove minRoot and set it to any sibling, if there exists one
		if(temp == minRoot)
		{
			if(minRoot->rightSibling)
				temp = minRoot->rightSibling;
			else
			{
				// Heap is obviously empty
				Node* out = minRoot;
				minRoot->remove();
				minRoot = NULL;
				return out;
			}
		}
		Node* out = minRoot;
		minRoot->remove();
		minRoot = temp;

		// Initialize list of roots	
		for(int i=0; i<100; i++)
			rootListByRank[i] = NULL;
		
		while(temp)
		{
			// Check if key of current vertex is smaller than the key of minRoot
			if(temp->key < minRoot->key)
			{
				minRoot = temp;
			}

			nextTemp = temp->rightSibling;		
			link(temp);
			temp = nextTemp;
		}

		return out;	
	}

	bool link(Node* root)
	{
		// Insert Vertex into root list
		if(rootListByRank[root->rank] == NULL)
		{
			rootListByRank[root->rank] = root;
			return false;
		}
		else
		{
			// Link the two roots
			Node* linkVertex = rootListByRank[root->rank];
			rootListByRank[root->rank] = NULL;
			
			if(root->key < linkVertex->key || root == minRoot)
			{
				linkVertex->remove();
				root->addChild(linkVertex);
				if(rootListByRank[root->rank] != NULL)
					link(root);
				else
					rootListByRank[root->rank] = root;
			}
			else
			{
				root->remove();
				linkVertex->addChild(root);
				if(rootListByRank[linkVertex->rank] != NULL)
					link(linkVertex);
				else
					rootListByRank[linkVertex->rank] = linkVertex;
			}
			return true;
		}
	}


	void decreaseKey(double delta, Node* vertex)
	{
		vertex->key = delta;

		if(vertex->parent != NULL) // The vertex has a parent
		{
			// Remove vertex and add to root list
			vertex->remove();
			minRoot->addSibling(vertex);		
		}
		// Check if key is smaller than the key of minRoot
		if(vertex->key < minRoot->key)
			minRoot = vertex;
	}

};


int main(int argc, char *argv[])
{
	printf("K-Shortest Path Algorithm\n\n");
		
	/*
		STEP 0: Initialization
	*/
	long n;

	/*if(argv[1]== NULL)
	{	
		printf("1 Argument required: shortestpath.exe [graph file name]\n");
		printf("Example: ./Dijkstra.exe scotland_big.dat\n");
		return 0;
	}	*/

	// Define test vertices
	std::vector<Node*> vertices;
	std::vector<Edge*> edges;

	// Read source file
	printf("Loading %s\n", argv[1]);
	//std::ifstream indat(argv[1]);
	std::ifstream indat("dijkstra.in");
	char inp[100];

	if(indat)
	{
		indat.getline(inp, 160);
		//n = atol(inp);
		int k=1;
		while(inp[k] != ' ' && inp[k]!='\0')
				k++;
		std::string inpstr = inp;
		n = atoi(const_cast<char*>(inpstr.substr(0, k).c_str()));

		for(int j=0; j<n-1 ; j++)
		{
			Node* v = new Node(j, -1);
			vertices.push_back(v);
		}

		printf("Vertices loaded...\n");

		vertices.push_back(new Node(n-1, 0)); 
		vertices[n-1]->state = LABELED;

		// Read edges and initialize
		while(!indat.eof())
		{
			memset(inp, '\0', sizeof(inp));
			indat.getline(inp, 160);

			int k=1;
			while(inp[k] != ' ' && inp[k]!='\0')
				k++;
			
			std::string inpstr = inp;
			int tail = atoi(const_cast<char*>(inpstr.substr(0, k).c_str()));
			int l=k+1;
			while(inp[l] != ' ' && inp[l]!='\0')
				l++;
			int head = atoi(const_cast<char*>(inpstr.substr(k+1, l).c_str()));
			k=l+1;
			
			while(inp[k] != ' ' && inp[k]!='\0')
				k++;

			double length = atof(const_cast<char*>(inpstr.substr(l+1, k).c_str()));

			Edge* edge = new Edge(vertices[tail], vertices[head], length);
			edge->head->addIncomingEdge(edge);
			edge->tail->addOutgoingEdge(edge);
			edges.push_back(edge);
		}	
	}
	else
	{
		printf("Could not open input data...\n");
		return 0;
	}

	printf("Edges loaded...\n");
	printf("Vertices: %d\nEdges: %d\n\n", vertices.size(), edges.size());
	printf("Building shortest path tree...\n");
	/*
		STEP 1: Shortest Path Tree
	*/

	FibonacciHeap* heap = new FibonacciHeap();

	heap->insertVertex(vertices[n-1]);
	
	bool abort = false;
	long j = 0;
	// Scan
	do
	{
		// Delete minimum path
		Node* v = heap->deleteMin();
		
		v->state = SCANNED;
		
		for(int i = 0; i < v->incomingEdges.size(); i++)
		{
			Edge* currentEdge = v->incomingEdges[i];
			Node* headOfCurrentEdge = currentEdge->tail;

			if(headOfCurrentEdge->state != SCANNED)
				{
				if(headOfCurrentEdge->state == UNLABELED)
				{
					// Insert a vertex with infinite key
					headOfCurrentEdge->state = LABELED;
					headOfCurrentEdge->pred = v;
					headOfCurrentEdge->key = v->key + currentEdge->length;
					heap->insertVertex(headOfCurrentEdge);
				}
				else if(headOfCurrentEdge->key > v->key + currentEdge->length )
				{
					// decrease the key of a vertex with finite key
					headOfCurrentEdge->pred = v;
					heap->decreaseKey(v->key + currentEdge->length, headOfCurrentEdge);
				}
			}
		}
	}
	while(!heap->isEmpty());

	// Print out path
	Node* temp = vertices[0];

	if(!temp->pred)
	{
		printf("There exist no s-t paths\n");
		return 0;
	}

	int vertexCount = 0;
	
	printf("Shortest Path found:\n");
	printf("Distance: %f\n", vertices[0]->key);
	
	while(temp)
	{
		printf("%d", temp->data);
		temp = temp->pred;
		if(temp)
			printf(" - ");

		vertexCount++;
	}

	printf("\nVertices passed: %d\n", vertexCount);
	getchar();
	//cout<<"buu";
	return 0;
}