diff options
author | buraq <buraq@epfl.ch> | 2003-06-19 17:15:34 +0000 |
---|---|---|
committer | buraq <buraq@epfl.ch> | 2003-06-19 17:15:34 +0000 |
commit | 88cb90bf6d10e0766c08cfa277e32a52de6f96ab (patch) | |
tree | 7ce6cfd1b271387904fdb68b6a9928768ac26403 /sources/scalac/transformer/matching/DetWordAutom.java | |
parent | e7609c9d0e314117ef1c6161827d0982076090e7 (diff) | |
download | scala-88cb90bf6d10e0766c08cfa277e32a52de6f96ab.tar.gz scala-88cb90bf6d10e0766c08cfa277e32a52de6f96ab.tar.bz2 scala-88cb90bf6d10e0766c08cfa277e32a52de6f96ab.zip |
automata stuff for pattern matching
Diffstat (limited to 'sources/scalac/transformer/matching/DetWordAutom.java')
-rw-r--r-- | sources/scalac/transformer/matching/DetWordAutom.java | 892 |
1 files changed, 892 insertions, 0 deletions
diff --git a/sources/scalac/transformer/matching/DetWordAutom.java b/sources/scalac/transformer/matching/DetWordAutom.java new file mode 100644 index 0000000000..1f81e8c04d --- /dev/null +++ b/sources/scalac/transformer/matching/DetWordAutom.java @@ -0,0 +1,892 @@ +package scalac.transformer.matching ; + +import scalac.ast.Tree ; +import Tree.* ; + +import java.util.* ; + +import scalac.ApplicationError ; + +public class DetWordAutom extends FiniteAutom { + + static final int FIRST = 0; + static final int LAST = FIRST + 1; + + static final int WHICH_LONGEST_MATCH = FIRST ; + + // inherited from FiniteAutom: + + // int nstates; // number of states + // HashSet labels;// the alphabet + // TreeMap finals; + + // HashMap deltaq[]; + //Integer defaultq[]; + + + // 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 (((HashMap[])deltaq)[ i ].keySet().isEmpty() + && (defaultq != null ) + && (((Integer)defaultq( i )).intValue() == i)); + } + + public boolean hasDefault( int i ) { + return (Integer) 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 ); + } + + } + ((HashMap[])deltaq)[ state_x.intValue() ] = newTrans; + ((Integer[])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 (HashMap) deltaq( (Integer) indexMap.get( nset ) ); + } + + + /** for a set of nfa states (that must exist), returns its transitions + */ + Integer defaultq( TreeSet nset ) { + return (Integer) 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) ((HashMap[])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 = (HashMap) 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 = (Integer) 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 = (HashMap) 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 = (Vector) 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"); + 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 ); + } + ((HashMap[])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()); + } + } + +} |