Algorithm
Development Kit 1.0

algs.model.searchtree
Interface INode

All Superinterfaces:
IGraphEntity
All Known Implementing Classes:
EightPuzzleNode, FifteenPuzzleNode

public interface INode
extends IGraphEntity

A valid representation of the node within a search tree.

To enable extensibility, different Search Tree variations can store an additional piece of information with a search node. It is stored as an Object and can be retrieved or set.

To support the efficient operation of the contains method within INodeStorage, classes that implement this interface must provide a suitable Object.hashCode() implementation.

The equals operator must properly compare states solely on the information contained in the state (and not in the storedData). To play nicely with INodeSet classes that uses StateStorageFactory.HASH as the storage method, make sure that Object.hashCode() is implemented otherwise you may encounter strange behavior. Note that there is no way to enforce that the INode implementing class actually provides this method; you are warned.

To support debugging, this interface extends IGraphEntity.

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

Nested Class Summary
 
Nested classes/interfaces inherited from interface algs.debug.IGraphEntity
IGraphEntity.Formatter
 
Method Summary
 INode copy()
          Enable one to grab a copy of this board state.
 boolean equivalent(INode state)
          Determine if this board state is equivalent to the given state.
 java.lang.Object key()
          Computes to a key value such that if two board states have the exact same key, then the board states are equivalent.
 int score()
          Evaluate the board state according to the scoring function and return an integer score.
 void score(int s)
          Set the score for this node.
 java.lang.Object storedData()
          Retrieve additional specific information stored with this search tree.
 java.lang.Object storedData(java.lang.Object o)
          Store additional information with this search tree, returning the old information that had been stored (if at all).
 DoubleLinkedList<IMove> validMoves()
          Return an ordered list of moves that can be made on this board state.
 
Methods inherited from interface algs.debug.IGraphEntity
nodeLabel
 

Method Detail

validMoves

DoubleLinkedList<IMove> validMoves()
Return an ordered list of moves that can be made on this board state.


score

void score(int s)
Set the score for this node.

Values are interpreted by the search algorithm being used. One common convention is that values closer to zero reflect board states that are closer to the goal state.

A score of zero might represent a solved solution, but that is up to the designer of the IScore evaluation function.


score

int score()
Evaluate the board state according to the scoring function and return an integer score.

Values are interpreted by the search algorithm being used. One common convention is that values closer to zero reflect board states that are closer to the goal state.

A score of zero might represent a solved solution, but that is up to the designer of the IScore evaluation function.


copy

INode copy()
Enable one to grab a copy of this board state.

Note that the storedData with the state is not copied.


equivalent

boolean equivalent(INode state)
Determine if this board state is equivalent to the given state. The notion of equivalence is based upon the actual game. For games that exhibit symmetries in board state (such as board games), you can get great savings simply by reducing symmetrical positions. At the same time, the large number of positions might make it prohibitively expensive to store all unique positions. Useful when attempting to reduce the search space.

Parameters:
state - State in question

key

java.lang.Object key()
Computes to a key value such that if two board states have the exact same key, then the board states are equivalent.

If a board state chooses not to implement a sophisticated function, then the implementing class should return 'this' as the implementation.


storedData

java.lang.Object storedData(java.lang.Object o)
Store additional information with this search tree, returning the old information that had been stored (if at all).

Returns the prior object that had been stored with the node.

Parameters:
o - object to store with the INode object.

storedData

java.lang.Object storedData()
Retrieve additional specific information stored with this search tree.


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.