Orbital library

orbital.algorithm.template
Class GeneralSearch.OptionIterator

java.lang.Object
  extended by 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.

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.