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