style cleanyp
[blender.git] / intern / container / CTR_UHeap.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file container/CTR_UHeap.h
29  *  \ingroup ctr
30  */
31
32
33 /**
34
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 __CTR_UHEAP_H__
48 #define __CTR_UHEAP_H__
49
50 #include <vector>
51
52 #include "MEM_NonCopyable.h"
53
54 class CTR_UHeapable {
55
56 public:
57         int &
58         HeapPos(
59             ) {
60                 return m_ind;
61         };
62         float &
63         HeapKey(
64             ) {
65                 return m_key;
66         };
67
68         const 
69         float &
70         HeapKey(
71             ) const {
72                 return m_key;
73         };
74
75         const 
76         int &
77         HeapPos(
78             ) const {
79                 return m_ind;
80         };
81
82 private:
83
84         float m_key;
85         int m_ind;
86
87 protected:
88
89         CTR_UHeapable(
90             ) : m_key(0),
91                 m_ind(0)
92         {
93         };
94
95         ~CTR_UHeapable(
96             ) {
97         };
98 };
99         
100 template <class HeapType>       
101 class CTR_UHeap : public MEM_NonCopyable
102 {
103
104 public:         
105
106         static
107         CTR_UHeap *
108         New(
109             ) {
110                 return new CTR_UHeap();
111         }
112
113         void
114         MakeHeap(
115             HeapType *base
116             ) {
117                 int i;
118                 int start = Parent(m_vector.size() - 1);
119                 for (i = start; i >= 0; --i) {
120                         DownHeap(base, i);
121                 }
122         }; 
123         
124         void
125         Insert(
126             HeapType *base,
127             int elem
128             ) {
129                 // add element to vector
130                 m_vector.push_back(elem);
131                 base[elem].HeapPos() = m_vector.size() - 1;
132
133                 // push the element up the heap
134                 UpHeap(base, m_vector.size() - 1);
135         }
136
137         // access to the vector for initial loading of elements
138
139         std::vector<int> &
140         HeapVector(
141             ) {
142                 return m_vector;
143         };
144
145
146         void
147         Remove(
148             HeapType *base,
149             int i
150             ) {
151         
152                 // exchange with last element - pop last
153                 // element and move up or down the heap as appropriate
154                 if (m_vector.empty()) {
155                         assert(false);
156                 }
157
158                 if (i != int(m_vector.size()) - 1) {
159                         
160                         Swap(base, i, m_vector.size() - 1);
161                         m_vector.pop_back();
162
163                         if (!m_vector.empty()) {
164                                 UpHeap(base, i);
165                                 DownHeap(base, i);
166                         }
167                 }
168                 else {
169                         m_vector.pop_back();
170                 }
171         }
172
173         int
174         Top(
175             ) const {
176                 if (m_vector.empty()) return -1;
177                 return m_vector[0];
178         }
179                 
180
181         void
182         SC_Heap(
183             HeapType *base
184             ) {
185                 int i;
186                 for (i = 1; i < int(m_vector.size()); i++) {
187                         
188                         CTR_UHeapable *elem = base + m_vector[i];
189                         CTR_UHeapable *p_elem = base + m_vector[Parent(i)];
190
191                         assert(p_elem->HeapKey() >= elem->HeapKey());
192                         assert(elem->HeapPos() == i);
193                 }
194
195         };
196                         
197
198         ~CTR_UHeap(
199             ) {
200         };      
201
202
203 private:
204
205         CTR_UHeap(
206             ) {
207         };
208
209
210         std::vector<int> m_vector;
211                 
212 private:
213         void
214         Swap(
215             HeapType *base,
216             int i,
217             int j
218             ) {
219                 std::swap(m_vector[i], m_vector[j]);
220                 
221                 CTR_UHeapable *heap_i = base + m_vector[i];
222                 CTR_UHeapable *heap_j = base + m_vector[j];
223                 
224                 // Exchange heap positions
225                 heap_i->HeapPos() = i;
226                 heap_j->HeapPos() = j;
227         }
228
229         int
230         Parent(
231             unsigned int i
232             ) {
233                 return (i - 1) >> 1;
234         }
235         int
236         Left(
237             int i
238             ) {
239                 return (i << 1) + 1;
240         }
241
242         int
243         Right(
244             int i
245             ) {
246                 return (i << 1) + 2;
247         }
248
249         float
250         HeapVal(
251             HeapType *base,
252             int i
253             ) {
254                 return base[m_vector[i]].HeapKey();
255         }
256
257         void
258         DownHeap(
259             HeapType *base,
260             int i
261             ) {
262                 int heap_size = m_vector.size();
263
264                 int l = Left(i);
265                 int r = Right(i);
266
267                 int largest;
268                 if (l < heap_size && HeapVal(base, l) > HeapVal(base, i)) {
269                         largest = l;
270                 }
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