#include <iostream>
#include "Profiler.h"
#define AVG_K_5 ("Average_Case_K_5");
#define AVG_K_10 ("Average_Case_K_10");
#define AVG_K_100 ("Average_Case_K_100");
using namespace std;
Profiler profiler("Merge K Sorted Lists");

int OP;

struct Node {
	int data;
	struct Node* next;
};

void PrintList(Node* list)
{
	Node* head = list;
	while (head != NULL)
	{
		cout << head->data << " ";
		head = head->next;
	}
	cout << endl;
}

Node* createNode(int data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode)
	{
		newNode->data = data;
		newNode->next = NULL;
	}
	return newNode;
}

void InsertNode(Node** list, int data)
{
	Node* node = createNode(data/*, KeyList*/);
	if (list == NULL)
		*list = node;
	else
	{
		node->next = *list;
		*list = node;
	}
}

void createList(Node** list, int size)
{
	int* a = (int*)malloc(size * sizeof(int));
	FillRandomArray(a, size, 10, 50000, false, 1);
	for (int i = size-1; i >= 0; i--)
		InsertNode(list, a[i]);

}

Node** createKLists(int n, int k)
{
	int length;
	Node** arrayLists = (Node**)malloc(k * sizeof(Node*));
	if (n % k == 0)
	{
		for (int i = 0; i < k; i++)
		{
			length = n / k;
			arrayLists[i] = (Node*)malloc(length * sizeof(Node));
			arrayLists[i] = NULL;
			createList(&arrayLists[i], length);
		}
	}
	else
	{
		for (int i = 0; i < k; i++)
		{
			if (i < n % k)
				length = (n / k) + 1;
			else
				length = n / k;
			arrayLists[i] = (Node*)malloc(length * sizeof(Node));
			arrayLists[i] = NULL;
			createList(&arrayLists[i], length);
		}
	}

	return arrayLists;
}

void Heapify(Node** heap, int n, int i)
{

	int root;
	int left = 2 * i + 1; //the left child of the node i is at (2*i+1) index
	int right = 2 * i + 2; //the right child of the node i is at (2*i+2) index

	if (left<n && heap[left]>heap[i]) //we check whether or not the left child is larger than the root and if it is, the root will take the index value of the left child
	{
		root = left;
		OP++;
	}
	else root = i;
	if (left < n) OP++;

	if (right<n && heap[right]>heap[root]) //we check whether or not the right child is larger than the root and if it is, the root will take the index value of the right child
	{
		root = right;
		OP++;
	}
	if (right < n) OP++;

	if (root != i)
	{
		swap(heap[i], heap[root]);
		OP += 3;
		Heapify(heap, n, root); //if the root doesn't have the same value as the initial value, then we swap the terms and recursively heapify the affected subtree
	}
}

void MinHeap(Node** heap, int n)
{
	for (int i = n / 2 - 1; i >= 0; i--)
		Heapify(heap, n, i);
}

Node* popHeap(Node** heap, int* heap_size)
{
	Node* pop = NULL;
	if (heap[0]->next == NULL)
	{
		pop = heap[0];
		(*heap_size)--;
		heap[0] = heap[*heap_size];
		Heapify(heap, *heap_size, 0);
	}
	else
	{
		pop = heap[0];
		heap[0] = heap[0]->next;
		Heapify(heap, *heap_size, 0);
	}
	return pop;
}

void Merge2Lists(Node* list1, Node* list2, Node* result)
{
	Node* current = NULL;
	while (list1 != NULL && list2 != NULL)
	{
		if (list1->data < list2->data)
		{
			current = list1;
			list1 = list1->next;
			current->next = NULL;
			result->next = current;
		}
		else
		{
			current = list2;
			list2 = list2->next;
			current->next = NULL;
			result->next = current;
		}
		result = result->next;
	}

	if (list1 == NULL)
		result->next = list2;
	else
		result->next = list1;
}

Node* MergeKLists(Node** arrayLists, int n, int k)
{
	Node* final = NULL;
	Node* result = NULL;
	Node** heap = (Node**)malloc(k * sizeof(Node*));
	int heap_size = k;
	for (int i = 0; i < k; i++)
		heap[i] = arrayLists[i]; //we memorize in heap the heads of each list
	MinHeap(heap, heap_size); //we heapify the constructed heap

	result = popHeap(heap, &heap_size);
	final = result;

	while (heap_size > 2)
	{
		Node* pop = popHeap(heap, &heap_size);
		final->next = pop;
		final = final->next;
	}
	Merge2Lists(heap[0], heap[1], final);

	return result;
}

void demo()
{
	int n = 20, k = 4;
	Node** arrayLists = createKLists(n, k);
	Node* result = NULL;
	cout << "The " << k << " lists are:\n";
	for (int i = 0; i < k; i++)
		PrintList(arrayLists[i]);
	result= MergeKLists(arrayLists, n, k);
	cout << "\nThe merged list:\n";
	PrintList(result);


}

int main()
{

	demo();
	return 0;
}