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    
017    package com.google.common.collect;
018    
019    import static com.google.common.base.Preconditions.checkArgument;
020    import static com.google.common.base.Preconditions.checkNotNull;
021    import static com.google.common.base.Preconditions.checkPositionIndex;
022    import static com.google.common.base.Preconditions.checkState;
023    
024    import com.google.common.annotations.Beta;
025    import com.google.common.annotations.VisibleForTesting;
026    import com.google.common.math.IntMath;
027    
028    import java.util.AbstractQueue;
029    import java.util.ArrayList;
030    import java.util.Collection;
031    import java.util.Collections;
032    import java.util.Comparator;
033    import java.util.ConcurrentModificationException;
034    import java.util.Iterator;
035    import java.util.LinkedList;
036    import java.util.List;
037    import java.util.NoSuchElementException;
038    import java.util.PriorityQueue;
039    import 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): @GwtCompatible
089    @Beta
090    public 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        // TODO(user): Switch to ArrayDeque once Guava supports it.
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          checkState(canRemove,
783              "no calls to remove() since the last call to next()");
784          checkModCount();
785          canRemove = false;
786          expectedModCount++;
787          if (cursor < size()) {
788            MoveDesc<E> moved = removeAt(cursor);
789            if (moved != null) {
790              if (forgetMeNot == null) {
791                forgetMeNot = new LinkedList<E>();
792                skipMe = new ArrayList<E>(3);
793              }
794              forgetMeNot.add(moved.toTrickle);
795              skipMe.add(moved.replaced);
796            }
797            cursor--;
798          } else { // we must have set lastFromForgetMeNot in next()
799            checkState(removeExact(lastFromForgetMeNot));
800            lastFromForgetMeNot = null;
801          }
802        }
803    
804        // Finds only this exact instance, not others that are equals()
805        private boolean containsExact(Iterable<E> elements, E target) {
806          for (E element : elements) {
807            if (element == target) {
808              return true;
809            }
810          }
811          return false;
812        }
813    
814        // Removes only this exact instance, not others that are equals()
815        boolean removeExact(Object target) {
816          for (int i = 0; i < size; i++) {
817            if (queue[i] == target) {
818              removeAt(i);
819              return true;
820            }
821          }
822          return false;
823        }
824    
825        void checkModCount() {
826          if (modCount != expectedModCount) {
827            throw new ConcurrentModificationException();
828          }
829        }
830    
831        /**
832         * Returns the index of the first element after {@code c} that is not in
833         * {@code skipMe} and returns {@code size()} if there is no such element.
834         */
835        private int nextNotInSkipMe(int c) {
836          if (skipMe != null) {
837            while (c < size() && containsExact(skipMe, elementData(c))) {
838              c++;
839            }
840          }
841          return c;
842        }
843      }
844    
845      /**
846       * Returns an iterator over the elements contained in this collection,
847       * <i>in no particular order</i>.
848       *
849       * <p>The iterator is <i>fail-fast</i>: If the MinMaxPriorityQueue is modified
850       * at any time after the iterator is created, in any way except through the
851       * iterator's own remove method, the iterator will generally throw a
852       * {@link ConcurrentModificationException}. Thus, in the face of concurrent
853       * modification, the iterator fails quickly and cleanly, rather than risking
854       * arbitrary, non-deterministic behavior at an undetermined time in the
855       * future.
856       *
857       * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
858       * as it is, generally speaking, impossible to make any hard guarantees in the
859       * presence of unsynchronized concurrent modification.  Fail-fast iterators
860       * throw {@code ConcurrentModificationException} on a best-effort basis.
861       * Therefore, it would be wrong to write a program that depended on this
862       * exception for its correctness: <i>the fail-fast behavior of iterators
863       * should be used only to detect bugs.</i>
864       *
865       * @return an iterator over the elements contained in this collection
866       */
867      @Override public Iterator<E> iterator() {
868        return new QueueIterator();
869      }
870    
871      @Override public void clear() {
872        for (int i = 0; i < size; i++) {
873          queue[i] = null;
874        }
875        size = 0;
876      }
877    
878      @Override public Object[] toArray() {
879        Object[] copyTo = new Object[size];
880        System.arraycopy(queue, 0, copyTo, 0, size);
881        return copyTo;
882      }
883    
884      /**
885       * Returns the comparator used to order the elements in this queue. Obeys the
886       * general contract of {@link PriorityQueue#comparator}, but returns {@link
887       * Ordering#natural} instead of {@code null} to indicate natural ordering.
888       */
889      public Comparator<? super E> comparator() {
890        return minHeap.ordering;
891      }
892    
893      @VisibleForTesting int capacity() {
894        return queue.length;
895      }
896    
897      // Size/capacity-related methods
898    
899      private static final int DEFAULT_CAPACITY = 11;
900    
901      @VisibleForTesting static int initialQueueSize(int configuredExpectedSize,
902          int maximumSize, Iterable<?> initialContents) {
903        // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY
904        int result = (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE)
905            ? DEFAULT_CAPACITY
906            : configuredExpectedSize;
907    
908        // Enlarge to contain initial contents
909        if (initialContents instanceof Collection) {
910          int initialSize = ((Collection<?>) initialContents).size();
911          result = Math.max(result, initialSize);
912        }
913    
914        // Now cap it at maxSize + 1
915        return capAtMaximumSize(result, maximumSize);
916      }
917    
918      private void growIfNeeded() {
919        if (size > queue.length) {
920          int newCapacity = calculateNewCapacity();
921          Object[] newQueue = new Object[newCapacity];
922          System.arraycopy(queue, 0, newQueue, 0, queue.length);
923          queue = newQueue;
924        }
925      }
926    
927      /** Returns ~2x the old capacity if small; ~1.5x otherwise. */
928      private int calculateNewCapacity() {
929        int oldCapacity = queue.length;
930        int newCapacity = (oldCapacity < 64)
931            ? (oldCapacity + 1) * 2
932            : IntMath.checkedMultiply(oldCapacity / 2, 3);
933        return capAtMaximumSize(newCapacity, maximumSize);
934      }
935    
936      /** There's no reason for the queueSize to ever be more than maxSize + 1 */
937      private static int capAtMaximumSize(int queueSize, int maximumSize) {
938        return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow
939      }
940    }