path: root/sources/scalac/transformer/matching/DetWordAutom.java

package scalac.transformer.matching ;

import scalac.ast.Tree ;
import Tree.* ;

import java.util.* ;

import scalac.ApplicationError ;

public class DetWordAutom  {

    // BEGIN stuff from FiniteAutom

    //final static Integer FINTAG = new Integer(0);

    /** number of states */
    protected int nstates;

    /** the 'alphabet' */
    protected HashSet labels;

    /** the set of final states, here as a TreeMap */
    protected TreeMap finals;

    /** dfa: HashMap trans: Object -> Integer
     *  nfa: HashMap trans: Object -> Vector [ Integer ]
     *
     *  nfa: Integer  ->(Object -> Vector [ Int ])
     *       [q]     |->( a |-> { q' | (q,a,q') in \deltaright } )
     *
     *  dfa: Integer  ->(Object -> Int)
     *       [q]     |->( a |-> q' | \deltaright(q,a) = q' } )
     */

    public HashMap[] deltaq;

    public Integer[] defaultq; // this gives the default transitions

    //protected HashMap deltaq[];

    // --- accessor methods

    /** returns number of states
     */
    public int nstates() {
	return nstates;
    }

    /** returns the labels
     */
    public HashSet labels() {
	return labels;
    }

    /** returns the transitions
     */
    public HashMap deltaq( int state ) {
	return deltaq[ state ];
    }

    /** returns the transitions
     */
    public HashMap deltaq( Integer state ) {
	return deltaq[ state.intValue() ];
    }


    /** returns the transitions
     */
    public Integer defaultq( int state ) {
	return defaultq[ state ];
    }

    /** returns the transitions
     */
    public Integer defaultq( Integer state ) {
	return defaultq[ state.intValue() ];
    }


    /** returns true if the state is final
     */
    public boolean isFinal( int state ) {
	return ((finals != null)
		&& (finals.get( new Integer( state )) != null));
    }

    /** returns true if the state is final
     */
    public boolean isFinal( Integer state ) {
	return ((finals != null) && finals.containsKey( state ));
    }

    /** returns true if the state is final
     */
    public Integer finalTag( Integer state ) {
	return (Integer) finals.get( state );
    }


    public Integer finalTag( int state ) {
	return (Integer) finals.get( new Integer (state ));
    }

    /** returns true if the set of states contains at least one final state
     */
    boolean containsFinal( TreeSet Q ) {
	for( Iterator it = Q.iterator(); it.hasNext(); ) {
	    if( isFinal( (Integer) it.next()))
		return true;
	}
	return false;
    }


    /** returns true if there are no finite states
     */
    public boolean isEmpty() {
	return finals.isEmpty();
    }

    // END stuff from FiniteAutom

    static final int FIRST = 0;
    static final int LAST  = FIRST + 1;

    //static final int WHICH_LONGEST_MATCH = FIRST ;
    static final int WHICH_LONGEST_MATCH = LAST ;

    // inherited from FiniteAutom:

    // int nstates;   // number of states
    // HashSet labels;// the alphabet
    // TreeMap finals;

    // HashMap deltaq[];
    //Integer defaultq[];


    // TEMPORARY VAR used only during determinization and debug printing
    // Q -> (Label -> Q )
    HashMap delta;
    // Q -> Integer;
    HashMap indexMap;

    // Integer -> Q
    HashMap invIndexMap;

    // only not null if this is a right-transducer
    public Vector qbinders[];

    final static Integer NODEFAULT = new Integer( -1 );

    public boolean isSink( int i ) {
	return  ( deltaq[ i ].keySet().isEmpty()
		  && (defaultq != null )
		  && (defaultq( i ).intValue() == i) );
    }

    public boolean hasDefault( int i ) {
	return defaultq( i ) != NODEFAULT;
    }

    void determinize( NondetWordAutom nfa ) {
	//System.out.println("DetWordAutom:determinize");
	//System.out.println("nfa:");nfa.print();
	TreeSet states;// temp: Set[Set[Integer]]
	HashMap deftrans; // Set[Integer] -> Int

	HashMap trans; // always points to a mapping ( Label -> Q )
	int ix = 0;    // state index

	this.labels = nfa.labels;
	////System.out.println("Labels: "+labels);
	this.delta = new HashMap();
	//this.dead = -1;

	states = new TreeSet( new StateSetComparator() );
	deftrans = new HashMap();
	// temporarily: Map[Set[Integer]] later: Map[Integer]
	this.finals = new TreeMap( new StateSetComparator() );
	this.invIndexMap = new HashMap();
	this.indexMap = new HashMap();

	// new initial state (singleton set { q0 } by construction)

	TreeSet q0 = new TreeSet();
	q0.addAll( nfa.initials ); /*new Integer( 0 )); */
	states.add( q0 );

	TreeSet empty = new TreeSet();
	deftrans.put( q0, empty );
	states.add( empty );
	deftrans.put( empty, empty );

	Stack rest = new Stack();
	if( nfa.isFinal( 0 ) )
	    this.finals.put( q0, nfa.finalTag( 0 ) );


	rest.push( empty );
	rest.push( q0 );
	while( !rest.empty() ) {
	    TreeSet P1 = (TreeSet) rest.pop();

	    //System.out.println("states:"+ states);
	    //System.out.println("P1:"+ P1);

	    invIndexMap.put( new Integer( ix ), P1 );
	    indexMap.put( P1, new Integer( ix++ ));
	    delta.put( P1, trans = new HashMap());

	    // labelled transitions

	    for( Iterator it = labels.iterator(); it.hasNext(); ) {
		Object label = it.next();
		//System.out.print( "Label: " + label +" ");
		// Qdest will contain all states reachable via `label'
		// from some nfa state in P1;
		TreeSet Qdest = nfa.getSide( P1, label );
		//System.out.println("Qdest:"+Qdest);
		if( !states.contains( Qdest ) ) {
		    states.add( Qdest );
		    ////System.out.print(" (added)" );
		    rest.push( Qdest );
		    ////System.out.print(" (pushed)");

		    if( nfa.containsFinal( Qdest ) )
			this.finals.put( Qdest, nfa.finalTag( Qdest ));
		    ////System.out.print(" (added final)");

		}
		////System.out.println(".Qdest");

		trans.put( label, Qdest );
		// //System.out.println( "Qdest: " + Qdest);

	    }

	    // default transitions

	    TreeSet defTarget = (TreeSet) nfa.defaultq( P1 );
	    //System.out.println("defTarget:"+defTarget);
	    deftrans.put( P1, defTarget );

	    if( !states.contains( defTarget ) ) {
		states.add( defTarget );
		rest.push( defTarget );
		if( nfa.containsFinal( defTarget ) )
		    this.finals.put( defTarget, nfa.finalTag( defTarget ));
	    }
	}

	// <DEBUG>
	//printBefore( states, deftrans );

	// </DEBUG> do not call printBefore after this point
	// //System.out.println("indexMap: "+indexMap);

	this.nstates = states.size();
	deltaq = new HashMap[ nstates ];
	defaultq = new Integer[ nstates ];

	// we replace Set[Set[Integer]] by its index and clean up

	for( Iterator it = states.iterator(); it.hasNext(); ) {
	    TreeSet state   = (TreeSet) it.next();
	    Integer state_x = (Integer) indexMap.get( state );

	    TreeSet defTarget  = (TreeSet) deftrans.get( state );
	    Integer defTarget_x;
	    if( defTarget != null ) {
		defTarget_x = (Integer) indexMap.get( defTarget );
		////System.out.println("deftarget" + defTarget);
	    } else
		defTarget_x = NODEFAULT;

	    ////System.out.print(state.toString() + " --> " + state_x);
	    //System.out.println(" deftarget " + defTarget + " --> "+defTarget_x);

	    trans = (HashMap) delta.get( state );
	    HashMap newTrans = new HashMap();
	    for( Iterator labs = labels.iterator(); labs.hasNext() ;) {
		Object label = labs.next();
		TreeSet target   = (TreeSet) trans.get( label );
		Integer target_x;
		if( target != null ) {
		    // //System.out.println("target :"+target);
		    target_x = (Integer) indexMap.get( target );

		    if( target_x.intValue() != defTarget_x.intValue() ) {
			// replace target by target_x
			// (use type-unawareness)
			newTrans.put( label, target_x );
		    }
		    trans.remove( label );
		}

	    }
	    deltaq[ state_x.intValue() ] = newTrans;
	    defaultq[ state_x.intValue() ] = defTarget_x;

	    delta.remove( state );
	    deftrans.remove( state );

	}

	TreeMap oldfin = finals;
	this.finals = new TreeMap();
	for( Iterator it = oldfin.keySet().iterator(); it.hasNext(); ) {
	    TreeSet state = (TreeSet) it.next();
	    Integer state_x = (Integer) indexMap.get( state );
	    this.finals.put( state_x, oldfin.get( state ) );// conserve tags
	}

	// clean up, delete temporary stuff
	/*
	// we cannot clean up, indexmap is needed later
	for( Iterator it = states.iterator(); it.hasNext(); ) {
	((TreeSet) it.next()).clear();
	}
	*/
	states.clear();

	//minimize();
    }

    public DetWordAutom() {}

    public boolean isDead( int state ) {
	return state == nstates - 1; // by construction
    }

    public boolean isDead( Integer state ) {
	return state.intValue() == nstates - 1; // by construction
    }

    /** determinization -- standard algorithm considering only
     *                    reachable states
     */
    public DetWordAutom( NondetWordAutom nfa ) {
	determinize( nfa );
    }

    /** for a set of nfa states (that must exist), returns its transitions
     */
    HashMap deltaq( TreeSet nset ) {
	return deltaq( (Integer) indexMap.get( nset ) );
    }


    /** for a set of nfa states (that must exist), returns its transitions
     */
    Integer defaultq( TreeSet nset ) {
	return defaultq( (Integer) indexMap.get( nset ) );
    }

    /** returns target of the transition from state i with label label.
     *  null if no such transition exists.
     */
    Integer delta( int i, Label label ) {
	Integer target;
	switch( label ) {
	case DefaultLabel:
	    if( !hasDefault( i ) )
		return null;
	    return (Integer) defaultq( i ) ;
	case SimpleLabel( _ ):
	case TreeLabel( _ ):
	    return (Integer) deltaq[ i ].get( label ) ;
	    /*case Pair( Integer state, Label lab ):
	      return state;
	    */
	default:
	    throw new ApplicationError("whut's this: label="+label+", class "+label.getClass());
	}
    }

    Integer delta( Integer i, Label label ) {
	return delta( i.intValue(), label );
    }

    /** should maybe in nfa, not here
     */
    protected static Integer smallestFinal( NondetWordAutom nfa,
					    TreeSet states ) {

	int min = Integer.MAX_VALUE ;
	for( Iterator it = states.iterator(); it.hasNext(); ) {
	    Integer state = (Integer) it.next();
	    if( nfa.isFinal( state ) && (state.intValue() < min ))
		min = state.intValue();
	}
	if( min == Integer.MAX_VALUE )
	    throw new ApplicationError("I expected a final set of states");
	return new Integer( min );

    }

    protected Vector allSetsThatContain( Integer ndstate ) {
	Vector v = new Vector();
	for( Iterator it = indexMap.keySet().iterator(); it.hasNext(); ) {
	    TreeSet ndstateSet = (TreeSet) it.next();
	    if( ndstateSet.contains( ndstate ))
		v.add( ndstateSet );
	}
	return v;
    }


    protected void filterItOutQuoi( DetWordAutom dLeft,
				    Cartesian.Npair npTarget,
				    Label.Pair lab,
				    TreeMap nsrc ) {
	Label theLabel  = lab.lab;
	Integer ntarget = lab.state;

	// e.g.[2,(3),4] --> 7
	Integer dstate = (Integer) dLeft.indexMap.get( npTarget.nset );

	// eg. 3 -> [3] [2,3]
	Vector targets = dLeft.allSetsThatContain( ntarget );

	////System.out.println( targets+", of these " ) ;

	// filter out those source states which arrive here...

	for( Iterator su = targets.iterator(); su.hasNext(); ) {
	    TreeSet nset   = (TreeSet) su.next();

	    HashMap ddelta = dLeft.deltaq( nset );

	    // ...  at THIS dstate
	    if( (Integer) ddelta.get( theLabel ) == dstate ) {

		Cartesian.Npair np1 = new Cartesian.Npair( ntarget, nset );

		////System.out.print( np1.toString( dLeft.indexMap ));

		if( WHICH_LONGEST_MATCH == FIRST )
		    addTransitionFLM( nsrc, np1 );
		else
		    addTransitionLLM( nsrc, np1 );
	    }

	}
    }

    /** all default transitions from sets that contain nq to npTarget
     */
    protected void filterItOutQuoiDefault( DetWordAutom dLeft,
					   Cartesian.Npair npTarget,
					   Integer nq,
					   TreeMap nsrc ) {


	////System.out.println( "npTarget = " + npTarget ) ;

	Vector allSources = dLeft.allSetsThatContain( npTarget.nstate );

	for( Iterator it = allSources.iterator(); it.hasNext(); ) {

	    // e.g.[2,(3),4] --> 7
	    //Integer dstate = (Integer) dLeft.indexMap.get( npTarget.nset );

	    Integer dstate = (Integer) dLeft.indexMap.get( it.next() );

	    //System.out.println( "dstate = " + dstate ) ;

	    assert dstate != null;

	    // eg. 3 -> [3] [2,3]
	    Vector targets = dLeft.allSetsThatContain( nq );

	    //System.out.println( "targets: " + targets ) ;

	    // filter out those source states which arrive here...

	    for( Iterator su = targets.iterator(); su.hasNext(); ) {
		TreeSet nset   = (TreeSet) su.next();

		Integer ddef = dLeft.defaultq( nset );

		//System.out.println( "ddef ="+ddef );

		// ...  at THIS dstate
		if( ddef == dstate ) {

		    Cartesian.Npair np1 = new Cartesian.Npair( nq, nset );

		    // print target
		    //System.out.print( np1.toString( dLeft.indexMap ));

		    if( WHICH_LONGEST_MATCH == FIRST )
			addTransitionFLM( nsrc, np1 );
		    else
			addTransitionLLM( nsrc, np1 );

		}

	    }
	}
    }

    /** this implements the first longest match policy
     */
    protected static void addTransitionFLM( TreeMap nsrc, Cartesian.Npair np ) {
	Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( np.nset );

	// (policy) first longest match
	if(( np2 == null )
	   ||( np2.nstate.intValue() > np.nstate.intValue())) {
	    nsrc.put( np.nset, np  );
	}

    }

    /** this implements the last longest match policy (!)
     */
    protected static void addTransitionLLM( TreeMap nsrc, Cartesian.Npair np ) {
	Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( np.nset );

	// (policy) first longest match
	if(( np2 == null )
	   ||( np2.nstate.intValue() < np.nstate.intValue())) {
	    nsrc.put( np.nset, np  );
	}

    }


    /** build a deterministic right to left transducer from the args
     */
    public DetWordAutom( NondetWordAutom right,
			 NondetWordAutom left,
			 DetWordAutom    dLeft ) {

	/* System.out.println("DetWordAutom.<init>(nfa,nfa,dfa)");
	   System.out.println("nfa-left:");left.print();
	   System.out.println("nfa-right:");right.print();
	   System.out.println("dLeft:"+dLeft.print());
	   System.out.println("dLeft.finals"+dLeft.finals);
	*/
	this.indexMap = dLeft.indexMap;
	this.invIndexMap = dLeft.invIndexMap;
	// fix indexMap
	/* // unnecessary
	   TreeSet q0 = new TreeSet();
	   q0.add( new Integer( 0 ));
	   indexMap.put( q0, new Integer( 0 ));
	   //System.out.println("check out the indexMap!" + indexMap);
	   */

	TreeSet visited_n = new TreeSet( new NpairComparator() );
	Stack rest    = new Stack();

	// right is "nearly deterministic"
	// we can follow reverse traces paths by using dLeft.indexMap

	// start with right.initials, left.final, dLeft.final
	for( Iterator it = dLeft.finals.keySet().iterator(); it.hasNext(); ) {
	    Integer fstate  = (Integer) it.next();
	    TreeSet nfstate = (TreeSet) invIndexMap.get( fstate );
	    //System.out.print( "final state:"+fstate);
	    //System.out.print( " correspond to set of states:"+ nfstate );

	    Integer min_ndstate = smallestFinal( left, nfstate );

	    Cartesian.Npair npair = new Cartesian.Npair( min_ndstate, nfstate );

	    //System.out.println( "  smallest final of these: "+ min_ndstate );


	    //System.out.println( "push final nfa state "+npair.toString( dLeft.indexMap ));

	    if( !visited_n.contains( npair )) {
		visited_n.add( npair );
		rest.push( npair );
	    }
	}

	HashMap ratLab     = new HashMap(); // maps nset to label,HashMap
	HashMap ratDelta   = new HashMap(); // maps nset to Vector[ NP ]targets

	HashMap ratDefault = new HashMap(); // maps nset to NP (one target)

	int ix = 1;
	Stack ix_initial = (Stack) rest.clone();
	TreeSet ix_final = new TreeSet( new NpairComparator() );;

	TreeMap newIndexMap = new TreeMap( new NpairComparator() );

	while( !rest.isEmpty() ) {

	    Cartesian.Npair npair = (Cartesian.Npair) rest.pop();
	    newIndexMap.put( npair, new Integer(ix));

	    ratDelta.put( npair, new Vector() );

	    if( npair.nset.contains( new Integer( 0 )) ) {
		ix_final.add( npair );
	    }
	    ix++;

	    //System.out.println(" popped "+npair.toString( dLeft.indexMap ));

	    ////System.out.print(" binders: ");
	    ////System.out.print( right.qbinders[ npair.nstate.intValue() ] );

	    HashMap delta = right.deltaq( npair.nstate );

	    ////System.out.print(" we could have arrived : ");
	    //search the delta for target invIndexMap

	    HashMap labelToNset = new HashMap();
	    HashMap labelToFrom = new HashMap();

	    // maps nsets to the active nstates
	    TreeMap nsrc = new TreeMap( new StateSetComparator() );

	    // berry-sethi construction assures that
	    //   there is only one label for outgoing transitions
	    Label theLabel = null;

	    // collect all transition possible in the DFA

	    for( Iterator it = delta.keySet().iterator(); it.hasNext(); ) {

		Label.Pair   lab = (Label.Pair) it.next();

		// lab.state is the target in the NFA

		if( theLabel == null ) {
		    ratLab.put( npair, lab.lab );
		    ////System.out.print(" with \""+lab.lab+"\" ");
		}
		theLabel = lab.lab ;

		////System.out.print("\nfrom n" + lab.state +"  ... ");

		// these are too many, filter out those that exist in DFA

		filterItOutQuoi( dLeft, npair, lab, nsrc );

	    }


	    ////System.out.println( "---" );

	    ////System.out.println("all sources: ");

	    // !!  first longest match

	    for( Iterator ut = nsrc.keySet().iterator(); ut.hasNext(); ) {
		TreeSet nset  = (TreeSet) ut.next();

		Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( nset );

		assert( np2 != null );
		////System.out.println("target: n"+npair.nstate+" via: "+theLabel+" from "+ np2.toString( dLeft.indexMap ));// nset:"+nset+ " namely state n"+ dest);

		Vector v = (Vector) ratDelta.get( npair );

		v.add( np2 );

		if( !visited_n.contains( np2 ) ) {

		    visited_n.add( np2 );
		    rest.push( np2 );
		}

	    }

	    //System.out.println("default sources: ");

	    // maps nsets to the active nstates
	    nsrc = new TreeMap( new StateSetComparator() );

	    // now for all default transitions that arrive at this nfa state
	    Vector defqs = right.defaultq( npair.nstate );
	    for( Iterator it = defqs.iterator(); it.hasNext(); ) {
		Integer nq = (Integer) it.next();
		//System.out.println("checking nq="+nq);
		filterItOutQuoiDefault( dLeft, npair, nq, nsrc );
		//System.out.println( "nsrc after "+nq+" is "+nsrc );
	    }

	    //System.out.println( "defqs :"+defqs );
	    //System.out.println( "nsrc :"+nsrc );

	    for( Iterator ut = nsrc.keySet().iterator(); ut.hasNext(); ) {

		Cartesian.Npair np2 = (Cartesian.Npair) nsrc.get( ut.next() );

		Vector v = (Vector) ratDefault.get( npair );
		if( v == null )
		    ratDefault.put( npair, v = new Vector() );
		v.add( np2 );

		if( !visited_n.contains( np2 ) ) {

		    visited_n.add( np2 );
		    rest.push( np2 );
		}

	    }

	    ////System.out.println("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz");

	}

	// Renumbering

	////System.out.println( "output: a dfa with "+ix+"states");

	// FIX: empty regular expression (as in "List()") is valid
	//assert ( !ix_final.isEmpty() ) : "no final states found";

	////System.out.println( "final state:"+ix_final);

	//System.out.println( "indexMap: " +indexMap);
	//System.out.println( "newIndexMap: " +newIndexMap);
	this.finals = new TreeMap();
	this.nstates = ix;
	HashMap dratDelta[] = new HashMap[ ix ];
	qbinders  = new Vector[ ix ];
	labels = new HashSet();
	for( Iterator it = ratDelta.keySet().iterator(); it.hasNext(); ) {
	    Cartesian.Npair np = (Cartesian.Npair) it.next();

	    //System.out.print( "\nstate: "+np);
	    TreeSet ndset = np.nset;
	    Integer dstate = (Integer) newIndexMap.get( np );
	    assert dstate != null : "no dstate for "+np.toString(dLeft.indexMap);

	    //System.out.print(" binders:");

	    qbinders[ dstate.intValue() ] = left.qbinders[ np.nstate.intValue() ];

	    //System.out.print( qbinders[dstate.intValue() ]);

	    //System.out.println(" transitions:");
	    if( ix_final.contains( np ) ) {
		Integer fin_ix = (Integer) newIndexMap.get( np );
		finals.put( fin_ix, new Integer( 0 ));
	    }

	    Label   lab   = (Label)  ratLab.get( np );
	    Vector  v     = (Vector) ratDelta.get( np );

	    HashMap ddelta = new HashMap();

	    // v might be null if there are only default transitions
	    if( v != null )
		for( Iterator it2 = v.iterator(); it2.hasNext() ; ) {

		    Cartesian.Npair np2= (Cartesian.Npair) it2.next();
		    //System.out.print( "("+lab+","+np2+") " );
		    Integer ddestR = (Integer) newIndexMap.get( np2 );
		    Integer ddest = (Integer) indexMap.get( np2.nset );
		    assert ddest != null :
			"no ddest for "
			+np2.toString(dLeft.indexMap);

		    Label.Pair newLab = new Label.Pair(ddest, lab);
		    ddelta.put( newLab, ddestR );
		    labels.add( newLab );

		}
	    dratDelta[ dstate.intValue() ] = ddelta;

	}

	for( Iterator it = ratDefault.keySet().iterator(); it.hasNext(); ) {
	    Cartesian.Npair np  = (Cartesian.Npair) it.next();
	    Integer         dstate = (Integer) newIndexMap.get( np );

	    //System.out.print("\nstate: "+np+" default trans: ");

	    Vector v = (Vector) ratDefault.get( np );
	    for( Iterator ut = v.iterator(); ut.hasNext(); ) {
		Cartesian.Npair np2  = (Cartesian.Npair) ut.next();
		Integer targetL      = (Integer) indexMap.get( np2.nset );
		Integer targetR      = (Integer) newIndexMap.get( np2 );

		Label defLab = new Label.Pair( targetL,
					       Label.DefaultLabel );

		labels.add( defLab );
		//System.out.print( "("+defLab+","+np2+") " );

		HashMap d = dratDelta[ dstate.intValue() ];
		if( d == null )
		    dratDelta[ dstate.intValue() ] = d = new HashMap();

		d.put( defLab, targetR );
	    }
	}

	deltaq = dratDelta;

	HashMap hmap = new HashMap();

	// final states of left are initial states of right
	// problem: still need to choose the one

	while( !ix_initial.isEmpty() ) {
	    Cartesian.Npair np = (Cartesian.Npair) ix_initial.pop();

	    Integer i          = (Integer) newIndexMap.get( np ); //R-state
	    Integer dtarget    = (Integer) indexMap.get( np.nset );// left-d-state

	    hmap.put( dtarget, i );
	}
	deltaq[ 0 ]  = hmap; // careful, this maps Int to Int

	qbinders[ 0 ] = new Vector();
	//((Vector[])defaultq)[ 0 ] = new Vector(); is null
	printBeforeRAT( dratDelta );

    }

    void printBeforeRAT1( String str ) {
	StringBuffer tmp = new StringBuffer( str );
	for( int j = tmp.length(); j < 20; j++ ) {
	    tmp.append(" ");
	}
	//System.out.print( tmp.toString() );
    }

    void printBeforeRAT( HashMap dratDelta[] ) {
	//System.out.println();
	printBeforeRAT1( "dratDelta" );
	printBeforeRAT1( "[index]" );
	//System.out.println();

	for( int i = 0; i < dratDelta.length; i++ ) {
	    if( isFinal( i ))
		printBeforeRAT1( "*"+i );
	    else
		printBeforeRAT1( " "+i );

	    //System.out.println( dratDelta[ i ] );
	}
    }

    /** you may only call this before the set[set[...]] representation
     *  gets flattened.
     */
    public void printBefore( TreeSet states, HashMap deftrans ) {
	HashMap trans;
	System.out.println( states );
	for( Iterator it = states.iterator(); it.hasNext(); ) {
	    TreeSet state = (TreeSet) it.next();
	    System.out.print("state:"+state.toString()+" transitions ");
	    trans = (HashMap) delta.get( state );
	    for( Iterator labs = labels.iterator(); labs.hasNext() ;) {
		Object label = labs.next();
		TreeSet target = (TreeSet) trans.get( label );
		System.out.print( "  (" + label.toString()
				  + "," + target.toString()+")");
	    }
	    System.out.print("default trans"+deftrans.get( state ));
	    System.out.println();
	}
	System.out.println("final states:" + finals );
    }


    /*
      public void minimize() { // TO DO
      //System.out.println("minimization");
      boolean mark[][] = new boolean[nstates][];
      for( int i = 0; i < nstates; i++ ) {
      mark[i] = new boolean[nstates - i];
      for( int j = 0; j < (nstates - i); j++ )
      mark[i][j] = false;
      }
      debugPrint( mark );
      }

      protected void debugPrint( boolean mark[][] ) {
      for( int i = 0; i < nstates; i++ ) {
      //System.out.print("[");
      for( int j = 0; j < nstates - i; j++ ) {
      //System.out.print(" "+mark[i][j]);
      if( mark[i][j] )
      //System.out.print(" ");
      }
      //System.out.println(" ]");
      }
      }

    */

    /*

    public void createDeadState() {
    assert dead == -1;
    this.dead = this.nstates++;
    Integer deadI = new Integer( dead );

    HashMap odelta[] = ((HashMap[])deltaq);
    deltaq = new HashMap[ this.nstates ];
    System.arraycopy(odelta, 0, ((HashMap[])deltaq), 0, odelta.length);
    HashMap trans = new HashMap();
    ((HashMap[])deltaq)[ this.dead ] = trans;
    for( Iterator labs = labels.iterator(); labs.hasNext(); ) {
    trans.put( labels, deadI );
    }
    //System.out.println("createDeadState, new dead state:"+dead);
    }



    // adjusts the alphabet of this automaton

    public void addLabels( HashSet labels ) {

    for(Iterator it = labels.iterator(); it.hasNext(); ) {
    Object label = it.next();
    if( this.labels.add( label )) { // new
    // adjust all transitions

    if( this.dead == -1 )
    createDeadState();

    Integer deadI = new Integer( this.dead );

    for( int i = 0; i < this.nstates; i++ ) {
    ((HashMap[])deltaq)[ i ].put( label, deadI );
    }
    }
    }
    }
    */

    // wishlist for jaco: why does Cartesian have to be static ?
    // if not, error "inner classes must not have static members"

    /** cartesian
     */

    static class Cartesian {
	/** Int x TreeSet[ Int ]
	 */
	case Npair(Integer nstate, TreeSet nset);

	public boolean equals( Object that ) {
	    if( !(that instanceof Cartesian ))
		return false;
	    switch( this ) {
	    case Npair( Integer nstate, TreeSet nset ):
		switch((Cartesian) that) {
		case Npair( Integer _nstate, TreeSet _nset ):
		    return ((nstate == _nstate)
			    &&( nset == _nset ));
		}
	    }
	    return false;
	}

	public String toString() {
	    switch( this ) {
	    case Npair( Integer nstate, TreeSet nset ):
		//Integer dstate = (Integer) indexMap.get( nset );
		return "<n"+nstate.toString()+" in "+nset /*+" = d"+dstate*/+">";
	    }
	    return null;
	}

	public String toString( HashMap indexMap ) {
	    //assert indexMap != null;
	    switch( this ) {
	    case Npair( Integer nstate, TreeSet nset ):
		assert nstate!=null;
		Integer dstate = (Integer) indexMap.get( nset );
		return "<n"+nstate.toString()+" in "+nset +" = d"+dstate +">";
	    }
	    return null;
	}


    }

    static class NpairComparator extends StateSetComparator {
	public int compare( Object o1, Object o2 ) {
	    if(( o1 instanceof Cartesian.Npair )&&
	       ( o2 instanceof Cartesian.Npair ))
		switch((Cartesian) o1) {
		case Npair( Integer nstate, TreeSet nset ):
		    switch( (Cartesian) o2 ) {
		    case Npair( Integer _nstate, TreeSet _nset ):
			int res = nstate.compareTo( _nstate );

			////System.out.println("nstate"+nstate+" <> _nstate "+ _nstate+" res"+res);
			if( res != 0 )
			    return res;
			else
			    return super.compare( nset, _nset );
		    }
		}
	    throw new ApplicationError( "illegal arg. to compare. "
					+o1.getClass()+" "+o2.getClass());
	}
    }

}