csutil/list.h
00001 /* 00002 Copyright (C) 2003 by Marten Svanfeldt 00003 influenced by Aapl by Adrian Thurston <adriant@ragel.ca> 00004 00005 This program is free software; you can redistribute it and/or modify 00006 it under the terms of the GNU General Public License as published by 00007 the Free Software Foundation; either version 2 of the License, or 00008 (at your option) any later version. 00009 00010 This program 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 00013 GNU General Public License for more details. 00014 00015 You should have received a copy of the GNU General Public License 00016 along with this program; if not, write to the Free Software 00017 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00018 */ 00019 00020 #ifndef __CS_UTIL_LIST_H__ 00021 #define __CS_UTIL_LIST_H__ 00022 00028 template <class T> 00029 class csList 00030 { 00031 protected: 00036 struct csListElement 00037 { 00039 csListElement(const T& d, csListElement* newnext, 00040 csListElement* newprev) 00041 : next(newnext), prev(newprev), data(d) 00042 {} 00043 00045 csListElement* next; 00046 00048 csListElement* prev; 00049 00051 T data; 00052 }; 00053 00055 void Delete (csListElement *el); 00056 00057 public: 00059 csList() 00060 : head(0), tail(0) 00061 {} 00062 00064 csList(const csList &other); 00065 00067 ~csList() 00068 { DeleteAll (); } 00069 00071 class Iterator 00072 { 00073 public: 00075 Iterator() : ptr(0) 00076 { } 00078 Iterator(const Iterator& other) 00079 { ptr = other.ptr; } 00081 Iterator(const csList<T> &list, bool reverse = false) 00082 { 00083 reversed = reverse; 00084 if (reverse) ptr = list.tail; 00085 else ptr = list.head; 00086 } 00088 const Iterator& operator= (const Iterator& other) 00089 { ptr = other.ptr; return *this; } 00091 bool HasCurrent() const 00092 { return ptr != 0; } 00094 bool HasNext() const 00095 { return ptr && ptr->next; } 00097 bool HasPrevious() const 00098 { return ptr && ptr->prev; } 00100 bool IsFirst() const 00101 { return ptr && ptr->prev == 0; } 00103 bool IsLast() const 00104 { return ptr && ptr->next == 0; } 00106 bool IsReverse() const 00107 { return reversed; } 00108 00110 operator T*() const 00111 { return &ptr->data; } 00113 T &operator *() const 00114 { return ptr->data; } 00116 T *operator->() const 00117 { return &ptr->data; } 00118 00120 void Clear () 00121 { 00122 ptr = 0; 00123 } 00125 T* Next () 00126 { 00127 T* rc = *this; 00128 ptr = ptr->next; 00129 return rc; 00130 } 00132 T* Prev() 00133 { 00134 T* rc = *this; 00135 ptr = ptr->prev; 00136 return rc; 00137 } 00139 Iterator& operator++() 00140 { 00141 T* rc = *this; 00142 ptr = ptr->next; 00143 return rc; 00144 } 00146 Iterator& operator--() 00147 { 00148 T* rc = *this; 00149 ptr = ptr->prev; 00150 return rc; 00151 } 00152 protected: 00153 friend class csList<T>; 00154 Iterator (csListElement* element) : ptr(element) 00155 {} 00156 00157 private: 00158 csListElement* ptr; 00159 bool reversed; 00160 }; 00161 00163 csList &operator=(const csList& other); 00164 00166 Iterator PushFront (const T & item); 00167 00169 Iterator PushBack (const T & item); 00170 00172 void InsertBefore(Iterator &it, const T & item); 00173 00175 void InsertAfter(Iterator &it, const T & item); 00176 00178 void Delete (Iterator &it); 00179 00181 void DeleteAll(); 00182 00184 const T& Front () const 00185 { return head->data; } 00187 const T& Last () const 00188 { return tail->data; } 00189 00191 bool PopFront () 00192 { 00193 if (!head) 00194 return false; 00195 Delete (head); 00196 return true; 00197 } 00198 00200 bool PopBack () 00201 { 00202 if (!tail) 00203 return false; 00204 Delete (tail); 00205 return true; 00206 } 00207 00208 private: 00209 friend class Iterator; 00210 csListElement *head, *tail; 00211 }; 00212 00214 template <class T> 00215 inline csList<T>::csList(const csList<T> &other) : head(0), tail(0) 00216 { 00217 csListElement* e = other.head; 00218 while( e != 0) 00219 { 00220 PushBack (e->data); 00221 e = e->next; 00222 } 00223 } 00224 00226 template <class T> 00227 inline csList<T>& csList<T>::operator= (const csList<T> &other) 00228 { 00229 DeleteAll (); 00230 csListElement* e = other.head; 00231 while(e != 0) 00232 { 00233 PushBack (e->data); 00234 e = e->next; 00235 } 00236 return *this; 00237 } 00238 00240 template <class T> 00241 inline void csList<T>::DeleteAll () 00242 { 00243 csListElement *cur = head, *next = 0; 00244 while(cur != 0) 00245 { 00246 next = cur->next; 00247 delete cur; 00248 cur = next; 00249 } 00250 head = tail = 0; 00251 } 00252 00254 template <class T> 00255 inline typename csList<T>::Iterator csList<T>::PushBack (const T& item) 00256 { 00257 csListElement* el = new csListElement (item, 0, tail); 00258 if (tail) 00259 tail->next = el; 00260 else 00261 head = el; 00262 tail = el; 00263 return Iterator(el); 00264 } 00265 00267 template <class T> 00268 inline typename csList<T>::Iterator csList<T>::PushFront (const T& item) 00269 { 00270 csListElement* el = new csListElement (item, head, 0); 00271 if (head) 00272 head->prev = el; 00273 else 00274 tail = el; 00275 head = el; 00276 return Iterator (el); 00277 } 00278 00279 template <class T> 00280 inline void csList<T>::InsertBefore (Iterator &it, const T& item) 00281 { 00282 csListElement* el = it.ptr; 00283 csListElement* next = el->next; 00284 csListElement* prev = el; 00285 csListElement* newEl = new csListElement (item, next, prev); 00286 if (!next) // this is the last element 00287 tail = newEl; 00288 else 00289 el->next->prev = newEl; 00290 el->next = newEl; 00291 } 00292 00293 template <class T> 00294 inline void csList<T>::InsertAfter (Iterator &it, const T& item) 00295 { 00296 csListElement* el = it.ptr; 00297 csListElement* next = el; 00298 csListElement* prev = el->prev; 00299 csListElement* newEl = new csListElement (item, next, prev); 00300 if (!prev) // this is the first element 00301 head = newEl; 00302 else 00303 el->prev->next = newEl; 00304 el->prev = newEl; 00305 } 00306 00307 template <class T> 00308 inline void csList<T>::Delete (Iterator &it) 00309 { 00310 csListElement* el = it.ptr; 00311 if (!el) 00312 return; 00313 00314 // Advance the iterator so we can delete the data its using 00315 if (it.IsReverse()) 00316 --it; 00317 else 00318 ++it; 00319 00320 Delete(el); 00321 } 00322 00323 template <class T> 00324 inline void csList<T>::Delete (csListElement *el) 00325 { 00326 CS_ASSERT(el); 00327 00328 // Fix the pointers of the 2 surrounding elements 00329 if (el->prev) 00330 el->prev->next = el->next; 00331 else 00332 head = el->next; 00333 00334 if (el->next) 00335 el->next->prev = el->prev; 00336 else 00337 tail = el->prev; 00338 00339 delete el; 00340 } 00341 00342 #endif //__CS_UTIL_LIST_H__
Generated for Crystal Space by doxygen 1.2.18