Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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 java.util.List;
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 construction time, the natural order of elements is used.

As a java.util.Queue it functions exactly as a java.util.PriorityQueue: its head element -- the implicit target of the methods peek(), poll() and java.util.AbstractQueue.remove() -- is defined as the least element in the queue according to the queue's comparator. But unlike a regular priority queue, the methods peekLast(), pollLast() and removeLast() are also provided, to act on the greatest element in the queue instead.

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.

This implementation is based on the min-max heap 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 java.util.PriorityQueue.

This class is not thread-safe, and does not accept null elements.

Performance notes:

Author(s):
Sverre Sundsdal
Torbjorn Gannholm
Since:
8.0
 
 // TODO(kevinb): GWT compatibility
 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 MinMaxPriorityQueue instances that use 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 MinMaxPriorityQueue instances sized appropriately to hold expectedSize elements.
  public static Builder<ComparableexpectedSize(int expectedSize) {
    return new Builder<Comparable>(Ordering.natural())
        .expectedSize(expectedSize);
  }

  
Creates and returns a new builder, configured to build MinMaxPriorityQueue instances that are limited to 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<ComparablemaximumSize(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 MinMaxPriorityQueue.orderedBy(java.util.Comparator), MinMaxPriorityQueue.expectedSize(int) or MinMaxPriorityQueue.maximumSize(int).

Parameters:
<B> the upper bound on the eventual type that can be produced by this builder (for example, a Builder<Number> can produce a Queue<Number> or Queue<Integer> but not a 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 = ;
    private int maximumSize = .;
    private Builder(Comparator<B> comparator) {
      this. = checkNotNull(comparator);
    }

    
Configures this builder to build min-max priority queues with an initial expected size of expectedSize.
    public Builder<B> expectedSize(int expectedSize) {
      checkArgument(expectedSize >= 0);
      this. = expectedSize;
      return this;
    }

    
Configures this builder to build MinMaxPriorityQueue instances that are limited to 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 Builder<B> maximumSize(int maximumSize) {
      checkArgument(maximumSize > 0);
      this. = 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>(
          thisinitialQueueSize(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>) );
    }
  }
  private final Heap minHeap;
  private final Heap maxHeap;
  private Object[] queue;
  private int size;
  private int modCount;
  private MinMaxPriorityQueue(Builder<? super E> builderint queueSize) {
    Ordering<E> ordering = builder.ordering();
    this. = new Heap(ordering);
    this. = new Heap(ordering.reverse());
    this. = builder.maximumSize;
    // TODO(kevinb): pad?
    this. = new Object[queueSize];
  }
  @Override public int size() {
    return ;
  }

  
Adds the given element to this queue. If this queue has a maximum size, after adding element the queue will automatically evict its greatest element (according to its comparator), which may be element itself.

Returns:
true always
  @Override public boolean add(E element) {
    offer(element);
    return true;
  }
  @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 element the queue will automatically evict its greatest element (according to its comparator), which may be element itself.
  @Override public boolean offer(E element) {
    checkNotNull(element);
    ++;
    int insertIndex = ++;
    growIfNeeded();
    // Adds the element to the end of the heap and bubbles it up to the correct
    // position.
    heapForIndex(insertIndex).bubbleUp(insertIndexelement);
    return  <=  || pollLast() != element;
  }
  @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) [index];
  }
  @Override public E peek() {
    return isEmpty() ? null : elementData(0);
  }

  
Returns the index of the max element.
  private int getMaxElementIndex() {
    switch () {
      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 (.compareElements(1, 2) <= 0) ? 1 : 2;
    }
  }

  
Removes and returns the least element of this queue, or returns null if the queue is empty.
  public E pollFirst() {
    return poll();
  }

  
Removes and returns the least element of this queue.

Throws:
java.util.NoSuchElementException if the queue is empty
  public E removeFirst() {
    return remove();
  }

  
Retrieves, but does not remove, the least element of this queue, or returns null if the queue is empty.
  public E peekFirst() {
    return peek();
  }

  
Removes and returns the greatest element of this queue, or returns null if the queue is empty.
  public E pollLast() {
    return isEmpty() ? null : removeAndGet(getMaxElementIndex());
  }

  
Removes and returns the greatest element of this queue.

Throws:
java.util.NoSuchElementException if the queue is empty
  public E removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
  }

  
Retrieves, but does not remove, the greatest element of this queue, or returns null if the queue is empty.
  public E peekLast() {
    return isEmpty() ? null : elementData(getMaxElementIndex());
  }

  
Removes the element at position index.

Normally this method leaves the elements at up to index - 1, inclusive, untouched. Under these circumstances, it returns null.

Occasionally, in order to maintain the heap invariant, it must swap a later element of the list with one before index. Under these circumstances it returns a pair of elements as a MinMaxPriorityQueue.MoveDesc. The first one is the element that was previously at the end of the heap and is now at some position before index. The second element is the one that was swapped down to replace the element at index. This fact is used by iterator.remove so as to visit elements during a traversal once and only once.

  @VisibleForTesting MoveDesc<E> removeAt(int index) {
    checkPositionIndex(index);
    ++;
    --;
    if ( == index) {
      [] = null;
      return null;
    }
    E actualLastElement = elementData();
    int lastElementAt = heapForIndex()
        .getCorrectLastElement(actualLastElement);
    E toTrickle = elementData();
    [] = null;
    MoveDesc<E> changes = fillHole(indextoTrickle);
    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>(actualLastElementtoTrickle);
      } else {
        // The trickled element is back before index, but the replaced element
        // has now been moved after index.
        return new MoveDesc<E>(actualLastElementchanges.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(vacatedtoTrickle);
    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(indexvacatedtoTrickle);
    } else {
      return (bubbledTo < index)
          ? new MoveDesc<E>(toTrickleelementData(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;
      this. = replaced;
    }
  }

  
Removes and returns the value at index.
  private E removeAndGet(int index) {
    E value = elementData(index);
    removeAt(index);
    return value;
  }
  private Heap heapForIndex(int i) {
    return isEvenLevel(i) ?  : ;
  }
  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;
    checkState(oneBased > 0, "negative index");
    return (oneBased & ) > (oneBased & );
  }

  
Returns true if the MinMax heap structure holds. This is only used in testing. TODO(kevinb): move to the test class?
  @VisibleForTesting boolean isIntact() {
    for (int i = 1; i < 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).
  private class Heap {
    final Ordering<E> ordering;
    Heap otherHeap;
    Heap(Ordering<E> ordering) {
      this. = ordering;
    }
    int compareElements(int aint b) {
      return .compare(elementData(a), elementData(b));
    }

    
Tries to move toTrickle from a min to a max level and bubble up there. If it moved before removeIndex this method returns a pair as described in MinMaxPriorityQueue.removeAt(int).
        int removeIndexint vacated, E toTrickle) {
      int crossOver = crossOver(vacatedtoTrickle);
      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 (.bubbleUpAlternatingLevels(crossOvertoTrickle)
          < removeIndex) {
        return new MoveDesc<E>(toTrickleparent);
      } else {
        return null;
      }
    }

    
Bubbles a value from index up the appropriate heap if required.
    void bubbleUp(int index, E x) {
      int crossOver = crossOverUp(indexx);
      Heap heap;
      if (crossOver == index) {
        heap = this;
      } else {
        index = crossOver;
        heap = ;
      }
      heap.bubbleUpAlternatingLevels(indexx);
    }

    
Bubbles a value from index up the levels of this heap, and returns the index the element ended up at.
    int bubbleUpAlternatingLevels(int index, E x) {
      while (index > 2) {
        int grandParentIndex = getGrandparentIndex(index);
        E e = elementData(grandParentIndex);
        if (.compare(ex) <= 0) {
          break;
        }
        [index] = e;
        index = grandParentIndex;
      }
      [index] = x;
      return index;
    }

    
Returns the index of minimum value between index and index + len, or -1 if index is greater than size.
    int findMin(int indexint len) {
      if (index >= ) {
        return -1;
      }
      checkState(index > 0);
      int limit = Math.min(index - len) + len;
      int minIndex = index;
      for (int i = index + 1; i < limiti++) {
        if (compareElements(iminIndex) < 0) {
          minIndex = i;
        }
      }
      return minIndex;
    }

    
Returns the minimum child or -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) {
        [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) >= ) {
          E uncleElement = elementData(uncleIndex);
          if (.compare(uncleElementparentElement) < 0) {
            parentIndex = uncleIndex;
            parentElement = uncleElement;
          }
        }
      }
      if (.compare(parentElementx) < 0) {
        [index] = parentElement;
        [parentIndex] = x;
        return parentIndex;
      }
      [index] = x;
      return index;
    }

    
Returns the conceptually correct last element of the heap.

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 getCorrectLastElement(E actualLastElement) {
      int parentIndex = getParentIndex();
      if (parentIndex != 0) {
        int grandparentIndex = getParentIndex(parentIndex);
        int uncleIndex = getRightChildIndex(grandparentIndex);
        if (uncleIndex != parentIndex
            && getLeftChildIndex(uncleIndex) >= ) {
          E uncleElement = elementData(uncleIndex);
          if (.compare(uncleElementactualLastElement) < 0) {
            [uncleIndex] = actualLastElement;
            [] = uncleElement;
            return uncleIndex;
          }
        }
      }
      return ;
    }

    
Crosses an element over to the opposite heap by moving it one level down (or up if there are no elements below it). 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)
          && (.compare(elementData(minChildIndex), x) < 0)) {
        [index] = elementData(minChildIndex);
        [minChildIndex] = x;
        return minChildIndex;
      }
      return crossOverUp(indexx);
    }

    
Fills the hole at index by moving in the least of its grandchildren to this position, then recursively filling the new hole created.

Returns:
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) {
        [index] = elementData(minGrandchildIndex);
        index = minGrandchildIndex;
      }
      return index;
    }
    private boolean verifyIndex(int i) {
      if ((getLeftChildIndex(i) < )
          && (compareElements(igetLeftChildIndex(i)) > 0)) {
        return false;
      }
      if ((getRightChildIndex(i) < )
          && (compareElements(igetRightChildIndex(i)) > 0)) {
        return false;
      }
      if ((i > 0) && (compareElements(igetParentIndex(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. 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 expectedModCount = ;
    private Queue<E> forgetMeNot;
    private List<E> skipMe;
    private E lastFromForgetMeNot;
    private boolean canRemove;
    @Override public boolean hasNext() {
      checkModCount();
      return (nextNotInSkipMe( + 1) < size())
          || (( != null) && !.isEmpty());
    }
    @Override public E next() {
      checkModCount();
      int tempCursor = nextNotInSkipMe( + 1);
      if (tempCursor < size()) {
         = tempCursor;
         = true;
        return elementData();
      } else if ( != null) {
         = size();
         = .poll();
        if ( != null) {
           = true;
          return ;
        }
      }
      throw new NoSuchElementException(
          "iterator moved past last element in queue.");
    }
    @Override public void remove() {
      checkModCount();
       = false;
      ++;
      if ( < size()) {
        MoveDesc<E> moved = removeAt();
        if (moved != null) {
          if ( == null) {
             = new ArrayDeque<E>();
             = new ArrayList<E>(3);
          }
          .add(moved.toTrickle);
          .add(moved.replaced);
        }
        --;
      } else { // we must have set lastFromForgetMeNot in next()
         = null;
      }
    }
    // Finds only this exact instance, not others that are equals()
    private boolean containsExact(Iterable<E> elements, E target) {
      for (E element : elements) {
        if (element == target) {
          return true;
        }
      }
      return false;
    }
    // Removes only this exact instance, not others that are equals()
    boolean removeExact(Object target) {
      for (int i = 0; i < i++) {
        if ([i] == target) {
          removeAt(i);
          return true;
        }
      }
      return false;
    }
    void checkModCount() {
      if ( != ) {
        throw new ConcurrentModificationException();
      }
    }

    
Returns the index of the first element after c that is not in skipMe and returns size() if there is no such element.
    private int nextNotInSkipMe(int c) {
      if ( != null) {
        while (c < size() && containsExact(elementData(c))) {
          c++;
        }
      }
      return c;
    }
  }

  
Returns an iterator over the elements contained in this collection, in no particular order.

The iterator is fail-fast: 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 java.util.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.

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 ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Returns:
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 < i++) {
      [i] = null;
    }
     = 0;
  }
  @Override public Object[] toArray() {
    Object[] copyTo = new Object[];
    System.arraycopy(, 0, copyTo, 0, );
    return copyTo;
  }

  
Returns the comparator used to order the elements in this queue. Obeys the general contract of java.util.PriorityQueue.comparator(), but returns Ordering.natural() instead of null to indicate natural ordering.
  public Comparator<? super E> comparator() {
    return .;
  }
    return .;
  }
  // Size/capacity-related methods
  private static final int DEFAULT_CAPACITY = 11;
  @VisibleForTesting static int initialQueueSize(int configuredExpectedSize,
      int maximumSizeIterable<?> initialContents) {
    // Start with what they said, if they said it, otherwise DEFAULT_CAPACITY
    int result = (configuredExpectedSize == .)
        ? 
        : configuredExpectedSize;
    // Enlarge to contain initial contents
    if (initialContents instanceof Collection) {
      int initialSize = ((Collection<?>) initialContents).size();
      result = Math.max(resultinitialSize);
    }
    // Now cap it at maxSize + 1
    return capAtMaximumSize(resultmaximumSize);
  }
  private void growIfNeeded() {
    if ( > .) {
      int newCapacity = calculateNewCapacity();
      Object[] newQueue = new Object[newCapacity];
      System.arraycopy(, 0, newQueue, 0, .);
       = newQueue;
    }
  }

  
Returns ~2x the old capacity if small; ~1.5x otherwise.
  private int calculateNewCapacity() {
    int oldCapacity = .;
    int newCapacity = (oldCapacity < 64)
        ? (oldCapacity + 1) * 2
        : IntMath.checkedMultiply(oldCapacity / 2, 3);
    return capAtMaximumSize(newCapacity);
  }

  
There's no reason for the queueSize to ever be more than maxSize + 1
  private static int capAtMaximumSize(int queueSizeint maximumSize) {
    return Math.min(queueSize - 1, maximumSize) + 1; // don't overflow
  }
New to GrepCode? Check out our FAQ X