source/gameengine/SceneGraph/SG_DList.h

   1 /*
   2  * $Id$
   3  *
   4  * ***** BEGIN GPL LICENSE BLOCK *****
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version 2
   9  * of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19  *
  20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  21  * All rights reserved.
  22  *
  23  * The Original Code is: all of this file.
  24  *
  25  * Contributor(s): none yet.
  26  *
  27  * ***** END GPL LICENSE BLOCK *****
  28  */
  29
  30 /** \file SG_DList.h
  31  *  \ingroup bgesg
  32  */
  33
  34 #ifndef __SG_DLIST
  35 #define __SG_DLIST
  36
  37 #include <stdlib.h>
  38
  39 #ifdef WITH_CXX_GUARDEDALLOC
  40 #include "MEM_guardedalloc.h"
  41 #endif
  42
  43 /**
  44  * Double circular linked list
  45  */
  46 class SG_DList
  47 {
  48 protected :
  49         SG_DList* m_flink;
  50         SG_DList* m_blink;
  51
  52 public:
  53         template<typename T> class iterator
  54         {
  55         private:
  56                 SG_DList&       m_head;
  57                 T*                      m_current;
  58         public:
  59                 typedef iterator<T> _myT;
  60                 iterator(SG_DList& head) : m_head(head), m_current(NULL) {}
  61                 ~iterator() {}
  62
  63                 void begin()
  64                 {
  65                         m_current = (T*)m_head.Peek();
  66                 }
  67                 void back()
  68                 {
  69                         m_current = (T*)m_head.Back();
  70                 }
  71                 bool end()
  72                 {
  73                         return (m_current == (T*)m_head.Self());
  74                 }
  75                 bool add_back(T* item)
  76                 {
  77                         return m_current->AddBack(item);
  78                 }
  79                 T* operator*()
  80                 {
  81                         return m_current;
  82                 }
  83                 _myT& operator++()
  84                 {
  85                         // no check of NULL! make sure you don't try to increment beyond end
  86                         m_current = (T*)m_current->Peek();
  87                         return *this;
  88                 }
  89                 _myT& operator--()
  90                 {
  91                         // no check of NULL! make sure you don't try to increment beyond end
  92                         m_current = (T*)m_current->Back();
  93                         return *this;
  94                 }
  95         };
  96
  97         template<typename T> class const_iterator
  98         {
  99         private:
 100                 const SG_DList& m_head;
 101                 const T*                m_current;
 102         public:
 103                 typedef const_iterator<T> _myT;
 104                 const_iterator(const SG_DList& head) : m_head(head), m_current(NULL) {}
 105                 ~const_iterator() {}
 106
 107                 void begin()
 108                 {
 109                         m_current = (const T*)m_head.Peek();
 110                 }
 111                 void back()
 112                 {
 113                         m_current = (const T*)m_head.Back();
 114                 }
 115                 bool end()
 116                 {
 117                         return (m_current == (const T*)m_head.Self());
 118                 }
 119                 const T* operator*()
 120                 {
 121                         return m_current;
 122                 }
 123                 _myT& operator++()
 124                 {
 125                         // no check of NULL! make sure you don't try to increment beyond end
 126                         m_current = (const T*)m_current->Peek();
 127                         return *this;
 128                 }
 129                 _myT& operator--()
 130                 {
 131                         // no check of NULL! make sure you don't try to increment beyond end
 132                         m_current = (const T*)m_current->Back();
 133                         return *this;
 134                 }
 135         };
 136
 137     SG_DList()
 138     {
 139         m_flink = m_blink = this;
 140     }
 141         SG_DList(const SG_DList& other)
 142         {
 143         m_flink = m_blink = this;
 144         }
 145     virtual ~SG_DList()
 146     {
 147                 Delink();
 148     }
 149
 150     inline bool Empty()               // Check for empty queue
 151     {
 152         return ( m_flink == this );
 153     }
 154     bool AddBack( SG_DList *item )  // Add to the back
 155     {
 156                 if (!item->Empty())
 157                         return false;
 158         item->m_blink = m_blink;
 159         item->m_flink = this;
 160         m_blink->m_flink = item;
 161         m_blink = item;
 162                 return true;
 163     }
 164     bool AddFront( SG_DList *item )  // Add to the back
 165     {
 166                 if (!item->Empty())
 167                         return false;
 168         item->m_flink = m_flink;
 169         item->m_blink = this;
 170         m_flink->m_blink = item;
 171         m_flink = item;
 172                 return true;
 173     }
 174     SG_DList *Remove()           // Remove from the front
 175     {
 176         if (Empty())
 177         {
 178             return NULL;
 179         }
 180         SG_DList* item = m_flink;
 181         m_flink = item->m_flink;
 182         m_flink->m_blink = this;
 183         item->m_flink = item->m_blink = item;
 184         return item;
 185     }
 186     bool Delink()             // Remove from the middle
 187     {
 188                 if (Empty())
 189                         return false;
 190                 m_blink->m_flink = m_flink;
 191                 m_flink->m_blink = m_blink;
 192                 m_flink = m_blink = this;
 193                 return true;
 194     }
 195     inline SG_DList *Peek()                     // Look at front without removing
 196     {
 197         return m_flink;
 198     }
 199     inline SG_DList *Back()                     // Look at front without removing
 200     {
 201         return m_blink;
 202     }
 203     inline SG_DList *Self()
 204     {
 205         return this;
 206     }
 207     inline const SG_DList *Peek() const                 // Look at front without removing
 208     {
 209         return (const SG_DList*)m_flink;
 210     }
 211     inline const SG_DList *Back() const                 // Look at front without removing
 212     {
 213         return (const SG_DList*)m_blink;
 214     }
 215     inline const SG_DList *Self() const
 216     {
 217         return this;
 218     }
 219
 220
 221 #ifdef WITH_CXX_GUARDEDALLOC
 222 public:
 223         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_DList"); }
 224         void operator delete( void *mem ) { MEM_freeN(mem); }
 225 #endif
 226 };
 227
 228 /**
 229  * SG_DListHead : Template class that implements copy constructor to duplicate list automatically
 230  *                The elements of the list must have themselves a copy constructor.
 231  */
 232 template<typename T> class SG_DListHead : public SG_DList
 233 {
 234 public:
 235         typedef SG_DListHead<T> _myT;
 236         SG_DListHead() : SG_DList() {}
 237         SG_DListHead(const _myT& other) : SG_DList()
 238         {
 239                 // copy the list, assuming objects of type T
 240                 const_iterator<T> eit(other);
 241                 T* elem;
 242                 for (eit.begin(); !eit.end(); ++eit) {
 243                         elem = (*eit)->GetReplica();
 244                         AddBack(elem);
 245                 }
 246         }
 247         virtual ~SG_DListHead() {}
 248     T* Remove()
 249     {
 250                 return static_cast<T*>(SG_DList::Remove());
 251     }
 252
 253 };
 254
 255 #endif //__SG_DLIST
 256