org.apache.commons.collections.buffer
public class PriorityBuffer extends AbstractCollection implements Buffer, Serializable
Buffer
that provides for
removal based on Comparator
ordering.
The removal order of a binary heap is based on either the natural sort
order of its elements or a specified Comparator. The
remove method always returns the first element as determined
by the sort order. (The ascendingOrder
flag in the constructors
can be used to reverse the sort order, in which case remove
will always remove the last element.) The removal order is
not the same as the order of iteration; elements are
returned by the iterator in no particular order.
The add and remove operations perform in logarithmic time. The get operation performs in constant time. All other operations perform in linear time or worse.
Note that this implementation is not synchronized. Use
synchronizedBuffer or
decorate
to provide synchronized access to a PriorityBuffer
:
Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
This class is Serializable from Commons Collections 3.2.
Since: Commons Collections 3.0 (previously BinaryHeap v1.0)
Version: $Revision: 405927 $ $Date: 2006-05-12 23:57:03 +0100 (Fri, 12 May 2006) $
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