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