Package de.saar.chorus.domgraph.chart

Class SolvedFormIterator<E extends GraphBasedNonterminal>

java.lang.Object

de.saar.chorus.domgraph.chart.SolvedFormIterator<E>

All Implemented Interfaces:

Iterator<SolvedFormSpec>

public class SolvedFormIterator<E extends GraphBasedNonterminal>
extends Object
implements Iterator<SolvedFormSpec>

An iterator over the different solved forms represented by a Chart. The chart is passed to the constructor of an object of this class. Then you can iterate over the solved forms of this chart using hasNext() and next() as usual.

Each successful call to next() will return an object of class List<DomEdge>, i.e. a list of dominance edge representations. This list can e.g. be passed to the encode method of OutputCodec or one of its subclasses.

This class implements a transition system for states consisting of an agenda of subgraphs that must currently be resolved, and a stack of splits that still need to be processed. This algorithm is dramatically faster than a naive algorithm which simply computes the sets of solved forms of a graph by computing the Cartesian product of the sets of solved forms of its subgraphs, but quite a bit more complicated.

Author:

Alexander Koller, Michaela Regneri

Constructor Summary

Constructors

Constructor	Description
SolvedFormIterator(RegularTreeGrammar<E> ch, DomGraph graph)

Method Summary

Modifier and Type	Method	Description
RegularTreeGrammar<E>	getChart()
SolvedFormSpec	getSolvedForm(int sf)	This returns a solved form represented by a List of DomEdge objects.
boolean	hasNext()	convenience methods for implementing Iterator
SolvedFormSpec	next()
void	remove()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Iterator

forEachRemaining

Constructor Details

SolvedFormIterator

public SolvedFormIterator(RegularTreeGrammar<E> ch,
 DomGraph graph)

Method Details

hasNext

public boolean hasNext()

convenience methods for implementing Iterator

Specified by:

hasNext in interface Iterator<E extends GraphBasedNonterminal>

next

public SolvedFormSpec next()

Specified by:

next in interface Iterator<E extends GraphBasedNonterminal>

getSolvedForm

public SolvedFormSpec getSolvedForm(int sf)

This returns a solved form represented by a List of DomEdge objects. The form is accessed via its index. Forms with indices exceeding the range of int have to be extracted manually by calling next() as often as necessary.

Parameters:

sf - index of the solved form to extract

Returns:

the solved form

remove

public void remove()

Specified by:

remove in interface Iterator<E extends GraphBasedNonterminal>

getChart

public RegularTreeGrammar<E> getChart()