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

package scalac.transformer.matching ;

import scalac.ApplicationError ;
import scalac.ast.Tree ;
import scalac.util.Name ;
import Tree.* ;

import java.util.* ;

//import scala.compiler.printer.TextTreePrinter ;

/** a nondeterministic word automaton.
 *  states are represented (implicitly) as Integer objects.
 */

public class NondetWordAutom  {

    // 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 Vector[]  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 Vector defaultq( int state ) {
            return defaultq[ state ];
      }

      /** returns the transitions
       */
      public Vector 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


      // inherited from FiniteAutom

      // set of *distinct* objects that may label transitions
      // see Object.hashCode() to see why this works

      //HashSet labels;
      //TreeMap finals;

      TreeSet initials; // ? need this ?
      // ---

      // Object deltaq -->
      // HashMap deltaq[]; // this gives the transitions of q;

      boolean leftTrans;
      boolean rightTrans;

      /** if true, this automaton behaves as a special left transducer.
       *  if a run succeeds, the result is not "true" but the entire
       *  run of the automaton as a sequence of (label,state) - pairs.
       *  used for binding variables.
       */
      public boolean producesRun() {
            return leftTrans;
      }

      public boolean consumesRun() {
            return rightTrans;
      }

      public boolean initial( Integer i ) {
            return initials.contains( i );
      }
      public Vector qbinders[];

      /** returns all states accessible from Qsrc via label.
       *  used by class DetWordAutomaton.
       */
      TreeSet getSide ( TreeSet Qsrc, Object label ) {
            TreeSet Qdest = new TreeSet();
            for( Iterator it = Qsrc.iterator(); it.hasNext(); ) {// state
                  int q = ((Integer) it.next()).intValue();
                  Vector ps = (Vector) deltaq[ q ].get( label );
                  if( ps!=null ) {
		      Qdest.addAll( ps );
                  }
                  Qdest.addAll( defaultq( q ) );
            }
            return Qdest;
      }

      /** returns the transitions
       */
      public Object defaultq( Set P1 ) {
            TreeSet defTarget = new TreeSet();
            for( Iterator p1 = P1.iterator(); p1.hasNext(); ) {
                  int q1 = ((Integer) p1.next()).intValue();
                  //System.out.println("   q1:"+q1+ " defa: "+defaultq( q1 ));
                  defTarget.addAll( defaultq( q1 ) );
            }
            return defTarget;
      }


      /** first match policy: among several final states, the smallest one is
       *   chosen. used by class DetWordAutomaton
       */
      Integer finalTag( Set Q ) {

            int min = Integer.MAX_VALUE ;

            for( Iterator it = Q.iterator(); it.hasNext(); ) {
                  Integer state = (Integer) it.next();
                  Integer tag = (Integer) finals.get( state );
                  if( tag != null ) {
                        if( tag.intValue() < min )
                              min = tag.intValue();
                  }
            }

            if ( min == Integer.MAX_VALUE )
                  throw new ApplicationError( "there should be a final state ");

            return new Integer( min );
      }

      /*
      protected void tmap(int offs, TreeMap t) {
            TreeMap nt = new TreeMap();
            for(Iterator it = t.keySet().iterator(); it.hasNext(); ) {
                  Integer key = (Integer) it.next();
                  Integer newkey = new Integer( key.intValue() + offs );
                  Integer val = (Integer) t.get( key );
                  Integer newval = new Integer( val.intValue() + offs );

                  nt.put( newkey, newval );
            }
            return nt;
      }
*/
      // hashmaps, treemaps
      protected Map mapmap(Map src,
                             int offset,
                             Map dest,
                             boolean mapkeys,
                             boolean mapvals) {
            for(Iterator it = src.keySet().iterator(); it.hasNext(); ) {
                  Object key = it.next();
                  Object val = src.get( key );
                  if( mapkeys ) key = new Integer( ((Integer)key).intValue()
                                                   + offset );
                  if( mapvals ) val = vmap( offset, (Vector) val ) ;
                                      /* new Integer( ((Integer)val).intValue()
                                                   + offset );
                                      */
                  dest.put( key, val );
            }
            return dest;
      }

      protected static Vector vmap(int offs, Vector v ) {
            if( v == null )
                  return null;
            Vector res = new Vector( v.size() );

            for(Iterator it = v.iterator(); it.hasNext(); ) {
                  Integer item = (Integer) it.next();
                  res.add( new Integer( item.intValue() + offs ));
            }
            return res;

      }

      /*
      protected void relocate_defaultq( int offs, Vector   _defaultq[] ) {
            for( int i = 0; i < this.nstates; i++ ) {
                  _defaultq[ i + offset ] = vmap( offset, ((Vector[])defaultq)[ i ]);
            }
      }
      */

      /** copies the values in the fields of this object into the
       *  arguments, possibly adding an offset.
       */
      protected void relocate( int      offset,
                               TreeMap  _finals,
                               HashMap  _deltaq[],
                               Vector   _defaultq[],
                               Vector   _qbinders[] ) {

            mapmap( finals, offset, _finals, true, false);

            for( int i = 0; i < this.nstates; i++ ) {

                  _deltaq  [ i + offset ] = (HashMap) mapmap( ((HashMap[])deltaq)[ i ],
                                                    offset, new HashMap(), false, true);

                  _defaultq[ i + offset ] = vmap( offset, defaultq[ i ] );

            }
            if ((_qbinders != null) &&( qbinders != null ))
                  for( int i = 0; i < this.nstates; i++ ) {
                        //System.out.println("hallo"+qbinders);
                        //System.out.println("qbinders[ i ] :"+qbinders[ i ]);
                        assert _qbinders != null;
                        //System.out.println("_qbinders :"+_qbinders);

                        _qbinders[ i + offset ] = qbinders[ i ];
                  }
      }

      /** if there is more than one initial state, a new initial state
       *  is created, with index 0
       */
      protected void normalize( TreeSet initials, boolean reloc ) {
            //if( initials.size() == 1 )
            //      return;

            HashMap idelta   = new HashMap();
            TreeSet idefault = new TreeSet();

            Integer q0 = new Integer( 0 );

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

                  Integer ostate = (Integer) it.next();

                  Integer finTag = (Integer) finals.get( ostate ) ;
                  if(( finTag != null ) && ( finals.get( q0 )  == null))
                        finals.put( q0, finTag );


                  HashMap tmp = deltaq( ostate );

                  if( reloc )
                        tmp = (HashMap) mapmap( tmp, 1, new HashMap(), false, true );

                  for( Iterator labs = tmp.keySet().iterator(); labs.hasNext(); ) {
                        Label  lab    = (Label) labs.next();
                        Vector itarget = (Vector) idelta.get( lab );
                        if( itarget == null )
                              idelta.put( lab, itarget = new Vector());
                        Vector otarget = (Vector) tmp.get( lab );
                        itarget.addAll( otarget );
                  }
                  //System.out.println( "normalize:defaultq[ "+ostate+" ] "+((Vector[]) defaultq) [ ostate.intValue() ]);
                  if( defaultq( ostate ) != null )
                        idefault.addAll( defaultq( ostate )  );
            }

            if( reloc ) {
                  int m = 1 + this.nstates;
                  TreeMap _finals     = new TreeMap();
                  HashMap _deltaq[]   = new HashMap[ m ];
                  Vector  _defaultq[] = new Vector[ m ];
                  Vector  _qbinders[] = null;

                  if( qbinders != null )
                        _qbinders = new Vector[ m ];

                  relocate( 1, _finals, _deltaq, _defaultq, _qbinders );

                  this.nstates  = m;
                  this.finals   = _finals;
                  this.deltaq   = _deltaq;
                  this.defaultq = _defaultq;
                  this.qbinders = _qbinders;
            }

            this.deltaq  [ 0 ] = idelta;
            //System.out.println("normalize:deltaq[ 0 ]"+ idelta );
            this.defaultq[ 0 ] = new Vector( idefault );

            //System.out.println("normalize:defaultq[ 0 ]"+ idefault );

            this.initials = new TreeSet();
            this.initials.add( q0 );
      }


      /** needed for NondetWordSwitch
       */
      NondetWordAutom() {}

      /** called from Berry-Sethi construction.
       */

      public NondetWordAutom(int nstates,
                             HashSet labels,
                             TreeSet initials,
                             TreeMap finals,
                             HashMap[] deltaq,
                             Vector[]  defaultq,
                             Object qbinders) {
            this.nstates = nstates;
            this.labels = labels;
            this.initials = initials;
            this.finals = finals;
            this.deltaq = deltaq;
            this.defaultq = defaultq;
            this.qbinders = (Vector[])qbinders;
            //print();
            //System.exit(0);
      }



      int offset[]; // only used if constructed from multiple

      protected void collectLabels( NondetWordAutom nfa[] ) {
            this.labels = new HashSet();
            for( int i = 0; i < nfa.length; i++ ) {
                  this.labels.addAll( nfa[ i ].labels );
            }
      }

      protected void collectOffsets( NondetWordAutom nfa[] ) {
            this.offset = new int[ nfa.length + 1 ];
            offset[ 0 ] = 1; // we have a new initial state
            for( int i = 0; i < nfa.length ; i++ )
                  offset[ i + 1 ] = nfa[ i ].nstates + offset[ i ];

      }

      /** collapses several normalized NondetWordAutom objects into one.
       */

      public NondetWordAutom( NondetWordAutom nfa[] ) {


            //this.m
            int m = nfa.length;
            //System.out.println("enter NondetWordSwitch, "
            //                   +"combining " + m + " automata");

            collectLabels( nfa );
            collectOffsets( nfa );

            this.nstates = offset[ nfa.length ]; //m - 1 ] + nfa[ m - 1 ].nstates;


            this.finals = new TreeMap();

            this.qbinders = new Vector[ nstates ];

            // new initial state gets all transitions from all initial states

            this.deltaq        = new HashMap[ nstates ];
            this.defaultq      = new Vector [ nstates ];

            //TreeSet defaultqSet = new TreeSet();
            deltaq[ 0 ] = new HashMap(); // 0 = our new initial state

            TreeSet initials = new TreeSet();


            for( int i = 0; i < m; i++ ) {
                  //System.out.println("i (current NFA):"+i);

                  NondetWordAutom n = nfa[ i ];

                  int offs = offset[ i ];

                  initials.add( new Integer( offs ));

                  n.relocate( offs,
                              this.finals,
                              this.deltaq,
                              this.defaultq,
                              (Vector[])  this.qbinders );
            }

            normalize( initials, false );

      }




      public void print() {

            System.out.print("NFA on labels "+ this.labels);

            if( offset != null ) {
                  System.out.print("offset");
                  for( int k = 0; k < offset.length; k++ ) {
                        if( k > 0)
                              System.out.print(", ");
                        System.out.print(offset[k]);
                  }
            }
            System.out.println();

            System.out.print("max state number :" + (nstates - 1)  );

            System.out.println("initials" + initials);

            System.out.println("finals" + finals);

            for( int i = 0; i < nstates; i++ ) {
                  System.out.print("state: " + i);
                  if( finals.containsKey( new Integer( i )) ){
                        System.out.print("*"); //final
                  }
                  System.out.print("  transitions: {");
                  HashMap arrows = deltaq[ i ];

                  for( Iterator it = arrows.keySet().iterator();
                       it.hasNext(); ) {
                        Object label = it.next();
                        Vector targets = (Vector) arrows.get( label );
                        for( Iterator jt = targets.iterator();
                             jt.hasNext(); ) {
                              Integer p = (Integer) jt.next();
                              System.out.print("("+label+","+p+")");
                        }
                  }

                  System.out.print("} ");
                  System.out.print(" default transitions: "+defaultq( i ));
                  if( qbinders != null )
                        System.out.println(" binders "+qbinders[ i ]);
                  System.out.println();

            }

      }

}