#include <iostream>


using namespace std;

class Node
{
public:
	int value;
	Node* prev;
	Node* next;

	Node()
	{
		value = 0;
		prev = NULL;
		next = NULL;
	}
	Node(int val, Node* pre, Node* nex)
	{
		value = val;
		prev = pre;
		next = nex;
	}
};

class DoublyLinkedList
{
public:
	Node* head;

	DoublyLinkedList()
	{
		head = NULL;
	}
	~DoublyLinkedList()
	{
		Node* current = head;
		while (current != NULL)
		{
			Node* temp = current->next;
			delete current;
			current = temp;
		}
		// DO NOT CALL DELETE THIS, THE COMPILER DOES IT.
	}






	void PushToBack(int value)
	{
		Node *node = new Node(value, NULL, NULL);

		if (head == NULL) {
			head = node;
		}
		else {
			Node *last = head;
			while (last->next != NULL)
				last = last->next;
			last->next = node;
			node->prev = last;
		}
		cout << "pushed Node of value: " << node->value << " to back of List" << endl;
		node = NULL; // remove associated memory
		delete node;
	}

	void PushToFront(int value)
	{
		Node *node = new Node(value, NULL, NULL);

		if (head == NULL) {
			head = node;
		}
		else {
			node->next = head;
			head->prev = node;
			head = node;
		}
		cout << "pushed Node of value: " << node->value << " to front of List"<< endl;
		node = NULL; // remove associated memory
		delete node;
	}

	void PopFromBack()
	{
		Node* current = head;
		while (current != NULL)
		{
			current = current->next;
			// A > B > C
			// we want to remove C because C is the last,
			// tell B that B has no more next
			// delete C
			if (current->next == NULL)
			{
				current->prev->next = NULL;
				cout << "popped Node of value: " << current->value << endl;
				delete current;
				current = NULL;
			}
		}
	}

	void PopFromFront() {
		// make sure there is something to pop front
		if (GetSize() == 0)
			return;
		// if popping front the last element in the list
		else if (GetSize() == 1)
		{
			head = NULL;
		}
		else
		{
			// create copy of head->next, we will need this
			Node *n = head->next;
			// prev should point to NULL
			cout << "popped Node of value: " << head->value << endl;
			n->prev = NULL;
			// delete head
			delete head;
			// assign head to the copy
			head = n;
		}
	}

	void insert(int value, int position)
	{
		int copyInt = position;
		if (position <= 1) // we are trying to add to front of list
		{
			this->PushToFront(value); //we just create a node there with this info.
		}

		else if (position >= GetSize()) // we are trying to add to back of list
		{
			this->PushToBack(value); //we just create a node there with this info.
		}

		else
		{
			Node* newNode = new Node(value, NULL, NULL);
			Node *current = head;
			while (position-- > 1)
				current = current->next;

			newNode->next = current;

			if (current->prev)
				current->prev->next = newNode;
			current->prev = newNode;
			// prev should point to NULL
			cout << "inserted new Node of value: " << newNode->value << " at position " << copyInt << endl;
			newNode = NULL;
			delete newNode;
		}
	}

	void removeAt(int position)
	{
		int IntCopy = position;
		if (position <= 1) // we are trying to pop front of list
		{
			this->PopFromFront();
		}

		else if (position >= GetSize()) // we are trying to pop back of list
		{
			this->PopFromBack();
		}

		else
		{
			Node *current = head;
			while (position-- > 1)
				current = current->next;

			//A > B > C > D
			// remove C,
			// TELL B THAT HIS NEXT IS D
			current->prev->next = current->next;
			// TELL D THAT HIS PREV IS B
			current->prev = current->prev->next;
			cout << "removed Node of value: " << current->value << " from position " << IntCopy << endl;
			delete current;
		}
	}

void Swap(int pos1, int pos2)
{

		int IntCopy1 = pos1;
		int IntCopy2 = pos2;
		if (pos1 == pos2 || (GetSize() == 1) || GetSize() == 0) //don't swap if have 1 or 0 things inside
			//also don't swap same index
			return;
		Node* copyA;
		if (pos1 <= 1) {
			// we get the first guy
			copyA = head;
		}
		else if (pos1 >= GetSize()) {
			// we need to get the pointer of the last guy
			Node* current = head;
			while (current != NULL) {
				current = current->next;
			}
			//now current confirm pointing to the last guy.
			copyA = current;
		}
		else {
			Node *current = head;
			while (pos1-- > 1) {
				current = current->next;
			}
			//current is now correct.
			copyA = current;
		}

		Node* copyB;
		if (pos2 <= 1) {
			// we get the first guy
			copyB = head;
		}
		else if (pos2 >= GetSize())
	    {
			// we need to get the pointer of the last guy
			Node* current = head;
			while (current != NULL)
			 {
				current = current->next;
			}
			//now current confirm pointing to the last guy.
			copyB = current;
		}
		else
		{
			Node *current = head;
			while (pos2-- > 1)
			{
				current = current->next;
			}
			//current is now correct.
			copyB = current;
		}
		Node* current = head;
		int temp = copyA->value;
		// no point swapping pointers and stuff, so we swap values.
		// this maintains the prev and next.
		while (current != NULL)
		{
			if (current == copyA)
			{
				cout << "Node[" << IntCopy1 << "] with value of " << copyA->value << endl;
				current->value = copyB->value;
			}
			else if (current == copyB)
			{
				cout << "Node[" << IntCopy2 << "] with value of " << copyB->value << endl;
				current->value = temp;
			}
			current = current->next;
		}
		//post swap checking
		cout << "Node[" << IntCopy1 << "] now has value of " << copyA->value << endl;
		cout << "Node[" << IntCopy2 << "] now has value of " << copyB->value << endl;
		this->Display();
}

	void Display(){


		int counter = 0;
		Node* current = head;

		while (current != NULL)
		{
			cout << current->value << endl;
			current = current->next;
			counter++;
		}
		cout << "Total numbers in the linked list : " << counter << endl;
	}

	int GetSize() //we use this to get the size of the list, the proper way.
	{
		int counter = 0;
		Node* current = head;

		while (current != NULL)
		{
			current = current->next;
			counter++;
		}
		return counter;
	}
};

int main()
{
	DoublyLinkedList* numberList = new DoublyLinkedList();


	numberList->Display();


	numberList->PushToBack(11);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	numberList->PushToBack(22);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	numberList->PushToBack(33);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	numberList->PushToBack(44);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	numberList->removeAt(3);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	numberList->PushToFront(13);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	numberList->removeAt(3);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	numberList->insert(15, 2);
	cout << "=================" << endl;
	numberList->Display();
	cout << "=================\n" << endl;

	cout << "=================" << endl;
	numberList->Display();
	cout<<"swap [1] with [3]"<<endl;
    numberList->Swap(1, 3);
	cout << "================\n"<<endl;

	cout << "=================" << endl;
	numberList->Display();
	cout<<"swap [2] with [3]"<<endl;
    numberList->Swap(2, 3);
	cout << "================\n"<<endl;


	return 0;
	system("pause");
}