Merge of itasc branch. Project files, scons and cmake should be working. Makefile...
[blender.git] / 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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 #ifndef __SG_DLIST
30 #define __SG_DLIST
31
32 #include <stdlib.h>
33
34 #ifdef WITH_CXX_GUARDEDALLOC
35 #include "MEM_guardedalloc.h"
36 #endif
37
38 /**
39  * Double circular linked list
40  */
41 class SG_DList
42 {
43 protected :
44         SG_DList* m_flink;
45         SG_DList* m_blink;
46
47 public:
48         template<typename T> class iterator
49         {
50         private:
51                 SG_DList&       m_head;
52                 T*                      m_current;
53         public:
54                 typedef iterator<T> _myT;
55                 iterator(SG_DList& head) : m_head(head), m_current(NULL) {}
56                 ~iterator() {}
57
58                 void begin()
59                 {
60                         m_current = (T*)m_head.Peek();
61                 }
62                 void back()
63                 {
64                         m_current = (T*)m_head.Back();
65                 }
66                 bool end()
67                 {
68                         return (m_current == (T*)m_head.Self());
69                 }
70                 bool add_back(T* item)
71                 {
72                         return m_current->AddBack(item);
73                 }
74                 T* operator*()
75                 {
76                         return m_current;
77                 }
78                 _myT& operator++()
79                 {
80                         // no check of NULL! make sure you don't try to increment beyond end
81                         m_current = (T*)m_current->Peek();
82                         return *this;
83                 }
84                 _myT& operator--()
85                 {
86                         // no check of NULL! make sure you don't try to increment beyond end
87                         m_current = (T*)m_current->Back();
88                         return *this;
89                 }
90         };
91
92         template<typename T> class const_iterator
93         {
94         private:
95                 const SG_DList& m_head;
96                 const T*                m_current;
97         public:
98                 typedef const_iterator<T> _myT;
99                 const_iterator(const SG_DList& head) : m_head(head), m_current(NULL) {}
100                 ~const_iterator() {}
101
102                 void begin()
103                 {
104                         m_current = (const T*)m_head.Peek();
105                 }
106                 void back()
107                 {
108                         m_current = (const T*)m_head.Back();
109                 }
110                 bool end()
111                 {
112                         return (m_current == (const T*)m_head.Self());
113                 }
114                 const T* operator*()
115                 {
116                         return m_current;
117                 }
118                 _myT& operator++()
119                 {
120                         // no check of NULL! make sure you don't try to increment beyond end
121                         m_current = (const T*)m_current->Peek();
122                         return *this;
123                 }
124                 _myT& operator--()
125                 {
126                         // no check of NULL! make sure you don't try to increment beyond end
127                         m_current = (const T*)m_current->Back();
128                         return *this;
129                 }
130         };
131
132     SG_DList() 
133     { 
134         m_flink = m_blink = this; 
135     }
136         SG_DList(const SG_DList& other)
137         {
138         m_flink = m_blink = this; 
139         }
140     virtual ~SG_DList() 
141     {
142                 Delink();
143     }
144
145     inline bool Empty()               // Check for empty queue
146     {     
147         return ( m_flink == this ); 
148     }
149     bool AddBack( SG_DList *item )  // Add to the back
150     {
151                 if (!item->Empty())
152                         return false;
153         item->m_blink = m_blink;
154         item->m_flink = this;
155         m_blink->m_flink = item;
156         m_blink = item;
157                 return true;
158     }
159     bool AddFront( SG_DList *item )  // Add to the back
160     {
161                 if (!item->Empty())
162                         return false;
163         item->m_flink = m_flink;
164         item->m_blink = this;
165         m_flink->m_blink = item;
166         m_flink = item;
167                 return true;
168     }
169     SG_DList *Remove()           // Remove from the front
170     {
171         if (Empty()) 
172         {
173             return NULL;
174         }
175         SG_DList* item = m_flink;
176         m_flink = item->m_flink;
177         m_flink->m_blink = this;
178         item->m_flink = item->m_blink = item;
179         return item;
180     }
181     bool Delink()             // Remove from the middle
182     {
183                 if (Empty())
184                         return false;
185                 m_blink->m_flink = m_flink;
186                 m_flink->m_blink = m_blink;
187                 m_flink = m_blink = this;
188                 return true;
189     }
190     inline SG_DList *Peek()                     // Look at front without removing
191     { 
192         return m_flink; 
193     }  
194     inline SG_DList *Back()                     // Look at front without removing
195     { 
196         return m_blink; 
197     }  
198     inline SG_DList *Self() 
199     { 
200         return this; 
201     }
202     inline const SG_DList *Peek() const                 // Look at front without removing
203     { 
204         return (const SG_DList*)m_flink; 
205     }  
206     inline const SG_DList *Back() const                 // Look at front without removing
207     { 
208         return (const SG_DList*)m_blink; 
209     }  
210     inline const SG_DList *Self() const 
211     { 
212         return this; 
213     }
214         
215         
216 #ifdef WITH_CXX_GUARDEDALLOC
217 public:
218         void *operator new( unsigned int num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_DList"); }
219         void operator delete( void *mem ) { MEM_freeN(mem); }
220 #endif
221 };
222
223 /**
224  * SG_DListHead : Template class that implements copy constructor to duplicate list automatically
225  *                The elements of the list must have themselves a copy constructor.
226  */
227 template<typename T> class SG_DListHead : public SG_DList
228 {
229 public:
230         typedef SG_DListHead<T> _myT;
231         SG_DListHead() : SG_DList() {}
232         SG_DListHead(const _myT& other) : SG_DList()
233         {
234                 // copy the list, assuming objects of type T
235                 const_iterator<T> eit(other);
236                 T* elem;
237                 for (eit.begin(); !eit.end(); ++eit) {
238                         elem = (*eit)->GetReplica();
239                         AddBack(elem);
240                 }
241         }
242         virtual ~SG_DListHead() {}
243     T* Remove()
244     {
245                 return static_cast<T*>(SG_DList::Remove());
246     }
247
248 };
249
250 #endif //__SG_DLIST
251