BGE performance, 3rd round: culling and rasterizer.
[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) : m_head(head), m_current(NULL) {}
53                 ~iterator() {}
54
55                 void begin()
56                 {
57                         m_current = (T*)m_head.QPeek();
58                         if (m_current == (T*)m_head.Self())
59                         {
60                                 m_current = NULL;
61                         }
62                 }
63                 bool end()
64                 {
65                         return (NULL == m_current);
66                 }
67                 T* operator*()
68                 {
69                         return m_current;
70                 }
71                 _myT& operator++()
72                 {
73                         assert(m_current);
74                         m_current = (T*)m_current->QPeek();
75                         if (m_current == (T*)m_head.Self())
76                         {
77                                 m_current = NULL;
78                         }
79                         return *this;
80                 }
81         };
82
83         SG_QList() : SG_DList()
84     { 
85         m_fqlink = m_bqlink = this; 
86     }
87         SG_QList(const SG_QList& other) : SG_DList()
88         {
89         m_fqlink = m_bqlink = this; 
90         }
91     virtual ~SG_QList() 
92     {
93                 QDelink();
94     }
95
96     inline bool QEmpty()               // Check for empty queue
97     {     
98         return ( m_fqlink == this ); 
99     }
100     bool QAddBack( SG_QList *item )  // Add to the back
101     {
102                 if (!item->QEmpty())
103                         return false;
104         item->m_bqlink = m_bqlink;
105         item->m_fqlink = this;
106         m_bqlink->m_fqlink = item;
107         m_bqlink = item;
108                 return true;
109     }
110     bool QAddFront( SG_QList *item )  // Add to the back
111     {
112                 if (!item->Empty())
113                         return false;
114         item->m_fqlink = m_fqlink;
115         item->m_bqlink = this;
116         m_fqlink->m_bqlink = item;
117         m_fqlink = item;
118                 return true;
119     }
120     SG_QList *QRemove()           // Remove from the front
121     {
122         if (QEmpty()) 
123         {
124             return NULL;
125         }
126         SG_QList* item = m_fqlink;
127         m_fqlink = item->m_fqlink;
128         m_fqlink->m_bqlink = this;
129         item->m_fqlink = item->m_bqlink = item;
130         return item;
131     }
132     void QDelink()             // Remove from the middle
133     {
134                 if (!QEmpty())
135                 {
136                         m_bqlink->m_fqlink = m_fqlink;
137                         m_fqlink->m_bqlink = m_bqlink;
138                         m_fqlink = m_bqlink = this;
139                 }
140     }
141     inline SG_QList *QPeek()                    // Look at front without removing
142     { 
143         return m_fqlink; 
144     }  
145 };
146
147 #endif //__SG_QLIST
148