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="[EMAIL PROTECTED]">Federico Barbieri</a>
* @author <a href="[EMAIL PROTECTED]">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:[EMAIL PROTECTED]";>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:[EMAIL PROTECTED]";>Peter Donald</a>
+ * @author <a href="mailto:[EMAIL PROTECTED]";>Ram Chidambaram</a>
+ * @author <a href="mailto:[EMAIL PROTECTED]";>Michael A. Smith</a>
+ * @author Paul Jack
+ * @author Stephen Colebourne
* @since 1.0
- * @author <a href="mailto:[EMAIL PROTECTED]";>Peter Donald</a>
- * @author <a href="mailto:[EMAIL PROTECTED]";>Ram Chidambaram</a>
- * @author <a href="mailto:[EMAIL PROTECTED]";>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 <= <code>0</code>
- **/
- public BinaryHeap( final int capacity )
- {
- this( capacity, true );
+ * @throws IllegalArgumentException
+ * if <code>capacity</code> is <= <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><= 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 <= <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><= 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><= 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><= 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><= 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:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
