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