CrystalSpace

Public API Reference

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.7.6.1