QGIS API Documentation 3.27.0-Master (0a97e3138f)
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.
int getSizeByPos() const
void decreaseKey(int key)
void setPriority(int key, double new_p)
void downheap(int id)
void insert(int key, double p)
int getId(int key) const
bool isIn(int key) const
void remove(int key)
void upheap(int key)
bool smaller(double l, double r)
bool bigger(double l, double r)
#define LEFT(x)
Definition: priorityqueue.h:38
#define RIGHT(x)
Definition: priorityqueue.h:39
#define PARENT(x)
Definition: priorityqueue.h:40