CrystalSpace

Public API Reference

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

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 
00023 /*
00024  * A lightweight template double-linked list.
00025  * This is VERY lightweight and not very tested, as it was writen for
00026  * one single purpose, and have not been extended to be more general
00027  */
00028 template <class T> class csList
00029 {
00030 protected:
00031   /* 
00032    * Template which describs the data stored in the linked list
00033    * For example a list of ints uses csListElement<int>
00034    */
00035   struct csListElement
00036   {
00038     csListElement(const T& d, csListElement* newnext,
00039                               csListElement* newprev)
00040       : next(newnext), prev(newprev), data(d)
00041     {}
00042   
00044     csListElement* next;
00045   
00047     csListElement* prev;
00048   
00050     T data;         
00051   };
00052 
00054   void Delete (csListElement *el);
00055 
00056 public:
00058   csList()
00059     : head(0), tail(0)
00060   {}
00061 
00063   csList(const csList &other);
00064 
00066   ~csList()
00067   { DeleteAll (); }
00068 
00070   class Iterator
00071   {
00072   public:
00073     Iterator()
00074       : 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 = NULL;
00111     }
00112 
00113     inline Iterator operator++(int)
00114     { 
00115       ptr = ptr->next;
00116       return Iterator(ptr);
00117     }
00118     inline Iterator operator--(int)
00119     { 
00120       ptr = ptr->prev;
00121       return Iterator(ptr);
00122     }
00123   protected:
00124     friend class csList;
00125     Iterator (csListElement* element)
00126       : ptr(element)
00127     { }
00128 
00129   private:
00130     csListElement* ptr;
00131     bool reversed;
00132   };
00133 
00135   csList &operator=(const csList& other);
00136 
00138   Iterator PushFront (const T & item);
00139   
00141   Iterator PushBack (const T & item);
00142 
00144   void Delete (Iterator &it);
00145 
00147   void DeleteAll();
00148 
00150   const T& Front () const
00151   { return head->data; }
00153   const T& Last () const
00154   { return tail->data; }
00155 
00157   bool PopFront ()
00158   {
00159     if (!head)
00160       return false;
00161 
00162     Delete (head);
00163     return true;
00164   }
00165   
00167   bool PopBack ()
00168   {
00169     if (!tail)
00170       return false;
00171     
00172     Delete (tail);
00173     return true;
00174   }
00175 
00176 private:
00177   friend class Iterator;
00178   csListElement *head, *tail;
00179 };
00180 
00182 template <class T> csList<T>::csList(const csList<T> &other)
00183   : head(0), tail(0)
00184 {
00185   csListElement* e = other.head;
00186   while( e != 0)
00187   {
00188     PushBack (e->data);
00189     e = e->next;
00190   }
00191 }
00192 
00194 template <class T> csList<T>& csList<T>::operator =(const csList<T> &other)
00195 {
00196   DeleteAll ();
00197 
00198   csListElement* e = other.head;
00199   while( e != 0)
00200   {
00201     PushBack (e->data);
00202     e = e->next;
00203   }
00204 
00205   return *this;
00206 }
00207 
00209 template <class T> void csList<T>::DeleteAll ()
00210 {
00211   csListElement *cur = head, *next = 0;
00212   
00213   while(cur != 0)
00214   {
00215     next = cur->next;
00216     delete cur;
00217     cur = next;
00218   }
00219   head = tail = 0;
00220 }
00221 
00223 template <class T> typename csList<T>::Iterator csList<T>::PushBack (const T& item)
00224 {
00225   csListElement* el = new csListElement (item, NULL, tail);
00226   if (tail)
00227     tail->next = el;
00228   else
00229     head = el;
00230   tail = el;
00231   
00232   return Iterator(el);
00233 }
00234 
00236 template <class T> typename csList<T>::Iterator csList<T>::PushFront (const T& item)
00237 {
00238   csListElement* el = new csListElement (item, head, NULL);
00239   if (head)
00240     head->prev = el;
00241   else
00242     tail = el;
00243   head = el;
00244   
00245   return Iterator (el);
00246 }
00247 
00248 
00249 template <class T> void csList<T>::Delete (Iterator &it)
00250 {
00251   csListElement* el = it.ptr;
00252 
00253   if (!el)
00254     return;
00255 
00256   // Advance the iterator so we can delete the data its using
00257   if (it.IsReverse())
00258       it--;
00259   else
00260       it++;
00261 
00262   Delete(el);
00263 }
00264 
00265 template <class T> void csList<T>::Delete (csListElement *el)
00266 {
00267   CS_ASSERT(el);
00268 
00269   // Fix the pointers of the 2 surrounding elements
00270   if (el->prev)
00271     el->prev->next = el->next;
00272   else
00273     head = el->next;
00274   
00275   if (el->next)
00276     el->next->prev = el->prev;
00277   else
00278     tail = el->prev;
00279 
00280   delete el;
00281 }
00282 
00283 #endif //__CS_UTIL_LIST_H__

Generated for Crystal Space by doxygen 1.2.14