#include <iostream>
#include <fstream>

using namespace std;

struct Node {
	int value;
	Node* next;
	Node* prev;

	Node(int v) {
		value = v;
	}

	Node() {}
};

struct List {
	Node* head = NULL;
	Node* last = NULL;
	int size = 0;

	List() {};

	List(Node* first, Node* last, int size) {

		this->head = first;
		this->last = last;
		this->size = size;

	}

	List* add(int v) {

		if (head == NULL) {
			head = new Node(v);
			size++;
			last = head;
			last->next = NULL;
			last->prev = NULL;
		}

		else {
			last->next = new Node(v);
			last->next->prev = last;
			size++;
			last = last->next;
			last->next = NULL;
		}

		return this;
	}


	void unshitf(int v) {
		if (size == 0) {
			head = new Node(v);
			size++;
			last = head;
			last->next = NULL;
			last->prev = NULL;
		}
		else {
			head->prev = new Node(v);
			head->prev->next = head;
			head = head->prev;
			size++;


		}
	}

	void wypisz() {
		Node* tmp = head;
		for (int i = 0; i < size; i++) {
			cout << tmp->value << " ";
			cout << "Poprzedni: " << tmp->prev << "  Nastepny: " << tmp->next << endl;
			tmp = tmp->next;

		}
		cout << endl;
	}

	void readFromFile(string filename) {

		ifstream input(filename);
		while (!input.eof()) {
			int tmp;
			input >> tmp;
			this->add(tmp);
		}
		input.close();
	}

	void deleteValue(int v) {

		Node* tmp = head;
		if (head->value == v) {
			tmp = head->next;
			delete head;
			head = tmp;
			tmp->prev = NULL;
			size--;
		}

		do {
			if (tmp->value == v) {
				tmp->prev->next = tmp->next;
				tmp->next->prev = tmp->prev;
				Node* tmp2 = tmp->next;
				delete tmp;
				size--;
				tmp = tmp2;
			}

			else tmp = tmp->next;
		} while (tmp->next != NULL);
		if (tmp->value == v) {
			tmp->prev->next = NULL;
			delete tmp;
			size--;
		}

	}

	void addAt(int index, int value) {

		if (index <= 0) { unshitf(value); return; }


		Node* tmp = head;
		for (int i = 0; i < size; i++) {

			if (i == index) {
				tmp->prev->next = new Node(value);
				tmp->prev->next->next = tmp;
				tmp->prev->next->prev = tmp->prev;
				tmp->prev = tmp->prev->next;
				size++;
				return;
			}
			tmp = tmp->next;
		}

		add(value);

	}


	void swap(int index1, int index2) {

		Node* tmp = head;
		Node* tmp1 = NULL;
		Node* tmp1Prev = NULL;
		Node* tmp1Next = NULL;
		Node* tmp2 = NULL;
		Node* tmp2Prev = NULL;
		Node* tmp2Next = NULL;

		if (index1 == index2)return;

		if (index1 > index2) {
			int tmp = index1;
			index1 = index2;
			index2 = tmp;

		}



		for (int i = 0; i < size; i++) {
			if (i == index1) {
				tmp1 = tmp;
				tmp1Next = tmp1->next;
				tmp1Prev = tmp1->prev;

			}
			if (i == index2) {
				tmp2 = tmp;
				tmp2Next = tmp2->next;
				tmp2Prev = tmp2->prev;

			}

			tmp = tmp->next;

		}

		if (index2 == size - 1 && index1 == 0) {

			tmp1->next = NULL;
			tmp1->prev = tmp2Prev;
			tmp1->prev->next = tmp1;

			tmp2->prev = NULL;
			tmp2->next = tmp1Next;
			tmp2->next->prev = tmp2;

			head = tmp2;
			last = tmp1;


			return;
		}

		if (index2 == size - 1 && index1 == size - 2) {
			last = tmp1;
			tmp1->next = NULL;
			tmp1->prev = tmp2;
			tmp1->prev->next = tmp1;



			tmp2->prev = tmp1Prev;
			tmp2->prev->next = tmp2;


			return;
		}


		if (index2 == size - 1) {
			last = tmp1;
			tmp1->next = NULL;
			tmp1->prev = tmp2Prev;
			tmp1->prev->next = tmp1;


			tmp2->next = tmp1Next;
			tmp2->prev = tmp1Prev;
			tmp2->prev->next = tmp2;
			tmp2->next->prev = tmp2;

			return;
		}


		if (index2 - index1 == 1) {
			tmp1->next = tmp2->next;
			tmp1->prev = tmp2;
			tmp2->next = tmp1;
			tmp2->prev = tmp1Prev;
			if (tmp1Next != NULL)tmp2Next->prev = tmp1;
			if (index1 == 0) {
				head = tmp2;
				tmp2->prev = NULL;

			}

			else { tmp1Prev->next = tmp2; }




			return;
		}

		if (index1 == 0) {

			tmp2->prev = NULL;
			tmp2->next = tmp1Next;
			tmp2->next->prev = tmp2;


			tmp2Prev->next = tmp1;
			tmp2Next->prev = tmp1;
			tmp1->next = tmp2Next;
			tmp1->prev = tmp2Prev;
			head = tmp2;

			return;
		}


		if (tmp1 == NULL || tmp2 == NULL) return;

		//Zamiana
		tmp1Prev->next = tmp2;
		tmp1Next->prev = tmp2;
		tmp2->next = tmp1Next;
		tmp2->prev = tmp1Prev;


		tmp2Prev->next = tmp1;
		tmp2Next->prev = tmp1;
		tmp1->next = tmp2Next;
		tmp1->prev = tmp2Prev;
	}


	int getIndex(Node* node) {

		Node* tmp = head;
		for (int i = 0; i < size; i++) {
			if (node == tmp) return i;

			tmp = tmp->next;
		}

		return -1;
	}




	void insertSort()
	{
		int i, j;

		i = 1;
		while (i < size) {
			j = i + 1;

			while (j > 0 && get(j - 1) > get(j))
			{
				swap(j, j - 1);
				j = j - 1;
			}
			i = i + 1;
		}
	}

	void set(int index, int value) {
		Node* tmp = head;

		for (int i = 0; i < size; i++) {

			if (i == index) {
				tmp->value = value;
				return;
			}
			tmp = tmp->next;
		}


	}

	int get(int index) {
		Node* tmp = head;

		for (int i = 0; i < size; i++) {

			if (i == index) {
				return tmp->value;
			}
			tmp = tmp->next;
		}


	}

	List* crop(int index) {
		if (index >= this->size) {
			return NULL;
		}

		Node* tmp = head;
		List* newList;

		for (int i = 0; i < size; i++) {

			if (i == index) {
				newList = new List(tmp, this->last, this->size - i);
				this->last = tmp->prev;
				this->size = i;
				return newList;
			}
			tmp = tmp->next;
		}

	}


	void sort() {
		Node* tmp = head;

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size - 1; j++) {
				if (tmp == NULL || tmp->next == NULL) break;
				if (tmp->value < tmp->next->value) {
					this->swap(j, j + 1);

				}

				tmp = tmp->next;
			}
			tmp = head;

		}
	}



	int maxValueIndex(int from = 0) {

		Node* tmp = head;
		int max = 0;
		int maxIndex = 0;


		for (int i = 0; i < size; i++) {
			if (tmp->value > max && i >= from) {
				max = tmp->value;
				maxIndex = i;

			}

			tmp = tmp->next;
		}
		return maxIndex;
	}




	void selectSort() {


		for (int i = 0; i < size - 1; i++) {
			int index = maxValueIndex(i);

			swap(i, index);

		}


	}

	Node* merge(Node *first, Node *second)
	{
		//Jesli pierwszy jest pusty
		if (!first)
			return second;

		//Jesli drugi jest pusty
		if (!second)
			return first;

		// Wybierz mniejsza watrosc
		if (first->value < second->value)
		{
			first->next = merge(first->next, second);
			first->next->prev = first;
			first->prev = NULL;
			return first;
		}
		else
		{
			second->next = merge(first, second->next);
			second->next->prev = second;
			second->prev = NULL;
			return second;
		}
	}


	Node* mergeSort()
	{
		return mergeSort(this->head);
	}


	Node* mergeSort(Node*& head)
	{
		if (!head || !head->next)
			return head;
		Node* second = split(head);


		head = mergeSort(head);
		second = mergeSort(second);


		return merge(head, second);
	}



	Node* split(Node* head)
	{
		Node* list1 = head, *list2 = head;
		while (list1->next && list1->next->next)
		{
			list1 = list1->next->next;
			list2 = list2->next;
		}
		Node* tmp = list2->next;
		list2->next = NULL;
		return tmp;
	}

	void insertSort(Node *head) {

		Node* tmp = head;
		Node* obecny = head->next;
		Node* prev = head;

		//jesli jest sa mniej niz 2 elementy to nie ma co sortowac
		if (!tmp || !tmp->next) {
			return;
		}

		while (obecny) {

			//pomin posortowane elementy

			if (prev->value <= obecny->value) {
				obecny = obecny->next;
				prev = prev->next;
			}

			else {
				//wstaw przed glowe
				if (head->value > obecny->value) {

					prev->next = obecny->next;
					obecny->next = head;
					head = obecny;

				}
				else {

					//wstaw w odpowiednie miejsce
					tmp = head;

					while (!tmp->next && tmp->next->value < obecny->value) {
						tmp = tmp->next;
					}

					prev->next = obecny->next;
					obecny->next = tmp->next;
					tmp->next = obecny;
					tmp->next->prev = tmp;

				}
			}

			obecny->next->prev = obecny;
			obecny = prev->next;

		}
	}



	void addBeforeFirst(Node *& head, double value) {

		Node * newNode = new Node;
		newNode->value = value;

		if (head == NULL) {
			head = newNode;
			newNode->next = NULL;

		}
		else {
			newNode->next = head;
			head = newNode;

			newNode->prev = NULL;
			newNode->next->prev = head;
		}

	}

	int partitionLomuto(Node * head, int l, int r) {

		//split using far right element
		double x = get(r);

		//DEBUG
		std::cout << "Value: " << x << " Index l: " << l << " Index r: " << r << "\n";
		//DEBUG

		int i = l - 1;

		for (int j = l; j < r; j++)

			if (get( j) < x) {
				i++;
				swap(i, j);
			}

		swap(i + 1, r);

		return i + 1;
	}

	void quickSort(Node * head, int l, int r) {

		if (l >= r) {
			return;
		}

		int pivot = partitionLomuto(head, l, r);

		quickSort(head, l, pivot - 1);
		quickSort(head, pivot + 1, r);
	}
	void quickSortV2(Node *& head) {
		this->add(NULL);
		//add sentry
		addBeforeFirst(head, 0);

		//get length of node
		Node * tmp = head;
		int i = 0;
		while (tmp) {
			i++;
			tmp = tmp->next;
		}

		//quickSort
		quickSort(head, 1, i - 1);

		//remove sentry
	//	Node * backupHead = head;
		//head = head->next;
	//	delete backupHead;

		//set prev pointer in first element
		head->prev = NULL;
		deleteValue(NULL);
	}


};



int main()
{
	List* list = new List();

	//list->readFromFile("test.txt");

	list->add(1)->add(4)->add(3)->add(2)->add(8)->add(1)->add(15)->add(10)->add(11)->add(7)->add(9);
	list->wypisz();

	//list->insertSort();


	//list->mergeSort();
	list->quickSortV2(list->head);
	list->wypisz();



	cout << endl << "Liczba elementow:" << list->size << endl;


	system("pause");
	return 0;
}