Yes I did it again ;)
[blender-staging.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
52 #ifdef HAVE_CONFIG_H
53 #include <config.h>
54 #endif
55
56 #include "MEM_NonCopyable.h"
57
58 class CTR_UHeapable {
59
60 public :
61                 int &
62         HeapPos(
63         ){
64                 return m_ind;
65         };
66                 float &
67         HeapKey(
68         ) {
69                 return m_key;
70         };
71
72         const 
73                 float &
74         HeapKey(
75         ) const {
76                 return m_key;
77         };
78
79         const 
80                 int &
81         HeapPos(
82         ) const {
83                 return m_ind;
84         };
85
86 private :
87
88         float m_key;
89         int m_ind;
90
91 protected :
92
93         CTR_UHeapable(
94         ) : m_key (0),
95                 m_ind (0)
96         {
97         };
98
99         ~CTR_UHeapable(
100         ){
101         };
102 };
103         
104 template <class HeapType>       
105 class CTR_UHeap : public MEM_NonCopyable
106 {
107
108 public:         
109
110         static
111                 CTR_UHeap *
112         New(
113         ) {
114                 return new CTR_UHeap();
115         }
116
117                 void
118         MakeHeap(
119                 HeapType *base
120         ) {
121                 int i;
122                 int start = Parent(m_vector.size()-1);
123                 for (i = start; i >=0; --i) {
124                         DownHeap(base,i);
125                 }
126         }; 
127         
128                 void
129         Insert(
130                 HeapType *base,
131                 int elem
132         ) {
133                 // add element to vector
134                 m_vector.push_back(elem);
135                 base[elem].HeapPos() = m_vector.size()-1;
136
137                 // push the element up the heap
138                 UpHeap(base,m_vector.size()-1);
139         }
140
141         // access to the vector for initial loading of elements
142
143                 std::vector<int> &
144         HeapVector(
145         ) {
146                 return m_vector;
147         };
148
149
150                 void
151         Remove(
152                 HeapType *base,
153                 int i
154         ) {
155         
156                 // exchange with last element - pop last
157                 // element and move up or down the heap as appropriate
158                 if (m_vector.empty()) {
159                         assert(false);
160                 }
161
162                 if (i  != int(m_vector.size())-1) {
163                         
164                         Swap(base,i,m_vector.size() - 1);
165                         m_vector.pop_back();
166
167                         if (!m_vector.empty()) {
168                                 UpHeap(base,i);
169                                 DownHeap(base,i);
170                         }
171                 } else {
172                         m_vector.pop_back();
173                 }
174         }
175
176                 int
177         Top(
178         ) const {
179                 if (m_vector.empty()) return -1;
180                 return m_vector[0];
181         }
182                 
183
184                 void
185         SC_Heap(
186                 HeapType *base
187         ) {
188                 int i;
189                 for (i = 1; i < int(m_vector.size()) ; i++) {
190                         
191                         CTR_UHeapable * elem = base + m_vector[i];                      
192                         CTR_UHeapable * p_elem = base + m_vector[Parent(i)];                    
193
194                         assert(p_elem->HeapKey() >= elem->HeapKey());
195                         assert(elem->HeapPos() == i);
196                 }
197
198         };
199                         
200
201         ~CTR_UHeap(
202         ) {
203         };      
204
205
206 private:
207
208         CTR_UHeap(
209         ) {
210         };
211
212
213         std::vector<int> m_vector;
214                 
215 private:
216                 void 
217         Swap(
218                 HeapType *base,
219                 int i, 
220                 int j
221         ){
222                 std::swap(m_vector[i],m_vector[j]);
223                 
224                 CTR_UHeapable *heap_i = base + m_vector[i];
225                 CTR_UHeapable *heap_j = base + m_vector[j];
226                 
227                 // Exchange heap positions
228                 heap_i->HeapPos() = i;
229                 heap_j->HeapPos() = j;
230         }
231
232                 int 
233         Parent(
234                 unsigned int i
235         ) {
236                  return (i-1) >> 1; 
237         }
238                 int 
239         Left(
240                 int i
241         ) {
242                 return (i<<1)+1; 
243         }
244
245                 int 
246         Right(
247                 int i
248         ) {
249                 return (i<<1)+2;
250         }
251
252                 float
253         HeapVal(
254                 HeapType *base,
255                 int i
256         ) {
257                 return base[m_vector[i]].HeapKey();
258         }
259
260                 void
261         DownHeap(
262                 HeapType *base,         
263                 int i
264         ) {
265                 int heap_size = m_vector.size();
266
267                 int l = Left(i);
268                 int r = Right(i);
269
270                 int largest;
271                 if (l < heap_size && HeapVal(base,l) > HeapVal(base,i)) {
272                         largest = l;
273                 } else {
274                         largest = i;
275                 }
276
277                 if (r < heap_size && HeapVal(base,r) > HeapVal(base,largest)) {
278                         largest = r;
279                 }       
280
281                 if (largest != i) {
282                         // exchange i and largest
283                         Swap(base,i,largest);
284                         DownHeap(base,largest);
285                 }
286         }
287
288                 void
289         UpHeap(
290                 HeapType *base,
291                 int i
292         ) {
293
294                 // swap parents untill it's found a place in the heap < it's parent or
295                 // top of heap
296
297                 while (i > 0) {
298                         int p = Parent(i);
299                         if (HeapVal(base,i) < HeapVal(base,p)) {
300                                 break;
301                         }
302                         Swap(base,p,i);
303                         i = p;
304                 }
305         }               
306 };
307
308 #endif
309