Package org.apache.commons.collections.buffer

Class PriorityBuffer

java.lang.Object
java.util.AbstractCollection
org.apache.commons.collections.buffer.PriorityBuffer
All Implemented Interfaces:
Serializable, Iterable, Collection, Buffer
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 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.

Since:
Commons Collections 3.0 (previously BinaryHeap v1.0)
Version:
$Revision: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $
Author:
Peter Donald, Ram Chidambaram, Michael A. Smith, Paul Jack, Stephen Colebourne, Steve Phelps
See Also:

  • Field Details

    • elements

      protected 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 Comparator comparator
      The comparator used to order the elements

  • Constructor Details

    • PriorityBuffer

      public PriorityBuffer()
      Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added.

    • PriorityBuffer

      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

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

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

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

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

    • PriorityBuffer

      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

  • Method Details

    • isAscendingOrder

      public boolean isAscendingOrder()
      Checks whether the heap is ascending or descending order.
      Returns:
      true if ascending order (a min heap)

    • comparator

      public 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 interface Collection
      Specified by:
      size in class AbstractCollection
      Returns:
      the number of elements in this buffer

    • clear

      public void clear()
      Clears all elements from the buffer.
      Specified by:
      clear in interface Collection
      Overrides:
      clear in class AbstractCollection

    • add

      public boolean add(Object element)
      Adds an element to the buffer.

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

      Specified by:
      add in interface Collection
      Overrides:
      add in class AbstractCollection
      Parameters:
      element - the element to be added
      Returns:
      true always

    • get

      public Object get()
      Gets the next element to be removed without actually removing it (peek).
      Specified by:
      get in interface Buffer
      Returns:
      the next element
      Throws:
      BufferUnderflowException - if the buffer is empty

    • remove

      public Object remove()
      Gets and removes the next element (pop).
      Specified by:
      remove in interface Buffer
      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(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(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(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

    • grow

      protected void grow()
      Increases the size of the heap to support additional elements

    • iterator

      public Iterator iterator()
      Returns an iterator over this heap's elements.
      Specified by:
      iterator in interface Collection
      Specified by:
      iterator in interface Iterable
      Specified by:
      iterator in class AbstractCollection
      Returns:
      an iterator over this heap's elements

    • toString

      public String toString()
      Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.
      Overrides:
      toString in class AbstractCollection
      Returns:
      a string representation of this heap