source/gameengine/SceneGraph/SG_QList.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_QList.h
  31  *  \ingroup bgesg
  32  */
  33
  34 #ifndef __SG_QLIST
  35 #define __SG_QLIST
  36
  37 #include "SG_DList.h"
  38
  39 /**
  40  * Double-Double circular linked list
  41  * For storing an object is two lists simultaneously
  42  */
  43 class SG_QList : public SG_DList
  44 {
  45 protected :
  46         SG_QList* m_fqlink;
  47         SG_QList* m_bqlink;
  48
  49 public:
  50         template<typename T> class iterator
  51         {
  52         private:
  53                 SG_QList&       m_head;
  54                 T*                      m_current;
  55         public:
  56                 typedef iterator<T> _myT;
  57                 iterator(SG_QList& head, SG_QList* current=NULL) : m_head(head) { m_current = (T*)current; }
  58                 ~iterator() {}
  59
  60                 void begin()
  61                 {
  62                         m_current = (T*)m_head.QPeek();
  63                 }
  64                 void back()
  65                 {
  66                         m_current = (T*)m_head.QBack();
  67                 }
  68                 bool end()
  69                 {
  70                         return (m_current == (T*)m_head.Self());
  71                 }
  72                 bool add_back(T* item)
  73                 {
  74                         return m_current->QAddBack(item);
  75                 }
  76                 T* operator*()
  77                 {
  78                         return m_current;
  79                 }
  80                 _myT& operator++()
  81                 {
  82                         m_current = (T*)m_current->QPeek();
  83                         return *this;
  84                 }
  85                 _myT& operator--()
  86                 {
  87                         // no check on NULL! make sure you don't try to increment beyond end
  88                         m_current = (T*)m_current->QBack();
  89                         return *this;
  90                 }
  91         };
  92
  93         SG_QList() : SG_DList()
  94     {
  95         m_fqlink = m_bqlink = this;
  96     }
  97         SG_QList(const SG_QList& other) : SG_DList()
  98         {
  99         m_fqlink = m_bqlink = this;
 100         }
 101     virtual ~SG_QList()
 102     {
 103                 QDelink();
 104     }
 105
 106     inline bool QEmpty()               // Check for empty queue
 107     {
 108         return ( m_fqlink == this );
 109     }
 110     bool QAddBack( SG_QList *item )  // Add to the back
 111     {
 112                 if (!item->QEmpty())
 113                         return false;
 114         item->m_bqlink = m_bqlink;
 115         item->m_fqlink = this;
 116         m_bqlink->m_fqlink = item;
 117         m_bqlink = item;
 118                 return true;
 119     }
 120     bool QAddFront( SG_QList *item )  // Add to the back
 121     {
 122                 if (!item->Empty())
 123                         return false;
 124         item->m_fqlink = m_fqlink;
 125         item->m_bqlink = this;
 126         m_fqlink->m_bqlink = item;
 127         m_fqlink = item;
 128                 return true;
 129     }
 130     SG_QList *QRemove()           // Remove from the front
 131     {
 132         if (QEmpty())
 133         {
 134             return NULL;
 135         }
 136         SG_QList* item = m_fqlink;
 137         m_fqlink = item->m_fqlink;
 138         m_fqlink->m_bqlink = this;
 139         item->m_fqlink = item->m_bqlink = item;
 140         return item;
 141     }
 142     bool QDelink()             // Remove from the middle
 143     {
 144                 if (QEmpty())
 145                         return false;
 146                 m_bqlink->m_fqlink = m_fqlink;
 147                 m_fqlink->m_bqlink = m_bqlink;
 148                 m_fqlink = m_bqlink = this;
 149                 return true;
 150     }
 151     inline SG_QList *QPeek()                    // Look at front without removing
 152     {
 153         return m_fqlink;
 154     }
 155     inline SG_QList *QBack()                    // Look at front without removing
 156     {
 157         return m_bqlink;
 158     }
 159
 160
 161 #ifdef WITH_CXX_GUARDEDALLOC
 162 public:
 163         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_QList"); }
 164         void operator delete( void *mem ) { MEM_freeN(mem); }
 165 #endif
 166 };
 167
 168 #endif //__SG_QLIST
 169