commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From scolebou...@apache.org
Subject cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections UnboundedFifoBuffer.java BoundedFifoBuffer.java BinaryHeap.java
Date Sun, 13 Oct 2002 12:59:04 GMT
scolebourne    2002/10/13 05:59:04

  Modified:    collections/src/java/org/apache/commons/collections
                        UnboundedFifoBuffer.java BoundedFifoBuffer.java
                        BinaryHeap.java
  Log:
  Tidy javadoc and code layout
  
  Revision  Changes    Path
  1.5       +105 -98   jakarta-commons/collections/src/java/org/apache/commons/collections/UnboundedFifoBuffer.java
  
  Index: UnboundedFifoBuffer.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/UnboundedFifoBuffer.java,v
  retrieving revision 1.4
  retrieving revision 1.5
  diff -u -r1.4 -r1.5
  --- UnboundedFifoBuffer.java	12 Oct 2002 22:15:18 -0000	1.4
  +++ UnboundedFifoBuffer.java	13 Oct 2002 12:59:04 -0000	1.5
  @@ -64,85 +64,78 @@
   import java.util.AbstractCollection;
   import java.util.Iterator;
   import java.util.NoSuchElementException;
  -
  -
   /**
    * UnboundedFifoBuffer is a <strong>very</strong> efficient buffer implementation.
    * According to performance testing, it exhibits a constant access time, but it
    * also outperforms ArrayList when used for the same purpose.
  - * <P>
  - * The removal order of an <Code>UnboundedFifoBuffer</Code> is based on the
insertion
  + * <p>
  + * The removal order of an <code>UnboundedFifoBuffer</code> is based on the
insertion
    * order; elements are removed in the same order in which they were added.
  - * The iteration order is the same as the removal order.<P>
  - *
  + * The iteration order is the same as the removal order.
  + * <p>
    * The {@link #remove()} and {@link #get()} operations perform in constant time.
    * The {@link #add(Object)} operation performs in amortized constant time.  All
  - * other operations perform in linear time or worse.<P>
  - *
  + * other operations perform in linear time or worse.
  + * <p>
    * Note that this implementation is not synchronized.  The following can be
  - * used to provide synchronized access to your <COde>BoundedFifo</Code>:
  - *
  - * <Pre>
  - *   Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifo());
  - * </Pre>
  + * used to provide synchronized access to your <code>UnboundedFifo</code>:
  + * <pre>
  + *   Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifo());
  + * </pre>
  + * <p>
  + * This buffer prevents null objects from being added.
    *
  + * @author Avalon
    * @author  <a href="fede@apache.org">Federico Barbieri</a>
    * @author  <a href="bloritsch@apache.org">Berin Loritsch</a>
    * @author Paul Jack
  - * @version CVS $Revision$ $Date$
  - * @since Avalon 4.0
  + * @author Stephen Colebourne
  + * @since 2.1
  + * @version $Id$
    */
  -public final class UnboundedFifoBuffer extends AbstractCollection implements Buffer
  -{
  +public final class UnboundedFifoBuffer extends AbstractCollection implements Buffer {
       protected Object[] m_buffer;
       protected int m_head;
       protected int m_tail;
   
       /**
  -     * Initialize the UnboundedFifoBuffer with the specified number of elements.  The
  -     * integer must be a positive integer.
  -     */
  -    public UnboundedFifoBuffer( int size )
  -    {
  -        m_buffer = new Object[ size + 1 ];
  -        m_head = 0;
  -        m_tail = 0;
  -    }
  -
  -    /**
  -     * Initialize the UnboundedFifoBuffer with the default number of elements.  It is
  -     * exactly the same as performing the following:
  +     * Constructs an UnboundedFifoBuffer with the default number of elements.
  +     * It is exactly the same as performing the following:
        *
        * <pre>
  -     *   new UnboundedFifoBuffer( 32 );
  +     *   new UnboundedFifoBuffer(32);
        * </pre>
        */
  -    public UnboundedFifoBuffer()
  -    {
  -        this( 32 );
  +    public UnboundedFifoBuffer() {
  +        this(32);
       }
   
       /**
  -     * Tests to see if the CircularBuffer is empty.
  +     * Constructs an UnboundedFifoBuffer with the specified number of elements.
  +     * The integer must be a positive integer.
  +     * 
  +     * @throws IllegalArgumentException  if the size is less than 1
        */
  -    public final boolean isEmpty()
  -    {
  -        return ( size() == 0 );
  +    public UnboundedFifoBuffer(int size) {
  +        if (size <= 0) {
  +            throw new IllegalArgumentException("The size must be greater than 0");
  +        }
  +        m_buffer = new Object[size + 1];
  +        m_head = 0;
  +        m_tail = 0;
       }
   
       /**
        * Returns the number of elements stored in the buffer.
  +     *
  +     * @return this buffer's size
        */
  -    public int size()
  -    {
  +    public int size() {
           int size = 0;
   
  -        if( m_tail < m_head )
  -        {
  +        if (m_tail < m_head) {
               size = m_buffer.length - m_head + m_tail;
  -        }
  -        else
  -        {
  +        } else {
               size = m_tail - m_head;
           }
   
  @@ -150,29 +143,38 @@
       }
   
       /**
  -     * Add an object into the buffer
  +     * Returns true if this buffer is empty; false otherwise.
  +     *
  +     * @return true if this buffer is empty
        */
  -    public boolean add( final Object o )
  -    {
  -        if( null == o )
  -        {
  -            throw new NullPointerException( "Attempted to add null object to buffer" );
  +    public boolean isEmpty() {
  +        return (size() == 0);
  +    }
  +
  +    /**
  +     * Adds the given element to this buffer.
  +     *
  +     * @param element  the element to add
  +     * @return true, always
  +     * @throws NullPointerException  if the given element is null
  +     * @throws BufferOverflowException  if this buffer is full
  +     */
  +    public boolean add(final Object o) {
  +        if (null == o) {
  +            throw new NullPointerException("Attempted to add null object to buffer");
           }
   
  -        if( size() + 1 >= m_buffer.length )
  -        {
  -            Object[] tmp = new Object[ ( ( m_buffer.length - 1 ) * 2 ) + 1 ];
  +        if (size() + 1 >= m_buffer.length) {
  +            Object[] tmp = new Object[((m_buffer.length - 1) * 2) + 1];
   
               int j = 0;
  -            for( int i = m_head; i != m_tail; )
  -            {
  -                tmp[ j ] = m_buffer[ i ];
  -                m_buffer[ i ] = null;
  +            for (int i = m_head; i != m_tail;) {
  +                tmp[j] = m_buffer[i];
  +                m_buffer[i] = null;
   
                   j++;
                   i++;
  -                if( i == m_buffer.length )
  -                {
  +                if (i == m_buffer.length) {
                       i = 0;
                   }
               }
  @@ -182,10 +184,9 @@
               m_tail = j;
           }
   
  -        m_buffer[ m_tail ] = o;
  +        m_buffer[m_tail] = o;
           m_tail++;
  -        if( m_tail >= m_buffer.length )
  -        {
  +        if (m_tail >= m_buffer.length) {
               m_tail = 0;
           }
           return true;
  @@ -195,41 +196,34 @@
        * Returns the next object in the buffer.
        *
        * @return the next object in the buffer
  -     * @throws BufferUnderflowException if this buffer is empty
  +     * @throws BufferUnderflowException  if this buffer is empty
        */
  -    public Object get()
  -    {
  -        if( isEmpty() )
  -        {
  -            throw new BufferUnderflowException( "The buffer is already empty" );
  +    public Object get() {
  +        if (isEmpty()) {
  +            throw new BufferUnderflowException("The buffer is already empty");
           }
   
  -        return m_buffer[ m_head ];
  +        return m_buffer[m_head];
       }
   
  -
       /**
        * Removes the next object from the buffer
        *
        * @return the removed object
  -     * @throws BufferUnderflowException if this buffer is empty
  +     * @throws BufferUnderflowException  if this buffer is empty
        */
  -    public Object remove()
  -    {
  -        if( isEmpty() )
  -        {
  -            throw new BufferUnderflowException( "The buffer is already empty" );
  +    public Object remove() {
  +        if (isEmpty()) {
  +            throw new BufferUnderflowException("The buffer is already empty");
           }
   
  -        Object element = m_buffer[ m_head ];
  +        Object element = m_buffer[m_head];
   
  -        if( null != element )
  -        {
  -            m_buffer[ m_head ] = null;
  +        if (null != element) {
  +            m_buffer[m_head] = null;
   
               m_head++;
  -            if( m_head >= m_buffer.length )
  -            {
  +            if (m_head >= m_buffer.length) {
                   m_head = 0;
               }
           }
  @@ -237,25 +231,36 @@
           return element;
       }
   
  -
  +    /**
  +     * Increments the internal index.
  +     * 
  +     * @param index  the index to increment
  +     * @return the updated index
  +     */
       private int increment(int index) {
  -        index++; 
  -        if (index >= m_buffer.length) index = 0;
  +        index++;
  +        if (index >= m_buffer.length)
  +            index = 0;
           return index;
       }
   
  -
  +    /**
  +     * Decrements the internal index.
  +     * 
  +     * @param index  the index to decrement
  +     * @return the updated index
  +     */
       private int decrement(int index) {
           index--;
  -        if (index < 0) index = m_buffer.length - 1;
  +        if (index < 0)
  +            index = m_buffer.length - 1;
           return index;
       }
   
  -
       /**
  -     *  Returns an iterator over this fifo's elements.
  +     * Returns an iterator over this buffer's elements.
        *
  -     *  @return an iterator over this fifo's elements
  +     * @return an iterator over this buffer's elements
        */
       public Iterator iterator() {
           return new Iterator() {
  @@ -265,18 +270,20 @@
   
               public boolean hasNext() {
                   return index != m_tail;
  -                
  +
               }
   
               public Object next() {
  -                if (!hasNext()) throw new NoSuchElementException();
  +                if (!hasNext())
  +                    throw new NoSuchElementException();
                   lastReturnedIndex = index;
                   index = increment(index);
                   return m_buffer[lastReturnedIndex];
               }
   
               public void remove() {
  -                if (lastReturnedIndex == -1) throw new IllegalStateException();
  +                if (lastReturnedIndex == -1)
  +                    throw new IllegalStateException();
   
                   // First element can be removed quickly
                   if (lastReturnedIndex == m_head) {
  @@ -305,6 +312,6 @@
   
           };
       }
  -
  +    
   }
   
  
  
  
  1.5       +108 -121  jakarta-commons/collections/src/java/org/apache/commons/collections/BoundedFifoBuffer.java
  
  Index: BoundedFifoBuffer.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/BoundedFifoBuffer.java,v
  retrieving revision 1.4
  retrieving revision 1.5
  diff -u -r1.4 -r1.5
  --- BoundedFifoBuffer.java	13 Aug 2002 00:46:25 -0000	1.4
  +++ BoundedFifoBuffer.java	13 Oct 2002 12:59:04 -0000	1.5
  @@ -60,192 +60,177 @@
    */
   package org.apache.commons.collections;
   
  -
   import java.util.AbstractCollection;
   import java.util.Arrays;
   import java.util.Collection;
   import java.util.Iterator;
   import java.util.NoSuchElementException;
  -
  -
   /**
    * The BoundedFifoBuffer is a <strong>very</strong> efficient implementation
of
  - * Buffer that does not alter the size of the buffer at runtime.<P>
  - *
  - * The removal order of a <Code>BoundedFifoBuffer</Code> is based on the 
  + * Buffer that does not alter the size of the buffer at runtime.
  + * <p>
  + * The removal order of a <code>BoundedFifoBuffer</code> is based on the 
    * insertion order; elements are removed in the same order in which they
  - * were added.  The iteration order is the same as the removal order.<P>
  - *
  + * were added.  The iteration order is the same as the removal order.
  + * <p>
    * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
    * all perform in constant time.  All other operations perform in linear
    * time or worse.
  - *
  + * <p>
    * Note that this implementation is not synchronized.  The following can be
  - * used to provide synchronized access to your <COde>BoundedFifoBuffer</Code>:
  - *
  - * <Pre>
  + * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
  + * <pre>
    *   Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
  - * </Pre>
  + * </pre>
  + * <p>
  + * This buffer prevents null objects from being added.
    *
  + * @author Avalon
    * @author <a href="mailto:bloritsch@apache.org">Berin Loritsch</a>
    * @author Paul Jack
  + * @author Stephen Colebourne
  + * @since 2.1
    * @version $Id$
  - * @since Avalon 4.0
    */
  -public class BoundedFifoBuffer extends AbstractCollection implements Buffer
  -{
  +public class BoundedFifoBuffer extends AbstractCollection implements Buffer {
       private final Object[] m_elements;
       private int m_start = 0;
       private int m_end = 0;
       private boolean m_full = false;
   
  -
       /**
  -     *  Constructs a new <Code>BoundedFifoBuffer</Code> big enough to hold
  -     *  the specified number of elements.
  -     *
  -     *  @param size  the maximum number of elements for this fifo
  +     * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
  +     * 32 elements.
        */
  -    public BoundedFifoBuffer( int size )
  -    {
  -        m_elements = new Object[ size ];
  +    public BoundedFifoBuffer() {
  +        this(32);
       }
   
  -
       /**
  -     *  Constructs a new <Code>BoundedFifoBuffer</Code> big enough to hold
  -     *  32 elements.
  +     * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
  +     * the specified number of elements.
  +     *
  +     * @param size  the maximum number of elements for this fifo
  +     * @throws IllegalArgumentException  if the size is less than 1
        */
  -    public BoundedFifoBuffer()
  -    {
  -        this( 32 );
  +    public BoundedFifoBuffer(int size) {
  +        if (size <= 0) {
  +            throw new IllegalArgumentException("The size must be greater than 0");
  +        }
  +        m_elements = new Object[size];
       }
   
  -
       /**
  -     *  Constructs a new <Code>BoundedFifoBuffer</Code> big enough to hold
all
  -     *  of the elements in the specified collection.  That collection's
  -     *  elements will also be added to the fifo.
  +     * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
  +     * of the elements in the specified collection. That collection's
  +     * elements will also be added to the buffer.
        *
  -     *  @param c  the collection whose elements to add
  +     * @param coll  the collection whose elements to add
        */
  -    public BoundedFifoBuffer(Collection c) {
  -        this(c.size());
  -        addAll(c);
  +    public BoundedFifoBuffer(Collection coll) {
  +        this(coll.size());
  +        addAll(coll);
       }
   
  -
       /**
  -     *  Returns this fifo's size.
  +     * Returns the number of elements stored in the buffer.
        *
  -     *  @return this fifo's size
  +     * @return this buffer's size
        */
  -    public int size()
  -    {
  +    public int size() {
           int size = 0;
   
  -        if( m_end < m_start )
  -        {
  +        if (m_end < m_start) {
               size = m_elements.length - m_start + m_end;
  -        }
  -        else if( m_end == m_start )
  -        {
  -            size = ( m_full ? m_elements.length : 0 );
  -        }
  -        else
  -        {
  +        } else if (m_end == m_start) {
  +            size = (m_full ? m_elements.length : 0);
  +        } else {
               size = m_end - m_start;
           }
   
           return size;
       }
   
  -
       /**
  -     *  Returns true if this fifo is empty; false otherwise.
  +     * Returns true if this buffer is empty; false otherwise.
        *
  -     *  @return true if this fifo is empty
  +     * @return true if this buffer is empty
        */
  -    public boolean isEmpty()
  -    {
  +    public boolean isEmpty() {
           return size() == 0;
       }
   
  +    /**
  +     * Clears this buffer.
  +     */
  +    public void clear() {
  +        m_full = false;
  +        m_start = 0;
  +        m_end = 0;
  +        Arrays.fill(m_elements, null);
  +    }
   
       /**
  -     *  Adds the given element to this fifo.
  +     * Adds the given element to this buffer.
        *
  -     *  @param element  the element to add
  -     *  @return true, always
  -     *  @throws NullPointerException if the given element is null
  -     *  @throws BufferOverflowException if this fifo is full
  +     * @param element  the element to add
  +     * @return true, always
  +     * @throws NullPointerException  if the given element is null
  +     * @throws BufferOverflowException  if this buffer is full
        */
  -    public boolean add( Object element )
  -    {
  -        if( null == element )
  -        {
  -            throw new NullPointerException( "Attempted to add null object to buffer" );
  +    public boolean add(Object element) {
  +        if (null == element) {
  +            throw new NullPointerException("Attempted to add null object to buffer");
           }
   
  -        if( m_full )
  -        {
  -            throw new BufferOverflowException( "The buffer cannot hold more than "
  -                                               + m_elements.length + " objects." );
  +        if (m_full) {
  +            throw new BufferOverflowException("The buffer cannot hold more than " + m_elements.length
+ " objects.");
           }
   
  -        m_elements[ m_end++ ] = element;
  +        m_elements[m_end++] = element;
   
  -        if( m_end >= m_elements.length )
  -        {
  +        if (m_end >= m_elements.length) {
               m_end = 0;
           }
   
  -        if( m_end == m_start )
  -        {
  +        if (m_end == m_start) {
               m_full = true;
           }
   
           return true;
       }
   
  -
       /**
  -     *  Returns the least recently inserted element in this fifo.
  +     * Returns the least recently inserted element in this buffer.
        *
  -     *  @return the least recently inserted element
  -     *  @throws BufferUnderflowException if the fifo is empty
  +     * @return the least recently inserted element
  +     * @throws BufferUnderflowException  if the buffer is empty
        */
       public Object get() {
  -        if( isEmpty() )
  -        {
  -            throw new BufferUnderflowException( "The buffer is already empty" );
  +        if (isEmpty()) {
  +            throw new BufferUnderflowException("The buffer is already empty");
           }
   
  -        return m_elements[ m_start ];
  +        return m_elements[m_start];
       }
   
  -
       /**
  -     *  Removes the least recently inserted element from this fifo.
  +     * Removes the least recently inserted element from this buffer.
        *
  -     *  @return the least recently inserted element
  -     *  @throws BufferUnderflowException if the fifo is empty
  +     * @return the least recently inserted element
  +     * @throws BufferUnderflowException  if the buffer is empty
        */
  -    public Object remove()
  -    {
  -        if( isEmpty() )
  -        {
  -            throw new BufferUnderflowException( "The buffer is already empty" );
  +    public Object remove() {
  +        if (isEmpty()) {
  +            throw new BufferUnderflowException("The buffer is already empty");
           }
   
  -        Object element = m_elements[ m_start ];
  +        Object element = m_elements[m_start];
   
  -        if( null != element )
  -        {
  -            m_elements[ m_start++ ] = null;
  +        if (null != element) {
  +            m_elements[m_start++] = null;
   
  -            if( m_start >= m_elements.length )
  -            {
  +            if (m_start >= m_elements.length) {
                   m_start = 0;
               }
   
  @@ -255,25 +240,38 @@
           return element;
       }
   
  -
  +    /**
  +     * Increments the internal index.
  +     * 
  +     * @param index  the index to increment
  +     * @return the updated index
  +     */
       private int increment(int index) {
           index++; 
  -        if (index >= m_elements.length) index = 0;
  +        if (index >= m_elements.length) {
  +            index = 0;
  +        }
           return index;
       }
   
  -
  +    /**
  +     * Decrements the internal index.
  +     * 
  +     * @param index  the index to decrement
  +     * @return the updated index
  +     */
       private int decrement(int index) {
           index--;
  -        if (index < 0) index = m_elements.length - 1;
  +        if (index < 0) {
  +            index = m_elements.length - 1;
  +        }
           return index;
       }
   
  -
       /**
  -     *  Returns an iterator over this fifo's elements.
  +     * Returns an iterator over this buffer's elements.
        *
  -     *  @return an iterator over this fifo's elements
  +     * @return an iterator over this buffer's elements
        */
       public Iterator iterator() {
           return new Iterator() {
  @@ -325,17 +323,6 @@
               }
   
           };
  -    }
  -
  -
  -    /**
  -     *  Clears this fifo.
  -     */
  -    public void clear() {
  -        m_full = false;
  -        m_start = 0;
  -        m_end = 0;
  -        Arrays.fill(m_elements, null);
       }
   
   }
  
  
  
  1.11      +219 -243  jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java
  
  Index: BinaryHeap.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/BinaryHeap.java,v
  retrieving revision 1.10
  retrieving revision 1.11
  diff -u -r1.10 -r1.11
  --- BinaryHeap.java	15 Aug 2002 20:04:31 -0000	1.10
  +++ BinaryHeap.java	13 Oct 2002 12:59:04 -0000	1.11
  @@ -64,425 +64,413 @@
   import java.util.Iterator;
   import java.util.NoSuchElementException;
   import java.util.Comparator;
  -
   /**
    * Binary heap implementation of {@link PriorityQueue} and {@link Buffer}.
  - *
  + * <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>isMinHeap</Code> flag in the constructors
  + * by the sort order.  (The <code>isMinHeap</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>
  - *
  + * <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>
  - *
  + * time.  All other operations perform in linear time or worse.
  + * <p>
    * Note that this implementation is not synchronized.  Use 
    * {@link BufferUtils#synchronizedBuffer(Buffer)} to provide
  - * synchronized access to a <Code>BinaryHeap</Code>:
  + * synchronized access to a <code>BinaryHeap</code>:
    *
  - * <Pre>
  + * <pre>
    * Buffer heap = BufferUtils.synchronizedBuffer(new BinaryHeap());
  - * </Pre>
  + * </pre>
    *
  + * @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
  + * @author <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
  + * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
  + * @author Paul Jack
  + * @author Stephen Colebourne
    * @since 1.0
  - * @author  <a href="mailto:donaldp@apache.org">Peter Donald</a>
  - * @author  <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
  - * @author  <a href="mailto:mas@apache.org">Michael A. Smith</a>
  - * @author  Paul Jack
  + * @version $Id$
    */
   public final class BinaryHeap extends AbstractCollection
  -    implements PriorityQueue, Buffer
  -{
  +        implements PriorityQueue, Buffer {
   
       /**
  -     *  The default capacity for a binary heap.
  +     * The default capacity for a binary heap.
        */
  -    protected final static int      DEFAULT_CAPACITY   = 13;
  -
  +    private final static int DEFAULT_CAPACITY = 13;
       /**
  -     *  The number of elements currently in this heap.
  +     * The number of elements currently in this heap.
        */
  -    protected int                   m_size;
  -
  +    int m_size;  // package scoped for testing
       /**
  -     *  The elements in this heap.
  +     * The elements in this heap.
        */
  -    protected Object[]              m_elements;
  -
  +    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 determiend 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               m_isMinHeap;
  -    private Comparator              m_comparator;
  +    boolean m_isMinHeap;  // package scoped for testing
  +    /**
  +     * The comparator used to order the elements
  +     */
  +    Comparator m_comparator;  // package scoped for testing
   
       /**
  -     *  Create a new minimum binary heap.
  +     * Constructs a new minimum binary heap.
        */
  -    public BinaryHeap()
  -    {
  -        this( DEFAULT_CAPACITY, true );
  +    public BinaryHeap() {
  +        this(DEFAULT_CAPACITY, true);
       }
   
       /**
  -     *  Constructs a new <Code>BinaryHeap</Code> that will use the given
  -     *  comparator to order its elements.
  +     * 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 )
  -    {
  +    public BinaryHeap(Comparator comparator) {
           this();
           m_comparator = comparator;
       }
  -
  +    
       /**
  -     *  Create a new minimum binary heap with the specified initial capacity.
  +     * Constructs a new minimum binary heap with the specified initial capacity.
        *  
  -     *  @param capacity the initial capacity for the heap.  This value must
  +     * @param capacity  The initial capacity for the heap.  This value must
        *  be greater than zero.
  -     *
  -     *  @exception IllegalArgumentException 
  -     *   if <code>capacity</code> is &lt;= <code>0</code>
  -     **/
  -    public BinaryHeap( final int capacity )
  -    {
  -        this( capacity, true );
  +     * @throws IllegalArgumentException  
  +     *  if <code>capacity</code> is &lt;= <code>0</code>
  +     */
  +    public BinaryHeap(int capacity) {
  +        this(capacity, true);
       }
   
       /**
  -     *  Constructs a new <Code>BinaryHeap</Code>.
  +     * Constructs a new <code>BinaryHeap</code>.
        *
  -     *  @param capacity  the initial capacity for the heap
  -     *  @param comparator  the comparator to use to order elements
  -     *  @exception IllegalArgumentException 
  -     *   if <code>capacity</code> is <code>&lt;= 0</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( final int capacity, Comparator comparator )
  -    {
  -        this( capacity );
  +    public BinaryHeap(int capacity, Comparator comparator) {
  +        this(capacity);
           m_comparator = comparator;
       }
   
       /**
  -     *  Create a new minimum or maximum binary 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( final boolean isMinHeap )
  -    {
  -        this( DEFAULT_CAPACITY, isMinHeap );
  +     * @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 <Code>BinaryHeap</Code>.
  +     * 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 to use to order elements
  +     * @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( final boolean isMinHeap, Comparator comparator )
  -    {
  -        this( isMinHeap );
  +    public BinaryHeap(boolean isMinHeap, Comparator comparator) {
  +        this(isMinHeap);
           m_comparator = comparator;
       }
   
       /**
  -     *  Create 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.
  +     * Constructs a new minimum or maximum binary heap with the specified 
  +     * initial capacity.
        *
  -     *  @param isMinHeap if <code>true</code> the heap is created as a 
  +     * @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.
  -     *
  -     *  @exception IllegalArgumentException 
  -     *   if <code>capacity</code> is <code>&lt;= 0</code>
  -     **/
  -    public BinaryHeap( final int capacity, final boolean isMinHeap )
  -    {
  -        if( capacity <= 0 ) {
  -            throw new IllegalArgumentException( "invalid capacity" );
  +     * @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 ];
  +        m_elements = new Object[capacity + 1];
       }
   
       /**
  -     *  Constructs a new <Code>BinaryHeap</Code>.
  +     * 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 to use to order elements
  -     *  @exception IllegalArgumentException 
  -     *   if <code>capacity</code> is <code>&lt;= 0</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( final int capacity, final boolean isMinHeap,
  -                       Comparator comparator ) 
  -    {
  -        this( capacity, isMinHeap );
  +    public BinaryHeap(int capacity, boolean isMinHeap, Comparator comparator) {
  +        this(capacity, isMinHeap);
           m_comparator = comparator;
       }
   
  +    
       /**
  -     * Clear all elements from queue.
  +     * Clears all elements from queue.
        */
  -    public void clear()
  -    {
  +    public void clear() {
  +        m_elements = new Object[m_elements.length];  // for gc
           m_size = 0;
       }
   
       /**
  -     * Test if queue is empty.
  +     * Tests if queue is empty.
        *
        * @return <code>true</code> if queue is empty; <code>false</code>

  -     * otherwise.
  +     *  otherwise.
        */
  -    public boolean isEmpty()
  -    {
  -        return ( 0 == m_size );
  +    public boolean isEmpty() {
  +        return m_size == 0;
       }
   
       /**
  -     * Test if queue is full.
  +     * Tests if queue is full.
        *
        * @return <code>true</code> if queue is full; <code>false</code>
  -     * otherwise.
  +     *  otherwise.
        */
  -    public boolean isFull()
  -    {
  +    public boolean isFull() {
           //+1 as element 0 is noop
  -        return ( m_elements.length == m_size+1 );
  +        return m_elements.length == m_size + 1;
       }
   
       /**
  -     * Insert an element into queue.
  +     * Inserts an element into queue.
        *
  -     * @param element the element to be inserted
  +     * @param element  the element to be inserted
        */
  -    public void insert( final Object element )
  -    {
  -        if( isFull() ) grow();
  -
  +    public void insert(Object element) {
  +        if (isFull()) {
  +            grow();
  +        }
           //percolate element to it's place in tree
  -        if( m_isMinHeap ) percolateUpMinHeap( element );
  -        else percolateUpMaxHeap( element );
  +        if (m_isMinHeap) {
  +            percolateUpMinHeap(element);
  +        } else {
  +            percolateUpMaxHeap(element);
  +        }
       }
   
       /**
  -     * Return element on top of heap but don't remove it.
  +     * Returns the element on top of heap but don't remove it.
        *
        * @return the element at top of heap
  -     * @exception NoSuchElementException if <code>isEmpty() == true</code>
  +     * @throws NoSuchElementException  if <code>isEmpty() == true</code>
        */
  -    public Object peek() throws NoSuchElementException
  -    {
  -        if( isEmpty() ) throw new NoSuchElementException();
  -        else return m_elements[ 1 ];
  +    public Object peek() throws NoSuchElementException {
  +        if (isEmpty()) {
  +            throw new NoSuchElementException();
  +        } else {
  +            return m_elements[1];
  +        }
       }
   
       /**
  -     * Return element on top of heap and remove it.
  +     * Returns the element on top of heap and remove it.
        *
        * @return the element at top of heap
  -     * @exception NoSuchElementException if <code>isEmpty() == true</code>
  +     * @throws NoSuchElementException  if <code>isEmpty() == true</code>
        */
  -    public Object pop() throws NoSuchElementException
  -    {
  +    public Object pop() throws NoSuchElementException {
           final Object result = peek();
  -        m_elements[ 1 ] = m_elements[ m_size-- ];
  +        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 );
  +        // 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;
       }
   
       /**
  -     * Percolate element down heap from top.
  +     * Percolates element down heap from top.
        * Assume it is a maximum heap.
        *
        * @param index the index for the element
        */
  -    protected void percolateDownMinHeap( final int index )
  -    {
  -        final Object element = m_elements[ index ];
  -
  +    protected void percolateDownMinHeap(final int index) {
  +        final Object element = m_elements[index];
           int hole = index;
   
  -        while( (hole * 2) <= m_size )
  -        {
  +        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 )
  -            {
  +            // 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 )
  -            {
  +            // if we found resting place of bubble then terminate search
  +            if (compare(m_elements[child], element) >= 0) {
                   break;
               }
   
  -            m_elements[ hole ] = m_elements[ child ];
  +            m_elements[hole] = m_elements[child];
               hole = child;
           }
   
  -        m_elements[ hole ] = element;
  +        m_elements[hole] = element;
       }
   
       /**
  -     * Percolate element down heap from top.
  +     * Percolates element down heap from top.
        * Assume it is a maximum heap.
        *
        * @param index the index of the element
        */
  -    protected void percolateDownMaxHeap( final int index )
  -    {
  -        final Object element = m_elements[ index ];
  -
  +    protected void percolateDownMaxHeap(final int index) {
  +        final Object element = m_elements[index];
           int hole = index;
   
  -        while( (hole * 2) <= m_size )
  -        {
  +        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 )
  -            {
  +            // 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 )
  -            {
  +            // if we found resting place of bubble then terminate search
  +            if (compare(m_elements[child], element) <= 0) {
                   break;
               }
   
  -            m_elements[ hole ] = m_elements[ child ];
  +            m_elements[hole] = m_elements[child];
               hole = child;
           }
   
  -        m_elements[ hole ] = element;
  +        m_elements[hole] = element;
       }
   
       /**
  -     * Percolate element up heap from bottom.
  +     * Percolates element up heap from bottom.
        * Assume it is a maximum heap.
        *
        * @param element the element
        */
  -    protected void percolateUpMinHeap( final Object element )
  -    {
  +    protected void percolateUpMinHeap(final Object element) {
           int hole = ++m_size;
   
  -        m_elements[ hole ] = element;
  +        m_elements[hole] = element;
   
  -        while( hole > 1 &&
  -               compare( element,  m_elements[ hole / 2 ] ) < 0 )
  -        {
  -            //save element that is being pushed down
  -            //as the element "bubble" is percolated up
  +        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 ];
  +            m_elements[hole] = m_elements[next];
               hole = next;
           }
   
  -        m_elements[ hole ] = element;
  +        m_elements[hole] = element;
       }
   
       /**
  -     * Percolate element up heap from bottom.
  +     * Percolates element up heap from bottom.
        * Assume it is a maximum heap.
        *
        * @param element the element
        */
  -    protected void percolateUpMaxHeap( final Object element )
  -    {
  +    protected void percolateUpMaxHeap(final Object element) {
           int hole = ++m_size;
   
  -        while( hole > 1 &&
  -               compare( element, m_elements[ hole / 2 ] ) > 0 )
  -        {
  -            //save element that is being pushed down
  -            //as the element "bubble" is percolated up
  +        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 ];
  +            m_elements[hole] = m_elements[next];
               hole = next;
           }
   
  -        m_elements[ hole ] = element;
  +        m_elements[hole] = element;
       }
  -
  +    
  +    /**
  +     * 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) {
  +        if (m_comparator != null) {
               return m_comparator.compare(a, b);
           } else {
  -            return ((Comparable)a).compareTo(b);
  +            return ((Comparable) a).compareTo(b);
           }
       }
   
       /**
  -     *  Increase 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 );
  +     * 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.  The returned string
  +     * is similar to those produced by standard JDK collections.
        *
  -     *  @return  a string representation of this heap
  +     * @return a string representation of this heap
        */
  -    public String toString()
  -    {
  +    public String toString() {
           final StringBuffer sb = new StringBuffer();
   
  -        sb.append( "[ " );
  +        sb.append("[ ");
   
  -        for( int i = 1; i < m_size + 1; i++ )
  -        {
  -            if( i != 1 ) sb.append( ", " );
  -            sb.append( m_elements[ i ] );
  +        for (int i = 1; i < m_size + 1; i++) {
  +            if (i != 1) {
  +                sb.append(", ");
  +            }
  +            sb.append(m_elements[i]);
           }
   
  -        sb.append( " ]" );
  +        sb.append(" ]");
   
           return sb.toString();
       }
   
   
       /**
  -     *  Returns an iterator over this heap's elements.
  +     * Returns an iterator over this heap's elements.
        *
  -     *  @return an iterator over this heap's elements
  +     * @return an iterator over this heap's elements
        */
       public Iterator iterator() {
           return new Iterator() {
  @@ -521,22 +509,21 @@
   
   
       /**
  -     *  Adds an object to this heap.  Same as {@link #insert(Object)}.
  +     * Adds an object to this heap. Same as {@link #insert(Object)}.
        *
  -     *  @param o  the object to add
  -     *  @return true, always
  +     * @param object  the object to add
  +     * @return true, always
        */
  -    public boolean add(Object o) {
  -        insert(o);
  +    public boolean add(Object object) {
  +        insert(object);
           return true;
       }
   
  -
       /**
  -     *  Returns the priority element.  Same as {@link #peek()}.
  +     * Returns the priority element. Same as {@link #peek()}.
        *
  -     *  @return the priority element
  -     *  @throws BufferUnderflowException if this heap is empty
  +     * @return the priority element
  +     * @throws BufferUnderflowException if this heap is empty
        */
       public Object get() {
           try {
  @@ -546,12 +533,11 @@
           }
       }
   
  -
       /**
  -     *  Removes the priority element.  Same as {@link #pop()}.
  +     * Removes the priority element. Same as {@link #pop()}.
        *
  -     *  @return the removed priority element
  -     *  @throws BufferUnderflowException if this heap is empty
  +     * @return the removed priority element
  +     * @throws BufferUnderflowException if this heap is empty
        */
       public Object remove() {
           try {
  @@ -561,23 +547,13 @@
           }
       }
   
  -
       /**
  -     *  Returns the number of elements in this heap.
  +     * Returns the number of elements in this heap.
        *
  -     *  @return the number of elements in this heap
  +     * @return the number of elements in this heap
        */
       public int size() {
           return m_size;
       }
   
  -    /**
  -     *  Used by testing code.
  -     *
  -     *  @return  the otherwise private comparator
  -     */
  -    Comparator comparator() {
  -        return m_comparator;
  -    }
   }
  -
  
  
  

--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message