///////////////////////////////////////////////////////////////////////////////
/// @file deList.hpp
///
/// @brief Templated linked list class
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Sept 2001
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DELIST_HPP
#define DELIST_HPP

#include "deGlobalTypes.hpp"

#ifndef NULL
#define NULL (0)
#endif

#pragma warning (disable : 4284) // return type for 'identifier::operator ->' is not a UDT or reference to a UDT. Will produce errors if applied using infix notation

/// templated linked-list storage class
template <class T>
class deTList
{
private:
	class TListNode
	{
	public:
		TListNode()
			:Next(NULL), Prev(NULL)
			{
			#ifdef _DEBUG
			List = NULL;
			#endif
			}
		TListNode(const T & ref)
			:Data(ref), Next(NULL), Prev(NULL)
			{
			#ifdef _DEBUG
			List = NULL;
			#endif
			}
		TListNode(const TListNode & ref)
			:Data(ref.Data), Next(NULL), Prev(NULL)
			{
			#ifdef _DEBUG
			List = NULL;
			#endif
			}
		virtual ~TListNode()
			{}

		TListNode *Next, *Prev;
		#ifdef _DEBUG
		deTList * List;
		#endif
		T Data;
	};

public:
	class iterator
	{
	private:
		friend class deTList<T>;
		TListNode* m_Node;
	protected:
		iterator(TListNode* node) : m_Node(node) {}
	public:
		iterator() : m_Node(0) {}
		~iterator() {}
		T& operator*() const
		{
			DE_ASSERT (m_Node != 0);
			return m_Node->Data;
		}
		T* operator->() const { return &operator*(); }
		void operator++() { m_Node = m_Node->Next; }
		void operator--() { m_Node = m_Node->Prev; }
		bool operator==(const iterator & other) const
			{ return m_Node == other.m_Node; }
		bool operator!=(const iterator & other) const
			{ return m_Node != other.m_Node; }
	};

private:
	TListNode *m_Front, *m_Back;
	long m_Length;

public:
	deTList()
	{
		m_Front = NULL;
		m_Back = NULL;
		m_Length = 0;
	}
	deTList(const deTList <T> & ref)
	{
		TListNode *Node = ref.m_Front, *NewNode = NULL, *tempnode = NULL;
		m_Front = NULL;
		m_Back = NULL;
		m_Length = 0;

		if (Node)
		{
			NewNode = new TListNode(Node->Data);
			#ifdef _DEBUG
			NewNode->List = this;
			#endif
			m_Front = NewNode;
			tempnode = NewNode;
			Node = Node->Next;
		}
		while(Node)
		{
			NewNode = new TListNode(Node->Data);
			#ifdef _DEBUG
			NewNode->List = this;
			#endif
			NewNode->Prev = tempnode;
			tempnode = NewNode;
			Node = Node->Next;
		}
		m_Back = NewNode;
		m_Length = ref.m_Length;
	}
	const deTList <T> & operator=(const deTList <T> & ref)
	{
		TListNode *Node = ref.m_Front, *NewNode = NULL, *tempnode = NULL;
		EmptyList();

		if (Node)
		{
			NewNode = new TListNode(Node->Data);
			#ifdef _DEBUG
			NewNode->List = this;
			#endif
			m_Front = NewNode;
			tempnode = NewNode;
			Node = Node->Next;
		}
		while(Node)
		{
			NewNode = new TListNode(Node->Data);
			#ifdef _DEBUG
			NewNode->List = this;
			#endif
			NewNode->Prev = tempnode;
			if (tempnode)
				tempnode->Next = NewNode;
			tempnode = NewNode;
			Node = Node->Next;
		}
		m_Back = NewNode;
		m_Length = ref.m_Length;

		return *this;
	}
	~deTList()
	{
		EmptyList();
	}

	void EmptyList()
	{
		TListNode *ptr1, *ptr2;
		ptr1 = m_Front;
		while(ptr1 != NULL)
		{
			ptr2 = ptr1->Next;
			delete ptr1;
			ptr1 = ptr2;
		}
		m_Front = m_Back = NULL;
		m_Length = 0;
	}
	void* FindData(void* current, T & data) const
	{
		void* ptr = current;
		T* temp;
		if (ptr)
			GetData(ptr, temp);
		else
			ptr = GetNext(NULL, temp);
		while( ptr && !(*temp == data))
		{
			ptr = GetNext(ptr, temp);
		}
		return ptr;
	}
	void* GetNext(void* current, T * & ptr) const
	{
		TListNode *Node = (TListNode*)current;
		if (Node)
		{
			if (Node->Next)
				Node = Node->Next;
			else
			{
				ptr = NULL;
				return NULL;
			}
		}
		else
		{
			if (m_Front)
				Node = m_Front;
			else
			{
				ptr = NULL;
				return NULL;
			}
		}
		ptr = &(Node->Data);
		return Node;
	}
	void* GetNext(void* current, T & obj) const
	{
		T * objptr;
		void * ptr;
		ptr = GetNext(current, objptr);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void* GetPrev(void* current, T * & ptr) const
	{
		TListNode *Node = (TListNode*)current;
		if (Node)
		{
			if (Node->Prev)
				Node = Node->Prev;
			else
			{
				ptr = NULL;
				return NULL;
			}
		}
		else
		{
			if (m_Back)
				Node = m_Back;
			else
			{
				ptr = NULL;
				return NULL;
			}
		}
		ptr = &(Node->Data);
		return Node;
	}
	void* GetPrev(void* current, T & obj) const
	{
		T * objptr;
		void * ptr;
		ptr = GetPrev(current, objptr);
		if (objptr)
			obj = *objptr;
		return ptr;
	}
	void GetData(void * current, T & obj) const
	{
		const TListNode *Node = (const TListNode*)current;
		if (Node)
			obj = (Node->Data);
	}
	void GetData(void * current, const T* & obj) const
	{
		const TListNode *Node = (const TListNode*)current;
		if (Node)
			obj = &(Node->Data);
	}
	void* AddElementNoData()
	{
		TListNode * Node = new TListNode();
		if (!Node)
			return NULL;
		#ifdef _DEBUG
		Node->List = this;
		#endif
		m_Length++;
		if (m_Front == NULL)
			m_Front = Node;
		if (m_Back)
			m_Back->Next = Node;
		Node->Prev = m_Back;
		m_Back = Node;
		
		return Node;
	}
	void* AddElement(const T & data)
	{
		TListNode * Node = new TListNode(data);
		if (!Node)
			return NULL;
		#ifdef _DEBUG
		Node->List = this;
		#endif
		m_Length++;
		if (m_Front == NULL)
			m_Front = Node;
		if (m_Back)
			m_Back->Next = Node;
		Node->Prev = m_Back;
		m_Back = Node;

		return Node;
	}
	void* AddElementBefore(const T & data, void * current)
	{
		TListNode * Node = (TListNode*)current;
		if (!Node)
		{
			Node = m_Front;
			if (!Node)
			{
				return AddElement(data);
			}
		}
		TListNode * NewNode = new TListNode(data);
		if (!NewNode)
			return NULL;
		#ifdef _DEBUG
		NewNode->List = this;
		#endif
		m_Length++;
		NewNode->Prev = Node->Prev;
		NewNode->Next = Node;
		if (Node->Prev)
			Node->Prev->Next = NewNode;
		else
			m_Front = NewNode;
		Node->Prev = NewNode;
		
		return NewNode;
	}
	void* AddElementAfter(const T & data, void * current)
	{
		TListNode * Node = (TListNode*)current;
		if (!Node)
		{
			Node = m_Back;
			if (!Node)
			{
				return AddElement(data);
			}
		}
		TListNode * NewNode = new TListNode(data);
		if (!NewNode)
			return NULL;
		#ifdef _DEBUG
		NewNode->List = this;
		#endif
		m_Length++;
		NewNode->Next = Node->Next;
		NewNode->Prev = Node;
		if (Node->Next)
			Node->Next->Prev = NewNode;
		else
			m_Back = NewNode;
		Node->Next = NewNode;
		
		return NewNode;
	}
	void AppendList(const deTList <T> & list)
	{
		TListNode *Node, *NodeCopy=NULL;
		Node = list.m_Front;
		while (Node != NULL)
		{
			NodeCopy = new TListNode(Node->Data);
			#ifdef _DEBUG
			NodeCopy->List = this;
			#endif
			if (!m_Back)
			{
				m_Back = NodeCopy;
				m_Front = NodeCopy;
			}
			else
			{
				m_Back->Next = NodeCopy;
				NodeCopy->Prev = m_Back;
				//NodeCopy->Next = NULL;
				m_Back = NodeCopy;
			}
			Node = Node->Next;
		}
		if (NodeCopy)
			NodeCopy->Next = NULL;
		m_Length += list.m_Length;
	}
	void MergeList(deTList <T> & list)
	{
		TListNode *Node;
		Node = list.m_Front;
		if (!m_Back)
		{
			m_Back = Node;
			m_Front = Node;
		}
		else
		{
			m_Back->Next = Node;
			Node->Prev = m_Back;
			m_Back = Node;
		}
		#ifdef _DEBUG
		while (Node != NULL)
		{
			Node->List = this;
			Node = Node->Next;
		}
		#endif
		m_Length += list.m_Length;
		list.m_Length = 0;
		list.m_Front = list.m_Back = NULL;
	}
	#ifdef _DEBUG
	static void StaticRemoveElement(void * ptr)
	{
		TListNode * Node = (TListNode*)ptr;
		if (Node->List)
			Node->List->RemoveElement(ptr);
	}
	#endif
	deBoolean RemoveElement(void * ptr)
	{
		TListNode * Node = (TListNode*)ptr;
		if (Node == NULL)
			return deTRUE;
		#ifdef _DEBUG
		if (Node->List != this)
			return deFALSE;
		#endif
		m_Length--;
		if (Node->Prev)
			Node->Prev->Next = Node->Next;
		if (Node->Next)
			Node->Next->Prev = Node->Prev;
		if (m_Front == Node)
			m_Front = Node->Next;
		if (m_Back == Node)
			m_Back = Node->Prev;
		Node->Next = NULL;
		Node->Prev = NULL;
		#ifdef _DEBUG
		Node->List = NULL;
		#endif
		delete Node;
		return deTRUE;
	}
	inline void * RemoveElementGetNext(void* current, T * & ptr)
	{
		void * ret;
		ret = GetNext(current, ptr);
		RemoveElement(current);
		return ret;
	}

	inline long Length() const	{ return m_Length; }
	inline long size() const	{ return m_Length; }

	// iterator stuff
	iterator push_back(const T & data)
	{
		TListNode * Node = (TListNode*)AddElement(data);
		return iterator(Node);
	}
	iterator push_back()
	{
		TListNode * Node = (TListNode*)AddElementNoData();
		return iterator(Node);
	}

	inline iterator begin() { return iterator(m_Front); }
	inline iterator end()   { return iterator(0); }

	inline iterator erase(iterator& it)
	{
		iterator next = it;
		++next;
		RemoveElement(it.m_Node);
		return next;
	}
};


//#pragma warning (default : 4710)

#endif
