001 /*
002 * Copyright (C) 2010 Google Inc.
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) 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 toTrickle = elementData(size);
385 queue[size] = null;
386 Heap heap = heapForIndex(index);
387 // We consider elementData(index) a "hole", and we want to fill it
388 // with the last element of the heap, toTrickle.
389 // Since the last element of the heap is from the bottom level, we
390 // optimistically fill index position with elements from lower levels,
391 // moving the hole down. In most cases this reduces the number of
392 // comparisons with toTrickle, but in some cases we will need to bubble it
393 // all the way up again.
394 int vacated = heap.fillHoleAt(index);
395 // Try to see if toTrickle can be bubbled up min levels.
396 int bubbledTo = heap.bubbleUpAlternatingLevels(vacated, toTrickle);
397 if (bubbledTo == vacated) {
398 // Could not bubble toTrickle up min levels, try moving
399 // it from min level to max level (or max to min level) and bubble up
400 // there.
401 return heap.tryCrossOverAndBubbleUp(index, vacated, toTrickle);
402 } else {
403 return (bubbledTo < index)
404 ? new MoveDesc<E>(toTrickle, elementData(index))
405 : null;
406 }
407 }
408
409 // Returned from removeAt() to iterator.remove()
410 static class MoveDesc<E> {
411 final E toTrickle;
412 final E replaced;
413
414 MoveDesc(E toTrickle, E replaced) {
415 this.toTrickle = toTrickle;
416 this.replaced = replaced;
417 }
418 }
419
420 /**
421 * Removes and returns the value at {@code index}.
422 */
423 private E removeAndGet(int index) {
424 E value = elementData(index);
425 removeAt(index);
426 return value;
427 }
428
429 private Heap heapForIndex(int i) {
430 return isEvenLevel(i) ? minHeap : maxHeap;
431 }
432
433 private static final int EVEN_POWERS_OF_TWO = 0x55555555;
434 private static final int ODD_POWERS_OF_TWO = 0xaaaaaaaa;
435
436 @VisibleForTesting static boolean isEvenLevel(int index) {
437 int oneBased = index + 1;
438 checkState(oneBased > 0, "negative index");
439 return (oneBased & EVEN_POWERS_OF_TWO) > (oneBased & ODD_POWERS_OF_TWO);
440 }
441
442 /**
443 * Returns {@code true} if the MinMax heap structure holds. This is only used
444 * in testing.
445 *
446 * TODO(kevinb): move to the test class?
447 */
448 @VisibleForTesting boolean isIntact() {
449 for (int i = 1; i < size; i++) {
450 if (!heapForIndex(i).verifyIndex(i)) {
451 return false;
452 }
453 }
454 return true;
455 }
456
457 /**
458 * Each instance of MinMaxPriortyQueue encapsulates two instances of Heap:
459 * a min-heap and a max-heap. Conceptually, these might each have their own
460 * array for storage, but for efficiency's sake they are stored interleaved on
461 * alternate heap levels in the same array (MMPQ.queue).
462 */
463 private class Heap {
464 final Ordering<E> ordering;
465 Heap otherHeap;
466
467 Heap(Ordering<E> ordering) {
468 this.ordering = ordering;
469 }
470
471 int compareElements(int a, int b) {
472 return ordering.compare(elementData(a), elementData(b));
473 }
474
475 /**
476 * Tries to move {@code toTrickle} from a min to a max level and
477 * bubble up there. If it moved before {@code removeIndex} this method
478 * returns a pair as described in {@link #removeAt}.
479 */
480 MoveDesc<E> tryCrossOverAndBubbleUp(
481 int removeIndex, int vacated, E toTrickle) {
482 int crossOver = crossOver(vacated, toTrickle);
483 if (crossOver == vacated) {
484 return null;
485 }
486 // Successfully crossed over from min to max.
487 // Bubble up max levels.
488 E parent;
489 // If toTrickle is moved up to a parent of removeIndex, the parent is
490 // placed in removeIndex position. We must return that to the iterator so
491 // that it knows to skip it.
492 if (crossOver < removeIndex) {
493 // We crossed over to the parent level in crossOver, so the parent
494 // has already been moved.
495 parent = elementData(removeIndex);
496 } else {
497 parent = elementData(getParentIndex(removeIndex));
498 }
499 // bubble it up the opposite heap
500 if (otherHeap.bubbleUpAlternatingLevels(crossOver, toTrickle)
501 < removeIndex) {
502 return new MoveDesc<E>(toTrickle, parent);
503 } else {
504 return null;
505 }
506 }
507
508 /**
509 * Bubbles a value from {@code index} up the appropriate heap if required.
510 */
511 void bubbleUp(int index, E x) {
512 int crossOver = crossOverUp(index, x);
513
514 Heap heap;
515 if (crossOver == index) {
516 heap = this;
517 } else {
518 index = crossOver;
519 heap = otherHeap;
520 }
521 heap.bubbleUpAlternatingLevels(index, x);
522 }
523
524 /**
525 * Bubbles a value from {@code index} up the levels of this heap, and
526 * returns the index the element ended up at.
527 */
528 int bubbleUpAlternatingLevels(int index, E x) {
529 while (index > 2) {
530 int grandParentIndex = getGrandparentIndex(index);
531 E e = elementData(grandParentIndex);
532 if (ordering.compare(e, x) <= 0) {
533 break;
534 }
535 queue[index] = e;
536 index = grandParentIndex;
537 }
538 queue[index] = x;
539 return index;
540 }
541
542 /**
543 * Returns the index of minimum value between {@code index} and
544 * {@code index + len}, or {@code -1} if {@code index} is greater than
545 * {@code size}.
546 */
547 int findMin(int index, int len) {
548 if (index >= size) {
549 return -1;
550 }
551 checkState(index > 0);
552 int limit = Math.min(index, size - len) + len;
553 int minIndex = index;
554 for (int i = index + 1; i < limit; i++) {
555 if (compareElements(i, minIndex) < 0) {
556 minIndex = i;
557 }
558 }
559 return minIndex;
560 }
561
562 /**
563 * Returns the minimum child or {@code -1} if no child exists.
564 */
565 int findMinChild(int index) {
566 return findMin(getLeftChildIndex(index), 2);
567 }
568
569 /**
570 * Returns the minimum grand child or -1 if no grand child exists.
571 */
572 int findMinGrandChild(int index) {
573 int leftChildIndex = getLeftChildIndex(index);
574 if (leftChildIndex < 0) {
575 return -1;
576 }
577 return findMin(getLeftChildIndex(leftChildIndex), 4);
578 }
579
580 /**
581 * Moves an element one level up from a min level to a max level
582 * (or vice versa).
583 * Returns the new position of the element.
584 */
585 int crossOverUp(int index, E x) {
586 if (index == 0) {
587 queue[0] = x;
588 return 0;
589 }
590 int parentIndex = getParentIndex(index);
591 E parentElement = elementData(parentIndex);
592 if (ordering.compare(parentElement, x) < 0) {
593 queue[index] = parentElement;
594 queue[parentIndex] = x;
595 return parentIndex;
596 }
597 queue[index] = x;
598 return index;
599 }
600
601 /**
602 * Crosses an element over to the opposite heap by moving it one level down
603 * (or up if there are no elements below it).
604 *
605 * Returns the new position of the element.
606 */
607 int crossOver(int index, E x) {
608 int minChildIndex = findMinChild(index);
609 // TODO(kevinb): split the && into two if's and move crossOverUp so it's
610 // only called when there's no child.
611 if ((minChildIndex > 0)
612 && (ordering.compare(elementData(minChildIndex), x) < 0)) {
613 queue[index] = elementData(minChildIndex);
614 queue[minChildIndex] = x;
615 return minChildIndex;
616 }
617 return crossOverUp(index, x);
618 }
619
620 /**
621 * Fills the hole at {@code index} by moving in the least of its
622 * grandchildren to this position, then recursively filling the new hole
623 * created.
624 *
625 * @return the position of the new hole (where the lowest grandchild moved
626 * from, that had no grandchild to replace it)
627 */
628 int fillHoleAt(int index) {
629 int minGrandchildIndex;
630 while ((minGrandchildIndex = findMinGrandChild(index)) > 0) {
631 queue[index] = elementData(minGrandchildIndex);
632 index = minGrandchildIndex;
633 }
634 return index;
635 }
636
637 private boolean verifyIndex(int i) {
638 if ((getLeftChildIndex(i) < size)
639 && (compareElements(i, getLeftChildIndex(i)) > 0)) {
640 return false;
641 }
642 if ((getRightChildIndex(i) < size)
643 && (compareElements(i, getRightChildIndex(i)) > 0)) {
644 return false;
645 }
646 if ((i > 0) && (compareElements(i, getParentIndex(i)) > 0)) {
647 return false;
648 }
649 if ((i > 2) && (compareElements(getGrandparentIndex(i), i) > 0)) {
650 return false;
651 }
652 return true;
653 }
654
655 // These would be static if inner classes could have static members.
656
657 private int getLeftChildIndex(int i) {
658 return i * 2 + 1;
659 }
660
661 private int getRightChildIndex(int i) {
662 return i * 2 + 2;
663 }
664
665 private int getParentIndex(int i) {
666 return (i - 1) / 2;
667 }
668
669 private int getGrandparentIndex(int i) {
670 return getParentIndex(getParentIndex(i)); // (i - 3) / 4
671 }
672 }
673
674 /**
675 * Iterates the elements of the queue in no particular order.
676 *
677 * If the underlying queue is modified during iteration an exception will be
678 * thrown.
679 */
680 private class QueueIterator implements Iterator<E> {
681 private int cursor = -1;
682 private int expectedModCount = modCount;
683 // TODO(user): Switch to ArrayDeque once Guava supports it.
684 private Queue<E> forgetMeNot;
685 private List<E> skipMe;
686 private E lastFromForgetMeNot;
687 private boolean canRemove;
688
689 @Override public boolean hasNext() {
690 checkModCount();
691 return (nextNotInSkipMe(cursor + 1) < size())
692 || ((forgetMeNot != null) && !forgetMeNot.isEmpty());
693 }
694
695 @Override public E next() {
696 checkModCount();
697 int tempCursor = nextNotInSkipMe(cursor + 1);
698 if (tempCursor < size()) {
699 cursor = tempCursor;
700 canRemove = true;
701 return elementData(cursor);
702 } else if (forgetMeNot != null) {
703 cursor = size();
704 lastFromForgetMeNot = forgetMeNot.poll();
705 if (lastFromForgetMeNot != null) {
706 canRemove = true;
707 return lastFromForgetMeNot;
708 }
709 }
710 throw new NoSuchElementException(
711 "iterator moved past last element in queue.");
712 }
713
714 @Override public void remove() {
715 checkState(canRemove,
716 "no calls to remove() since the last call to next()");
717 checkModCount();
718 canRemove = false;
719 expectedModCount++;
720 if (cursor < size()) {
721 MoveDesc<E> moved = removeAt(cursor);
722 if (moved != null) {
723 if (forgetMeNot == null) {
724 forgetMeNot = new LinkedList<E>();
725 skipMe = new ArrayList<E>(3);
726 }
727 forgetMeNot.add(moved.toTrickle);
728 skipMe.add(moved.replaced);
729 }
730 cursor--;
731 } else { // we must have set lastFromForgetMeNot in next()
732 checkState(removeExact(lastFromForgetMeNot));
733 lastFromForgetMeNot = null;
734 }
735 }
736
737 // Finds only this exact instance, not others that are equals()
738 private boolean containsExact(Iterable<E> elements, E target) {
739 for (E element : elements) {
740 if (element == target) {
741 return true;
742 }
743 }
744 return false;
745 }
746
747 // Removes only this exact instance, not others that are equals()
748 boolean removeExact(Object target) {
749 for (int i = 0; i < size; i++) {
750 if (queue[i] == target) {
751 removeAt(i);
752 return true;
753 }
754 }
755 return false;
756 }
757
758 void checkModCount() {
759 if (modCount != expectedModCount) {
760 throw new ConcurrentModificationException();
761 }
762 }
763
764 /**
765 * Returns the index of the first element after {@code c} that is not in
766 * {@code skipMe} and returns {@code size()} if there is no such element.
767 */
768 private int nextNotInSkipMe(int c) {
769 if (skipMe != null) {
770 while (c < size() && containsExact(skipMe, elementData(c))) {
771 c++;
772 }
773 }
774 return c;
775 }
776 }
777
778 /**
779 * Returns an iterator over the elements contained in this collection,
780 * <i>in no particular order</i>.
781 *
782 * <p>The iterator is <i>fail-fast</i>: If the MinMaxPriorityQueue is modified
783 * at any time after the iterator is created, in any way except through the
784 * iterator's own remove method, the iterator will generally throw a
785 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
786 * modification, the iterator fails quickly and cleanly, rather than risking
787 * arbitrary, non-deterministic behavior at an undetermined time in the
788 * future.
789 *
790 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
791 * as it is, generally speaking, impossible to make any hard guarantees in the
792 * presence of unsynchronized concurrent modification. Fail-fast iterators
793 * throw {@code ConcurrentModificationException} on a best-effort basis.
794 * Therefore, it would be wrong to write a program that depended on this
795 * exception for its correctness: <i>the fail-fast behavior of iterators
796 * should be used only to detect bugs.</i>
797 *
798 * @return an iterator over the elements contained in this collection
799 */
800 @Override public Iterator<E> iterator() {
801 return new QueueIterator();
802 }
803
804 @Override public void clear() {
805 for (int i = 0; i < size; i++) {
806 queue[i] = null;
807 }
808 size = 0;
809 }
810
811 @Override public Object[] toArray() {
812 Object[] copyTo = new Object[size];
813 System.arraycopy(queue, 0, copyTo, 0, size);
814 return copyTo;
815 }
816
817 /**
818 * Returns the comparator used to order the elements in this queue. Obeys the
819 * general contract of {@link PriorityQueue#comparator}, but returns {@link
820 * Ordering#natural} instead of {@code null} to indicate natural ordering.
821 */
822 public Comparator<? super E> comparator() {
823 return minHeap.ordering;
824 }
825
826 @VisibleForTesting int capacity() {
827 return queue.length;
828 }
829
830 // Size/capacity-related methods
831
832 private static final int DEFAULT_CAPACITY = 11;
833
834 @VisibleForTesting static int initialQueueSize(int configuredExpectedSize,
835 int maximumSize, Iterable<?> initialContents) {
836 // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY
837 int result = (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE)
838 ? DEFAULT_CAPACITY
839 : configuredExpectedSize;
840
841 // Enlarge to contain initial contents
842 if (initialContents instanceof Collection) {
843 int initialSize = ((Collection<?>) initialContents).size();
844 result = Math.max(result, initialSize);
845 }
846
847 // Now cap it at maxSize + 1
848 return capAtMaximumSize(result, maximumSize);
849 }
850
851 private void growIfNeeded() {
852 if (size > queue.length) {
853 int newCapacity = calculateNewCapacity();
854 Object[] newQueue = new Object[newCapacity];
855 System.arraycopy(queue, 0, newQueue, 0, queue.length);
856 queue = newQueue;
857 }
858 }
859
860 /** Returns ~2x the old capacity if small; ~1.5x otherwise. */
861 private int calculateNewCapacity() {
862 int oldCapacity = queue.length;
863 int newCapacity = (oldCapacity < 64)
864 ? (oldCapacity + 1) * 2
865 : (oldCapacity / 2) * 3;
866 if (newCapacity < 0) {
867 newCapacity = Integer.MAX_VALUE; // overflow - hotspot will throw OOME
868 }
869 return capAtMaximumSize(newCapacity, maximumSize);
870 }
871
872 /** There's no reason for the queueSize to ever be more than maxSize + 1 */
873 private static int capAtMaximumSize(int queueSize, int maximumSize) {
874 return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow
875 }
876 }