00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
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(); }
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(); }
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)
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)
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
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)
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
00465 return;
00466
00467 ListElement* el = tail;
00468 ListElement* prev = el;
00469
00470
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
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)
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
00522 return;
00523
00524 ListElement* el = head.p;
00525 ListElement* next = el;
00526
00527
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
00549 if (it.IsReverse())
00550 --it;
00551 else
00552 ++it;
00553 Delete(el);
00554 it.visited = false;
00555 }
00556 else
00557 {
00558
00559
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
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__