csutil/list.h
Go to the documentation of this file.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 00027 #include "csextern.h" 00028 00029 #include "csutil/allocator.h" 00030 00035 template <class T, class MemoryAllocator = CS::Memory::AllocatorMalloc> 00036 class csList 00037 { 00038 protected: 00043 struct ListElement 00044 { 00046 ListElement(const T& d, ListElement* newnext, ListElement* newprev) : 00047 next(newnext), prev(newprev), data(d) {} 00048 00050 ListElement* next; 00051 00053 ListElement* prev; 00054 00056 T data; 00057 }; 00058 00060 void Delete (ListElement *el); 00061 00062 void* AllocElement () 00063 { 00064 return head.Alloc (sizeof (ListElement)); 00065 } 00066 void FreeElement (ListElement* el) 00067 { 00068 el->~ListElement(); 00069 head.Free (el); 00070 } 00071 public: 00077 static const size_t allocSize = sizeof (ListElement); 00078 00080 csList() : head ((ListElement*)0), tail(0) {} 00081 00083 csList (const MemoryAllocator& alloc) : head (alloc, (ListElement*)0), 00084 tail(0) {} 00085 00087 csList(const csList<T, MemoryAllocator> &other); 00088 00090 ~csList() 00091 { DeleteAll (); } 00092 00094 class Iterator 00095 { 00096 public: 00098 Iterator() : ptr(0), visited(false), reversed(false) 00099 { } 00101 Iterator(const Iterator& r) 00102 { ptr = r.ptr; visited = r.visited; reversed = r.reversed; } 00104 Iterator(const csList<T, MemoryAllocator> &list, bool reverse = false) : 00105 visited(false), reversed(reverse) 00106 { 00107 if (reverse) ptr = list.tail; 00108 else ptr = list.head.p; 00109 } 00111 Iterator& operator= (const Iterator& r) 00112 { ptr = r.ptr; visited = r.visited; reversed = r.reversed; return *this; } 00114 bool HasCurrent() const 00115 { return visited && ptr != 0; } 00117 bool HasNext() const 00118 { return ptr && (ptr->next || !visited); } 00120 bool HasPrevious() const 00121 { return ptr && (ptr->prev || !visited); } 00123 bool IsFirst() const 00124 { return ptr && ptr->prev == 0; } 00126 bool IsLast() const 00127 { return ptr && ptr->next == 0; } 00129 bool IsReverse() const 00130 { return reversed; } 00131 00133 operator T*() const 00134 { return visited && ptr ? &ptr->data : 0; } 00136 T& operator *() const 00137 { CS_ASSERT(ptr != 0); return ptr->data; } 00139 T* operator->() const 00140 { return visited && ptr ? &ptr->data : 0; } 00141 00143 void Clear () 00144 { 00145 ptr = 0; 00146 visited = true; 00147 } 00149 T& Next () 00150 { 00151 if (visited && ptr != 0) 00152 ptr = ptr->next; 00153 visited = true; 00154 CS_ASSERT(ptr != 0); 00155 return ptr->data; 00156 } 00158 T& Previous() 00159 { 00160 if (visited && ptr != 0) 00161 ptr = ptr->prev; 00162 visited = true; 00163 CS_ASSERT(ptr != 0); 00164 return ptr->data; 00165 } 00166 T& Prev() { return Previous(); } // Backward compatibility. 00167 00169 Iterator& operator++() 00170 { 00171 if (visited && ptr != 0) 00172 ptr = ptr->next; 00173 visited = true; 00174 return *this; 00175 } 00177 Iterator& operator--() 00178 { 00179 if (visited && ptr != 0) 00180 ptr = ptr->prev; 00181 visited = true; 00182 return *this; 00183 } 00184 00189 T& FetchCurrent () const 00190 { 00191 CS_ASSERT(visited && ptr != 0); 00192 return ptr->data; 00193 } 00198 T& FetchNext () const 00199 { 00200 CS_ASSERT(ptr != 0); 00201 return visited ? ptr->next->data : ptr->data; 00202 } 00207 T& FetchPrevious () const 00208 { 00209 CS_ASSERT(ptr != 0); 00210 return visited ? ptr->prev->data : ptr->data; 00211 } 00212 T& FetchPrev () const { return FetchPrevious(); } // Backward compat. 00213 00214 protected: 00215 friend class csList<T, MemoryAllocator>; 00216 Iterator (ListElement* element, bool visit = true, bool rev = false) : 00217 ptr(element), visited(visit), reversed(rev) 00218 {} 00219 00220 private: 00221 ListElement* ptr; 00222 bool visited; 00223 bool reversed; 00224 }; 00225 00227 csList& operator=(const csList<T, MemoryAllocator>& other); 00228 00230 Iterator PushFront (const T& item); 00231 00233 Iterator PushBack (const T& item); 00234 00236 void InsertBefore(Iterator& it, const T& item); 00237 00239 void InsertAfter(Iterator& it, const T& item); 00240 00245 void MoveBefore(const Iterator& it, const Iterator& item); 00247 void MoveToFront (const Iterator& item); 00248 00253 void MoveAfter(const Iterator& it, const Iterator& item); 00255 void MoveToBack (const Iterator& item); 00256 00258 void Delete (Iterator& it); 00259 00264 bool Delete (const T& item) 00265 { 00266 ListElement* e = head.p; 00267 while (e != 0) 00268 { 00269 if (e->data == item) 00270 { 00271 Delete (e); 00272 return true; 00273 } 00274 e = e->next; 00275 } 00276 return false; 00277 } 00278 00280 void DeleteAll(); 00281 00283 T& Front () const 00284 { return head.p->data; } 00286 T& Last () const 00287 { return tail->data; } 00288 00290 bool PopFront () 00291 { 00292 if (!head.p) 00293 return false; 00294 Delete (head.p); 00295 return true; 00296 } 00297 00299 bool PopBack () 00300 { 00301 if (!tail) 00302 return false; 00303 Delete (tail); 00304 return true; 00305 } 00306 00307 bool IsEmpty () const 00308 { 00309 CS_ASSERT((head.p == 0 && tail == 0) || (head.p !=0 && tail != 0)); 00310 return head.p == 0; 00311 } 00312 00313 private: 00314 friend class Iterator; 00315 CS::Memory::AllocatorPointerWrapper<ListElement, MemoryAllocator> head; 00316 ListElement* tail; 00317 }; 00318 00320 template <class T, class MemoryAllocator> 00321 inline csList<T, MemoryAllocator>::csList( 00322 const csList<T, MemoryAllocator> &other) : head((ListElement*)0), tail(0) 00323 { 00324 ListElement* e = other.head.p; 00325 while (e != 0) 00326 { 00327 PushBack (e->data); 00328 e = e->next; 00329 } 00330 } 00331 00333 template <class T, class MemoryAllocator> 00334 inline csList<T, MemoryAllocator>& csList<T, MemoryAllocator>::operator= ( 00335 const csList<T, MemoryAllocator> &other) 00336 { 00337 DeleteAll (); 00338 ListElement* e = other.head.p; 00339 while (e != 0) 00340 { 00341 PushBack (e->data); 00342 e = e->next; 00343 } 00344 return *this; 00345 } 00346 00348 template <class T, class MemoryAllocator> 00349 inline void csList<T, MemoryAllocator>::DeleteAll () 00350 { 00351 ListElement *cur = head.p, *next = 0; 00352 while (cur != 0) 00353 { 00354 next = cur->next; 00355 FreeElement (cur); 00356 cur = next; 00357 } 00358 head.p = tail = 0; 00359 } 00360 00361 #include "csutil/custom_new_disable.h" 00362 00364 template <class T, class MemoryAllocator> 00365 inline typename csList<T, MemoryAllocator>::Iterator 00366 csList<T, MemoryAllocator>::PushBack (const T& e) 00367 { 00368 ListElement* el = new (AllocElement()) ListElement (e, 0, tail); 00369 if (tail) 00370 tail->next = el; 00371 else 00372 head.p = el; 00373 tail = el; 00374 return Iterator(el); 00375 } 00376 00378 template <class T, class MemoryAllocator> 00379 inline typename csList<T, MemoryAllocator>::Iterator 00380 csList<T, MemoryAllocator>::PushFront (const T& e) 00381 { 00382 ListElement* el = new (AllocElement()) ListElement (e, head.p, 0); 00383 if (head.p) 00384 head.p->prev = el; 00385 else 00386 tail = el; 00387 head.p = el; 00388 return Iterator (el); 00389 } 00390 00391 template <class T, class MemoryAllocator> 00392 inline void csList<T, MemoryAllocator>::InsertAfter (Iterator &it, 00393 const T& item) 00394 { 00395 CS_ASSERT(it.HasCurrent()); 00396 ListElement* el = it.ptr; 00397 ListElement* next = el->next; 00398 ListElement* prev = el; 00399 ListElement* newEl = new (AllocElement()) ListElement (item, next, 00400 prev); 00401 if (!next) // this is the last element 00402 tail = newEl; 00403 else 00404 el->next->prev = newEl; 00405 el->next = newEl; 00406 } 00407 00408 template <class T, class MemoryAllocator> 00409 inline void csList<T, MemoryAllocator>::InsertBefore (Iterator &it, 00410 const T& item) 00411 { 00412 CS_ASSERT(it.HasCurrent()); 00413 ListElement* el = it.ptr; 00414 ListElement* next = el; 00415 ListElement* prev = el->prev; 00416 ListElement* newEl = new (AllocElement()) ListElement (item, next, prev); 00417 if (!prev) // this is the first element 00418 head.p = newEl; 00419 else 00420 el->prev->next = newEl; 00421 el->prev = newEl; 00422 } 00423 00424 #include "csutil/custom_new_enable.h" 00425 00426 template <class T, class MemoryAllocator> 00427 inline void csList<T, MemoryAllocator>::MoveAfter (const Iterator &it, 00428 const Iterator &item) 00429 { 00430 CS_ASSERT(item.HasCurrent()); 00431 ListElement* el_item = item.ptr; 00432 00433 // Unlink the item. 00434 if (el_item->prev) 00435 el_item->prev->next = el_item->next; 00436 else 00437 head.p = el_item->next; 00438 if (el_item->next) 00439 el_item->next->prev = el_item->prev; 00440 else 00441 tail = el_item->prev; 00442 00443 CS_ASSERT(it.HasCurrent()); 00444 ListElement* el = it.ptr; 00445 ListElement* next = el->next; 00446 ListElement* prev = el; 00447 00448 el_item->next = next; 00449 el_item->prev = prev; 00450 if (!next) // this is the last element 00451 tail = el_item; 00452 else 00453 el->next->prev = el_item; 00454 el->next = el_item; 00455 } 00456 00457 template <class T, class MemoryAllocator> 00458 inline void csList<T, MemoryAllocator>::MoveToBack (const Iterator &item) 00459 { 00460 CS_ASSERT(item.HasCurrent()); 00461 ListElement* el_item = item.ptr; 00462 00463 if (!el_item->next) 00464 // Already at back. 00465 return; 00466 00467 ListElement* el = tail; 00468 ListElement* prev = el; 00469 00470 // Unlink the item. 00471 if (el_item->prev) 00472 el_item->prev->next = el_item->next; 00473 else 00474 head.p = el_item->next; 00475 el_item->next->prev = el_item->prev; 00476 00477 el_item->next = 0; 00478 el_item->prev = prev; 00479 tail = el_item; 00480 el->next = el_item; 00481 } 00482 00483 template <class T, class MemoryAllocator> 00484 inline void csList<T, MemoryAllocator>::MoveBefore (const Iterator &it, 00485 const Iterator &item) 00486 { 00487 CS_ASSERT(item.HasCurrent()); 00488 ListElement* el_item = item.ptr; 00489 00490 // Unlink the item. 00491 if (el_item->prev) 00492 el_item->prev->next = el_item->next; 00493 else 00494 head.p = el_item->next; 00495 if (el_item->next) 00496 el_item->next->prev = el_item->prev; 00497 else 00498 tail = el_item->prev; 00499 00500 CS_ASSERT(it.HasCurrent()); 00501 ListElement* el = it.ptr; 00502 ListElement* next = el; 00503 ListElement* prev = el->prev; 00504 00505 el_item->next = next; 00506 el_item->prev = prev; 00507 if (!prev) // this is the first element 00508 head.p = el_item; 00509 else 00510 el->prev->next = el_item; 00511 el->prev = el_item; 00512 } 00513 00514 template <class T, class MemoryAllocator> 00515 inline void csList<T, MemoryAllocator>::MoveToFront (const Iterator &item) 00516 { 00517 CS_ASSERT(item.HasCurrent()); 00518 ListElement* el_item = item.ptr; 00519 00520 if (!el_item->prev) 00521 // Already at front. 00522 return; 00523 00524 ListElement* el = head.p; 00525 ListElement* next = el; 00526 00527 // Unlink the item. 00528 el_item->prev->next = el_item->next; 00529 if (el_item->next) 00530 el_item->next->prev = el_item->prev; 00531 else 00532 tail = el_item->prev; 00533 00534 el_item->next = next; 00535 el_item->prev = 0; 00536 head.p = el_item; 00537 el->prev = el_item; 00538 } 00539 00540 template <class T, class MemoryAllocator> 00541 inline void csList<T, MemoryAllocator>::Delete (Iterator &it) 00542 { 00543 CS_ASSERT(it.HasCurrent()); 00544 ListElement* el = it.ptr; 00545 00546 if (el->prev == 0) 00547 { 00548 // Deleting first element, reset to next 00549 if (it.IsReverse()) 00550 --it; 00551 else 00552 ++it; 00553 Delete(el); 00554 it.visited = false; 00555 } 00556 else 00557 { 00558 /* Make a step back so the current element can be deleted 00559 and the next element returned is the one after the deleted */ 00560 if (it.IsReverse()) 00561 ++it; 00562 else 00563 --it; 00564 Delete(el); 00565 } 00566 } 00567 00568 template <class T, class MemoryAllocator> 00569 inline void csList<T, MemoryAllocator>::Delete (ListElement *el) 00570 { 00571 CS_ASSERT(el != 0); 00572 00573 // Fix the pointers of the 2 surrounding elements 00574 if (el->prev) 00575 el->prev->next = el->next; 00576 else 00577 head.p = el->next; 00578 00579 if (el->next) 00580 el->next->prev = el->prev; 00581 else 00582 tail = el->prev; 00583 00584 FreeElement (el); 00585 } 00586 00587 #endif //__CS_UTIL_LIST_H__
Generated for Crystal Space 2.0 by doxygen 1.6.1