QGIS API Documentation
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 ) : size( 0 ), maxsize( n ), maxId( maxId )
49 {
50  heap = new int[maxsize];
51  p = new double[maxsize];
52  pos = new int[maxId+1];
53 
54  int i;
55 
56  for ( i = 0; i <= maxId; i++ )
57  pos[i] = -1;
58 
59 
60  if ( min )
61  greater = smaller;
62  else
63  greater = bigger;
64 }
65 
67 {
68  delete[] heap;
69  delete[] p;
70  delete[] pos;
71 }
72 
74 {
75  return size;
76 }
77 
78 // O(log size)
80 {
81  if ( size <= 0 )
83 
84  int return_value = heap[0];
85 
86  size--;
87 
88  pos[heap[0]] = -1;
89 
90  if ( size > 0 )
91  {
92  pos[heap[size]] = 0;
93 
94  heap[0] = heap[size];
95  p[0] = p[size];
96  downheap( 0 );
97  }
98 
99  return return_value;
100 }
101 
102 
103 bool PriorityQueue::isIn( int key )
104 {
105  return key <= maxId && pos[key] >= 0;
106 }
107 
108 int PriorityQueue::getId( int key )
109 {
110  return key <= maxId ? pos[key] : -1;
111 }
112 
113 void PriorityQueue::insert( int key, double p )
114 {
115  if ( size == maxsize || key > maxId || key < 0 )
116  throw InternalException::Full();
117 
118  heap[size] = key;
119  pos[key] = size;
120  this->p[size] = p;
121 
122  size++;
123 
124 
125  upheap( key );
126 }
127 
128 
129 // O(size)
130 //
131 void PriorityQueue::remove( int key )
132 {
133  if ( key < 0 || key > maxId )
134  return;
135  int i = pos[key];
136 
137  if ( i >= 0 )
138  {
139  size--;
140  pos[heap[size]] = i;
141  pos[key] = -1;
142 
143  heap[i] = heap[size];
144  p[i] = p[size];
145 
146  downheap( i );
147  }
148 }
149 
150 // O (size log size)
152 {
153  int i;
154  int pi = 2;
155  while ( size > pi ) pi *= 2;
156 
157  i = pi / 2 - 2;
158 
159  for ( i = size - 1; i >= 0; i-- )
160  downheap( i );
161 
162 }
163 
164 
165 void PriorityQueue::upheap( int key )
166 {
167  int i;
168  int i2;
169 
170  int tmpT;
171  double tmpP;
172 
173 
174  if ( key < 0 || key > maxId )
175  return;
176 
177  i = pos[key];
178 
179  if ( i >= -1 )
180  {
181  while ( i > 0 )
182  {
183  if ( greater( p[PARENT( i )], p[i] ) )
184  {
185  i2 = PARENT( i );
186 
187  pos[heap[i]] = i2;
188  pos[heap[i2]] = i;
189 
190  tmpT = heap[i];
191  tmpP = p[i];
192 
193  heap[i] = heap[i2];
194  p[i] = p[i2];
195 
196  heap[i2] = tmpT;
197  p[i2] = tmpP;
198 
199  i = i2;
200  }
201  else
202  break;
203  }
204  }
205 }
206 
207 // O(log n)
209 {
210  int min_child;
211  int tmpT;
212  double tmpP;
213 
214  for ( ;; )
215  {
216  if ( LEFT( id ) < size )
217  {
218  if ( RIGHT( id ) < size )
219  {
220  min_child = greater( p[RIGHT( id )], p[LEFT( id )] ) ? LEFT( id ) : RIGHT( id );
221  }
222  else
223  min_child = LEFT( id );
224  }
225  else // leaf
226  break;
227 
228  if ( greater( p[id], p[min_child] ) )
229  {
230  pos[heap[id]] = min_child;
231  pos[heap[min_child]] = id;
232 
233  tmpT = heap[id];
234  tmpP = p[id];
235 
236  heap[id] = heap[min_child];
237  p[id] = p[min_child];
238 
239  heap[min_child] = tmpT;
240  p[min_child] = tmpP;
241 
242  id = min_child;
243  }
244  else
245  break;
246  }
247 }
248 
249 void PriorityQueue::setPriority( int key, double new_p )
250 {
251 
252  if ( key < 0 || key > maxId )
253  return;
254 
255  int i = pos[key];
256 
257  if ( i < 0 )
258  {
259  insert( key, new_p );
260  return;
261  }
262 
263  p[i] = new_p;
264 
265  upheap( key );
266  downheap( pos[key] );
267 }
268 
269 
271 {
272 
273  if ( key < 0 || key > maxId )
274  return;
275 
276  int i = pos[key];
277 
278  if ( i < 0 )
279  return;
280 
281  p[i]--;
282 
283  upheap( key );
284  downheap( pos[key] );
285 }
286 
287 
289 {
290  int i;
291 
292  fprintf( stderr, "Size: %d\nMaxSize: %d\n", size, maxsize );
293 
294  for ( i = 0; i < size; i++ )
295  {
296  //printf ("key: %7d -> index: %7d -> key: %7d p: %7d\n", i, pos[i], heap[pos[i]], p[pos[i]]);
297  fprintf( stderr, "id: %7d -> key: %7d -> id: %7d p: %7f\n", i, heap[i], pos[heap[i]], p[i] );
298  }
299  fprintf( stderr, "\n" );
300 
301 }
302 
303 
305 {
306  int i;
307  int count = 0;
308  for ( i = 0; i < maxsize; i++ )
309  {
310  if ( pos[i] >= 0 )
311  count++;
312  }
313  return count;
314 }
#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)