Opus5
Class OpenScatterTable

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractSearchableContainer
                    |
                    +--Opus5.AbstractHashTable
                          |
                          +--Opus5.OpenScatterTable

All Implemented Interfaces:

Comparable, Container, HashTable, SearchableContainer

Direct Known Subclasses:

OpenScatterTableV2

public class OpenScatterTable

extends AbstractHashTable

Open scatter table implemented using an array.

Version:

$Id: OpenScatterTable.java,v 3.2 1998/07/28 02:24:04 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

See Also:

HashTable

Inner Class Summary

protected static class

OpenScatterTable.Entry Entry data structure.

Field Summary

protected OpenScatterTable.Entry[]

array An array of entries.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.HashTable

copyright

Constructor Summary

OpenScatterTable(int length)
Constructs an OpenScatterTable with the specified length.

Method Summary

void	accept(Visitor visitor) Accepts the specified visitor and makes it visit all the objects in this open scatter table.
protected static int	c(int i) Implements the linear-probing collision resolution strategy.
protected int	compareTo(Comparable arg) Compares this open scatter table with the specified comparable object.
Comparable	find(Comparable object) Finds an object in this open scatter table that matches the specified object.
protected int	findInstance(Comparable object) Finds the position of the specified object in this open scatter table.
protected int	findMatch(Comparable object) Finds the position of an object in this open scatter table that matches the given object.
protected int	findUnoccupied(java.lang.Object object) Finds the position of an unoccupied entry into which the specified object can be stored.
Enumeration	getEnumeration() Returns an enumeration that enumerates the objects in this open scatter table.
int	getLength() Returns the length of this open scatter table.
void	insert(Comparable object) Inserts the specified comparable object into this open scatter table.
boolean	isFull() Tests if this open scatter table is full.
boolean	isMember(Comparable object) Tests whether the specified object is contained in this open scatter table.
void	purge() Purges this open scatter table, making it empty.
void	withdraw(Comparable object) Withdraws the specified object from this open scatter table.

Methods inherited from class Opus5.AbstractHashTable

f, g, getLoadFactor, h

Methods inherited from class Opus5.AbstractContainer

getCount, hashCode, isEmpty, toString

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Container

getCount, isEmpty

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

array

protected OpenScatterTable.Entry[] array

An array of entries.

Constructor Detail

OpenScatterTable

public OpenScatterTable(int length)

Constructs an OpenScatterTable with the specified length.

Parameters:

length - The desired length.

Method Detail

getLength

public int getLength()

Returns the length of this open scatter table.

Overrides:

getLength in class AbstractHashTable

Returns:

the length of this open scatter table.

purge

public void purge()

Purges this open scatter table, making it empty.

isFull

public boolean isFull()

Tests if this open scatter table is full.

Overrides:

isFull in class AbstractContainer

Returns:

True if this open scatter table is full; false otherwise.

accept

public void accept(Visitor visitor)

Accepts the specified visitor and makes it visit all the objects in this open scatter table.

Overrides:

accept in class AbstractContainer

Parameters:

visitor - The visitor to accept.

c

protected static int c(int i)

Implements the linear-probing collision resolution strategy.

Parameters:

i - The probe number.

Returns:

The ith position to probe.

findUnoccupied

protected int findUnoccupied(java.lang.Object object)

Finds the position of an unoccupied entry into which the specified object can be stored.

Parameters:

object - The object to be stored.

Returns:

The position of an unoccupied entry.

Throws:

ContainerFullException - If the open scatter table is full.

insert

public void insert(Comparable object)

Inserts the specified comparable object into this open scatter table.

Parameters:

object - The object to insert.

Throws:

ContainerFullException - If this open scatter table is full.

findMatch

protected int findMatch(Comparable object)

Finds the position of an object in this open scatter table that matches the given object.

Parameters:

object - The object to match.

Returns:

The position of the matching object; -1 if no match.

find

public Comparable find(Comparable object)

Finds an object in this open scatter table that matches the specified object.

Parameters:

object - The object to match.

Returns:

The object in this open scatter table that matches the specified object; null if no match.

findInstance

protected int findInstance(Comparable object)

Finds the position of the specified object in this open scatter table.

Parameters:

object - The object for which to look.

Returns:

The position of the specified object; -1 if it is not in the table.

withdraw

public void withdraw(Comparable object)

Withdraws the specified object from this open scatter table.

Parameters:

object - The object to be withdrawn.

Throws:

ContainerEmptyException - If this open scatter table is empty.

java.lang.IllegalArgumentException - If the specified object is not in this open scatter table.

isMember

public boolean isMember(Comparable object)

Tests whether the specified object is contained in this open scatter table.

Parameters:

object - The object for which to look.

Returns:

True if the specified object is in this open scatter table; false otherwise.

getEnumeration

public Enumeration getEnumeration()

Returns an enumeration that enumerates the objects in this open scatter table.

Returns:

An enumeration that enumerates the objects in this open scatter table.

compareTo

protected int compareTo(Comparable arg)

Compares this open scatter table with the specified comparable object. This method is not implemented.

Overrides:

compareTo in class AbstractObject

Parameters:

arg - The object with which this open scatter table is compared.

Throws:

MethodNotImplemented - Always.