diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala')
-rw-r--r-- | src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala | 522 |
1 files changed, 522 insertions, 0 deletions
diff --git a/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala b/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala new file mode 100644 index 0000000000..cd1d8b576e --- /dev/null +++ b/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala @@ -0,0 +1,522 @@ +package scala.tools.nsc.matching ; +import java.util._ ; + +trait NondetWordAutoms { +/** a nondeterministic word automaton. + * states are represented (implicitly) as Integer objects. + */ +class NondetWordAutom { + // BEGIN stuff from FiniteAutom + + //final static Integer FINTAG = new Integer(0); + + /** number of states */ + var nstates: int =_; + + /** the 'alphabet' */ + var labels: HashSet = _; + + /** the set of final states, here as a TreeMap */ + var finals: TreeMap = _; + + /** 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' } ) + */ + + var _deltaq:Array[HashMap] = _; + + var _defaultq:Array[Vector] = _; // this gives the default transitions + + //public HashMap deltaq[]; + + // --- accessor methods + + /** returns number of states + def nstates(): int = { + return nstates; + } + */ + + /** returns the labels + def labels(): HashSet = { + return _labels; + } + */ + + /** returns the transitions + */ + def deltaq( state: int ):HashMap = { + return _deltaq( state ); + } + + /** returns the transitions + */ + def deltaq( state: Integer ): HashMap = { + return _deltaq( state.intValue() ); + } + + /** returns the transitions + */ + def defaultq( state: int ): Vector = { + return _defaultq( state ); + } + + /** returns the transitions + */ + def defaultq( state:Integer ): Vector = { + return _defaultq( state.intValue() ); + } + + + /** returns true if the state is final + */ + def isFinal( state:int ): boolean = { + return ((finals != null) + && (finals.get( new Integer( state )) != null)); + } + + /** returns true if the state is final + */ + def isFinal( state:Integer ): boolean = { + return ((finals != null) && finals.containsKey( state )); + } + + /** returns true if the state is final + */ + def finalTag( state: Integer ): Integer = { + return finals.get( state ).asInstanceOf[Integer]; + } + + + def finalTag( state:int ): Integer = { + return finals.get( new Integer (state )).asInstanceOf[Integer]; + } + + /** returns true if the set of states contains at least one final state + */ + def containsFinal( Q:TreeSet ): boolean = { + var it = Q.iterator(); + while(it.hasNext()) { + if( isFinal( it.next().asInstanceOf[Integer])) + return true; + } + return false; + } + + + /** returns true if there are no finite states + */ + def isEmpty(): boolean = 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; + + var initials: TreeSet = _; // ? need this ? + // --- + + // Object deltaq --> + // HashMap deltaq[]; // this gives the transitions of q; + + var leftTrans: boolean = _; + var rightTrans: boolean = _; + + /** 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. + */ + def producesRun(): boolean = { + return leftTrans; + } + + def consumesRun(): boolean = { + return rightTrans; + } + + def initial( i: Integer ): boolean = { + return initials.contains( i ); + } + var qbinders: Array[Vector] = _; + + /** returns all states accessible from Qsrc via label. + * used by class DetWordAutomaton. + */ + def getSide ( Qsrc:TreeSet , label:Object ): TreeSet = { + //Console.println("NWA::getSide(Qsrc="+Qsrc); + val Qdest = new TreeSet(); + var it = Qsrc.iterator(); + while(it.hasNext()) {// state + val q = it.next().asInstanceOf[Integer].intValue(); + val ps = deltaq( q ).get( label ).asInstanceOf[Vector]; + //Console.println("deltaq(q) = "+deltaq(q)); + //Console.println("_deltaq(q) = "+_deltaq(q)); + //Console.println("ps = "+ps); + if( null != ps ) { + Qdest.addAll( ps ); + } + //Console.println("defq = "+_defaultq( q )); + Qdest.addAll( _defaultq( q ) ); + } + //Console.println("DONE-NWA::getSide"); + return Qdest; + } + + /** returns the transitions + */ + def defaultq( P1: Set ): Object = { + val defTarget = new TreeSet(); + var p1 = P1.iterator(); + while(p1.hasNext()) { + val q1 = p1.next().asInstanceOf[Integer].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 + */ + def finalTag( Q:Set ): Integer = { + + var min = Integer.MAX_VALUE ; + var it = Q.iterator(); + while(it.hasNext()) { + val state = it.next().asInstanceOf[Integer]; + val tag = finals.get( state ).asInstanceOf[Integer]; + if( tag != null ) { + if( tag.intValue() < min ) + min = tag.intValue(); + } + } + + if ( min == Integer.MAX_VALUE ) + scala.Predef.error( "there should be a final state "); + + return new Integer( min ); + } + + /* + 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 + def mapmap(src:Map, offset:int , dest:Map , mapkeys:boolean , mapvals:boolean ): Map = { + var it = src.keySet().iterator(); + while(it.hasNext()) { + var key = it.next(); + var value = src.get( key ); + if( mapkeys ) key = new Integer( key.asInstanceOf[Integer].intValue() + + offset ); + if( mapvals ) value = vmap( offset, value.asInstanceOf[Vector] ) ; + /* new Integer( ((Integer)val).intValue() + + offset ); + */ + dest.put( key, value ); + } + return dest; + } + + def vmap(offs:int , v:Vector ): Vector = { + if( v == null ) + return null; + var res = new Vector( v.size() ); + var it = v.iterator(); + while(it.hasNext()) { + val item = it.next().asInstanceOf[Integer]; + res.add( new Integer( item.intValue() + offs )); + } + return res; + + } + + /* + 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. + */ + def relocate( offset:int, _finals:TreeMap, _deltaq1:Array[HashMap], _defaultq1:Array[Vector], _qbinders1:Array[Vector] ): Unit = { + + mapmap( finals, offset, _finals, true, false); + var i = 0; + while(i < this.nstates) { + + _deltaq1 ( i + offset ) = + mapmap( deltaq( i ), offset, new HashMap(), false, true).asInstanceOf[HashMap]; + + _defaultq1( i + offset ) = vmap( offset, this.defaultq( i ) ); + i = i + 1; + } + if ((_qbinders1 != null) &&( qbinders != null )) { + i = 0; + while(i < this.nstates ) { + //System.out.println("hallo"+qbinders); + //System.out.println("qbinders[ i ] :"+qbinders[ i ]); + //assert _qbinders != null; + //System.out.println("_qbinders :"+_qbinders); + + _qbinders1( i + offset ) = qbinders( i ); + i = i + 1 + } + } + } + + + /** if there is more than one initial state, a new initial state + * is created, with index 0 + */ + def normalize( initials:TreeSet , reloc:boolean ): Unit = { + //if( initials.size() == 1 ) + // return; + + var idelta = new HashMap(); + var idefault = new TreeSet(); + + var q0 = new Integer( 0 ); + + var it = initials.iterator(); + while(it.hasNext()) { + + val ostate = it.next().asInstanceOf[Integer]; + + val finTag = finals.get( ostate ).asInstanceOf[Integer] ; + if(( finTag != null ) && ( finals.get( q0 ) == null)) + finals.put( q0, finTag ); + + + var tmp = deltaq( ostate ); + + if( reloc ) + tmp = mapmap( tmp, 1, new HashMap(), false, true ).asInstanceOf[HashMap]; + + val labs = tmp.keySet().iterator(); + while(labs.hasNext()) { + val lab = labs.next(); + var itarget = idelta.get( lab ).asInstanceOf[Vector]; + if( null == itarget ) + idelta.put( lab, {itarget = new Vector(); itarget}); + val otarget = tmp.get( lab ).asInstanceOf[Vector]; + itarget.addAll( otarget ); + } + //System.out.println( "normalize:defaultq[ "+ostate+" ] "+((Vector[]) defaultq) [ ostate.intValue() ]); + if( defaultq( ostate ) != null ) + idefault.addAll( defaultq( ostate ) ); + } + + if( reloc ) { + val m = 1 + this.nstates; + val _finals = new TreeMap(); + val _deltaq = new Array[HashMap]( m ); + val _defaultq = new Array[Vector]( m ); + var _qbinders: Array[Vector] = null; + + if( qbinders != null ) + _qbinders = new Array[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 ); + } + + + /** called from Berry-Sethi construction. + */ + + def this(nstates:int, _labels:HashSet, initials: TreeSet, finals:TreeMap, deltaq:Array[HashMap], defaultq:Array[Vector], qbinders:Object ) = { + this(); + //Console.println("NWA::this(. . . . )"); + this.nstates = nstates; + this.labels = _labels; + this.initials = initials; + this.finals = finals; + this._deltaq = deltaq; + this._defaultq = defaultq; + this.qbinders = qbinders.asInstanceOf[Array[Vector]]; + //print(); + //System.exit(0); + } + + + + var offset:Array[int] = _; // only used if constructed from multiple + + def collectLabels( nfa:Array[NondetWordAutom ] ): Unit = { + this.labels = new HashSet(); + var i = 0; + while(i < nfa.length) { + this.labels.addAll( nfa( i ).labels ); + i = i + 1 + } + } + + def collectOffsets( nfa:Array[NondetWordAutom] ): Unit = { + this.offset = new Array[int]( nfa.length + 1 ); + offset( 0 ) = 1; // we have a new initial state + var i = 0; + while(i < nfa.length ) { + offset( i + 1 ) = nfa( i ).nstates + offset( i ); + i = i + 1 + } + } + + /** collapses several normalized NondetWordAutom objects into one. + */ + + def this( nfa: Array[NondetWordAutom] ) = { + this(); + //Console.println("NWA::this(.)"); + + //this.m + val m = nfa.length; + //System.out.println("enter NondetWordSwitch, " + // +"combining " + m + " automata"); + + collectLabels( nfa ); + collectOffsets( nfa ); + + //Console.println(" X 1"); + + + this.nstates = offset( nfa.length ); //m - 1 ] + nfa[ m - 1 ].nstates; + + + this.finals = new TreeMap(); + + this.qbinders = new Array[Vector]( nstates ); + + // new initial state gets all transitions from all initial states + + this._deltaq = new Array[HashMap]( nstates ); + this._defaultq = new Array[Vector]( nstates ); + //Console.println(" X 2"); + + //TreeSet defaultqSet = new TreeSet(); + _deltaq( 0 ) = new HashMap(); // 0 = our new initial state + + val initials = new TreeSet(); + + var i = 0; + while(i < m) { + //System.out.println("i (current NFA):"+i); + + val n = nfa( i ); + + val offs = offset( i ); + + initials.add( new Integer( offs )); + + n.relocate( offs, + this.finals, + this._deltaq, + this._defaultq, + this.qbinders ); + i = i + 1; + } + + normalize( initials, false ); + //Console.println("Leave-NWA::this(.)"); + } + + + + + def print(): Unit = { + + Console.print("NFA on labels "+ this.labels); + + if( offset != null ) { + Console.print("offset"); + var k = 0; + while(k < offset.length) { + if( k > 0) + Console.print(", "); + Console.print(offset(k)); + k = k + 1; + } + } + Console.println; + + Console.print("max state number :" + (nstates - 1) ); + + Console.println("initials" + initials); + + Console.println("finals" + finals); + + var i = 0; + while(i < nstates) { + Console.print("state: " + i); + if( finals.containsKey( new Integer( i )) ){ + Console.print("*"); //final + } + Console.print(" transitions: {"); + var arrows:HashMap = deltaq( i ); + + var it = arrows.keySet().iterator(); + while(it.hasNext()) { + val label = it.next(); + val targets = arrows.get( label ).asInstanceOf[Vector]; + val jt = targets.iterator(); + while(jt.hasNext()) { + val p = jt.next().asInstanceOf[Integer]; + Console.print("("+label+","+p+")"); + } + } + + Console.print("} "); + Console.print(" default transitions: "+_defaultq( i )); + if( null != qbinders ) + Console.println(" binders "+qbinders( i )); + Console.println; + i = i + 1; + } + } + + +} + +} |