|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object heaps.generic.GenericHeap<E> heaps.generic.SingletonGenericHeap<E>
E
- the type of all heap objects.public class SingletonGenericHeap<E>
An implementation of interface GenericHeap
that does not allow
duplicates. This means that before an element is inserted using
add
, the backing array must be searched for duplicates;
method add
and all other methods of GenericHeap
that depend on the implementation thus take O(N) time.
Constructor Summary | |
---|---|
SingletonGenericHeap()
Creates a new heap with the backing array having an initial size of 16. |
|
SingletonGenericHeap(java.util.Comparator<? super E> _comp)
Creates a new heap with the backing array having an initial size of 16. |
|
SingletonGenericHeap(java.util.Comparator<? super E> _comp,
int _init_capacity)
Creates a new heap with the backing array having the specified initial size. |
|
SingletonGenericHeap(int _init_capacity)
Creates a new heap with the backing array having the specified initial size. |
Method Summary | |
---|---|
boolean |
add(E 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(E element)
Returns whether the heap contains the argument element . |
E |
extract()
Extracts the next element from the heap. |
int |
getSize()
Returns the number of elements in the heap. |
boolean |
isEmpty()
Returns true if the heap is empty, false
otherwise. |
boolean |
remove(E element)
Finds the object in the heap equal to element , removes
it, and returns true . |
E |
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 SingletonGenericHeap()
Comparable
interface and be mutually
comparable.
public SingletonGenericHeap(int _init_capacity)
Comparable
interface and be mutually comparable.
_init_capacity
- the initial size of the backing arraypublic SingletonGenericHeap(java.util.Comparator<? super E> _comp)
_comp
- the comparator used to order heap elementspublic SingletonGenericHeap(java.util.Comparator<? super E> _comp, int _init_capacity)
_comp
- the comparator used to order heap elements_init_capacity
- the initial size of the backing arrayMethod Detail |
---|
public boolean add(E 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<E>
element
- the object to add to the heap
true
if element
is added,
false
otherwisepublic boolean allowsDuplicates()
GenericHeap
allowsDuplicates
in class GenericHeap<E>
true
if this heap permits duplicates,
false
otherwisepublic void clear()
Heap
public E top()
Heap
Comparable
. If the heap is
empty, null
is returned.
public E 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
otherwisepublic boolean remove(E 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<E>
element
- the element to remove from the heap
true
if element
is removed,
false
otherwisepublic boolean contains(E element)
GenericHeap
element
.
contains
in class GenericHeap<E>
element
- the element to query for membership in the heap
true
if element
is in the heap,
false
otherwise
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |