priorityqueue.java

rule engine drools-2.0-beta-18

package org.drools.util;
/*
 * 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.
 */

import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Binary heap implementation of <code>Buffer</code> that provides for removal
 * based on <code>Comparator</code> ordering. <p/>The removal order of a
 * binary heap is based on either the natural sort order of its elements or a
 * specified {@linkComparator}. The {@link #remove()}method always returns the
 * first element as determined by the sort order. (The
 * <code>ascendingOrder</code> flag in the constructors can be used to reverse
 * the sort order, in which case {@link#remove()}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 #add(Object)}and {@link #remove()}operations perform in
 * logarithmic time. The {@link #get()}operation performs in constant time. All
 * other operations perform in linear time or worse. <p/>Note that this
 * implementation is not synchronized.
 * 
 * @author Peter Donald
 * @author Ram Chidambaram
 * @author Michael A. Smith
 * @author Paul Jack
 * @author Stephen Colebourne
 * @author <a href="mailto:[e-mail]">Simon Harris </a>
 * @version $Revision: 1.2 $ $Date: 2004/11/19 02:15:18 $
 */
public class PriorityQueue extends AbstractCollection
    implements
    Serializable
{

    /**
     * The default capacity for the buffer.
     */
    private static final int DEFAULT_CAPACITY = 13;

    /**
     * The elements in this buffer.
     */
    protected Object[] elements;

    /**
     * The number of elements currently in this buffer.
     */
    protected int size;

    /**
     * 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.
     */
    protected boolean ascendingOrder;

    /**
     * The comparator used to order the elements
     */
    protected Comparator comparator;

    // -----------------------------------------------------------------------
    /**
     * Constructs a new empty buffer that sorts in ascending order by the
     * natural order of the objects added.
     */
    public PriorityQueue()
    {
        this( DEFAULT_CAPACITY,
              true,
              null );
    }

    /**
     * Constructs a new empty buffer that sorts in ascending order using the
     * specified comparator.
     * 
     * @param comparator
     *            the comparator used to order the elements, null means use
     *            natural order
     */
    public PriorityQueue(Comparator comparator)
    {
        this( DEFAULT_CAPACITY,
              true,
              comparator );
    }

    /**
     * Constructs a new empty buffer specifying the sort order and using the
     * natural order of the objects added.
     * 
     * @param ascendingOrder
     *            if <code>true</code> the heap is created as a minimum heap;
     *            otherwise, the heap is created as a maximum heap
     */
    public PriorityQueue(boolean ascendingOrder)
    {
        this( DEFAULT_CAPACITY,
              ascendingOrder,
              null );
    }

    /**
     * Constructs a new empty buffer specifying the sort order and comparator.
     * 
     * @param ascendingOrder
     *            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 PriorityQueue(boolean ascendingOrder,
                         Comparator comparator)
    {
        this( DEFAULT_CAPACITY,
              ascendingOrder,
              comparator );
    }

    /**
     * Constructs a new empty buffer that sorts in ascending order by the
     * natural order of the objects added, specifying an initial capacity.
     * 
     * @param capacity
     *            the initial capacity for the buffer, greater than zero
     * @throws IllegalArgumentException
     *             if <code>capacity</code> is &lt;= <code>0</code>
     */
    public PriorityQueue(int capacity)
    {
        this( capacity,
              true,
              null );
    }

    /**
     * Constructs a new empty buffer that sorts in ascending order using the
     * specified comparator and initial capacity.
     * 
     * @param capacity
     *            the initial capacity for the buffer, greater than zero
     * @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 PriorityQueue(int capacity,
                         Comparator comparator)
    {
        this( capacity,
              true,
              comparator );
    }

    /**
     * Constructs a new empty buffer that specifying initial capacity and sort
     * order, using the natural order of the objects added.
     * 
     * @param capacity
     *            the initial capacity for the buffer, greater than zero
     * @param ascendingOrder
     *            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 PriorityQueue(int capacity,
                         boolean ascendingOrder)
    {
        this( capacity,
              ascendingOrder,
              null );
    }

    /**
     * Constructs a new empty buffer that specifying initial capacity, sort
     * order and comparator.
     * 
     * @param capacity
     *            the initial capacity for the buffer, greater than zero
     * @param ascendingOrder
     *            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 PriorityQueue(int capacity,
                         boolean ascendingOrder,
                         Comparator comparator)
    {
        super( );
        if ( capacity <= 0 )
        {
            throw new IllegalArgumentException( "invalid capacity" );
        }
        this.ascendingOrder = ascendingOrder;

        // +1 as 0 is noop
        this.elements = new Object[capacity + 1];
        this.comparator = comparator;
    }

    // -----------------------------------------------------------------------
    /**
     * Checks whether the heap is ascending or descending order.
     * 
     * @return true if ascending order (a min heap)
     */
    public boolean isAscendingOrder()
    {
        return ascendingOrder;
    }

    /**
     * Gets the comparator being used for this buffer, null is natural order.
     * 
     * @return the comparator in use, null is natural order
     */
    public Comparator comparator()
    {
        return comparator;
    }

    // -----------------------------------------------------------------------
    /**
     * Returns the number of elements in this buffer.
     * 
     * @return the number of elements in this buffer
     */
    public int size()
    {
        return size;
    }

    /**
     * Clears all elements from the buffer.
     */
    public void clear()
    {
        elements = new Object[elements.length]; // for gc
        size = 0;
    }

    /**
     * Adds an element to the buffer. <p/>The element added will be sorted
     * according to the comparator in use.
     * 
     * @param element
     *            the element to be added
     * @return true always
     */
    public boolean add(Object element)
    {
        if ( isAtCapacity( ) )
        {
            grow( );
        }
        // percolate element to it's place in tree
        if ( ascendingOrder )
        {
            percolateUpMinHeap( element );
        }
        else
        {
            percolateUpMaxHeap( element );
        }
        return true;
    }

    /**
     * Gets the next element to be removed without actually removing it (peek).
     * 
     * @return the next element
     * @throws NoSuchElementException
     *             if the buffer is empty
     */
    public Object get()
    {
        if ( isEmpty( ) )
        {
            throw new NoSuchElementException( );
        }
        else
        {
            return elements[1];
        }
    }

    /**
     * Gets and removes the next element (pop).
     * 
     * @return the next element
     * @throws NoSuchElementException
     *             if the buffer is empty
     */
    public Object remove()
    {
        final Object result = get( );
        elements[1] = elements[size--];

        // set the unused element to 'null' so that the garbage collector
        // can free the object if not used anywhere else.(remove reference)
        elements[size + 1] = null;