/*
 *  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.buffer;

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

import org.apache.commons.collections.Buffer;
import org.apache.commons.collections.BufferUnderflowException;

Binary heap implementation of Buffer that provides for
removal based on Comparator ordering.
 The removal order of a binary heap is based on either the natural sort order of its elements or a specified Comparator. The remove() method always returns the first element as determined by the sort order. (The ascendingOrder flag in the constructors can be used to reverse the sort order, in which case remove() 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 add(Object) and remove() operations perform in logarithmic time. The get() operation performs in constant time. All other operations perform in linear time or worse. 
 Note that this implementation is not synchronized. Use BufferUtils.synchronizedBuffer(Buffer) or SynchronizedBuffer.decorate(Buffer) to provide synchronized access to a PriorityBuffer:
Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());


This class is Serializable from Commons Collections 3.2.
Author:
Peter Donald, Ram Chidambaram, Michael A. Smith, Paul Jack, Stephen Colebourne, Steve Phelps
Since:
Commons Collections 3.0 (previously BinaryHeap v1.0)
Version:
$Revision: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $/**
 * 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 {@link Comparator}.  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.  Use 
 * {@link org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or
 * {@link org.apache.commons.collections.buffer.SynchronizedBuffer#decorate(Buffer)}
 * to provide synchronized access to a <code>PriorityBuffer</code>:
 * <pre>
 * Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
 * </pre>
 * <p>
 * This class is Serializable from Commons Collections 3.2.
 *
 * @since Commons Collections 3.0 (previously BinaryHeap v1.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
 * @author Steve Phelps
 */
public class PriorityBuffer extends AbstractCollection
        implements Buffer, Serializable {

    
Serialization lock. /** Serialization lock. */
    private static final long serialVersionUID = 6891186490470027896L;

    
The default capacity for the buffer.
/**
     * The default capacity for the buffer.
     */
    private static final int DEFAULT_CAPACITY = 13;
    
    
The elements in this buffer.
/**
     * The elements in this buffer.
     */
    protected Object[] elements;
    
The number of elements currently in this buffer.
/**
     * 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.
/**
     * 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
/**
     * 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.
/**
     * Constructs a new empty buffer that sorts in ascending order by the
     * natural order of the objects added.
     */
    public PriorityBuffer() {
        this(DEFAULT_CAPACITY, true, null);
    }

    
Constructs a new empty buffer that sorts in ascending order using the
specified comparator.
Params:
comparator –  the comparator used to order the elements,
 null means use natural order/**
     * 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 PriorityBuffer(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.
Params:
ascendingOrder –  if true the heap is created as a 
minimum heap; otherwise, the heap is created as a maximum heap/**
     * 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 PriorityBuffer(boolean ascendingOrder) {
        this(DEFAULT_CAPACITY, ascendingOrder, null);
    }

    
Constructs a new empty buffer specifying the sort order and comparator.
Params:
ascendingOrder –  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 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 PriorityBuffer(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.
 
Params:
capacity –  the initial capacity for the buffer, greater than zero
Throws:
IllegalArgumentException – if capacity is <= 0/**
     * 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 PriorityBuffer(int capacity) {
        this(capacity, true, null);
    }

    
Constructs a new empty buffer that sorts in ascending order using the
specified comparator and initial capacity.
Params:
capacity –  the initial capacity for the buffer, greater than zero
comparator –  the comparator used to order the elements,
 null means use natural order
Throws:
IllegalArgumentException – if capacity is <= 0/**
     * 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 PriorityBuffer(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.
Params:
capacity –  the initial capacity for the buffer, greater than zero
ascendingOrder – 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 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 PriorityBuffer(int capacity, boolean ascendingOrder) {
        this(capacity, ascendingOrder, null);
    }

    
Constructs a new empty buffer that specifying initial capacity,
sort order and comparator.
Params:
capacity –  the initial capacity for the buffer, greater than zero
ascendingOrder –  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 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 PriorityBuffer(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.
Returns:
true if ascending order (a min heap)/**
     * 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.
Returns:
the comparator in use, null is natural order/**
     * 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.
Returns:
the number of elements in this buffer/**
     * 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.
/**
     * Clears all elements from the buffer.
     */
    public void clear() {
        elements = new Object[elements.length]; // for gc
        size = 0;
    }

    
Adds an element to the buffer.

The element added will be sorted according to the comparator in use.
Params:
element –  the element to be added
Returns:
true always/**
     * 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).
Throws:
BufferUnderflowException – if the buffer is empty
Returns:
the next element/**
     * Gets the next element to be removed without actually removing it (peek).
     *
     * @return the next element
     * @throws BufferUnderflowException if the buffer is empty
     */
    public Object get() {
        if (isEmpty()) {
            throw new BufferUnderflowException();
        } else {
            return elements[1];
        }
    }

    
Gets and removes the next element (pop).
Throws:
BufferUnderflowException – if the buffer is empty
Returns:
the next element/**
     * Gets and removes the next element (pop).
     *
     * @return the next element
     * @throws BufferUnderflowException 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;

        if (size != 0) {
            // percolate top element to it's place in tree
            if (ascendingOrder) {
                percolateDownMinHeap(1);
            } else {
                percolateDownMaxHeap(1);
            }
        }

        return result;
    }

    //-----------------------------------------------------------------------
    
Tests if the buffer is at capacity.
Returns:
true if buffer is full; false otherwise./**
     * Tests if the buffer is at capacity.
     *
     * @return <code>true</code> if buffer is full; <code>false</code> otherwise.
     */
    protected boolean isAtCapacity() {
        //+1 as element 0 is noop
        return elements.length == size + 1;
    }

    
    
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 = elements[index];
        int hole = index;

        while ((hole * 2) <= 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 != size && compare(elements[child + 1], elements[child]) < 0) {
                child++;
            }

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

            elements[hole] = elements[child];
            hole = child;
        }

        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 = elements[index];
        int hole = index;

        while ((hole * 2) <= 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 != size && compare(elements[child + 1], elements[child]) > 0) {
                child++;
            }

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

            elements[hole] = elements[child];
            hole = child;
        }

        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 = elements[hole];
        while (hole > 1 && compare(element, elements[hole / 2]) < 0) {
            // save element that is being pushed down
            // as the element "bubble" is percolated up
            final int next = hole / 2;
            elements[hole] = elements[next];
            hole = next;
        }
        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) {
        elements[++size] = element;
        percolateUpMinHeap(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 = elements[hole];

        while (hole > 1 && compare(element, elements[hole / 2]) > 0) {
            // save element that is being pushed down
            // as the element "bubble" is percolated up
            final int next = hole / 2;
            elements[hole] = elements[next];
            hole = next;
        }

        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) {
        elements[++size] = element;
        percolateUpMaxHeap(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
     */
    protected int compare(Object a, Object b) {
        if (comparator != null) {
            return 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[] array = new Object[elements.length * 2];
        System.arraycopy(elements, 0, array, 0, elements.length);
        elements = array;
    }

    //-----------------------------------------------------------------------
    
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 <= size;
            }

            public Object next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                lastReturnedIndex = index;
                index++;
                return elements[lastReturnedIndex];
            }

            public void remove() {
                if (lastReturnedIndex == -1) {
                    throw new IllegalStateException();
                }
                elements[ lastReturnedIndex ] = elements[ size ];
                elements[ size ] = null;
                size--;  
                if( size != 0 && lastReturnedIndex <= size) {
                    int compareToParent = 0;
                    if (lastReturnedIndex > 1) {
                        compareToParent = compare(elements[lastReturnedIndex], 
                            elements[lastReturnedIndex / 2]);  
                    }
                    if (ascendingOrder) {
                        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; 
            }

        };
    }

    
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 < size + 1; i++) {
            if (i != 1) {
                sb.append(", ");
            }
            sb.append(elements[i]);
        }

        sb.append(" ]");

        return sb.toString();
    }

}