QGIS API Documentation  2.99.0-Master (e077efd)
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 
35 using namespace pal;
36 
37 bool smaller( double l, double r )
38 {
39  return l > r;
40 }
41 
42 bool bigger( double l, double r )
43 {
44  return l < r;
45 }
46 
47 // O (size log size)
48 PriorityQueue::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  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 
106 bool PriorityQueue::isIn( int key )
107 {
108  return key <= maxId && pos[key] >= 0;
109 }
110 
111 int PriorityQueue::getId( int key )
112 {
113  return key <= maxId ? pos[key] : -1;
114 }
115 
116 void PriorityQueue::insert( int key, double p )
117 {
118  if ( size == maxsize || key > maxId || key < 0 )
119  throw InternalException::Full();
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 //
134 void PriorityQueue::remove( int key )
135 {
136  if ( key < 0 || key > maxId )
137  return;
138  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 
168 void PriorityQueue::upheap( int key )
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 
252 void PriorityQueue::setPriority( int key, double new_p )
253 {
254 
255  if ( key < 0 || key > maxId )
256  return;
257 
258  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  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 }
#define LEFT(x)
Definition: priorityqueue.h:35
bool smaller(double l, double r)
bool isIn(int key)
Thrown when something is added in a Full set.
void remove(int key)
void upheap(int key)
void downheap(int id)
double ANALYSIS_EXPORT min(double x, double y)
Returns the minimum of two doubles or the first argument if both are equal.
Definition: MathUtils.cc:452
void insert(int key, double p)
#define PARENT(x)
Definition: priorityqueue.h:37
void setPriority(int key, double new_p)
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...
#define RIGHT(x)
Definition: priorityqueue.h:36
bool bigger(double l, double r)
Thrown when trying to access an empty dada set.
void decreaseKey(int key)