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(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
BufferUtils.synchronizedBuffer(Buffer)
or
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.
Modifier and Type | Field and Description |
---|---|
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 and 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,
Comparator comparator)
Constructs a new empty buffer specifying the sort order and comparator.
|
PriorityBuffer(Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the
specified 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,
Comparator comparator)
Constructs a new empty buffer that specifying initial capacity,
sort order and comparator.
|
PriorityBuffer(int capacity,
Comparator comparator)
Constructs a new empty buffer that sorts in ascending order using the
specified comparator and initial capacity.
|
Modifier and Type | Method and Description |
---|---|
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.
|
addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray
protected Object[] elements
protected int size
protected boolean ascendingOrder
protected Comparator comparator
public PriorityBuffer()
public PriorityBuffer(Comparator comparator)
comparator
- the comparator used to order the elements,
null means use natural orderpublic PriorityBuffer(boolean ascendingOrder)
ascendingOrder
- if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heappublic PriorityBuffer(boolean ascendingOrder, Comparator comparator)
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 orderpublic PriorityBuffer(int capacity)
capacity
- the initial capacity for the buffer, greater than zeroIllegalArgumentException
- if capacity
is <= 0
public PriorityBuffer(int capacity, Comparator comparator)
capacity
- the initial capacity for the buffer, greater than zerocomparator
- the comparator used to order the elements,
null means use natural orderIllegalArgumentException
- if capacity
is <= 0
public PriorityBuffer(int capacity, boolean ascendingOrder)
capacity
- the initial capacity for the buffer, greater than zeroascendingOrder
- if true
the heap is created as a
minimum heap; otherwise, the heap is created as a maximum heap.IllegalArgumentException
- if capacity
is <= 0
public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator)
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 orderIllegalArgumentException
- if capacity
is <= 0
public boolean isAscendingOrder()
public Comparator comparator()
public int size()
size
in interface Collection
size
in class AbstractCollection
public void clear()
clear
in interface Collection
clear
in class AbstractCollection
public boolean add(Object element)
The element added will be sorted according to the comparator in use.
add
in interface Collection
add
in class AbstractCollection
element
- the element to be addedpublic Object get()
get
in interface Buffer
BufferUnderflowException
- if the buffer is emptypublic Object remove()
remove
in interface Buffer
BufferUnderflowException
- if the buffer is emptyprotected boolean isAtCapacity()
true
if buffer is full; false
otherwise.protected void percolateDownMinHeap(int index)
Assumes it is a minimum heap.
index
- the index for the elementprotected void percolateDownMaxHeap(int index)
Assumes it is a maximum heap.
index
- the index of the elementprotected void percolateUpMinHeap(int index)
Assumes it is a minimum heap.
index
- the index of the element to be percolated upprotected void percolateUpMinHeap(Object element)
Assumes it is a minimum heap.
element
- the elementprotected void percolateUpMaxHeap(int index)
Assume it is a maximum heap.
index
- the index of the element to be percolated upprotected void percolateUpMaxHeap(Object element)
Assume it is a maximum heap.
element
- the elementprotected int compare(Object a, Object b)
a
- the first objectb
- the second objectprotected void grow()
public Iterator iterator()
iterator
in interface Iterable
iterator
in interface Collection
iterator
in class AbstractCollection
public String toString()
toString
in class AbstractCollection
Copyright © 2001–2015 The Apache Software Foundation. All rights reserved.