1.1 --- a/emul/compact/src/main/java/java/util/PriorityQueue.java Mon Feb 25 19:00:08 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,731 +0,0 @@
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 -}