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