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