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