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