Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.commons.collections.buffer
Class PriorityBuffer

    java.lang.Object
      |
      +--java.util.AbstractCollection
            |
            +--org.apache.commons.collections.buffer.PriorityBuffer

All Implemented Interfaces:
  Buffer, Collection

public class PriorityBuffer
extends AbstractCollection
implements Buffer

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());

Since:
  Commons Collections 3.0 (previously BinaryHeap v1.0)
Version:
  $Revision: 1.5 $ $Date: 2004/05/15 12:33:23 $
Author:
  Peter Donald, Ram Chidambaram, Michael A. Smith, Paul Jack, Stephen Colebourne

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

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

Methods inherited from interface java.util.Collection
`addAll, contains, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray`

Field Detail

### 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 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(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 Detail

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

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2001-2004 Apache Software Foundation. All Rights Reserved.