//*******************************************************************************************************
//
//			File:			LinkedList.h
//
//			Student:		Georgy Sinitsyn
//
//			Assignment:		Assignment #14: StudentList
//
//			Course name:	Data Structures I
//
//			Course number:	COSC 3050 - 01
//
//			Due:			October 10, 2016
//
//
//			This header contains the LinkedList class with all functions
//
//			Other files required:
//				1. LLdriver.cpp
//				2. Node.h
//
//*******************************************************************************************************

#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H

#include "Node.h"
#include <iostream>
using namespace std;

template <typename Type>
class DLList
{
private:
	Node <Type> *front;
	Node <Type> *rear;
public:
	DLList();
	~DLList();
	bool insert(const Type &);
	bool remove(Type &);
	bool retrieve(Type &) const;
	bool viewFront(Type &) const;
	bool viewBack(Type &) const;
	bool isEmpty() const;
	bool isFull() const;
	bool clearList();
	void display() const;
	void displayReverse() const;
	int getSize() const;
	bool counting(const Type &, int &) const;
	bool removeAllBut(const Type &);
};

//*******************************************************************************************************
//	Constructor
//*******************************************************************************************************

template <typename Type>
DLList <Type> ::DLList()
{
	front = nullptr;
	rear = nullptr;
}

//*******************************************************************************************************
//	Destructor
//*******************************************************************************************************

template <typename Type>
DLList <Type> :: ~DLList()
{
	Node <Type> *pTemp;
	rear = nullptr;
	while (front != nullptr)
	{
		pTemp = front;
		front = pTemp->next;
		delete pTemp;
	}
}

//*******************************************************************************************************
//	insert() function
//		insert a new node into the linkedlist
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::insert(const Type &dataIn)
{
	bool success = false;

	Node <Type> *pTemp = front;

	while (pTemp != nullptr && pTemp->data < dataIn)
		pTemp = pTemp->next;

	Node <Type> *pNew = new (nothrow) Node <Type>(dataIn, pTemp, nullptr);

	if (pNew != nullptr)
	{
		if (front == nullptr)
		{
			rear = pNew;
			front = pNew;
		}
		else if (pTemp == front)
		{
			front->prev = pNew;
			front = pNew;
		}
		else if (pTemp == nullptr)
		{
			rear->next = pNew;
			pNew->prev = rear;
			rear = pNew;
		}
		else
		{
			pNew->prev = pTemp->prev;
			pTemp->prev->next = pNew;
			pTemp->prev = pNew;
		}
		success = true;
	}

	return success;
}

//*******************************************************************************************************
//	remove() function
//		removes a node from the linkedlist
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::remove(Type &dataOut)
{
	bool success = false;

	Node <Type> *pDel = front;

	while (pDel != nullptr && pDel->data < dataOut)
		pDel = pDel->next;

	if (pDel != nullptr && pDel->data == dataOut)
	{
		dataOut = pDel->data;
		if (front->next == nullptr)
		{
			rear = nullptr;
			front = nullptr;
		}
		else if (pDel->prev == nullptr)
			front = front->next;
		else if (pDel->next == nullptr)
			rear = rear->prev;
		else
		{
			pDel->prev->next = pDel->next;
			pDel->next->prev = pDel->prev;
		}

		delete pDel;
		success = true;
	}

	return success;
}

//*******************************************************************************************************
//	retrieve() function
//		retrieves a node from the linkedlist
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::retrieve(Type &dataOut) const
{
	bool success = false;

	Node <Type> *pTemp = front;

	while (pTemp != nullptr && pTemp->data < dataOut)
		pTemp = pTemp->next;

	if (pTemp != nullptr && pTemp->data == dataOut)
	{
		dataOut = pTemp->data;
		success = true;
	}

	return success;
}

//*******************************************************************************************************
//	viewFront() function
//		view the first node in the linkedlist
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::viewFront(Type &dataOut) const
{
	bool success = false;

	if (front != nullptr)
	{
		dataOut = front->data;
		success = true;
	}

	return success;
}

//*******************************************************************************************************
//	viewBack() function
//		view the last node in the linkedlist
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::viewBack(Type &dataOut) const
{
	bool success = false;

	if (front != nullptr)
	{
		dataOut = rear->data;
		success = true;
	}

	return success;
}

//*******************************************************************************************************
//	isEmpty() function
//		checks if the linkedlist is empty
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::isEmpty() const
{
	bool success = false;

	if (front == nullptr)
		success = true;

	return success;
}

//*******************************************************************************************************
//	isFull() function
//		checks if the linkedlist is full
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::isFull() const
{
	bool full = true;
	Node <Type> *pTemp = new (nothrow)Node <Type>;
	if (pTemp != nullptr)
	{
		full = false;
		delete pTemp;
	}
	return full;

}

//*******************************************************************************************************
//	clearList() function
//		clears the list from every node
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::clearList()
{
	bool success = false;

	Node <Type> *pTemp;
	rear = nullptr;
	if (front != nullptr)
	{
		while (front != nullptr)
		{
			pTemp = front;
			front = pTemp->next;
			delete pTemp;
		}
		success = true;
	}

	return success;
}

//*******************************************************************************************************
//	display() function
//		displays every node in the console
//*******************************************************************************************************

template <typename Type>
void DLList <Type> ::display() const
{
	Node <Type> *pTemp = front;

	while (pTemp != nullptr)
	{
		cout << pTemp->data;
		pTemp = pTemp->next;
	}
}

//*******************************************************************************************************
//	display() function
//		displays every node in reversed way in the console
//*******************************************************************************************************

template <typename Type>
void DLList <Type> ::displayReverse() const
{
	Node <Type> *pTemp = rear;
	while (pTemp != nullptr)
	{
		cout << pTemp->data;
		pTemp = pTemp->prev;
	}

}

//*******************************************************************************************************
//	getSize() function
//		gets the number of nodes in the linkedlist
//*******************************************************************************************************

template <typename Type>
int DLList <Type> ::getSize() const
{
	Node <Type> *pTemp = front;
	int num = 0;

	while (pTemp != nullptr)
	{
		num++;
		pTemp = pTemp->next;
	}

	return num;
}

//*******************************************************************************************************
//	counting() function
//		gets the number of specific nodes
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::counting(const Type &dataIn, int &count) const
{
	Node <Type> *pTemp = front;
	bool success = false;

	count = 0;

	if (pTemp != nullptr)
	{
		while (pTemp != nullptr)
		{
			if (pTemp->data == dataIn)
				count++;
			pTemp = pTemp->next;
		}
		success = true;
	}

	return success;
}

//*******************************************************************************************************
//	removeAllBut() function
//		remove all nodes except for a chosen one
//*******************************************************************************************************

template <typename Type>
bool DLList <Type> ::removeAllBut(const Type &dataIn)
{
	bool success = false;

	Node <Type> *pTemp = front;
	Node <Type> *pDel = nullptr;

	if (pTemp != nullptr)
	{
		while (pTemp != nullptr)
		{
			if (pTemp->data != dataIn)
			{
				pDel = pTemp;
				if (rear = pDel && front == pDel)
				{
					front = nullptr;
					rear = nullptr;
				}
				else if (front == pDel)
				{
					front = front->next;
					pTemp = front;
				}
				else if (rear == pDel)
				{
					rear = rear->prev;
				}
				else
				{
					pTemp->prev->next = pTemp->next;
					pTemp->next->prev = pTemp->prev;
				}
				delete pDel;
			}
			else
				pTemp = pTemp->next;
		}
		success = true;
	}
	return success;
}

#endif