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 
00033 template <class T>
00034 class csList
00035 {
00036 protected:
00041   struct csListElement
00042   {
00044     csListElement(const T& d, csListElement* newnext, csListElement* newprev) :
00045       next(newnext), prev(newprev), data(d) {}
00046 
00048     csListElement* next;
00049 
00051     csListElement* prev;
00052 
00054     T data;
00055   };
00056 
00058   void Delete (csListElement *el);
00059 
00060 public:
00062   csList() : head(0), tail(0) {}
00063 
00065   csList(const csList<T> &other);
00066 
00068   ~csList()
00069   { DeleteAll (); }
00070 
00072   class Iterator
00073   {
00074   public:
00076     Iterator() : ptr(0), visited(false), reversed(false)
00077     { }
00079     Iterator(const Iterator& r)
00080     { ptr = r.ptr; visited = r.visited; reversed = r.reversed; }
00082     Iterator(const csList<T> &list, bool reverse = false) :
00083       visited(false), reversed(reverse)
00084     {
00085       if (reverse) ptr = list.tail;
00086       else ptr = list.head;
00087     }
00089     Iterator& operator= (const Iterator& r)
00090     { ptr = r.ptr; visited = r.visited; reversed = r.reversed; return *this; }
00092     bool HasCurrent() const
00093     { return visited && ptr != 0; }
00095     bool HasNext() const
00096     { return ptr && (ptr->next || !visited); }
00098     bool HasPrevious() const
00099     { return ptr && (ptr->prev || !visited); }
00101     bool IsFirst() const
00102     { return ptr && ptr->prev == 0; }
00104     bool IsLast() const
00105     { return ptr && ptr->next == 0; }
00107     bool IsReverse() const
00108     { return reversed; }
00109 
00111     operator T*() const
00112     { return visited && ptr ? &ptr->data : 0; }
00114     T& operator *() const
00115     { CS_ASSERT(ptr != 0); return ptr->data; }
00117     T* operator->() const
00118     { return visited && ptr ? &ptr->data : 0; }
00119 
00121     void Clear ()
00122     {
00123       ptr = 0;
00124       visited = true;
00125     }
00127     T& Next ()
00128     {
00129       if (visited && ptr != 0)
00130         ptr = ptr->next;
00131       visited = true;
00132       CS_ASSERT(ptr != 0);
00133       return ptr->data;
00134     }
00136     T& Previous()
00137     {
00138       if (visited && ptr != 0)
00139         ptr = ptr->prev;
00140       visited = true;
00141       CS_ASSERT(ptr != 0);
00142       return ptr->data;
00143     }
00144     T& Prev() { return Previous(); } // Backward compatibility.
00145 
00147     Iterator& operator++()
00148     {
00149       if (visited && ptr != 0)
00150         ptr = ptr->next;
00151       visited = true;
00152       return *this;
00153     }
00155     Iterator& operator--()
00156     {
00157       if (visited && ptr != 0)
00158         ptr = ptr->prev;
00159       visited = true;
00160       return *this;
00161     }
00162 
00167     T& FetchCurrent () const
00168     {
00169       CS_ASSERT(visited && ptr != 0);
00170       return ptr->data;
00171     }
00176     T& FetchNext () const
00177     {
00178       CS_ASSERT(ptr != 0);
00179       return visited ? ptr->next->data : ptr->data;
00180     }
00185     T& FetchPrevious () const
00186     {
00187       CS_ASSERT(ptr != 0);
00188       return visited ? ptr->prev->data : ptr->data;
00189     }
00190     T& FetchPrev () const { return FetchPrevious(); } // Backward compat.
00191 
00192   protected:
00193     friend class csList<T>;
00194     Iterator (csListElement* element, bool visit = true, bool rev = false) :
00195       ptr(element), visited(visit), reversed(rev)
00196     {}
00197 
00198   private:
00199     csListElement* ptr;
00200     bool visited;
00201     bool reversed;
00202   };
00203 
00205   csList& operator=(const csList<T>& other);
00206 
00208   Iterator PushFront (const T& item);
00209 
00211   Iterator PushBack (const T& item);
00212 
00214   void InsertBefore(Iterator& it, const T& item);
00215 
00217   void InsertAfter(Iterator& it, const T& item);
00218 
00220   void MoveBefore(const Iterator& it, const Iterator& item);
00221 
00223   void MoveAfter(const Iterator& it, const Iterator& item);
00224 
00226   void Delete (Iterator& it);
00227 
00229   void DeleteAll();
00230 
00232   T& Front () const
00233   { return head->data; }
00235   T& Last () const
00236   { return tail->data; }
00237 
00239   bool PopFront ()
00240   {
00241     if (!head)
00242       return false;
00243     Delete (head);
00244     return true;
00245   }
00246 
00248   bool PopBack ()
00249   {
00250     if (!tail)
00251       return false;
00252     Delete (tail);
00253     return true;
00254   }
00255   
00256   bool IsEmpty () const
00257   {
00258     CS_ASSERT((head == 0 && tail == 0) || (head !=0 && tail != 0));
00259     return head == 0;
00260   }
00261 
00262 private:
00263   friend class Iterator;
00264   csListElement *head, *tail;
00265 };
00266 
00268 template <class T>
00269 inline csList<T>::csList(const csList<T> &other) : head(0), tail(0)
00270 {
00271   csListElement* e = other.head;
00272   while (e != 0)
00273   {
00274     PushBack (e->data);
00275     e = e->next;
00276   }
00277 }
00278 
00280 template <class T>
00281 inline csList<T>& csList<T>::operator= (const csList<T> &other)
00282 {
00283   DeleteAll ();
00284   csListElement* e = other.head;
00285   while (e != 0)
00286   {
00287     PushBack (e->data);
00288     e = e->next;
00289   }
00290   return *this;
00291 }
00292 
00294 template <class T>
00295 inline void csList<T>::DeleteAll ()
00296 {
00297   csListElement *cur = head, *next = 0;
00298   while (cur != 0)
00299   {
00300     next = cur->next;
00301     delete cur;
00302     cur = next;
00303   }
00304   head = tail = 0;
00305 }
00306 
00308 template <class T>
00309 inline typename csList<T>::Iterator csList<T>::PushBack (const T& e)
00310 {
00311   csListElement* el = new csListElement (e, 0, tail);
00312   if (tail)
00313     tail->next = el;
00314   else
00315     head = el;
00316   tail = el;
00317   return Iterator(el);
00318 }
00319 
00321 template <class T>
00322 inline typename csList<T>::Iterator csList<T>::PushFront (const T& e)
00323 {
00324   csListElement* el = new csListElement (e, head, 0);
00325   if (head)
00326     head->prev = el;
00327   else
00328     tail = el;
00329   head = el;
00330   return Iterator (el);
00331 }
00332 
00333 template <class T>
00334 inline void csList<T>::InsertAfter (Iterator &it, const T& item)
00335 {
00336   CS_ASSERT(it.HasCurrent());
00337   csListElement* el = it.ptr;
00338   csListElement* next = el->next;
00339   csListElement* prev = el;
00340   csListElement* newEl = new csListElement (item, next, prev);
00341   if (!next) // this is the last element
00342     tail = newEl;
00343   else
00344     el->next->prev = newEl;
00345   el->next = newEl;
00346 }
00347 
00348 template <class T>
00349 inline void csList<T>::InsertBefore (Iterator &it, const T& item)
00350 {
00351   CS_ASSERT(it.HasCurrent());
00352   csListElement* el = it.ptr;
00353   csListElement* next = el;
00354   csListElement* prev = el->prev;
00355   csListElement* newEl = new csListElement (item, next, prev);
00356   if (!prev) // this is the first element
00357     head = newEl;
00358   else
00359     el->prev->next = newEl;
00360   el->prev = newEl;
00361 }
00362 
00363 template <class T>
00364 inline void csList<T>::MoveAfter (const Iterator &it, const Iterator &item)
00365 {
00366   CS_ASSERT(item.HasCurrent());
00367   csListElement* el_item = item.ptr;
00368 
00369   // Unlink the item.
00370   if (el_item->prev)
00371     el_item->prev->next = el_item->next;
00372   else
00373     head = el_item->next;
00374   if (el_item->next)
00375     el_item->next->prev = el_item->prev;
00376   else
00377     tail = el_item->prev;
00378 
00379   CS_ASSERT(it.HasCurrent());
00380   csListElement* el = it.ptr;
00381   csListElement* next = el->next;
00382   csListElement* prev = el;
00383 
00384   el_item->next = next;
00385   el_item->prev = prev;
00386   if (!next) // this is the last element
00387     tail = el_item;
00388   else
00389     el->next->prev = el_item;
00390   el->next = el_item;
00391 }
00392 
00393 template <class T>
00394 inline void csList<T>::MoveBefore (const Iterator &it, const Iterator &item)
00395 {
00396   CS_ASSERT(item.HasCurrent());
00397   csListElement* el_item = item.ptr;
00398 
00399   // Unlink the item.
00400   if (el_item->prev)
00401     el_item->prev->next = el_item->next;
00402   else
00403     head = el_item->next;
00404   if (el_item->next)
00405     el_item->next->prev = el_item->prev;
00406   else
00407     tail = el_item->prev;
00408 
00409   CS_ASSERT(it.HasCurrent());
00410   csListElement* el = it.ptr;
00411   csListElement* next = el;
00412   csListElement* prev = el->prev;
00413 
00414   el_item->next = next;
00415   el_item->prev = prev;
00416   if (!prev) // this is the first element
00417     head = el_item;
00418   else
00419     el->prev->next = el_item;
00420   el->prev = el_item;
00421 }
00422 
00423 template <class T>
00424 inline void csList<T>::Delete (Iterator &it)
00425 {
00426   CS_ASSERT(it.HasCurrent());
00427   csListElement* el = it.ptr;
00428 
00429   // Advance the iterator so we can delete the data it's using
00430   if (it.IsReverse())
00431     --it;
00432   else
00433     ++it;
00434 
00435   Delete(el);
00436 }
00437 
00438 template <class T>
00439 inline void csList<T>::Delete (csListElement *el)
00440 {
00441   CS_ASSERT(el != 0);
00442 
00443   // Fix the pointers of the 2 surrounding elements
00444   if (el->prev)
00445     el->prev->next = el->next;
00446   else
00447     head = el->next;
00448 
00449   if (el->next)
00450     el->next->prev = el->prev;
00451   else
00452     tail = el->prev;
00453 
00454   delete el;
00455 }
00456 
00457 #endif //__CS_UTIL_LIST_H__

Generated for Crystal Space 1.0.2 by doxygen 1.4.7