|
Algorithm Development Kit 1.0 |
||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Objectalgs.model.searchtree.states.StateTree
public class StateTree
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.
| 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 |
|---|
public StateTree()
| Method Detail |
|---|
public void insert(INode n)
insert in interface INodeSetn - Board state to be inserted.public INode remove()
comp as the comparator.
remove in interface INodeSetpublic boolean isEmpty()
INodeSet
isEmpty in interface INodeSetpublic int size()
INodeSet
size in interface INodeSetpublic java.util.Iterator<INode> iterator()
INodeSet
iterator in interface INodeSetpublic INode contains(INode n)
contains in interface INodeSetn - the node whose score is to be used when searching.public boolean remove(INode n)
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.
remove in interface INodeSetn - the node representing the value to be removed from the setINodeSet.remove(INode)
|
Algorithm Development Kit 1.0 | ||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||