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