|
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 INodeSet
n
- Board state to be inserted.public INode remove()
comp
as the comparator.
remove
in interface INodeSet
public boolean isEmpty()
INodeSet
isEmpty
in interface INodeSet
public int size()
INodeSet
size
in interface INodeSet
public java.util.Iterator<INode> iterator()
INodeSet
iterator
in interface INodeSet
public INode contains(INode n)
contains
in interface INodeSet
n
- 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 INodeSet
n
- 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 |