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