| java.lang.Object
 java.util.AbstractCollection
org.apache.commons.collections.buffer.PriorityBuffer
| PriorityBuffer | | public class PriorityBuffer extends AbstractCollection implements Buffer,Serializable(Code) | | Binary heap implementation of 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
PriorityBuffer.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
PriorityBuffer.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
PriorityBuffer.add(Object) and
PriorityBuffer.remove() operations perform
in logarithmic time. The
PriorityBuffer.get() operation performs in constant
time. All other operations perform in linear time or worse.
Note that this implementation is not synchronized. Use
org.apache.commons.collections.BufferUtils.synchronizedBuffer(Buffer) or
org.apache.commons.collections.buffer.SynchronizedBuffer.decorate(Buffer) 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) $
author:
Peter Donald
author:
Ram Chidambaram
author:
Michael A. Smith
author:
Paul Jack
author:
Stephen Colebourne
author:
Steve Phelps |
| Field Summary | |
| protected boolean | ascendingOrder
If true, the first element as determined by the sort order will
be returned. | | protected Comparator | comparator
| | protected Object[] | elements
The elements in this buffer. | | protected int | size
The number of elements currently in this buffer. |
| Constructor Summary | |
| public | PriorityBuffer()
Constructs a new empty buffer that sorts in ascending order by the
natural order of the objects added. | | public | PriorityBuffer(Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the
specified comparator. | | public | PriorityBuffer(boolean ascendingOrder)
Constructs a new empty buffer specifying the sort order and using the
natural order of the objects added. | | public | PriorityBuffer(boolean ascendingOrder, Comparator comparator)
Constructs a new empty buffer specifying the sort order and comparator. | | public | 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. | | public | PriorityBuffer(int capacity, Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the
specified comparator and initial capacity. | | public | 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. | | public | PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator)
Constructs a new empty buffer that specifying initial capacity,
sort order and comparator. |
| Method Summary | |
| public boolean | add(Object element)
Adds an element to the buffer. | | public void | clear()
Clears all elements from the buffer. | | public 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. | | public Object | get()
Gets the next element to be removed without actually removing it (peek). | | protected void | grow()
| | public boolean | isAscendingOrder()
Checks whether the heap is ascending or descending order. | | protected boolean | isAtCapacity()
Tests if the buffer is at capacity. | | public 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. | | public Object | remove()
Gets and removes the next element (pop). | | public int | size()
Returns the number of elements in this buffer. | | public String | toString()
Returns a string representation of this heap. |
| ascendingOrder | | protected boolean ascendingOrder(Code) | | 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.
|
| comparator | | protected Comparator comparator(Code) | | The comparator used to order the elements
|
| elements | | protected Object[] elements(Code) | | The elements in this buffer.
|
| size | | protected int size(Code) | | The number of elements currently in this buffer.
|
| PriorityBuffer | | public PriorityBuffer()(Code) | | Constructs a new empty buffer that sorts in ascending order by the
natural order of the objects added.
|
| PriorityBuffer | | public PriorityBuffer(Comparator comparator)(Code) | | Constructs a new empty buffer that sorts in ascending order using the
specified comparator.
Parameters:
comparator - the comparator used to order the elements,null means use natural order |
| PriorityBuffer | | public PriorityBuffer(boolean ascendingOrder)(Code) | | Constructs a new empty buffer specifying the sort order and using the
natural order of the objects added.
Parameters:
ascendingOrder - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap |
| PriorityBuffer | | public PriorityBuffer(boolean ascendingOrder, Comparator comparator)(Code) | | Constructs a new empty buffer specifying the sort order and comparator.
Parameters:
ascendingOrder - true to use the order imposed by the given comparator; false to reverse that order
Parameters:
comparator - the comparator used to order the elements,null means use natural order |
| PriorityBuffer | | public PriorityBuffer(int capacity)(Code) | | Constructs a new empty buffer that sorts in ascending order by the
natural order of the objects added, specifying an initial capacity.
Parameters:
capacity - the initial capacity for the buffer, greater than zero
throws:
IllegalArgumentException - if capacity is <= 0 |
| PriorityBuffer | | public PriorityBuffer(int capacity, Comparator comparator)(Code) | | Constructs a new empty buffer that sorts in ascending order using the
specified comparator and initial capacity.
Parameters:
capacity - the initial capacity for the buffer, greater than zero
Parameters:
comparator - the comparator used to order the elements,null means use natural order
throws:
IllegalArgumentException - if capacity is <= 0 |
| PriorityBuffer | | public PriorityBuffer(int capacity, boolean ascendingOrder)(Code) | | Constructs a new empty buffer that specifying initial capacity and
sort order, using the natural order of the objects added.
Parameters:
capacity - the initial capacity for the buffer, greater than zero
Parameters:
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 |
| PriorityBuffer | | public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator)(Code) | | Constructs a new empty buffer that specifying initial capacity,
sort order and comparator.
Parameters:
capacity - the initial capacity for the buffer, greater than zero
Parameters:
ascendingOrder - true to use the order imposed by the given comparator; false to reverse that order
Parameters:
comparator - the comparator used to order the elements,null means use natural order
throws:
IllegalArgumentException - if capacity is <= 0 |
| add | | public boolean add(Object element)(Code) | | Adds an element to the buffer.
The element added will be sorted according to the comparator in use.
Parameters:
element - the element to be added true always |
| clear | | public void clear()(Code) | | Clears all elements from the buffer.
|
| comparator | | public Comparator comparator()(Code) | | Gets the comparator being used for this buffer, null is natural order.
the comparator in use, null is natural order |
| compare | | protected int compare(Object a, Object b)(Code) | | Compares two objects using the comparator if specified, or the
natural order otherwise.
Parameters:
a - the first object
Parameters:
b - the second object -ve if a less than b, 0 if they are equal, +ve if a greater than b |
| grow | | protected void grow()(Code) | | Increases the size of the heap to support additional elements
|
| isAscendingOrder | | public boolean isAscendingOrder()(Code) | | Checks whether the heap is ascending or descending order.
true if ascending order (a min heap) |
| isAtCapacity | | protected boolean isAtCapacity()(Code) | | Tests if the buffer is at capacity.
true if buffer is full; false otherwise. |
| iterator | | public Iterator iterator()(Code) | | Returns an iterator over this heap's elements.
an iterator over this heap's elements |
| percolateDownMaxHeap | | protected void percolateDownMaxHeap(int index)(Code) | | Percolates element down heap from the position given by the index.
Assumes it is a maximum heap.
Parameters:
index - the index of the element |
| percolateDownMinHeap | | protected void percolateDownMinHeap(int index)(Code) | | Percolates element down heap from the position given by the index.
Assumes it is a minimum heap.
Parameters:
index - the index for the element |
| percolateUpMaxHeap | | protected void percolateUpMaxHeap(int index)(Code) | | Percolates element up heap from from the position given by the index.
Assume it is a maximum heap.
Parameters:
index - the index of the element to be percolated up |
| percolateUpMaxHeap | | protected void percolateUpMaxHeap(Object element)(Code) | | Percolates a new element up heap from the bottom.
Assume it is a maximum heap.
Parameters:
element - the element |
| percolateUpMinHeap | | protected void percolateUpMinHeap(int index)(Code) | | Percolates element up heap from the position given by the index.
Assumes it is a minimum heap.
Parameters:
index - the index of the element to be percolated up |
| percolateUpMinHeap | | protected void percolateUpMinHeap(Object element)(Code) | | Percolates a new element up heap from the bottom.
Assumes it is a minimum heap.
Parameters:
element - the element |
| size | | public int size()(Code) | | Returns the number of elements in this buffer.
the number of elements in this buffer |
| toString | | public String toString()(Code) | | Returns a string representation of this heap. The returned string
is similar to those produced by standard JDK collections.
a string representation of this heap |
|
|