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