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