CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

csutil/list.h

00001 /*
00002     Copyright (C) 2003 by Marten Svanfeldt
00003     influenced by Aapl by Adrian Thurston <adriant@ragel.ca>
00004 
00005     This program is free software; you can redistribute it and/or modify
00006     it under the terms of the GNU General Public License as published by
00007     the Free Software Foundation; either version 2 of the License, or
00008     (at your option) any later version.
00009 
00010     This program 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
00013     GNU General Public License for more details.
00014 
00015     You should have received a copy of the GNU General Public License
00016     along with this program; if not, write to the Free Software
00017     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 */
00019 
00020 #ifndef __CS_UTIL_LIST_H__
00021 #define __CS_UTIL_LIST_H__
00022 
00028 template <class T>
00029 class csList
00030 {
00031 protected:
00036   struct csListElement
00037   {
00039     csListElement(const T& d, csListElement* newnext,
00040                               csListElement* newprev)
00041       : next(newnext), prev(newprev), data(d)
00042     {}
00043 
00045     csListElement* next;
00046 
00048     csListElement* prev;
00049 
00051     T data;
00052   };
00053 
00055   void Delete (csListElement *el);
00056 
00057 public:
00059   csList()
00060     : head(0), tail(0)
00061   {}
00062 
00064   csList(const csList &other);
00065 
00067   ~csList()
00068   { DeleteAll (); }
00069 
00071   class Iterator
00072   {
00073   public:
00075     Iterator() : ptr(0)
00076     { }
00078     Iterator(const Iterator& other)
00079     { ptr = other.ptr; }
00081     Iterator(const csList<T> &list, bool reverse = false)
00082     {
00083       reversed = reverse;
00084       if (reverse) ptr = list.tail;
00085       else ptr = list.head;
00086     }
00088     const Iterator& operator= (const Iterator& other)
00089     { ptr = other.ptr; return *this; }
00091     bool HasCurrent() const
00092     { return ptr != 0; }
00094     bool HasNext() const
00095     { return ptr && ptr->next; }
00097     bool HasPrevious() const
00098     { return ptr && ptr->prev; }
00100     bool IsFirst() const
00101     { return ptr && ptr->prev == 0; }
00103     bool IsLast() const
00104     { return ptr && ptr->next == 0; }
00106     bool IsReverse() const
00107     { return reversed; }
00108 
00110     operator T*() const
00111     { return &ptr->data; }
00113     T &operator *() const
00114     { return ptr->data; }
00116     T *operator->() const
00117     { return &ptr->data; }
00118 
00120     void Clear ()
00121     {
00122       ptr = 0;
00123     }
00125     T* Next ()
00126     {
00127       T* rc = *this;
00128       ptr = ptr->next;
00129       return rc;
00130     }
00132     T* Prev()
00133     {
00134       T* rc = *this;
00135       ptr = ptr->prev;
00136       return rc;
00137     }
00139     Iterator& operator++()
00140     {
00141       T* rc = *this;
00142       ptr = ptr->next;
00143       return rc;
00144     }
00146     Iterator& operator--()
00147     {
00148       T* rc = *this;
00149       ptr = ptr->prev;
00150       return rc;
00151     }
00152   protected:
00153     friend class csList<T>;
00154     Iterator (csListElement* element) : ptr(element)
00155     {}
00156 
00157   private:
00158     csListElement* ptr;
00159     bool reversed;
00160   };
00161 
00163   csList &operator=(const csList& other);
00164 
00166   Iterator PushFront (const T & item);
00167 
00169   Iterator PushBack (const T & item);
00170 
00172   void InsertBefore(Iterator &it, const T & item);
00173 
00175   void InsertAfter(Iterator &it, const T & item);
00176 
00178   void Delete (Iterator &it);
00179 
00181   void DeleteAll();
00182 
00184   const T& Front () const
00185   { return head->data; }
00187   const T& Last () const
00188   { return tail->data; }
00189 
00191   bool PopFront ()
00192   {
00193     if (!head)
00194       return false;
00195     Delete (head);
00196     return true;
00197   }
00198 
00200   bool PopBack ()
00201   {
00202     if (!tail)
00203       return false;
00204     Delete (tail);
00205     return true;
00206   }
00207 
00208 private:
00209   friend class Iterator;
00210   csListElement *head, *tail;
00211 };
00212 
00214 template <class T>
00215 inline csList<T>::csList(const csList<T> &other) : head(0), tail(0)
00216 {
00217   csListElement* e = other.head;
00218   while( e != 0)
00219   {
00220     PushBack (e->data);
00221     e = e->next;
00222   }
00223 }
00224 
00226 template <class T>
00227 inline csList<T>& csList<T>::operator= (const csList<T> &other)
00228 {
00229   DeleteAll ();
00230   csListElement* e = other.head;
00231   while(e != 0)
00232   {
00233     PushBack (e->data);
00234     e = e->next;
00235   }
00236   return *this;
00237 }
00238 
00240 template <class T>
00241 inline void csList<T>::DeleteAll ()
00242 {
00243   csListElement *cur = head, *next = 0;
00244   while(cur != 0)
00245   {
00246     next = cur->next;
00247     delete cur;
00248     cur = next;
00249   }
00250   head = tail = 0;
00251 }
00252 
00254 template <class T>
00255 inline typename csList<T>::Iterator csList<T>::PushBack (const T& item)
00256 {
00257   csListElement* el = new csListElement (item, 0, tail);
00258   if (tail)
00259     tail->next = el;
00260   else
00261     head = el;
00262   tail = el;
00263   return Iterator(el);
00264 }
00265 
00267 template <class T>
00268 inline typename csList<T>::Iterator csList<T>::PushFront (const T& item)
00269 {
00270   csListElement* el = new csListElement (item, head, 0);
00271   if (head)
00272     head->prev = el;
00273   else
00274     tail = el;
00275   head = el;
00276   return Iterator (el);
00277 }
00278 
00279 template <class T>
00280 inline void csList<T>::InsertBefore (Iterator &it, const T& item)
00281 {
00282   csListElement* el = it.ptr;
00283   csListElement* next = el->next;
00284   csListElement* prev = el;
00285   csListElement* newEl = new csListElement (item, next, prev);
00286   if (!next) // this is the last element
00287     tail = newEl;
00288   else
00289     el->next->prev = newEl;
00290   el->next = newEl;
00291 }
00292 
00293 template <class T>
00294 inline void csList<T>::InsertAfter (Iterator &it, const T& item)
00295 {
00296   csListElement* el = it.ptr;
00297   csListElement* next = el;
00298   csListElement* prev = el->prev;
00299   csListElement* newEl = new csListElement (item, next, prev);
00300   if (!prev) // this is the first element
00301     head = newEl;
00302   else
00303     el->prev->next = newEl;
00304   el->prev = newEl;
00305 }
00306 
00307 template <class T>
00308 inline void csList<T>::Delete (Iterator &it)
00309 {
00310   csListElement* el = it.ptr;
00311   if (!el)
00312     return;
00313 
00314   // Advance the iterator so we can delete the data its using
00315   if (it.IsReverse())
00316       --it;
00317   else
00318       ++it;
00319 
00320   Delete(el);
00321 }
00322 
00323 template <class T>
00324 inline void csList<T>::Delete (csListElement *el)
00325 {
00326   CS_ASSERT(el);
00327 
00328   // Fix the pointers of the 2 surrounding elements
00329   if (el->prev)
00330     el->prev->next = el->next;
00331   else
00332     head = el->next;
00333 
00334   if (el->next)
00335     el->next->prev = el->prev;
00336   else
00337     tail = el->prev;
00338 
00339   delete el;
00340 }
00341 
00342 #endif //__CS_UTIL_LIST_H__

Generated for Crystal Space by doxygen 1.2.18