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