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