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