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.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@Beta 102@GwtCompatible 103@ElementTypesAreNonnullByDefault 104public final class MinMaxPriorityQueue<E> extends AbstractQueue<E> { 105 106 /** 107 * Creates a new min-max priority queue with default settings: natural order, no maximum size, no 108 * initial contents, and an initial expected size of 11. 109 */ 110 public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() { 111 return new Builder<Comparable>(Ordering.natural()).create(); 112 } 113 114 /** 115 * Creates a new min-max priority queue using natural order, no maximum size, and initially 116 * containing the given elements. 117 */ 118 public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create( 119 Iterable<? extends E> initialContents) { 120 return new Builder<E>(Ordering.<E>natural()).create(initialContents); 121 } 122 123 /** 124 * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances 125 * that use {@code comparator} to determine the least and greatest elements. 126 */ 127 /* 128 * TODO(cpovirk): Change to Comparator<? super B> to permit Comparator<@Nullable ...> and 129 * Comparator<SupertypeOfB>? What we have here matches the immutable collections, but those also 130 * expose a public Builder constructor that accepts "? super." So maybe we should do *that* 131 * instead. 132 */ 133 public static <B> Builder<B> orderedBy(Comparator<B> comparator) { 134 return new Builder<B>(comparator); 135 } 136 137 /** 138 * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances 139 * sized appropriately to hold {@code expectedSize} elements. 140 */ 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 public static Builder<Comparable> maximumSize(int maximumSize) { 152 return new Builder<Comparable>(Ordering.natural()).maximumSize(maximumSize); 153 } 154 155 /** 156 * The builder class used in creation of min-max priority queues. Instead of constructing one 157 * directly, use {@link MinMaxPriorityQueue#orderedBy(Comparator)}, {@link 158 * MinMaxPriorityQueue#expectedSize(int)} or {@link MinMaxPriorityQueue#maximumSize(int)}. 159 * 160 * @param <B> the upper bound on the eventual type that can be produced by this builder (for 161 * example, a {@code Builder<Number>} can produce a {@code Queue<Number>} or {@code 162 * Queue<Integer>} but not a {@code Queue<Object>}). 163 * @since 8.0 164 */ 165 @Beta 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<T>( 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<E>(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<E>(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 MinMaxPriortyQueue 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 private class Heap { 527 final Ordering<E> ordering; 528 @Weak Heap otherHeap; // always initialized immediately after construction 529 530 Heap(Ordering<E> ordering) { 531 this.ordering = ordering; 532 } 533 534 int compareElements(int a, int b) { 535 return ordering.compare(elementData(a), elementData(b)); 536 } 537 538 /** 539 * Tries to move {@code toTrickle} from a min to a max level and bubble up there. If it moved 540 * before {@code removeIndex} this method returns a pair as described in {@link #removeAt}. 541 */ 542 @CheckForNull 543 MoveDesc<E> tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle) { 544 int crossOver = crossOver(vacated, toTrickle); 545 if (crossOver == vacated) { 546 return null; 547 } 548 // Successfully crossed over from min to max. 549 // Bubble up max levels. 550 E parent; 551 // If toTrickle is moved up to a parent of removeIndex, the parent is 552 // placed in removeIndex position. We must return that to the iterator so 553 // that it knows to skip it. 554 if (crossOver < removeIndex) { 555 // We crossed over to the parent level in crossOver, so the parent 556 // has already been moved. 557 parent = elementData(removeIndex); 558 } else { 559 parent = elementData(getParentIndex(removeIndex)); 560 } 561 // bubble it up the opposite heap 562 if (otherHeap.bubbleUpAlternatingLevels(crossOver, toTrickle) < removeIndex) { 563 return new MoveDesc<E>(toTrickle, parent); 564 } else { 565 return null; 566 } 567 } 568 569 /** Bubbles a value from {@code index} up the appropriate heap if required. */ 570 void bubbleUp(int index, E x) { 571 int crossOver = crossOverUp(index, x); 572 573 Heap heap; 574 if (crossOver == index) { 575 heap = this; 576 } else { 577 index = crossOver; 578 heap = otherHeap; 579 } 580 heap.bubbleUpAlternatingLevels(index, x); 581 } 582 583 /** 584 * Bubbles a value from {@code index} up the levels of this heap, and returns the index the 585 * element ended up at. 586 */ 587 @CanIgnoreReturnValue 588 int bubbleUpAlternatingLevels(int index, E x) { 589 while (index > 2) { 590 int grandParentIndex = getGrandparentIndex(index); 591 E e = elementData(grandParentIndex); 592 if (ordering.compare(e, x) <= 0) { 593 break; 594 } 595 queue[index] = e; 596 index = grandParentIndex; 597 } 598 queue[index] = x; 599 return index; 600 } 601 602 /** 603 * Returns the index of minimum value between {@code index} and {@code index + len}, or {@code 604 * -1} if {@code index} is greater than {@code size}. 605 */ 606 int findMin(int index, int len) { 607 if (index >= size) { 608 return -1; 609 } 610 checkState(index > 0); 611 int limit = Math.min(index, size - len) + len; 612 int minIndex = index; 613 for (int i = index + 1; i < limit; i++) { 614 if (compareElements(i, minIndex) < 0) { 615 minIndex = i; 616 } 617 } 618 return minIndex; 619 } 620 621 /** Returns the minimum child or {@code -1} if no child exists. */ 622 int findMinChild(int index) { 623 return findMin(getLeftChildIndex(index), 2); 624 } 625 626 /** Returns the minimum grand child or -1 if no grand child exists. */ 627 int findMinGrandChild(int index) { 628 int leftChildIndex = getLeftChildIndex(index); 629 if (leftChildIndex < 0) { 630 return -1; 631 } 632 return findMin(getLeftChildIndex(leftChildIndex), 4); 633 } 634 635 /** 636 * Moves an element one level up from a min level to a max level (or vice versa). Returns the 637 * new position of the element. 638 */ 639 int crossOverUp(int index, E x) { 640 if (index == 0) { 641 queue[0] = x; 642 return 0; 643 } 644 int parentIndex = getParentIndex(index); 645 E parentElement = elementData(parentIndex); 646 if (parentIndex != 0) { 647 // This is a guard for the case of the childless uncle. 648 // Since the end of the array is actually the middle of the heap, 649 // a smaller childless uncle can become a child of x when we 650 // bubble up alternate levels, violating the invariant. 651 int grandparentIndex = getParentIndex(parentIndex); 652 int uncleIndex = getRightChildIndex(grandparentIndex); 653 if (uncleIndex != parentIndex && getLeftChildIndex(uncleIndex) >= size) { 654 E uncleElement = elementData(uncleIndex); 655 if (ordering.compare(uncleElement, parentElement) < 0) { 656 parentIndex = uncleIndex; 657 parentElement = uncleElement; 658 } 659 } 660 } 661 if (ordering.compare(parentElement, x) < 0) { 662 queue[index] = parentElement; 663 queue[parentIndex] = x; 664 return parentIndex; 665 } 666 queue[index] = x; 667 return index; 668 } 669 670 /** 671 * Swap {@code actualLastElement} with the conceptually correct last element of the heap. 672 * Returns the index that {@code actualLastElement} now resides in. 673 * 674 * <p>Since the last element of the array is actually in the middle of the sorted structure, a 675 * childless uncle node could be smaller, which would corrupt the invariant if this element 676 * becomes the new parent of the uncle. In that case, we first switch the last element with its 677 * uncle, before returning. 678 */ 679 int swapWithConceptuallyLastElement(E actualLastElement) { 680 int parentIndex = getParentIndex(size); 681 if (parentIndex != 0) { 682 int grandparentIndex = getParentIndex(parentIndex); 683 int uncleIndex = getRightChildIndex(grandparentIndex); 684 if (uncleIndex != parentIndex && getLeftChildIndex(uncleIndex) >= size) { 685 E uncleElement = elementData(uncleIndex); 686 if (ordering.compare(uncleElement, actualLastElement) < 0) { 687 queue[uncleIndex] = actualLastElement; 688 queue[size] = uncleElement; 689 return uncleIndex; 690 } 691 } 692 } 693 return size; 694 } 695 696 /** 697 * Crosses an element over to the opposite heap by moving it one level down (or up if there are 698 * no elements below it). 699 * 700 * <p>Returns the new position of the element. 701 */ 702 int crossOver(int index, E x) { 703 int minChildIndex = findMinChild(index); 704 // TODO(kevinb): split the && into two if's and move crossOverUp so it's 705 // only called when there's no child. 706 if ((minChildIndex > 0) && (ordering.compare(elementData(minChildIndex), x) < 0)) { 707 queue[index] = elementData(minChildIndex); 708 queue[minChildIndex] = x; 709 return minChildIndex; 710 } 711 return crossOverUp(index, x); 712 } 713 714 /** 715 * Fills the hole at {@code index} by moving in the least of its grandchildren to this position, 716 * then recursively filling the new hole created. 717 * 718 * @return the position of the new hole (where the lowest grandchild moved from, that had no 719 * grandchild to replace it) 720 */ 721 int fillHoleAt(int index) { 722 int minGrandchildIndex; 723 while ((minGrandchildIndex = findMinGrandChild(index)) > 0) { 724 queue[index] = elementData(minGrandchildIndex); 725 index = minGrandchildIndex; 726 } 727 return index; 728 } 729 730 private boolean verifyIndex(int i) { 731 if ((getLeftChildIndex(i) < size) && (compareElements(i, getLeftChildIndex(i)) > 0)) { 732 return false; 733 } 734 if ((getRightChildIndex(i) < size) && (compareElements(i, getRightChildIndex(i)) > 0)) { 735 return false; 736 } 737 if ((i > 0) && (compareElements(i, getParentIndex(i)) > 0)) { 738 return false; 739 } 740 if ((i > 2) && (compareElements(getGrandparentIndex(i), i) > 0)) { 741 return false; 742 } 743 return true; 744 } 745 746 // These would be static if inner classes could have static members. 747 748 private int getLeftChildIndex(int i) { 749 return i * 2 + 1; 750 } 751 752 private int getRightChildIndex(int i) { 753 return i * 2 + 2; 754 } 755 756 private int getParentIndex(int i) { 757 return (i - 1) / 2; 758 } 759 760 private int getGrandparentIndex(int i) { 761 return getParentIndex(getParentIndex(i)); // (i - 3) / 4 762 } 763 } 764 765 /** 766 * Iterates the elements of the queue in no particular order. 767 * 768 * <p>If the underlying queue is modified during iteration an exception will be thrown. 769 */ 770 private class QueueIterator implements Iterator<E> { 771 private int cursor = -1; 772 private int nextCursor = -1; 773 private int expectedModCount = modCount; 774 // The same element is not allowed in both forgetMeNot and skipMe, but duplicates are allowed in 775 // either of them, up to the same multiplicity as the queue. 776 @CheckForNull private Queue<E> forgetMeNot; 777 @CheckForNull private List<E> skipMe; 778 @CheckForNull private E lastFromForgetMeNot; 779 private boolean canRemove; 780 781 @Override 782 public boolean hasNext() { 783 checkModCount(); 784 nextNotInSkipMe(cursor + 1); 785 return (nextCursor < size()) || ((forgetMeNot != null) && !forgetMeNot.isEmpty()); 786 } 787 788 @Override 789 public E next() { 790 checkModCount(); 791 nextNotInSkipMe(cursor + 1); 792 if (nextCursor < size()) { 793 cursor = nextCursor; 794 canRemove = true; 795 return elementData(cursor); 796 } else if (forgetMeNot != null) { 797 cursor = size(); 798 lastFromForgetMeNot = forgetMeNot.poll(); 799 if (lastFromForgetMeNot != null) { 800 canRemove = true; 801 return lastFromForgetMeNot; 802 } 803 } 804 throw new NoSuchElementException("iterator moved past last element in queue."); 805 } 806 807 @Override 808 public void remove() { 809 checkRemove(canRemove); 810 checkModCount(); 811 canRemove = false; 812 expectedModCount++; 813 if (cursor < size()) { 814 MoveDesc<E> moved = removeAt(cursor); 815 if (moved != null) { 816 // Either both are null or neither is, but we check both to satisfy the nullness checker. 817 if (forgetMeNot == null || skipMe == null) { 818 forgetMeNot = new ArrayDeque<E>(); 819 skipMe = new ArrayList<E>(3); 820 } 821 if (!foundAndRemovedExactReference(skipMe, moved.toTrickle)) { 822 forgetMeNot.add(moved.toTrickle); 823 } 824 if (!foundAndRemovedExactReference(forgetMeNot, moved.replaced)) { 825 skipMe.add(moved.replaced); 826 } 827 } 828 cursor--; 829 nextCursor--; 830 } else { // we must have set lastFromForgetMeNot in next() 831 checkState(removeExact(requireNonNull(lastFromForgetMeNot))); 832 lastFromForgetMeNot = null; 833 } 834 } 835 836 /** Returns true if an exact reference (==) was found and removed from the supplied iterable. */ 837 private boolean foundAndRemovedExactReference(Iterable<E> elements, E target) { 838 for (Iterator<E> it = elements.iterator(); it.hasNext(); ) { 839 E element = it.next(); 840 if (element == target) { 841 it.remove(); 842 return true; 843 } 844 } 845 return false; 846 } 847 848 /** Removes only this exact instance, not others that are equals() */ 849 private boolean removeExact(Object target) { 850 for (int i = 0; i < size; i++) { 851 if (queue[i] == target) { 852 removeAt(i); 853 return true; 854 } 855 } 856 return false; 857 } 858 859 private void checkModCount() { 860 if (modCount != expectedModCount) { 861 throw new ConcurrentModificationException(); 862 } 863 } 864 865 /** 866 * Advances nextCursor to the index of the first element after {@code c} that is not in {@code 867 * skipMe} and returns {@code size()} if there is no such element. 868 */ 869 private void nextNotInSkipMe(int c) { 870 if (nextCursor < c) { 871 if (skipMe != null) { 872 while (c < size() && foundAndRemovedExactReference(skipMe, elementData(c))) { 873 c++; 874 } 875 } 876 nextCursor = c; 877 } 878 } 879 } 880 881 /** 882 * Returns an iterator over the elements contained in this collection, <i>in no particular 883 * order</i>. 884 * 885 * <p>The iterator is <i>fail-fast</i>: If the MinMaxPriorityQueue is modified at any time after 886 * the iterator is created, in any way except through the iterator's own remove method, the 887 * iterator will generally throw a {@link ConcurrentModificationException}. Thus, in the face of 888 * concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, 889 * non-deterministic behavior at an undetermined time in the future. 890 * 891 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally 892 * speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent 893 * modification. Fail-fast iterators throw {@code ConcurrentModificationException} on a 894 * best-effort basis. Therefore, it would be wrong to write a program that depended on this 895 * exception for its correctness: <i>the fail-fast behavior of iterators should be used only to 896 * detect bugs.</i> 897 * 898 * @return an iterator over the elements contained in this collection 899 */ 900 @Override 901 public Iterator<E> iterator() { 902 return new QueueIterator(); 903 } 904 905 @Override 906 public void clear() { 907 for (int i = 0; i < size; i++) { 908 queue[i] = null; 909 } 910 size = 0; 911 } 912 913 @Override 914 public Object[] toArray() { 915 Object[] copyTo = new Object[size]; 916 System.arraycopy(queue, 0, copyTo, 0, size); 917 return copyTo; 918 } 919 920 /** 921 * Returns the comparator used to order the elements in this queue. Obeys the general contract of 922 * {@link PriorityQueue#comparator}, but returns {@link Ordering#natural} instead of {@code null} 923 * to indicate natural ordering. 924 */ 925 public Comparator<? super E> comparator() { 926 return minHeap.ordering; 927 } 928 929 @VisibleForTesting 930 int capacity() { 931 return queue.length; 932 } 933 934 // Size/capacity-related methods 935 936 private static final int DEFAULT_CAPACITY = 11; 937 938 @VisibleForTesting 939 static int initialQueueSize( 940 int configuredExpectedSize, int maximumSize, Iterable<?> initialContents) { 941 // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY 942 int result = 943 (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE) 944 ? DEFAULT_CAPACITY 945 : configuredExpectedSize; 946 947 // Enlarge to contain initial contents 948 if (initialContents instanceof Collection) { 949 int initialSize = ((Collection<?>) initialContents).size(); 950 result = Math.max(result, initialSize); 951 } 952 953 // Now cap it at maxSize + 1 954 return capAtMaximumSize(result, maximumSize); 955 } 956 957 private void growIfNeeded() { 958 if (size > queue.length) { 959 int newCapacity = calculateNewCapacity(); 960 Object[] newQueue = new Object[newCapacity]; 961 System.arraycopy(queue, 0, newQueue, 0, queue.length); 962 queue = newQueue; 963 } 964 } 965 966 /** Returns ~2x the old capacity if small; ~1.5x otherwise. */ 967 private int calculateNewCapacity() { 968 int oldCapacity = queue.length; 969 int newCapacity = 970 (oldCapacity < 64) ? (oldCapacity + 1) * 2 : IntMath.checkedMultiply(oldCapacity / 2, 3); 971 return capAtMaximumSize(newCapacity, maximumSize); 972 } 973 974 /** There's no reason for the queueSize to ever be more than maxSize + 1 */ 975 private static int capAtMaximumSize(int queueSize, int maximumSize) { 976 return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow 977 } 978}