#pragma once

#include "windows.h"

#define FOREACH(el,list,type) for(ListElement<type>* el=(list).GetHead();el;el=el->GetNext())

template <class T> class LList;

template <class T>
class ListElement
{
	friend LList<T>;

protected:
	ListElement<T> *m_pNext,*m_pPrev;
	T		*m_pInfo;
	unsigned   m_ID;
	LList<T>*m_pList;

public:
	void SetNext(ListElement<T>* const n)
	{
		m_pNext=n;
	}

	ListElement<T>* GetNext(void) const
	{
		return m_pNext;
	}

	void SetPrev(ListElement<T>* const p)
	{
		m_pPrev=p;
	}

	ListElement<T>* GetPrev(void) const
	{
		return m_pPrev;
	}

	ListElement(T* const info, const unsigned id)
	{
		m_pInfo = info;
		m_ID = id;
		m_pNext = NULL;
		m_pPrev = NULL;
		m_pList = NULL;
	}

	~ListElement(void)
	{
	}

	T* GetInfo(void) const
	{
		return m_pInfo;
	}

	void Unlink(void)
	{
		if(m_pList)
		{
			if(m_pPrev)
				m_pPrev->m_pNext = m_pNext;
			else
				m_pList->m_pHead = m_pNext;
			if(m_pNext)
				m_pNext->m_pPrev = m_pPrev;
			else
				m_pList->m_pTail = m_pPrev;

			m_pList->m_ElementCount--;
			m_pList = NULL;
			m_pNext = NULL;
			m_pPrev = NULL;
		}
	}

	void Delete(void)
	{
		Unlink();
		if(m_pInfo)
			delete m_pInfo;
		delete this;
	}

	unsigned GetID(void) const
	{
 		return m_ID;
	}

	void SetID(const unsigned id)
	{
		m_ID = id;
	}

	void SetInfo(T* const info)
	{
		m_pInfo = info;
	}

	LList<T>* GetList(void) const
	{
		return m_pList;
	}

	ListElement<T>* operator[](int index)
	{
		ListElement<T>* ptr = this;

		for(index;index&&ptr;index--)
			ptr = ptr->m_pNext;

		return ptr; 
	}
};

template <class T>
class LList
{ 
	friend ListElement<T>;
protected:

	ListElement<T> *m_pHead,*m_pTail;
	unsigned		m_ElementCount;

public:

	void Release(void)
	{
		ListElement<T> *p,*p2;

		p = m_pHead;
		while(p)
		{
			p2 = p;
			p = p->m_pNext;
			delete p2;
		}
		
		ZeroMemory(this,sizeof(LList));
	}

	void Clear(void)
	{
		ListElement<T> *p,*p2;

		p = m_pHead;

		//invalidate list immediately, eg some ressource might try to do something with this list
		ZeroMemory(this, sizeof(LList));

		while(p)
		{
			p2 = p;
			p = p->m_pNext;
			delete p2->m_pInfo;
			delete p2;
		}
	}

	LList(void)
	{
		ZeroMemory(this,sizeof(LList));
	}

	~LList(void)
	{
		Release();
	}
	
	void CopyDataFrom(const LList<T>&l)
	{
		Release();
		for(ListElement<T>*el=l.m_pHead;el;el=el->GetNext())
			AddTail(new T(*el->GetInfo()),el->GetID());
	}

	const void CopyPointersFrom(const LList<T>&l)
	{
		Release();
		for(ListElement<T>*el=l.m_pHead;el;el=el->GetNext())
			AddTail(el->GetInfo(),el->GetID());
	}

	/*LList(LList<T>&l)
	{
		ZeroMemory(this,sizeof(LList));
		
		for(ListElement<T>*el=l.GetHead();el;el=el->GetNext())
		{
			AddTail(new ListElement<T>(new T(*el->GetInfo()),el->GetID()));
		}
	}

	void operator =(LList&l)
	{
		Release();

		for(ListElement<T>*el=l.GetHead();el;el=el->GetNext())
		{
			AddTail(new ListElement<T>(new T(*el->GetInfo()),el->GetID()));
		}
	}*/

	void AddHead(T* const info,const unsigned id)
	{
		AddHead(new ListElement<T>(info,id));
	}

	void AddTail(T* const info,const unsigned id)
	{
		AddTail(new ListElement<T>(info,id));
	}

	void AddHead(ListElement<T>* const el)
	{
		if(el->m_pList)
			el->Unlink();

		el->m_pList = this;
		el->m_pNext = m_pHead;
		el->m_pPrev = NULL;

		if(m_pHead)
			m_pHead->m_pPrev = el;
		else
			m_pTail = el;

        m_pHead = el;

		m_ElementCount++;
	}

	void AddTail(ListElement<T>* const el)
	{
		if(el->m_pList)
			el->Unlink();

		el->m_pList = this;
		el->m_pNext = NULL;
		el->m_pPrev = m_pTail;

		if(m_pTail)
			m_pTail->m_pNext = el;
		else
			m_pHead = el;

        m_pTail = el;

		m_ElementCount++;
	}

	ListElement<T>* GetHead(void) const
	{
		return m_pHead;
	}

	ListElement<T>* GetTail(void) const
	{
		return m_pTail;
	}

	unsigned GetElementCount(void) const
	{
		return m_ElementCount;
	}

	ListElement<T>* GetN(int index) const
	{
		ListElement<T> *ptr = m_pHead;

		for(index;index&&ptr;index--)
			ptr = ptr->m_pNext;

		return ptr;
	}

	ListElement<T>* operator[](int index) const
	{
		return GetN(index); 
	}

	int GetIndexOf(const T* const obj) const
	{
		ListElement<T>	*el = m_pHead;
		int n=0;
		while(el)
		{
			if(el->GetInfo() == obj)
				return n;
			n++;
			el=el->m_pNext;
		}
		return -1;
	}

	int GetIndexOf(const unsigned id) const
	{
		ListElement<T>	*el = m_pHead;
		int n=0;
		while(el)
		{
			if(el->GetID()==id)
				return n;
			n++;
			el=el->m_pNext;
		}
		return -1;
	}

	bool Contains(const unsigned id) const
	{
		return (GetElement(id) != NULL);
	}

	bool Contains(const T* const el) const
	{
		return (GetElement(el) != NULL);
	}

	ListElement<T>* GetElement(const unsigned id) const
	{
		ListElement<T>	*el = m_pHead;

		while(el)
		{
			if(el->m_ID==id)
				break;
			el = el->m_pNext;
		}
		return el;
	}

	ListElement<T>* GetElement(const T* const ptr) const
	{
		ListElement<T>	*el = m_pHead;

		while(el)
		{
			if(el->m_pInfo == ptr)
				break;
			el = el->m_pNext;
		}
		return el;
	}

	ListElement<T>* GetElementOf(ListElement<T>* el, const unsigned id) const
	{
		el = el->GetNext();
		while(el)
		{
			if(el->m_ID==id)
				break;
			el = el->m_pNext;
		}
		return el;
	}

	void DeleteElement(const T* info)
	{
		ListElement<T> *h = GetElement(info);
		if(h)
			h->Delete();
	}

	void DeleteElement(const unsigned id)
	{
		ListElement<T> *h = GetElement(id);
		if(h)
			h->Delete();
	}

	void DeleteByIndex(const unsigned index)
	{
		ListElement<T> *h = GetN(index);
		if(h)
			h->Delete();
	}

	void ReleaseElement(const T* info)
	{
		ListElement<T> *h = GetElement(info);
		if(h)
		{
			h->Unlink();
			delete h;
		}
	}

	void ReleaseElement(const unsigned id)
	{
		ListElement<T> *h = GetElement(id);
		if(h)
		{
			h->Unlink();
			delete h;
		}
	}

	void AddAfter(ListElement<T>* const el,ListElement<T>* const eltoadd)
	{
		if(el->m_pList == this)
		{
			if(eltoadd->m_pList)
				eltoadd->Unlink();

			eltoadd->m_pList = this;
			eltoadd->m_pNext = el->m_pNext;
			eltoadd->m_pPrev = el;

			if(el->m_pNext)
				el->m_pNext->m_pPrev = eltoadd;
			else
				m_pTail = eltoadd;

			el->m_pNext = eltoadd;

			m_ElementCount++;
		}
	}

	void AddBefore(ListElement<T> *el,ListElement<T> *eltoadd)
	{
		if(el->m_pList == this)
		{
			if(eltoadd->m_pList)
				eltoadd->Unlink();

			eltoadd->m_pList = this;
			eltoadd->m_pPrev = el->m_pPrev;
			eltoadd->m_pNext = el;

			if(el->m_pPrev)
				el->m_pPrev->m_pNext = eltoadd;
			else
				m_pHead = eltoadd;

			el->m_pPrev = eltoadd;

			m_ElementCount++;
		}
	}

	void AddSortedByID(T*info,unsigned id,bool asc)
	{
		AddSortedByID(new ListElement<T>(info,id), asc);

		/*ListElement<T>	*el=m_pHead;

		if(asc)
		{
			while(el && el->m_ID < id)
				el = el->m_pNext;

			if(el)
				AddBefore(el,new ListElement<T>(info,id));
			else
				AddTail(info,id);
		}
		else
		{
			while(el && el->m_ID > id)
				el = el->m_pNext;

			if(el)
				AddAfter(el,new ListElement<T>(info,id));
			else
				AddTail(info,id);
		}*/
	}

	void AddSortedByID(ListElement<T>*eltoinsert, bool asc)
	{
		ListElement<T>	*el=m_pHead;
		unsigned id = eltoinsert->GetID();

		if(asc)
		{
			while(el && el->m_ID < id)
				el = el->m_pNext;

			if(el)
				AddBefore(el,eltoinsert);
			else
				AddTail(eltoinsert);
		}
		else
		{
			while(el && el->m_ID > id)
				el = el->m_pNext;

			if(el)
				AddAfter(el,eltoinsert);
			else
				AddTail(eltoinsert);
		}
	}

	/*inline void AddSorted(T*info,unsigned id,bool(*cmp)(T*a,T*b))
	{
		AddSorted(new ListElement<T>(this,info,id),cmp);
	}

	void AddSorted(ListElement<T>*el,bool(*cmpgreater)(T*a,T*b))
	{
		ListElement<T>*p=head;
		while(p=getnext(p))
		{
			if(!(*cmpgreater)(el->GetInfo(),p->GetInfo()))
				break;
		}
		if(p)
		{
			AddBefore(p,el);
		}
		else
		{
			add(el);
		}
	}*/

	void Sort(bool(*cmpless)(T*a,T*b),bool(*cmpgreater)(T*a,T*b)) //its a simple bubblesort
	{
		if(m_ElementCount > 1)
			QuickSort(m_pHead,m_pTail,m_ElementCount,cmpless,cmpgreater);
	}

	void SortByID(bool asc)
	{
		if(m_ElementCount > 1)
		{
			AddHead(NULL,0);
			AddTail(NULL,0);
			QuickSortByID(m_pHead->GetNext(),m_pTail->GetPrev(),m_ElementCount-2,asc);
			m_pHead->Delete();
			m_pTail->Delete();
		}
	}
private :
	void QuickSort(ListElement<T>*s,ListElement<T>*e,unsigned n,bool(*cmpless)(T*a,T*b),bool(*cmpgreater)(T*a,T*b))
	{			
		ListElement<T> *mid = (*s)[n/2];
		ListElement<T> *i = s, *hi;
		
		s = s->m_pPrev;
		e = e->m_pNext;

		unsigned nl = n>>1;
		unsigned nh = n - (n>>1);

        while (i != mid)
        {    
            while (cmpless(i->m_pInfo,mid->m_pInfo)) i = i->m_pNext; 

			if(i != mid)
            {
				hi = i->m_pNext;

				i->Unlink();
				//i->prev->m_pNext = i->m_pNext;
				//i->m_pNext->prev = i->prev;

				AddAfter(mid,i);
				//i->m_pNext = mid->m_pNext;
				//i->prev = mid;
				//mid->m_pNext->prev = i;
				//mid->m_pNext = i;

				i = hi;
				
				nh++;
				nl--;
            }
		}

		ListElement<T> *j = e->m_pPrev, *hj;

		while (j != mid)
		{
            while (cmpgreater(j->m_pInfo,mid->m_pInfo)) j = j->m_pPrev;
            
			if(j != mid)
            {
				hj = j->m_pPrev;

				j->Unlink();
				//j->prev->next = j->next;
				//j->next->prev = j->prev;

				AddBefore(mid,j);
				//j->next = mid;
				//j->prev = mid->prev;
				//mid->prev->next = j;
				//mid->prev = j;

				j = hj;

				nh--;
				nl++;
            }
        }

        if (nl > 1) QuickSort(s->m_pNext,mid->m_pPrev,nl,cmpless,cmpgreater);
        if (nh > 1) QuickSort(mid,e->m_pPrev,nh,cmpless,cmpgreater);

	}

	void QuickSortByID(ListElement<T>*s,ListElement<T>*e,unsigned n,bool asc)
	{			
		ListElement<T> *mid = (*s)[n/2];
		ListElement<T> *i = s, *hi;
		
		s = s->m_pPrev;
		e = e->m_pNext;

		unsigned nl = n>>1;
		unsigned nh = n - (n>>1);

        while (i != mid)
        {    
			if(asc)
			{
				while (i->m_ID < mid->m_ID) i = i->m_pNext; 
			}
			else
			{
				while (i->m_ID > mid->m_ID) i = i->m_pNext; 
			}

			if(i != mid)
            {
				hi = i->m_pNext;

				//i->Unlink();
				i->m_pPrev->m_pNext = i->m_pNext;
				i->m_pNext->m_pPrev = i->m_pPrev;

				//AddAfter(mid,i);
				i->m_pNext = mid->m_pNext;
				i->m_pPrev = mid;
				mid->m_pNext->m_pPrev = i;
				mid->m_pNext = i;

				i = hi;
				
				nh++;
				nl--;
            }
		}

		ListElement<T> *j = e->m_pPrev, *hj;

		while (j != mid)
		{
			if(asc)
			{
				while (j->m_ID > mid->m_ID) j = j->m_pPrev; 
			}
			else
			{
				while (j->m_ID < mid->m_ID) j = j->m_pPrev; 
			}
            
			if(j != mid)
            {
				hj = j->m_pPrev;

				//j->Unlink();
				j->m_pPrev->m_pNext = j->m_pNext;
				j->m_pNext->m_pPrev = j->m_pPrev;

				//AddBefore(mid,j);
				j->m_pNext = mid;
				j->m_pPrev = mid->m_pPrev;
				mid->m_pPrev->m_pNext = j;
				mid->m_pPrev = j;

				j = hj;

				nh--;
				nl++;
            }
        }

        if (nl > 1) QuickSortByID(s->m_pNext,mid->m_pPrev,nl,asc);
        if (nh > 1) QuickSortByID(mid,e->m_pPrev,nh,asc);

	}
};