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_ |
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.
alma.ACS.jbaci.Heap.Heap | ( | int | capacity, | |
Comparator | cmp | |||
) | throws IllegalArgumentException |
Create a Heap with the given initial capacity and comparator
capacity | initial capacity. | |
cmp | comparator instance. |
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.
capacity | initial capacity. |
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.
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.
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.
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 | ( | ) |
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().