|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object heaps.generic.GenericHeap<TimeAssociation<T>> heaps.event.EventHeap<T> heaps.event.FastEventHeap<T>
T
- the type of all heap elementspublic class FastEventHeap<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
.
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 |
---|
public FastEventHeap()
Method Detail |
---|
public boolean add(TimeAssociation<T> element)
GenericHeap
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.
add
in class GenericHeap<TimeAssociation<T>>
element
- the object to add to the heap
true
if element
is added,
false
otherwisepublic boolean setNextTime(TimeAssociation<T> element, boolean do_add)
EventHeap
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.
setNextTime
in class EventHeap<T>
element
- the element to update in the heapdo_add
- if true
, then element
will be added to the
heap even if not already present
element
was either updated or addedpublic TimeAssociation<T> getNextTime(T element)
EventHeap
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
.
getNextTime
in class EventHeap<T>
element
- the element to query for in the list
TimeAssociation
whose event is equal to
argument event
, or null
if none existspublic boolean containsElement(T element)
EventHeap
TimeAssociation
in the heap
that is associated with the given element
parameter.
containsElement
in class EventHeap<T>
element
- the element to query for in the heap
true
if a TimeAssociation
exists
associated with element
, false
otheriwsepublic TimeAssociation<T> removeNextTime(T element)
EventHeap
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
.
removeNextTime
in class EventHeap<T>
element
- the element to remove from the list
TimeAssociation
that was removed from the
heap, or null
if the list remains unchangedpublic boolean contains(TimeAssociation<T> element)
GenericHeap
element
.
contains
in class GenericHeap<TimeAssociation<T>>
element
- the element to query for membership in the heap
true
if element
is in the heap,
false
otherwisepublic boolean remove(TimeAssociation<T> element)
GenericHeap
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.
remove
in class GenericHeap<TimeAssociation<T>>
element
- the element to remove from the heap
true
if element
is removed,
false
otherwisepublic boolean allowsDuplicates()
GenericHeap
allowsDuplicates
in class GenericHeap<TimeAssociation<T>>
true
if this heap permits duplicates,
false
otherwisepublic void clear()
Heap
public TimeAssociation<T> top()
Heap
Comparable
. If the heap is
empty, null
is returned.
public TimeAssociation<T> extract()
Heap
Comparable
. If the
heap is empty, null
is returned.
public int getSize()
Heap
public boolean isEmpty()
Heap
true
if the heap is empty, false
otherwise. This is equivalent to returning true if and only if
getSize
returns 0
.
true
if the heap is empty, false
otherwise
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |