|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.set.DirectAddressing<E>
public class DirectAddressing<E>
This data structure provides excellent performance, but O(|U|) space is required. This data structure is the best choice when at least a quarter of the elements in the universe U are expected to be held in the collection. When n is expected to be much smaller than |U|/4, then either separate chaining or open addressing should be used.
Nested Class Summary | |
---|---|
static class |
DirectAddressing.DirectAddressingHasher<E>
The direct addressing hasher allocates slot 0 for the null element and adds one to each of the naturally computed hash codes for the elements. |
protected class |
DirectAddressing.Marker
|
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection |
---|
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator |
Field Summary |
---|
Fields inherited from class goldman.collection.AbstractCollection |
---|
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version |
Constructor Summary | |
---|---|
|
DirectAddressing(int capacity)
Creates a hash table with the specified capacity (plus one to handle null values), and with the default comparator and direct addressing hasher |
protected |
DirectAddressing(int capacity,
Comparator<? super E> comp)
Creates a hash table with the specified capacity (plus one to handle null values), and with the given comparator and default direct addressing hasher |
protected |
DirectAddressing(int capacity,
double load,
Comparator<? super E> equivalenceTester,
Hasher<? super E> hasher)
Creates a hash table with the specified capacity (plus one to handle null values), and with the given comparator and hasher |
Method Summary | |
---|---|
void |
add(E element)
If an equivalent element x is in the set,
then element replaces x |
void |
clear()
Removes all elements from the collection. |
boolean |
contains(E element)
This implementation for contains takes linear time, so it
is overridden by a more efficient method in most data structure
implementations. |
void |
ensureCapacity(int capacity)
Increases the capacity of the collection, if necessary, to ensure that it can hold at least capacity elements. |
int |
getCapacity()
By default this method returns Integer.MAX_VALUE . |
E |
getEquivalentElement(E target)
Returns an element in the collection that is equivalent to target . |
Locator<E> |
getLocator(E value)
Returns a locator that has been initialized to an element equivalent to target . |
Locator<E> |
iterator()
Creates a new marker that is placed at FORE |
boolean |
remove(E element)
Removes from this collection an arbitrary element equivalent to target , if such an element exists
in the collection. |
void |
trimToSize()
Trims the capacity of this collection to be its current size. |
Methods inherited from class goldman.collection.AbstractCollection |
---|
accept, addAll, checkRep, compare, equivalent, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, traverseForVisitor, writeElements |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Methods inherited from interface goldman.collection.Collection |
---|
accept, addAll, checkRep, getComparator, getSize, isEmpty, retainAll, toArray, toArray, toString |
Constructor Detail |
---|
protected DirectAddressing(int capacity, double load, Comparator<? super E> equivalenceTester, Hasher<? super E> hasher)
capacity
- the desired capacityequivalenceTester
- the comparator that defines equivalence of objectshasher
- the user-supplied hash code computation
IllegalArgumentException
- capacity
< 0.protected DirectAddressing(int capacity, Comparator<? super E> comp)
capacity
- the desired capacitycomp
- the comparator that defines equivalence of objects
IllegalArgumentException
- capacity
< 0.public DirectAddressing(int capacity)
capacity
- the desired capacity
IllegalArgumentException
- capacity
< 0.Method Detail |
---|
public int getCapacity()
AbstractCollection
Integer.MAX_VALUE
.
getCapacity
in interface Collection<E>
getCapacity
in class AbstractCollection<E>
public boolean contains(E element)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
element
- the target
public E getEquivalentElement(E target)
Collection
target
. It
throws a NoSuchElementException
when there is no equivalent
element. The contains
method should be used to
determine if an element is in the collection.
getEquivalentElement
in interface Collection<E>
getEquivalentElement
in class AbstractCollection<E>
target
- the target element
NoSuchElementException
- there is no equivalent element in the
collection.public void ensureCapacity(int capacity)
AbstractCollection
capacity
elements.
ensureCapacity
in interface Collection<E>
ensureCapacity
in class AbstractCollection<E>
capacity
- the desired capacity for the collection
UnsupportedOperationException
- it
is called for direct addressingpublic void trimToSize()
AbstractCollection
trimToSize
in interface Collection<E>
trimToSize
in class AbstractCollection<E>
UnsupportedOperationException
- it
is called for direct addressingpublic void add(E element)
x
is in the set,
then element
replaces x
add
in interface Collection<E>
element
- the element to add to the set
IllegalHashCodeException
- hashCode
is
not a valid slot in the table.public boolean remove(E element)
Collection
target
, if such an element exists
in the collection. It
returns true
if an element was removed, and false
otherwise.
remove
in interface Collection<E>
element
- the element (if it exists) to be remove from the set
public void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public Locator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public Locator<E> getLocator(E value)
Collection
target
. Like the iterator
method, this method enables
navigation, but from a specified starting point. This method
throws a NoSuchElementException
if there is no equivalent element
in the collection.
getLocator
in interface Collection<E>
value
- the target
NoSuchElementException
- there is no equivalent element in this set.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |