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