|
|||||||||||||||||||
Source file | Conditionals | Statements | Methods | TOTAL | |||||||||||||||
PriorityQueue.java | 52.1% | 57.4% | 55.2% | 55.7% |
|
1 | package org.drools.util; | |
2 | /* | |
3 | * Copyright 2001-2004 The Apache Software Foundation | |
4 | * | |
5 | * Licensed under the Apache License, Version 2.0 (the "License"); you may not | |
6 | * use this file except in compliance with the License. You may obtain a copy of | |
7 | * the License at | |
8 | * | |
9 | * http://www.apache.org/licenses/LICENSE-2.0 | |
10 | * | |
11 | * Unless required by applicable law or agreed to in writing, software | |
12 | * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT | |
13 | * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the | |
14 | * License for the specific language governing permissions and limitations under | |
15 | * the License. | |
16 | */ | |
17 | ||
18 | import java.io.Serializable; | |
19 | import java.util.AbstractCollection; | |
20 | import java.util.Comparator; | |
21 | import java.util.Iterator; | |
22 | import java.util.NoSuchElementException; | |
23 | ||
24 | /** | |
25 | * Binary heap implementation of <code>Buffer</code> that provides for removal | |
26 | * based on <code>Comparator</code> ordering. <p/>The removal order of a | |
27 | * binary heap is based on either the natural sort order of its elements or a | |
28 | * specified {@linkComparator}. The {@link #remove()}method always returns the | |
29 | * first element as determined by the sort order. (The | |
30 | * <code>ascendingOrder</code> flag in the constructors can be used to reverse | |
31 | * the sort order, in which case {@link#remove()}will always remove the last | |
32 | * element.) The removal order is <i>not </i> the same as the order of | |
33 | * iteration; elements are returned by the iterator in no particular order. <p/> | |
34 | * The {@link #add(Object)}and {@link #remove()}operations perform in | |
35 | * logarithmic time. The {@link #get()}operation performs in constant time. All | |
36 | * other operations perform in linear time or worse. <p/>Note that this | |
37 | * implementation is not synchronized. | |
38 | * | |
39 | * @author Peter Donald | |
40 | * @author Ram Chidambaram | |
41 | * @author Michael A. Smith | |
42 | * @author Paul Jack | |
43 | * @author Stephen Colebourne | |
44 | * @author <a href="mailto:simon@redhillconsulting.com.au">Simon Harris </a> | |
45 | * @version $Revision: 1.2 $ $Date: 2004/11/19 02:15:18 $ | |
46 | */ | |
47 | public class PriorityQueue extends AbstractCollection | |
48 | implements | |
49 | Serializable | |
50 | { | |
51 | ||
52 | /** | |
53 | * The default capacity for the buffer. | |
54 | */ | |
55 | private static final int DEFAULT_CAPACITY = 13; | |
56 | ||
57 | /** | |
58 | * The elements in this buffer. | |
59 | */ | |
60 | protected Object[] elements; | |
61 | ||
62 | /** | |
63 | * The number of elements currently in this buffer. | |
64 | */ | |
65 | protected int size; | |
66 | ||
67 | /** | |
68 | * If true, the first element as determined by the sort order will be | |
69 | * returned. If false, the last element as determined by the sort order will | |
70 | * be returned. | |
71 | */ | |
72 | protected boolean ascendingOrder; | |
73 | ||
74 | /** | |
75 | * The comparator used to order the elements | |
76 | */ | |
77 | protected Comparator comparator; | |
78 | ||
79 | // ----------------------------------------------------------------------- | |
80 | /** | |
81 | * Constructs a new empty buffer that sorts in ascending order by the | |
82 | * natural order of the objects added. | |
83 | */ | |
84 | 0 | public PriorityQueue() |
85 | { | |
86 | 0 | this( DEFAULT_CAPACITY, |
87 | true, | |
88 | null ); | |
89 | } | |
90 | ||
91 | /** | |
92 | * Constructs a new empty buffer that sorts in ascending order using the | |
93 | * specified comparator. | |
94 | * | |
95 | * @param comparator | |
96 | * the comparator used to order the elements, null means use | |
97 | * natural order | |
98 | */ | |
99 | 124 | public PriorityQueue(Comparator comparator) |
100 | { | |
101 | 124 | this( DEFAULT_CAPACITY, |
102 | true, | |
103 | comparator ); | |
104 | } | |
105 | ||
106 | /** | |
107 | * Constructs a new empty buffer specifying the sort order and using the | |
108 | * natural order of the objects added. | |
109 | * | |
110 | * @param ascendingOrder | |
111 | * if <code>true</code> the heap is created as a minimum heap; | |
112 | * otherwise, the heap is created as a maximum heap | |
113 | */ | |
114 | 0 | public PriorityQueue(boolean ascendingOrder) |
115 | { | |
116 | 0 | this( DEFAULT_CAPACITY, |
117 | ascendingOrder, | |
118 | null ); | |
119 | } | |
120 | ||
121 | /** | |
122 | * Constructs a new empty buffer specifying the sort order and comparator. | |
123 | * | |
124 | * @param ascendingOrder | |
125 | * true to use the order imposed by the given comparator; false | |
126 | * to reverse that order | |
127 | * @param comparator | |
128 | * the comparator used to order the elements, null means use | |
129 | * natural order | |
130 | */ | |
131 | 0 | public PriorityQueue(boolean ascendingOrder, |
132 | Comparator comparator) | |
133 | { | |
134 | 0 | this( DEFAULT_CAPACITY, |
135 | ascendingOrder, | |
136 | comparator ); | |
137 | } | |
138 | ||
139 | /** | |
140 | * Constructs a new empty buffer that sorts in ascending order by the | |
141 | * natural order of the objects added, specifying an initial capacity. | |
142 | * | |
143 | * @param capacity | |
144 | * the initial capacity for the buffer, greater than zero | |
145 | * @throws IllegalArgumentException | |
146 | * if <code>capacity</code> is <= <code>0</code> | |
147 | */ | |
148 | 0 | public PriorityQueue(int capacity) |
149 | { | |
150 | 0 | this( capacity, |
151 | true, | |
152 | null ); | |
153 | } | |
154 | ||
155 | /** | |
156 | * Constructs a new empty buffer that sorts in ascending order using the | |
157 | * specified comparator and initial capacity. | |
158 | * | |
159 | * @param capacity | |
160 | * the initial capacity for the buffer, greater than zero | |
161 | * @param comparator | |
162 | * the comparator used to order the elements, null means use | |
163 | * natural order | |
164 | * @throws IllegalArgumentException | |
165 | * if <code>capacity</code> is <= <code>0</code> | |
166 | */ | |
167 | 0 | public PriorityQueue(int capacity, |
168 | Comparator comparator) | |
169 | { | |
170 | 0 | this( capacity, |
171 | true, | |
172 | comparator ); | |
173 | } | |
174 | ||
175 | /** | |
176 | * Constructs a new empty buffer that specifying initial capacity and sort | |
177 | * order, using the natural order of the objects added. | |
178 | * | |
179 | * @param capacity | |
180 | * the initial capacity for the buffer, greater than zero | |
181 | * @param ascendingOrder | |
182 | * if <code>true</code> the heap is created as a minimum heap; | |
183 | * otherwise, the heap is created as a maximum heap. | |
184 | * @throws IllegalArgumentException | |
185 | * if <code>capacity</code> is <code><= 0</code> | |
186 | */ | |
187 | 0 | public PriorityQueue(int capacity, |
188 | boolean ascendingOrder) | |
189 | { | |
190 | 0 | this( capacity, |
191 | ascendingOrder, | |
192 | null ); | |
193 | } | |
194 | ||
195 | /** | |
196 | * Constructs a new empty buffer that specifying initial capacity, sort | |
197 | * order and comparator. | |
198 | * | |
199 | * @param capacity | |
200 | * the initial capacity for the buffer, greater than zero | |
201 | * @param ascendingOrder | |
202 | * true to use the order imposed by the given comparator; false | |
203 | * to reverse that order | |
204 | * @param comparator | |
205 | * the comparator used to order the elements, null means use | |
206 | * natural order | |
207 | * @throws IllegalArgumentException | |
208 | * if <code>capacity</code> is <code><= 0</code> | |
209 | */ | |
210 | 124 | public PriorityQueue(int capacity, |
211 | boolean ascendingOrder, | |
212 | Comparator comparator) | |
213 | { | |
214 | 124 | super( ); |
215 | 124 | if ( capacity <= 0 ) |
216 | { | |
217 | 0 | throw new IllegalArgumentException( "invalid capacity" ); |
218 | } | |
219 | 124 | this.ascendingOrder = ascendingOrder; |
220 | ||
221 | // +1 as 0 is noop | |
222 | 124 | this.elements = new Object[capacity + 1]; |
223 | 124 | this.comparator = comparator; |
224 | } | |
225 | ||
226 | // ----------------------------------------------------------------------- | |
227 | /** | |
228 | * Checks whether the heap is ascending or descending order. | |
229 | * | |
230 | * @return true if ascending order (a min heap) | |
231 | */ | |
232 | 0 | public boolean isAscendingOrder() |
233 | { | |
234 | 0 | return ascendingOrder; |
235 | } | |
236 | ||
237 | /** | |
238 | * Gets the comparator being used for this buffer, null is natural order. | |
239 | * | |
240 | * @return the comparator in use, null is natural order | |
241 | */ | |
242 | 0 | public Comparator comparator() |
243 | { | |
244 | 0 | return comparator; |
245 | } | |
246 | ||
247 | // ----------------------------------------------------------------------- | |
248 | /** | |
249 | * Returns the number of elements in this buffer. | |
250 | * | |
251 | * @return the number of elements in this buffer | |
252 | */ | |
253 | 1311 | public int size() |
254 | { | |
255 | 1311 | return size; |
256 | } | |
257 | ||
258 | /** | |
259 | * Clears all elements from the buffer. | |
260 | */ | |
261 | 0 | public void clear() |
262 | { | |
263 | 0 | elements = new Object[elements.length]; // for gc |
264 | 0 | size = 0; |
265 | } | |
266 | ||
267 | /** | |
268 | * Adds an element to the buffer. <p/>The element added will be sorted | |
269 | * according to the comparator in use. | |
270 | * | |
271 | * @param element | |
272 | * the element to be added | |
273 | * @return true always | |
274 | */ | |
275 | 6252 | public boolean add(Object element) |
276 | { | |
277 | 6252 | if ( isAtCapacity( ) ) |
278 | { | |
279 | 11 | grow( ); |
280 | } | |
281 | // percolate element to it's place in tree | |
282 | 6252 | if ( ascendingOrder ) |
283 | { | |
284 | 6252 | percolateUpMinHeap( element ); |
285 | } | |
286 | else | |
287 | { | |
288 | 0 | percolateUpMaxHeap( element ); |
289 | } | |
290 | 6252 | return true; |
291 | } | |
292 | ||
293 | /** | |
294 | * Gets the next element to be removed without actually removing it (peek). | |
295 | * | |
296 | * @return the next element | |
297 | * @throws NoSuchElementException | |
298 | * if the buffer is empty | |
299 | */ | |
300 | 481 | public Object get() |
301 | { | |
302 | 481 | if ( isEmpty( ) ) |
303 | { | |
304 | 0 | throw new NoSuchElementException( ); |
305 | } | |
306 | else | |
307 | { | |
308 | 481 | return elements[1]; |
309 | } | |
310 | } | |
311 | ||
312 | /** | |
313 | * Gets and removes the next element (pop). | |
314 | * | |
315 | * @return the next element | |
316 | * @throws NoSuchElementException | |
317 | * if the buffer is empty | |
318 | */ | |
319 | 481 | public Object remove() |
320 | { | |
321 | 481 | final Object result = get( ); |
322 | 481 | elements[1] = elements[size--]; |
323 | ||
324 | // set the unused element to 'null' so that the garbage collector | |
325 | // can free the object if not used anywhere else.(remove reference) | |
326 | 481 | elements[size + 1] = null; |
327 | ||
328 | 481 | if ( size != 0 ) |
329 | { | |
330 | // percolate top element to it's place in tree | |
331 | 326 | if ( ascendingOrder ) |
332 | { | |
333 | 326 | percolateDownMinHeap( 1 ); |
334 | } | |
335 | else | |
336 | { | |
337 | 0 | percolateDownMaxHeap( 1 ); |
338 | } | |
339 | } | |
340 | ||
341 | 481 | return result; |
342 | } | |
343 | ||
344 | // ----------------------------------------------------------------------- | |
345 | /** | |
346 | * Tests if the buffer is at capacity. | |
347 | * | |
348 | * @return <code>true</code> if buffer is full; <code>false</code> | |
349 | * otherwise. | |
350 | */ | |
351 | 6252 | protected boolean isAtCapacity() |
352 | { | |
353 | // +1 as element 0 is noop | |
354 | 6252 | return elements.length == size + 1; |
355 | } | |
356 | ||
357 | /** | |
358 | * Percolates element down heap from the position given by the index. <p/> | |
359 | * Assumes it is a minimum heap. | |
360 | * | |
361 | * @param index | |
362 | * the index for the element | |
363 | */ | |
364 | 6038 | protected void percolateDownMinHeap(final int index) |
365 | { | |
366 | 6038 | final Object element = elements[index]; |
367 | 6038 | int hole = index; |
368 | ||
369 | 6038 | while ( (hole * 2) <= size ) |
370 | { | |
371 | 22373 | int child = hole * 2; |
372 | ||
373 | // if we have a right child and that child can not be percolated | |
374 | // up then move onto other child | |
375 | 22373 | if ( child != size && compare( elements[child + 1], |
376 | elements[child] ) < 0 ) | |
377 | { | |
378 | 8067 | child++; |
379 | } | |
380 | ||
381 | // if we found resting place of bubble then terminate search | |
382 | 22373 | if ( compare( elements[child], |
383 | element ) >= 0 ) | |
384 | { | |
385 | 3916 | break; |
386 | } | |
387 | ||
388 | 18457 | elements[hole] = elements[child]; |
389 | 18457 | hole = child; |
390 | } | |
391 | ||
392 | 6038 | elements[hole] = element; |
393 | } | |
394 | ||
395 | /** | |
396 | * Percolates element down heap from the position given by the index. <p/> | |
397 | * Assumes it is a maximum heap. | |
398 | * | |
399 | * @param index | |
400 | * the index of the element | |
401 | */ | |
402 | 0 | protected void percolateDownMaxHeap(final int index) |
403 | { | |
404 | 0 | final Object element = elements[index]; |
405 | 0 | int hole = index; |
406 | ||
407 | 0 | while ( (hole * 2) <= size ) |
408 | { | |
409 | 0 | int child = hole * 2; |
410 | ||
411 | // if we have a right child and that child can not be percolated | |
412 | // up then move onto other child | |
413 | 0 | if ( child != size && compare( elements[child + 1], |
414 | elements[child] ) > 0 ) | |
415 | { | |
416 | 0 | child++; |
417 | } | |
418 | ||
419 | // if we found resting place of bubble then terminate search | |
420 | 0 | if ( compare( elements[child], |
421 | element ) <= 0 ) | |
422 | { | |
423 | 0 | break; |
424 | } | |
425 | ||
426 | 0 | elements[hole] = elements[child]; |
427 | 0 | hole = child; |
428 | } | |
429 | ||
430 | 0 | elements[hole] = element; |
431 | } | |
432 | ||
433 | /** | |
434 | * Percolates element up heap from the position given by the index. <p/> | |
435 | * Assumes it is a minimum heap. | |
436 | * | |
437 | * @param index | |
438 | * the index of the element to be percolated up | |
439 | */ | |
440 | 6252 | protected void percolateUpMinHeap(final int index) |
441 | { | |
442 | 6252 | int hole = index; |
443 | 6252 | Object element = elements[hole]; |
444 | 6252 | while ( hole > 1 && compare( element, |
445 | elements[hole / 2] ) < 0 ) | |
446 | { | |
447 | // save element that is being pushed down | |
448 | // as the element "bubble" is percolated up | |
449 | 235 | final int next = hole / 2; |
450 | 235 | elements[hole] = elements[next]; |
451 | 235 | hole = next; |
452 | } | |
453 | 6252 | elements[hole] = element; |
454 | } | |
455 | ||
456 | /** | |
457 | * Percolates a new element up heap from the bottom. <p/>Assumes it is a | |
458 | * minimum heap. | |
459 | * | |
460 | * @param element | |
461 | * the element | |
462 | */ | |
463 | 6252 | protected void percolateUpMinHeap(final Object element) |
464 | { | |
465 | 6252 | elements[++size] = element; |
466 | 6252 | percolateUpMinHeap( size ); |
467 | } | |
468 | ||
469 | /** | |
470 | * Percolates element up heap from from the position given by the index. | |
471 | * <p/>Assume it is a maximum heap. | |
472 | * | |
473 | * @param index | |
474 | * the index of the element to be percolated up | |
475 | */ | |
476 | 0 | protected void percolateUpMaxHeap(final int index) |
477 | { | |
478 | 0 | int hole = index; |
479 | 0 | Object element = elements[hole]; |
480 | ||
481 | 0 | while ( hole > 1 && compare( element, |
482 | elements[hole / 2] ) > 0 ) | |
483 | { | |
484 | // save element that is being pushed down | |
485 | // as the element "bubble" is percolated up | |
486 | 0 | final int next = hole / 2; |
487 | 0 | elements[hole] = elements[next]; |
488 | 0 | hole = next; |
489 | } | |
490 | ||
491 | 0 | elements[hole] = element; |
492 | } | |
493 | ||
494 | /** | |
495 | * Percolates a new element up heap from the bottom. <p/>Assume it is a | |
496 | * maximum heap. | |
497 | * | |
498 | * @param element | |
499 | * the element | |
500 | */ | |
501 | 0 | protected void percolateUpMaxHeap(final Object element) |
502 | { | |
503 | 0 | elements[++size] = element; |
504 | 0 | percolateUpMaxHeap( size ); |
505 | } | |
506 | ||
507 | /** | |
508 | * Compares two objects using the comparator if specified, or the natural | |
509 | * order otherwise. | |
510 | * | |
511 | * @param a | |
512 | * the first object | |
513 | * @param b | |
514 | * the second object | |
515 | * @return -ve if a less than b, 0 if they are equal, +ve if a greater than | |
516 | * b | |
517 | */ | |
518 | 51040 | protected int compare(Object a, |
519 | Object b) | |
520 | { | |
521 | 51040 | if ( comparator != null ) |
522 | { | |
523 | 51040 | return comparator.compare( a, |
524 | b ); | |
525 | } | |
526 | else | |
527 | { | |
528 | 0 | return ((Comparable) a).compareTo( b ); |
529 | } | |
530 | } | |
531 | ||
532 | /** | |
533 | * Increases the size of the heap to support additional elements | |
534 | */ | |
535 | 11 | protected void grow() |
536 | { | |
537 | 11 | final Object[] array = new Object[elements.length * 2]; |
538 | 11 | System.arraycopy( elements, |
539 | 0, | |
540 | array, | |
541 | 0, | |
542 | elements.length ); | |
543 | 11 | elements = array; |
544 | } | |
545 | ||
546 | // ----------------------------------------------------------------------- | |
547 | /** | |
548 | * Returns an iterator over this heap's elements. | |
549 | * | |
550 | * @return an iterator over this heap's elements | |
551 | */ | |
552 | 6697 | public Iterator iterator() |
553 | { | |
554 | 6697 | return new Iterator( ) |
555 | { | |
556 | ||
557 | private int index = 1; | |
558 | ||
559 | private int lastReturnedIndex = -1; | |
560 | ||
561 | 45566 | public boolean hasNext() |
562 | { | |
563 | 45566 | return index <= size; |
564 | } | |
565 | ||
566 | 22315 | public Object next() |
567 | { | |
568 | 22315 | if ( !hasNext( ) ) |
569 | { | |
570 | 0 | throw new NoSuchElementException( ); |
571 | } | |
572 | 22315 | lastReturnedIndex = index; |
573 | 22315 | index++; |
574 | 22315 | return elements[lastReturnedIndex]; |
575 | } | |
576 | ||
577 | 5768 | public void remove() |
578 | { | |
579 | 5768 | if ( lastReturnedIndex == -1 ) |
580 | { | |
581 | 0 | throw new IllegalStateException( ); |
582 | } | |
583 | 5768 | elements[lastReturnedIndex] = elements[size]; |
584 | 5768 | elements[size] = null; |
585 | 5768 | size--; |
586 | 5768 | if ( size != 0 && lastReturnedIndex <= size ) |
587 | { | |
588 | 5712 | int compareToParent = 0; |
589 | 5712 | if ( lastReturnedIndex > 1 ) |
590 | { | |
591 | 205 | compareToParent = compare( elements[lastReturnedIndex], |
592 | elements[lastReturnedIndex / 2] ); | |
593 | } | |
594 | 5712 | if ( ascendingOrder ) |
595 | { | |
596 | 5712 | if ( lastReturnedIndex > 1 && compareToParent < 0 ) |
597 | { | |
598 | 0 | percolateUpMinHeap( lastReturnedIndex ); |
599 | } | |
600 | else | |
601 | { | |
602 | 5712 | percolateDownMinHeap( lastReturnedIndex ); |
603 | } | |
604 | } | |
605 | else | |
606 | { // max heap | |
607 | 0 | if ( lastReturnedIndex > 1 && compareToParent > 0 ) |
608 | { | |
609 | 0 | percolateUpMaxHeap( lastReturnedIndex ); |
610 | } | |
611 | else | |
612 | { | |
613 | 0 | percolateDownMaxHeap( lastReturnedIndex ); |
614 | } | |
615 | } | |
616 | } | |
617 | 5768 | index--; |
618 | 5768 | lastReturnedIndex = -1; |
619 | } | |
620 | ||
621 | }; | |
622 | } | |
623 | ||
624 | /** | |
625 | * Returns a string representation of this heap. The returned string is | |
626 | * similar to those produced by standard JDK collections. | |
627 | * | |
628 | * @return a string representation of this heap | |
629 | */ | |
630 | 0 | public String toString() |
631 | { | |
632 | 0 | final StringBuffer sb = new StringBuffer( ); |
633 | ||
634 | 0 | sb.append( "[ " ); |
635 | ||
636 | 0 | for ( int i = 1; i < size + 1; i++ ) |
637 | { | |
638 | 0 | if ( i != 1 ) |
639 | { | |
640 | 0 | sb.append( ", " ); |
641 | } | |
642 | 0 | sb.append( elements[i] ); |
643 | } | |
644 | ||
645 | 0 | sb.append( " ]" ); |
646 | ||
647 | 0 | return sb.toString( ); |
648 | } | |
649 | ||
650 | } |
|