de79c35821e9a365d8d3f1183fe930a5401d6e13
[blender-staging.git] / 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