////////////////////////////////////////////////////////////////////////
//
//  CList.h: Singly Linked List (Templated Class)
//
//	Author: Christian Benavides
//
//  Description: 
//				-Contains the definition and implementation of the Linked
//				List Class. It uses the Merge Sort Algorithm to sort the values of the
//				list in Ascending Order
////////////////////////////////////////////////////////////////////////

#pragma once
#include "stdafx.h"

template<class T> class CIterator;
template<class T> class CList;

template<class T>
class CList
{
public:
	///	Encapsulated node class
	struct TNode
	{
		T m_data;
		TNode* m_pNext;

		TNode(const T& _value,TNode* _node=nullptr)
		{
			m_data  = _value;
			m_pNext = _node;
		}

	};
private:
	///	Friendly relationship with iterator class
	friend class CIterator < T > ;

	///	Members
	TNode*	m_pHead;	
	int		m_nSize;
	bool	(*m_pComparisonFunction)(const T& _lhs, const T& _rhs);	//	Function pointer used for sorting

	///	Sort related functions. Used on the merge sort.
	void SortList(TNode** _pHeadList, int _nSize);	
	void SplitList(TNode* _pHead, TNode** _frontList, TNode** _backList, int _nSize);
	TNode*  MergeSubLists(TNode* _frontList, TNode* _backList);
	
public:
		
	CList();
	~CList();

	/*ACCESORS*/
	int		GetSize()	const   { return m_nSize; };
	TNode*	GetFront()			{ return m_pHead; };

	/*METHODS*/
	void	Add(const T& _value);			//	Add to head
	bool	Remove(CIterator<T>& _iter);	//	Takes an iterator that indicates what to remove
	void	Insert(CIterator<T>& _iter, const T& _value);	//	Inserts a value in a specified iterator location

	void	Clear();	//	Delete the whole list

	bool	Empty();	//	Returns a flag indicating if it is empty

	void	MergeSort(bool(*_cmpFunc)(const T& _lhs, const T& _rhs));	//	Sort the list using the Merge Sort algorithm and the comparison func proportionated

	

};

////////////////////////////////////////////////////////////////
// IMPLEMENTATION
////////////////////////////////////////////////////////////////

///	Create empty list
template<class T>
CList<T>::CList()
{
	m_pHead = nullptr;
	m_nSize = 0;
}

///	Deallocate the list
template<class T>
CList<T>::~CList()
{
	Clear();
}

///	Add to the head of the list
template<class T>
void CList<T>::Add(const T& _value)
{
	///	Create a new node
	TNode* pNewNode = new TNode(_value);


	/*Special Case: The list is empty, the node is the new head*/	
	if (Empty())
	{
		m_pHead = pNewNode;
		m_nSize++;
		return;
	}

	pNewNode->m_pNext = m_pHead;
	m_pHead = pNewNode;
	m_nSize++;
}

///	Remove a node specified by an iterator
template<class T>
bool CList<T>::Remove(CIterator<T>& _iter)	//	Takes an iterator that indicates what to remove
{

	if (_iter)
	{
		/*Special Case: The list is empty,do not remove OR the iterator is at the end*/
		if (Empty() || _iter.End())
			return false;

		TNode* pNodeToRemove = _iter.m_pCurrent;

		/*Special Case: The node is the head of the list*/
		if (pNodeToRemove == m_pHead)
		{
			m_pHead = m_pHead->m_pNext;
			delete pNodeToRemove;

			///	Update iter
			_iter.m_pCurrent = m_pHead;
			_iter.m_pPrev = nullptr;

			///	Update size
			--m_nSize;

			return true;
		}

		/*Any other case*/

		///	Fix links
		_iter.m_pPrev->m_pNext = _iter.m_pCurrent->m_pNext;
		_iter.m_pCurrent = _iter.m_pCurrent->m_pNext;
		delete pNodeToRemove;

		m_nSize--;
		return true;
	}
}

///	Inserts a value in a specified iterator location (Between Previous and Current)
template<class T>
void CList<T>::Insert(CIterator<T>& _iter, const T& _value)
{
	
		/*Special case: The list is empty*/
		if (Empty())
			return;

		/*Special case: Adding to the head*/
		if (!_iter.m_pPrev)
		{
			Add(_value);	//	Add to head
			_iter.m_pCurrent = m_pHead;
			return;
		}

		/*Any other case*/
		TNode* pNewNode = new TNode(_value);

		///	Update iter and fix links
		_iter.m_pPrev->m_pNext = pNewNode;
		pNewNode->m_pNext		= _iter.m_pCurrent;
		_iter.m_pCurrent		= pNewNode;

		m_nSize++;
	
}

///	Flag is the list is empty
template<class T>
bool CList<T>::Empty()
{
	if (m_pHead)
		return false;

	return true;
}

///	Delete the list
template<class T>
void CList<T>::Clear()
{

	///	Traverse the list and delete 
	while (m_pHead)
	{
		TNode* pTempHead = m_pHead;
		m_pHead = m_pHead->m_pNext;
		delete pTempHead;
	}

	m_nSize = 0;
}

////////////////////////////////////////////////////////////////
// MERGE SORT ALGORITHM FUNCTIONS
//  -Based on the code sample shown at http://www.geeksforgeeks.org/merge-sort-for-linked-list/
////////////////////////////////////////////////////////////////

///	Define the function to use for comparison and start the sort process
template<class T>
void CList<T>::MergeSort(bool(*_cmpFunc)(const T& _lhs, const T& _rhs))
{
	m_pComparisonFunction = _cmpFunc;
	SortList(&m_pHead, m_nSize);
}

///	Recursively sorts and merges the sub-lists
template<class T>
void CList<T>::SortList(TNode** _pHeadList, int _nSize)
{
	TNode* pHead = *_pHeadList, *_pFirst, *_pSecond;

	/*Special case: Empty or end*/
	if (!pHead || !pHead->m_pNext)
		return;

	///	Split the list in the middle
	_nSize /= 2;
	SplitList(pHead, &_pFirst, &_pSecond, _nSize);

	///	Recurse sorting both halves
	SortList(&_pFirst, _nSize);
	SortList(&_pSecond, _nSize);

	*_pHeadList = MergeSubLists(_pFirst, _pSecond);

}

///	Helper to divide the list in two
template<class T>
void CList<T>::SplitList(TNode* _pHead, TNode** _frontList, TNode** _backList, int _nSize)
{
	///	Front list is always at the front
	*_frontList = *_backList = _pHead;

	/*Special case: Empty or end*/
	if (!_pHead || !_pHead->m_pNext)
		*_backList = nullptr;

	///	Divide the list based on the size parameter
	else
	{

		TNode* pTempNode = *_backList;
		for (int iter = 0; iter < _nSize - 1 && pTempNode->m_pNext != nullptr; iter++)
		{
			pTempNode = pTempNode->m_pNext;
		}

		*_backList = pTempNode->m_pNext;
		pTempNode->m_pNext = nullptr;
	}
}

///	Compares the values. Does the actual sorting of the lists.
template<class T>
typename CList<T>::TNode* CList<T>::MergeSubLists(TNode* _frontList, TNode* _backList)
{
	TNode* pFinal = nullptr;

	/*Special cases*/
	if (!_frontList)
		return _backList;
	else if (!_backList)
		return _frontList;

	///	Compare and merge
	if (m_pComparisonFunction(_frontList->m_data, _backList->m_data))
	{
		pFinal = _frontList;
		pFinal->m_pNext = MergeSubLists(_frontList->m_pNext, _backList);
	}
	else
	{
		pFinal = _backList;
		pFinal->m_pNext = MergeSubLists(_backList->m_pNext, _frontList);
	}

	return pFinal;
}