/*
*
* 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.IntegerSet;
import com.tradery.contract.Contract;
import java.util.Hashtable;
import java.util.Enumeration;
import java.util.Vector;
import java.io.IOException;
/**************************************************
* StateMachine - holds the state transition table
* and provides state machine functionality
* the state machine start state is always 0. Invalid transitions
* are marked with NOTRANSITION (-1)
***************************************************/
class StateMachineNoRanges 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 IntegerSet finalStates;
// the name of the state machine (the name of the model too)
private final String name;
/**************************************************
* 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 = StateMachineNoRanges.START;
// the state machine to which it refers
private StateMachineNoRanges sm;
// constructor - attaches it to a state machine
State( StateMachineNoRanges _sm )
{
sm = _sm;
}
// 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 );
int n = sm.transition( symbol, crtState );
if( n == StateMachineNoRanges.NOTRANSITION )
return false;
else
{
crtState = n;
return true;
}
}
public boolean isValidTransition( String symbol )
{
if( Contract.REQUIRE )
{
Contract.require( symbol != null );
}
return sm.transition( symbol, crtState ) != StateMachineNoRanges.NOTRANSITION;
}
// determines if the current state is also a final state
// which would allow the user to terminate the validation
public boolean canTerminate()
{
return sm.isFinal( crtState );
}
public Enumeration getValidTransitions()
{
return sm.getValidSymbolsFromState( 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
*************************************************/
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 int[] row;
// constructor
// takes the row size as argument
Row( int n )
{
// create the row
row = new int[ n ];
// initialize it with no transitions
for( int m = 0; m < n; m++ )
{
row[ m ] = NOTRANSITION;
}
}
// adds a transition to the row
boolean addTransition( int from, int to )
{
if( Contract.REQUIRE )
Contract.require( from >= 0 && to > 0 );
// if there is already a transition there, return false
// this means the content model is not deterministic
if( row[ from ] != NOTRANSITION )
return false;
// set the new state value
row[ from ] = to;
return true;
}
// returns the next transition
int transition( int from )
{
return row[ from ];
}
public void dump()
{
for( int n = 0; n < row.length; n++ )
{
if( row[ n ] != -1 )
{
ModelWriter.print( n );
ModelWriter.print( " -> " );
ModelWriter.print( row[ n ] );
ModelWriter.print( ", " );
}
}
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, int to )
{
if( Contract.REQUIRE )
{
Contract.require( symbol != null );
Contract.require( from >= 0 && to > 0 );
}
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, to );
}
// calculates the next state, from the sybmol and current state
int transition( String symbol, int from )
{
if( Contract.REQUIRE )
{
Contract.require( symbol != null );
Contract.require( from >= 0 );
}
Row row = (Row)get( symbol );
if( row == null )
// throw something
return -1;
else
return row.transition( from );
}
Enumeration getValidSymbolsFromState( int from )
{
Vector v = new Vector();
for( Enumeration e = keys(); e.hasMoreElements(); )
{
String symbol = (String)e.nextElement();
Row row = (Row)get( symbol );
if( row.transition( from ) != NOTRANSITION )
v.addElement( symbol );
}
return v.elements();
}
public void dump()
{
for( Enumeration e = keys(); e.hasMoreElements(); )
{
String symbol = (String)e.nextElement();
ModelWriter.print( "\"" + 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 );
}
// constructor - creates a table with the specified number of states
StateMachineNoRanges( String _name, int states )
{
if( Contract.REQUIRE )
{
Contract.require( _name != null );
Contract.require( states > 0 );
}
name = _name;
stateTable = new StateTable( states );
// by default, a newly constructed state machine starts and ends on state 0;
finalStates = new IntegerSet();
finalStates.add( 0 );
}
// adds a transition to the table
boolean addTransition( String symbol, int from, int to )
{
return stateTable.addTransition( symbol, from, to );
}
// sets the final states
private void setFinalStates( IntegerSet _finalStates )
{
finalStates = _finalStates;
}
public void setFinalStates( Object o )
{
setFinalStates( (IntegerSet)o );
}
// calculates the next state
int transition( String symbol, int from )
{
/* ModelWriter.print( "Trans - " + name + ": \"" + symbol + "\" ");
ModelWriter.print( from );
ModelWriter.print( "->" );
*/
int n = stateTable.transition( symbol, from );
// ModelWriter.println( n );
return n;
}
// tests if a state is final
boolean isFinal( int state )
{
// ModelWriter.print( "isFinal - " + name + ": " );
boolean b = finalStates.contains( new Integer( state ) );
// ModelWriter.println( b );
return b;
}
Enumeration getValidSymbolsFromState( int from )
{
return stateTable.getValidSymbolsFromState( from );
}
public void dump()
{
try
{
ModelWriter.println( "--------------- State Machine ---------------" );
ModelWriter.println( "Name: " + name );
stateTable.dump();
ModelWriter.println( "Start: 0" );
ModelWriter.print( "Finals: " );
finalStates.dump( ModelWriter.getOutputStream() );
ModelWriter.println();
ModelWriter.println();
}
catch( IOException e )
{
System.err.println( "IOException in StateMachineNoRanges.dump: " + e.getMessage() );
}
}
}