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