edu.buffalo.nsf.xmlcqa.data.dtd
Class RegExpr

java.lang.Object
  extended byedu.buffalo.nsf.xmlcqa.data.dtd.NDFA
      extended byedu.buffalo.nsf.xmlcqa.data.dtd.RegExpr
All Implemented Interfaces:
Constants
Direct Known Subclasses:
Clousure, Concat, Tag, Union

public abstract class RegExpr
extends NDFA

An abstract class facilitating construction of regular expressions. The semantics of regular expression is expressed by means of nondeterministic finite automata. Therefore this class extends NDFA. Also this class allows to delegate construction of all methods specified by NDFA by implementing four of it abstract methods: _getStateCount(), _fillFinalStates(boolean[] f , int offset), _fillDelta(boolean[][][] delta, int offset), and _fillEpsilonDelta(boolean[][] epsilon, int offset). Three of those methods have a parameter offset, which facilitates structural composition of regular expressions. An object implementing those methods should assume that numbers of its states start with the value offset.

The values specified by abstract methods in NDFA are memoized once they have been computed. Should the value of the parameters change, the vlaues will be recomputed.

Author:
staworko

Field Summary
 
Fields inherited from class edu.buffalo.nsf.xmlcqa.data.dtd.NDFA
EPSILON
 
Fields inherited from interface edu.buffalo.nsf.xmlcqa.Constants
INF
 
Constructor Summary
RegExpr()
           
 
Method Summary
protected abstract  void _fillDelta(boolean[][][] delta, int offset)
          Used to fill tag driven part of the transition table of a regular expression whose position if relative to offset.
protected abstract  void _fillEpsilonDelta(boolean[][] delta, int offset)
          Used to fill epsilon part of the transition talbe of a regular expressio whose possition is relative to offset.
protected abstract  void _fillFinalStates(boolean[] f, int offset)
          Used to indicate final states of a regular expression whose position is relative to offset.
protected abstract  int _getStateCount()
          Should return the number of states the implementation is using.
 boolean[][][] getDelta()
          Returns the tag controled part of the transition relation.
 boolean[][] getEpsilonDelta()
          Returns the epsilon part of the transition relation.
 boolean[] getFinalStates()
          Returns a boolean vector specifying final states.
 int[][][] getFstIndTrDelta(DTD d)
          Returns a two dimensional array containing vectors of suffixes of the cheapest paths between each pair of vertices.
 Tag[][][] getFstTagTrDelta(DTD d)
          Returns a two dimentional array containing vectors of suffizes of labels of the cheapest paths between each pair of vertices.
 int[][] getMinCostDelta(DTD d)
          Returns an array containing costs of cheapest paths between every pari of states.
 int getStateCount()
          Returns the number of states used by the underlying NDFA.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

RegExpr

public RegExpr()
Method Detail

_fillDelta

protected abstract void _fillDelta(boolean[][][] delta,
                                   int offset)
Used to fill tag driven part of the transition table of a regular expression whose position if relative to offset. The implementing class doesn't have indicate transitions obtained in a consequence of clousure under epsilon transition. This clousure will be computed automatically by this class.


_fillEpsilonDelta

protected abstract void _fillEpsilonDelta(boolean[][] delta,
                                          int offset)
Used to fill epsilon part of the transition talbe of a regular expressio whose possition is relative to offset. The implementing class doesn't have indicate transitions obtained in the consequence of the clousure. This clousure will be computed by this class.


_fillFinalStates

protected abstract void _fillFinalStates(boolean[] f,
                                         int offset)
Used to indicate final states of a regular expression whose position is relative to offset.


_getStateCount

protected abstract int _getStateCount()
Should return the number of states the implementation is using. This method will be executed only once and its result stored and returned with each call of getStateCount() method (memoization).


getDelta

public boolean[][][] getDelta()
Description copied from class: NDFA
Returns the tag controled part of the transition relation. getDelta()[t][i][j] is true if and only if there is transition with a tag of identifier equal to t, from the state i to the state j

Specified by:
getDelta in class NDFA

getEpsilonDelta

public boolean[][] getEpsilonDelta()
Description copied from class: NDFA
Returns the epsilon part of the transition relation. getEpsilonDelta()[i][j] is true if and only if there is an epsilon transition from the state i to the state j.

Specified by:
getEpsilonDelta in class NDFA

getFinalStates

public boolean[] getFinalStates()
Description copied from class: NDFA
Returns a boolean vector specifying final states. A state i is final if and only if getFinalStates()[i] is true.

Specified by:
getFinalStates in class NDFA

getFstIndTrDelta

public int[][][] getFstIndTrDelta(DTD d)
Description copied from class: NDFA
Returns a two dimensional array containing vectors of suffixes of the cheapest paths between each pair of vertices.

Specified by:
getFstIndTrDelta in class NDFA

getFstTagTrDelta

public Tag[][][] getFstTagTrDelta(DTD d)
Description copied from class: NDFA
Returns a two dimentional array containing vectors of suffizes of labels of the cheapest paths between each pair of vertices.

Specified by:
getFstTagTrDelta in class NDFA

getMinCostDelta

public int[][] getMinCostDelta(DTD d)
Description copied from class: NDFA
Returns an array containing costs of cheapest paths between every pari of states. The costs of the edges depend on the values of DTD.getMinTreeSize(Tag).

Specified by:
getMinCostDelta in class NDFA

getStateCount

public int getStateCount()
Description copied from class: NDFA
Returns the number of states used by the underlying NDFA. The states are number with indexes 0 and higher (similar to arrays).

Specified by:
getStateCount in class NDFA