Algorithm
Development Kit 1.0

algs.model.searchtree.states
Class StateHash

java.lang.Object
  extended by algs.model.searchtree.states.StateHash
All Implemented Interfaces:
INodeSet

public class StateHash
extends java.lang.Object
implements INodeSet

Maintains the set of open states using a Hash.

INodeSet.insert(INode) and INodeSet.remove(INode) can be essentially linear if the Object.hashCode() function for INode properly distributes the potential set of INode objects uniformly. Note that remove is unsupported in this context because there is no clear interpretation that makes external sense. The Hashtable constructed to store the states could return the INode objects in an implementation-specific way, but that would not be testable under any circumstance.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
static int initialCapacity
          Initial capacity.
 
Constructor Summary
StateHash()
          Construct hash to store INode objects.
 
Method Summary
 INode contains(INode n)
          Locate element stored in set that equals n.
 void insert(INode n)
          Insert a node into the hash.
 boolean isEmpty()
          Is collection empty.
 java.util.Iterator<INode> iterator()
          Return iterator to the existing board states.
 INode remove()
          Not supported since it makes no sense in this context.
 boolean remove(INode n)
          Remove actual entry from the set.
 int size()
          Return the number of states in the set.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

initialCapacity

public static int initialCapacity
Initial capacity. Settable for debugging purposes.

Constructor Detail

StateHash

public StateHash()
Construct hash to store INode objects.

Method Detail

insert

public void insert(INode n)
Insert a node into the hash.

Specified by:
insert in interface INodeSet
Parameters:
n -

remove

public INode remove()
Not supported since it makes no sense in this context.

Specified by:
remove in interface INodeSet

isEmpty

public boolean isEmpty()
Description copied from interface: INodeSet
Is collection empty.

Specified by:
isEmpty in interface INodeSet

size

public int size()
Description copied from interface: INodeSet
Return the number of states in the set.

Specified by:
size in interface INodeSet

iterator

public java.util.Iterator<INode> iterator()
Description copied from interface: INodeSet
Return iterator to the existing board states.

Specified by:
iterator in interface INodeSet

contains

public INode contains(INode n)
Locate element stored in set that equals n. Using the hashCode method for the INode to locate the proper hash bucket and then the equals check is performed. Thus this method only works if the INode implementation properly codes Object.equals(Object) and Object.hashCode().

Specified by:
contains in interface INodeSet
Parameters:
n - target node to be searched for

remove

public boolean remove(INode n)
Remove actual entry from the set.

The INode passed in must be an actual value returned by INodeSet.contains(INode).

Specified by:
remove in interface INodeSet
Parameters:
n - the node representing the entry to be removed.
See Also:
INodeSet.remove(INode)

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.