1 |
|
/* |
2 |
< |
* @(#)PriorityQueue.java 1.8 05/08/27 |
2 |
> |
* %W% %E% |
3 |
|
* |
4 |
< |
* Copyright 2005 Sun Microsystems, Inc. All rights reserved. |
4 |
> |
* Copyright 2006 Sun Microsystems, Inc. All rights reserved. |
5 |
|
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. |
6 |
|
*/ |
7 |
|
|
8 |
|
package java.util; |
9 |
– |
import java.util.*; // for javadoc (till 6280605 is fixed) |
9 |
|
|
10 |
|
/** |
11 |
|
* An unbounded priority {@linkplain Queue queue} based on a priority |
55 |
|
* <a href="{@docRoot}/../guide/collections/index.html"> |
56 |
|
* Java Collections Framework</a>. |
57 |
|
* @since 1.5 |
58 |
< |
* @version 1.8, 08/27/05 |
58 |
> |
* @version %I%, %G% |
59 |
|
* @author Josh Bloch |
60 |
|
* @param <E> the type of elements held in this collection |
61 |
|
*/ |
135 |
|
this.queue = new Object[initialCapacity]; |
136 |
|
this.comparator = comparator; |
137 |
|
} |
138 |
< |
|
138 |
> |
|
139 |
|
/** |
140 |
|
* Creates a <tt>PriorityQueue</tt> containing the elements in the |
141 |
|
* specified collection. If the specified collection is an |
154 |
|
*/ |
155 |
|
public PriorityQueue(Collection<? extends E> c) { |
156 |
|
initFromCollection(c); |
157 |
< |
if (c instanceof SortedSet) |
157 |
> |
if (c instanceof SortedSet) |
158 |
|
comparator = (Comparator<? super E>) |
159 |
|
((SortedSet<? extends E>)c).comparator(); |
160 |
< |
else if (c instanceof PriorityQueue) |
160 |
> |
else if (c instanceof PriorityQueue) |
161 |
|
comparator = (Comparator<? super E>) |
162 |
|
((PriorityQueue<? extends E>)c).comparator(); |
163 |
|
else { |
214 |
|
a = Arrays.copyOf(a, a.length, Object[].class); |
215 |
|
queue = a; |
216 |
|
size = a.length; |
217 |
< |
} |
217 |
> |
} |
218 |
|
|
219 |
|
/** |
220 |
|
* Increases the capacity of the array. |
228 |
|
// Double size if small; else grow by 50% |
229 |
|
int newCapacity = ((oldCapacity < 64)? |
230 |
|
((oldCapacity + 1) * 2): |
231 |
< |
((oldCapacity * 3) / 2)); |
231 |
> |
((oldCapacity / 2) * 3)); |
232 |
> |
if (newCapacity < 0) // overflow |
233 |
> |
newCapacity = Integer.MAX_VALUE; |
234 |
|
if (newCapacity < minCapacity) |
235 |
|
newCapacity = minCapacity; |
236 |
|
queue = Arrays.copyOf(queue, newCapacity); |
308 |
|
} |
309 |
|
} |
310 |
|
|
311 |
< |
/** |
311 |
> |
/** |
312 |
|
* Version of remove using reference equality, not equals. |
313 |
< |
* Needed by iterator.remove |
314 |
< |
* |
313 |
> |
* Needed by iterator.remove. |
314 |
> |
* |
315 |
|
* @param o element to be removed from this queue, if present |
316 |
< |
* @return <tt>true</tt> if removed. |
316 |
> |
* @return <tt>true</tt> if removed |
317 |
|
*/ |
318 |
|
boolean removeEq(Object o) { |
319 |
|
for (int i = 0; i < size; i++) { |
345 |
|
* maintained by this list. (In other words, this method must allocate |
346 |
|
* a new array). The caller is thus free to modify the returned array. |
347 |
|
* |
348 |
< |
* @return an array containing all of the elements in this queue. |
348 |
> |
* @return an array containing all of the elements in this queue |
349 |
|
*/ |
350 |
|
public Object[] toArray() { |
351 |
|
return Arrays.copyOf(queue, size); |
436 |
|
private int expectedModCount = modCount; |
437 |
|
|
438 |
|
public boolean hasNext() { |
439 |
< |
return cursor < size || |
439 |
> |
return cursor < size || |
440 |
|
(forgetMeNot != null && !forgetMeNot.isEmpty()); |
441 |
|
} |
442 |
|
|
443 |
|
public E next() { |
444 |
|
if (expectedModCount != modCount) |
445 |
|
throw new ConcurrentModificationException(); |
446 |
< |
if (cursor < size) |
446 |
> |
if (cursor < size) |
447 |
|
return (E) queue[lastRet = cursor++]; |
448 |
|
if (forgetMeNot != null) { |
449 |
|
lastRet = -1; |
450 |
|
lastRetElt = forgetMeNot.poll(); |
451 |
< |
if (lastRetElt != null) |
451 |
> |
if (lastRetElt != null) |
452 |
|
return lastRetElt; |
453 |
|
} |
454 |
|
throw new NoSuchElementException(); |
462 |
|
if (lastRet != -1) { |
463 |
|
E moved = PriorityQueue.this.removeAt(lastRet); |
464 |
|
lastRet = -1; |
465 |
< |
if (moved == null) |
465 |
> |
if (moved == null) |
466 |
|
cursor--; |
467 |
|
else { |
468 |
|
if (forgetMeNot == null) |
469 |
|
forgetMeNot = new ArrayDeque<E>(); |
470 |
|
forgetMeNot.add(moved); |
471 |
< |
} |
471 |
> |
} |
472 |
|
} else { |
473 |
|
PriorityQueue.this.removeEq(lastRetElt); |
474 |
|
lastRetElt = null; |
475 |
< |
} |
475 |
> |
} |
476 |
|
expectedModCount = modCount; |
477 |
|
} |
478 |
|
|
526 |
|
queue[i] = null; |
527 |
|
else { |
528 |
|
E moved = (E) queue[s]; |
529 |
< |
queue[s] = null; |
529 |
> |
queue[s] = null; |
530 |
|
siftDown(i, moved); |
531 |
|
if (queue[i] == moved) { |
532 |
|
siftUp(i, moved); |
545 |
|
* To simplify and speed up coercions and comparisons. the |
546 |
|
* Comparable and Comparator versions are separated into different |
547 |
|
* methods that are otherwise identical. (Similarly for siftDown.) |
548 |
< |
* |
548 |
> |
* |
549 |
|
* @param k the position to fill |
550 |
|
* @param x the item to insert |
551 |
|
*/ |
552 |
|
private void siftUp(int k, E x) { |
553 |
< |
if (comparator != null) |
553 |
> |
if (comparator != null) |
554 |
|
siftUpUsingComparator(k, x); |
555 |
|
else |
556 |
|
siftUpComparable(k, x); |
561 |
|
while (k > 0) { |
562 |
|
int parent = (k - 1) >>> 1; |
563 |
|
Object e = queue[parent]; |
564 |
< |
if (key.compareTo((E)e) >= 0) |
564 |
> |
if (key.compareTo((E)e) >= 0) |
565 |
|
break; |
566 |
|
queue[k] = e; |
567 |
|
k = parent; |
573 |
|
while (k > 0) { |
574 |
|
int parent = (k - 1) >>> 1; |
575 |
|
Object e = queue[parent]; |
576 |
< |
if (comparator.compare(x, (E)e) >= 0) |
576 |
> |
if (comparator.compare(x, (E)e) >= 0) |
577 |
|
break; |
578 |
|
queue[k] = e; |
579 |
|
k = parent; |
590 |
|
* @param x the item to insert |
591 |
|
*/ |
592 |
|
private void siftDown(int k, E x) { |
593 |
< |
if (comparator != null) |
593 |
> |
if (comparator != null) |
594 |
|
siftDownUsingComparator(k, x); |
595 |
|
else |
596 |
|
siftDownComparable(k, x); |
622 |
|
int right = child + 1; |
623 |
|
if (right < size && |
624 |
|
comparator.compare((E)c, (E)queue[right]) > 0) |
625 |
< |
c = queue[child = right]; |
626 |
< |
if (comparator.compare(x, (E)c) <= 0) |
625 |
> |
c = queue[child = right]; |
626 |
> |
if (comparator.compare(x, (E)c) <= 0) |
627 |
|
break; |
628 |
|
queue[k] = c; |
629 |
|
k = child; |
636 |
|
* assuming nothing about the order of the elements prior to the call. |
637 |
|
*/ |
638 |
|
private void heapify() { |
639 |
< |
for (int i = (size >>> 1) - 1; i >= 0; i--) |
639 |
> |
for (int i = (size >>> 1) - 1; i >= 0; i--) |
640 |
|
siftDown(i, (E)queue[i]); |
641 |
|
} |
642 |
|
|