* Added a bit more 'padding' around the node sockets, so there's a
[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 #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                 } else {
168                         m_vector.pop_back();
169                 }
170         }
171
172                 int
173         Top(
174         ) const {
175                 if (m_vector.empty()) return -1;
176                 return m_vector[0];
177         }
178                 
179
180                 void
181         SC_Heap(
182                 HeapType *base
183         ) {
184                 int i;
185                 for (i = 1; i < int(m_vector.size()) ; i++) {
186                         
187                         CTR_UHeapable * elem = base + m_vector[i];                      
188                         CTR_UHeapable * p_elem = base + m_vector[Parent(i)];                    
189
190                         assert(p_elem->HeapKey() >= elem->HeapKey());
191                         assert(elem->HeapPos() == i);
192                 }
193
194         };
195                         
196
197         ~CTR_UHeap(
198         ) {
199         };      
200
201
202 private:
203
204         CTR_UHeap(
205         ) {
206         };
207
208
209         std::vector<int> m_vector;
210                 
211 private:
212                 void 
213         Swap(
214                 HeapType *base,
215                 int i, 
216                 int j
217         ){
218                 std::swap(m_vector[i],m_vector[j]);
219                 
220                 CTR_UHeapable *heap_i = base + m_vector[i];
221                 CTR_UHeapable *heap_j = base + m_vector[j];
222                 
223                 // Exchange heap positions
224                 heap_i->HeapPos() = i;
225                 heap_j->HeapPos() = j;
226         }
227
228                 int 
229         Parent(
230                 unsigned int i
231         ) {
232                  return (i-1) >> 1; 
233         }
234                 int 
235         Left(
236                 int i
237         ) {
238                 return (i<<1)+1; 
239         }
240
241                 int 
242         Right(
243                 int i
244         ) {
245                 return (i<<1)+2;
246         }
247
248                 float
249         HeapVal(
250                 HeapType *base,
251                 int i
252         ) {
253                 return base[m_vector[i]].HeapKey();
254         }
255
256                 void
257         DownHeap(
258                 HeapType *base,         
259                 int i
260         ) {
261                 int heap_size = m_vector.size();
262
263                 int l = Left(i);
264                 int r = Right(i);
265
266                 int largest;
267                 if (l < heap_size && HeapVal(base,l) > HeapVal(base,i)) {
268                         largest = l;
269                 } else {
270                         largest = i;
271                 }
272
273                 if (r < heap_size && HeapVal(base,r) > HeapVal(base,largest)) {
274                         largest = r;
275                 }       
276
277                 if (largest != i) {
278                         // exchange i and largest
279                         Swap(base,i,largest);
280                         DownHeap(base,largest);
281                 }
282         }
283
284                 void
285         UpHeap(
286                 HeapType *base,
287                 int i
288         ) {
289
290                 // swap parents untill it's found a place in the heap < it's parent or
291                 // top of heap
292
293                 while (i > 0) {
294                         int p = Parent(i);
295                         if (HeapVal(base,i) < HeapVal(base,p)) {
296                                 break;
297                         }
298                         Swap(base,p,i);
299                         i = p;
300                 }
301         }               
302 };
303
304 #endif
305