csutil/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) 00073 { } 00075 Iterator(const Iterator& other) 00076 { ptr = other.ptr; } 00078 Iterator(const csList<T> &list, bool reverse = false) 00079 { 00080 reversed = reverse; 00081 if (reverse) ptr = list.tail; 00082 else ptr = list.head; 00083 } 00085 const Iterator& operator= (const Iterator& other) 00086 { ptr = other.ptr; reversed = other.reversed; return *this; } 00088 bool HasCurrent() const 00089 { return ptr != 0; } 00091 bool HasNext() const 00092 { return ptr && ptr->next; } 00094 bool HasPrevious() const 00095 { return ptr && ptr->prev; } 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 &ptr->data; } 00110 T &operator *() const 00111 { return ptr->data; } 00113 T *operator->() const 00114 { return &ptr->data; } 00115 00117 void Clear () 00118 { 00119 ptr = 0; 00120 } 00122 T* Next () 00123 { 00124 if (ptr != 0) 00125 ptr = ptr->next; 00126 return *this; 00127 } 00129 T* Prev() 00130 { 00131 if (ptr != 0) 00132 ptr = ptr->prev; 00133 return *this; 00134 } 00136 Iterator& operator++() 00137 { 00138 if (ptr != 0) 00139 ptr = ptr->next; 00140 return *this; 00141 } 00143 Iterator& operator--() 00144 { 00145 if (ptr != 0) 00146 ptr = ptr->prev; 00147 return *this; 00148 } 00149 protected: 00150 friend class csList<T>; 00151 Iterator (csListElement* element) : ptr(element) 00152 {} 00153 00154 private: 00155 csListElement* ptr; 00156 bool reversed; 00157 }; 00158 00160 csList &operator=(const csList& other); 00161 00163 Iterator PushFront (const T & item); 00164 00166 Iterator PushBack (const T & item); 00167 00169 void InsertBefore(Iterator &it, const T & item); 00170 00172 void InsertAfter(Iterator &it, const T & item); 00173 00175 void Delete (Iterator &it); 00176 00178 void DeleteAll(); 00179 00181 const T& Front () const 00182 { return head->data; } 00184 const T& Last () const 00185 { return tail->data; } 00186 00188 bool PopFront () 00189 { 00190 if (!head) 00191 return false; 00192 Delete (head); 00193 return true; 00194 } 00195 00197 bool PopBack () 00198 { 00199 if (!tail) 00200 return false; 00201 Delete (tail); 00202 return true; 00203 } 00204 00205 bool IsEmpty () const 00206 { 00207 CS_ASSERT((head == 0 && tail == 0) || (head !=0 && tail != 0)); 00208 return head == 0; 00209 } 00210 00211 private: 00212 friend class Iterator; 00213 csListElement *head, *tail; 00214 }; 00215 00217 template <class T> 00218 inline csList<T>::csList(const csList<T> &other) : head(0), tail(0) 00219 { 00220 csListElement* e = other.head; 00221 while (e != 0) 00222 { 00223 PushBack (e->data); 00224 e = e->next; 00225 } 00226 } 00227 00229 template <class T> 00230 inline csList<T>& csList<T>::operator= (const csList<T> &other) 00231 { 00232 DeleteAll (); 00233 csListElement* e = other.head; 00234 while (e != 0) 00235 { 00236 PushBack (e->data); 00237 e = e->next; 00238 } 00239 return *this; 00240 } 00241 00243 template <class T> 00244 inline void csList<T>::DeleteAll () 00245 { 00246 csListElement *cur = head, *next = 0; 00247 while (cur != 0) 00248 { 00249 next = cur->next; 00250 delete cur; 00251 cur = next; 00252 } 00253 head = tail = 0; 00254 } 00255 00257 template <class T> 00258 inline typename csList<T>::Iterator csList<T>::PushBack (const T& item) 00259 { 00260 csListElement* el = new csListElement (item, 0, tail); 00261 if (tail) 00262 tail->next = el; 00263 else 00264 head = el; 00265 tail = el; 00266 return Iterator(el); 00267 } 00268 00270 template <class T> 00271 inline typename csList<T>::Iterator csList<T>::PushFront (const T& item) 00272 { 00273 csListElement* el = new csListElement (item, head, 0); 00274 if (head) 00275 head->prev = el; 00276 else 00277 tail = el; 00278 head = el; 00279 return Iterator (el); 00280 } 00281 00282 template <class T> 00283 inline void csList<T>::InsertAfter (Iterator &it, const T& item) 00284 { 00285 csListElement* el = it.ptr; 00286 csListElement* next = el->next; 00287 csListElement* prev = el; 00288 csListElement* newEl = new csListElement (item, next, prev); 00289 if (!next) // this is the last element 00290 tail = newEl; 00291 else 00292 el->next->prev = newEl; 00293 el->next = newEl; 00294 } 00295 00296 template <class T> 00297 inline void csList<T>::InsertBefore (Iterator &it, const T& item) 00298 { 00299 csListElement* el = it.ptr; 00300 csListElement* next = el; 00301 csListElement* prev = el->prev; 00302 csListElement* newEl = new csListElement (item, next, prev); 00303 if (!prev) // this is the first element 00304 head = newEl; 00305 else 00306 el->prev->next = newEl; 00307 el->prev = newEl; 00308 } 00309 00310 template <class T> 00311 inline void csList<T>::Delete (Iterator &it) 00312 { 00313 csListElement* el = it.ptr; 00314 if (!el) 00315 return; 00316 00317 // Advance the iterator so we can delete the data it's using 00318 if (it.IsReverse()) 00319 --it; 00320 else 00321 ++it; 00322 00323 Delete(el); 00324 } 00325 00326 template <class T> 00327 inline void csList<T>::Delete (csListElement *el) 00328 { 00329 CS_ASSERT(el); 00330 00331 // Fix the pointers of the 2 surrounding elements 00332 if (el->prev) 00333 el->prev->next = el->next; 00334 else 00335 head = el->next; 00336 00337 if (el->next) 00338 el->next->prev = el->prev; 00339 else 00340 tail = el->prev; 00341 00342 delete el; 00343 } 00344 00345 #endif //__CS_UTIL_LIST_H__
Generated for Crystal Space by doxygen 1.2.18