1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/util/PriorityQueue.java Fri Feb 01 16:10:10 2013 +0100
1.3 @@ -0,0 +1,775 @@
1.4 +/*
1.5 + * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +
1.31 +/**
1.32 + * An unbounded priority {@linkplain Queue queue} based on a priority heap.
1.33 + * The elements of the priority queue are ordered according to their
1.34 + * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
1.35 + * provided at queue construction time, depending on which constructor is
1.36 + * used. A priority queue does not permit {@code null} elements.
1.37 + * A priority queue relying on natural ordering also does not permit
1.38 + * insertion of non-comparable objects (doing so may result in
1.39 + * {@code ClassCastException}).
1.40 + *
1.41 + * <p>The <em>head</em> of this queue is the <em>least</em> element
1.42 + * with respect to the specified ordering. If multiple elements are
1.43 + * tied for least value, the head is one of those elements -- ties are
1.44 + * broken arbitrarily. The queue retrieval operations {@code poll},
1.45 + * {@code remove}, {@code peek}, and {@code element} access the
1.46 + * element at the head of the queue.
1.47 + *
1.48 + * <p>A priority queue is unbounded, but has an internal
1.49 + * <i>capacity</i> governing the size of an array used to store the
1.50 + * elements on the queue. It is always at least as large as the queue
1.51 + * size. As elements are added to a priority queue, its capacity
1.52 + * grows automatically. The details of the growth policy are not
1.53 + * specified.
1.54 + *
1.55 + * <p>This class and its iterator implement all of the
1.56 + * <em>optional</em> methods of the {@link Collection} and {@link
1.57 + * Iterator} interfaces. The Iterator provided in method {@link
1.58 + * #iterator()} is <em>not</em> guaranteed to traverse the elements of
1.59 + * the priority queue in any particular order. If you need ordered
1.60 + * traversal, consider using {@code Arrays.sort(pq.toArray())}.
1.61 + *
1.62 + * <p> <strong>Note that this implementation is not synchronized.</strong>
1.63 + * Multiple threads should not access a {@code PriorityQueue}
1.64 + * instance concurrently if any of the threads modifies the queue.
1.65 + * Instead, use the thread-safe {@link
1.66 + * java.util.concurrent.PriorityBlockingQueue} class.
1.67 + *
1.68 + * <p>Implementation note: this implementation provides
1.69 + * O(log(n)) time for the enqueing and dequeing methods
1.70 + * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
1.71 + * linear time for the {@code remove(Object)} and {@code contains(Object)}
1.72 + * methods; and constant time for the retrieval methods
1.73 + * ({@code peek}, {@code element}, and {@code size}).
1.74 + *
1.75 + * <p>This class is a member of the
1.76 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.77 + * Java Collections Framework</a>.
1.78 + *
1.79 + * @since 1.5
1.80 + * @author Josh Bloch, Doug Lea
1.81 + * @param <E> the type of elements held in this collection
1.82 + */
1.83 +public class PriorityQueue<E> extends AbstractQueue<E>
1.84 + implements java.io.Serializable {
1.85 +
1.86 + private static final long serialVersionUID = -7720805057305804111L;
1.87 +
1.88 + private static final int DEFAULT_INITIAL_CAPACITY = 11;
1.89 +
1.90 + /**
1.91 + * Priority queue represented as a balanced binary heap: the two
1.92 + * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
1.93 + * priority queue is ordered by comparator, or by the elements'
1.94 + * natural ordering, if comparator is null: For each node n in the
1.95 + * heap and each descendant d of n, n <= d. The element with the
1.96 + * lowest value is in queue[0], assuming the queue is nonempty.
1.97 + */
1.98 + private transient Object[] queue;
1.99 +
1.100 + /**
1.101 + * The number of elements in the priority queue.
1.102 + */
1.103 + private int size = 0;
1.104 +
1.105 + /**
1.106 + * The comparator, or null if priority queue uses elements'
1.107 + * natural ordering.
1.108 + */
1.109 + private final Comparator<? super E> comparator;
1.110 +
1.111 + /**
1.112 + * The number of times this priority queue has been
1.113 + * <i>structurally modified</i>. See AbstractList for gory details.
1.114 + */
1.115 + private transient int modCount = 0;
1.116 +
1.117 + /**
1.118 + * Creates a {@code PriorityQueue} with the default initial
1.119 + * capacity (11) that orders its elements according to their
1.120 + * {@linkplain Comparable natural ordering}.
1.121 + */
1.122 + public PriorityQueue() {
1.123 + this(DEFAULT_INITIAL_CAPACITY, null);
1.124 + }
1.125 +
1.126 + /**
1.127 + * Creates a {@code PriorityQueue} with the specified initial
1.128 + * capacity that orders its elements according to their
1.129 + * {@linkplain Comparable natural ordering}.
1.130 + *
1.131 + * @param initialCapacity the initial capacity for this priority queue
1.132 + * @throws IllegalArgumentException if {@code initialCapacity} is less
1.133 + * than 1
1.134 + */
1.135 + public PriorityQueue(int initialCapacity) {
1.136 + this(initialCapacity, null);
1.137 + }
1.138 +
1.139 + /**
1.140 + * Creates a {@code PriorityQueue} with the specified initial capacity
1.141 + * that orders its elements according to the specified comparator.
1.142 + *
1.143 + * @param initialCapacity the initial capacity for this priority queue
1.144 + * @param comparator the comparator that will be used to order this
1.145 + * priority queue. If {@code null}, the {@linkplain Comparable
1.146 + * natural ordering} of the elements will be used.
1.147 + * @throws IllegalArgumentException if {@code initialCapacity} is
1.148 + * less than 1
1.149 + */
1.150 + public PriorityQueue(int initialCapacity,
1.151 + Comparator<? super E> comparator) {
1.152 + // Note: This restriction of at least one is not actually needed,
1.153 + // but continues for 1.5 compatibility
1.154 + if (initialCapacity < 1)
1.155 + throw new IllegalArgumentException();
1.156 + this.queue = new Object[initialCapacity];
1.157 + this.comparator = comparator;
1.158 + }
1.159 +
1.160 + /**
1.161 + * Creates a {@code PriorityQueue} containing the elements in the
1.162 + * specified collection. If the specified collection is an instance of
1.163 + * a {@link SortedSet} or is another {@code PriorityQueue}, this
1.164 + * priority queue will be ordered according to the same ordering.
1.165 + * Otherwise, this priority queue will be ordered according to the
1.166 + * {@linkplain Comparable natural ordering} of its elements.
1.167 + *
1.168 + * @param c the collection whose elements are to be placed
1.169 + * into this priority queue
1.170 + * @throws ClassCastException if elements of the specified collection
1.171 + * cannot be compared to one another according to the priority
1.172 + * queue's ordering
1.173 + * @throws NullPointerException if the specified collection or any
1.174 + * of its elements are null
1.175 + */
1.176 + @SuppressWarnings("unchecked")
1.177 + public PriorityQueue(Collection<? extends E> c) {
1.178 + if (c instanceof SortedSet<?>) {
1.179 + SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
1.180 + this.comparator = (Comparator<? super E>) ss.comparator();
1.181 + initElementsFromCollection(ss);
1.182 + }
1.183 + else if (c instanceof PriorityQueue<?>) {
1.184 + PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
1.185 + this.comparator = (Comparator<? super E>) pq.comparator();
1.186 + initFromPriorityQueue(pq);
1.187 + }
1.188 + else {
1.189 + this.comparator = null;
1.190 + initFromCollection(c);
1.191 + }
1.192 + }
1.193 +
1.194 + /**
1.195 + * Creates a {@code PriorityQueue} containing the elements in the
1.196 + * specified priority queue. This priority queue will be
1.197 + * ordered according to the same ordering as the given priority
1.198 + * queue.
1.199 + *
1.200 + * @param c the priority queue whose elements are to be placed
1.201 + * into this priority queue
1.202 + * @throws ClassCastException if elements of {@code c} cannot be
1.203 + * compared to one another according to {@code c}'s
1.204 + * ordering
1.205 + * @throws NullPointerException if the specified priority queue or any
1.206 + * of its elements are null
1.207 + */
1.208 + @SuppressWarnings("unchecked")
1.209 + public PriorityQueue(PriorityQueue<? extends E> c) {
1.210 + this.comparator = (Comparator<? super E>) c.comparator();
1.211 + initFromPriorityQueue(c);
1.212 + }
1.213 +
1.214 + /**
1.215 + * Creates a {@code PriorityQueue} containing the elements in the
1.216 + * specified sorted set. This priority queue will be ordered
1.217 + * according to the same ordering as the given sorted set.
1.218 + *
1.219 + * @param c the sorted set whose elements are to be placed
1.220 + * into this priority queue
1.221 + * @throws ClassCastException if elements of the specified sorted
1.222 + * set cannot be compared to one another according to the
1.223 + * sorted set's ordering
1.224 + * @throws NullPointerException if the specified sorted set or any
1.225 + * of its elements are null
1.226 + */
1.227 + @SuppressWarnings("unchecked")
1.228 + public PriorityQueue(SortedSet<? extends E> c) {
1.229 + this.comparator = (Comparator<? super E>) c.comparator();
1.230 + initElementsFromCollection(c);
1.231 + }
1.232 +
1.233 + private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
1.234 + if (c.getClass() == PriorityQueue.class) {
1.235 + this.queue = c.toArray();
1.236 + this.size = c.size();
1.237 + } else {
1.238 + initFromCollection(c);
1.239 + }
1.240 + }
1.241 +
1.242 + private void initElementsFromCollection(Collection<? extends E> c) {
1.243 + Object[] a = c.toArray();
1.244 + // If c.toArray incorrectly doesn't return Object[], copy it.
1.245 + if (a.getClass() != Object[].class)
1.246 + a = Arrays.copyOf(a, a.length, Object[].class);
1.247 + int len = a.length;
1.248 + if (len == 1 || this.comparator != null)
1.249 + for (int i = 0; i < len; i++)
1.250 + if (a[i] == null)
1.251 + throw new NullPointerException();
1.252 + this.queue = a;
1.253 + this.size = a.length;
1.254 + }
1.255 +
1.256 + /**
1.257 + * Initializes queue array with elements from the given Collection.
1.258 + *
1.259 + * @param c the collection
1.260 + */
1.261 + private void initFromCollection(Collection<? extends E> c) {
1.262 + initElementsFromCollection(c);
1.263 + heapify();
1.264 + }
1.265 +
1.266 + /**
1.267 + * The maximum size of array to allocate.
1.268 + * Some VMs reserve some header words in an array.
1.269 + * Attempts to allocate larger arrays may result in
1.270 + * OutOfMemoryError: Requested array size exceeds VM limit
1.271 + */
1.272 + private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1.273 +
1.274 + /**
1.275 + * Increases the capacity of the array.
1.276 + *
1.277 + * @param minCapacity the desired minimum capacity
1.278 + */
1.279 + private void grow(int minCapacity) {
1.280 + int oldCapacity = queue.length;
1.281 + // Double size if small; else grow by 50%
1.282 + int newCapacity = oldCapacity + ((oldCapacity < 64) ?
1.283 + (oldCapacity + 2) :
1.284 + (oldCapacity >> 1));
1.285 + // overflow-conscious code
1.286 + if (newCapacity - MAX_ARRAY_SIZE > 0)
1.287 + newCapacity = hugeCapacity(minCapacity);
1.288 + queue = Arrays.copyOf(queue, newCapacity);
1.289 + }
1.290 +
1.291 + private static int hugeCapacity(int minCapacity) {
1.292 + if (minCapacity < 0) // overflow
1.293 + throw new OutOfMemoryError();
1.294 + return (minCapacity > MAX_ARRAY_SIZE) ?
1.295 + Integer.MAX_VALUE :
1.296 + MAX_ARRAY_SIZE;
1.297 + }
1.298 +
1.299 + /**
1.300 + * Inserts the specified element into this priority queue.
1.301 + *
1.302 + * @return {@code true} (as specified by {@link Collection#add})
1.303 + * @throws ClassCastException if the specified element cannot be
1.304 + * compared with elements currently in this priority queue
1.305 + * according to the priority queue's ordering
1.306 + * @throws NullPointerException if the specified element is null
1.307 + */
1.308 + public boolean add(E e) {
1.309 + return offer(e);
1.310 + }
1.311 +
1.312 + /**
1.313 + * Inserts the specified element into this priority queue.
1.314 + *
1.315 + * @return {@code true} (as specified by {@link Queue#offer})
1.316 + * @throws ClassCastException if the specified element cannot be
1.317 + * compared with elements currently in this priority queue
1.318 + * according to the priority queue's ordering
1.319 + * @throws NullPointerException if the specified element is null
1.320 + */
1.321 + public boolean offer(E e) {
1.322 + if (e == null)
1.323 + throw new NullPointerException();
1.324 + modCount++;
1.325 + int i = size;
1.326 + if (i >= queue.length)
1.327 + grow(i + 1);
1.328 + size = i + 1;
1.329 + if (i == 0)
1.330 + queue[0] = e;
1.331 + else
1.332 + siftUp(i, e);
1.333 + return true;
1.334 + }
1.335 +
1.336 + public E peek() {
1.337 + if (size == 0)
1.338 + return null;
1.339 + return (E) queue[0];
1.340 + }
1.341 +
1.342 + private int indexOf(Object o) {
1.343 + if (o != null) {
1.344 + for (int i = 0; i < size; i++)
1.345 + if (o.equals(queue[i]))
1.346 + return i;
1.347 + }
1.348 + return -1;
1.349 + }
1.350 +
1.351 + /**
1.352 + * Removes a single instance of the specified element from this queue,
1.353 + * if it is present. More formally, removes an element {@code e} such
1.354 + * that {@code o.equals(e)}, if this queue contains one or more such
1.355 + * elements. Returns {@code true} if and only if this queue contained
1.356 + * the specified element (or equivalently, if this queue changed as a
1.357 + * result of the call).
1.358 + *
1.359 + * @param o element to be removed from this queue, if present
1.360 + * @return {@code true} if this queue changed as a result of the call
1.361 + */
1.362 + public boolean remove(Object o) {
1.363 + int i = indexOf(o);
1.364 + if (i == -1)
1.365 + return false;
1.366 + else {
1.367 + removeAt(i);
1.368 + return true;
1.369 + }
1.370 + }
1.371 +
1.372 + /**
1.373 + * Version of remove using reference equality, not equals.
1.374 + * Needed by iterator.remove.
1.375 + *
1.376 + * @param o element to be removed from this queue, if present
1.377 + * @return {@code true} if removed
1.378 + */
1.379 + boolean removeEq(Object o) {
1.380 + for (int i = 0; i < size; i++) {
1.381 + if (o == queue[i]) {
1.382 + removeAt(i);
1.383 + return true;
1.384 + }
1.385 + }
1.386 + return false;
1.387 + }
1.388 +
1.389 + /**
1.390 + * Returns {@code true} if this queue contains the specified element.
1.391 + * More formally, returns {@code true} if and only if this queue contains
1.392 + * at least one element {@code e} such that {@code o.equals(e)}.
1.393 + *
1.394 + * @param o object to be checked for containment in this queue
1.395 + * @return {@code true} if this queue contains the specified element
1.396 + */
1.397 + public boolean contains(Object o) {
1.398 + return indexOf(o) != -1;
1.399 + }
1.400 +
1.401 + /**
1.402 + * Returns an array containing all of the elements in this queue.
1.403 + * The elements are in no particular order.
1.404 + *
1.405 + * <p>The returned array will be "safe" in that no references to it are
1.406 + * maintained by this queue. (In other words, this method must allocate
1.407 + * a new array). The caller is thus free to modify the returned array.
1.408 + *
1.409 + * <p>This method acts as bridge between array-based and collection-based
1.410 + * APIs.
1.411 + *
1.412 + * @return an array containing all of the elements in this queue
1.413 + */
1.414 + public Object[] toArray() {
1.415 + return Arrays.copyOf(queue, size);
1.416 + }
1.417 +
1.418 + /**
1.419 + * Returns an array containing all of the elements in this queue; the
1.420 + * runtime type of the returned array is that of the specified array.
1.421 + * The returned array elements are in no particular order.
1.422 + * If the queue fits in the specified array, it is returned therein.
1.423 + * Otherwise, a new array is allocated with the runtime type of the
1.424 + * specified array and the size of this queue.
1.425 + *
1.426 + * <p>If the queue fits in the specified array with room to spare
1.427 + * (i.e., the array has more elements than the queue), the element in
1.428 + * the array immediately following the end of the collection is set to
1.429 + * {@code null}.
1.430 + *
1.431 + * <p>Like the {@link #toArray()} method, this method acts as bridge between
1.432 + * array-based and collection-based APIs. Further, this method allows
1.433 + * precise control over the runtime type of the output array, and may,
1.434 + * under certain circumstances, be used to save allocation costs.
1.435 + *
1.436 + * <p>Suppose <tt>x</tt> is a queue known to contain only strings.
1.437 + * The following code can be used to dump the queue into a newly
1.438 + * allocated array of <tt>String</tt>:
1.439 + *
1.440 + * <pre>
1.441 + * String[] y = x.toArray(new String[0]);</pre>
1.442 + *
1.443 + * Note that <tt>toArray(new Object[0])</tt> is identical in function to
1.444 + * <tt>toArray()</tt>.
1.445 + *
1.446 + * @param a the array into which the elements of the queue are to
1.447 + * be stored, if it is big enough; otherwise, a new array of the
1.448 + * same runtime type is allocated for this purpose.
1.449 + * @return an array containing all of the elements in this queue
1.450 + * @throws ArrayStoreException if the runtime type of the specified array
1.451 + * is not a supertype of the runtime type of every element in
1.452 + * this queue
1.453 + * @throws NullPointerException if the specified array is null
1.454 + */
1.455 + public <T> T[] toArray(T[] a) {
1.456 + if (a.length < size)
1.457 + // Make a new array of a's runtime type, but my contents:
1.458 + return (T[]) Arrays.copyOf(queue, size, a.getClass());
1.459 + System.arraycopy(queue, 0, a, 0, size);
1.460 + if (a.length > size)
1.461 + a[size] = null;
1.462 + return a;
1.463 + }
1.464 +
1.465 + /**
1.466 + * Returns an iterator over the elements in this queue. The iterator
1.467 + * does not return the elements in any particular order.
1.468 + *
1.469 + * @return an iterator over the elements in this queue
1.470 + */
1.471 + public Iterator<E> iterator() {
1.472 + return new Itr();
1.473 + }
1.474 +
1.475 + private final class Itr implements Iterator<E> {
1.476 + /**
1.477 + * Index (into queue array) of element to be returned by
1.478 + * subsequent call to next.
1.479 + */
1.480 + private int cursor = 0;
1.481 +
1.482 + /**
1.483 + * Index of element returned by most recent call to next,
1.484 + * unless that element came from the forgetMeNot list.
1.485 + * Set to -1 if element is deleted by a call to remove.
1.486 + */
1.487 + private int lastRet = -1;
1.488 +
1.489 + /**
1.490 + * A queue of elements that were moved from the unvisited portion of
1.491 + * the heap into the visited portion as a result of "unlucky" element
1.492 + * removals during the iteration. (Unlucky element removals are those
1.493 + * that require a siftup instead of a siftdown.) We must visit all of
1.494 + * the elements in this list to complete the iteration. We do this
1.495 + * after we've completed the "normal" iteration.
1.496 + *
1.497 + * We expect that most iterations, even those involving removals,
1.498 + * will not need to store elements in this field.
1.499 + */
1.500 + private ArrayDeque<E> forgetMeNot = null;
1.501 +
1.502 + /**
1.503 + * Element returned by the most recent call to next iff that
1.504 + * element was drawn from the forgetMeNot list.
1.505 + */
1.506 + private E lastRetElt = null;
1.507 +
1.508 + /**
1.509 + * The modCount value that the iterator believes that the backing
1.510 + * Queue should have. If this expectation is violated, the iterator
1.511 + * has detected concurrent modification.
1.512 + */
1.513 + private int expectedModCount = modCount;
1.514 +
1.515 + public boolean hasNext() {
1.516 + return cursor < size ||
1.517 + (forgetMeNot != null && !forgetMeNot.isEmpty());
1.518 + }
1.519 +
1.520 + public E next() {
1.521 + if (expectedModCount != modCount)
1.522 + throw new ConcurrentModificationException();
1.523 + if (cursor < size)
1.524 + return (E) queue[lastRet = cursor++];
1.525 + if (forgetMeNot != null) {
1.526 + lastRet = -1;
1.527 + lastRetElt = forgetMeNot.poll();
1.528 + if (lastRetElt != null)
1.529 + return lastRetElt;
1.530 + }
1.531 + throw new NoSuchElementException();
1.532 + }
1.533 +
1.534 + public void remove() {
1.535 + if (expectedModCount != modCount)
1.536 + throw new ConcurrentModificationException();
1.537 + if (lastRet != -1) {
1.538 + E moved = PriorityQueue.this.removeAt(lastRet);
1.539 + lastRet = -1;
1.540 + if (moved == null)
1.541 + cursor--;
1.542 + else {
1.543 + if (forgetMeNot == null)
1.544 + forgetMeNot = new ArrayDeque<>();
1.545 + forgetMeNot.add(moved);
1.546 + }
1.547 + } else if (lastRetElt != null) {
1.548 + PriorityQueue.this.removeEq(lastRetElt);
1.549 + lastRetElt = null;
1.550 + } else {
1.551 + throw new IllegalStateException();
1.552 + }
1.553 + expectedModCount = modCount;
1.554 + }
1.555 + }
1.556 +
1.557 + public int size() {
1.558 + return size;
1.559 + }
1.560 +
1.561 + /**
1.562 + * Removes all of the elements from this priority queue.
1.563 + * The queue will be empty after this call returns.
1.564 + */
1.565 + public void clear() {
1.566 + modCount++;
1.567 + for (int i = 0; i < size; i++)
1.568 + queue[i] = null;
1.569 + size = 0;
1.570 + }
1.571 +
1.572 + public E poll() {
1.573 + if (size == 0)
1.574 + return null;
1.575 + int s = --size;
1.576 + modCount++;
1.577 + E result = (E) queue[0];
1.578 + E x = (E) queue[s];
1.579 + queue[s] = null;
1.580 + if (s != 0)
1.581 + siftDown(0, x);
1.582 + return result;
1.583 + }
1.584 +
1.585 + /**
1.586 + * Removes the ith element from queue.
1.587 + *
1.588 + * Normally this method leaves the elements at up to i-1,
1.589 + * inclusive, untouched. Under these circumstances, it returns
1.590 + * null. Occasionally, in order to maintain the heap invariant,
1.591 + * it must swap a later element of the list with one earlier than
1.592 + * i. Under these circumstances, this method returns the element
1.593 + * that was previously at the end of the list and is now at some
1.594 + * position before i. This fact is used by iterator.remove so as to
1.595 + * avoid missing traversing elements.
1.596 + */
1.597 + private E removeAt(int i) {
1.598 + assert i >= 0 && i < size;
1.599 + modCount++;
1.600 + int s = --size;
1.601 + if (s == i) // removed last element
1.602 + queue[i] = null;
1.603 + else {
1.604 + E moved = (E) queue[s];
1.605 + queue[s] = null;
1.606 + siftDown(i, moved);
1.607 + if (queue[i] == moved) {
1.608 + siftUp(i, moved);
1.609 + if (queue[i] != moved)
1.610 + return moved;
1.611 + }
1.612 + }
1.613 + return null;
1.614 + }
1.615 +
1.616 + /**
1.617 + * Inserts item x at position k, maintaining heap invariant by
1.618 + * promoting x up the tree until it is greater than or equal to
1.619 + * its parent, or is the root.
1.620 + *
1.621 + * To simplify and speed up coercions and comparisons. the
1.622 + * Comparable and Comparator versions are separated into different
1.623 + * methods that are otherwise identical. (Similarly for siftDown.)
1.624 + *
1.625 + * @param k the position to fill
1.626 + * @param x the item to insert
1.627 + */
1.628 + private void siftUp(int k, E x) {
1.629 + if (comparator != null)
1.630 + siftUpUsingComparator(k, x);
1.631 + else
1.632 + siftUpComparable(k, x);
1.633 + }
1.634 +
1.635 + private void siftUpComparable(int k, E x) {
1.636 + Comparable<? super E> key = (Comparable<? super E>) x;
1.637 + while (k > 0) {
1.638 + int parent = (k - 1) >>> 1;
1.639 + Object e = queue[parent];
1.640 + if (key.compareTo((E) e) >= 0)
1.641 + break;
1.642 + queue[k] = e;
1.643 + k = parent;
1.644 + }
1.645 + queue[k] = key;
1.646 + }
1.647 +
1.648 + private void siftUpUsingComparator(int k, E x) {
1.649 + while (k > 0) {
1.650 + int parent = (k - 1) >>> 1;
1.651 + Object e = queue[parent];
1.652 + if (comparator.compare(x, (E) e) >= 0)
1.653 + break;
1.654 + queue[k] = e;
1.655 + k = parent;
1.656 + }
1.657 + queue[k] = x;
1.658 + }
1.659 +
1.660 + /**
1.661 + * Inserts item x at position k, maintaining heap invariant by
1.662 + * demoting x down the tree repeatedly until it is less than or
1.663 + * equal to its children or is a leaf.
1.664 + *
1.665 + * @param k the position to fill
1.666 + * @param x the item to insert
1.667 + */
1.668 + private void siftDown(int k, E x) {
1.669 + if (comparator != null)
1.670 + siftDownUsingComparator(k, x);
1.671 + else
1.672 + siftDownComparable(k, x);
1.673 + }
1.674 +
1.675 + private void siftDownComparable(int k, E x) {
1.676 + Comparable<? super E> key = (Comparable<? super E>)x;
1.677 + int half = size >>> 1; // loop while a non-leaf
1.678 + while (k < half) {
1.679 + int child = (k << 1) + 1; // assume left child is least
1.680 + Object c = queue[child];
1.681 + int right = child + 1;
1.682 + if (right < size &&
1.683 + ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
1.684 + c = queue[child = right];
1.685 + if (key.compareTo((E) c) <= 0)
1.686 + break;
1.687 + queue[k] = c;
1.688 + k = child;
1.689 + }
1.690 + queue[k] = key;
1.691 + }
1.692 +
1.693 + private void siftDownUsingComparator(int k, E x) {
1.694 + int half = size >>> 1;
1.695 + while (k < half) {
1.696 + int child = (k << 1) + 1;
1.697 + Object c = queue[child];
1.698 + int right = child + 1;
1.699 + if (right < size &&
1.700 + comparator.compare((E) c, (E) queue[right]) > 0)
1.701 + c = queue[child = right];
1.702 + if (comparator.compare(x, (E) c) <= 0)
1.703 + break;
1.704 + queue[k] = c;
1.705 + k = child;
1.706 + }
1.707 + queue[k] = x;
1.708 + }
1.709 +
1.710 + /**
1.711 + * Establishes the heap invariant (described above) in the entire tree,
1.712 + * assuming nothing about the order of the elements prior to the call.
1.713 + */
1.714 + private void heapify() {
1.715 + for (int i = (size >>> 1) - 1; i >= 0; i--)
1.716 + siftDown(i, (E) queue[i]);
1.717 + }
1.718 +
1.719 + /**
1.720 + * Returns the comparator used to order the elements in this
1.721 + * queue, or {@code null} if this queue is sorted according to
1.722 + * the {@linkplain Comparable natural ordering} of its elements.
1.723 + *
1.724 + * @return the comparator used to order this queue, or
1.725 + * {@code null} if this queue is sorted according to the
1.726 + * natural ordering of its elements
1.727 + */
1.728 + public Comparator<? super E> comparator() {
1.729 + return comparator;
1.730 + }
1.731 +
1.732 + /**
1.733 + * Saves the state of the instance to a stream (that
1.734 + * is, serializes it).
1.735 + *
1.736 + * @serialData The length of the array backing the instance is
1.737 + * emitted (int), followed by all of its elements
1.738 + * (each an {@code Object}) in the proper order.
1.739 + * @param s the stream
1.740 + */
1.741 + private void writeObject(java.io.ObjectOutputStream s)
1.742 + throws java.io.IOException{
1.743 + // Write out element count, and any hidden stuff
1.744 + s.defaultWriteObject();
1.745 +
1.746 + // Write out array length, for compatibility with 1.5 version
1.747 + s.writeInt(Math.max(2, size + 1));
1.748 +
1.749 + // Write out all elements in the "proper order".
1.750 + for (int i = 0; i < size; i++)
1.751 + s.writeObject(queue[i]);
1.752 + }
1.753 +
1.754 + /**
1.755 + * Reconstitutes the {@code PriorityQueue} instance from a stream
1.756 + * (that is, deserializes it).
1.757 + *
1.758 + * @param s the stream
1.759 + */
1.760 + private void readObject(java.io.ObjectInputStream s)
1.761 + throws java.io.IOException, ClassNotFoundException {
1.762 + // Read in size, and any hidden stuff
1.763 + s.defaultReadObject();
1.764 +
1.765 + // Read in (and discard) array length
1.766 + s.readInt();
1.767 +
1.768 + queue = new Object[size];
1.769 +
1.770 + // Read in all elements.
1.771 + for (int i = 0; i < size; i++)
1.772 + queue[i] = s.readObject();
1.773 +
1.774 + // Elements are guaranteed to be in "proper order", but the
1.775 + // spec has never explained what that might be.
1.776 + heapify();
1.777 + }
1.778 +}