## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# 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_qualifier 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_qualifier 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__