Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# deList.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deList.hpp
    00003 ///
    00004 /// @brief Templated linked list class
    00005 ///
    00006 /// @author Assassin
    00007 ///
    00008 /// This file is the intellectual property of Novus Delta, LLC.. Usage of the
    00009 /// contents of this file is subject to the Destiny3D Member License which
    00010 /// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
    00011 ///
    00012 /// This file is distributed "AS IS" without warranty of any kind.  Novus
    00013 /// Delta, LLC. does not guarantee the fitness of the contents of this file
    00014 /// for any particular purpose.
    00015 ///
    00016 /// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
    00017 ///
    00018 /// <hr>
    00019 ///                                 Change History
    00020 /// <hr>
    00021 ///
    00022 /// @date Sept 2001
    00023 /// @author Assassin
    00024 /// @remarks Creation
    00025 ///
    00026 ///////////////////////////////////////////////////////////////////////////////
    00027
    00028 #ifndef DELIST_HPP
    00029 #define DELIST_HPP
    00030
    00031 #include "deGlobalTypes.hpp"
    00032
    00033 #ifndef NULL
    00034 #define NULL (0)
    00035 #endif
    00036
    00037 #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
    00038
    00039 /// templated linked-list storage class
    00040 template <class T>
    00041 class deTList
    00042 {
    00043 private:
    00044     class TListNode
    00045     {
    00046     public:
    00047         TListNode()
    00048             :Next(NULL), Prev(NULL)
    00049             {
    00050             #ifdef _DEBUG
    00051             List = NULL;
    00052             #endif
    00053             }
    00054         TListNode(const T & ref)
    00055             :Data(ref), Next(NULL), Prev(NULL)
    00056             {
    00057             #ifdef _DEBUG
    00058             List = NULL;
    00059             #endif
    00060             }
    00061         TListNode(const TListNode & ref)
    00062             :Data(ref.Data), Next(NULL), Prev(NULL)
    00063             {
    00064             #ifdef _DEBUG
    00065             List = NULL;
    00066             #endif
    00067             }
    00068         virtual ~TListNode()
    00069             {}
    00070
    00071         TListNode *Next, *Prev;
    00072         #ifdef _DEBUG
    00073         deTList * List;
    00074         #endif
    00075         T Data;
    00076     };
    00077
    00078 public:
    00079     class iterator
    00080     {
    00081     private:
    00082         friend class deTList<T>;
    00083         TListNode* m_Node;
    00084     protected:
    00085         iterator(TListNode* node) : m_Node(node) {}
    00086     public:
    00087         iterator() : m_Node(0) {}
    00088         ~iterator() {}
    00089         T& operator*() const
    00090         {
    00091             DE_ASSERT (m_Node != 0);
    00092             return m_Node->Data;
    00093         }
    00094         T* operator->() const { return &operator*(); }
    00095         void operator++() { m_Node = m_Node->Next; }
    00096         void operator--() { m_Node = m_Node->Prev; }
    00097         bool operator==(const iterator & other) const
    00098             { return m_Node == other.m_Node; }
    00099         bool operator!=(const iterator & other) const
    00100             { return m_Node != other.m_Node; }
    00101     };
    00102
    00103 private:
    00104     TListNode *m_Front, *m_Back;
    00105     long m_Length;
    00106
    00107 public:
    00108     deTList()
    00109     {
    00110         m_Front = NULL;
    00111         m_Back = NULL;
    00112         m_Length = 0;
    00113     }
    00114     deTList(const deTList <T> & ref)
    00115     {
    00116         TListNode *Node = ref.m_Front, *NewNode = NULL, *tempnode = NULL;
    00117         m_Front = NULL;
    00118         m_Back = NULL;
    00119         m_Length = 0;
    00120
    00121         if (Node)
    00122         {
    00123             NewNode = new TListNode(Node->Data);
    00124             #ifdef _DEBUG
    00125             NewNode->List = this;
    00126             #endif
    00127             m_Front = NewNode;
    00128             tempnode = NewNode;
    00129             Node = Node->Next;
    00130         }
    00131         while(Node)
    00132         {
    00133             NewNode = new TListNode(Node->Data);
    00134             #ifdef _DEBUG
    00135             NewNode->List = this;
    00136             #endif
    00137             NewNode->Prev = tempnode;
    00138             tempnode = NewNode;
    00139             Node = Node->Next;
    00140         }
    00141         m_Back = NewNode;
    00142         m_Length = ref.m_Length;
    00143     }
    00144     const deTList <T> & operator=(const deTList <T> & ref)
    00145     {
    00146         TListNode *Node = ref.m_Front, *NewNode = NULL, *tempnode = NULL;
    00147         EmptyList();
    00148
    00149         if (Node)
    00150         {
    00151             NewNode = new TListNode(Node->Data);
    00152             #ifdef _DEBUG
    00153             NewNode->List = this;
    00154             #endif
    00155             m_Front = NewNode;
    00156             tempnode = NewNode;
    00157             Node = Node->Next;
    00158         }
    00159         while(Node)
    00160         {
    00161             NewNode = new TListNode(Node->Data);
    00162             #ifdef _DEBUG
    00163             NewNode->List = this;
    00164             #endif
    00165             NewNode->Prev = tempnode;
    00166             if (tempnode)
    00167                 tempnode->Next = NewNode;
    00168             tempnode = NewNode;
    00169             Node = Node->Next;
    00170         }
    00171         m_Back = NewNode;
    00172         m_Length = ref.m_Length;
    00173
    00174         return *this;
    00175     }
    00176     ~deTList()
    00177     {
    00178         EmptyList();
    00179     }
    00180
    00181     void EmptyList()
    00182     {
    00183         TListNode *ptr1, *ptr2;
    00184         ptr1 = m_Front;
    00185         while(ptr1 != NULL)
    00186         {
    00187             ptr2 = ptr1->Next;
    00188             delete ptr1;
    00189             ptr1 = ptr2;
    00190         }
    00191         m_Front = m_Back = NULL;
    00192         m_Length = 0;
    00193     }
    00194     void* FindData(void* current, T & data) const
    00195     {
    00196         void* ptr = current;
    00197         T* temp;
    00198         if (ptr)
    00199             GetData(ptr, temp);
    00200         else
    00201             ptr = GetNext(NULL, temp);
    00202         while( ptr && !(*temp == data))
    00203         {
    00204             ptr = GetNext(ptr, temp);
    00205         }
    00206         return ptr;
    00207     }
    00208     void* GetNext(void* current, T * & ptr) const
    00209     {
    00210         TListNode *Node = (TListNode*)current;
    00211         if (Node)
    00212         {
    00213             if (Node->Next)
    00214                 Node = Node->Next;
    00215             else
    00216             {
    00217                 ptr = NULL;
    00218                 return NULL;
    00219             }
    00220         }
    00221         else
    00222         {
    00223             if (m_Front)
    00224                 Node = m_Front;
    00225             else
    00226             {
    00227                 ptr = NULL;
    00228                 return NULL;
    00229             }
    00230         }
    00231         ptr = &(Node->Data);
    00232         return Node;
    00233     }
    00234     void* GetNext(void* current, T & obj) const
    00235     {
    00236         T * objptr;
    00237         void * ptr;
    00238         ptr = GetNext(current, objptr);
    00239         if (objptr)
    00240             obj = *objptr;
    00241         return ptr;
    00242     }
    00243     void* GetPrev(void* current, T * & ptr) const
    00244     {
    00245         TListNode *Node = (TListNode*)current;
    00246         if (Node)
    00247         {
    00248             if (Node->Prev)
    00249                 Node = Node->Prev;
    00250             else
    00251             {
    00252                 ptr = NULL;
    00253                 return NULL;
    00254             }
    00255         }
    00256         else
    00257         {
    00258             if (m_Back)
    00259                 Node = m_Back;
    00260             else
    00261             {
    00262                 ptr = NULL;
    00263                 return NULL;
    00264             }
    00265         }
    00266         ptr = &(Node->Data);
    00267         return Node;
    00268     }
    00269     void* GetPrev(void* current, T & obj) const
    00270     {
    00271         T * objptr;
    00272         void * ptr;
    00273         ptr = GetPrev(current, objptr);
    00274         if (objptr)
    00275             obj = *objptr;
    00276         return ptr;
    00277     }
    00278     void GetData(void * current, T & obj) const
    00279     {
    00280         const TListNode *Node = (const TListNode*)current;
    00281         if (Node)
    00282             obj = (Node->Data);
    00283     }
    00284     void GetData(void * current, const T* & obj) const
    00285     {
    00286         const TListNode *Node = (const TListNode*)current;
    00287         if (Node)
    00288             obj = &(Node->Data);
    00289     }
    00290     void* AddElementNoData()
    00291     {
    00292         TListNode * Node = new TListNode();
    00293         if (!Node)
    00294             return NULL;
    00295         #ifdef _DEBUG
    00296         Node->List = this;
    00297         #endif
    00298         m_Length++;
    00299         if (m_Front == NULL)
    00300             m_Front = Node;
    00301         if (m_Back)
    00302             m_Back->Next = Node;
    00303         Node->Prev = m_Back;
    00304         m_Back = Node;
    00305
    00306         return Node;
    00307     }
    00308     void* AddElement(const T & data)
    00309     {
    00310         TListNode * Node = new TListNode(data);
    00311         if (!Node)
    00312             return NULL;
    00313         #ifdef _DEBUG
    00314         Node->List = this;
    00315         #endif
    00316         m_Length++;
    00317         if (m_Front == NULL)
    00318             m_Front = Node;
    00319         if (m_Back)
    00320             m_Back->Next = Node;
    00321         Node->Prev = m_Back;
    00322         m_Back = Node;
    00323
    00324         return Node;
    00325     }
    00326     void* AddElementBefore(const T & data, void * current)
    00327     {
    00328         TListNode * Node = (TListNode*)current;
    00329         if (!Node)
    00330         {
    00331             Node = m_Front;
    00332             if (!Node)
    00333             {
    00334                 return AddElement(data);
    00335             }
    00336         }
    00337         TListNode * NewNode = new TListNode(data);
    00338         if (!NewNode)
    00339             return NULL;
    00340         #ifdef _DEBUG
    00341         NewNode->List = this;
    00342         #endif
    00343         m_Length++;
    00344         NewNode->Prev = Node->Prev;
    00345         NewNode->Next = Node;
    00346         if (Node->Prev)
    00347             Node->Prev->Next = NewNode;
    00348         else
    00349             m_Front = NewNode;
    00350         Node->Prev = NewNode;
    00351
    00352         return NewNode;
    00353     }
    00354     void* AddElementAfter(const T & data, void * current)
    00355     {
    00356         TListNode * Node = (TListNode*)current;
    00357         if (!Node)
    00358         {
    00359             Node = m_Back;
    00360             if (!Node)
    00361             {
    00362                 return AddElement(data);
    00363             }
    00364         }
    00365         TListNode * NewNode = new TListNode(data);
    00366         if (!NewNode)
    00367             return NULL;
    00368         #ifdef _DEBUG
    00369         NewNode->List = this;
    00370         #endif
    00371         m_Length++;
    00372         NewNode->Next = Node->Next;
    00373         NewNode->Prev = Node;
    00374         if (Node->Next)
    00375             Node->Next->Prev = NewNode;
    00376         else
    00377             m_Back = NewNode;
    00378         Node->Next = NewNode;
    00379
    00380         return NewNode;
    00381     }
    00382     void AppendList(const deTList <T> & list)
    00383     {
    00384         TListNode *Node, *NodeCopy=NULL;
    00385         Node = list.m_Front;
    00386         while (Node != NULL)
    00387         {
    00388             NodeCopy = new TListNode(Node->Data);
    00389             #ifdef _DEBUG
    00390             NodeCopy->List = this;
    00391             #endif
    00392             if (!m_Back)
    00393             {
    00394                 m_Back = NodeCopy;
    00395                 m_Front = NodeCopy;
    00396             }
    00397             else
    00398             {
    00399                 m_Back->Next = NodeCopy;
    00400                 NodeCopy->Prev = m_Back;
    00401                 //NodeCopy->Next = NULL;
    00402                 m_Back = NodeCopy;
    00403             }
    00404             Node = Node->Next;
    00405         }
    00406         if (NodeCopy)
    00407             NodeCopy->Next = NULL;
    00408         m_Length += list.m_Length;
    00409     }
    00410     void MergeList(deTList <T> & list)
    00411     {
    00412         TListNode *Node;
    00413         Node = list.m_Front;
    00414         if (!m_Back)
    00415         {
    00416             m_Back = Node;
    00417             m_Front = Node;
    00418         }
    00419         else
    00420         {
    00421             m_Back->Next = Node;
    00422             Node->Prev = m_Back;
    00423             m_Back = Node;
    00424         }
    00425         #ifdef _DEBUG
    00426         while (Node != NULL)
    00427         {
    00428             Node->List = this;
    00429             Node = Node->Next;
    00430         }
    00431         #endif
    00432         m_Length += list.m_Length;
    00433         list.m_Length = 0;
    00434         list.m_Front = list.m_Back = NULL;
    00435     }
    00436     #ifdef _DEBUG
    00437     static void StaticRemoveElement(void * ptr)
    00438     {
    00439         TListNode * Node = (TListNode*)ptr;
    00440         if (Node->List)
    00441             Node->List->RemoveElement(ptr);
    00442     }
    00443     #endif
    00444     deBoolean RemoveElement(void * ptr)
    00445     {
    00446         TListNode * Node = (TListNode*)ptr;
    00447         if (Node == NULL)
    00448             return deTRUE;
    00449         #ifdef _DEBUG
    00450         if (Node->List != this)
    00451             return deFALSE;
    00452         #endif
    00453         m_Length--;
    00454         if (Node->Prev)
    00455             Node->Prev->Next = Node->Next;
    00456         if (Node->Next)
    00457             Node->Next->Prev = Node->Prev;
    00458         if (m_Front == Node)
    00459             m_Front = Node->Next;
    00460         if (m_Back == Node)
    00461             m_Back = Node->Prev;
    00462         Node->Next = NULL;
    00463         Node->Prev = NULL;
    00464         #ifdef _DEBUG
    00465         Node->List = NULL;
    00466         #endif
    00467         delete Node;
    00468         return deTRUE;
    00469     }
    00470     inline void * RemoveElementGetNext(void* current, T * & ptr)
    00471     {
    00472         void * ret;
    00473         ret = GetNext(current, ptr);
    00474         RemoveElement(current);
    00475         return ret;
    00476     }
    00477
    00478     inline long Length() const  { return m_Length; }
    00479     inline long size() const    { return m_Length; }
    00480
    00481     // iterator stuff
    00482     iterator push_back(const T & data)
    00483     {
    00484         TListNode * Node = (TListNode*)AddElement(data);
    00485         return iterator(Node);
    00486     }
    00487     iterator push_back()
    00488     {
    00489         TListNode * Node = (TListNode*)AddElementNoData();
    00490         return iterator(Node);
    00491     }
    00492
    00493     inline iterator begin() { return iterator(m_Front); }
    00494     inline iterator end()   { return iterator(0); }
    00495
    00496     inline iterator erase(iterator& it)
    00497     {
    00498         iterator next = it;
    00499         ++next;
    00500         RemoveElement(it.m_Node);
    00501         return next;
    00502     }
    00503 };
    00504
    00505
    00506 //#pragma warning (default : 4710)
    00507
    00508 #endif