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