Algorithm
Development Kit 1.0

algs.model.searchtree.states
Class StateTree

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

public class StateTree
extends java.lang.Object
implements INodeSet

Maintains the set of open states in ordered fashion, using the score() as the ordering value.

Because multiple nodes may have the same score, the remove(INode) and contains(INode) methods will act strangely to the outside world. They only care about the score; thus it may be possible there will be two boards with the same score and the request to remove(INode) will actually remove a different node with the same score. It is thus recommended not to use the remove(INode) method on StateTree.

INodeSet.insert(INode) and INodeSet.remove(INode) are O(log n) operations where n is the size of the balanced binary tree. INodeSet.remove() removes the INode with minimum INode.key() value, so this is typically not that useful during the evaluation of a search. After all, the key is reflective of the board state, not the evaluation of the board state (as would be found in INode.score() for example).

This state variation is not suitable to use as the Closed Set for any of the searching algorithms, since you won't determine whether a board has been discovered before; rather you will find whether a board with the same score has been seen before.

Author:
George Heineman

Constructor Summary
StateTree()
          Construct Binary tree to use.
 
Method Summary
 INode contains(INode n)
          Locate element within the set whose score is the same.
 void insert(INode n)
          Insert the board state into the tree.
 boolean isEmpty()
          Is collection empty.
 java.util.Iterator<INode> iterator()
          Return iterator to the existing board states.
 INode remove()
          Return INode with minimum score value since tree was constructed using comp as the comparator.
 boolean remove(INode n)
          Remove actual value from the set whose score is the same.
 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
 

Constructor Detail

StateTree

public StateTree()
Construct Binary tree to use. Allow duplicates in the tree.

Method Detail

insert

public void insert(INode n)
Insert the board state into the tree.

Specified by:
insert in interface INodeSet
Parameters:
n - Board state to be inserted.

remove

public INode remove()
Return INode with minimum score value since tree was constructed using comp as the comparator.

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 within the set whose score is the same.

Specified by:
contains in interface INodeSet
Parameters:
n - the node whose score is to be used when searching.

remove

public boolean remove(INode n)
Remove actual value from the set whose score is the same.

The score from the INode passed in is used to locate the desired INode within the set. As such, the behavior of this method may be surprising since you could have two nodes in the tree with the same score and one of them will be removed, though you won't know exactly which one.

Specified by:
remove in interface INodeSet
Parameters:
n - the node representing the value to be removed from the set
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.