/*
 * Copyright (C) The Apache Software Foundation. All rights reserved.
 *
 * This software is published under the terms of the Apache Software License
 * version 1.1, a copy of which has been included with this distribution in
 * the LICENSE file.
 */
package org.apache.avalon.excalibur.collections;

import java.util.Comparator;
import java.util.NoSuchElementException;

/**
 * Iterface for priority queues.
 * This interface does not dictate whether it is min or max heap.
 *
 * @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
 * @author <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
 * @version CVS $Revision: 1.2 $ $Date: 2001/08/07 10:57:04 $
 * @since 4.0
 */
public final class BinaryHeap
    implements PriorityQueue
{

	public final static class MinComparator
	extends Object
	implements Comparator
	{
		public final int compare(final Object lhs, final Object rhs)
		{
			return ((Comparable)lhs).compareTo(rhs);
		}
	}

	public final static class MaxComparator
	extends Object
	implements Comparator
	{
		public final int compare(final Object lhs, final Object rhs)
		{
			return ((Comparable)rhs).compareTo(lhs);
		}
	}

    public static final Comparator	MIN_COMPARATOR = new MinComparator();
    public static final Comparator	MAX_COMPARATOR = new MaxComparator();
    private static final int      	DEFAULT_CAPACITY   = 13;
    private static final Comparator	DEFAULT_COMPARATOR = MIN_COMPARATOR;
    private int                   	m_size;
    private Object[]         	 	m_elements;
    private Comparator              m_comparator;

	/**
	 * Instantiates a new min binary heap with the default initial capacity.
	 */
    public BinaryHeap()
    {
        this( DEFAULT_CAPACITY, DEFAULT_COMPARATOR );
    }

	/**
	 * Instantiates a new min binary heap with the given initial capacity.
	 */
    public BinaryHeap( final int capacity )
    {
        this( capacity, DEFAULT_COMPARATOR );
    }

	/**
	 * Instantiates a new binary heap with the default initial capacity and
	 * ordered using the given Comparator.
	 */
	public BinaryHeap( final Comparator comparator )
	{
        this( DEFAULT_CAPACITY, comparator );
	}

	/**
	 * Instantiates a new binary heap with the given initial capacity and
	 * ordered using the given Comparator.
	 */
	public BinaryHeap( final int capacity, final Comparator comparator )
	{
		m_elements = new Object[ capacity + 1 ];
		m_comparator = comparator;
	}

    /**
     * Clear all elements from queue.
     */
    public void clear()
    {
        m_size = 0;
    }

    /**
     * Test if queue is empty.
     *
     * @return true if queue is empty else false.
     */
    public boolean isEmpty()
    {
        return ( 0 == m_size );
    }

    /**
     * Test if queue is full.
     *
     * @return true if queue is full else false.
     */
    public boolean isFull()
    {
        //+1 as element 0 is noop
        return ( m_elements.length == m_size+1 );
    }

    /**
     * Insert an element into queue.
     *
     * @param element the element to be inserted
     */
    public void insert( final Object element )
    {
        if( isFull() )
        {
            grow();
        }

		percolateUpHeap( element );
    }

    /**
     * Return element on top of heap but don't remove it.
     *
     * @return the element at top of heap
     * @exception NoSuchElementException if isEmpty() == true
     */
    public Object peek() throws NoSuchElementException
    {
        if( isEmpty() )
        {
            throw new NoSuchElementException();
        }
        else
        {
            return m_elements[ 1 ];
        }
    }

    /**
     * Return element on top of heap and remove it.
     *
     * @return the element at top of heap
     * @exception NoSuchElementException if isEmpty() == true
     */
    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 )
        {
			percolateDownHeap( 1 );
        }

        return result;
    }

    /**
     * Percolate element down heap from top.
     *
     * @param element the element
     */
    protected void percolateDownHeap( final int index )
    {
        final Object element = m_elements[ index ];

        int hole = index;
        int child = hole << 1;

        while( child <= m_size )
        {
            //if we have a right child and that child can not be percolated
            //up then move onto other child
            if( child != m_size &&
                m_comparator.compare( m_elements[ child + 1 ], m_elements[ child ] ) < 0 )
            {
                child++;
            }

            //if we found resting place of bubble then terminate search
            if( m_comparator.compare( m_elements[ child ], element ) >= 0 )
            {
                break;
            }

            m_elements[ hole ] = m_elements[ child ];
            hole = child;
            child = hole << 1;
        }

        m_elements[ hole ] = element;
    }

    /**
     * Percolate element up heap from bottom.
     *
     * @param element the element
     */
    protected void percolateUpHeap( final Object element )
    {
        int hole = ++m_size;
		int next = hole >> 1;

        m_elements[ hole ] = element;

        while( hole > 1 &&
               m_comparator.compare( element, m_elements[ next ] ) < 0 )
        {
            m_elements[ hole ] = m_elements[ next ];
            hole = next;
            next = hole >> 1;
        }

        m_elements[ hole ] = element;
    }

    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;
    }

    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();
    }
}