xref: /external/guava/guava/src/com/google/common/collect/MinMaxPriorityQueue.java

/*
 * Copyright (C) 2010 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkPositionIndex;
import static com.google.common.base.Preconditions.checkState;

import com.google.common.annotations.Beta;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.math.IntMath;

import java.util.AbstractQueue;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * A double-ended priority queue, which provides constant-time access to both
 * its least element and its greatest element, as determined by the queue's
 * specified comparator. If no comparator is given at construction time, the
 * natural order of elements is used.
 *
 * <p>As a {@link Queue} it functions exactly as a {@link PriorityQueue}: its
 * head element -- the implicit target of the methods {@link #peek()}, {@link
 * #poll()} and {@link #remove()} -- is defined as the <i>least</i> element in
 * the queue according to the queue's comparator. But unlike a regular priority
 * queue, the methods {@link #peekLast}, {@link #pollLast} and
 * {@link #removeLast} are also provided, to act on the <i>greatest</i> element
 * in the queue instead.
 *
 * <p>A min-max priority queue can be configured with a maximum size. If so,
 * each time the size of the queue exceeds that value, the queue automatically
 * removes its greatest element according to its comparator (which might be the
 * element that was just added). This is different from conventional bounded
 * queues, which either block or reject new elements when full.
 *
 * <p>This implementation is based on the
 * <a href="http://portal.acm.org/citation.cfm?id=6621">min-max heap</a>
 * developed by Atkinson, et al. Unlike many other double-ended priority queues,
 * it stores elements in a single array, as compact as the traditional heap data
 * structure used in {@link PriorityQueue}.
 *
 * <p>This class is not thread-safe, and does not accept null elements.
 *
 * <p><i>Performance notes:</i>
 *
 * <ul>
 * <li>The retrieval operations {@link #peek}, {@link #peekFirst}, {@link
 *     #peekLast}, {@link #element}, and {@link #size} are constant-time
 * <li>The enqueing and dequeing operations ({@link #offer}, {@link #add}, and
 *     all the forms of {@link #poll} and {@link #remove()}) run in {@code
 *     O(log n) time}
 * <li>The {@link #remove(Object)} and {@link #contains} operations require
 *     linear ({@code O(n)}) time
 * <li>If you only access one end of the queue, and don't use a maximum size,
 *     this class is functionally equivalent to {@link PriorityQueue}, but
 *     significantly slower.
 * </ul>
 *
 * @author Sverre Sundsdal
 * @author Torbjorn Gannholm
 * @since 8.0
 */
// TODO(kevinb): @GwtCompatible
@Beta
public final class MinMaxPriorityQueue<E> extends AbstractQueue<E> {

  /**
   * Creates a new min-max priority queue with default settings: natural order,
   * no maximum size, no initial contents, and an initial expected size of 11.
   */
  public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() {
    return new Builder<Comparable>(Ordering.natural()).create();
  }

  /**
   * Creates a new min-max priority queue using natural order, no maximum size,
   * and initially containing the given elements.
   */
  public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create(
      Iterable<? extends E> initialContents) {
    return new Builder<E>(Ordering.<E>natural()).create(initialContents);
  }

  /**
   * Creates and returns a new builder, configured to build {@code
   * MinMaxPriorityQueue} instances that use {@code comparator} to determine the
   * least and greatest elements.
   */
  public static <B> Builder<B> orderedBy(Comparator<B> comparator) {
    return new Builder<B>(comparator);
  }

  /**
   * Creates and returns a new builder, configured to build {@code
   * MinMaxPriorityQueue} instances sized appropriately to hold {@code
   * expectedSize} elements.
   */
  public static Builder<Comparable> expectedSize(int expectedSize) {
    return new Builder<Comparable>(Ordering.natural())
        .expectedSize(expectedSize);
  }

  /**
   * Creates and returns a new builder, configured to build {@code
   * MinMaxPriorityQueue} instances that are limited to {@code maximumSize}
   * elements. Each time a queue grows beyond this bound, it immediately
   * removes its greatest element (according to its comparator), which might be
   * the element that was just added.
   */
  public static Builder<Comparable> maximumSize(int maximumSize) {
    return new Builder<Comparable>(Ordering.natural())
        .maximumSize(maximumSize);
  }

  /**
   * The builder class used in creation of min-max priority queues. Instead of
   * constructing one directly, use {@link
   * MinMaxPriorityQueue#orderedBy(Comparator)}, {@link
   * MinMaxPriorityQueue#expectedSize(int)} or {@link
   * MinMaxPriorityQueue#maximumSize(int)}.
   *
   * @param <B> the upper bound on the eventual type that can be produced by
   *     this builder (for example, a {@code Builder<Number>} can produce a
   *     {@code Queue<Number>} or {@code Queue<Integer>} but not a {@code
   *     Queue<Object>}).
   * @since 8.0
   */
  @Beta
  public static final class Builder<B> {
    /*
     * TODO(kevinb): when the dust settles, see if we still need this or can
     * just default to DEFAULT_CAPACITY.
     */
    private static final int UNSET_EXPECTED_SIZE = -1;

    private final Comparator<B> comparator;
    private int expectedSize = UNSET_EXPECTED_SIZE;
    private int maximumSize = Integer.MAX_VALUE;

    private Builder(Comparator<B> comparator) {
      this.comparator = checkNotNull(comparator);
    }

    /**
     * Configures this builder to build min-max priority queues with an initial
     * expected size of {@code expectedSize}.
     */
    public Builder<B> expectedSize(int expectedSize) {
      checkArgument(expectedSize >= 0);
      this.expectedSize = expectedSize;
      return this;
    }

    /**
     * Configures this builder to build {@code MinMaxPriorityQueue} instances
     * that are limited to {@code maximumSize} elements. Each time a queue grows
     * beyond this bound, it immediately removes its greatest element (according
     * to its comparator), which might be the element that was just added.
     */
    public Builder<B> maximumSize(int maximumSize) {
      checkArgument(maximumSize > 0);
      this.maximumSize = maximumSize;
      return this;
    }

    /**
     * Builds a new min-max priority queue using the previously specified
     * options, and having no initial contents.
     */
    public <T extends B> MinMaxPriorityQueue<T> create() {
      return create(Collections.<T>emptySet());
    }

    /**
     * Builds a new min-max priority queue using the previously specified
     * options, and having the given initial elements.
     */
    public <T extends B> MinMaxPriorityQueue<T> create(
        Iterable<? extends T> initialContents) {
      MinMaxPriorityQueue<T> queue = new MinMaxPriorityQueue<T>(
          this, initialQueueSize(expectedSize, maximumSize, initialContents));
      for (T element : initialContents) {
        queue.offer(element);
      }
      return queue;
    }

    @SuppressWarnings("unchecked") // safe "contravariant cast"
    private <T extends B> Ordering<T> ordering() {
      return Ordering.from((Comparator<T>) comparator);
    }
  }

  private final Heap minHeap;
  private final Heap maxHeap;
  @VisibleForTesting final int maximumSize;
  private Object[] queue;
  private int size;
  private int modCount;

  private MinMaxPriorityQueue(Builder<? super E> builder, int queueSize) {
    Ordering<E> ordering = builder.ordering();
    this.minHeap = new Heap(ordering);
    this.maxHeap = new Heap(ordering.reverse());
    minHeap.otherHeap = maxHeap;
    maxHeap.otherHeap = minHeap;

    this.maximumSize = builder.maximumSize;
    // TODO(kevinb): pad?
    this.queue = new Object[queueSize];
  }

  @Override public int size() {
    return size;
  }

  /**
   * Adds the given element to this queue. If this queue has a maximum size,
   * after adding {@code element} the queue will automatically evict its
   * greatest element (according to its comparator), which may be {@code
   * element} itself.
   *
   * @return {@code true} always
   */
  @Override public boolean add(E element) {
    offer(element);
    return true;
  }

  @Override public boolean addAll(Collection<? extends E> newElements) {
    boolean modified = false;
    for (E element : newElements) {
      offer(element);
      modified = true;
    }
    return modified;
  }

  /**
   * Adds the given element to this queue. If this queue has a maximum size,
   * after adding {@code element} the queue will automatically evict its
   * greatest element (according to its comparator), which may be {@code
   * element} itself.
   */
  @Override public boolean offer(E element) {
    checkNotNull(element);
    modCount++;
    int insertIndex = size++;

    growIfNeeded();

    // Adds the element to the end of the heap and bubbles it up to the correct
    // position.
    heapForIndex(insertIndex).bubbleUp(insertIndex, element);
    return size <= maximumSize || pollLast() != element;
  }

  @Override public E poll() {
    return isEmpty() ? null : removeAndGet(0);
  }

  @SuppressWarnings("unchecked") // we must carefully only allow Es to get in
  E elementData(int index) {
    return (E) queue[index];
  }

  @Override public E peek() {
    return isEmpty() ? null : elementData(0);
  }

  /**
   * Returns the index of the max element.
   */
  private int getMaxElementIndex() {
    switch (size) {
      case 1:
        return 0; // The lone element in the queue is the maximum.
      case 2:
        return 1; // The lone element in the maxHeap is the maximum.
      default:
        // The max element must sit on the first level of the maxHeap. It is
        // actually the *lesser* of the two from the maxHeap's perspective.
        return (maxHeap.compareElements(1, 2) <= 0) ? 1 : 2;
    }
  }

  /**
   * Removes and returns the least element of this queue, or returns {@code
   * null} if the queue is empty.
   */
  public E pollFirst() {
    return poll();
  }

  /**
   * Removes and returns the least element of this queue.
   *
   * @throws NoSuchElementException if the queue is empty
   */
  public E removeFirst() {
    return remove();
  }

  /**
   * Retrieves, but does not remove, the least element of this queue, or returns
   * {@code null} if the queue is empty.
   */
  public E peekFirst() {
    return peek();
  }

  /**
   * Removes and returns the greatest element of this queue, or returns {@code
   * null} if the queue is empty.
   */
  public E pollLast() {
    return isEmpty() ? null : removeAndGet(getMaxElementIndex());
  }

  /**
   * Removes and returns the greatest element of this queue.
   *
   * @throws NoSuchElementException if the queue is empty
   */
  public E removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return removeAndGet(getMaxElementIndex());
  }

  /**
   * Retrieves, but does not remove, the greatest element of this queue, or
   * returns {@code null} if the queue is empty.
   */
  public E peekLast() {
    return isEmpty() ? null : elementData(getMaxElementIndex());
  }

  /**
   * Removes the element at position {@code index}.
   *
   * <p>Normally this method leaves the elements at up to {@code index - 1},
   * inclusive, untouched.  Under these circumstances, it returns {@code null}.
   *
   * <p>Occasionally, in order to maintain the heap invariant, it must swap a
   * later element of the list with one before {@code index}. Under these
   * circumstances it returns a pair of elements as a {@link MoveDesc}. The
   * first one is the element that was previously at the end of the heap and is
   * now at some position before {@code index}. The second element is the one
   * that was swapped down to replace the element at {@code index}. This fact is
   * used by iterator.remove so as to visit elements during a traversal once and
   * only once.
   */
  @VisibleForTesting MoveDesc<E> removeAt(int index) {
    checkPositionIndex(index, size);
    modCount++;
    size--;
    if (size == index) {
      queue[size] = null;
      return null;
    }
    E actualLastElement = elementData(size);
    int lastElementAt = heapForIndex(size)
        .getCorrectLastElement(actualLastElement);
    E toTrickle = elementData(size);
    queue[size] = null;
    MoveDesc<E> changes = fillHole(index, toTrickle);
    if (lastElementAt < index) {
      // Last element is moved to before index, swapped with trickled element.
      if (changes == null) {
        // The trickled element is still after index.
        return new MoveDesc<E>(actualLastElement, toTrickle);
      } else {
        // The trickled element is back before index, but the replaced element
        // has now been moved after index.
        return new MoveDesc<E>(actualLastElement, changes.replaced);
      }
    }
    // Trickled element was after index to begin with, no adjustment needed.
    return changes;
  }

  private MoveDesc<E> fillHole(int index, E toTrickle) {
    Heap heap = heapForIndex(index);
    // We consider elementData(index) a "hole", and we want to fill it
    // with the last element of the heap, toTrickle.
    // Since the last element of the heap is from the bottom level, we
    // optimistically fill index position with elements from lower levels,
    // moving the hole down. In most cases this reduces the number of
    // comparisons with toTrickle, but in some cases we will need to bubble it
    // all the way up again.
    int vacated = heap.fillHoleAt(index);
    // Try to see if toTrickle can be bubbled up min levels.
    int bubbledTo = heap.bubbleUpAlternatingLevels(vacated, toTrickle);
    if (bubbledTo == vacated) {
      // Could not bubble toTrickle up min levels, try moving
      // it from min level to max level (or max to min level) and bubble up
      // there.
      return heap.tryCrossOverAndBubbleUp(index, vacated, toTrickle);
    } else {
      return (bubbledTo < index)
          ? new MoveDesc<E>(toTrickle, elementData(index))
          : null;
    }
  }

  // Returned from removeAt() to iterator.remove()
  static class MoveDesc<E> {
    final E toTrickle;
    final E replaced;

    MoveDesc(E toTrickle, E replaced) {
      this.toTrickle = toTrickle;
      this.replaced = replaced;
    }
  }

  /**
   * Removes and returns the value at {@code index}.
   */
  private E removeAndGet(int index) {
    E value = elementData(index);
    removeAt(index);
    return value;
  }

  private Heap heapForIndex(int i) {
    return isEvenLevel(i) ? minHeap : maxHeap;
  }

  private static final int EVEN_POWERS_OF_TWO = 0x55555555;
  private static final int ODD_POWERS_OF_TWO = 0xaaaaaaaa;

  @VisibleForTesting static boolean isEvenLevel(int index) {
    int oneBased = index + 1;
    checkState(oneBased > 0, "negative index");
    return (oneBased & EVEN_POWERS_OF_TWO) > (oneBased & ODD_POWERS_OF_TWO);
  }

  /**
   * Returns {@code true} if the MinMax heap structure holds. This is only used
   * in testing.
   *
   * TODO(kevinb): move to the test class?
   */
  @VisibleForTesting boolean isIntact() {
    for (int i = 1; i < size; i++) {
      if (!heapForIndex(i).verifyIndex(i)) {
        return false;
      }
    }
    return true;
  }

  /**
   * Each instance of MinMaxPriortyQueue encapsulates two instances of Heap:
   * a min-heap and a max-heap. Conceptually, these might each have their own
   * array for storage, but for efficiency's sake they are stored interleaved on
   * alternate heap levels in the same array (MMPQ.queue).
   */
  private class Heap {
    final Ordering<E> ordering;
    Heap otherHeap;

    Heap(Ordering<E> ordering) {
      this.ordering = ordering;
    }

    int compareElements(int a, int b) {
      return ordering.compare(elementData(a), elementData(b));
    }

    /**
     * Tries to move {@code toTrickle} from a min to a max level and
     * bubble up there. If it moved before {@code removeIndex} this method
     * returns a pair as described in {@link #removeAt}.
     */
    MoveDesc<E> tryCrossOverAndBubbleUp(
        int removeIndex, int vacated, E toTrickle) {
      int crossOver = crossOver(vacated, toTrickle);
      if (crossOver == vacated) {
        return null;
      }
      // Successfully crossed over from min to max.
      // Bubble up max levels.
      E parent;
      // If toTrickle is moved up to a parent of removeIndex, the parent is
      // placed in removeIndex position. We must return that to the iterator so
      // that it knows to skip it.
      if (crossOver < removeIndex) {
        // We crossed over to the parent level in crossOver, so the parent
        // has already been moved.
        parent = elementData(removeIndex);
      } else {
        parent = elementData(getParentIndex(removeIndex));
      }
      // bubble it up the opposite heap
      if (otherHeap.bubbleUpAlternatingLevels(crossOver, toTrickle)
          < removeIndex) {
        return new MoveDesc<E>(toTrickle, parent);
      } else {
        return null;
      }
    }

    /**
     * Bubbles a value from {@code index} up the appropriate heap if required.
     */
    void bubbleUp(int index, E x) {
      int crossOver = crossOverUp(index, x);

      Heap heap;
      if (crossOver == index) {
        heap = this;
      } else {
        index = crossOver;
        heap = otherHeap;
      }
      heap.bubbleUpAlternatingLevels(index, x);
    }

    /**
     * Bubbles a value from {@code index} up the levels of this heap, and
     * returns the index the element ended up at.
     */
    int bubbleUpAlternatingLevels(int index, E x) {
      while (index > 2) {
        int grandParentIndex = getGrandparentIndex(index);
        E e = elementData(grandParentIndex);
        if (ordering.compare(e, x) <= 0) {
          break;
        }
        queue[index] = e;
        index = grandParentIndex;
      }
      queue[index] = x;
      return index;
    }

    /**
     * Returns the index of minimum value between {@code index} and
     * {@code index + len}, or {@code -1} if {@code index} is greater than
     * {@code size}.
     */
    int findMin(int index, int len) {
      if (index >= size) {
        return -1;
      }
      checkState(index > 0);
      int limit = Math.min(index, size - len) + len;
      int minIndex = index;
      for (int i = index + 1; i < limit; i++) {
        if (compareElements(i, minIndex) < 0) {
          minIndex = i;
        }
      }
      return minIndex;
    }

    /**
     * Returns the minimum child or {@code -1} if no child exists.
     */
    int findMinChild(int index) {
      return findMin(getLeftChildIndex(index), 2);
    }

    /**
     * Returns the minimum grand child or -1 if no grand child exists.
     */
    int findMinGrandChild(int index) {
      int leftChildIndex = getLeftChildIndex(index);
      if (leftChildIndex < 0) {
        return -1;
      }
      return findMin(getLeftChildIndex(leftChildIndex), 4);
    }

    /**
     * Moves an element one level up from a min level to a max level
     * (or vice versa).
     * Returns the new position of the element.
     */
    int crossOverUp(int index, E x) {
      if (index == 0) {
        queue[0] = x;
        return 0;
      }
      int parentIndex = getParentIndex(index);
      E parentElement = elementData(parentIndex);
      if (parentIndex != 0) {
        // This is a guard for the case of the childless uncle.
        // Since the end of the array is actually the middle of the heap,
        // a smaller childless uncle can become a child of x when we
        // bubble up alternate levels, violating the invariant.
        int grandparentIndex = getParentIndex(parentIndex);
        int uncleIndex = getRightChildIndex(grandparentIndex);
        if (uncleIndex != parentIndex
            && getLeftChildIndex(uncleIndex) >= size) {
          E uncleElement = elementData(uncleIndex);
          if (ordering.compare(uncleElement, parentElement) < 0) {
            parentIndex = uncleIndex;
            parentElement = uncleElement;
          }
        }
      }
      if (ordering.compare(parentElement, x) < 0) {
        queue[index] = parentElement;
        queue[parentIndex] = x;
        return parentIndex;
      }
      queue[index] = x;
      return index;
    }

    /**
     * Returns the conceptually correct last element of the heap.
     *
     * <p>Since the last element of the array is actually in the
     * middle of the sorted structure, a childless uncle node could be
     * smaller, which would corrupt the invariant if this element
     * becomes the new parent of the uncle. In that case, we first
     * switch the last element with its uncle, before returning.
     */
    int getCorrectLastElement(E actualLastElement) {
      int parentIndex = getParentIndex(size);
      if (parentIndex != 0) {
        int grandparentIndex = getParentIndex(parentIndex);
        int uncleIndex = getRightChildIndex(grandparentIndex);
        if (uncleIndex != parentIndex
            && getLeftChildIndex(uncleIndex) >= size) {
          E uncleElement = elementData(uncleIndex);
          if (ordering.compare(uncleElement, actualLastElement) < 0) {
            queue[uncleIndex] = actualLastElement;
            queue[size] = uncleElement;
            return uncleIndex;
          }
        }
      }
      return size;
    }

    /**
     * Crosses an element over to the opposite heap by moving it one level down
     * (or up if there are no elements below it).
     *
     * Returns the new position of the element.
     */
    int crossOver(int index, E x) {
      int minChildIndex = findMinChild(index);
      // TODO(kevinb): split the && into two if's and move crossOverUp so it's
      // only called when there's no child.
      if ((minChildIndex > 0)
          && (ordering.compare(elementData(minChildIndex), x) < 0)) {
        queue[index] = elementData(minChildIndex);
        queue[minChildIndex] = x;
        return minChildIndex;
      }
      return crossOverUp(index, x);
    }

    /**
     * Fills the hole at {@code index} by moving in the least of its
     * grandchildren to this position, then recursively filling the new hole
     * created.
     *
     * @return the position of the new hole (where the lowest grandchild moved
     *     from, that had no grandchild to replace it)
     */
    int fillHoleAt(int index) {
      int minGrandchildIndex;
      while ((minGrandchildIndex = findMinGrandChild(index)) > 0) {
        queue[index] = elementData(minGrandchildIndex);
        index = minGrandchildIndex;
      }
      return index;
    }

    private boolean verifyIndex(int i) {
      if ((getLeftChildIndex(i) < size)
          && (compareElements(i, getLeftChildIndex(i)) > 0)) {
        return false;
      }
      if ((getRightChildIndex(i) < size)
          && (compareElements(i, getRightChildIndex(i)) > 0)) {
        return false;
      }
      if ((i > 0) && (compareElements(i, getParentIndex(i)) > 0)) {
        return false;
      }
      if ((i > 2) && (compareElements(getGrandparentIndex(i), i) > 0)) {
        return false;
      }
      return true;
    }

    // These would be static if inner classes could have static members.

    private int getLeftChildIndex(int i) {
      return i * 2 + 1;
    }

    private int getRightChildIndex(int i) {
      return i * 2 + 2;
    }

    private int getParentIndex(int i) {
      return (i - 1) / 2;
    }

    private int getGrandparentIndex(int i) {
      return getParentIndex(getParentIndex(i)); // (i - 3) / 4
    }
  }

  /**
   * Iterates the elements of the queue in no particular order.
   *
   * If the underlying queue is modified during iteration an exception will be
   * thrown.
   */
  private class QueueIterator implements Iterator<E> {
    private int cursor = -1;
    private int expectedModCount = modCount;
    // TODO(user): Switch to ArrayDeque once Guava supports it.
    private Queue<E> forgetMeNot;
    private List<E> skipMe;
    private E lastFromForgetMeNot;
    private boolean canRemove;

    @Override public boolean hasNext() {
      checkModCount();
      return (nextNotInSkipMe(cursor + 1) < size())
          || ((forgetMeNot != null) && !forgetMeNot.isEmpty());
    }

    @Override public E next() {
      checkModCount();
      int tempCursor = nextNotInSkipMe(cursor + 1);
      if (tempCursor < size()) {
        cursor = tempCursor;
        canRemove = true;
        return elementData(cursor);
      } else if (forgetMeNot != null) {
        cursor = size();
        lastFromForgetMeNot = forgetMeNot.poll();
        if (lastFromForgetMeNot != null) {
          canRemove = true;
          return lastFromForgetMeNot;
        }
      }
      throw new NoSuchElementException(
          "iterator moved past last element in queue.");
    }

    @Override public void remove() {
      checkState(canRemove,
          "no calls to remove() since the last call to next()");
      checkModCount();
      canRemove = false;
      expectedModCount++;
      if (cursor < size()) {
        MoveDesc<E> moved = removeAt(cursor);
        if (moved != null) {
          if (forgetMeNot == null) {
            forgetMeNot = new LinkedList<E>();
            skipMe = new ArrayList<E>(3);
          }
          forgetMeNot.add(moved.toTrickle);
          skipMe.add(moved.replaced);
        }
        cursor--;
      } else { // we must have set lastFromForgetMeNot in next()
        checkState(removeExact(lastFromForgetMeNot));
        lastFromForgetMeNot = null;
      }
    }

    // Finds only this exact instance, not others that are equals()
    private boolean containsExact(Iterable<E> elements, E target) {
      for (E element : elements) {
        if (element == target) {
          return true;
        }
      }
      return false;
    }

    // Removes only this exact instance, not others that are equals()
    boolean removeExact(Object target) {
      for (int i = 0; i < size; i++) {
        if (queue[i] == target) {
          removeAt(i);
          return true;
        }
      }
      return false;
    }

    void checkModCount() {
      if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
      }
    }

    /**
     * Returns the index of the first element after {@code c} that is not in
     * {@code skipMe} and returns {@code size()} if there is no such element.
     */
    private int nextNotInSkipMe(int c) {
      if (skipMe != null) {
        while (c < size() && containsExact(skipMe, elementData(c))) {
          c++;
        }
      }
      return c;
    }
  }

  /**
   * Returns an iterator over the elements contained in this collection,
   * <i>in no particular order</i>.
   *
   * <p>The iterator is <i>fail-fast</i>: If the MinMaxPriorityQueue is modified
   * at any time after the iterator is created, in any way except through the
   * iterator's own remove method, the iterator will generally throw a
   * {@link ConcurrentModificationException}. Thus, in the face of concurrent
   * modification, the iterator fails quickly and cleanly, rather than risking
   * arbitrary, non-deterministic behavior at an undetermined time in the
   * future.
   *
   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
   * as it is, generally speaking, impossible to make any hard guarantees in the
   * presence of unsynchronized concurrent modification.  Fail-fast iterators
   * throw {@code ConcurrentModificationException} on a best-effort basis.
   * Therefore, it would be wrong to write a program that depended on this
   * exception for its correctness: <i>the fail-fast behavior of iterators
   * should be used only to detect bugs.</i>
   *
   * @return an iterator over the elements contained in this collection
   */
  @Override public Iterator<E> iterator() {
    return new QueueIterator();
  }

  @Override public void clear() {
    for (int i = 0; i < size; i++) {
      queue[i] = null;
    }
    size = 0;
  }

  @Override public Object[] toArray() {
    Object[] copyTo = new Object[size];
    System.arraycopy(queue, 0, copyTo, 0, size);
    return copyTo;
  }

  /**
   * Returns the comparator used to order the elements in this queue. Obeys the
   * general contract of {@link PriorityQueue#comparator}, but returns {@link
   * Ordering#natural} instead of {@code null} to indicate natural ordering.
   */
  public Comparator<? super E> comparator() {
    return minHeap.ordering;
  }

  @VisibleForTesting int capacity() {
    return queue.length;
  }

  // Size/capacity-related methods

  private static final int DEFAULT_CAPACITY = 11;

  @VisibleForTesting static int initialQueueSize(int configuredExpectedSize,
      int maximumSize, Iterable<?> initialContents) {
    // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY
    int result = (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE)
        ? DEFAULT_CAPACITY
        : configuredExpectedSize;

    // Enlarge to contain initial contents
    if (initialContents instanceof Collection) {
      int initialSize = ((Collection<?>) initialContents).size();
      result = Math.max(result, initialSize);
    }

    // Now cap it at maxSize + 1
    return capAtMaximumSize(result, maximumSize);
  }

  private void growIfNeeded() {
    if (size > queue.length) {
      int newCapacity = calculateNewCapacity();
      Object[] newQueue = new Object[newCapacity];
      System.arraycopy(queue, 0, newQueue, 0, queue.length);
      queue = newQueue;
    }
  }

  /** Returns ~2x the old capacity if small; ~1.5x otherwise. */
  private int calculateNewCapacity() {
    int oldCapacity = queue.length;
    int newCapacity = (oldCapacity < 64)
        ? (oldCapacity + 1) * 2
        : IntMath.checkedMultiply(oldCapacity / 2, 3);
    return capAtMaximumSize(newCapacity, maximumSize);
  }

  /** There's no reason for the queueSize to ever be more than maxSize + 1 */
  private static int capAtMaximumSize(int queueSize, int maximumSize) {
    return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow
  }
}