jdsl.core.ref
Class HashtableDictionary

java.lang.Object
  |
  +--jdsl.core.ref.AbstractDictionary
        |
        +--jdsl.core.ref.HashtableDictionary
All Implemented Interfaces:
Container, Dictionary, InspectableContainer, InspectableDictionary, InspectableKeyBasedContainer, KeyBasedContainer, java.io.Serializable

public class HashtableDictionary
extends AbstractDictionary
implements Dictionary, java.io.Serializable

An implementation of Dictionary using a chaining hashtable. Elements are inserted at the front of each chain, to ensure a constant time bound (disregarding resizing overhead).

The chains have references to both the next and previous element in the chains to make remove(Locator) guaranteed constant time (again, disregarding resizing overhead).

In the time complexities listed for the methods, O(1) is constant time, O(N) is time proportional to the number of elements in the data structure, and O(C) is time proportional to the capacity of the data structure.

Version:
$Id: HashtableDictionary.java,v 1.13 2000/02/14 11:13:53 lv Exp $
Author:
Mike Boilen (mgb) , Benoit Hudson (bh) , Ryan Shaun Baker (rsb) , Keith Schmidt (kas)
See Also:
Serialized Form

Inner classes inherited from class jdsl.core.api.InspectableDictionary
InspectableDictionary.InvalidLocator
 
Fields inherited from interface jdsl.core.api.InspectableDictionary
NO_SUCH_KEY
 
Constructor Summary
HashtableDictionary(HashComparator comp)
          This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more.
HashtableDictionary(HashComparator comp, int initCap)
          This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more, and an integer denoting the initial capacity.
 
Method Summary
 boolean contains(Accessor acc)
          O(1)
 ObjectIterator elements()
          O(1) if structure *AND* elements haven't changed, O(N) otherwise.
 Locator find(java.lang.Object key)
          O(1) -- expected, O(N) worst case with excessive chaining.
 LocatorIterator findAll(java.lang.Object key)
          O(#elts with target key), worst case O(N)
 Locator insert(java.lang.Object key, java.lang.Object value)
          O(1) expected, O(N) if insertion pushes the size above the rehashing threshhold.
 boolean isEmpty()
          O(1)
 ObjectIterator keys()
          O(1) if structure hasn't changed, O(N) otherwise.
 LocatorIterator locators()
          O(1) if structure hasn't changed, O(N) otherwise.
 Container newContainer()
          O(1)
 void remove(Locator loc)
          O(1) expected: strictly O(1) unless removal reduces size below the downhashing threshhold, in which case it is O(N)
 LocatorIterator removeAll(java.lang.Object key)
          O(#elts with target key) expected, worst case O(N) with excessive chaining, or if removeAll drops the size below the downhashing threshhold.
 Locator removeKey(java.lang.Object key)
          Removes the first element found with the given key from the hashtable.
 java.lang.Object replaceElement(Accessor acc, java.lang.Object Element)
          O(1)
 java.lang.Object replaceKey(Locator loc, java.lang.Object key)
          O(1)
 int size()
          O(1)
 java.lang.String toString()
          O(N) human readable description of the contents of this dictionary, conforming to the Collections spec for key-element structures.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

HashtableDictionary

public HashtableDictionary(HashComparator comp)
This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more.

HashtableDictionary

public HashtableDictionary(HashComparator comp,
                           int initCap)
This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more, and an integer denoting the initial capacity.
Method Detail

size

public final int size()
O(1)
Specified by:
size in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
Number of elements stored by the container.

isEmpty

public boolean isEmpty()
O(1)
Specified by:
isEmpty in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
true if and only if the container is empty (holds no elements)
See Also:
InspectableBinaryTree

replaceElement

public java.lang.Object replaceElement(Accessor acc,
                                       java.lang.Object Element)
O(1)
Specified by:
replaceElement in interface Container
Following copied from interface: jdsl.core.api.Container
Parameters:
a - Accessor in this container
newElement - to be stored at a
Returns:
old element, previously stored at a
Throws:
InvalidAccessorException - if a is null or does not belong to this container

newContainer

public Container newContainer()
O(1)
Specified by:
newContainer in interface Container
Following copied from interface: jdsl.core.api.Container
Returns:
A new, empty Container of the same class as this one.

contains

public boolean contains(Accessor acc)
O(1)
Specified by:
contains in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Throws:
InvalidAccessorException - if a is null

remove

public void remove(Locator loc)
            throws InvalidAccessorException
O(1) expected: strictly O(1) unless removal reduces size below the downhashing threshhold, in which case it is O(N)
Specified by:
remove in interface KeyBasedContainer
Following copied from interface: jdsl.core.api.KeyBasedContainer
Parameters:
loc - a locator in the container to remove
Throws:
InvalidAccessorException - if the locator is not valid or is not contained by this container

replaceKey

public java.lang.Object replaceKey(Locator loc,
                                   java.lang.Object key)
O(1)
Specified by:
replaceKey in interface KeyBasedContainer
Following copied from interface: jdsl.core.api.KeyBasedContainer
Parameters:
loc - the locator in the container whose key should be replaced
key - the new key to associate with loc.
Returns:
The old key
Throws:
InvalidAccessorException - If the locator is not valid or is not contained by this container
InvalidKeyException - If key cannot be used by this container

locators

public LocatorIterator locators()
O(1) if structure hasn't changed, O(N) otherwise.
Specified by:
locators in interface InspectableKeyBasedContainer
Following copied from interface: jdsl.core.api.InspectableKeyBasedContainer
Returns:
a LocatorIterator over all of the locators in the container

keys

public ObjectIterator keys()
O(1) if structure hasn't changed, O(N) otherwise.
Specified by:
keys in interface InspectableKeyBasedContainer
Following copied from interface: jdsl.core.api.InspectableKeyBasedContainer
Returns:
an iterator over all the keys stored in this container

elements

public ObjectIterator elements()
O(1) if structure *AND* elements haven't changed, O(N) otherwise.
Specified by:
elements in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
an iterator over all the elements stored in this container

findAll

public LocatorIterator findAll(java.lang.Object key)
                        throws InvalidKeyException
O(#elts with target key), worst case O(N)
Specified by:
findAll in interface InspectableDictionary
Following copied from interface: jdsl.core.api.InspectableDictionary
Parameters:
key - The key to search for.
Returns:
A LocatorIterator over the set of (key, element) pairs whose keys match the parameter key
Throws:
InvalidKeyException - if the specified key is not valid in this container

removeAll

public LocatorIterator removeAll(java.lang.Object key)
O(#elts with target key) expected, worst case O(N) with excessive chaining, or if removeAll drops the size below the downhashing threshhold.
Specified by:
removeAll in interface Dictionary
Following copied from interface: jdsl.core.api.Dictionary
Parameters:
key - the key to search for
Returns:
a LocatorIterator over the (key, element) pairs whose keys match the parameter key
Throws:
InvalidKeyException - if the specified key is not a valid key in this container

removeKey

public Locator removeKey(java.lang.Object key)
                  throws InvalidKeyException
Removes the first element found with the given key from the hashtable. O(1) -- expected. will be O(N) with excessive chaining or if removal reduces below the downhashing threshhold.
Throws:
InvalidKeyException - if the key cannot be compared

insert

public Locator insert(java.lang.Object key,
                      java.lang.Object value)
               throws InvalidKeyException
O(1) expected, O(N) if insertion pushes the size above the rehashing threshhold.
Specified by:
insert in interface KeyBasedContainer
Following copied from interface: jdsl.core.api.KeyBasedContainer
Parameters:
key - the key associated with the specified element.
element - the element to insert into the container.
Returns:
a locator associated with the inserted pair.
Throws:
InvalidKeyException - if key cannot be used by this container

find

public Locator find(java.lang.Object key)
             throws InvalidKeyException
O(1) -- expected, O(N) worst case with excessive chaining.
Specified by:
find in interface InspectableDictionary
Following copied from interface: jdsl.core.api.InspectableDictionary
Parameters:
key - The key mapped to search for.
Returns:
The Locator referring to the key-element pair that was found, or NO_SUCH_KEY if it could not be found.
Throws:
InvalidKeyException - if the specified key is not a valid key in this container.
See Also:
InspectableDictionary.NO_SUCH_KEY

toString

public java.lang.String toString()
O(N) human readable description of the contents of this dictionary, conforming to the Collections spec for key-element structures.
Overrides:
toString in class java.lang.Object