Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages
list.h
00001 /* 00002 Copyright (C) 2003 by Marten Svanfeldt 00003 influenced by Aapl by Adrian Thurston <adriant@ragel.ca> 00004 00005 This library is free software; you can redistribute it and/or 00006 modify it under the terms of the GNU Library General Public 00007 License as published by the Free Software Foundation; either 00008 version 2 of the License, or (at your option) any later version. 00009 00010 This library is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 Library General Public License for more details. 00014 00015 You should have received a copy of the GNU Library General Public 00016 License along with this library; if not, write to the Free 00017 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00018 */ 00019 00020 #ifndef __CS_UTIL_LIST_H__ 00021 #define __CS_UTIL_LIST_H__ 00022 00023 #include "csextern.h" 00024 00029 template <class T> 00030 class csList 00031 { 00032 protected: 00037 struct csListElement 00038 { 00040 csListElement(const T& d, csListElement* newnext, csListElement* newprev) : 00041 next(newnext), prev(newprev), data(d) {} 00042 00044 csListElement* next; 00045 00047 csListElement* prev; 00048 00050 T data; 00051 }; 00052 00054 void Delete (csListElement *el); 00055 00056 public: 00058 csList() : head(0), tail(0) {} 00059 00061 csList(const csList &other); 00062 00064 ~csList() 00065 { DeleteAll (); } 00066 00068 class Iterator 00069 { 00070 public: 00072 Iterator() : ptr(0), visited(false), reversed(false) 00073 { } 00075 Iterator(const Iterator& r) 00076 { ptr = r.ptr; visited = r.visited; reversed = r.reversed; } 00078 Iterator(const csList<T> &list, bool reverse = false) : 00079 visited(false), reversed(reverse) 00080 { 00081 if (reverse) ptr = list.tail; 00082 else ptr = list.head; 00083 } 00085 Iterator& operator= (const Iterator& r) 00086 { ptr = r.ptr; visited = r.visited; reversed = r.reversed; return *this; } 00088 bool HasCurrent() const 00089 { return visited && ptr != 0; } 00091 bool HasNext() const 00092 { return ptr && (ptr->next || !visited); } 00094 bool HasPrevious() const 00095 { return ptr && (ptr->prev || !visited); } 00097 bool IsFirst() const 00098 { return ptr && ptr->prev == 0; } 00100 bool IsLast() const 00101 { return ptr && ptr->next == 0; } 00103 bool IsReverse() const 00104 { return reversed; } 00105 00107 operator T*() const 00108 { return visited && ptr ? &ptr->data : 0; } 00110 T& operator *() const 00111 { CS_ASSERT(ptr != 0); return ptr->data; } 00113 T* operator->() const 00114 { return visited && ptr ? &ptr->data : 0; } 00115 00117 void Clear () 00118 { 00119 ptr = 0; 00120 visited = true; 00121 } 00123 T& Next () 00124 { 00125 if (visited && ptr != 0) 00126 ptr = ptr->next; 00127 visited = true; 00128 CS_ASSERT(ptr != 0); 00129 return ptr->data; 00130 } 00132 T& Previous() 00133 { 00134 if (visited && ptr != 0) 00135 ptr = ptr->prev; 00136 visited = true; 00137 CS_ASSERT(ptr != 0); 00138 return ptr->data; 00139 } 00140 T& Prev() { return Previous(); } // Backward compatibility. 00141 00143 Iterator& operator++() 00144 { 00145 if (visited && ptr != 0) 00146 ptr = ptr->next; 00147 visited = true; 00148 return *this; 00149 } 00151 Iterator& operator--() 00152 { 00153 if (visited && ptr != 0) 00154 ptr = ptr->prev; 00155 visited = true; 00156 return *this; 00157 } 00158 00163 T& FetchCurrent () const 00164 { 00165 CS_ASSERT(visited && ptr != 0); 00166 return ptr->data; 00167 } 00172 T& FetchNext () const 00173 { 00174 CS_ASSERT(ptr != 0); 00175 return visited ? ptr->next->data : ptr->data; 00176 } 00181 T& FetchPrevious () const 00182 { 00183 CS_ASSERT(ptr != 0); 00184 return visited ? ptr->prev->data : ptr->data; 00185 } 00186 T& FetchPrev () const { return FetchPrevious(); } // Backward compat. 00187 00188 protected: 00189 friend class csList<T>; 00190 Iterator (csListElement* element, bool visit = true, bool rev = false) : 00191 ptr(element), visited(visit), reversed(rev) 00192 {} 00193 00194 private: 00195 csListElement* ptr; 00196 bool visited; 00197 bool reversed; 00198 }; 00199 00201 csList& operator=(const csList& other); 00202 00204 Iterator PushFront (const T& item); 00205 00207 Iterator PushBack (const T& item); 00208 00210 void InsertBefore(Iterator& it, const T& item); 00211 00213 void InsertAfter(Iterator& it, const T& item); 00214 00216 void MoveBefore(const Iterator& it, const Iterator& item); 00217 00219 void MoveAfter(const Iterator& it, const Iterator& item); 00220 00222 void Delete (Iterator& it); 00223 00225 void DeleteAll(); 00226 00228 T& Front () const 00229 { return head->data; } 00231 T& Last () const 00232 { return tail->data; } 00233 00235 bool PopFront () 00236 { 00237 if (!head) 00238 return false; 00239 Delete (head); 00240 return true; 00241 } 00242 00244 bool PopBack () 00245 { 00246 if (!tail) 00247 return false; 00248 Delete (tail); 00249 return true; 00250 } 00251 00252 bool IsEmpty () const 00253 { 00254 CS_ASSERT((head == 0 && tail == 0) || (head !=0 && tail != 0)); 00255 return head == 0; 00256 } 00257 00258 private: 00259 friend class Iterator; 00260 csListElement *head, *tail; 00261 }; 00262 00264 template <class T> 00265 inline csList<T>::csList(const csList<T> &other) : head(0), tail(0) 00266 { 00267 csListElement* e = other.head; 00268 while (e != 0) 00269 { 00270 PushBack (e->data); 00271 e = e->next; 00272 } 00273 } 00274 00276 template <class T> 00277 inline csList<T>& csList<T>::operator= (const csList<T> &other) 00278 { 00279 DeleteAll (); 00280 csListElement* e = other.head; 00281 while (e != 0) 00282 { 00283 PushBack (e->data); 00284 e = e->next; 00285 } 00286 return *this; 00287 } 00288 00290 template <class T> 00291 inline void csList<T>::DeleteAll () 00292 { 00293 csListElement *cur = head, *next = 0; 00294 while (cur != 0) 00295 { 00296 next = cur->next; 00297 delete cur; 00298 cur = next; 00299 } 00300 head = tail = 0; 00301 } 00302 00304 template <class T> 00305 inline typename_qualifier csList<T>::Iterator csList<T>::PushBack (const T& e) 00306 { 00307 csListElement* el = new csListElement (e, 0, tail); 00308 if (tail) 00309 tail->next = el; 00310 else 00311 head = el; 00312 tail = el; 00313 return Iterator(el); 00314 } 00315 00317 template <class T> 00318 inline typename_qualifier csList<T>::Iterator csList<T>::PushFront (const T& e) 00319 { 00320 csListElement* el = new csListElement (e, head, 0); 00321 if (head) 00322 head->prev = el; 00323 else 00324 tail = el; 00325 head = el; 00326 return Iterator (el); 00327 } 00328 00329 template <class T> 00330 inline void csList<T>::InsertAfter (Iterator &it, const T& item) 00331 { 00332 CS_ASSERT(it.HasCurrent()); 00333 csListElement* el = it.ptr; 00334 csListElement* next = el->next; 00335 csListElement* prev = el; 00336 csListElement* newEl = new csListElement (item, next, prev); 00337 if (!next) // this is the last element 00338 tail = newEl; 00339 else 00340 el->next->prev = newEl; 00341 el->next = newEl; 00342 } 00343 00344 template <class T> 00345 inline void csList<T>::InsertBefore (Iterator &it, const T& item) 00346 { 00347 CS_ASSERT(it.HasCurrent()); 00348 csListElement* el = it.ptr; 00349 csListElement* next = el; 00350 csListElement* prev = el->prev; 00351 csListElement* newEl = new csListElement (item, next, prev); 00352 if (!prev) // this is the first element 00353 head = newEl; 00354 else 00355 el->prev->next = newEl; 00356 el->prev = newEl; 00357 } 00358 00359 template <class T> 00360 inline void csList<T>::MoveAfter (const Iterator &it, const Iterator &item) 00361 { 00362 CS_ASSERT(item.HasCurrent()); 00363 csListElement* el_item = item.ptr; 00364 00365 // Unlink the item. 00366 if (el_item->prev) 00367 el_item->prev->next = el_item->next; 00368 else 00369 head = el_item->next; 00370 if (el_item->next) 00371 el_item->next->prev = el_item->prev; 00372 else 00373 tail = el_item->prev; 00374 00375 CS_ASSERT(it.HasCurrent()); 00376 csListElement* el = it.ptr; 00377 csListElement* next = el->next; 00378 csListElement* prev = el; 00379 00380 el_item->next = next; 00381 el_item->prev = prev; 00382 if (!next) // this is the last element 00383 tail = el_item; 00384 else 00385 el->next->prev = el_item; 00386 el->next = el_item; 00387 } 00388 00389 template <class T> 00390 inline void csList<T>::MoveBefore (const Iterator &it, const Iterator &item) 00391 { 00392 CS_ASSERT(item.HasCurrent()); 00393 csListElement* el_item = item.ptr; 00394 00395 // Unlink the item. 00396 if (el_item->prev) 00397 el_item->prev->next = el_item->next; 00398 else 00399 head = el_item->next; 00400 if (el_item->next) 00401 el_item->next->prev = el_item->prev; 00402 else 00403 tail = el_item->prev; 00404 00405 CS_ASSERT(it.HasCurrent()); 00406 csListElement* el = it.ptr; 00407 csListElement* next = el; 00408 csListElement* prev = el->prev; 00409 00410 el_item->next = next; 00411 el_item->prev = prev; 00412 if (!prev) // this is the first element 00413 head = el_item; 00414 else 00415 el->prev->next = el_item; 00416 el->prev = el_item; 00417 } 00418 00419 template <class T> 00420 inline void csList<T>::Delete (Iterator &it) 00421 { 00422 CS_ASSERT(it.HasCurrent()); 00423 csListElement* el = it.ptr; 00424 00425 // Advance the iterator so we can delete the data it's using 00426 if (it.IsReverse()) 00427 --it; 00428 else 00429 ++it; 00430 00431 Delete(el); 00432 } 00433 00434 template <class T> 00435 inline void csList<T>::Delete (csListElement *el) 00436 { 00437 CS_ASSERT(el != 0); 00438 00439 // Fix the pointers of the 2 surrounding elements 00440 if (el->prev) 00441 el->prev->next = el->next; 00442 else 00443 head = el->next; 00444 00445 if (el->next) 00446 el->next->prev = el->prev; 00447 else 00448 tail = el->prev; 00449 00450 delete el; 00451 } 00452 00453 #endif //__CS_UTIL_LIST_H__
Generated for Crystal Space by doxygen 1.3.9.1