goldman.collection.set
Class DirectAddressing<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.set.DirectAddressing<E>
All Implemented Interfaces:
Collection<E>, Set<E>, Iterable<E>
Direct Known Subclasses:
OpenAddressing

public class DirectAddressing<E>
extends AbstractCollection<E>
implements Set<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

DirectAddressing

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

Parameters:
capacity - the desired capacity
equivalenceTester - the comparator that defines equivalence of objects
hasher - the user-supplied hash code computation
Throws:
IllegalArgumentException - capacity < 0.

DirectAddressing

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

Parameters:
capacity - the desired capacity
comp - the comparator that defines equivalence of objects
Throws:
IllegalArgumentException - capacity < 0.

DirectAddressing

public 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

Parameters:
capacity - the desired capacity
Throws:
IllegalArgumentException - capacity < 0.
Method Detail

getCapacity

public int getCapacity()
Description copied from class: AbstractCollection
By default this method returns Integer.MAX_VALUE.

Specified by:
getCapacity in interface Collection<E>
Overrides:
getCapacity in class AbstractCollection<E>
Returns:
the capacity of the collection

contains

public boolean contains(E element)
Description copied from class: AbstractCollection
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
element - the target
Returns:
true if and only if an equivalent element exists in the collection

getEquivalentElement

public E getEquivalentElement(E target)
Description copied from interface: Collection
Returns an element in the collection that is equivalent to 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.

Specified by:
getEquivalentElement in interface Collection<E>
Overrides:
getEquivalentElement in class AbstractCollection<E>
Parameters:
target - the target element
Returns:
an equivalent element that is in the collection
Throws:
NoSuchElementException - there is no equivalent element in the collection.

ensureCapacity

public void ensureCapacity(int capacity)
Description copied from class: AbstractCollection
Increases the capacity of the collection, if necessary, to ensure that it can hold at least capacity elements.

Specified by:
ensureCapacity in interface Collection<E>
Overrides:
ensureCapacity in class AbstractCollection<E>
Parameters:
capacity - the desired capacity for the collection
Throws:
UnsupportedOperationException - it is called for direct addressing

trimToSize

public void trimToSize()
Description copied from class: AbstractCollection
Trims the capacity of this collection to be its current size. An application can use this operation to minimize space usage.

Specified by:
trimToSize in interface Collection<E>
Overrides:
trimToSize in class AbstractCollection<E>
Throws:
UnsupportedOperationException - it is called for direct addressing

add

public void add(E element)
If an equivalent element x is in the set, then element replaces x

Specified by:
add in interface Collection<E>
Parameters:
element - the element to add to the set
Throws:
IllegalHashCodeException - hashCode is not a valid slot in the table.

remove

public boolean remove(E element)
Description copied from interface: Collection
Removes from this collection an arbitrary element equivalent to target, if such an element exists in the collection. It returns true if an element was removed, and false otherwise.

Specified by:
remove in interface Collection<E>
Parameters:
element - the element (if it exists) to be remove from the set
Returns:
true if and only if the element had been in the set and was therefore removed

clear

public void clear()
Removes all elements from the collection.

Specified by:
clear in interface Collection<E>
Overrides:
clear in class AbstractCollection<E>

iterator

public Locator<E> iterator()
Creates a new marker that is placed at FORE

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

getLocator

public Locator<E> getLocator(E value)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to 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.

Specified by:
getLocator in interface Collection<E>
Parameters:
value - the target
Returns:
a marker initialized at an equivalent element in the set
Throws:
NoSuchElementException - there is no equivalent element in this set.