QGIS API Documentation  2.11.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
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 namespace pal
36 {
37 
38  bool smaller( double l, double r )
39  {
40  return l > r;
41  }
42 
43  bool bigger( double l, double r )
44  {
45  return l < r;
46  }
47 
48 // O (size log size)
49  PriorityQueue::PriorityQueue( int n, int maxId, bool min ) : size( 0 ), maxsize( n ), maxId( maxId )
50  {
51  heap = new int[maxsize];
52  p = new double[maxsize];
53  pos = new int[maxId+1];
54 
55  int i;
56 
57  for ( i = 0; i <= maxId; i++ )
58  pos[i] = -1;
59 
60 
61  if ( min )
62  greater = smaller;
63  else
64  greater = bigger;
65  }
66 
68  {
69  delete[] heap;
70  delete[] p;
71  delete[] pos;
72  }
73 
75  {
76  return size;
77  }
78 
79 // O(log size)
81  {
82  if ( size <= 0 )
84 
85  int return_value = heap[0];
86 
87  //std::cerr << "getBest" << std::endl;
88  //std::cerr << " key: " << return_value << std::endl;
89  //std::cerr << " Size: " << size << std::endl;
90 
91  size--;
92 
93 
94  pos[heap[0]] = -1;
95 
96  if ( size > 0 )
97  {
98  pos[heap[size]] = 0;
99 
100  heap[0] = heap[size];
101  p[0] = p[size];
102  downheap( 0 );
103  }
104 
105  return return_value;
106  }
107 
108 
109  bool PriorityQueue::isIn( int key )
110  {
111  return key <= maxId && pos[key] >= 0;
112  }
113 
114  int PriorityQueue::getId( int key )
115  {
116  return key <= maxId ? pos[key] : -1;
117  }
118 
119  void PriorityQueue::insert( int key, double p )
120  {
121  if ( size == maxsize || key > maxId || key < 0 )
122  throw InternalException::Full();
123 
124  //std::cerr << "insert" << std::endl;
125  //std::cerr << " key: " << key << std::endl;
126  //std::cerr << " size: " << size << std::endl;
127 
128  heap[size] = key;
129  pos[key] = size;
130  this->p[size] = p;
131 
132  size++;
133 
134 
135  upheap( key );
136  }
137 
138 
139 // O(size)
140 //
141  void PriorityQueue::remove( int key )
142  {
143  if ( key < 0 || key > maxId )
144  return;
145  int i = pos[key];
146 
147  //std::cerr << "Remove " << key << std::endl;
148  //std::cerr << " pos[key]: " << i << std::endl;
149 
150  if ( i >= 0 )
151  {
152 
153  //std::cerr << "size:" << size << std::endl;
154  //std::cerr << "heap[size]:" << heap[size] << std::endl;
155  //std::cerr << "pos[heap[size]]:" << pos[heap[size]] << std::endl;
156  //std::cerr << "pos[key]:" << pos[key] << std::endl;
157 
158  size--;
159  pos[heap[size]] = i;
160  pos[key] = -1;
161 
162  heap[i] = heap[size];
163  p[i] = p[size];
164 
165  downheap( i );
166  }
167  }
168 
169 // O (size log size)
171  {
172  int i;
173  int pi = 2;
174  while ( size > pi ) pi *= 2;
175 
176  i = pi / 2 - 2;
177 
178  for ( i = size - 1; i >= 0; i-- )
179  downheap( i );
180 
181  }
182 
183 
184  void PriorityQueue::upheap( int key )
185  {
186  int i;
187  int i2;
188 
189  int tmpT;
190  double tmpP;
191 
192 
193  if ( key < 0 || key > maxId )
194  return;
195 
196  i = pos[key];
197 
198  if ( i >= -1 )
199  {
200  while ( i > 0 )
201  {
202  if ( greater( p[PARENT( i )], p[i] ) )
203  {
204  i2 = PARENT( i );
205 
206  pos[heap[i]] = i2;
207  pos[heap[i2]] = i;
208 
209  tmpT = heap[i];
210  tmpP = p[i];
211 
212  heap[i] = heap[i2];
213  p[i] = p[i2];
214 
215  heap[i2] = tmpT;
216  p[i2] = tmpP;
217 
218  i = i2;
219  }
220  else
221  break;
222  }
223  }
224  }
225 
226 // O(log n)
227  void PriorityQueue::downheap( int id )
228  {
229  int min_child;
230  int tmpT;
231  double tmpP;
232 
233  for ( ;; )
234  {
235  if ( LEFT( id ) < size )
236  {
237  if ( RIGHT( id ) < size )
238  {
239  min_child = greater( p[RIGHT( id )], p[LEFT( id )] ) ? LEFT( id ) : RIGHT( id );
240  }
241  else
242  min_child = LEFT( id );
243  }
244  else // leaf
245  break;
246 
247  if ( greater( p[id], p[min_child] ) )
248  {
249  pos[heap[id]] = min_child;
250  pos[heap[min_child]] = id;
251 
252  tmpT = heap[id];
253  tmpP = p[id];
254 
255  heap[id] = heap[min_child];
256  p[id] = p[min_child];
257 
258  heap[min_child] = tmpT;
259  p[min_child] = tmpP;
260 
261  id = min_child;
262  }
263  else
264  break;
265  }
266  }
267 
268  void PriorityQueue::setPriority( int key, double new_p )
269  {
270 
271  if ( key < 0 || key > maxId )
272  return;
273 
274  int i = pos[key];
275 
276  if ( i < 0 )
277  {
278  insert( key, new_p );
279  return;
280  }
281 
282  p[i] = new_p;;
283 
284  upheap( key );
285  downheap( pos[key] );
286  }
287 
288 
290  {
291 
292  if ( key < 0 || key > maxId )
293  return;
294 
295  int i = pos[key];
296 
297  if ( i < 0 )
298  return;
299 
300  p[i]--;
301 
302  upheap( key );
303  downheap( pos[key] );
304  }
305 
306 
308  {
309  int i;
310 
311  fprintf( stderr, "Size: %d\nMaxSize: %d\n", size, maxsize );
312 
313  for ( i = 0; i < size; i++ )
314  {
315  //printf ("key: %7d -> index: %7d -> key: %7d p: %7d\n", i, pos[i], heap[pos[i]], p[pos[i]]);
316  fprintf( stderr, "id: %7d -> key: %7d -> id: %7d p: %7f\n", i, heap[i], pos[heap[i]], p[i] );
317  }
318  fprintf( stderr, "\n" );
319 
320  }
321 
322 
324  {
325  int i;
326  int count = 0;
327  for ( i = 0; i < maxsize; i++ )
328  {
329  if ( pos[i] >= 0 )
330  count++;
331  }
332  return count;
333  }
334 
335 } // namespace
336 
#define LEFT(x)
Definition: priorityqueue.h:35
void remove(int key)
Thrown when something is added in a Full set.
void downheap(int id)
void setPriority(int key, double new_p)
bool bigger(double l, double r)
void insert(int key, double p)
#define PARENT(x)
Definition: priorityqueue.h:37
bool smaller(double l, double r)
void upheap(int key)
void decreaseKey(int key)
#define RIGHT(x)
Definition: priorityqueue.h:36
bool isIn(int key)
double ANALYSIS_EXPORT min(double x, double y)
Returns the minimum of two doubles or the first argument if both are equal.
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...
Thrown when trying to access an empty dada set.