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