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