com.mhhe.clrs2e
Class DirectAddressTable

java.lang.Object
  |
  +--com.mhhe.clrs2e.DirectAddressTable

All Implemented Interfaces:

Dictionary

public class DirectAddressTable

extends java.lang.Object

implements Dictionary

Implements a direct-address table from page 222 of Introduction to Algorithms, Second edition. Indices into the direct-address table are based on the Java hashCode method applied to objects, modulo the table size.

Field Summary

private int	m The number of entries in the direct-address table.
private java.lang.Object[]	table The direct-address table.

Constructor Summary

DirectAddressTable(int m)
Creates a new direct-address table of a given size.

Method Summary

void	delete(java.lang.Object handle) Removes an element from a direct-address table.
private int	indexOf(java.lang.Comparable k) Returns the index into the direct-address table at which an element is placed.
java.lang.Object	insert(java.lang.Comparable o) Inserts an element into a direct-address table.
java.lang.Object	search(java.lang.Comparable k) Searches for an element with a given key in a direct-address table.

Methods inherited from class java.lang.Object

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

Field Detail

table

private java.lang.Object[] table

The direct-address table. An object with key k is stored in table[k].

m

private int m

The number of entries in the direct-address table.

Constructor Detail

DirectAddressTable

public DirectAddressTable(int m)

Creates a new direct-address table of a given size.

Parameters:

m - The size of the direct-address table.

Method Detail

insert

public java.lang.Object insert(java.lang.Comparable o)

Inserts an element into a direct-address table.

Specified by:

insert in interface Dictionary

Parameters:

o - The element to insert.

Returns:

A handle to the new element. The handle is the object that is inserted.

delete

public void delete(java.lang.Object handle)

Removes an element from a direct-address table.

Specified by:

delete in interface Dictionary

Parameters:

handle - A handle to the element to remove.

Throws:

java.lang.ClassCastException - if handle does not reference an object that implements Comparable.

search

public java.lang.Object search(java.lang.Comparable k)

Searches for an element with a given key in a direct-address table.

Specified by:

search in interface Dictionary

Parameters:

k - The key being searched for.

Returns:

A handle to the object found, or null if there is no match.

indexOf

private int indexOf(java.lang.Comparable k)

Returns the index into the direct-address table at which an element is placed. If the element implements DynamicSetElement, the hash code of the element's key is used. Otherwise, the hash code of the element itself is used. In any case, the hash code is taken modulo the table size.

Returns:

The index into the direct-address table.