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