orbital.algorithm.template
Class GeneralSearch.OptionIterator

java.lang.Object
  orbital.algorithm.template.GeneralSearch.OptionIterator

All Implemented Interfaces:

java.io.Serializable, java.util.Iterator

Direct Known Subclasses:

BestFirstSearch.OptionIterator, BreadthFirstSearch.OptionIterator, DepthFirstSearch.OptionIterator

Enclosing class:

GeneralSearch

public abstract static class GeneralSearch.OptionIterator
extends java.lang.Object
implements java.util.Iterator, java.io.Serializable

Abstract implementation base class for iterators determining the traversal order. Concrete implementations define the traversal order for the state space by providing an iterator over the state options of a search graph (as induced by a state-model).

Although it is not required that option iterators extend this class, it usually comes as a great relief since sub classes will not have to deal with too much details. Full-blown option iterators only have to implement the abstract methods of this class and determine the data collection implementation maintained.

Particularly, this iterator approach has the advantage of promising that an option node will not be required again, when the next element has already been requested. Those search algorithms that have a need to keep intermediate states for later comparison, will need to remember the states themselves.

Author:

André Platzer

See Also:

Strategy, GeneralSearch.createTraversal(GeneralSearchProblem), Serialized Form

Invariants:

sub classes maintain a collection of nodes to select from

Attributes:

secret traversal order

Constructor Summary

protected

GeneralSearch.OptionIterator(GeneralSearchProblem problem) Create a traversal iterator over the problem's state options.

Method Summary

protected abstract boolean	add(java.util.Iterator newNodes) Concatenate the new nodes and the old nodes.
protected GeneralSearchProblem	getProblem() Get the current problem.
boolean	hasNext()
protected abstract boolean	isEmpty() Returns true if this iterator's collection of nodes currently does not contain any elements.
java.lang.Object	next()
void	remove() Removes from the list of exandable nodes the last element returned by the iterator.
protected abstract java.lang.Object	select() Selects an option to visit from nodes.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GeneralSearch.OptionIterator

protected GeneralSearch.OptionIterator(GeneralSearchProblem problem)

Create a traversal iterator over the problem's state options.

Sub classes must add the initial state to their internal collection of nodes, such that it will be the (single) element expanded first.

Parameters:

problem - the problem whose options to iterate in an iterator specific order.

Postconditions:

must still add problem.getInitialState() to nodes, such that !isEmpty()

Method Detail

getProblem

protected final GeneralSearchProblem getProblem()

Get the current problem.

Returns:

the problem specified in the last call to solve.

Preconditions:

true

isEmpty

protected abstract boolean isEmpty()

Returns true if this iterator's collection of nodes currently does not contain any elements.

Returns:

true if this collection contains no elements.

Postconditions:

RES == nodes.isEmpty()

select

protected abstract java.lang.Object select()

Selects an option to visit from nodes.

Returns:

the selected option after removing it from nodes.

Preconditions:

!isEmpty()

Postconditions:

OLD(nodes).contains(RES) && nodes == OLD(nodes) \ {RES}

add

protected abstract boolean add(java.util.Iterator newNodes)

Concatenate the new nodes and the old nodes. Concatenates by some algorithm-dependant means.

Parameters:

newNodes - the new nodes we apparently became aware of. (Might be modified by this method).

Returns:

true if nodes changed as a result of the call.

Postconditions:

nodes ⊆ OLD(nodes) ∪ newNodes && RES = nodes≠OLD(nodes)

hasNext

public boolean hasNext()

Specified by:

hasNext in interface java.util.Iterator

See Also:

Template Method

Preconditions:

true

next

public java.lang.Object next()

Will expand the last element returned, and select a state option to visit.

Specified by:

next in interface java.util.Iterator

See Also:

Template Method

Preconditions:

hasNext()

remove

public void remove()

Removes from the list of exandable nodes the last element returned by the iterator.

When calling this method, the last node that was returned by this iterator will be pruned and not expanded any further.

Specified by:

remove in interface java.util.Iterator

Throws:

java.lang.UnsupportedOperationException - if the remove operation is not supported by this Iterator.

java.lang.IllegalStateException - if the next method has not yet been called, or the remove method has already been called after the last call to the next method.