- /*
- * Copyright 2001-2004 The Apache Software Foundation
- *
- * 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 org.apache.commons.collections;
-
- import java.util.AbstractCollection;
- import java.util.Comparator;
- import java.util.Iterator;
- import java.util.NoSuchElementException;
-
- /**
- * Binary heap implementation of <code>PriorityQueue</code>.
- * <p>
- * The <code>PriorityQueue</code> interface has now been replaced for most uses
- * by the <code>Buffer</code> interface. This class and the interface are
- * retained for backwards compatibility. The intended replacement is
- * {@link org.apache.commons.collections.buffer.PriorityBuffer PriorityBuffer}.
- * <p>
- * The removal order of a binary heap is based on either the natural sort
- * order of its elements or a specified {@link Comparator}. The
- * {@link #pop()} method always returns the first element as determined
- * by the sort order. (The <code>isMinHeap</code> flag in the constructors
- * can be used to reverse the sort order, in which case {@link #pop()}
- * will always remove the last element.) The removal order is
- * <i>not</i> the same as the order of iteration; elements are
- * returned by the iterator in no particular order.
- * <p>
- * The {@link #insert(Object)} and {@link #pop()} operations perform
- * in logarithmic time. The {@link #peek()} operation performs in constant
- * time. All other operations perform in linear time or worse.
- * <p>
- * Note that this implementation is not synchronized. Use SynchronizedPriorityQueue
- * to provide synchronized access to a <code>BinaryHeap</code>:
- *
- * <pre>
- * PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());
- * </pre>
- *
- * @deprecated Replaced by PriorityBuffer in buffer subpackage.
- * Due to be removed in v4.0.
- * @since Commons Collections 1.0
- * @version $Revision: 1.24 $ $Date: 2004/02/18 01:15:42 $
- *
- * @author Peter Donald
- * @author Ram Chidambaram
- * @author Michael A. Smith
- * @author Paul Jack
- * @author Stephen Colebourne
- */
- public final class BinaryHeap extends AbstractCollection
- implements PriorityQueue, Buffer {
-
- /**
- * The default capacity for a binary heap.
- */
- private final static int DEFAULT_CAPACITY = 13;
- /**
- * The number of elements currently in this heap.
- */
- int m_size; // package scoped for testing
- /**
- * The elements in this heap.
- */
- Object[] m_elements; // package scoped for testing
- /**
- * If true, the first element as determined by the sort order will
- * be returned. If false, the last element as determined by the
- * sort order will be returned.
- */
- boolean m_isMinHeap; // package scoped for testing
- /**
- * The comparator used to order the elements
- */
- Comparator m_comparator; // package scoped for testing
-
- /**
- * Constructs a new minimum binary heap.
- */
- public BinaryHeap() {
- this(DEFAULT_CAPACITY, true);
- }
-
- /**
- * Constructs a new <code>BinaryHeap</code> that will use the given
- * comparator to order its elements.
- *
- * @param comparator the comparator used to order the elements, null
- * means use natural order
- */
- public BinaryHeap(Comparator comparator) {
- this();
- m_comparator = comparator;
- }
-
- /**
- * Constructs a new minimum binary heap with the specified initial capacity.
- *
- * @param capacity The initial capacity for the heap. This value must
- * be greater than zero.
- * @throws IllegalArgumentException
- * if <code>capacity</code> is <= <code>0</code>
- */
- public BinaryHeap(int capacity) {
- this(capacity, true);
- }
-
- /**
- * Constructs a new <code>BinaryHeap</code>.
- *
- * @param capacity the initial capacity for the heap
- * @param comparator the comparator used to order the elements, null
- * means use natural order
- * @throws IllegalArgumentException
- * if <code>capacity</code> is <= <code>0</code>
- */
- public BinaryHeap(int capacity, Comparator comparator) {
- this(capacity);
- m_comparator = comparator;
- }
-
- /**
- * Constructs a new minimum or maximum binary heap
- *
- * @param isMinHeap if <code>true</code> the heap is created as a
- * minimum heap; otherwise, the heap is created as a maximum heap
- */
- public BinaryHeap(boolean isMinHeap) {
- this(DEFAULT_CAPACITY, isMinHeap);
- }
-
- /**
- * Constructs a new <code>BinaryHeap</code>.
- *
- * @param isMinHeap true to use the order imposed by the given
- * comparator; false to reverse that order
- * @param comparator the comparator used to order the elements, null
- * means use natural order
- */
- public BinaryHeap(boolean isMinHeap, Comparator comparator) {
- this(isMinHeap);
- m_comparator = comparator;
- }
-
- /**
- * Constructs a new minimum or maximum binary heap with the specified
- * initial capacity.
- *
- * @param capacity the initial capacity for the heap. This value must
- * be greater than zero.
- * @param isMinHeap if <code>true</code> the heap is created as a
- * minimum heap; otherwise, the heap is created as a maximum heap.
- * @throws IllegalArgumentException
- * if <code>capacity</code> is <code><= 0</code>
- */
- public BinaryHeap(int capacity, boolean isMinHeap) {
- if (capacity <= 0) {
- throw new IllegalArgumentException("invalid capacity");
- }
- m_isMinHeap = isMinHeap;
-
- //+1 as 0 is noop
- m_elements = new Object[capacity + 1];
- }
-
- /**
- * Constructs a new <code>BinaryHeap</code>.
- *
- * @param capacity the initial capacity for the heap
- * @param isMinHeap true to use the order imposed by the given
- * comparator; false to reverse that order
- * @param comparator the comparator used to order the elements, null
- * means use natural order
- * @throws IllegalArgumentException
- * if <code>capacity</code> is <code><= 0</code>
- */
- public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator) {
- this(capacity, isMinHeap);
- m_comparator = comparator;
- }
-
- //-----------------------------------------------------------------------
- /**
- * Clears all elements from queue.
- */
- public void clear() {
- m_elements = new Object[m_elements.length]; // for gc
- m_size = 0;
- }
-
- /**
- * Tests if queue is empty.
- *
- * @return <code>true</code> if queue is empty; <code>false</code>
- * otherwise.
- */
- public boolean isEmpty() {
- return m_size == 0;
- }
-
- /**
- * Tests if queue is full.
- *
- * @return <code>true</code> if queue is full; <code>false</code>
- * otherwise.
- */
- public boolean isFull() {
- //+1 as element 0 is noop
- return m_elements.length == m_size + 1;
- }
-
- /**
- * Inserts an element into queue.
- *
- * @param element the element to be inserted
- */
- public void insert(Object element) {
- if (isFull()) {
- grow();
- }
- //percolate element to it's place in tree
- if (m_isMinHeap) {
- percolateUpMinHeap(element);
- } else {
- percolateUpMaxHeap(element);
- }
- }
-
- /**
- * Returns the element on top of heap but don't remove it.
- *
- * @return the element at top of heap
- * @throws NoSuchElementException if <code>isEmpty() == true</code>
- */
- public Object peek() throws NoSuchElementException {
- if (isEmpty()) {
- throw new NoSuchElementException();
- } else {
- return m_elements[1];
- }
- }
-
- /**
- * Returns the element on top of heap and remove it.
- *
- * @return the element at top of heap
- * @throws NoSuchElementException if <code>isEmpty() == true</code>
- */
- public Object pop() throws NoSuchElementException {
- final Object result = peek();
- m_elements[1] = m_elements[m_size--];
-
- // set the unused element to 'null' so that the garbage collector
- // can free the object if not used anywhere else.(remove reference)
- m_elements[m_size + 1] = null;
-
- if (m_size != 0) {
- // percolate top element to it's place in tree
- if (m_isMinHeap) {
- percolateDownMinHeap(1);
- } else {
- percolateDownMaxHeap(1);
- }
- }
-
- return result;
- }
-
- /**
- * Percolates element down heap from the position given by the index.
- * <p>
- * Assumes it is a minimum heap.
- *
- * @param index the index for the element
- */
- protected void percolateDownMinHeap(final int index) {
- final Object element = m_elements[index];
- int hole = index;
-
- while ((hole * 2) <= m_size) {
- int child = hole * 2;
-
- // if we have a right child and that child can not be percolated
- // up then move onto other child
- if (child != m_size && compare(m_elements[child + 1], m_elements[child]) < 0) {
- child++;
- }
-
- // if we found resting place of bubble then terminate search
- if (compare(m_elements[child], element) >= 0) {
- break;
- }
-
- m_elements[hole] = m_elements[child];
- hole = child;
- }
-
- m_elements[hole] = element;
- }
-
- /**
- * Percolates element down heap from the position given by the index.
- * <p>
- * Assumes it is a maximum heap.
- *
- * @param index the index of the element
- */
- protected void percolateDownMaxHeap(final int index) {
- final Object element = m_elements[index];
- int hole = index;
-
- while ((hole * 2) <= m_size) {
- int child = hole * 2;
-
- // if we have a right child and that child can not be percolated
- // up then move onto other child
- if (child != m_size && compare(m_elements[child + 1], m_elements[child]) > 0) {
- child++;
- }
-
- // if we found resting place of bubble then terminate search
- if (compare(m_elements[child], element) <= 0) {
- break;
- }
-
- m_elements[hole] = m_elements[child];
- hole = child;
- }
-
- m_elements[hole] = element;
- }
-
- /**
- * Percolates element up heap from the position given by the index.
- * <p>
- * Assumes it is a minimum heap.
- *
- * @param index the index of the element to be percolated up
- */
- protected void percolateUpMinHeap(final int index) {
- int hole = index;
- Object element = m_elements[hole];
- while (hole > 1 && compare(element, m_elements[hole / 2]) < 0) {
- // save element that is being pushed down
- // as the element "bubble" is percolated up
- final int next = hole / 2;
- m_elements[hole] = m_elements[next];
- hole = next;
- }
- m_elements[hole] = element;
- }
-
- /**
- * Percolates a new element up heap from the bottom.
- * <p>
- * Assumes it is a minimum heap.
- *
- * @param element the element
- */
- protected void percolateUpMinHeap(final Object element) {
- m_elements[++m_size] = element;
- percolateUpMinHeap(m_size);
- }
-
- /**
- * Percolates element up heap from from the position given by the index.
- * <p>
- * Assume it is a maximum heap.
- *
- * @param index the index of the element to be percolated up
- */
- protected void percolateUpMaxHeap(final int index) {
- int hole = index;
- Object element = m_elements[hole];
-
- while (hole > 1 && compare(element, m_elements[hole / 2]) > 0) {
- // save element that is being pushed down
- // as the element "bubble" is percolated up
- final int next = hole / 2;
- m_elements[hole] = m_elements[next];
- hole = next;
- }
-
- m_elements[hole] = element;
- }
-
- /**
- * Percolates a new element up heap from the bottom.
- * <p>
- * Assume it is a maximum heap.
- *
- * @param element the element
- */
- protected void percolateUpMaxHeap(final Object element) {
- m_elements[++m_size] = element;
- percolateUpMaxHeap(m_size);
- }
-
- /**
- * Compares two objects using the comparator if specified, or the
- * natural order otherwise.
- *
- * @param a the first object
- * @param b the second object
- * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
- */
- private int compare(Object a, Object b) {
- if (m_comparator != null) {
- return m_comparator.compare(a, b);
- } else {
- return ((Comparable) a).compareTo(b);
- }
- }
-
- /**
- * Increases the size of the heap to support additional elements
- */
- protected void grow() {
- final Object[] elements = new Object[m_elements.length * 2];
- System.arraycopy(m_elements, 0, elements, 0, m_elements.length);
- m_elements = elements;
- }
-
- /**
- * Returns a string representation of this heap. The returned string
- * is similar to those produced by standard JDK collections.
- *
- * @return a string representation of this heap
- */
- public String toString() {
- final StringBuffer sb = new StringBuffer();
-
- sb.append("[ ");
-
- for (int i = 1; i < m_size + 1; i++) {
- if (i != 1) {
- sb.append(", ");
- }
- sb.append(m_elements[i]);
- }
-
- sb.append(" ]");
-
- return sb.toString();
- }
-
-
- /**
- * Returns an iterator over this heap's elements.
- *
- * @return an iterator over this heap's elements
- */
- public Iterator iterator() {
- return new Iterator() {
-
- private int index = 1;
- private int lastReturnedIndex = -1;
-
- public boolean hasNext() {
- return index <= m_size;
- }
-
- public Object next() {
- if (!hasNext()) throw new NoSuchElementException();
- lastReturnedIndex = index;
- index++;
- return m_elements[lastReturnedIndex];
- }
-
- public void remove() {
- if (lastReturnedIndex == -1) {
- throw new IllegalStateException();
- }
- m_elements[ lastReturnedIndex ] = m_elements[ m_size ];
- m_elements[ m_size ] = null;
- m_size--;
- if( m_size != 0 && lastReturnedIndex <= m_size) {
- int compareToParent = 0;
- if (lastReturnedIndex > 1) {
- compareToParent = compare(m_elements[lastReturnedIndex],
- m_elements[lastReturnedIndex / 2]);
- }
- if (m_isMinHeap) {
- if (lastReturnedIndex > 1 && compareToParent < 0) {
- percolateUpMinHeap(lastReturnedIndex);
- } else {
- percolateDownMinHeap(lastReturnedIndex);
- }
- } else { // max heap
- if (lastReturnedIndex > 1 && compareToParent > 0) {
- percolateUpMaxHeap(lastReturnedIndex);
- } else {
- percolateDownMaxHeap(lastReturnedIndex);
- }
- }
- }
- index--;
- lastReturnedIndex = -1;
- }
-
- };
- }
-
-
- /**
- * Adds an object to this heap. Same as {@link #insert(Object)}.
- *
- * @param object the object to add
- * @return true, always
- */
- public boolean add(Object object) {
- insert(object);
- return true;
- }
-
- /**
- * Returns the priority element. Same as {@link #peek()}.
- *
- * @return the priority element
- * @throws BufferUnderflowException if this heap is empty
- */
- public Object get() {
- try {
- return peek();
- } catch (NoSuchElementException e) {
- throw new BufferUnderflowException();
- }
- }
-
- /**
- * Removes the priority element. Same as {@link #pop()}.
- *
- * @return the removed priority element
- * @throws BufferUnderflowException if this heap is empty
- */
- public Object remove() {
- try {
- return pop();
- } catch (NoSuchElementException e) {
- throw new BufferUnderflowException();
- }
- }
-
- /**
- * Returns the number of elements in this heap.
- *
- * @return the number of elements in this heap
- */
- public int size() {
- return m_size;
- }
-
- }