| /* |
| * Copyright (C) 2010 The Guava Authors |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.collect; |
| |
| import static com.google.common.base.Preconditions.checkArgument; |
| import static com.google.common.base.Preconditions.checkNotNull; |
| import static com.google.common.base.Preconditions.checkPositionIndex; |
| import static com.google.common.base.Preconditions.checkState; |
| import static com.google.common.collect.CollectPreconditions.checkRemove; |
| |
| import com.google.common.annotations.Beta; |
| import com.google.common.annotations.GwtCompatible; |
| import com.google.common.annotations.VisibleForTesting; |
| import com.google.common.math.IntMath; |
| import com.google.errorprone.annotations.CanIgnoreReturnValue; |
| import com.google.j2objc.annotations.Weak; |
| import com.google.j2objc.annotations.WeakOuter; |
| import java.util.AbstractQueue; |
| import java.util.ArrayDeque; |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.ConcurrentModificationException; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.NoSuchElementException; |
| import java.util.PriorityQueue; |
| import java.util.Queue; |
| import org.checkerframework.checker.nullness.compatqual.MonotonicNonNullDecl; |
| import org.checkerframework.checker.nullness.compatqual.NullableDecl; |
| |
| /** |
| * A double-ended priority queue, which provides constant-time access to both its least element and |
| * its greatest element, as determined by the queue's specified comparator. If no comparator is |
| * given at creation time, the natural order of elements is used. If no maximum size is given at |
| * creation time, the queue is unbounded. |
| * |
| * <p>Usage example: |
| * |
| * <pre>{@code |
| * MinMaxPriorityQueue<User> users = MinMaxPriorityQueue.orderedBy(userComparator) |
| * .maximumSize(1000) |
| * .create(); |
| * }</pre> |
| * |
| * <p>As a {@link Queue} it functions exactly as a {@link PriorityQueue}: its head element -- the |
| * implicit target of the methods {@link #peek()}, {@link #poll()} and {@link #remove()} -- is |
| * defined as the <i>least</i> element in the queue according to the queue's comparator. But unlike |
| * a regular priority queue, the methods {@link #peekLast}, {@link #pollLast} and {@link |
| * #removeLast} are also provided, to act on the <i>greatest</i> element in the queue instead. |
| * |
| * <p>A min-max priority queue can be configured with a maximum size. If so, each time the size of |
| * the queue exceeds that value, the queue automatically removes its greatest element according to |
| * its comparator (which might be the element that was just added). This is different from |
| * conventional bounded queues, which either block or reject new elements when full. |
| * |
| * <p>This implementation is based on the <a |
| * href="http://portal.acm.org/citation.cfm?id=6621">min-max heap</a> developed by Atkinson, et al. |
| * Unlike many other double-ended priority queues, it stores elements in a single array, as compact |
| * as the traditional heap data structure used in {@link PriorityQueue}. |
| * |
| * <p>This class is not thread-safe, and does not accept null elements. |
| * |
| * <p><i>Performance notes:</i> |
| * |
| * <ul> |
| * <li>If you only access one end of the queue, and do use a maximum size, this class will perform |
| * significantly worse than a {@code PriorityQueue} with manual eviction above the maximum |
| * size. In many cases {@link Ordering#leastOf} may work for your use case with significantly |
| * improved (and asymptotically superior) performance. |
| * <li>The retrieval operations {@link #peek}, {@link #peekFirst}, {@link #peekLast}, {@link |
| * #element}, and {@link #size} are constant-time. |
| * <li>The enqueuing and dequeuing operations ({@link #offer}, {@link #add}, and all the forms of |
| * {@link #poll} and {@link #remove()}) run in {@code O(log n) time}. |
| * <li>The {@link #remove(Object)} and {@link #contains} operations require linear ({@code O(n)}) |
| * time. |
| * <li>If you only access one end of the queue, and don't use a maximum size, this class is |
| * functionally equivalent to {@link PriorityQueue}, but significantly slower. |
| * </ul> |
| * |
| * @author Sverre Sundsdal |
| * @author Torbjorn Gannholm |
| * @since 8.0 |
| */ |
| @Beta |
| @GwtCompatible |
| public final class MinMaxPriorityQueue<E> extends AbstractQueue<E> { |
| |
| /** |
| * Creates a new min-max priority queue with default settings: natural order, no maximum size, no |
| * initial contents, and an initial expected size of 11. |
| */ |
| public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() { |
| return new Builder<Comparable>(Ordering.natural()).create(); |
| } |
| |
| /** |
| * Creates a new min-max priority queue using natural order, no maximum size, and initially |
| * containing the given elements. |
| */ |
| public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create( |
| Iterable<? extends E> initialContents) { |
| return new Builder<E>(Ordering.<E>natural()).create(initialContents); |
| } |
| |
| /** |
| * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances |
| * that use {@code comparator} to determine the least and greatest elements. |
| */ |
| public static <B> Builder<B> orderedBy(Comparator<B> comparator) { |
| return new Builder<B>(comparator); |
| } |
| |
| /** |
| * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances |
| * sized appropriately to hold {@code expectedSize} elements. |
| */ |
| public static Builder<Comparable> expectedSize(int expectedSize) { |
| return new Builder<Comparable>(Ordering.natural()).expectedSize(expectedSize); |
| } |
| |
| /** |
| * Creates and returns a new builder, configured to build {@code MinMaxPriorityQueue} instances |
| * that are limited to {@code maximumSize} elements. Each time a queue grows beyond this bound, it |
| * immediately removes its greatest element (according to its comparator), which might be the |
| * element that was just added. |
| */ |
| public static Builder<Comparable> maximumSize(int maximumSize) { |
| return new Builder<Comparable>(Ordering.natural()).maximumSize(maximumSize); |
| } |
| |
| /** |
| * The builder class used in creation of min-max priority queues. Instead of constructing one |
| * directly, use {@link MinMaxPriorityQueue#orderedBy(Comparator)}, {@link |
| * MinMaxPriorityQueue#expectedSize(int)} or {@link MinMaxPriorityQueue#maximumSize(int)}. |
| * |
| * @param <B> the upper bound on the eventual type that can be produced by this builder (for |
| * example, a {@code Builder<Number>} can produce a {@code Queue<Number>} or {@code |
| * Queue<Integer>} but not a {@code Queue<Object>}). |
| * @since 8.0 |
| */ |
| @Beta |
| public static final class Builder<B> { |
| /* |
| * TODO(kevinb): when the dust settles, see if we still need this or can |
| * just default to DEFAULT_CAPACITY. |
| */ |
| private static final int UNSET_EXPECTED_SIZE = -1; |
| |
| private final Comparator<B> comparator; |
| private int expectedSize = UNSET_EXPECTED_SIZE; |
| private int maximumSize = Integer.MAX_VALUE; |
| |
| private Builder(Comparator<B> comparator) { |
| this.comparator = checkNotNull(comparator); |
| } |
| |
| /** |
| * Configures this builder to build min-max priority queues with an initial expected size of |
| * {@code expectedSize}. |
| */ |
| @CanIgnoreReturnValue |
| public Builder<B> expectedSize(int expectedSize) { |
| checkArgument(expectedSize >= 0); |
| this.expectedSize = expectedSize; |
| return this; |
| } |
| |
| /** |
| * Configures this builder to build {@code MinMaxPriorityQueue} instances that are limited to |
| * {@code maximumSize} elements. Each time a queue grows beyond this bound, it immediately |
| * removes its greatest element (according to its comparator), which might be the element that |
| * was just added. |
| */ |
| @CanIgnoreReturnValue |
| public Builder<B> maximumSize(int maximumSize) { |
| checkArgument(maximumSize > 0); |
| this.maximumSize = maximumSize; |
| return this; |
| } |
| |
| /** |
| * Builds a new min-max priority queue using the previously specified options, and having no |
| * initial contents. |
| */ |
| public <T extends B> MinMaxPriorityQueue<T> create() { |
| return create(Collections.<T>emptySet()); |
| } |
| |
| /** |
| * Builds a new min-max priority queue using the previously specified options, and having the |
| * given initial elements. |
| */ |
| public <T extends B> MinMaxPriorityQueue<T> create(Iterable<? extends T> initialContents) { |
| MinMaxPriorityQueue<T> queue = |
| new MinMaxPriorityQueue<T>( |
| this, initialQueueSize(expectedSize, maximumSize, initialContents)); |
| for (T element : initialContents) { |
| queue.offer(element); |
| } |
| return queue; |
| } |
| |
| @SuppressWarnings("unchecked") // safe "contravariant cast" |
| private <T extends B> Ordering<T> ordering() { |
| return Ordering.from((Comparator<T>) comparator); |
| } |
| } |
| |
| private final Heap minHeap; |
| private final Heap maxHeap; |
| @VisibleForTesting final int maximumSize; |
| private Object[] queue; |
| private int size; |
| private int modCount; |
| |
| private MinMaxPriorityQueue(Builder<? super E> builder, int queueSize) { |
| Ordering<E> ordering = builder.ordering(); |
| this.minHeap = new Heap(ordering); |
| this.maxHeap = new Heap(ordering.reverse()); |
| minHeap.otherHeap = maxHeap; |
| maxHeap.otherHeap = minHeap; |
| |
| this.maximumSize = builder.maximumSize; |
| // TODO(kevinb): pad? |
| this.queue = new Object[queueSize]; |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| /** |
| * Adds the given element to this queue. If this queue has a maximum size, after adding {@code |
| * element} the queue will automatically evict its greatest element (according to its comparator), |
| * which may be {@code element} itself. |
| * |
| * @return {@code true} always |
| */ |
| @CanIgnoreReturnValue |
| @Override |
| public boolean add(E element) { |
| offer(element); |
| return true; |
| } |
| |
| @CanIgnoreReturnValue |
| @Override |
| public boolean addAll(Collection<? extends E> newElements) { |
| boolean modified = false; |
| for (E element : newElements) { |
| offer(element); |
| modified = true; |
| } |
| return modified; |
| } |
| |
| /** |
| * Adds the given element to this queue. If this queue has a maximum size, after adding {@code |
| * element} the queue will automatically evict its greatest element (according to its comparator), |
| * which may be {@code element} itself. |
| */ |
| @CanIgnoreReturnValue |
| @Override |
| public boolean offer(E element) { |
| checkNotNull(element); |
| modCount++; |
| int insertIndex = size++; |
| |
| growIfNeeded(); |
| |
| // Adds the element to the end of the heap and bubbles it up to the correct |
| // position. |
| heapForIndex(insertIndex).bubbleUp(insertIndex, element); |
| return size <= maximumSize || pollLast() != element; |
| } |
| |
| @CanIgnoreReturnValue |
| @Override |
| public E poll() { |
| return isEmpty() ? null : removeAndGet(0); |
| } |
| |
| @SuppressWarnings("unchecked") // we must carefully only allow Es to get in |
| E elementData(int index) { |
| return (E) queue[index]; |
| } |
| |
| @Override |
| public E peek() { |
| return isEmpty() ? null : elementData(0); |
| } |
| |
| /** Returns the index of the max element. */ |
| private int getMaxElementIndex() { |
| switch (size) { |
| case 1: |
| return 0; // The lone element in the queue is the maximum. |
| case 2: |
| return 1; // The lone element in the maxHeap is the maximum. |
| default: |
| // The max element must sit on the first level of the maxHeap. It is |
| // actually the *lesser* of the two from the maxHeap's perspective. |
| return (maxHeap.compareElements(1, 2) <= 0) ? 1 : 2; |
| } |
| } |
| |
| /** |
| * Removes and returns the least element of this queue, or returns {@code null} if the queue is |
| * empty. |
| */ |
| @CanIgnoreReturnValue |
| public E pollFirst() { |
| return poll(); |
| } |
| |
| /** |
| * Removes and returns the least element of this queue. |
| * |
| * @throws NoSuchElementException if the queue is empty |
| */ |
| @CanIgnoreReturnValue |
| public E removeFirst() { |
| return remove(); |
| } |
| |
| /** |
| * Retrieves, but does not remove, the least element of this queue, or returns {@code null} if the |
| * queue is empty. |
| */ |
| public E peekFirst() { |
| return peek(); |
| } |
| |
| /** |
| * Removes and returns the greatest element of this queue, or returns {@code null} if the queue is |
| * empty. |
| */ |
| @CanIgnoreReturnValue |
| public E pollLast() { |
| return isEmpty() ? null : removeAndGet(getMaxElementIndex()); |
| } |
| |
| /** |
| * Removes and returns the greatest element of this queue. |
| * |
| * @throws NoSuchElementException if the queue is empty |
| */ |
| @CanIgnoreReturnValue |
| public E removeLast() { |
| if (isEmpty()) { |
| throw new NoSuchElementException(); |
| } |
| return removeAndGet(getMaxElementIndex()); |
| } |
| |
| /** |
| * Retrieves, but does not remove, the greatest element of this queue, or returns {@code null} if |
| * the queue is empty. |
| */ |
| public E peekLast() { |
| return isEmpty() ? null : elementData(getMaxElementIndex()); |
| } |
| |
| /** |
| * Removes the element at position {@code index}. |
| * |
| * <p>Normally this method leaves the elements at up to {@code index - 1}, inclusive, untouched. |
| * Under these circumstances, it returns {@code null}. |
| * |
| * <p>Occasionally, in order to maintain the heap invariant, it must swap a later element of the |
| * list with one before {@code index}. Under these circumstances it returns a pair of elements as |
| * a {@link MoveDesc}. The first one is the element that was previously at the end of the heap and |
| * is now at some position before {@code index}. The second element is the one that was swapped |
| * down to replace the element at {@code index}. This fact is used by iterator.remove so as to |
| * visit elements during a traversal once and only once. |
| */ |
| @VisibleForTesting |
| @CanIgnoreReturnValue |
| MoveDesc<E> removeAt(int index) { |
| checkPositionIndex(index, size); |
| modCount++; |
| size--; |
| if (size == index) { |
| queue[size] = null; |
| return null; |
| } |
| E actualLastElement = elementData(size); |
| int lastElementAt = heapForIndex(size).swapWithConceptuallyLastElement(actualLastElement); |
| if (lastElementAt == index) { |
| // 'actualLastElement' is now at 'lastElementAt', and the element that was at 'lastElementAt' |
| // is now at the end of queue. If that's the element we wanted to remove in the first place, |
| // don't try to (incorrectly) trickle it. Instead, just delete it and we're done. |
| queue[size] = null; |
| return null; |
| } |
| E toTrickle = elementData(size); |
| queue[size] = null; |
| MoveDesc<E> changes = fillHole(index, toTrickle); |
| if (lastElementAt < index) { |
| // Last element is moved to before index, swapped with trickled element. |
| if (changes == null) { |
| // The trickled element is still after index. |
| return new MoveDesc<E>(actualLastElement, toTrickle); |
| } else { |
| // The trickled element is back before index, but the replaced element |
| // has now been moved after index. |
| return new MoveDesc<E>(actualLastElement, changes.replaced); |
| } |
| } |
| // Trickled element was after index to begin with, no adjustment needed. |
| return changes; |
| } |
| |
| private MoveDesc<E> fillHole(int index, E toTrickle) { |
| Heap heap = heapForIndex(index); |
| // We consider elementData(index) a "hole", and we want to fill it |
| // with the last element of the heap, toTrickle. |
| // Since the last element of the heap is from the bottom level, we |
| // optimistically fill index position with elements from lower levels, |
| // moving the hole down. In most cases this reduces the number of |
| // comparisons with toTrickle, but in some cases we will need to bubble it |
| // all the way up again. |
| int vacated = heap.fillHoleAt(index); |
| // Try to see if toTrickle can be bubbled up min levels. |
| int bubbledTo = heap.bubbleUpAlternatingLevels(vacated, toTrickle); |
| if (bubbledTo == vacated) { |
| // Could not bubble toTrickle up min levels, try moving |
| // it from min level to max level (or max to min level) and bubble up |
| // there. |
| return heap.tryCrossOverAndBubbleUp(index, vacated, toTrickle); |
| } else { |
| return (bubbledTo < index) ? new MoveDesc<E>(toTrickle, elementData(index)) : null; |
| } |
| } |
| |
| // Returned from removeAt() to iterator.remove() |
| static class MoveDesc<E> { |
| final E toTrickle; |
| final E replaced; |
| |
| MoveDesc(E toTrickle, E replaced) { |
| this.toTrickle = toTrickle; |
| this.replaced = replaced; |
| } |
| } |
| |
| /** Removes and returns the value at {@code index}. */ |
| private E removeAndGet(int index) { |
| E value = elementData(index); |
| removeAt(index); |
| return value; |
| } |
| |
| private Heap heapForIndex(int i) { |
| return isEvenLevel(i) ? minHeap : maxHeap; |
| } |
| |
| private static final int EVEN_POWERS_OF_TWO = 0x55555555; |
| private static final int ODD_POWERS_OF_TWO = 0xaaaaaaaa; |
| |
| @VisibleForTesting |
| static boolean isEvenLevel(int index) { |
| int oneBased = ~~(index + 1); // for GWT |
| checkState(oneBased > 0, "negative index"); |
| return (oneBased & EVEN_POWERS_OF_TWO) > (oneBased & ODD_POWERS_OF_TWO); |
| } |
| |
| /** |
| * Returns {@code true} if the MinMax heap structure holds. This is only used in testing. |
| * |
| * <p>TODO(kevinb): move to the test class? |
| */ |
| @VisibleForTesting |
| boolean isIntact() { |
| for (int i = 1; i < size; i++) { |
| if (!heapForIndex(i).verifyIndex(i)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /** |
| * Each instance of MinMaxPriortyQueue encapsulates two instances of Heap: a min-heap and a |
| * max-heap. Conceptually, these might each have their own array for storage, but for efficiency's |
| * sake they are stored interleaved on alternate heap levels in the same array (MMPQ.queue). |
| */ |
| @WeakOuter |
| private class Heap { |
| final Ordering<E> ordering; |
| @MonotonicNonNullDecl @Weak Heap otherHeap; |
| |
| Heap(Ordering<E> ordering) { |
| this.ordering = ordering; |
| } |
| |
| int compareElements(int a, int b) { |
| return ordering.compare(elementData(a), elementData(b)); |
| } |
| |
| /** |
| * Tries to move {@code toTrickle} from a min to a max level and bubble up there. If it moved |
| * before {@code removeIndex} this method returns a pair as described in {@link #removeAt}. |
| */ |
| MoveDesc<E> tryCrossOverAndBubbleUp(int removeIndex, int vacated, E toTrickle) { |
| int crossOver = crossOver(vacated, toTrickle); |
| if (crossOver == vacated) { |
| return null; |
| } |
| // Successfully crossed over from min to max. |
| // Bubble up max levels. |
| E parent; |
| // If toTrickle is moved up to a parent of removeIndex, the parent is |
| // placed in removeIndex position. We must return that to the iterator so |
| // that it knows to skip it. |
| if (crossOver < removeIndex) { |
| // We crossed over to the parent level in crossOver, so the parent |
| // has already been moved. |
| parent = elementData(removeIndex); |
| } else { |
| parent = elementData(getParentIndex(removeIndex)); |
| } |
| // bubble it up the opposite heap |
| if (otherHeap.bubbleUpAlternatingLevels(crossOver, toTrickle) < removeIndex) { |
| return new MoveDesc<E>(toTrickle, parent); |
| } else { |
| return null; |
| } |
| } |
| |
| /** Bubbles a value from {@code index} up the appropriate heap if required. */ |
| void bubbleUp(int index, E x) { |
| int crossOver = crossOverUp(index, x); |
| |
| Heap heap; |
| if (crossOver == index) { |
| heap = this; |
| } else { |
| index = crossOver; |
| heap = otherHeap; |
| } |
| heap.bubbleUpAlternatingLevels(index, x); |
| } |
| |
| /** |
| * Bubbles a value from {@code index} up the levels of this heap, and returns the index the |
| * element ended up at. |
| */ |
| @CanIgnoreReturnValue |
| int bubbleUpAlternatingLevels(int index, E x) { |
| while (index > 2) { |
| int grandParentIndex = getGrandparentIndex(index); |
| E e = elementData(grandParentIndex); |
| if (ordering.compare(e, x) <= 0) { |
| break; |
| } |
| queue[index] = e; |
| index = grandParentIndex; |
| } |
| queue[index] = x; |
| return index; |
| } |
| |
| /** |
| * Returns the index of minimum value between {@code index} and {@code index + len}, or {@code |
| * -1} if {@code index} is greater than {@code size}. |
| */ |
| int findMin(int index, int len) { |
| if (index >= size) { |
| return -1; |
| } |
| checkState(index > 0); |
| int limit = Math.min(index, size - len) + len; |
| int minIndex = index; |
| for (int i = index + 1; i < limit; i++) { |
| if (compareElements(i, minIndex) < 0) { |
| minIndex = i; |
| } |
| } |
| return minIndex; |
| } |
| |
| /** Returns the minimum child or {@code -1} if no child exists. */ |
| int findMinChild(int index) { |
| return findMin(getLeftChildIndex(index), 2); |
| } |
| |
| /** Returns the minimum grand child or -1 if no grand child exists. */ |
| int findMinGrandChild(int index) { |
| int leftChildIndex = getLeftChildIndex(index); |
| if (leftChildIndex < 0) { |
| return -1; |
| } |
| return findMin(getLeftChildIndex(leftChildIndex), 4); |
| } |
| |
| /** |
| * Moves an element one level up from a min level to a max level (or vice versa). Returns the |
| * new position of the element. |
| */ |
| int crossOverUp(int index, E x) { |
| if (index == 0) { |
| queue[0] = x; |
| return 0; |
| } |
| int parentIndex = getParentIndex(index); |
| E parentElement = elementData(parentIndex); |
| if (parentIndex != 0) { |
| // This is a guard for the case of the childless uncle. |
| // Since the end of the array is actually the middle of the heap, |
| // a smaller childless uncle can become a child of x when we |
| // bubble up alternate levels, violating the invariant. |
| int grandparentIndex = getParentIndex(parentIndex); |
| int uncleIndex = getRightChildIndex(grandparentIndex); |
| if (uncleIndex != parentIndex && getLeftChildIndex(uncleIndex) >= size) { |
| E uncleElement = elementData(uncleIndex); |
| if (ordering.compare(uncleElement, parentElement) < 0) { |
| parentIndex = uncleIndex; |
| parentElement = uncleElement; |
| } |
| } |
| } |
| if (ordering.compare(parentElement, x) < 0) { |
| queue[index] = parentElement; |
| queue[parentIndex] = x; |
| return parentIndex; |
| } |
| queue[index] = x; |
| return index; |
| } |
| |
| /** |
| * Swap {@code actualLastElement} with the conceptually correct last element of the heap. |
| * Returns the index that {@code actualLastElement} now resides in. |
| * |
| * <p>Since the last element of the array is actually in the middle of the sorted structure, a |
| * childless uncle node could be smaller, which would corrupt the invariant if this element |
| * becomes the new parent of the uncle. In that case, we first switch the last element with its |
| * uncle, before returning. |
| */ |
| int swapWithConceptuallyLastElement(E actualLastElement) { |
| int parentIndex = getParentIndex(size); |
| if (parentIndex != 0) { |
| int grandparentIndex = getParentIndex(parentIndex); |
| int uncleIndex = getRightChildIndex(grandparentIndex); |
| if (uncleIndex != parentIndex && getLeftChildIndex(uncleIndex) >= size) { |
| E uncleElement = elementData(uncleIndex); |
| if (ordering.compare(uncleElement, actualLastElement) < 0) { |
| queue[uncleIndex] = actualLastElement; |
| queue[size] = uncleElement; |
| return uncleIndex; |
| } |
| } |
| } |
| return size; |
| } |
| |
| /** |
| * Crosses an element over to the opposite heap by moving it one level down (or up if there are |
| * no elements below it). |
| * |
| * <p>Returns the new position of the element. |
| */ |
| int crossOver(int index, E x) { |
| int minChildIndex = findMinChild(index); |
| // TODO(kevinb): split the && into two if's and move crossOverUp so it's |
| // only called when there's no child. |
| if ((minChildIndex > 0) && (ordering.compare(elementData(minChildIndex), x) < 0)) { |
| queue[index] = elementData(minChildIndex); |
| queue[minChildIndex] = x; |
| return minChildIndex; |
| } |
| return crossOverUp(index, x); |
| } |
| |
| /** |
| * Fills the hole at {@code index} by moving in the least of its grandchildren to this position, |
| * then recursively filling the new hole created. |
| * |
| * @return the position of the new hole (where the lowest grandchild moved from, that had no |
| * grandchild to replace it) |
| */ |
| int fillHoleAt(int index) { |
| int minGrandchildIndex; |
| while ((minGrandchildIndex = findMinGrandChild(index)) > 0) { |
| queue[index] = elementData(minGrandchildIndex); |
| index = minGrandchildIndex; |
| } |
| return index; |
| } |
| |
| private boolean verifyIndex(int i) { |
| if ((getLeftChildIndex(i) < size) && (compareElements(i, getLeftChildIndex(i)) > 0)) { |
| return false; |
| } |
| if ((getRightChildIndex(i) < size) && (compareElements(i, getRightChildIndex(i)) > 0)) { |
| return false; |
| } |
| if ((i > 0) && (compareElements(i, getParentIndex(i)) > 0)) { |
| return false; |
| } |
| if ((i > 2) && (compareElements(getGrandparentIndex(i), i) > 0)) { |
| return false; |
| } |
| return true; |
| } |
| |
| // These would be static if inner classes could have static members. |
| |
| private int getLeftChildIndex(int i) { |
| return i * 2 + 1; |
| } |
| |
| private int getRightChildIndex(int i) { |
| return i * 2 + 2; |
| } |
| |
| private int getParentIndex(int i) { |
| return (i - 1) / 2; |
| } |
| |
| private int getGrandparentIndex(int i) { |
| return getParentIndex(getParentIndex(i)); // (i - 3) / 4 |
| } |
| } |
| |
| /** |
| * Iterates the elements of the queue in no particular order. |
| * |
| * <p>If the underlying queue is modified during iteration an exception will be thrown. |
| */ |
| private class QueueIterator implements Iterator<E> { |
| private int cursor = -1; |
| private int nextCursor = -1; |
| private int expectedModCount = modCount; |
| // The same element is not allowed in both forgetMeNot and skipMe, but duplicates are allowed in |
| // either of them, up to the same multiplicity as the queue. |
| @MonotonicNonNullDecl private Queue<E> forgetMeNot; |
| @MonotonicNonNullDecl private List<E> skipMe; |
| @NullableDecl private E lastFromForgetMeNot; |
| private boolean canRemove; |
| |
| @Override |
| public boolean hasNext() { |
| checkModCount(); |
| nextNotInSkipMe(cursor + 1); |
| return (nextCursor < size()) || ((forgetMeNot != null) && !forgetMeNot.isEmpty()); |
| } |
| |
| @Override |
| public E next() { |
| checkModCount(); |
| nextNotInSkipMe(cursor + 1); |
| if (nextCursor < size()) { |
| cursor = nextCursor; |
| canRemove = true; |
| return elementData(cursor); |
| } else if (forgetMeNot != null) { |
| cursor = size(); |
| lastFromForgetMeNot = forgetMeNot.poll(); |
| if (lastFromForgetMeNot != null) { |
| canRemove = true; |
| return lastFromForgetMeNot; |
| } |
| } |
| throw new NoSuchElementException("iterator moved past last element in queue."); |
| } |
| |
| @Override |
| public void remove() { |
| checkRemove(canRemove); |
| checkModCount(); |
| canRemove = false; |
| expectedModCount++; |
| if (cursor < size()) { |
| MoveDesc<E> moved = removeAt(cursor); |
| if (moved != null) { |
| if (forgetMeNot == null) { |
| forgetMeNot = new ArrayDeque<E>(); |
| skipMe = new ArrayList<E>(3); |
| } |
| if (!foundAndRemovedExactReference(skipMe, moved.toTrickle)) { |
| forgetMeNot.add(moved.toTrickle); |
| } |
| if (!foundAndRemovedExactReference(forgetMeNot, moved.replaced)) { |
| skipMe.add(moved.replaced); |
| } |
| } |
| cursor--; |
| nextCursor--; |
| } else { // we must have set lastFromForgetMeNot in next() |
| checkState(removeExact(lastFromForgetMeNot)); |
| lastFromForgetMeNot = null; |
| } |
| } |
| |
| /** Returns true if an exact reference (==) was found and removed from the supplied iterable. */ |
| private boolean foundAndRemovedExactReference(Iterable<E> elements, E target) { |
| for (Iterator<E> it = elements.iterator(); it.hasNext(); ) { |
| E element = it.next(); |
| if (element == target) { |
| it.remove(); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** Removes only this exact instance, not others that are equals() */ |
| private boolean removeExact(Object target) { |
| for (int i = 0; i < size; i++) { |
| if (queue[i] == target) { |
| removeAt(i); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| private void checkModCount() { |
| if (modCount != expectedModCount) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| /** |
| * Advances nextCursor to the index of the first element after {@code c} that is not in {@code |
| * skipMe} and returns {@code size()} if there is no such element. |
| */ |
| private void nextNotInSkipMe(int c) { |
| if (nextCursor < c) { |
| if (skipMe != null) { |
| while (c < size() && foundAndRemovedExactReference(skipMe, elementData(c))) { |
| c++; |
| } |
| } |
| nextCursor = c; |
| } |
| } |
| } |
| |
| /** |
| * Returns an iterator over the elements contained in this collection, <i>in no particular |
| * order</i>. |
| * |
| * <p>The iterator is <i>fail-fast</i>: If the MinMaxPriorityQueue is modified at any time after |
| * the iterator is created, in any way except through the iterator's own remove method, the |
| * iterator will generally throw a {@link ConcurrentModificationException}. Thus, in the face of |
| * concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, |
| * non-deterministic behavior at an undetermined time in the future. |
| * |
| * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally |
| * speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent |
| * modification. Fail-fast iterators throw {@code ConcurrentModificationException} on a |
| * best-effort basis. Therefore, it would be wrong to write a program that depended on this |
| * exception for its correctness: <i>the fail-fast behavior of iterators should be used only to |
| * detect bugs.</i> |
| * |
| * @return an iterator over the elements contained in this collection |
| */ |
| @Override |
| public Iterator<E> iterator() { |
| return new QueueIterator(); |
| } |
| |
| @Override |
| public void clear() { |
| for (int i = 0; i < size; i++) { |
| queue[i] = null; |
| } |
| size = 0; |
| } |
| |
| @Override |
| public Object[] toArray() { |
| Object[] copyTo = new Object[size]; |
| System.arraycopy(queue, 0, copyTo, 0, size); |
| return copyTo; |
| } |
| |
| /** |
| * Returns the comparator used to order the elements in this queue. Obeys the general contract of |
| * {@link PriorityQueue#comparator}, but returns {@link Ordering#natural} instead of {@code null} |
| * to indicate natural ordering. |
| */ |
| public Comparator<? super E> comparator() { |
| return minHeap.ordering; |
| } |
| |
| @VisibleForTesting |
| int capacity() { |
| return queue.length; |
| } |
| |
| // Size/capacity-related methods |
| |
| private static final int DEFAULT_CAPACITY = 11; |
| |
| @VisibleForTesting |
| static int initialQueueSize( |
| int configuredExpectedSize, int maximumSize, Iterable<?> initialContents) { |
| // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY |
| int result = |
| (configuredExpectedSize == Builder.UNSET_EXPECTED_SIZE) |
| ? DEFAULT_CAPACITY |
| : configuredExpectedSize; |
| |
| // Enlarge to contain initial contents |
| if (initialContents instanceof Collection) { |
| int initialSize = ((Collection<?>) initialContents).size(); |
| result = Math.max(result, initialSize); |
| } |
| |
| // Now cap it at maxSize + 1 |
| return capAtMaximumSize(result, maximumSize); |
| } |
| |
| private void growIfNeeded() { |
| if (size > queue.length) { |
| int newCapacity = calculateNewCapacity(); |
| Object[] newQueue = new Object[newCapacity]; |
| System.arraycopy(queue, 0, newQueue, 0, queue.length); |
| queue = newQueue; |
| } |
| } |
| |
| /** Returns ~2x the old capacity if small; ~1.5x otherwise. */ |
| private int calculateNewCapacity() { |
| int oldCapacity = queue.length; |
| int newCapacity = |
| (oldCapacity < 64) ? (oldCapacity + 1) * 2 : IntMath.checkedMultiply(oldCapacity / 2, 3); |
| return capAtMaximumSize(newCapacity, maximumSize); |
| } |
| |
| /** There's no reason for the queueSize to ever be more than maxSize + 1 */ |
| private static int capAtMaximumSize(int queueSize, int maximumSize) { |
| return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow |
| } |
| } |