b82e51e0d2f8b411714cbfc11768d349146cfdb6
[blender-staging.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., 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