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