Class PriorityBuffer
- java.lang.Object
-
- java.util.AbstractCollection
-
- org.apache.commons.collections.buffer.PriorityBuffer
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Iterable
,java.util.Collection
,Buffer
public class PriorityBuffer extends java.util.AbstractCollection implements Buffer, java.io.Serializable
Binary heap implementation ofBuffer
that provides for removal based onComparator
ordering.The removal order of a binary heap is based on either the natural sort order of its elements or a specified
Comparator
. Theremove()
method always returns the first element as determined by the sort order. (TheascendingOrder
flag in the constructors can be used to reverse the sort order, in which caseremove()
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)
andremove()
operations perform in logarithmic time. Theget()
operation performs in constant time. All other operations perform in linear time or worse.Note that this implementation is not synchronized. Use
BufferUtils.synchronizedBuffer(Buffer)
orSynchronizedBuffer.decorate(Buffer)
to provide synchronized access to aPriorityBuffer
: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: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description protected boolean
ascendingOrder
If true, the first element as determined by the sort order will be returned.protected java.util.Comparator
comparator
The comparator used to order the elementsprivate static int
DEFAULT_CAPACITY
The default capacity for the buffer.protected java.lang.Object[]
elements
The elements in this buffer.private static long
serialVersionUID
Serialization lock.protected int
size
The number of elements currently in this buffer.
-
Constructor Summary
Constructors Constructor Description PriorityBuffer()
Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added.PriorityBuffer(boolean ascendingOrder)
Constructs a new empty buffer specifying the sort order and using the natural order of the objects added.PriorityBuffer(boolean ascendingOrder, java.util.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, 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, java.util.Comparator comparator)
Constructs a new empty buffer that specifying initial capacity, sort order and comparator.PriorityBuffer(int capacity, java.util.Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the specified comparator and initial capacity.PriorityBuffer(java.util.Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the specified comparator.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(java.lang.Object element)
Adds an element to the buffer.void
clear()
Clears all elements from the buffer.java.util.Comparator
comparator()
Gets the comparator being used for this buffer, null is natural order.protected int
compare(java.lang.Object a, java.lang.Object b)
Compares two objects using the comparator if specified, or the natural order otherwise.java.lang.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 elementsboolean
isAscendingOrder()
Checks whether the heap is ascending or descending order.protected boolean
isAtCapacity()
Tests if the buffer is at capacity.java.util.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(java.lang.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(java.lang.Object element)
Percolates a new element up heap from the bottom.java.lang.Object
remove()
Gets and removes the next element (pop).int
size()
Returns the number of elements in this buffer.java.lang.String
toString()
Returns a string representation of this heap.-
Methods inherited from class java.util.AbstractCollection
addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
Serialization lock.- See Also:
- Constant Field Values
-
DEFAULT_CAPACITY
private static final int DEFAULT_CAPACITY
The default capacity for the buffer.- See Also:
- Constant Field Values
-
elements
protected java.lang.Object[] elements
The elements in this buffer.
-
size
protected int size
The number of elements currently in this buffer.
-
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.
-
comparator
protected java.util.Comparator comparator
The comparator used to order the elements
-
-
Constructor Detail
-
PriorityBuffer
public PriorityBuffer()
Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added.
-
PriorityBuffer
public PriorityBuffer(java.util.Comparator comparator)
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)
Constructs a new empty buffer specifying the sort order and using the natural order of the objects added.- Parameters:
ascendingOrder
- iftrue
the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap
-
PriorityBuffer
public PriorityBuffer(boolean ascendingOrder, java.util.Comparator comparator)
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 ordercomparator
- the comparator used to order the elements, null means use natural order
-
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:
capacity
- the initial capacity for the buffer, greater than zero- Throws:
java.lang.IllegalArgumentException
- ifcapacity
is <=0
-
PriorityBuffer
public PriorityBuffer(int capacity, java.util.Comparator comparator)
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 zerocomparator
- the comparator used to order the elements, null means use natural order- Throws:
java.lang.IllegalArgumentException
- ifcapacity
is <=0
-
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:
capacity
- the initial capacity for the buffer, greater than zeroascendingOrder
- iftrue
the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap.- Throws:
java.lang.IllegalArgumentException
- ifcapacity
is<= 0
-
PriorityBuffer
public PriorityBuffer(int capacity, boolean ascendingOrder, java.util.Comparator comparator)
Constructs a new empty buffer that specifying initial capacity, sort order and comparator.- Parameters:
capacity
- the initial capacity for the buffer, greater than zeroascendingOrder
- true to use the order imposed by the given comparator; false to reverse that ordercomparator
- the comparator used to order the elements, null means use natural order- Throws:
java.lang.IllegalArgumentException
- ifcapacity
is<= 0
-
-
Method Detail
-
isAscendingOrder
public boolean isAscendingOrder()
Checks whether the heap is ascending or descending order.- Returns:
- true if ascending order (a min heap)
-
comparator
public java.util.Comparator comparator()
Gets the comparator being used for this buffer, null is natural order.- Returns:
- the comparator in use, null is natural order
-
size
public int size()
Returns the number of elements in this buffer.- Specified by:
size
in interfacejava.util.Collection
- Specified by:
size
in classjava.util.AbstractCollection
- Returns:
- the number of elements in this buffer
-
clear
public void clear()
Clears all elements from the buffer.- Specified by:
clear
in interfacejava.util.Collection
- Overrides:
clear
in classjava.util.AbstractCollection
-
add
public boolean add(java.lang.Object element)
Adds an element to the buffer.The element added will be sorted according to the comparator in use.
- Specified by:
add
in interfacejava.util.Collection
- Overrides:
add
in classjava.util.AbstractCollection
- Parameters:
element
- the element to be added- Returns:
- true always
-
get
public java.lang.Object get()
Gets the next element to be removed without actually removing it (peek).- Specified by:
get
in interfaceBuffer
- Returns:
- the next element
- Throws:
BufferUnderflowException
- if the buffer is empty
-
remove
public java.lang.Object remove()
Gets and removes the next element (pop).- Specified by:
remove
in interfaceBuffer
- Returns:
- the next element
- Throws:
BufferUnderflowException
- if the buffer is empty
-
isAtCapacity
protected boolean isAtCapacity()
Tests if the buffer is at capacity.- Returns:
true
if buffer is full;false
otherwise.
-
percolateDownMinHeap
protected void percolateDownMinHeap(int index)
Percolates element down heap from the position given by the index.Assumes it is a minimum heap.
- Parameters:
index
- the index for the element
-
percolateDownMaxHeap
protected void percolateDownMaxHeap(int index)
Percolates element down heap from the position given by the index.Assumes it is a maximum heap.
- Parameters:
index
- the index of the element
-
percolateUpMinHeap
protected void percolateUpMinHeap(int index)
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(java.lang.Object element)
Percolates a new element up heap from the bottom.Assumes it is a minimum heap.
- Parameters:
element
- the element
-
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:
index
- the index of the element to be percolated up
-
percolateUpMaxHeap
protected void percolateUpMaxHeap(java.lang.Object element)
Percolates a new element up heap from the bottom.Assume it is a maximum heap.
- Parameters:
element
- the element
-
compare
protected int compare(java.lang.Object a, java.lang.Object b)
Compares two objects using the comparator if specified, or the natural order otherwise.- Parameters:
a
- the first objectb
- the second object- Returns:
- -ve if a less than b, 0 if they are equal, +ve if a greater than b
-
grow
protected void grow()
Increases the size of the heap to support additional elements
-
iterator
public java.util.Iterator iterator()
Returns an iterator over this heap's elements.- Specified by:
iterator
in interfacejava.util.Collection
- Specified by:
iterator
in interfacejava.lang.Iterable
- Specified by:
iterator
in classjava.util.AbstractCollection
- Returns:
- an iterator over this heap's elements
-
toString
public java.lang.String toString()
Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.- Overrides:
toString
in classjava.util.AbstractCollection
- Returns:
- a string representation of this heap
-
-