QGIS API Documentation  2.15.0-Master (94d88e6)
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)
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
double ANALYSIS_EXPORT min(double x, double y)
Returns the minimum of two doubles or the first argument if both are equal.
bool bigger(double l, double r)
Thrown when trying to access an empty dada set.
void decreaseKey(int key)