org.apache.commons.collections.buffer
public class PriorityBuffer extends AbstractCollection implements Buffer
Buffer
that provides for
removal based on Comparator
ordering.
The removal order of a binary heap is based on either the natural sort
order of its elements or a specified {@link Comparator}. The
{@link #remove()} method always returns the first element as determined
by the sort order. (The ascendingOrder
flag in the constructors
can be used to reverse the sort order, in which case {@link #remove()}
will always remove the last element.) The removal order is
not the same as the order of iteration; elements are
returned by the iterator in no particular order.
The {@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.
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 PriorityBuffer
:
Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
Since: Commons Collections 3.0 (previously BinaryHeap v1.0)
Version: $Revision: 1.5 $ $Date: 2004/05/15 12:33:23 $
Field Summary | |
---|---|
protected boolean | ascendingOrder
If true, the first element as determined by the sort order will
be returned. |
protected Comparator | comparator
The comparator used to order the elements |
protected Object[] | elements
The elements in this buffer. |
protected int | size
The number of elements currently in this buffer. |
Constructor Summary | |
---|---|
PriorityBuffer()
Constructs a new empty buffer that sorts in ascending order by the
natural order of the objects added. | |
PriorityBuffer(Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the
specified comparator.
| |
PriorityBuffer(boolean ascendingOrder)
Constructs a new empty buffer specifying the sort order and using the
natural order of the objects added.
| |
PriorityBuffer(boolean ascendingOrder, Comparator comparator)
Constructs a new empty buffer specifying the sort order and comparator.
| |
PriorityBuffer(int capacity)
Constructs a new empty buffer that sorts in ascending order by the
natural order of the objects added, specifying an initial capacity.
| |
PriorityBuffer(int capacity, Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the
specified comparator and initial capacity.
| |
PriorityBuffer(int capacity, boolean ascendingOrder)
Constructs a new empty buffer that specifying initial capacity and
sort order, using the natural order of the objects added.
| |
PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator)
Constructs a new empty buffer that specifying initial capacity,
sort order and comparator.
|
Method Summary | |
---|---|
boolean | add(Object element)
Adds an element to the buffer.
|
void | clear()
Clears all elements from the buffer. |
Comparator | comparator()
Gets the comparator being used for this buffer, null is natural order.
|
protected int | compare(Object a, Object b)
Compares two objects using the comparator if specified, or the
natural order otherwise.
|
Object | get()
Gets the next element to be removed without actually removing it (peek).
|
protected void | grow()
Increases the size of the heap to support additional elements |
boolean | isAscendingOrder()
Checks whether the heap is ascending or descending order.
|
protected boolean | isAtCapacity()
Tests if the buffer is at capacity.
|
Iterator | iterator()
Returns an iterator over this heap's elements.
|
protected void | percolateDownMaxHeap(int index)
Percolates element down heap from the position given by the index.
|
protected void | percolateDownMinHeap(int index)
Percolates element down heap from the position given by the index.
|
protected void | percolateUpMaxHeap(int index)
Percolates element up heap from from the position given by the index.
|
protected void | percolateUpMaxHeap(Object element)
Percolates a new element up heap from the bottom.
|
protected void | percolateUpMinHeap(int index)
Percolates element up heap from the position given by the index.
|
protected void | percolateUpMinHeap(Object element)
Percolates a new element up heap from the bottom.
|
Object | remove()
Gets and removes the next element (pop).
|
int | size()
Returns the number of elements in this buffer.
|
String | toString()
Returns a string representation of this heap. |
Parameters: comparator the comparator used to order the elements, null means use natural order
Parameters: ascendingOrder if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heap
Parameters: ascendingOrder true to use the order imposed by the given comparator; false to reverse that order comparator the comparator used to order the elements, null means use natural order
Parameters: capacity the initial capacity for the buffer, greater than zero
Throws: IllegalArgumentException if capacity
is <= 0
Parameters: capacity the initial capacity for the buffer, greater than zero comparator the comparator used to order the elements, null means use natural order
Throws: IllegalArgumentException if capacity
is <= 0
Parameters: capacity the initial capacity for the buffer, greater than zero ascendingOrder if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heap.
Throws: IllegalArgumentException if capacity
is <= 0
Parameters: capacity the initial capacity for the buffer, greater than zero ascendingOrder true to use the order imposed by the given comparator; false to reverse that order comparator the comparator used to order the elements, null means use natural order
Throws: IllegalArgumentException if capacity
is <= 0
The element added will be sorted according to the comparator in use.
Parameters: element the element to be added
Returns: true always
Returns: the comparator in use, null is natural order
Parameters: a the first object b the second object
Returns: -ve if a less than b, 0 if they are equal, +ve if a greater than b
Returns: the next element
Throws: BufferUnderflowException if the buffer is empty
Returns: true if ascending order (a min heap)
Returns: true
if buffer is full; false
otherwise.
Returns: an iterator over this heap's elements
Assumes it is a maximum heap.
Parameters: index the index of the element
Assumes it is a minimum heap.
Parameters: index the index for the element
Assume it is a maximum heap.
Parameters: index the index of the element to be percolated up
Assume it is a maximum heap.
Parameters: element the element
Assumes it is a minimum heap.
Parameters: index the index of the element to be percolated up
Assumes it is a minimum heap.
Parameters: element the element
Returns: the next element
Throws: BufferUnderflowException if the buffer is empty
Returns: the number of elements in this buffer
Returns: a string representation of this heap