#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <crtdbg.h>
#include <string>
#include "List.h"

using namespace std;

void IntegerTest()
{
	List<int>	IntegerList;

	IntegerList.PushBack(1);
	IntegerList.PushBack(3);
	IntegerList.PushBack(5);
	IntegerList.PushBack(6);

	IntegerList.Unsafe_Show();

	IntegerList.PushFront(10);
	IntegerList.PushFront(20);
	IntegerList.PushFront(40);
	IntegerList.PushFront(90);

	IntegerList.Unsafe_Show();

	List<int>::iterator Remove = IntegerList.Remove(40);
	delete Remove; Remove = NULL;
	Remove = IntegerList.Remove(5);
	delete Remove; Remove = NULL;

	IntegerList.Unsafe_Show();

	ListWipe(IntegerList);

	//IntegerList.Clear();
}

bool CompareString( const string& A, const string& B )
{
	return !A.compare(B);
}

void StringTest()
{
	List<string>	StringList;
	StringList.PushBack("Hello World");
	StringList.PushBack("Mo18");
	StringList.PushBack("Kekeke");

	List<string>::iterator it = StringList.Remove("Mo18",CompareString);
	if(it)
		delete it;

	StringList.Unsafe_Show();
	
	ListWipe(StringList);

	//StringList.Clear();
}

int main(void)
{
	//_CrtSetBreakAlloc(130);
	IntegerTest();
	StringTest();

	_CrtDumpMemoryLeaks();

	getchar();

	return 0;
}

template<class Type>
class List
{
public:
	struct Node
	{
		Type	Data;
		Node*	Next;
		Node*	Prev;
	};
	typedef Node* iterator;
protected:

	Node *Head;
	Node *Tail;
	int  Size;

	void _Init()
	{
		Head = new Node;
		Tail = new Node;
		Head->Prev = Tail;	Head->Next = Tail;
		Tail->Next = Head;	Tail->Prev = Head;
		Size = 0;
	}

public:
	List()
	{
		_Init();
	}

	Node* Begin()
	{
		return Head->Next;
	}

	Node* End()
	{
		return Tail;
	}

	void Clear()
	{
		if(Head) delete Head; Head = NULL;
		if(Tail) delete Tail; Tail = NULL;
		Size = 0;
	}

	void PushBack(Type InValue)
	{
		if(!Head || !Tail)
			_Init();

		Node * NewNode = new Node;
		NewNode->Data = InValue;
		Node * PrevNode = Tail->Prev;
		PrevNode->Next = NewNode;
		Tail->Prev = NewNode;
		NewNode->Prev = PrevNode;
		NewNode->Next = Tail;

		++Size;
	}

	void PushFront(Type InValue)
	{
		if(!Head || !Tail)
			_Init();

		Node * NewNode = new Node;
		NewNode->Data = InValue;
		Node * NextNode = Head->Next;
		Head->Next = NewNode;
		NextNode->Prev = NewNode;
		NewNode->Prev = Head;
		NewNode->Next = NextNode;

		++Size;
	}

	Node* Remove(Type InValue, bool (*ComparisonFn)(const Type & A, const Type & B) = NULL)
	{
		Node * Itor = Head;
		bool bResult = false;

		while( Itor != NULL )
		{
			if( ComparisonFn != NULL )
			{
				bResult = ComparisonFn(Itor->Data, InValue);
			}
			else
			{
				bResult = ( Itor->Data == InValue ) ? true : false;
			}

			if(true == bResult)
			{
				Node * TPrev = Itor->Prev;
				Node * TNext = Itor->Next;
				TPrev->Next = TNext;
				TNext->Prev = TPrev;

				--Size;

				return Itor;
			}

			Itor = Itor->Next;
		}

		return NULL;
	}

	void Unsafe_Show()
	{
#ifdef _DEBUG
		Node * Itor = Begin();

		std::cout << "------------------------------------" << std::endl;
		while(Itor != End())
		{
			std::cout << Itor->Data << std::endl;
			Itor = Itor->Next;
		}
#endif
	}
};

template<class Type>
void ListWipe( List<Type>& Cont )
{
	List<Type>::iterator Itor = Cont.Begin();
	List<Type>::Node * Remove = NULL;

	while(Itor != Cont.End())
	{
		//cout << "Deleting... " << Itor->Data << endl;

		Remove = Cont.Remove(Itor->Data);
		Itor = Remove->Next;
		delete Remove;
	}

	Cont.Clear();
}