public class

PriorityBuffer

extends AbstractCollection<E>
implements Serializable Buffer
java.lang.Object
   ↳ java.util.AbstractCollection<E>
     ↳ org.apache.commons.collections.buffer.PriorityBuffer

Class Overview

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.

Summary

Fields
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.
Public Constructors
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.
Public Methods
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.
Object get()
Gets the next element to be removed without actually removing it (peek).
boolean isAscendingOrder()
Checks whether the heap is ascending or descending order.
Iterator iterator()
Returns an iterator over this heap's elements.
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.
Protected Methods
int compare(Object a, Object b)
Compares two objects using the comparator if specified, or the natural order otherwise.
void grow()
Increases the size of the heap to support additional elements
boolean isAtCapacity()
Tests if the buffer is at capacity.
void percolateDownMaxHeap(int index)
Percolates element down heap from the position given by the index.
void percolateDownMinHeap(int index)
Percolates element down heap from the position given by the index.
void percolateUpMaxHeap(Object element)
Percolates a new element up heap from the bottom.
void percolateUpMaxHeap(int index)
Percolates element up heap from from the position given by the index.
void percolateUpMinHeap(Object element)
Percolates a new element up heap from the bottom.
void percolateUpMinHeap(int index)
Percolates element up heap from the position given by the index.
[Expand]
Inherited Methods
From class java.util.AbstractCollection
From class java.lang.Object
From interface java.lang.Iterable
From interface java.util.Collection
From interface org.apache.commons.collections.Buffer

Fields

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.

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.

Public Constructors

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.

Parameters
comparator the comparator used to order the elements, null means use natural order

public PriorityBuffer (boolean ascendingOrder)

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

public PriorityBuffer (boolean ascendingOrder, 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 order
comparator the comparator used to order the elements, null means use natural order

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
IllegalArgumentException if capacity is <= 0

public PriorityBuffer (int capacity, 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 zero
comparator the comparator used to order the elements, null means use natural order
Throws
IllegalArgumentException if capacity is <= 0

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 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

public PriorityBuffer (int capacity, boolean ascendingOrder, 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 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

Public Methods

public boolean add (Object element)

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
Returns
  • true always

public void clear ()

Clears all elements from the buffer.

public Comparator comparator ()

Gets the comparator being used for this buffer, null is natural order.

Returns
  • the comparator in use, null is natural order

public Object get ()

Gets the next element to be removed without actually removing it (peek).

Returns
  • the next element
Throws
BufferUnderflowException if the buffer is empty

public boolean isAscendingOrder ()

Checks whether the heap is ascending or descending order.

Returns
  • true if ascending order (a min heap)

public Iterator iterator ()

Returns an iterator over this heap's elements.

Returns
  • an iterator over this heap's elements

public Object remove ()

Gets and removes the next element (pop).

Returns
  • the next element
Throws
BufferUnderflowException if the buffer is empty

public int size ()

Returns the number of elements in this buffer.

Returns
  • the number of elements in this buffer

public String toString ()

Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.

Returns
  • a string representation of this heap

Protected Methods

protected int compare (Object a, Object b)

Compares two objects using the comparator if specified, or the natural order otherwise.

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

protected void grow ()

Increases the size of the heap to support additional elements

protected boolean isAtCapacity ()

Tests if the buffer is at capacity.

Returns
  • true if buffer is full; false otherwise.

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

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

protected void percolateUpMaxHeap (Object element)

Percolates a new element up heap from the bottom.

Assume it is a maximum heap.

Parameters
element the element

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

protected void percolateUpMinHeap (Object element)

Percolates a new element up heap from the bottom.

Assumes it is a minimum heap.

Parameters
element the element

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