/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You 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 PriorityQueue.

The PriorityQueue interface has now been replaced for most uses
by the Buffer interface. This class and the interface are retained for backwards compatibility. The intended replacement is PriorityBuffer. 
 The removal order of a binary heap is based on either the natural sort order of its elements or a specified Comparator. The pop() method always returns the first element as determined by the sort order. (The isMinHeap flag in the constructors can be used to reverse the sort order, in which case pop() will always remove the last element.) The removal order is not the same as the order of iteration; elements are
returned by the iterator in no particular order.
 The insert(Object) and pop() operations perform in logarithmic time. The peek() operation performs in constant time. All other operations perform in linear time or worse. 

Note that this implementation is not synchronized.  Use SynchronizedPriorityQueue
to provide synchronized access to a BinaryHeap:
PriorityQueue heap = new SynchronizedPriorityQueue(new BinaryHeap());

Author:
Peter Donald, Ram Chidambaram, Michael A. Smith, Paul Jack, Stephen Colebourne
Deprecated:
Replaced by PriorityBuffer in buffer subpackage.
 Due to be removed in v4.0.
Since:
Commons Collections 1.0
Version:
$Revision: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $/**
 * 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: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $
 * 
 * @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.
/**
     * The default capacity for a binary heap.
     */
    private final static int DEFAULT_CAPACITY = 13;
    
The number of elements currently in this heap.
/**
     * The number of elements currently in this heap.
     */
    int m_size;  // package scoped for testing
    
The elements in this heap.
/**
     * 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.
/**
     * 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
/**
     * The comparator used to order the elements
     */
    Comparator m_comparator;  // package scoped for testing

    
Constructs a new minimum binary heap.
/**
     * Constructs a new minimum binary heap.
     */
    public BinaryHeap() {
        this(DEFAULT_CAPACITY, true);
    }

    
Constructs a new BinaryHeap that will use the given
comparator to order its elements.
Params:
comparator –  the comparator used to order the elements, null
 means use natural order/**
     * 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.
 
Params:
capacity –  The initial capacity for the heap.  This value must
 be greater than zero.
Throws:
IllegalArgumentException –  
 if capacity is <= 0/**
     * 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 &lt;= <code>0</code>
     */
    public BinaryHeap(int capacity) {
        this(capacity, true);
    }

    
Constructs a new BinaryHeap.
Params:
capacity –  the initial capacity for the heap
comparator –  the comparator used to order the elements, null
 means use natural order
Throws:
IllegalArgumentException –  
 if capacity is <= 0/**
     * 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 &lt;= <code>0</code>
     */
    public BinaryHeap(int capacity, Comparator comparator) {
        this(capacity);
        m_comparator = comparator;
    }

    
Constructs a new minimum or maximum binary heap
Params:
isMinHeap –  if true the heap is created as a 
minimum heap; otherwise, the heap is created as a maximum heap/**
     * 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 BinaryHeap.
Params:
isMinHeap –  true to use the order imposed by the given 
  comparator; false to reverse that order
comparator –  the comparator used to order the elements, null
 means use natural order/**
     * 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.
Params:
capacity – the initial capacity for the heap.  This value must 
be greater than zero.
isMinHeap – if true the heap is created as a 
 minimum heap; otherwise, the heap is created as a maximum heap.
Throws:
IllegalArgumentException – 
 if capacity is <= 0/**
     * 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>&lt;= 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 BinaryHeap.
Params:
capacity –  the initial capacity for the heap
isMinHeap –  true to use the order imposed by the given 
  comparator; false to reverse that order
comparator –  the comparator used to order the elements, null
 means use natural order
Throws:
IllegalArgumentException – 
 if capacity is <= 0/**
     * 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>&lt;= 0</code>
     */
    public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator) {
        this(capacity, isMinHeap);
        m_comparator = comparator;
    }

    //-----------------------------------------------------------------------
    
Clears all elements from queue.
/**
     * 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.
Returns:
true if queue is empty; false 
 otherwise./**
     * 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.
Returns:
true if queue is full; false
 otherwise./**
     * 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.
Params:
element –  the element to be inserted/**
     * 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.
Throws:
NoSuchElementException –  if isEmpty() == true
Returns:
the element at top of heap/**
     * 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.
Throws:
NoSuchElementException –  if isEmpty() == true
Returns:
the element at top of heap/**
     * 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.

Assumes it is a minimum heap.
Params:
index – the index for the element/**
     * 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.

Assumes it is a maximum heap.
Params:
index – the index of the 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.

Assumes it is a minimum heap.
Params:
index – the index of the element to be percolated up/**
     * 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.

Assumes it is a minimum heap.
Params:
element – the 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.

Assume it is a maximum heap.
Params:
index – the index of the element to be percolated up/**
     * 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.

Assume it is a maximum heap.
Params:
element – the 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.
Params:
a –  the first object
b –  the second object
Returns:
-ve if a less than b, 0 if they are equal, +ve if a greater than b/**
     * 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
/**
     * 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.
Returns:
a string representation of this heap/**
     * 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.
Returns:
an iterator over this heap's elements/**
     * 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 insert(Object). 
Params:
object –  the object to add
Returns:
true, always/**
     * 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 peek(). 
Throws:
BufferUnderflowException – if this heap is empty
Returns:
the priority element/**
     * 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 pop(). 
Throws:
BufferUnderflowException – if this heap is empty
Returns:
the removed priority element/**
     * 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.
Returns:
the number of elements in this heap/**
     * Returns the number of elements in this heap.
     *
     * @return the number of elements in this heap
     */
    public int size() {
        return m_size;
    }

}