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