/*
*
* Copyright (c) 2007
* Adrian Michel
* http://www.tradery.com
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Adrian Michel makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
package com.tradery.contentmodel;
import com.tradery.collections.IntegerVector;
import java.util.Hashtable;
import java.util.Dictionary;
import java.util.Enumeration;
import java.util.Stack;
import java.util.Vector;
import java.io.IOException;
import com.tradery.contract.Contract;
/**
* StateMachine - holds the state transition table
* and provides state machine functionality
* the state machine start state is always 0. Invalid transitions
*/
class StateMachineRanges implements AbstractStateMachine
{
// constants
private static final int START = 0;
private static final int NOTRANSITION = -1;
// the state transition table
private StateTable stateTable;
// indicates the final states
private FinalStates finalStates = new FinalStates();
// the name of the state machine (the name of the model too)
private final String name;
// this holds the limits for all the ranges in the state machine.
// used by the state class to create a vector of ranges
private LimitsVector lv;
/**
* a map of integers to IntegerVectors
* each integer vector has indexes to ranges that have to be
* checked when terminating through the particular state machine
* cannot use a vector because the keys are not necessarily
* contiguous
*/
static class FinalStates extends Hashtable
{
// by default, a newly constructed state machine ends on state 0
// and doesn't have any ranges
void init()
{
put( new Integer( 0 ), new IntegerVector() );
}
IntegerVector get( int n )
{
return(IntegerVector)get( new Integer( n ) );
}
public void dump()
{
try
{
ModelWriter.println( "Final states:" );
for( Enumeration e = keys(); e.hasMoreElements(); )
{
Integer i = (Integer)e.nextElement();
IntegerVector v = get( i.intValue() );
ModelWriter.print( "\t" + i.toString() + " " );
v.dump( ModelWriter.getOutputStream() );
ModelWriter.println();
}
}
catch( IOException e )
{
System.err.println( "IOException in StateMachineRanges.dump: " + e.getMessage() );
}
}
}
/**
* State - holds the current state. Used by the parser
* in the validation process to traverse the DFA graph
*/
public static class State implements AbstractState
{
// initally, the state is start
private int crtState = StateMachineRanges.START;
// the state machine to which it refers
private final StateMachineRanges sm;
// holds the ranges current info for each state: counts and limits
private RangeVector rv;
int getCrtState()
{
return crtState;
}
void setState( int _state )
{
crtState = _state;
}
// constructor - attaches it to a state machine
State( StateMachineRanges _sm, LimitsVector lv )
{
sm = _sm; rv = new RangeVector( lv );
}
// calculates the next state, based on the input symbol and the current state
public boolean doTransition( String symbol )
{
if( Contract.REQUIRE )
Contract.require( symbol != null );
return sm.transition( symbol, this );
}
public boolean isValidTransition( String symbol )
{
int oldCrtState = crtState;
RangeVector oldRv = (RangeVector)rv.clone();
boolean b = doTransition( symbol );
crtState = oldCrtState;
rv = oldRv;
return b;
}
// determines if the current state is also a final state
// which would allow the user to terminate the validation
public boolean canTerminate()
{
return sm.canTerminate( this );
}
// initializes the ranges whose indexes are in "v"
// used when a transition goes into a start range node
boolean initStart( IntegerVector v )
{
if( Contract.REQUIRE )
Contract.require( v != null );
rv.initStart( v );
return true;
}
// checks that counts are within allowed limits for ranges
// whose indexes are in "v" and then resets the counters
// used when a transition leaves a end range state (or node)
boolean checkAndReset( IntegerVector v )
{
if( Contract.REQUIRE )
Contract.require( v != null );
return rv.checkAndReset( v );
}
// check that counts are within allowed limits for ranges whose
// indexes are in "v".
boolean check( IntegerVector v )
{
if( Contract.REQUIRE )
Contract.require( v != null );
return rv.check( v );
}
boolean increment( int n )
{
return rv.increment( n );
}
public Enumeration getValidTransitions()
{
return sm.getValidSymbolsFromState( this );
}
public void dump()
{
ModelWriter.print( "State: ");
ModelWriter.print( crtState );
}
}
/**
* StateTable - the transitions table - a bidemensional matrix of symbols and states
* maps (symbol, current state) pairs to next states
* note that the states in the table are not objects of class State but pure integers,
* for performance reasons
*
*
* TODO: call this TransitionTable
*/
private static class StateTable extends Hashtable
{
// the number of states in the state machine
private final int stateNumber;
/**************************************************
* State - a row in the transition table
* it is an array of integers
*************************************************/
private static class Row
{
private static final int NOTRANSITION = -1;
// the actual row
private final Transition[] row;
// constructor
// takes the row size as argument
Row( int n )
{
// create the row
row = new Transition[ n ];
// initialize it with no transitions
for( int m = 0; m < n; m++ )
{
row[ m ] = InvalidTransition.getInvalidTransition();
}
}
// adds a transition to the row
boolean addTransition( int from, Transition transition )
{
if( Contract.REQUIRE )
{
Contract.require( transition != null );
Contract.require( from >= 0 );
}
// if there is already a valid transition there, return false
// this means the content model is not deterministic
if( !( ( Transition )row[ from ] ).canAddTransition() )
return false;
else
{
// set the new state value
row[ from ] = transition;
return true;
}
}
// returns the next transition
boolean transition( State state )
{
if( Contract.REQUIRE )
Contract.require( state != null );
return( ( Transition )row[ state.getCrtState() ] ).toNextState( state );
}
boolean isValidTransition( State state )
{
if( Contract.REQUIRE )
Contract.require( state != null );
return( ( Transition)row[ state.getCrtState() ] ).isValid();
}
public void dump()
{
for( int n = 0; n < row.length; n++ )
row[ n ].dump( n );
// ModelWriter.println();
}
}
// constructor
// sets the number of states in the state machine
StateTable( int _stateNumber )
{
stateNumber = _stateNumber;
}
// adds a transition to the table
// returns false if non-deterministic
boolean addTransition( String symbol, int from, Transition transition )
{
if( Contract.REQUIRE )
{
Contract.require( symbol != null );
Contract.require( from >= 0 );
Contract.require( transition != null );
}
Row row = (Row)get( symbol );
// if there is no row corresponding to "symbol"
// create a new row
if( row == null )
{
row = new Row( stateNumber );
put( symbol, row );
}
return row.addTransition( from, transition );
}
// calculates the next state, from the symbol and current state
boolean transition( String symbol, State state )
{
if( Contract.REQUIRE )
{
Contract.require( symbol != null );
Contract.require( state != null );
}
Row row = (Row)get( symbol );
if( row != null )
return row.transition( state );
else
return false;
}
Enumeration getValidSymbolsFromState( State state )
{
Vector v = new Vector();
for( Enumeration e = keys(); e.hasMoreElements(); )
{
String symbol = (String)e.nextElement();
Row row = (Row)get( symbol );
if( row.isValidTransition( state ) )
v.addElement( symbol );
}
return v.elements();
}
public void dump()
{
ModelWriter.println( "Transitions:" );
for( Enumeration e = keys(); e.hasMoreElements(); )
{
String symbol = (String)e.nextElement();
ModelWriter.println( "\"" + symbol + "\" " );
Row row = (Row)get( symbol );
row.dump();
}
ModelWriter.println();
}
}
// makes a new state object, to be used on this state machine
public AbstractState getInitialState()
{
// ModelWriter.println( "************* Getting the initial state ***************" );
return new State( this, lv );
}
// constructor - creates a table with the specified number of states
StateMachineRanges( String _name, int states, LimitsVector _lv )
{
if( Contract.REQUIRE )
{
Contract.require( _name != null );
Contract.require( _lv != null );
}
name = _name;
finalStates.init();
stateTable = new StateTable( states );
lv = _lv;
}
// adds a transition to the table
private boolean addTransition( String symbol, int from, Transition transition )
{
if( Contract.REQUIRE )
{
Contract.require( symbol != null );
Contract.require( from >= 0 );
Contract.require( transition != null );
}
return stateTable.addTransition( symbol, from, transition );
}
// sets the final states
private void setFinalStates( FinalStates _finalStates )
{
if( Contract.REQUIRE )
{
Contract.require( _finalStates != null );
}
finalStates = _finalStates;
}
public void setFinalStates( Object o )
{
setFinalStates( (FinalStates)o );
}
// calculates the next state
boolean transition( String symbol, State state )
{
if( Contract.REQUIRE )
{
Contract.require( symbol != null );
Contract.require( state != null );
}
return stateTable.transition( symbol, state );
}
boolean canTerminate( State state )
{
if( isFinal( state.getCrtState() ) )
// checks that all the ranges terminating in this state
// have the count within limits
return state.check( finalStates.get( state.getCrtState() ) );
else
return false;
}
// tests if a state is final
boolean isFinal( int state )
{
// ModelWriter.print( "isFinal - " + name + ": " );
boolean b = finalStates.containsKey( new Integer( state ) );
// ModelWriter.println( b );
return b;
}
public void dump()
{
ModelWriter.println( "------------------- State Machine -----------------" );
ModelWriter.println( "Name: " + name );
ModelWriter.print( "Ranges: " );
lv.dump();
ModelWriter.println();
stateTable.dump();
ModelWriter.println( "Start: 0" );
finalStates.dump();
ModelWriter.println();
}
private static interface Transition
{
public boolean toNextState( State state );
public boolean canAddTransition();
public void dump( int from );
public boolean isValid();
}
private static class ValidTransition implements Transition
{
protected int nextState;
ValidTransition( int _nextState )
{
nextState = _nextState;
}
public boolean toNextState( State state )
{
if( Contract.REQUIRE )
Contract.require( state != null );
state.setState( nextState );
return true;
}
final protected int getState()
{
return nextState;
}
// this indicates that we cannot replace this transition
// in the transition table or it is a nondeterministic FA
public boolean canAddTransition()
{
return false;
}
public void dump( int from )
{
ModelWriter.print( "\t" );
ModelWriter.print( from );
ModelWriter.print( " -> " );
ModelWriter.print( nextState );
ModelWriter.println();
}
public boolean isValid()
{
return true;
}
}
private static class InvalidTransition implements Transition
{
private static InvalidTransition it = new InvalidTransition();
static InvalidTransition getInvalidTransition()
{
return it;
}
public boolean toNextState( State state )
{
return false;
}
// initially, the state machine has only invalid transitions
// and they can be replaced in the state machine by other valid transitions
public boolean canAddTransition()
{
return true;
}
public void dump( int from )
{ /*ModelWriter.print( "Invalid transition" );*/
}
public boolean isValid()
{
return false;
}
}
/**
* goes from a state to a range start
* This transition will push the ranges that start onto the stack
* The order in which they are pushed is important,
* and should reflect the range nesting in the syntax tree
*/
private static class TransitionToStartRange extends ValidTransition
{
private IntegerVector v;
TransitionToStartRange( int nextState, IntegerVector _v )
{
super( nextState );
v = _v;
}
public boolean toNextState( State state )
{
if( Contract.REQUIRE )
Contract.require( state != null );
if( super.toNextState( state ) )
return state.initStart( v );
else
return false;
}
public void dump( int from )
{
try
{
ModelWriter.print( "\t" );
ModelWriter.print( from );
ModelWriter.print( " -> " );
ModelWriter.print( nextState );
ModelWriter.print( " (-SR), " );
ModelWriter.print( "Init: " );
v.dump( ModelWriter.getOutputStream() );
ModelWriter.println();
}
catch( IOException e )
{
System.err.println( "IOException in StateMachineRanges.TransitionToStartRange.dump( int ): " + e.getMessage() );
}
}
protected IntegerVector getInit()
{
return v;
}
}
/**
* goes from a range end state to a non start range state
* (can be end range state or any other state)
* This transition will pop the ending ranges from the stack,
* checking that the count is within ranges in the process
*/
private class TransitionFromEndRange extends ValidTransition
{
private IntegerVector v;
TransitionFromEndRange( int nextState, IntegerVector _v )
{
super( nextState );
if( Contract.REQUIRE )
Contract.require( _v != null );
v = _v;
}
public boolean toNextState( State state )
{
if( super.toNextState( state ) )
return state.check( v );
else
return false;
}
public void dump( int from )
{
try
{
ModelWriter.print( "\t" );
ModelWriter.print( from );
ModelWriter.print(" -> ");
ModelWriter.print( nextState );
ModelWriter.print( " (ER-), " );
ModelWriter.print( "Check: " );
v.dump( ModelWriter.getOutputStream() );
ModelWriter.println();
}
catch( IOException e )
{
System.err.println( "IOException in StateMachineRanges.dump( int ): " + e.getMessage() );
}
}
protected IntegerVector getCheck()
{
return v;
}
}
/**
* goes from a range end to a range start
* This transition will pop any other range
* that ends into the same end node,
* checking that their count is within the range,
* then increment the TOS, then push onto the stack
* other ranges that start in the same start node
* The order in which they are pushed is important,
* and should reflect the range nesting in the syntax tree
*/
private class TransitionFromEndToStartRangeIncrement extends TransitionFromEndToStartRangeNoIncrement
{
int inc;
TransitionFromEndToStartRangeIncrement( int nextState, IntegerVector _v1, IntegerVector _v2, int _inc )
{
super( nextState, _v1, _v2 );
inc = _inc;
}
public boolean toNextState( State state )
{
if( state.increment( inc ) )
return super.toNextState( state );
else
return false;
}
public void dump( int from )
{
try
{
ModelWriter.print( "\t" );
ModelWriter.print( from );
ModelWriter.print(" -> ");
ModelWriter.print( nextState );
ModelWriter.print( " (ER++-SR), " );
ModelWriter.print( "inc = " );
ModelWriter.print( inc );
ModelWriter.print( ", " );
ModelWriter.print( "Check: " );
getCheck().dump( ModelWriter.getOutputStream() );
ModelWriter.print( ", Init: " );
getInit().dump( ModelWriter.getOutputStream() );
ModelWriter.println();
}
catch( IOException e )
{
System.err.println( "IOException in StateMachineRanges.TransitionFromEndToStartRangeIncrement.dump( int ): " + e.getMessage() );
}
}
}
/**
* goes from a range end to a range start,
* but which doesn't correspond to the same range,
* so it will not do the increment
* This transition will pop any other range
* that ends into the same end node,
* checking that their count is within the range,
* then push onto the stack
* other ranges that start in the same start node
* The order in which they are pushed is important,
* and should reflect the range nesting in the syntax tree
*/
private class TransitionFromEndToStartRangeNoIncrement extends TransitionFromEndRange
{
private IntegerVector v;
TransitionFromEndToStartRangeNoIncrement( int nextState, IntegerVector _v1, IntegerVector _v2 )
{
super( nextState, _v2 );
v = _v1;
}
public boolean toNextState( State state )
{
if( super.toNextState( state ) )
return state.initStart( v );
else
return true;
}
public void dump( int from )
{
try
{
ModelWriter.print( "\t" );
ModelWriter.print( from );
ModelWriter.print( " -> " );
ModelWriter.print( nextState );
ModelWriter.print( " (ER-SR), " );
ModelWriter.print( "Check: " );
getCheck().dump( ModelWriter.getOutputStream() );
ModelWriter.print( ", Init: " );
v.dump( ModelWriter.getOutputStream() );
ModelWriter.println();
}
catch( IOException e )
{
System.err.println( "IOException in StateMachineRanges.TransitionFromEndToStartRangeNoIncrement.dump( int ): " + e.getMessage() );
}
}
protected IntegerVector getInit()
{
return v;
}
}
private static class RangeVector extends Vector
{
RangeVector( LimitsVector lv )
{
for( int n = 0; n < lv.size(); n++ )
addElement( new Range( lv.getLimits( n ) ) );
}
private RangeVector( RangeVector rv )
{
for( int n = 0; n < rv.size(); n++ )
{
addElement( rv.getRange( n ).clone() );
}
}
public Object clone()
{
return new RangeVector( this );
}
boolean increment( int n )
{
Range range = (Range)elementAt( n );
return range.increment();
}
Range getRange( int n )
{
return(Range)elementAt( n );
}
Range getRange( Integer n )
{
return(Range)elementAt( n.intValue() );
}
// sets the counters to 1, as to the entry into the range
boolean initStart( IntegerVector v )
{
for( int n = 0; n < v.size(); n++ )
{
Range r = getRange( v.getInteger( n ) );
r.init();
}
return true;
}
boolean checkAll()
{
for( int n = 0; n < size(); n++ )
{
if( !getRange( n ).check() )
return false;
}
return true;
}
// non-destructive check
boolean check( IntegerVector v )
{
for( int n = 0; n < v.size(); n++ )
{
Range r = getRange( v.getInteger( n ) );
if( !r.check() )
return false;
}
return true;
}
void reset( IntegerVector v )
{
for( int n = 0; n < v.size(); n++ )
{
Range r = getRange( v.getInteger( n ) );