CrystalSpace

Public API Reference

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

list.h

00001 /*
00002     Copyright (C) 2003 by Mårten 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:
00032   /* 
00033    * Template which describs the data stored in the linked list
00034    * For example a list of ints uses csListElement<int>
00035    */
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:
00074     Iterator() : ptr(0)
00075     { }
00076     Iterator(const Iterator& other)
00077     { ptr = other.ptr; }
00078     Iterator(const csList<T> &list, bool reverse = false) 
00079     {
00080       reversed=reverse;
00081       if(reverse) ptr = list.tail;
00082       else ptr = list.head;
00083     }
00084     const Iterator& operator= (const Iterator& other)
00085     { ptr = other.ptr; return *this; }
00086 
00087     bool HasCurrent() const
00088     { return ptr != 0; }
00089     bool HasNext() const
00090     { return ptr && ptr->next; }
00091     bool HasPrevious() const
00092     { return ptr && ptr->prev; }
00093     bool IsFirst() const
00094     { return ptr && ptr->prev == 0; }
00095     bool IsLast() const
00096     { return ptr && ptr->next == 0; }
00097     bool IsReverse() const
00098     { return reversed; }
00099 
00100     operator T*() const
00101     { return &ptr->data; }
00102     T &operator *() const
00103     { return ptr->data; }
00104     T *operator->() const
00105     { return &ptr->data; }
00106 
00108     inline void Clear ()
00109     {
00110       ptr = 0;
00111     }
00112 
00113     inline T* Next ()
00114     {
00115       ptr = ptr->next;
00116       return *this;
00117     }
00118 
00119     inline Iterator& operator++()
00120     { 
00121       ptr = ptr->next;
00122       return *this;
00123     }
00124     inline Iterator& operator--()
00125     { 
00126       ptr = ptr->prev;
00127       return *this;
00128     }
00129   protected:
00130     friend class csList;
00131     Iterator (csListElement* element)
00132       : ptr(element)
00133     { }
00134 
00135   private:
00136     csListElement* ptr;
00137     bool reversed;
00138   };
00139 
00141   csList &operator=(const csList& other);
00142 
00144   Iterator PushFront (const T & item);
00145   
00147   Iterator PushBack (const T & item);
00148 
00150   void Delete (Iterator &it);
00151 
00153   void DeleteAll();
00154 
00156   const T& Front () const
00157   { return head->data; }
00159   const T& Last () const
00160   { return tail->data; }
00161 
00163   bool PopFront ()
00164   {
00165     if (!head)
00166       return false;
00167 
00168     Delete (head);
00169     return true;
00170   }
00171   
00173   bool PopBack ()
00174   {
00175     if (!tail)
00176       return false;
00177     
00178     Delete (tail);
00179     return true;
00180   }
00181 
00182 private:
00183   friend class Iterator;
00184   csListElement *head, *tail;
00185 };
00186 
00188 template <class T> csList<T>::csList(const csList<T> &other)
00189   : head(0), tail(0)
00190 {
00191   csListElement* e = other.head;
00192   while( e != 0)
00193   {
00194     PushBack (e->data);
00195     e = e->next;
00196   }
00197 }
00198 
00200 template <class T> csList<T>& csList<T>::operator =(const csList<T> &other)
00201 {
00202   DeleteAll ();
00203 
00204   csListElement* e = other.head;
00205   while( e != 0)
00206   {
00207     PushBack (e->data);
00208     e = e->next;
00209   }
00210 
00211   return *this;
00212 }
00213 
00215 template <class T> void csList<T>::DeleteAll ()
00216 {
00217   csListElement *cur = head, *next = 0;
00218   
00219   while(cur != 0)
00220   {
00221     next = cur->next;
00222     delete cur;
00223     cur = next;
00224   }
00225   head = tail = 0;
00226 }
00227 
00229 template <class T> typename csList<T>::Iterator csList<T>::PushBack (
00230         const T& item)
00231 {
00232   csListElement* el = new csListElement (item, 0, tail);
00233   if (tail)
00234     tail->next = el;
00235   else
00236     head = el;
00237   tail = el;
00238   
00239   return Iterator(el);
00240 }
00241 
00243 template <class T> typename csList<T>::Iterator csList<T>::PushFront (
00244         const T& item)
00245 {
00246   csListElement* el = new csListElement (item, head, 0);
00247   if (head)
00248     head->prev = el;
00249   else
00250     tail = el;
00251   head = el;
00252   
00253   return Iterator (el);
00254 }
00255 
00256 
00257 template <class T> void csList<T>::Delete (Iterator &it)
00258 {
00259   csListElement* el = it.ptr;
00260 
00261   if (!el)
00262     return;
00263 
00264   // Advance the iterator so we can delete the data its using
00265   if (it.IsReverse())
00266       --it;
00267   else
00268       ++it;
00269 
00270   Delete(el);
00271 }
00272 
00273 template <class T> void csList<T>::Delete (csListElement *el)
00274 {
00275   CS_ASSERT(el);
00276 
00277   // Fix the pointers of the 2 surrounding elements
00278   if (el->prev)
00279     el->prev->next = el->next;
00280   else
00281     head = el->next;
00282   
00283   if (el->next)
00284     el->next->prev = el->prev;
00285   else
00286     tail = el->prev;
00287 
00288   delete el;
00289 }
00290 
00291 #endif //__CS_UTIL_LIST_H__

Generated for Crystal Space by doxygen 1.2.14