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 }