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