///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Contains a linked list.
 *	\file		IceLinkedList.h
 *	\author		Pierre Terdiman
 *	\date		April, 4, 2000
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Include Guard
#ifndef __ICELINKEDLIST_H__
#define __ICELINKEDLIST_H__

	class ICECORE_API ListElem
	{
		public:
		// Constructor / Destructor
										ListElem()		{ mNext = mPrev = null; }
		virtual							~ListElem()		{}

						ListElem*		mNext;			// Next element of list
						ListElem*		mPrev;			// Previous element of list
	};

	class ICECORE_API LinkedList
	{
		public:
		// Constructor / Destructor
										LinkedList()	{ mHead = mTail = null; mNb = 0; }
										~LinkedList()	{}

		// Add an element to the list
		__forceinline	void			AddElem(ListElem* le)
						{
							ListElem*	prev = mTail;
							mTail=le;

							if(prev)
							{
								mTail->mPrev = prev;
								mTail->mNext = null;
								prev->mNext = mTail;
							}
							else
							{
								mTail->mPrev = null;
								mTail->mNext = null;
								mHead = mTail;
							}
							mNb++;
						}

		// Add an element before
		__forceinline	void			AddBefore(ListElem* le, ListElem* el)
						{
							// add le before element el
							if(el)
							{
								if(el==mHead)	AddAfter(le, null);	// add at the head
								else
								{
									le->mPrev = el->mPrev;
									el->mPrev = le;
									le->mPrev->mNext = le;
									le->mNext = el;
									mNb++;
								}
							}
							else AddElem(le); // adding before NULL means adding add the end
						}

		// Another element in the list
		// Add an element after
		__forceinline	void			AddAfter(ListElem* le, ListElem* el)
						{
							// add le after element el
							if(el)
							{
								if(el==mTail)	AddElem(le);	// add at the tail
								else
								{
									le->mNext = el->mNext;
									el->mNext = le;
									le->mNext->mPrev = le;
									le->mPrev = el;
									mNb++;
								}
							}
							else
							{
								// adding after NULL means adding add the head
								le->mPrev = null;
								le->mNext = mHead;
								if(mHead)
								{
									mHead->mPrev = le;
									mHead = le;
								}
								else mHead = mTail = le;

								mNb++;
							}
						}

		// Another element in the list

		// Remove list element (not deleted)
		__forceinline	void			RemElem(ListElem* le)
						{
							if( (mHead == le) && (mTail == le))
							{
								mHead = null;
								mTail = null;
							}
							else
							{
								if(mHead==le)
								{
									mHead = mHead->mNext;
									if(mHead) mHead->mPrev = null;
								}
								else
								{
									if(mTail==le)
									{
										if(mTail->mPrev)	mTail->mPrev->mNext = null;
										mTail = mTail->mPrev;
									}
									else
									{
										le->mPrev->mNext = le->mNext;
										if(le->mNext)	le->mNext->mPrev = le->mPrev;
									}
								}
							}
							mNb--;
							// maybe delete le?
						}

		// remove all list elements
		__forceinline	void			RemAll()
						{
							while(mHead)	RemElem(mHead);
							mNb = 0;
						}

		// delete all list elements
		__forceinline	void			DeleteAll()
						{
							ListElem *tmp2,*tmp = mHead;
							while(tmp)
							{
								tmp2 = tmp->mNext;
								delete tmp;
								tmp = tmp2;
							}
							mHead = mTail = null;
							mNb = 0;
						}

		// Return the length of the list
		__forceinline	udword			Length()		{ return mNb; }

		// Get first list element
		__forceinline	ListElem*		GetFirst()		{ return mHead; }

		// Get next list element
		__forceinline	ListElem*		GetNext(ListElem* le)
						{
							if(le) return le->mNext;
							else return mHead;
						};

		// Get last list element
		__forceinline	ListElem*		GetLast()		{ return mTail; }

		// Get previous list element
		__forceinline	ListElem*		GetPrev(ListElem* le)
						{
							if(le) return le->mPrev;
							else return mTail;
						};

		// Get a list element
		__forceinline	ListElem*		Element(udword i)
						{
							if(i<mNb)
							{
								udword Count=0;
								ListElem* le = mHead;
								while(Count<i)
								{
									le = le->mNext;
									Count++;
								};
								return le;
							}
							else return null;
						}

		private:
						ListElem*		mHead;			// Pointer to head of list
						ListElem*		mTail;			// Pointer to tail of list
						udword			mNb;			// Number of elements in the list
	}; 

#endif // __ICELINKEDLIST_H__
