tc3d_list.h

自己写的一些基本的3d引擎的基础的代码

/**
 * Comet 3D Engine file (c) 2007 - 2008 Tianjie Wei, THSystems Research Group
 *
 * Released under BSD license, please refer to license.txt for more information
 */

#ifndef _TC3D_LIST_H_
#define _TC3D_LIST_H_

#include "TC3D_Allocator.h"

namespace C3D
{
	namespace Util
	{
		/**
		 * Doubly linked list class
		 *
		 * @Author Tianjie (James) Wei
		 * @Version 3.0
		 */
		template < class T, class TAlloc = TC3D_Allocator<T> >
		class TC3D_List
		{
			private:

				/**
				 * List node structure
				 */
			    template < class U >
				struct SC3D_List_Node
				{
					SC3D_List_Node *pPrev;
					SC3D_List_Node *pNext;
					U tData;

					/** Default constructor */
					SC3D_List_Node()
					{
						pPrev = DC3D_NULL;
						pNext = DC3D_NULL;
					}

					/** Initializing constructor */
					SC3D_List_Node(const U &d)
					{
						pPrev = DC3D_NULL;
						pNext = DC3D_NULL;
						tData = d;
					}
				};

			private:

				SC3D_List_Node<T> *pFirst;
				SC3D_List_Node<T> *pLast;
				TAlloc tAllocator;
				TC3D_U32 tSize;
				TC3D_Bool tSorted;

			public:

				/**
				 * List iterator class
				 */
				class CC3D_Iterator
				{
					private:

						/** Grant linked list class private access */
						friend class TC3D_List<T, TAlloc>;

						/** Pointer to the current list item */
						SC3D_List_Node<T> *pData;

						/** Pointer to the linked list */
						TC3D_List<T, TAlloc> *pBase;
					
						/** Private constructor for container use only */
						CC3D_Iterator(SC3D_List_Node<T> *current, TC3D_List<T, TAlloc> *base)
						{
							pData = current;
							pBase = base;
						}

					public:

						/** Default constructor */
						CC3D_Iterator()
						{
							pData = DC3D_NULL;
							pBase = DC3D_NULL;
						}

						/** Copy constructor */
						CC3D_Iterator(const CC3D_Iterator &it)
						{
							pData = it.pData;
							pBase = it.pBase;
						}

						/** Assignment operator */
						CC3D_Iterator &operator = (const CC3D_Iterator &it) 
						{ 
							if(this != &it)
							{
								pData = it.pData;
								pBase = it.pBase;
							}
							return *this; 
						}

						/** Dereferencing operator */
						T &operator * () const
						{  
							MC3D_DEBUG_ASSERT(pData);
							return pData->tData;
						}

						/** Calling member function */
						T *operator -> () const
						{ 
							MC3D_DEBUG_ASSERT(pData);
							return &(pData->tData); 
						}

						/** Prefix increment opeartor */
						CC3D_Iterator &operator ++ ()
						{ 
							MC3D_DEBUG_ASSERT(pData);
							pData = pData->pNext; 
							return *this; 
						}

						/** Prefix decrement operator */
						CC3D_Iterator &operator -- ()	
						{ 
							if(!pData)
								pData = pBase->Last();
							else
							{
								MC3D_DEBUG_ASSERT(pData->pPrev);
								pData = pData->pPrev;
							}
							return *this; 
						}

						/** Postfix increment operator */
						CC3D_Iterator operator ++ (TC3D_S32 dummy)	
						{ 
							MC3D_DEBUG_ASSERT(pData);
							CC3D_Iterator temp(pData, pBase);
							pData = pData->pNext; 
							return temp;
						}

						/** Postfix decrement operator */
						CC3D_Iterator operator -- (TC3D_S32 dummy)	
						{
							CC3D_Iterator temp(pData, pBase);
							if(!pData)
								pData = pBase->Last();
							else
							{
								MC3D_DEBUG_ASSERT(pData->pPrev);
								pData = pData->pPrev;
							}
							return temp; 
						}

						/** Addition operator */
						CC3D_Iterator operator + (TC3D_S32 value) 
						{ 
							CC3D_Iterator temp(pData, pBase);
							if(value >= 0)
							{
								while(value--)
									++temp;
							}
							else
							{
								while(value++)
									--temp;
							}
							return temp;
						}

						/** Subtraction operator */
						CC3D_Iterator operator - (TC3D_S32 value) const
						{ 
							CC3D_Iterator temp(pData, pBase);
							temp += (-value);
							return temp;
						}

						/** Addition and assignment */
						CC3D_Iterator &operator += (TC3D_S32 value) 
						{ 
							if(value >= 0)
							{
								while(value--)
									++(*this);
							}
							else
							{
								while(value++)
									--(*this);
							}
							return *this; 
						}

						/** Subtraction and assignment */
						CC3D_Iterator &operator -= (TC3D_S32 value) const
						{ 
							*this += (-value);
							return *this; 
						}

						/** String iterator comparison */
						TC3D_Bool operator == (const CC3D_Iterator &it) const
						{ 
							return (pData == it.pData); 
						}

						/** String iterator comparison */
						TC3D_Bool operator != (const CC3D_Iterator &it) const
						{ 
							return (pData != it.pData); 
						}

						/** String iterator comparison */
						TC3D_Bool operator >= (const CC3D_Iterator &it) const
						{ 
							if(pData == it.pData)
								return DC3D_TRUE;

							if(!pData)
								return DC3D_TRUE;

							if(!it.pData)
								return DC3D_FALSE;

							return (pData > it.pData);
						}

						/** String iterator comparison */
						TC3D_Bool operator <= (const CC3D_Iterator &it) const
						{ 
							if(pData == it.pData)
								return DC3D_TRUE;

							if(!pData)
								return DC3D_FALSE;

							if(!it.pData)
								return DC3D_TRUE;

							return (pData < it.pData);
						}

						/** String iterator comparison */
						TC3D_Bool operator > (const CC3D_Iterator &it) const
						{ 
							if(pData == it.pData)
								return DC3D_FALSE;

							if(!pData)
								return DC3D_TRUE;

							if(!it.pData)
								return DC3D_FALSE;

							return (pData > it.pData);
						}

						/** String iterator comparison */
						TC3D_Bool operator < (const CC3D_Iterator &it) const
						{ 
							if(pData == it.pData)
								return DC3D_FALSE;

							if(!pData)
								return DC3D_FALSE;

							if(!it.pData)
								return DC3D_TRUE;

							return (pData < it.pData);
						}
				};

			private:

				/** Internal function for removing a node from the list */
				void Remove_Node(SC3D_List_Node<T> *node)
				{
					MC3D_DEBUG_ASSERT(node);

					if(pFirst == node)
						pFirst = node->pNext;
					if(pLast == node)
						pLast = node->pPrev;
					if(node->pNext)
						node->pNext->pPrev = node->pPrev;
					if(node->pPrev)
						node->pPrev->pNext = node->pNext;
				}

				/** Get the end of the list pointer */
				SC3D_List_Node<T> *Last() const
				{
					return pLast;
				}

			public:

				/** Default constructor */
				TC3D_List()
				{
					pFirst = DC3D_NULL;
					pLast = DC3D_NULL;
					tSize = 0;
					tSorted = DC3D_TRUE;
				}

				/** Copy constructor */
				TC3D_List(const TC3D_List<T> &src)
				{
					pFirst = DC3D_NULL;
					pLast = DC3D_NULL;
					tSize = src.tSize;
					tSorted = src.tSorted;

					SC3D_List_Node<T> *node;

					for(node = src.pFirst; node; node = node->pNext)
						Push_Back(node->tData);
				}

				/** Destructor */
				virtual ~TC3D_List()
				{
					Clear();
				}

				/**
				 * Push an element to the back of the linked list.
				 * Everytime you do a push, a new node is allocated.
				 * This function will attach the node to the end of
				 * the linked list.
				 *
				 * @param	item	item to push
				 * @return	none
				 */
				virtual void Push_Back(const T &item)
				{
					SC3D_List_Node<T> *node;
					
                    typename TAlloc::template Rebind< SC3D_List_Node<T> >::Other nodeAlloc(tAllocator);
                    node = (SC3D_List_Node<T> *)nodeAlloc.Allocate(1);
                    nodeAlloc.Construct(node, SC3D_List_Node<T>(item));
                    
					node->pPrev = pLast;

					if(pLast)
						pLast->pNext = node;

					node->pNext = DC3D_NULL;
					pLast = node;

					if(!pFirst)
						pFirst = pLast;

					tSorted = DC3D_FALSE;
					tSize++;
				}

				/**
				 * Push an element to the front of the linked
				 * list. Unless the array class, this function
				 * is equally efficient as Push_Back.
				 *
				 * @param	item	item to push
				 * @return	none
				 */
				virtual void Push_Front(const T &item)
				{
					SC3D_List_Node<T> *node;
					
			        typename TAlloc::template Rebind< SC3D_List_Node<T> >::Other nodeAlloc(tAllocator);
                    node = (SC3D_List_Node<T> *)nodeAlloc.Allocate(1);
                    nodeAlloc.Construct(node, SC3D_List_Node<T>(item));
					
					node->pNext = pFirst;

					if(pFirst)
						pFirst->pPrev = node;

					node->pPrev = DC3D_NULL;
					pFirst = node;

					if(!pLast)
						pLast = pFirst;

					tSorted = DC3D_FALSE;
					tSize++;
				}

                virtual T Pop_Back()
                {
                    MC3D_DEBUG_ASSERT(tSize);

                    T item;

                    item = pLast->tData;

                    Erase(End() - 1, End());

                    return item;
                }

                virtual T Pop_Front()
                {
                    MC3D_DEBUG_ASSERT(tSize);

                    T item;

                    item = pFirst->tData;

                    Erase(Begin(), Begin() + 1);

                    return item;
                }

				/** Inserts after an element */
				virtual void Insert(const CC3D_Iterator &it, const T &item)
				{
					SC3D_List_Node<T> *node;
					
				    typename TAlloc::template Rebind< SC3D_List_Node<T> >::Other nodeAlloc(tAllocator);
					node = (SC3D_List_Node<T> *)nodeAlloc.Allocate(1);
					nodeAlloc.Construct(node, SC3D_List_Node<T>(item));

					node->pNext = it.pData;

					if(it.pData)
					{
						node->pPrev = it.pData->pPrev;
						if(it.pData->pPrev)
							it.pData->pPrev->pNext = node;
						it.pData->pPrev = node;
					}
					tSorted = DC3D_FALSE;
					tSize++;
				}

				virtual void Erase(CC3D_Iterator &begin)
				{
					Erase(begin, begin + 1);
				}

				virtual void Erase(const CC3D_Iterator &begin, const CC3D_Iterator &end)
				{
					SC3D_List_Node<T> *node;
					SC3D_List_Node<T> *nodeNext;
					
					typename TAlloc::template Rebind< SC3D_List_Node<T> >::Other nodeAlloc(tAllocator);
                    
					TC3D_U32 i;
					for(node = begin.pData, i = 0; node != end.pData; node = nodeNext)
					{
						nodeNext = node->pNext;
						Remove_Node(node);
						nodeAlloc.Destruct(node);
						nodeAlloc.Deallocate(node);
						i++;
					}
					tSize -= i;
				}

				/**
				 * Clear add deallocate the entire linked list,
				 * this function will free up the memory occupied
				 * by the linked list nodes.
				 *
				 * @param	none
				 * @return	none
				 */
				virtual void Clear()
				{
					
					Erase(Begin(), End());

					pFirst = DC3D_NULL;
					pLast = DC3D_NULL;
					tSize = 0;
					tSorted = DC3D_TRUE;
				}

				virtual void Sort()
				{
				}

				/** Find an item with linear search */
				CC3D_Iterator Find(const T &item) const 
				{
					SC3D_List_Node<T> *node;

					for(node = pFirst; node; node = node->pNext)
					{
						if(node->tData == item)
							return CC3D_Iterator(node, this);
					}
					return CC3D_Iterator(DC3D_NULL, this);
				}

				/** Get an iterator pointed at the beginning of the list */
				CC3D_Iterator Begin()
				{
					return CC3D_Iterator(pFirst, this);
				}

				/** Get an iterator pointed at DC3D_NULL */
				CC3D_Iterator End()
				{
					return CC3D_Iterator(DC3D_NULL, this);
				}

				/** Get the size of the linked list */
				virtual TC3D_U32 Size() const
				{
					return tSize;
				}

				/** Assignment operator */
				virtual TC3D_List<T, TAlloc> &operator = (const TC3D_List<T, TAlloc> &src)
				{
					if(this != &src)
					{
						Clear();

						tSize = src.tSize;
						tSorted = src.tSorted;

						SC3D_List_Node<T> *node;

						for(node = src.pFirst; node; node = node->pNext)
							Push_Back(node->tData);
					}

					return *this;
				}
		};
	};
};

#endif