prioritybuffer.java

初级java程序员如果想要更深一步提高自己的实力

/*
 *  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.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 <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: 405927 $ $Date: 2006-05-12 23:57:03 +0100 (Fri, 12 May 2006) $
 * 
 * @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. */
    private static final long serialVersionUID = 6891186490470027896L;

    /**
     * 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 PriorityBuffer() {
        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 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.
     *
     * @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.
     *
     * @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.
     *  
     * @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.
     *
     * @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.
     *
     * @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.
     *
     * @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.
     * 
     * @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 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).
     *
     * @return the next element
     * @throws BufferUnderflowException if the buffer is empty