heaps.generic
Class GenericHeap<E>

java.lang.Object
  heaps.generic.GenericHeap<E>

Type Parameters:

E - the type of all heap elements

All Implemented Interfaces:

Heap<E>

Direct Known Subclasses:

DuplicateGenericHeap, EventHeap, FastGenericHeap, SingletonGenericHeap

public abstract class GenericHeap<E>
extends java.lang.Object
implements Heap<E>

An extension of the Heap interface that provides methods for adding, removing, and querying the membership of heap elements. Whether duplicates are allowed, as well as the running time of the add, contains, and remove methods, is dependent on the backing implementation. An object of type E is said to be a duplicate of some other object if the equals method between them returns true.

Author:

Michael Parker

Method Summary

abstract boolean	add(E element) Adds the object element to the heap.
abstract boolean	allowsDuplicates() Returns whether this heap allows duplicate elements.
abstract boolean	contains(E element) Returns whether the heap contains the argument element.
java.util.Comparator<? super E>	getComparator() Returns the comparator associated with this heap, or null if it uses its elements' natural ordering.
abstract boolean	remove(E element) Finds the object in the heap equal to element, removes it, and returns true.

Methods inherited from class java.lang.Object

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

Methods inherited from interface heaps.Heap

clear, extract, getSize, isEmpty, top

Method Detail

getComparator

public final java.util.Comparator<? super E> getComparator()

Returns the comparator associated with this heap, or null if it uses its elements' natural ordering.

Returns:

the associated comparator

add

public abstract boolean add(E element)

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.

Parameters:

element - the object to add to the heap

Returns:

true if element is added, false otherwise

contains

public abstract boolean contains(E element)

Returns whether the heap contains the argument element.

Parameters:

element - the element to query for membership in the heap

Returns:

true if element is in the heap, false otherwise

remove

public abstract boolean remove(E element)

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.

Parameters:

element - the element to remove from the heap

Returns:

true if element is removed, false otherwise

allowsDuplicates

public abstract boolean allowsDuplicates()

Returns whether this heap allows duplicate elements.

Returns:

true if this heap permits duplicates, false otherwise