org.apache.avalon.cornerstone.blocks.scheduler
Class BinaryHeap

java.lang.Object
  extended by org.apache.avalon.cornerstone.blocks.scheduler.BinaryHeap
All Implemented Interfaces:
PriorityQueue

public final class BinaryHeap
extends java.lang.Object
implements PriorityQueue

BinaryHeap implementation of priority queue. The heap is either a minimum or maximum heap as determined by parameters passed to constructor.

Since:
4.0
Version:
CVS $Revision: 1.1 $ $Date: 2004/03/16 12:49:52 $
Author:
Avalon Development Team

Nested Class Summary
private static class BinaryHeap.MaxComparator
           
private static class BinaryHeap.MinComparator
           
 
Field Summary
private static int DEFAULT_CAPACITY
           
private static java.util.Comparator DEFAULT_COMPARATOR
           
private  java.util.Comparator m_comparator
           
private  java.lang.Object[] m_elements
           
private  int m_size
           
static java.util.Comparator MAX_COMPARATOR
          Comparator used to instantiate a max heap - assumes contents implement the Comparable interface.
static java.util.Comparator MIN_COMPARATOR
          Comparator used to instantiate a min heap - assumes contents implement the Comparable interface.
 
Constructor Summary
BinaryHeap()
          Instantiates a new min binary heap with the default initial capacity.
BinaryHeap(boolean isMinHeap)
          Create a binary heap of Comparables.
BinaryHeap(java.util.Comparator comparator)
          Instantiates a new binary heap with the default initial capacity and ordered using the given Comparator.
BinaryHeap(int capacity)
          Instantiates a new min binary heap with the given initial capacity.
BinaryHeap(int capacity, boolean isMinHeap)
          Create a binary heap of Comparables.
BinaryHeap(int capacity, java.util.Comparator comparator)
          Instantiates a new binary heap with the given initial capacity and ordered using the given Comparator.
 
Method Summary
 void clear()
          Clear all elements from queue.
private  void grow()
          Grows the heap by a factor of 2.
 void insert(java.lang.Object element)
          Insert an element into queue.
 boolean isEmpty()
          Test if queue is empty.
 boolean isFull()
          Test if queue is full.
 java.lang.Object peek()
          Return element on top of heap but don't remove it.
private  void percolateDownHeap(int index)
          Percolate element down heap from top.
private  void percolateUpHeap(java.lang.Object element)
          Percolate element up heap from bottom.
 java.lang.Object pop()
          Return element on top of heap and remove it.
 int size()
          Returns the number of elements currently on the heap.
 java.lang.String toString()
          Create a string representing heap and all elements in heap.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

MIN_COMPARATOR

public static final java.util.Comparator MIN_COMPARATOR
Comparator used to instantiate a min heap - assumes contents implement the Comparable interface.


MAX_COMPARATOR

public static final java.util.Comparator MAX_COMPARATOR
Comparator used to instantiate a max heap - assumes contents implement the Comparable interface.


DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY
See Also:
Constant Field Values

DEFAULT_COMPARATOR

private static final java.util.Comparator DEFAULT_COMPARATOR

m_size

private int m_size

m_elements

private java.lang.Object[] m_elements

m_comparator

private java.util.Comparator m_comparator
Constructor Detail

BinaryHeap

public BinaryHeap()
Instantiates a new min binary heap with the default initial capacity.


BinaryHeap

public BinaryHeap(int capacity)
Instantiates a new min binary heap with the given initial capacity.

Parameters:
capacity - the size of the heap

BinaryHeap

public BinaryHeap(java.util.Comparator comparator)
Instantiates a new binary heap with the default initial capacity and ordered using the given Comparator.

Parameters:
comparator - to order the contents of the heap

BinaryHeap

public BinaryHeap(int capacity,
                  java.util.Comparator comparator)
Instantiates a new binary heap with the given initial capacity and ordered using the given Comparator.

Parameters:
capacity - the size of the heap
comparator - to order the contents of the heap

BinaryHeap

public BinaryHeap(boolean isMinHeap)
Create a binary heap of Comparables. Takes a parameter to specify whether it is a minimum or maximum heap.

Parameters:
isMinHeap - true to make it a minimum heap, false to make it a max heap

BinaryHeap

public BinaryHeap(int capacity,
                  boolean isMinHeap)
Create a binary heap of Comparables. Takes a parameter to specify whether it is a minimum or maximum heap and another parameter to specify the size of the heap.

Parameters:
capacity - the size of the heap
isMinHeap - true to make it a minimum heap, false to make it a max heap
Method Detail

clear

public void clear()
Clear all elements from queue.

Specified by:
clear in interface PriorityQueue

isEmpty

public boolean isEmpty()
Test if queue is empty.

Specified by:
isEmpty in interface PriorityQueue
Returns:
true if queue is empty else false.

isFull

public boolean isFull()
Test if queue is full.

Returns:
true if queue is full else false.

size

public int size()
Returns the number of elements currently on the heap.

Returns:
the size of the heap.

insert

public void insert(java.lang.Object element)
Insert an element into queue.

Specified by:
insert in interface PriorityQueue
Parameters:
element - the element to be inserted

peek

public java.lang.Object peek()
                      throws java.util.NoSuchElementException
Return element on top of heap but don't remove it.

Specified by:
peek in interface PriorityQueue
Returns:
the element at top of heap
Throws:
java.util.NoSuchElementException - if isEmpty() == true

pop

public java.lang.Object pop()
                     throws java.util.NoSuchElementException
Return element on top of heap and remove it.

Specified by:
pop in interface PriorityQueue
Returns:
the element at top of heap
Throws:
java.util.NoSuchElementException - if isEmpty() == true

percolateDownHeap

private void percolateDownHeap(int index)
Percolate element down heap from top.

Parameters:
index - the index of element

percolateUpHeap

private void percolateUpHeap(java.lang.Object element)
Percolate element up heap from bottom.

Parameters:
element - the element

grow

private void grow()
Grows the heap by a factor of 2.


toString

public java.lang.String toString()
Create a string representing heap and all elements in heap.

Overrides:
toString in class java.lang.Object
Returns:
the string representing heap