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