heaps.event
Class FastEventHeap<T>

java.lang.Object
  extended by heaps.generic.GenericHeap<TimeAssociation<T>>
      extended by heaps.event.EventHeap<T>
          extended by heaps.event.FastEventHeap<T>
Type Parameters:
T - the type of all heap elements
All Implemented Interfaces:
Heap<TimeAssociation<T>>

public class FastEventHeap<T>
extends EventHeap<T>

A implementation of the EventHeap interface that executes all methods it defines in O(lg N) time. These methods are faster than their counterparts implemented in ArrayBackedEventHeap because heap elements are mapped to their position in the backing array using a HashMap.

Author:
Michael Parker

Constructor Summary
FastEventHeap()
           
 
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.
 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.
 
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

FastEventHeap

public FastEventHeap()
Method Detail

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>>
Parameters:
element - the object to add to the heap
Returns:
true if element is added, 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>
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

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>
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

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>
Parameters:
element - the element to query for in the heap
Returns:
true if a TimeAssociation exists associated with element, false otheriwse

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>
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

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>>
Parameters:
element - the element to query for membership in the heap
Returns:
true if element is in the heap, false otherwise

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>>
Parameters:
element - the element to remove from the heap
Returns:
true if element is removed, false otherwise

allowsDuplicates

public boolean allowsDuplicates()
Description copied from class: GenericHeap
Returns whether this heap allows duplicate elements.

Specified by:
allowsDuplicates in class GenericHeap<TimeAssociation<T>>
Returns:
true if this heap permits duplicates, false otherwise

clear

public void clear()
Description copied from interface: Heap
Removes all elements from the heap.


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.

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.

Returns:
the top element removed from the heap

getSize

public int getSize()
Description copied from interface: Heap
Returns the number of elements in the heap.

Returns:
the number of heap elements

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.

Returns:
true if the heap is empty, false otherwise