Initial revision
[blender.git] / intern / container / CTR_UHeap.h
1 /**
2  * $Id$
3  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version. The Blender
9  * Foundation also sells licenses for use in proprietary software under
10  * the Blender License.  See http://www.blender.org/BL/ for information
11  * about this.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL/BL DUAL LICENSE BLOCK *****
30  */
31
32 /**
33
34  * $Id$
35  * Copyright (C) 2001 NaN Technologies B.V.
36  *
37  * @author Laurence
38  * @mainpage CTR_UHeap an updatable heap template class (also
39  * known as an updatable priority queue)
40  *
41  * Todo: Make CTR_UHeapable a template class with m_key the
42  * template parameter, so that arbitrary value types with
43  * operators (=,>) defined can be used.
44  *
45  */
46
47 #ifndef NAN_INCLUDED_CTR_UHeap_h
48 #define NAN_INCLUDED_CTR_UHeap_h
49
50 #include <vector>
51 #include "MEM_NonCopyable.h"
52
53 class CTR_UHeapable {
54
55 public :
56                 int &
57         HeapPos(
58         ){
59                 return m_ind;
60         };
61                 float &
62         HeapKey(
63         ) {
64                 return m_key;
65         };
66
67         const 
68                 float &
69         HeapKey(
70         ) const {
71                 return m_key;
72         };
73
74         const 
75                 int &
76         HeapPos(
77         ) const {
78                 return m_ind;
79         };
80
81 private :
82
83         float m_key;
84         int m_ind;
85
86 protected :
87
88         CTR_UHeapable(
89         ) : m_key (0),
90                 m_ind (0)
91         {
92         };
93
94         ~CTR_UHeapable(
95         ){
96         };
97 };
98         
99 template <class HeapType>       
100 class CTR_UHeap : public MEM_NonCopyable
101 {
102
103 public:         
104
105         static
106                 CTR_UHeap *
107         New(
108         ) {
109                 return new CTR_UHeap();
110         }
111
112                 void
113         MakeHeap(
114                 HeapType *base
115         ) {
116                 int i;
117                 int start = Parent(m_vector.size()-1);
118                 for (i = start; i >=0; --i) {
119                         DownHeap(base,i);
120                 }
121         }; 
122         
123                 void
124         Insert(
125                 HeapType *base,
126                 int elem
127         ) {
128                 // add element to vector
129                 m_vector.push_back(elem);
130                 base[elem].HeapPos() = m_vector.size()-1;
131
132                 // push the element up the heap
133                 UpHeap(base,m_vector.size()-1);
134         }
135
136         // access to the vector for initial loading of elements
137
138                 std::vector<int> &
139         HeapVector(
140         ) {
141                 return m_vector;
142         };
143
144
145                 void
146         Remove(
147                 HeapType *base,
148                 int i
149         ) {
150         
151                 // exchange with last element - pop last
152                 // element and move up or down the heap as appropriate
153                 if (m_vector.empty()) {
154                         assert(false);
155                 }
156
157                 if (i  != int(m_vector.size())-1) {
158                         
159                         Swap(base,i,m_vector.size() - 1);
160                         m_vector.pop_back();
161
162                         if (!m_vector.empty()) {
163                                 UpHeap(base,i);
164                                 DownHeap(base,i);
165                         }
166                 } else {
167                         m_vector.pop_back();
168                 }
169         }
170
171                 int
172         Top(
173         ) const {
174                 if (m_vector.empty()) return -1;
175                 return m_vector[0];
176         }
177                 
178
179                 void
180         SC_Heap(
181                 HeapType *base
182         ) {
183                 int i;
184                 for (i = 1; i < int(m_vector.size()) ; i++) {
185                         
186                         CTR_UHeapable * elem = base + m_vector[i];                      
187                         CTR_UHeapable * p_elem = base + m_vector[Parent(i)];                    
188
189                         assert(p_elem->HeapKey() >= elem->HeapKey());
190                         assert(elem->HeapPos() == i);
191                 }
192
193         };
194                         
195
196         ~CTR_UHeap(
197         ) {
198         };      
199
200
201 private:
202
203         CTR_UHeap(
204         ) {
205         };
206
207
208         std::vector<int> m_vector;
209                 
210 private:
211                 void 
212         Swap(
213                 HeapType *base,
214                 int i, 
215                 int j
216         ){
217                 std::swap(m_vector[i],m_vector[j]);
218                 
219                 CTR_UHeapable *heap_i = base + m_vector[i];
220                 CTR_UHeapable *heap_j = base + m_vector[j];
221                 
222                 // Exchange heap positions
223                 heap_i->HeapPos() = i;
224                 heap_j->HeapPos() = j;
225         }
226
227                 int 
228         Parent(
229                 unsigned int i
230         ) {
231                  return (i-1) >> 1; 
232         }
233                 int 
234         Left(
235                 int i
236         ) {
237                 return (i<<1)+1; 
238         }
239
240                 int 
241         Right(
242                 int i
243         ) {
244                 return (i<<1)+2;
245         }
246
247                 float
248         HeapVal(
249                 HeapType *base,
250                 int i
251         ) {
252                 return base[m_vector[i]].HeapKey();
253         }
254
255                 void
256         DownHeap(
257                 HeapType *base,         
258                 int i
259         ) {
260                 int heap_size = m_vector.size();
261
262                 int l = Left(i);
263                 int r = Right(i);
264
265                 int largest;
266                 if (l < heap_size && HeapVal(base,l) > HeapVal(base,i)) {
267                         largest = l;
268                 } else {
269                         largest = i;
270                 }
271
272                 if (r < heap_size && HeapVal(base,r) > HeapVal(base,largest)) {
273                         largest = r;
274                 }       
275
276                 if (largest != i) {
277                         // exchange i and largest
278                         Swap(base,i,largest);
279                         DownHeap(base,largest);
280                 }
281         }
282
283                 void
284         UpHeap(
285                 HeapType *base,
286                 int i
287         ) {
288
289                 // swap parents untill it's found a place in the heap < it's parent or
290                 // top of heap
291
292                 while (i > 0) {
293                         int p = Parent(i);
294                         if (HeapVal(base,i) < HeapVal(base,p)) {
295                                 break;
296                         }
297                         Swap(base,p,i);
298                         i = p;
299                 }
300         }               
301 };
302
303 #endif