alma.ACS.jbaci.Heap Class Reference

List of all members.

Public Member Functions
	Heap (int capacity, Comparator cmp) throws IllegalArgumentException
	Heap (int capacity)
synchronized void	insert (Object x)
synchronized Object	extract ()
synchronized Object	peek ()
synchronized int	size ()
synchronized void	clear ()
Protected Member Functions
int	compare (Object a, Object b)
final int	parent (int k)
final int	left (int k)
final int	right (int k)
Protected Attributes
Object[]	nodes_
int	count_ = 0
final Comparator	cmp_

---

Detailed Description

A heap-based priority queue. The class currently uses a standard array-based heap, as described in, for example, Sedgewick's Algorithms text. All methods are fully synchronized.

---

Constructor & Destructor Documentation

alma.ACS.jbaci.Heap.Heap	(	int	capacity,
		Comparator	cmp
	)			throws IllegalArgumentException

Create a Heap with the given initial capacity and comparator

Parameters:

	capacity	initial capacity.
	cmp	comparator instance.

Exceptions:

IllegalArgumentException

if capacity less or equal to zero

References alma.ACS.jbaci.Heap.cmp_, and alma.ACS.jbaci.Heap.nodes_.

alma.ACS.jbaci.Heap.Heap

(

int

capacity

)

Create a Heap with the given capacity, and relying on natural ordering.

Parameters:

capacity

initial capacity.

---

Member Function Documentation

synchronized void alma.ACS.jbaci.Heap.clear

(

)

Remove all elements.

References alma.ACS.jbaci.Heap.count_, and alma.ACS.jbaci.Heap.nodes_.

Referenced by alma.ACS.jbaci.BACITimer.shutDown().

int alma.ACS.jbaci.Heap.compare	(	Object	a,
		Object	b
	)			[protected]

Perform element comparisons using comparator or natural ordering.

References alma.ACS.jbaci.Heap.cmp_.

Referenced by alma.ACS.jbaci.Heap.extract(), and alma.ACS.jbaci.Heap.insert().

synchronized Object alma.ACS.jbaci.Heap.extract

(

)

Return and remove least element, or null if empty.

Returns:

extraced least element.

References alma.ACS.jbaci.Heap.compare(), alma.ACS.jbaci.Heap.count_, alma.ACS.jbaci.Heap.left(), alma.ACS.jbaci.Heap.nodes_, and alma.ACS.jbaci.Heap.right().

Referenced by alma.ACS.jbaci.BACITimer.nextTask().

synchronized void alma.ACS.jbaci.Heap.insert

(

Object

x

)

Insert an element, resize if necessary.

Parameters:

x

object to insert.

References alma.ACS.jbaci.Heap.compare(), alma.ACS.jbaci.Heap.count_, alma.ACS.jbaci.Heap.nodes_, and alma.ACS.jbaci.Heap.parent().

Referenced by alma.ACS.jbaci.BACITimer.executeAfterDelay(), alma.ACS.jbaci.BACITimer.executeAt(), alma.ACS.jbaci.BACITimer.executePeriodically(), and alma.ACS.jbaci.BACITimer.nextTask().

final int alma.ACS.jbaci.Heap.left

(

int

k

)

[protected]

Get left child.

Referenced by alma.ACS.jbaci.Heap.extract().

final int alma.ACS.jbaci.Heap.parent

(

int

k

)

[protected]

Get parent index.

Referenced by alma.ACS.jbaci.Heap.insert().

synchronized Object alma.ACS.jbaci.Heap.peek

(

)

Return least element without removing it, or null if empty.

Returns:

least element.

References alma.ACS.jbaci.Heap.count_, and alma.ACS.jbaci.Heap.nodes_.

Referenced by alma.ACS.jbaci.BACITimer.nextTask().

final int alma.ACS.jbaci.Heap.right

(

int

k

)

[protected]

Get right child.

Referenced by alma.ACS.jbaci.Heap.extract().

synchronized int alma.ACS.jbaci.Heap.size

(

)

Return number of elements.

Returns:

number of elements.

References alma.ACS.jbaci.Heap.count_.

---

Member Data Documentation

final Comparator alma.ACS.jbaci.Heap.cmp_ [protected]

Ordering comparator.

Referenced by alma.ACS.jbaci.Heap.compare(), and alma.ACS.jbaci.Heap.Heap().

int alma.ACS.jbaci.Heap.count_ = 0 [protected]

Number of used slots.

Referenced by alma.ACS.jbaci.Heap.clear(), alma.ACS.jbaci.Heap.extract(), alma.ACS.jbaci.Heap.insert(), alma.ACS.jbaci.Heap.peek(), and alma.ACS.jbaci.Heap.size().

Object [] alma.ACS.jbaci.Heap.nodes_ [protected]

The tree nodes, packed into an array.

Referenced by alma.ACS.jbaci.Heap.clear(), alma.ACS.jbaci.Heap.extract(), alma.ACS.jbaci.Heap.Heap(), alma.ACS.jbaci.Heap.insert(), and alma.ACS.jbaci.Heap.peek().

---

The documentation for this class was generated from the following file:

• Heap.java