heaps.event.hierarchy
Class BetweenHeap<T extends HeapChild>

java.lang.Object
  heaps.generic.GenericHeap<TimeAssociation<T>>
      heaps.event.EventHeap<T>
          heaps.event.hierarchy.BetweenHeap<T>

Type Parameters:

T - all heap objects are of time TimeAssociation<T>

All Implemented Interfaces:

HeapChild, HeapParent<T>, Heap<TimeAssociation<T>>

public class BetweenHeap<T extends HeapChild>
extends EventHeap<T>
implements HeapParent<T>, HeapChild

A wrapper for a EventHeap object, allowing it to be presented as both a timer (by implementing interface HeapChild, enabling it to be added into other heaps), and a heap into which timers can be added (by implementing interface HeapParent). In a hierarchy of this timers, instances of this class are used between the root and any leaf.

Author:

Michael Parker

Constructor Summary

BetweenHeap(HeapParent<HeapChild> _hp, EventHeap<T> _h)
Creates a new wrapper for a TimedHeap object, allowing it to be used as an intermediate node along a hierarchy of heaps.

Method Summary

boolean	add(TimeAssociation<T> element) Adds the object element to the heap.
boolean	allowsDuplicates() Returns whether this heap allows duplicate elements.
void	clear() Removes all elements from the heap.
boolean	contains(TimeAssociation<T> element) Returns whether the heap contains the argument element.
boolean	containsElement(T element) Returns whether there exists a TimeAssociation in the heap that is associated with the given element parameter.
TimeAssociation<T>	extract() Extracts the next element from the heap.
TimeAssociation<T>	getNextTime(T element) Returns the first TimeAssociation in the heap that is associated with the given element parameter.
int	getSize() Returns the number of elements in the heap.
boolean	isEmpty() Returns true if the heap is empty, false otherwise.
void	process(long curr_time) This callback method is invoked when the heap that this timer is part of has determined that the timer has expired.
boolean	remove(T element) This method is invoked by a timer when it wishes to remove itself from the heap, so that its process method is never invoked.
boolean	remove(TimeAssociation<T> element) Finds the object in the heap equal to element, removes it, and returns true.
TimeAssociation<T>	removeNextTime(T element) Returns and removes the first TimeAssociation in the heap that is associated with the given element parameter.
boolean	setNextTime(TimeAssociation<T> element, boolean do_add) Substitues the given parameter for the first TimeAssociation in the heap that is associated with the object returned by method getObject of the parameter.
TimeAssociation<T>	top() Returns the next object element to be extracted from the heap without actually removing it from the heap.
void	update(TimeAssociation<T> element) This method is invoked by a timer when it wishes to add itself to the heap, or when it wishes to change the time at which it should be invoked.

Methods inherited from class heaps.generic.GenericHeap

getComparator

Methods inherited from class java.lang.Object

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

Constructor Detail

BetweenHeap

public BetweenHeap(HeapParent<HeapChild> _hp,
                   EventHeap<T> _h)

Creates a new wrapper for a TimedHeap object, allowing it to be used as an intermediate node along a hierarchy of heaps.

Parameters:

_hp - the parent heap in which this object should insert itself as a timer, as needed

_h - the TimedHeap object to wrap as both a timer and a heap for timers

Method Detail

clear

public void clear()

Description copied from interface: Heap

Removes all elements from the heap.

Specified by:

clear in interface Heap<TimeAssociation<T extends HeapChild>>

add

public boolean add(TimeAssociation<T> element)

Description copied from class: GenericHeap

Adds the object element to the heap. If the implementing heap allows duplicates, element is always added to the heap and this method returns true. If the implementing heap does not allow duplicates, element is added and method returns true only if no duplicate of element exists in the heap. Otherwise, if a duplicate exists in the heap and none are allowed, this method returns false and the heap remains unchanged.

Specified by:

add in class GenericHeap<TimeAssociation<T extends HeapChild>>

Parameters:

element - the object to add to the heap

Returns:

true if element is added, false otherwise

top

public TimeAssociation<T> top()

Description copied from interface: Heap

Returns the next object element to be extracted from the heap without actually removing it from the heap. If the heap is non-empty, this value returned must be the smallest of all objects in the heap, as determined by the natural ordering of Comparable. If the heap is empty, null is returned.

Specified by:

top in interface Heap<TimeAssociation<T extends HeapChild>>

Returns:

the top element in the heap

extract

public TimeAssociation<T> extract()

Description copied from interface: Heap

Extracts the next element from the heap. If the heap is non-empty, the value returned must be the smallest of all objects in the heap, as determined by the natural ordering of Comparable. If the heap is empty, null is returned.

Specified by:

extract in interface Heap<TimeAssociation<T extends HeapChild>>

Returns:

the top element removed from the heap

containsElement

public boolean containsElement(T element)

Description copied from class: EventHeap

Returns whether there exists a TimeAssociation in the heap that is associated with the given element parameter.

Specified by:

containsElement in class EventHeap<T extends HeapChild>

Parameters:

element - the element to query for in the heap

Returns:

true if a TimeAssociation exists associated with element, false otheriwse

contains

public boolean contains(TimeAssociation<T> element)

Description copied from class: GenericHeap

Returns whether the heap contains the argument element.

Specified by:

contains in class GenericHeap<TimeAssociation<T extends HeapChild>>

Parameters:

element - the element to query for membership in the heap

Returns:

true if element is in the heap, false otherwise

getSize

public int getSize()

Description copied from interface: Heap

Returns the number of elements in the heap.

Specified by:

getSize in interface Heap<TimeAssociation<T extends HeapChild>>

Returns:

the number of heap elements

getNextTime

public TimeAssociation<T> getNextTime(T element)

Description copied from class: EventHeap

Returns the first TimeAssociation in the heap that is associated with the given element parameter. That is, of all the TimeAssociation elements that are associated with the given parameter, the one returned has the smallest value returned by method getTime. If no such element exists, this method returns null.

Specified by:

getNextTime in class EventHeap<T extends HeapChild>

Parameters:

element - the element to query for in the list

Returns:

the first TimeAssociation whose event is equal to argument event, or null if none exists

isEmpty

public boolean isEmpty()

Description copied from interface: Heap

Returns true if the heap is empty, false otherwise. This is equivalent to returning true if and only if getSize returns 0.

Specified by:

isEmpty in interface Heap<TimeAssociation<T extends HeapChild>>

Returns:

true if the heap is empty, false otherwise

setNextTime

public boolean setNextTime(TimeAssociation<T> element,
                           boolean do_add)

Description copied from class: EventHeap

Substitues the given parameter for the first TimeAssociation in the heap that is associated with the object returned by method getObject of the parameter. Thus, if the object returned by method getObject is only present once in the heap, this method is equivalent to updating its time. If no such TimeAssociation object exists, this method has the same effect as calling method add(element) in interface GenericHeap if flag do_add is true; otherwise, this method returns false and has no effect.

Specified by:

setNextTime in class EventHeap<T extends HeapChild>

Parameters:

element - the element to update in the heap

do_add - if true, then element will be added to the heap even if not already present

Returns:

if element was either updated or added

allowsDuplicates

public boolean allowsDuplicates()

Description copied from class: GenericHeap

Returns whether this heap allows duplicate elements.

Specified by:

allowsDuplicates in class GenericHeap<TimeAssociation<T extends HeapChild>>

Returns:

true if this heap permits duplicates, false otherwise

removeNextTime

public TimeAssociation<T> removeNextTime(T element)

Description copied from class: EventHeap

Returns and removes the first TimeAssociation in the heap that is associated with the given element parameter. That is, of all the TimeAssociation elements that are associated with the given parameter, the one removed has the smallest value returned by method getTime. If no such element exists, the heap remains unchanged and this method returns null.

Specified by:

removeNextTime in class EventHeap<T extends HeapChild>

Parameters:

element - the element to remove from the list

Returns:

the TimeAssociation that was removed from the heap, or null if the list remains unchanged

remove

public boolean remove(TimeAssociation<T> element)

Description copied from class: GenericHeap

Finds the object in the heap equal to element, removes it, and returns true. If no such object exists, this method returns false and the heap remains unchanged. Note that if duplicates are allowed in the heap, any one of the duplicates of element could be removed.

Specified by:

remove in class GenericHeap<TimeAssociation<T extends HeapChild>>

Parameters:

element - the element to remove from the heap

Returns:

true if element is removed, false otherwise

process

public void process(long curr_time)

Description copied from interface: HeapChild

This callback method is invoked when the heap that this timer is part of has determined that the timer has expired. The current time, or argument curr_time, should be no less than the time at which this timer asked to be invoked.

Specified by:

process in interface HeapChild

Parameters:

curr_time - the current time, in milliseconds

update

public void update(TimeAssociation<T> element)

Description copied from interface: HeapParent

This method is invoked by a timer when it wishes to add itself to the heap, or when it wishes to change the time at which it should be invoked.

Specified by:

update in interface HeapParent<T extends HeapChild>

Parameters:

element - the timer to add or update in the heap

remove

public boolean remove(T element)

Description copied from interface: HeapParent

This method is invoked by a timer when it wishes to remove itself from the heap, so that its process method is never invoked.

Specified by:

remove in interface HeapParent<T extends HeapChild>

Parameters:

element - the timer to remove from the heap

Returns:

true if element is successfully removed from the heap, false otherwise