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

# deStack.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deStack.hpp
    00003 ///
    00004 /// @brief Templated Stack/Queue 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 /// @date Jan 2002
    00027 /// @author Assassin
    00028 /// @remarks Bug fixes
    00029 ///
    00030 ///////////////////////////////////////////////////////////////////////////////
    00031
    00032 #ifndef DESTACK_HPP
    00033 #define DESTACK_HPP
    00034
    00035
    00036 #include "deGlobalTypes.hpp"
    00037
    00038
    00039 // Structures defined in this header
    00040
    00041 typedef struct StackNode StackNode;
    00042
    00043
    00044
    00045 // Enums
    00046
    00047 #pragma warning (disable : 4710)
    00048
    00049 /// templated stack (or queue) storage class
    00050 template <class T>
    00051 class deTStack
    00052 {
    00053 public:
    00054     enum deStackType
    00055     {
    00056         LIFO_STACK = 0,
    00057         FIFO_STACK = 1,
    00058         StackType_32bit = 0x7fffffff
    00059     };
    00060     deTStack();
    00061     deTStack(deStackType PopOrder);
    00062     deTStack(const deTStack &Stack);
    00063     ~deTStack();
    00064
    00065     deBoolean   Push(const T& ItemData);
    00066     deBoolean   Push(const T& ItemData, T* &ref);
    00067     deBoolean   Pop();
    00068     deBoolean   Pop(T & target);
    00069     T*          Peek(int ItemOffset);
    00070     T*          Peek();
    00071     deBoolean   Clear();
    00072     deBoolean   isEmpty()   { return (ItemCount == 0); }
    00073     int Length(void)    { return ItemCount; }
    00074     deStackType GetStackType(void) { return StackType; }
    00075     void SetStackType(deStackType PopOrder) { StackType = PopOrder; }
    00076     bool HasData(T & data);
    00077
    00078     class TStackNode
    00079     {
    00080     public:
    00081         TStackNode(const T & ref) : Data(ref) {}
    00082
    00083         TStackNode * Next;
    00084         TStackNode * Prev;
    00085         T Data;
    00086     };
    00087
    00088 private:
    00089     TStackNode  *Head;
    00090     TStackNode  *Tail;
    00091     int         ItemCount;
    00092     deStackType StackType;
    00093
    00094     TStackNode *InsertItem(TStackNode *PrevItem, TStackNode *NextItem, const T& ItemData);
    00095     TStackNode *AppendItem(const T& ItemData);
    00096     deBoolean RemoveItem(TStackNode *sn);
    00097     T* GetFirstItem(TStackNode *&sn);
    00098     T* GetLastItem(TStackNode *&sn);
    00099     T* GetNextItem(TStackNode *&sn);
    00100     T* GetPrevItem(TStackNode *&sn);
    00101 };
    00102
    00103
    00104 /*********************************************************************/
    00105 // templated implementation below
    00106 /*********************************************************************/
    00107
    00108
    00109 template <class T>
    00110 deTStack<T>::deTStack()
    00111 {
    00112    ItemCount = 0;
    00113    Head      = NULL;
    00114    Tail      = NULL;
    00115    StackType = LIFO_STACK;
    00116 }
    00117
    00118 template <class T>
    00119 deTStack<T>::deTStack(deStackType PopOrder)
    00120 :StackType(PopOrder)
    00121 {
    00122    ItemCount = 0;
    00123    Head      = NULL;
    00124    Tail      = NULL;
    00125 }
    00126
    00127 template <class T>
    00128 deTStack<T>::deTStack(const deTStack<T> &Stack)
    00129 {
    00130    TStackNode *sn;
    00131
    00132    ItemCount    = 0;
    00133    Head         = NULL;
    00134    Tail         = NULL;
    00135    StackType    = Stack.StackType;
    00136
    00137    if (Stack.Head == NULL)
    00138       return;
    00139
    00140    sn = Stack.Head;
    00141
    00142    while (sn != NULL)
    00143    {
    00144       AppendItem(sn->Data);
    00145       sn = sn->Next;
    00146    }
    00147 }
    00148
    00149 template <class T>
    00150 deTStack<T>::~deTStack()
    00151 {
    00152     Clear();
    00153 }
    00154
    00155
    00156 template <class T>
    00157 deBoolean deTStack<T>::Push(const T& ItemData)
    00158 {
    00159     TStackNode *sn;
    00160
    00161     sn = AppendItem(ItemData);
    00162
    00163     if (sn == NULL)
    00164         return (DE_FALSE);
    00165
    00166     return (DE_TRUE);
    00167 }
    00168
    00169 template <class T>
    00170 deBoolean deTStack<T>::Push(const T& ItemData, T* &ref)
    00171 {
    00172     TStackNode *sn;
    00173
    00174     sn = AppendItem(ItemData);
    00175
    00176     if (sn == NULL)
    00177         return (DE_FALSE);
    00178
    00179     ref = &(sn->Data);
    00180     return (DE_TRUE);
    00181 }
    00182
    00183 template <class T>
    00184 deBoolean deTStack<T>::Pop()
    00185 {
    00186     TStackNode *sn = NULL;
    00187
    00188     if (ItemCount == 0)
    00189         return DE_FALSE;
    00190
    00191     if (StackType == LIFO_STACK)
    00192         GetLastItem(sn);
    00193     else
    00194         GetFirstItem(sn);
    00195
    00196     if (!RemoveItem(sn))
    00197     {
    00198         //Need error handling here
    00199     }
    00200
    00201     return DE_TRUE;
    00202 }
    00203
    00204 template <class T>
    00205 deBoolean deTStack<T>::Pop(T & target)
    00206 {
    00207     TStackNode *sn = NULL;
    00208     T *pData = NULL;
    00209
    00210     if (ItemCount == 0)
    00211         return DE_FALSE;
    00212
    00213     if (StackType == LIFO_STACK)
    00214         pData = GetLastItem(sn);
    00215     else
    00216         pData = GetFirstItem(sn);
    00217
    00218     target = *pData;
    00219
    00220     if (!RemoveItem(sn))
    00221     {
    00222         //Need error handling here
    00223     }
    00224
    00225     return DE_TRUE;
    00226 }
    00227
    00228 template <class T>
    00229 T* deTStack<T>::Peek(int ItemOffset)
    00230 {
    00231     if (ItemCount == 0)
    00232       return NULL;
    00233
    00234     if ((ItemCount < (ItemOffset + 1)) || (ItemOffset < 0))
    00235         return NULL;
    00236
    00237     TStackNode *sn = NULL;
    00238     T* pData = NULL;
    00239     int i;
    00240
    00241     if (StackType == LIFO_STACK)
    00242     {
    00243         pData = GetLastItem(sn);
    00244
    00245         for (i = ItemOffset; i > 0; i--)
    00246         {
    00247             pData = GetPrevItem(sn);
    00248         }
    00249     }
    00250     else
    00251     {
    00252         pData = GetFirstItem(sn);
    00253
    00254         for (i = ItemOffset; i > 0; i--)
    00255         {
    00256             pData = GetNextItem(sn);
    00257         }
    00258     }
    00259
    00260     return pData;
    00261 }
    00262
    00263 template <class T>
    00264 T* deTStack<T>::Peek()
    00265 {
    00266     if (ItemCount == 0)
    00267         return NULL;
    00268
    00269     TStackNode * sn = NULL;
    00270     if (StackType == LIFO_STACK)
    00271     {
    00272         return GetLastItem(sn);
    00273     }
    00274     else
    00275     {
    00276         return GetFirstItem(sn);
    00277     }
    00278 }
    00279
    00280 template <class T>
    00281 deBoolean deTStack<T>::Clear()
    00282 {
    00283    TStackNode *sn;
    00284    TStackNode *Nextsn;
    00285
    00286    sn = Head;
    00287
    00288    while (sn != NULL)
    00289    {
    00290       Nextsn = sn->Next;
    00291       delete sn;
    00292       --ItemCount;
    00293       sn = Nextsn;
    00294     }
    00295
    00296    Head = NULL;
    00297    Tail = NULL;
    00298
    00299    if (ItemCount != 0)
    00300    {
    00301        //assert(NULL == "Failed to remove number of nodes matching internal counter in deTStack");
    00302        return DE_FALSE;
    00303    }
    00304    return DE_TRUE;
    00305 }
    00306
    00307 template <class T>
    00308 typename deTStack<T>::TStackNode * deTStack<T>::InsertItem(TStackNode *PrevItem, TStackNode *NextItem, const T& ItemData)
    00309 {
    00310    TStackNode *NewNode;
    00311
    00312    NewNode = new TStackNode(ItemData);
    00313
    00314    if (NewNode == NULL)
    00315    {
    00316       //Need error handling here
    00317       return NULL;
    00318    }
    00319
    00320    NewNode->Data = ItemData;
    00321    NewNode->Prev = PrevItem;
    00322    NewNode->Next = NextItem;
    00323
    00324    // Append
    00325    if (NextItem == NULL)
    00326       Tail = NewNode;
    00327
    00328    // Prepend
    00329    if (PrevItem == NULL)
    00330       Head = NewNode;
    00331
    00332    //Set Prev/Next pointers
    00333    if (PrevItem != NULL)
    00334       PrevItem->Next = NewNode;
    00335
    00336    if (NextItem != NULL)
    00337       NextItem->Prev = NewNode;
    00338
    00339    // Increment node count
    00340    ++ItemCount;
    00341
    00342    return NewNode;
    00343 }
    00344
    00345 template <class T>
    00346 typename deTStack<T>::TStackNode * deTStack<T>::AppendItem(const T& ItemData)
    00347 {
    00348    return InsertItem(Tail, NULL, ItemData);
    00349 }
    00350
    00351 template <class T>
    00352 deBoolean deTStack<T>::RemoveItem(TStackNode *sn)
    00353 {
    00354     // Unlink the node
    00355     if (Head == sn)
    00356     {
    00357         if (sn->Prev == NULL)
    00358         {
    00359             Head = sn->Next;
    00360             if (Head != NULL)
    00361                 Head->Prev = NULL;
    00362         }
    00363         else
    00364         {
    00365             //Need error handling here
    00366             return DE_FALSE;
    00367         }
    00368     }
    00369     if (Tail == sn)
    00370     {
    00371     if (sn->Next == NULL)
    00372     {
    00373         Tail = sn->Prev;
    00374         if (Tail != NULL)
    00375             Tail->Next = NULL;
    00376     }
    00377     else
    00378     {
    00379         //Need error handling here
    00380         return DE_FALSE;
    00381     }
    00382     }
    00383     else
    00384     {
    00385         if (sn->Prev != NULL)
    00386         {
    00387             sn->Prev->Next = sn->Next;
    00388         }
    00389         else
    00390         {
    00391             //Need error handling here
    00392             return DE_FALSE;
    00393         }
    00394
    00395         if (sn->Next != NULL)
    00396         {
    00397             sn->Next->Prev = sn->Prev;
    00398         }
    00399         else
    00400         {
    00401             //Need error handling here
    00402             return DE_FALSE;
    00403         }
    00404     }
    00405
    00406     // Deallocate the node
    00407     delete sn;
    00408
    00409     --ItemCount;
    00410
    00411     return DE_TRUE;
    00412 }
    00413
    00414 template <class T>
    00415 bool deTStack<T>::HasData(T & data)
    00416 {
    00417     TStackNode * n = Head;
    00418     while (n)
    00419     {
    00420         if (n->Data == data)
    00421             return true;
    00422         n = n->Next;
    00423     }
    00424     return false;
    00425 }
    00426
    00427 template <class T>
    00428 T* deTStack<T>::GetFirstItem(TStackNode *&sn)
    00429 {
    00430     if (Head == NULL)
    00431     {
    00432         sn = NULL;
    00433         return NULL;
    00434     }
    00435
    00436     sn = Head;
    00437
    00438     return &(sn->Data);
    00439 }
    00440
    00441 template <class T>
    00442 T* deTStack<T>::GetLastItem(TStackNode *&sn)
    00443 {
    00444     if (Tail == NULL)
    00445     {
    00446         sn = NULL;
    00447         return NULL;
    00448     }
    00449
    00450     sn = Tail;
    00451
    00452     return &(sn->Data);
    00453 }
    00454
    00455 template <class T>
    00456 T* deTStack<T>::GetNextItem(TStackNode *&sn)
    00457 {
    00458     if (sn == NULL)
    00459         return NULL;
    00460
    00461     if (sn->Next == NULL)
    00462     {
    00463         sn = NULL;
    00464         return NULL;
    00465     }
    00466
    00467     sn = sn->Next;
    00468
    00469     return &(sn->Data);
    00470 }
    00471
    00472 template <class T>
    00473 T* deTStack<T>::GetPrevItem(TStackNode *&sn)
    00474 {
    00475     if (sn == NULL)
    00476         return NULL;
    00477
    00478     if (sn->Prev == NULL)
    00479     {
    00480         sn = NULL;
    00481         return NULL;
    00482     }
    00483
    00484     sn = sn->Prev;
    00485
    00486     return &(sn->Data);
    00487 }
    00488
    00489 //#pragma warning (default : 4710)
    00490
    00491 #endif  // End DESTACK_HPP