    001    /*
    002     * Copyright (C) 2010 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License");
    005     * you may not use this file except in compliance with the License.
    006     * You may obtain a copy of the License at
    007     *
    008     * http://www.apache.org/licenses/LICENSE-2.0
    009     *
    010     * Unless required by applicable law or agreed to in writing, software
    011     * distributed under the License is distributed on an "AS IS" BASIS,
    012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    013     * See the License for the specific language governing permissions and
    014     * limitations under the License.
    015     */
    016
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021    import static com.google.common.base.Preconditions.checkPositionIndex;
    022    import static com.google.common.base.Preconditions.checkState;
    023
    024    import com.google.common.annotations.Beta;
    025    import com.google.common.annotations.VisibleForTesting;
    026
    027    import java.util.AbstractQueue;
    028    import java.util.ArrayList;
    029    import java.util.Collection;
    030    import java.util.Collections;
    031    import java.util.Comparator;
    032    import java.util.ConcurrentModificationException;
    033    import java.util.Iterator;
    034    import java.util.LinkedList;
    035    import java.util.List;
    036    import java.util.NoSuchElementException;
    037    import java.util.PriorityQueue;
    038    import java.util.Queue;
    039
    040    /**
    041     * A double-ended priority queue, which provides constant-time access to both
    042     * its least element and its greatest element, as determined by the queue's
    043     * specified comparator. If no comparator is given at construction time, the
    044     * natural order of elements is used.
    045     *
    046     * <p>As a {@link Queue} it functions exactly as a {@link PriorityQueue}: its
    047     * head element -- the implicit target of the methods {@link #peek()}, {@link
    048     * #poll()} and {@link #remove()} -- is defined as the <i>least</i> element in
    049     * the queue according to the queue's comparator. But unlike a regular priority
    050     * queue, the methods {@link #peekLast}, {@link #pollLast} and
    051     * {@link #removeLast} are also provided, to act on the <i>greatest</i> element
    052     * in the queue instead.
    053     *
    054     * <p>A min-max priority queue can be configured with a maximum size. If so,
    055     * each time the size of the queue exceeds that value, the queue automatically
    056     * removes its greatest element according to its comparator (which might be the
    057     * element that was just added). This is different from conventional bounded
    058     * queues, which either block or reject new elements when full.
    059     *
    060     * <p>This implementation is based on the
    061     * <a href="http://portal.acm.org/citation.cfm?id=6621">min-max heap</a>
    062     * developed by Atkinson, et al. Unlike many other double-ended priority queues,
    063     * it stores elements in a single array, as compact as the traditional heap data
    064     * structure used in {@link PriorityQueue}.
    065     *
    066     * <p>This class is not thread-safe, and does not accept null elements.
    067     *
    068     * <p><i>Performance notes:</i>
    069     *
    070     * <ul>
    071     * <li>The retrieval operations {@link #peek}, {@link #peekFirst}, {@link
    072     *     #peekLast}, {@link #element}, and {@link #size} are constant-time
    073     * <li>The enqueing and dequeing operations ({@link #offer}, {@link #add}, and
    074     *     all the forms of {@link #poll} and {@link #remove()}) run in {@code
    075     *     O(log n) time}
    076     * <li>The {@link #remove(Object)} and {@link #contains} operations require
    077     *     linear ({@code O(n)}) time
    078     * <li>If you only access one end of the queue, and don't use a maximum size,
    079     *     this class is functionally equivalent to {@link PriorityQueue}, but
    080     *     significantly slower.
    081     * </ul>
    082     *
    083     * @author Sverre Sundsdal
    084     * @author Torbjorn Gannholm
    085     * @since 8.0
    086     */
    087    // TODO(kevinb): @GwtCompatible
    088    @Beta
    089    public final class MinMaxPriorityQueue<E> extends AbstractQueue<E> {
    090
    091      /**
    092       * Creates a new min-max priority queue with default settings: natural order,
    093       * no maximum size, no initial contents, and an initial expected size of 11.
    094       */
    095      public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() {
    096        return new Builder<Comparable>(Ordering.natural()).create();
    097      }
    098
    099      /**
    100       * Creates a new min-max priority queue using natural order, no maximum size,
    101       * and initially containing the given elements.
    102       */
    103      public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create(
    104          Iterable<? extends E> initialContents) {
    105        return new Builder<E>(Ordering.<E>natural()).create(initialContents);
    106      }
    107
    108      /**
    109       * Creates and returns a new builder, configured to build {@code
    110       * MinMaxPriorityQueue} instances that use {@code comparator} to determine the
    111       * least and greatest elements.
    112       */
    113      public static <B> Builder<B> orderedBy(Comparator<B> comparator) {
    114        return new Builder<B>(comparator);
    115      }
    116
    117      /**
    118       * Creates and returns a new builder, configured to build {@code
    119       * MinMaxPriorityQueue} instances sized appropriately to hold {@code
    120       * expectedSize} elements.
    121       */
    122      public static Builder<Comparable> expectedSize(int expectedSize) {
    123        return new Builder<Comparable>(Ordering.natural())
    124            .expectedSize(expectedSize);
    125      }
    126
    127      /**
    128       * Creates and returns a new builder, configured to build {@code
    129       * MinMaxPriorityQueue} instances that are limited to {@code maximumSize}
    130       * elements. Each time a queue grows beyond this bound, it immediately
    131       * removes its greatest element (according to its comparator), which might be
    132       * the element that was just added.
    133       */
    134      public static Builder<Comparable> maximumSize(int maximumSize) {
    135        return new Builder<Comparable>(Ordering.natural())
    136            .maximumSize(maximumSize);
    137      }
    138
    139      /**
    140       * The builder class used in creation of min-max priority queues. Instead of
    141       * constructing one directly, use {@link
    142       * MinMaxPriorityQueue#orderedBy(Comparator)}, {@link
    143       * MinMaxPriorityQueue#expectedSize(int)} or {@link
    144       * MinMaxPriorityQueue#maximumSize(int)}.
    145       *
    146       * @param <B> the upper bound on the eventual type that can be produced by
    147       *     this builder (for example, a {@code Builder<Number>} can produce a
    148       *     {@code Queue<Number>} or {@code Queue<Integer>} but not a {@code
    149       *     Queue<Object>}).
    150       * @since 8.0
    151       */
    152      @Beta
    153      public static final class Builder<B> {
    154        /*
    155         * TODO(kevinb): when the dust settles, see if we still need this or can
    156         * just default to DEFAULT_CAPACITY.
    157         */
    158        private static final int UNSET_EXPECTED_SIZE = -1;
    159
    160        private final Comparator<B> comparator;
    161        private int expectedSize = UNSET_EXPECTED_SIZE;
    162        private int maximumSize = Integer.MAX_VALUE;
    163
    164        private Builder(Comparator<B> comparator) {
    165          this.comparator = checkNotNull(comparator);
    166        }
    167
    168        /**
    169         * Configures this builder to build min-max priority queues with an initial
    170         * expected size of {@code expectedSize}.
    171         */
    172        public Builder<B> expectedSize(int expectedSize) {
    173          checkArgument(expectedSize >= 0);
    174          this.expectedSize = expectedSize;
    175          return this;
    176        }
    177
    178        /**
    179         * Configures this builder to build {@code MinMaxPriorityQueue} instances
    180         * that are limited to {@code maximumSize} elements. Each time a queue grows
    181         * beyond this bound, it immediately removes its greatest element (according
    182         * to its comparator), which might be the element that was just added.
    183         */
    184        public Builder<B> maximumSize(int maximumSize) {
    185          checkArgument(maximumSize > 0);
    186          this.maximumSize = maximumSize;
    187          return this;
    188        }
    189
    190        /**
    191         * Builds a new min-max priority queue using the previously specified
    192         * options, and having no initial contents.
    193         */
    194        public <T extends B> MinMaxPriorityQueue<T> create() {
    195          return create(Collections.<T>emptySet());
    196        }
    197
    198        /**
    199         * Builds a new min-max priority queue using the previously specified
    200         * options, and having the given initial elements.
    201         */
    202        public <T extends B> MinMaxPriorityQueue<T> create(
    203            Iterable<? extends T> initialContents) {
    204          MinMaxPriorityQueue<T> queue = new MinMaxPriorityQueue<T>(
    205              this, initialQueueSize(expectedSize, maximumSize, initialContents));
    206          for (T element : initialContents) {
    207            queue.offer(element);
    208          }
    209          return queue;
    210        }
    211
    212        @SuppressWarnings("unchecked") // safe "contravariant cast"
    213        private <T extends B> Ordering<T> ordering() {
    214          return Ordering.from((Comparator<T>) comparator);
    215        }
    216      }
    217
    218      private final Heap minHeap;
    219      private final Heap maxHeap;
    220      @VisibleForTesting final int maximumSize;
    221      private Object[] queue;
    222      private int size;
    223      private int modCount;
    224
    225      private MinMaxPriorityQueue(Builder<? super E> builder, int queueSize) {
    226        Ordering<E> ordering = builder.ordering();
    227        this.minHeap = new Heap(ordering);
    228        this.maxHeap = new Heap(ordering.reverse());
    229        minHeap.otherHeap = maxHeap;
    230        maxHeap.otherHeap = minHeap;
    231
    232        this.maximumSize = builder.maximumSize;
    233        // TODO(kevinb): pad?
    234        this.queue = new Object[queueSize];
    235      }
    236
    237      @Override public int size() {
    238        return size;
    239      }
    240
    241      /**
    242       * Adds the given element to this queue. If this queue has a maximum size,
    243       * after adding {@code element} the queue will automatically evict its
    244       * greatest element (according to its comparator), which may be {@code
    245       * element} itself.
    246       *
    247       * @return {@code true} always
    248       */
    249      @Override public boolean add(E element) {
    250        offer(element);
    251        return true;
    252      }
    253
    254      @Override public boolean addAll(Collection<? extends E> newElements) {
    255        boolean modified = false;
    256        for (E element : newElements) {
    257          offer(element);
    258          modified = true;
    259        }
    260        return modified;
    261      }
    262
    263      /**
    264       * Adds the given element to this queue. If this queue has a maximum size,
    265       * after adding {@code element} the queue will automatically evict its
    266       * greatest element (according to its comparator), which may be {@code
    267       * element} itself.
    268       */
    269      @Override public boolean offer(E element) {
    270        checkNotNull(element);
    271        modCount++;
    272        int insertIndex = size++;
    273
    274        growIfNeeded();
    275
    276        // Adds the element to the end of the heap and bubbles it up to the correct
    277        // position.
    278        heapForIndex(insertIndex).bubbleUp(insertIndex, element);
    279        return size <= maximumSize || pollLast() != element;
    280      }
    281
    282      @Override public E poll() {
    283        return isEmpty() ? null : removeAndGet(0);
    284      }
    285
    286      @SuppressWarnings("unchecked") // we must carefully only allow Es to get in
    287      E elementData(int index) {
    288        return (E) queue[index];
    289      }
    290
    291      @Override public E peek() {
    292        return isEmpty() ? null : elementData(0);
    293      }
    294
    295      /**
    296       * Returns the index of the max element.
    297       */
    298      private int getMaxElementIndex() {
    299        switch (size) {
    300          case 1:
    301            return 0; // The lone element in the queue is the maximum.
    302          case 2:
    303            return 1; // The lone element in the maxHeap is the maximum.
    304          default:
    305            // The max element must sit on the first level of the maxHeap. It is
    306            // actually the *lesser* of the two from the maxHeap's perspective.
    307            return (maxHeap.compareElements(1, 2) <= 0) ? 1 : 2;
    308        }
    309      }
    310
    311      /**
    312       * Removes and returns the least element of this queue, or returns {@code
    313       * null} if the queue is empty.
    314       */
    315      public E pollFirst() {
    316        return poll();
    317      }
    318
    319      /**
    320       * Removes and returns the least element of this queue.
    321       *
    322       * @throws NoSuchElementException if the queue is empty
    323       */
    324      public E removeFirst() {
    325        return remove();
    326      }
    327
    328      /**
    329       * Retrieves, but does not remove, the least element of this queue, or returns
    330       * {@code null} if the queue is empty.
    331       */
    332      public E peekFirst() {
    333        return peek();
    334      }
    335
    336      /**
    337       * Removes and returns the greatest element of this queue, or returns {@code
    338       * null} if the queue is empty.
    339       */
    340      public E pollLast() {
    341        return isEmpty() ? null : removeAndGet(getMaxElementIndex());
    342      }
    343
    344      /**
    345       * Removes and returns the greatest element of this queue.
    346       *
    347       * @throws NoSuchElementException if the queue is empty
    348       */
    349      public E removeLast() {
    350        if (isEmpty()) {
    351          throw new NoSuchElementException();
    352        }
    353        return removeAndGet(getMaxElementIndex());
    354      }
    355
    356      /**
    357       * Retrieves, but does not remove, the greatest element of this queue, or
    358       * returns {@code null} if the queue is empty.
    359       */
    360      public E peekLast() {
    361        return isEmpty() ? null : elementData(getMaxElementIndex());
    362      }
    363
    364      /**
    365       * Removes the element at position {@code index}.
    366       *
    367       * <p>Normally this method leaves the elements at up to {@code index - 1},
    368       * inclusive, untouched.  Under these circumstances, it returns {@code null}.
    369       *
    370       * <p>Occasionally, in order to maintain the heap invariant, it must swap a
    371       * later element of the list with one before {@code index}. Under these
    372       * circumstances it returns a pair of elements as a {@link MoveDesc}. The
    373       * first one is the element that was previously at the end of the heap and is
    374       * now at some position before {@code index}. The second element is the one
    375       * that was swapped down to replace the element at {@code index}. This fact is
    376       * used by iterator.remove so as to visit elements during a traversal once and
    377       * only once.
    378       */
    379      @VisibleForTesting MoveDesc<E> removeAt(int index) {
    380        checkPositionIndex(index, size);
    381        modCount++;
    382        size--;
    383        if (size == index) {
    384          queue[size] = null;
    385          return null;
    386        }
    387        E actualLastElement = elementData(size);
    388        int lastElementAt = heapForIndex(size)
    389            .getCorrectLastElement(actualLastElement);
    390        E toTrickle = elementData(size);
    391        queue[size] = null;
    392        MoveDesc<E> changes = fillHole(index, toTrickle);
    393        if (lastElementAt < index) {
    394          // Last element is moved to before index, swapped with trickled element.
    395          if (changes == null) {
    396            // The trickled element is still after index.
    397            return new MoveDesc<E>(actualLastElement, toTrickle);
    398          } else {
    399            // The trickled element is back before index, but the replaced element
    400            // has now been moved after index.
    401            return new MoveDesc<E>(actualLastElement, changes.replaced);
    402          }
    403        }
    404        // Trickled element was after index to begin with, no adjustment needed.
    405        return changes;
    406      }
    407
    408      private MoveDesc<E> fillHole(int index, E toTrickle) {
    409        Heap heap = heapForIndex(index);
    410        // We consider elementData(index) a "hole", and we want to fill it
    411        // with the last element of the heap, toTrickle.
    412        // Since the last element of the heap is from the bottom level, we
    413        // optimistically fill index position with elements from lower levels,
    414        // moving the hole down. In most cases this reduces the number of
    415        // comparisons with toTrickle, but in some cases we will need to bubble it
    416        // all the way up again.
    417        int vacated = heap.fillHoleAt(index);
    418        // Try to see if toTrickle can be bubbled up min levels.
    419        int bubbledTo = heap.bubbleUpAlternatingLevels(vacated, toTrickle);
    420        if (bubbledTo == vacated) {
    421          // Could not bubble toTrickle up min levels, try moving
    422          // it from min level to max level (or max to min level) and bubble up
    423          // there.
    424          return heap.tryCrossOverAndBubbleUp(index, vacated, toTrickle);
    425        } else {
    426          return (bubbledTo < index)
    427              ? new MoveDesc<E>(toTrickle, elementData(index))
    428              : null;
    429        }
    430      }
    431
    432      // Returned from removeAt() to iterator.remove()
    433      static class MoveDesc<E> {
    434        final E toTrickle;
    435        final E replaced;
    436
    437        MoveDesc(E toTrickle, E replaced) {
    438          this.toTrickle = toTrickle;
    439          this.replaced = replaced;
    440        }
    441      }
    442
    443      /**
    444       * Removes and returns the value at {@code index}.
    445       */
    446      private E removeAndGet(int index) {
    447        E value = elementData(index);
    448        removeAt(index);
    449        return value;
    450      }
    451
    452      private Heap heapForIndex(int i) {
    453        return isEvenLevel(i) ? minHeap : maxHeap;
    454      }
    455
    456      private static final int EVEN_POWERS_OF_TWO = 0x55555555;
    457      private static final int ODD_POWERS_OF_TWO = 0xaaaaaaaa;
    458
    459      @VisibleForTesting static boolean isEvenLevel(int index) {
    460        int oneBased = index + 1;
    461        checkState(oneBased > 0, "negative index");
    462        return (oneBased & EVEN_POWERS_OF_TWO) > (oneBased & ODD_POWERS_OF_TWO);
    463      }
    464
    465      /**
    466       * Returns {@code true} if the MinMax heap structure holds. This is only used
    467       * in testing.
    468       *
    469       * TODO(kevinb): move to the test class?
    470       */
    471      @VisibleForTesting boolean isIntact() {
    472        for (int i = 1; i < size; i++) {
    473          if (!heapForIndex(i).verifyIndex(i)) {
    474            return false;
    475          }
    476        }
    477        return true;
    478      }
    479
    480      /**
    481       * Each instance of MinMaxPriortyQueue encapsulates two instances of Heap:
    482       * a min-heap and a max-heap. Conceptually, these might each have their own
    483       * array for storage, but for efficiency's sake they are stored interleaved on
    484       * alternate heap levels in the same array (MMPQ.queue).
    485       */
    486      private class Heap {
    487        final Ordering<E> ordering;
    488        Heap otherHeap;
    489
    490        Heap(Ordering<E> ordering) {
    491          this.ordering = ordering;
    492        }
    493
    494        int compareElements(int a, int b) {
    495          return ordering.compare(elementData(a), elementData(b));
    496        }
    497
    498        /**
    499         * Tries to move {@code toTrickle} from a min to a max level and
    500         * bubble up there. If it moved before {@code removeIndex} this method
    501         * returns a pair as described in {@link #removeAt}.
    502         */
    503        MoveDesc<E> tryCrossOverAndBubbleUp(
    504            int removeIndex, int vacated, E toTrickle) {
    505          int crossOver = crossOver(vacated, toTrickle);
    506          if (crossOver == vacated) {
    507            return null;
    508          }
    509          // Successfully crossed over from min to max.
    510          // Bubble up max levels.
    511          E parent;
    512          // If toTrickle is moved up to a parent of removeIndex, the parent is
    513          // placed in removeIndex position. We must return that to the iterator so
    514          // that it knows to skip it.
    515          if (crossOver < removeIndex) {
    516            // We crossed over to the parent level in crossOver, so the parent
    517            // has already been moved.
    518            parent = elementData(removeIndex);
    519          } else {
    520            parent = elementData(getParentIndex(removeIndex));
    521          }
    522          // bubble it up the opposite heap
    523          if (otherHeap.bubbleUpAlternatingLevels(crossOver, toTrickle)
    524              < removeIndex) {
    525            return new MoveDesc<E>(toTrickle, parent);
    526          } else {
    527            return null;
    528          }
    529        }
    530
    531        /**
    532         * Bubbles a value from {@code index} up the appropriate heap if required.
    533         */
    534        void bubbleUp(int index, E x) {
    535          int crossOver = crossOverUp(index, x);
    536
    537          Heap heap;
    538          if (crossOver == index) {
    539            heap = this;
    540          } else {
    541            index = crossOver;
    542            heap = otherHeap;
    543          }
    544          heap.bubbleUpAlternatingLevels(index, x);
    545        }
    546
    547        /**
    548         * Bubbles a value from {@code index} up the levels of this heap, and
    549         * returns the index the element ended up at.
    550         */
    551        int bubbleUpAlternatingLevels(int index, E x) {
    552          while (index > 2) {
    553            int grandParentIndex = getGrandparentIndex(index);
    554            E e = elementData(grandParentIndex);
    555            if (ordering.compare(e, x) <= 0) {
    556              break;
    557            }
    558            queue[index] = e;
    559            index = grandParentIndex;
    560          }
    561          queue[index] = x;
    562          return index;
    563        }
    564
    565        /**
    566         * Returns the index of minimum value between {@code index} and
    567         * {@code index + len}, or {@code -1} if {@code index} is greater than
    568         * {@code size}.
    569         */
    570        int findMin(int index, int len) {
    571          if (index >= size) {
    572            return -1;
    573          }
    574          checkState(index > 0);
    575          int limit = Math.min(index, size - len) + len;
    576          int minIndex = index;
    577          for (int i = index + 1; i < limit; i++) {
    578            if (compareElements(i, minIndex) < 0) {
    579              minIndex = i;
    580            }
    581          }
    582          return minIndex;
    583        }
    584
    585        /**
    586         * Returns the minimum child or {@code -1} if no child exists.
    587         */
    588        int findMinChild(int index) {
    589          return findMin(getLeftChildIndex(index), 2);
    590        }
    591
    592        /**
    593         * Returns the minimum grand child or -1 if no grand child exists.
    594         */
    595        int findMinGrandChild(int index) {
    596          int leftChildIndex = getLeftChildIndex(index);
    597          if (leftChildIndex < 0) {
    598            return -1;
    599          }
    600          return findMin(getLeftChildIndex(leftChildIndex), 4);
    601        }
    602
    603        /**
    604         * Moves an element one level up from a min level to a max level
    605         * (or vice versa).
    606         * Returns the new position of the element.
    607         */
    608        int crossOverUp(int index, E x) {
    609          if (index == 0) {
    610            queue[0] = x;
    611            return 0;
    612          }
    613          int parentIndex = getParentIndex(index);
    614          E parentElement = elementData(parentIndex);
    615          if (parentIndex != 0) {
    616            // This is a guard for the case of the childless uncle.
    617            // Since the end of the array is actually the middle of the heap,
    618            // a smaller childless uncle can become a child of x when we
    619            // bubble up alternate levels, violating the invariant.
    620            int grandparentIndex = getParentIndex(parentIndex);
    621            int uncleIndex = getRightChildIndex(grandparentIndex);
    622            if (uncleIndex != parentIndex
    623                && getLeftChildIndex(uncleIndex) >= size) {
    624              E uncleElement = elementData(uncleIndex);
    625              if (ordering.compare(uncleElement, parentElement) < 0) {
    626                parentIndex = uncleIndex;
    627                parentElement = uncleElement;
    628              }
    629            }
    630          }
    631          if (ordering.compare(parentElement, x) < 0) {
    632            queue[index] = parentElement;
    633            queue[parentIndex] = x;
    634            return parentIndex;
    635          }
    636          queue[index] = x;
    637          return index;
    638        }
    639
    640        /**
    641         * Returns the conceptually correct last element of the heap.
    642         *
    643         * <p>Since the last element of the array is actually in the
    644         * middle of the sorted structure, a childless uncle node could be
    645         * smaller, which would corrupt the invariant if this element
    646         * becomes the new parent of the uncle. In that case, we first
    647         * switch the last element with its uncle, before returning.
    648         */
    649        int getCorrectLastElement(E actualLastElement) {
    650          int parentIndex = getParentIndex(size);
    651          if (parentIndex != 0) {
    652            int grandparentIndex = getParentIndex(parentIndex);
    653            int uncleIndex = getRightChildIndex(grandparentIndex);
    654            if (uncleIndex != parentIndex
    655                && getLeftChildIndex(uncleIndex) >= size) {
    656              E uncleElement = elementData(uncleIndex);
    657              if (ordering.compare(uncleElement, actualLastElement) < 0) {
    658                queue[uncleIndex] = actualLastElement;
    659                queue[size] = uncleElement;
    660                return uncleIndex;
    661              }
    662            }
    663          }
    664          return size;
    665        }
    666
    667        /**
    668         * Crosses an element over to the opposite heap by moving it one level down
    669         * (or up if there are no elements below it).
    670         *
    671         * Returns the new position of the element.
    672         */
    673        int crossOver(int index, E x) {
    674          int minChildIndex = findMinChild(index);
    675          // TODO(kevinb): split the && into two if's and move crossOverUp so it's
    676          // only called when there's no child.
    677          if ((minChildIndex > 0)
    678              && (ordering.compare(elementData(minChildIndex), x) < 0)) {
    679            queue[index] = elementData(minChildIndex);
    680            queue[minChildIndex] = x;
    681            return minChildIndex;
    682          }
    683          return crossOverUp(index, x);
    684        }
    685
    686        /**
    687         * Fills the hole at {@code index} by moving in the least of its
    688         * grandchildren to this position, then recursively filling the new hole
    689         * created.
    690         *
    691         * @return the position of the new hole (where the lowest grandchild moved
    692         *     from, that had no grandchild to replace it)
    693         */
    694        int fillHoleAt(int index) {
    695          int minGrandchildIndex;
    696          while ((minGrandchildIndex = findMinGrandChild(index)) > 0) {
    697            queue[index] = elementData(minGrandchildIndex);
    698            index = minGrandchildIndex;
    699          }
    700          return index;
    701        }
    702
    703        private boolean verifyIndex(int i) {
    704          if ((getLeftChildIndex(i) < size)
    705              && (compareElements(i, getLeftChildIndex(i)) > 0)) {
    706            return false;
    707          }
    708          if ((getRightChildIndex(i) < size)
    709              && (compareElements(i, getRightChildIndex(i)) > 0)) {
    710            return false;
    711          }
    712          if ((i > 0) && (compareElements(i, getParentIndex(i)) > 0)) {
    713            return false;
    714          }
    715          if ((i > 2) && (compareElements(getGrandparentIndex(i), i) > 0)) {
    716            return false;
    717          }
    718          return true;
    719        }
    720
    721        // These would be static if inner classes could have static members.
    722
    723        private int getLeftChildIndex(int i) {
    724          return i * 2 + 1;
    725        }
    726
    727        private int getRightChildIndex(int i) {
    728          return i * 2 + 2;
    729        }
    730
    731        private int getParentIndex(int i) {
    732          return (i - 1) / 2;
    733        }
    734
    735        private int getGrandparentIndex(int i) {
    736          return getParentIndex(getParentIndex(i)); // (i - 3) / 4
    737        }
    738      }
    739
    740      /**
    741       * Iterates the elements of the queue in no particular order.
    742       *
    743       * If the underlying queue is modified during iteration an exception will be
    744       * thrown.
    745       */
    746      private class QueueIterator implements Iterator<E> {
    747        private int cursor = -1;
    748        private int expectedModCount = modCount;
    749        // TODO(user): Switch to ArrayDeque once Guava supports it.
    750        private Queue<E> forgetMeNot;
    751        private List<E> skipMe;
    752        private E lastFromForgetMeNot;
    753        private boolean canRemove;
    754
    755        @Override public boolean hasNext() {
    756          checkModCount();
    757          return (nextNotInSkipMe(cursor + 1) < size())
    758              || ((forgetMeNot != null) && !forgetMeNot.isEmpty());
    759        }
    760
    761        @Override public E next() {
    762          checkModCount();
    763          int tempCursor = nextNotInSkipMe(cursor + 1);
    764          if (tempCursor < size()) {
    765            cursor = tempCursor;
    766            canRemove = true;
    767            return elementData(cursor);
    768          } else if (forgetMeNot != null) {
    769            cursor = size();
    770            lastFromForgetMeNot = forgetMeNot.poll();
    771            if (lastFromForgetMeNot != null) {
    772              canRemove = true;
    773              return lastFromForgetMeNot;
    774            }
    775          }
    776          throw new NoSuchElementException(
    777              "iterator moved past last element in queue.");
    778        }
    779
    780        @Override public void remove() {
    781          checkState(canRemove,
    782              "no calls to remove() since the last call to next()");
    783          checkModCount();
    784          canRemove = false;
    785          expectedModCount++;
    786          if (cursor < size()) {
    787            MoveDesc<E> moved = removeAt(cursor);
    788            if (moved != null) {
    789              if (forgetMeNot == null) {
    790                forgetMeNot = new LinkedList<E>();
    791                skipMe = new ArrayList<E>(3);
    792              }
    793              forgetMeNot.add(moved.toTrickle);
    794              skipMe.add(moved.replaced);
    795            }
    796            cursor--;
    797          } else { // we must have set lastFromForgetMeNot in next()
    798            checkState(removeExact(lastFromForgetMeNot));
    799            lastFromForgetMeNot = null;
    800          }
    801        }
    802
    803        // Finds only this exact instance, not others that are equals()
    804        private boolean containsExact(Iterable<E> elements, E target) {
    805          for (E element : elements) {
    806            if (element == target) {
    807              return true;
    808            }
    809          }
    810          return false;
    811        }
    812
    813        // Removes only this exact instance, not others that are equals()
    814        boolean removeExact(Object target) {
    815          for (int i = 0; i < size; i++) {
    816            if (queue[i] == target) {
    817              removeAt(i);
    818              return true;
    819            }
    820          }
    821          return false;
    822        }
    823
    824        void checkModCount() {
    825          if (modCount != expectedModCount) {
    826            throw new ConcurrentModificationException();
    827          }
    828        }
    829
    830        /**
    831         * Returns the index of the first element after {@code c} that is not in
    832         * {@code skipMe} and returns {@code size()} if there is no such element.
    833         */
    834        private int nextNotInSkipMe(int c) {
    835          if (skipMe != null) {
    836            while (c < size() && containsExact(skipMe, elementData(c))) {
    837              c++;
    838            }
    839          }
    840          return c;
    841        }
    842      }
    843
    844      /**
    845       * Returns an iterator over the elements contained in this collection,
    846       * <i>in no particular order</i>.
    847       *
    848       * <p>The iterator is <i>fail-fast</i>: If the MinMaxPriorityQueue is modified
    849       * at any time after the iterator is created, in any way except through the
    850       * iterator's own remove method, the iterator will generally throw a
    851       * {@link ConcurrentModificationException}. Thus, in the face of concurrent
    852       * modification, the iterator fails quickly and cleanly, rather than risking
    853       * arbitrary, non-deterministic behavior at an undetermined time in the
    854       * future.
    855       *
    856       * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
    857       * as it is, generally speaking, impossible to make any hard guarantees in the
    858       * presence of unsynchronized concurrent modification.  Fail-fast iterators
    859       * throw {@code ConcurrentModificationException} on a best-effort basis.
    860       * Therefore, it would be wrong to write a program that depended on this
    861       * exception for its correctness: <i>the fail-fast behavior of iterators
    862       * should be used only to detect bugs.</i>
    863       *
    864       * @return an iterator over the elements contained in this collection
    865       */
    866      @Override public Iterator<E> iterator() {
    867        return new QueueIterator();
    868      }
    869
    870      @Override public void clear() {
    871        for (int i = 0; i < size; i++) {
    872          queue[i] = null;
    873        }
    874        size = 0;
    875      }
    876
    877      @Override public Object[] toArray() {
    878        Object[] copyTo = new Object[size];
    879        System.arraycopy(queue, 0, copyTo, 0, size);
    880        return copyTo;
    881      }
    882
    883      /**
    884       * Returns the comparator used to order the elements in this queue. Obeys the
    885       * general contract of {@link PriorityQueue#comparator}, but returns {@link
    886       * Ordering#natural} instead of {@code null} to indicate natural ordering.
    887       */
    888      public Comparator<? super E> comparator() {
    889        return minHeap.ordering;
    890      }
    891
    892      @VisibleForTesting int capacity() {
    893        return queue.length;
    894      }
    895
    896      // Size/capacity-related methods
    897
    898      private static final int DEFAULT_CAPACITY = 11;
    899
    900      @VisibleForTesting static int initialQueueSize(int configuredExpectedSize,
    901          int maximumSize, Iterable<?> initialContents) {
    902        // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY
    903        int result = (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE)
    904            ? DEFAULT_CAPACITY
    905            : configuredExpectedSize;
    906
    907        // Enlarge to contain initial contents
    908        if (initialContents instanceof Collection) {
    909          int initialSize = ((Collection<?>) initialContents).size();
    910          result = Math.max(result, initialSize);
    911        }
    912
    913        // Now cap it at maxSize + 1
    914        return capAtMaximumSize(result, maximumSize);
    915      }
    916
    917      private void growIfNeeded() {
    918        if (size > queue.length) {
    919          int newCapacity = calculateNewCapacity();
    920          Object[] newQueue = new Object[newCapacity];
    921          System.arraycopy(queue, 0, newQueue, 0, queue.length);
    922          queue = newQueue;
    923        }
    924      }
    925
    926      /** Returns ~2x the old capacity if small; ~1.5x otherwise. */
    927      private int calculateNewCapacity() {
    928        int oldCapacity = queue.length;
    929        int newCapacity = (oldCapacity < 64)
    930            ? (oldCapacity + 1) * 2
    931            : (oldCapacity / 2) * 3;
    932        if (newCapacity < 0) {
    933          newCapacity = Integer.MAX_VALUE; // overflow - hotspot will throw OOME
    934        }
    935        return capAtMaximumSize(newCapacity, maximumSize);
    936      }
    937
    938      /** There's no reason for the queueSize to ever be more than maxSize + 1 */
    939      private static int capAtMaximumSize(int queueSize, int maximumSize) {
    940        return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow
    941      }
    942    }