Eclipse
Eclipse
IDEA
IntelliJ
NetBeans
NetBeans
XpoLog
XpoLog
org.apache.commons.collections.buffer
Class PriorityBuffer
Tab mode
public class PriorityBuffer
extends AbstractCollection
implements Buffer, Serializable
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 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(Object) 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(Buffer) or decorate(Buffer) to provide synchronized access to a PriorityBuffer: 

 Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());

This class is Serializable from Commons Collections 3.2.

SinceCommons Co
Version$Revision:
AuthorPeter Donald, Ram Chidambaram, Michael A. Smith, Paul Jack, Stephen Colebourne, Steve Phelps
Wiki javadoc Use textile entry format.
Add your comments here.
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.
Methods inherited from java.utilAbstractCollection
Methods inherited from java.utilCollection
Methods inherited from java.langObject
Field Detail
ascendingOrder
protected boolean ascendingOrder
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.
Wiki javadoc Use textile entry format.
Add your comments here.
comparator
protected Comparator comparator
The comparator used to order the elements
Wiki javadoc Use textile entry format.
Add your comments here.
elements
protected Object[] elements
The elements in this buffer.
Wiki javadoc Use textile entry format.
Add your comments here.
size
protected int size
The number of elements currently in this buffer.
Wiki javadoc Use textile entry format.
Add your comments here.
Constructor Detail
PriorityBuffer
public PriorityBuffer ( )
Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added.
Wiki javadoc Use textile entry format.
Add your comments here.
PriorityBuffer
public PriorityBuffer ( Comparator comparator )
Constructs a new empty buffer that sorts in ascending order using the specified comparator.
Parameters
TypeNameDescription
Comparator comparator the comparator used to order the elements, null means use natural order
Wiki javadoc Use textile entry format.
Add your comments here.
PriorityBuffer
public PriorityBuffer ( boolean ascendingOrder )
Constructs a new empty buffer specifying the sort order and using the natural order of the objects added.
Parameters
TypeNameDescription
boolean ascendingOrder if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap
Wiki javadoc Use textile entry format.
Add your comments here.
PriorityBuffer
public PriorityBuffer ( boolean ascendingOrder, Comparator comparator )
Constructs a new empty buffer specifying the sort order and comparator.
Parameters
TypeNameDescription
boolean ascendingOrder true to use the order imposed by the given comparator; false to reverse that order
Comparator comparator the comparator used to order the elements, null means use natural order
Wiki javadoc Use textile entry format.
Add your comments here.
PriorityBuffer
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.
Parameters
TypeNameDescription
int capacity the initial capacity for the buffer, greater than zero
Wiki javadoc Use textile entry format.
Add your comments here.
PriorityBuffer
public PriorityBuffer ( int capacity, Comparator comparator )
Constructs a new empty buffer that sorts in ascending order using the specified comparator and initial capacity.
Parameters
TypeNameDescription
int capacity the initial capacity for the buffer, greater than zero
Comparator comparator the comparator used to order the elements, null means use natural order
Wiki javadoc Use textile entry format.
Add your comments here.
PriorityBuffer
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.
Parameters
TypeNameDescription
int capacity the initial capacity for the buffer, greater than zero
boolean ascendingOrder if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap.
Wiki javadoc Use textile entry format.
Add your comments here.
PriorityBuffer
public PriorityBuffer ( int capacity, boolean ascendingOrder, Comparator comparator )
Constructs a new empty buffer that specifying initial capacity, sort order and comparator.
Parameters
TypeNameDescription
int capacity the initial capacity for the buffer, greater than zero
boolean ascendingOrder true to use the order imposed by the given comparator; false to reverse that order
Comparator comparator the comparator used to order the elements, null means use natural order
Wiki javadoc Use textile entry format.
Add your comments here.
Method Detail
add
public boolean add ( Object element )
Adds an element to the buffer.

The element added will be sorted according to the comparator in use.

Overrides method in AbstractCollection
Parameters
TypeNameDescription
Object element the element to be added
Wiki javadoc Use textile entry format.
Add your comments here.
clear
public void clear ( )
Clears all elements from the buffer.
Overrides method in AbstractCollection
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
comparator
public Comparator comparator ( )
Gets the comparator being used for this buffer, null is natural order.
Wiki javadoc Use textile entry format.
Add your comments here.
compare
protected int compare ( Object a, Object b )
Compares two objects using the comparator if specified, or the natural order otherwise.
Parameters
TypeNameDescription
Object a the first object
Object b the second object
Wiki javadoc Use textile entry format.
Add your comments here.
get
public Object get ( )
Gets the next element to be removed without actually removing it (peek).
Implements method in Buffer
Wiki javadoc Use textile entry format.
Add your comments here.
grow
protected void grow ( )
Increases the size of the heap to support additional elements
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
isAscendingOrder
public boolean isAscendingOrder ( )
Checks whether the heap is ascending or descending order.
Wiki javadoc Use textile entry format.
Add your comments here.
isAtCapacity
protected boolean isAtCapacity ( )
Tests if the buffer is at capacity.
Wiki javadoc Use textile entry format.
Add your comments here.
iterator
public Iterator iterator ( )
Returns an iterator over this heap's elements.
Overrides method in AbstractCollection
Wiki javadoc Use textile entry format.
Add your comments here.
percolateDownMaxHeap
protected void percolateDownMaxHeap ( int index )
Percolates element down heap from the position given by the index.

Assumes it is a maximum heap.

Parameters
TypeNameDescription
int index the index of the element
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
percolateDownMinHeap
protected void percolateDownMinHeap ( int index )
Percolates element down heap from the position given by the index.

Assumes it is a minimum heap.

Parameters
TypeNameDescription
int index the index for the element
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
percolateUpMaxHeap
protected void percolateUpMaxHeap ( int index )
Percolates element up heap from from the position given by the index.

Assume it is a maximum heap.

Parameters
TypeNameDescription
int index the index of the element to be percolated up
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
percolateUpMaxHeap
protected void percolateUpMaxHeap ( Object element )
Percolates a new element up heap from the bottom.

Assume it is a maximum heap.

Parameters
TypeNameDescription
Object element the element
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
percolateUpMinHeap
protected void percolateUpMinHeap ( int index )
Percolates element up heap from the position given by the index.

Assumes it is a minimum heap.

Parameters
TypeNameDescription
int index the index of the element to be percolated up
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
percolateUpMinHeap
protected void percolateUpMinHeap ( Object element )
Percolates a new element up heap from the bottom.

Assumes it is a minimum heap.

Parameters
TypeNameDescription
Object element the element
Returns void No description provided.
Wiki javadoc Use textile entry format.
Add your comments here.
remove
public Object remove ( )
Gets and removes the next element (pop).
Implements method in Buffer
Wiki javadoc Use textile entry format.
Add your comments here.
size
public int size ( )
Returns the number of elements in this buffer.
Overrides method in AbstractCollection
Wiki javadoc Use textile entry format.
Add your comments here.
toString
public String toString ( )
Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.
Overrides method in AbstractCollection
Wiki javadoc Use textile entry format.
Add your comments here.