jist.runtime
Class Scheduler.Heap

java.lang.Object
  jist.runtime.Scheduler
      jist.runtime.Scheduler.Heap

Enclosing class:

Scheduler

static final class Scheduler.Heap
extends Scheduler

Implements an array-based heap of Events. In addition to the regular heap functionality, there are methods for extracting elements other than the min.

Since:

JIST1.0

Version:

$Id: Scheduler.java,v 1.14 2005/03/13 16:11:54 barr Exp $

Author:

Rimon Barr <barr+jist@cs.cornell.edu>

Nested Class Summary

Nested classes/interfaces inherited from class jist.runtime.Scheduler

Scheduler.Calendar, Scheduler.Heap

Field Summary

private int	halveSize Collapse size.
static int	INIT_LENGTH Initial size of internal heap array.
private Event[]	items Internal array of heap items.
private int	size Number of elements in heap.

Constructor Summary

Scheduler.Heap()
Create a new, empty heap with given comparator.

Method Summary

private void	doubleCapacity() Double the capacity of the internal array.
private void	halveCapacity() Halve the capacity of the internal array.
private void	heapify(int i) Establish heap order in internal array from given index.
void	insert(Event ev) Insert event into event queue.
boolean	isEmpty() Return whether event queue is empty.
private int	left(int i) Find left child location in heap-ordered array.
private int	parent(int i) Find parent location in heap-ordered array.
Event	peekFirst() Peek at first event in queue.
Event	removeFirst() Remove first event in queue.
Event	removeIndex(int i) Return the element stored a given location in the internal heap array and remove it from the heap.
private int	right(int i) Find right child location in heap-ordered array.
int	size() Return size of event queue.
private void	swap(int i, int j) Swap data in two array locations.

Methods inherited from class jist.runtime.Scheduler

clear, main

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

INIT_LENGTH

public static final int INIT_LENGTH

Initial size of internal heap array.

See Also:

Constant Field Values

items

private Event[] items

Internal array of heap items.

size

private int size

Number of elements in heap.

halveSize

private int halveSize

Collapse size.

Constructor Detail

Scheduler.Heap

public Scheduler.Heap()

Create a new, empty heap with given comparator.

Method Detail

parent

private int parent(int i)

Find parent location in heap-ordered array.

Parameters:

i - location to find parent of

Returns:

parent location

left

private int left(int i)

Find left child location in heap-ordered array.

Parameters:

i - location to find left child of

Returns:

left child location

right

private int right(int i)

Find right child location in heap-ordered array.

Parameters:

i - location to find right child of

Returns:

right child location

swap

private void swap(int i,
                  int j)

Swap data in two array locations.

Parameters:

i - first location

j - second location

insert

public void insert(Event ev)

Insert event into event queue.

Specified by:

insert in class Scheduler

Parameters:

ev - event to insert

size

public int size()

Return size of event queue.

Specified by:

size in class Scheduler

Returns:

number of events in event queue

isEmpty

public boolean isEmpty()

Return whether event queue is empty.

Specified by:

isEmpty in class Scheduler

Returns:

whether event queue is empty

peekFirst

public Event peekFirst()

Peek at first event in queue.

Specified by:

peekFirst in class Scheduler

Returns:

first event (still) in queue

removeFirst

public Event removeFirst()

Remove first event in queue.

Specified by:

removeFirst in class Scheduler

Returns:

first event (removed) from queue

removeIndex

public Event removeIndex(int i)

Return the element stored a given location in the internal heap array and remove it from the heap.

Parameters:

i - index into the internal heap array

Returns:

datum object removed from heap

heapify

private void heapify(int i)

Establish heap order in internal array from given index.

Parameters:

i - index into internal heap array

doubleCapacity

private void doubleCapacity()

Double the capacity of the internal array.

halveCapacity

private void halveCapacity()

Halve the capacity of the internal array.