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