QGIS API Documentation 3.39.0-Master (f549811d78c)
Loading...
Searching...
No Matches
priorityqueue.cpp
Go to the documentation of this file.
1/*
2 * libpal - Automated Placement of Labels Library
3 *
4 * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5 * University of Applied Sciences, Western Switzerland
6 * http://www.hes-so.ch
7 *
8 * Contact:
9 * maxence.laurent <at> heig-vd <dot> ch
10 * or
11 * eric.taillard <at> heig-vd <dot> ch
12 *
13 * This file is part of libpal.
14 *
15 * libpal is free software: you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation, either version 3 of the License, or
18 * (at your option) any later version.
19 *
20 * libpal is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
24 *
25 * You should have received a copy of the GNU General Public License
26 * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27 *
28 */
29
30#include <cstdio>
31
32#include "internalexception.h"
33#include "priorityqueue.h"
34
35using namespace pal;
36
37bool smaller( double l, double r )
38{
39 return l > r;
40}
41
42bool bigger( double l, double r )
43{
44 return l < r;
45}
46
47// O (size log size)
48PriorityQueue::PriorityQueue( int n, int maxId, bool min )
49 : size( 0 )
50 , maxsize( n )
51 , maxId( maxId )
52{
53 heap = new int[maxsize];
54 p = new double[maxsize];
55 pos = new int[maxId + 1];
56
57 int i;
58
59 for ( i = 0; i <= maxId; i++ )
60 pos[i] = -1;
61
62
63 if ( min )
64 greater = smaller;
65 else
66 greater = bigger;
67}
68
70{
71 delete[] heap;
72 delete[] p;
73 delete[] pos;
74}
75
77{
78 return size;
79}
80
81// O(log size)
83{
84 if ( size <= 0 )
86
87 const int return_value = heap[0];
88
89 size--;
90
91 pos[heap[0]] = -1;
92
93 if ( size > 0 )
94 {
95 pos[heap[size]] = 0;
96
97 heap[0] = heap[size];
98 p[0] = p[size];
99 downheap( 0 );
100 }
101
102 return return_value;
103}
104
105
106bool PriorityQueue::isIn( int key ) const
107{
108 return key <= maxId && pos[key] >= 0;
109}
110
111int PriorityQueue::getId( int key ) const
112{
113 return key <= maxId ? pos[key] : -1;
114}
115
116void PriorityQueue::insert( int key, double p )
117{
118 if ( size == maxsize || key > maxId || key < 0 )
120
121 heap[size] = key;
122 pos[key] = size;
123 this->p[size] = p;
124
125 size++;
126
127
128 upheap( key );
129}
130
131
132// O(size)
133//
135{
136 if ( key < 0 || key > maxId )
137 return;
138 const int i = pos[key];
139
140 if ( i >= 0 )
141 {
142 size--;
143 pos[heap[size]] = i;
144 pos[key] = -1;
145
146 heap[i] = heap[size];
147 p[i] = p[size];
148
149 downheap( i );
150 }
151}
152
153// O (size log size)
155{
156 int i;
157 int pi = 2;
158 while ( size > pi ) pi *= 2;
159
160 i = pi / 2 - 2;
161
162 for ( i = size - 1; i >= 0; i-- )
163 downheap( i );
164
165}
166
167
169{
170 int i;
171 int i2;
172
173 int tmpT;
174 double tmpP;
175
176
177 if ( key < 0 || key > maxId )
178 return;
179
180 i = pos[key];
181
182 if ( i >= -1 )
183 {
184 while ( i > 0 )
185 {
186 if ( greater( p[PARENT( i )], p[i] ) )
187 {
188 i2 = PARENT( i );
189
190 pos[heap[i]] = i2;
191 pos[heap[i2]] = i;
192
193 tmpT = heap[i];
194 tmpP = p[i];
195
196 heap[i] = heap[i2];
197 p[i] = p[i2];
198
199 heap[i2] = tmpT;
200 p[i2] = tmpP;
201
202 i = i2;
203 }
204 else
205 break;
206 }
207 }
208}
209
210// O(log n)
212{
213 int min_child;
214 int tmpT;
215 double tmpP;
216
217 for ( ;; )
218 {
219 if ( LEFT( id ) < size )
220 {
221 if ( RIGHT( id ) < size )
222 {
223 min_child = greater( p[RIGHT( id )], p[LEFT( id )] ) ? LEFT( id ) : RIGHT( id );
224 }
225 else
226 min_child = LEFT( id );
227 }
228 else // leaf
229 break;
230
231 if ( greater( p[id], p[min_child] ) )
232 {
233 pos[heap[id]] = min_child;
234 pos[heap[min_child]] = id;
235
236 tmpT = heap[id];
237 tmpP = p[id];
238
239 heap[id] = heap[min_child];
240 p[id] = p[min_child];
241
242 heap[min_child] = tmpT;
243 p[min_child] = tmpP;
244
245 id = min_child;
246 }
247 else
248 break;
249 }
250}
251
252void PriorityQueue::setPriority( int key, double new_p )
253{
254
255 if ( key < 0 || key > maxId )
256 return;
257
258 const int i = pos[key];
259
260 if ( i < 0 )
261 {
262 insert( key, new_p );
263 return;
264 }
265
266 p[i] = new_p;
267
268 upheap( key );
269 downheap( pos[key] );
270}
271
272
274{
275
276 if ( key < 0 || key > maxId )
277 return;
278
279 const int i = pos[key];
280
281 if ( i < 0 )
282 return;
283
284 p[i]--;
285
286 upheap( key );
287 downheap( pos[key] );
288}
289
290
292{
293 int i;
294
295 fprintf( stderr, "Size: %d\nMaxSize: %d\n", size, maxsize );
296
297 for ( i = 0; i < size; i++ )
298 {
299 //printf ("key: %7d -> index: %7d -> key: %7d p: %7d\n", i, pos[i], heap[pos[i]], p[pos[i]]);
300 fprintf( stderr, "id: %7d -> key: %7d -> id: %7d p: %7f\n", i, heap[i], pos[heap[i]], p[i] );
301 }
302 fprintf( stderr, "\n" );
303
304}
305
306
308{
309 int i;
310 int count = 0;
311 for ( i = 0; i < maxsize; i++ )
312 {
313 if ( pos[i] >= 0 )
314 count++;
315 }
316 return count;
317}
Thrown when trying to access an empty data set.
Thrown when something is added in a Full set.
PriorityQueue(int n, int maxId, bool min)
Create a priority queue of max size n \param n max size of the queuet \param p external vector repres...
void decreaseKey(int key)
void setPriority(int key, double new_p)
void insert(int key, double p)
int getId(int key) const
bool isIn(int key) const
bool smaller(double l, double r)
bool bigger(double l, double r)
#define LEFT(x)
#define RIGHT(x)
#define PARENT(x)