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