dllist.h
00001 /*
00002  *      dllist.h
00003  *
00004  *      Copyright 2007 Joey Durham <joey@engineering.ucsb.edu>
00005  *
00006  *      This program is free software; you can redistribute it and/or modify
00007  *      it under the terms of the GNU General Public License as published by
00008  *      the Free Software Foundation; either version 2 of the License, or
00009  *      (at your option) any later version.
00010  *
00011  *      This program is distributed in the hope that it will be useful,
00012  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  *      GNU General Public License for more details.
00015  *
00016  *      You should have received a copy of the GNU General Public License
00017  *      along with this program; if not, write to the Free Software
00018  *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00019  */
00020 
00021 
00022 #ifndef DLLIST_H
00023 #define DLLIST_H
00024 
00025 #include <iostream>
00026 #include <assert.h>
00027 
00028 template <class tVARTYPE> class DLList;
00029 
00030 
00031 
00032 template <class tVARTYPE> class DLLNode
00033 {
00034         friend class DLList<tVARTYPE>;
00035         
00036         protected :
00037                 DLLNode<tVARTYPE>* m_pNext;
00038                 DLLNode<tVARTYPE>* m_pPrev;
00039                 
00040         public :
00041                 tVARTYPE m_data;
00042                 
00043                 DLLNode(const tVARTYPE& val)
00044                 {
00045                         m_data = val;
00046                         
00047                         m_pNext = NULL;
00048                         m_pPrev = NULL;
00049                 }
00050                 virtual ~DLLNode() {}
00051 
00052 };
00053 template <class tVARTYPE> class DLList
00054 {
00055 
00056 public:
00057 
00058     DLList();
00059     virtual ~DLList();
00060 
00061     void clear();
00062 
00063     void insertAtBeginning(const tVARTYPE& val);
00064     void insertAtEnd(const tVARTYPE& val);
00065     void insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
00066     void insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
00067     DLLNode<tVARTYPE>* deleteNode(DLLNode<tVARTYPE>* pNode);
00068     void moveToEnd(DLLNode<tVARTYPE>* pThisNode);
00069 
00070     DLLNode<tVARTYPE>* next(DLLNode<tVARTYPE>* pNode) const;
00071     DLLNode<tVARTYPE>* prev(DLLNode<tVARTYPE>* pNode) const;
00072 
00073     DLLNode<tVARTYPE>* nodeNum(int iNum) const;
00074 
00075     int getLength() const
00076     {
00077         return m_iLength;
00078     }
00079 
00080     DLLNode<tVARTYPE>* head() const
00081     {
00082         return m_pHead;
00083     }
00084 
00085     DLLNode<tVARTYPE>* tail() const
00086     {
00087         return m_pTail;
00088     }
00089 
00090 protected:
00091     int m_iLength;
00092 
00093     DLLNode<tVARTYPE>* m_pHead;
00094     DLLNode<tVARTYPE>* m_pTail;
00095 };
00096 
00097 
00098 
00099 //constructor
00100 //resets local vars
00101 template <class tVARTYPE>
00102 inline DLList<tVARTYPE>::DLList()
00103 {
00104     m_iLength = 0;
00105 
00106     m_pHead = NULL;
00107     m_pTail = NULL;
00108 }
00109 
00110 
00111 //Destructor
00112 //resets local vars
00113 template <class tVARTYPE>
00114 inline DLList<tVARTYPE>::~DLList()
00115 {
00116   clear();
00117 }
00118 
00119 
00120 template <class tVARTYPE>
00121 inline void DLList<tVARTYPE>::clear()
00122 {
00123     DLLNode<tVARTYPE>* pCurrNode;
00124     DLLNode<tVARTYPE>* pNextNode;
00125 
00126     pCurrNode = m_pHead;
00127     while (pCurrNode != NULL)
00128     {
00129         pNextNode = pCurrNode->m_pNext;
00130         delete pCurrNode;
00131         pCurrNode = pNextNode;
00132     }
00133 
00134     m_iLength = 0;
00135 
00136     m_pHead = NULL;
00137     m_pTail = NULL;
00138 }
00139 
00140 
00141 //inserts at the tail of the list
00142 template <class tVARTYPE>
00143 inline void DLList<tVARTYPE>::insertAtBeginning(const tVARTYPE& val)
00144 {   
00145     DLLNode<tVARTYPE>* pNode;
00146 
00147     assert((m_pHead == NULL) || (m_iLength > 0));
00148 
00149     pNode = new DLLNode<tVARTYPE>(val);
00150 
00151     if (m_pHead != NULL)
00152     {
00153         m_pHead->m_pPrev = pNode;
00154         pNode->m_pNext = m_pHead;
00155         m_pHead = pNode;
00156     }
00157     else
00158     {
00159         m_pHead = pNode;
00160         m_pTail = pNode;
00161     }
00162 
00163     m_iLength++;
00164 }
00165 
00166 
00167 //inserts at the tail of the list
00168 template <class tVARTYPE>
00169 inline void DLList<tVARTYPE>::insertAtEnd(const tVARTYPE& val)
00170 {   
00171     DLLNode<tVARTYPE>* pNode;
00172 
00173     assert((m_pHead == NULL) || (m_iLength > 0));
00174 
00175     pNode = new DLLNode<tVARTYPE>(val);
00176 
00177     if (m_pTail != NULL)
00178     {
00179         m_pTail->m_pNext = pNode;
00180         pNode->m_pPrev = m_pTail;
00181         m_pTail = pNode;
00182     }
00183     else
00184     {
00185         m_pHead = pNode;
00186         m_pTail = pNode;
00187     }
00188 
00189     m_iLength++;
00190 }
00191 
00192 
00193 //inserts before the specified node
00194 template <class tVARTYPE>
00195 inline void DLList<tVARTYPE>::insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
00196 {
00197     DLLNode<tVARTYPE>* pNode;
00198 
00199     assert((m_pHead == NULL) || (m_iLength > 0));
00200 
00201     if ((pThisNode == NULL) || (pThisNode->m_pPrev == NULL))
00202     {
00203         insertAtBeginning(val);
00204         return;
00205     }
00206 
00207     pNode = new DLLNode<tVARTYPE>(val);
00208 
00209     pThisNode->m_pPrev->m_pNext = pNode;
00210     pNode->m_pPrev = pThisNode->m_pPrev;
00211     pThisNode->m_pPrev = pNode;
00212     pNode->m_pNext = pThisNode;
00213 
00214     m_iLength++;
00215 }
00216 
00217 
00218 //inserts after the specified node
00219 template <class tVARTYPE>
00220 inline void DLList<tVARTYPE>::insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
00221 {
00222     DLLNode<tVARTYPE>* pNode;
00223 
00224     assert((m_pHead == NULL) || (m_iLength > 0));
00225 
00226     if ((pThisNode == NULL) || (pThisNode->m_pNext == NULL))
00227     {
00228         insertAtEnd(val);
00229         return;
00230     }
00231 
00232     pNode = new DLLNode<tVARTYPE>(val);
00233 
00234     pThisNode->m_pNext->m_pPrev = pNode;
00235     pNode->m_pNext              = pThisNode->m_pNext;
00236     pThisNode->m_pNext          = pNode;
00237     pNode->m_pPrev                    = pThisNode;
00238 
00239     m_iLength++;
00240 }
00241 
00242 
00243 template <class tVARTYPE>
00244 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::deleteNode(DLLNode<tVARTYPE>* pNode)
00245 {
00246     DLLNode<tVARTYPE>* pPrevNode;
00247     DLLNode<tVARTYPE>* pNextNode;
00248 
00249     assert(pNode != NULL);
00250 
00251     pPrevNode = pNode->m_pPrev;
00252     pNextNode = pNode->m_pNext;
00253 
00254     if ((pPrevNode != NULL) && (pNextNode != NULL))
00255     {
00256         pPrevNode->m_pNext = pNextNode;
00257         pNextNode->m_pPrev = pPrevNode;
00258     }
00259     else if (pPrevNode != NULL)
00260     {
00261         pPrevNode->m_pNext = NULL;
00262         m_pTail = pPrevNode;
00263     }
00264     else if (pNextNode != NULL)
00265     {
00266         pNextNode->m_pPrev = NULL;
00267         m_pHead = pNextNode;
00268     }
00269     else
00270     {
00271         m_pHead = NULL;
00272         m_pTail = NULL;
00273     }
00274 
00275     delete pNode;
00276 
00277     m_iLength--;
00278 
00279     return pNextNode;
00280 }
00281 
00282 
00283 template <class tVARTYPE>
00284 inline void DLList<tVARTYPE>::moveToEnd(DLLNode<tVARTYPE>* pNode)
00285 {
00286     DLLNode<tVARTYPE>* pPrevNode;
00287     DLLNode<tVARTYPE>* pNextNode;
00288 
00289     assert(pNode != NULL);
00290 
00291     if (getLength() == 1)
00292     {
00293     return;
00294     }
00295 
00296     if (pNode == m_pTail)
00297     {
00298         return;
00299     }
00300 
00301     pPrevNode = pNode->m_pPrev;
00302     pNextNode = pNode->m_pNext;
00303 
00304     if ((pPrevNode != NULL) && (pNextNode != NULL))
00305     {
00306         pPrevNode->m_pNext = pNextNode;
00307         pNextNode->m_pPrev = pPrevNode;
00308     }
00309     else if (pPrevNode != NULL)
00310     {
00311         pPrevNode->m_pNext = NULL;
00312         m_pTail = pPrevNode;
00313     }
00314     else if (pNextNode != NULL)
00315     {
00316         pNextNode->m_pPrev = NULL;
00317         m_pHead = pNextNode;
00318     }
00319     else
00320     {
00321         m_pHead = NULL;
00322         m_pTail = NULL;
00323     }
00324 
00325     pNode->m_pNext = NULL;
00326     m_pTail->m_pNext = pNode;
00327     pNode->m_pPrev = m_pTail;
00328     m_pTail = pNode;
00329 }
00330 
00331 
00332 template <class tVARTYPE>
00333 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::next(DLLNode<tVARTYPE>* pNode) const
00334 {
00335   assert(pNode != NULL);
00336 
00337   return pNode->m_pNext;
00338 }
00339 
00340 
00341 template <class tVARTYPE>
00342 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::prev(DLLNode<tVARTYPE>* pNode) const
00343 {
00344     assert(pNode != NULL);
00345 
00346     return pNode->m_pPrev;
00347 }
00348 
00349 
00350 template <class tVARTYPE>
00351 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::nodeNum(int iNum) const
00352 {
00353     DLLNode<tVARTYPE>* pNode;
00354     int iCount;
00355 
00356     iCount = 0;
00357     pNode = m_pHead;
00358 
00359     while (pNode != NULL)
00360     {
00361         if (iCount == iNum)
00362         {
00363             return pNode;
00364         }
00365 
00366         iCount++;
00367         pNode = pNode->m_pNext;
00368     }
00369 
00370     return NULL;
00371 }
00372 
00373 
00374 #endif    //LINKEDLIST_H

Last updated 12 September 2005 21:38:45