1   /*
2    *  SinglePhaseTransducer.java - transducer class
3    *
4    *  Copyright (c) 1998-2005, The University of Sheffield.
5    *
6    *  This file is part of GATE (see http://gate.ac.uk/), and is free
7    *  software, licenced under the GNU Library General Public License,
8    *  Version 2, June 1991 (in the distribution as file licence.html,
9    *  and also available at http://gate.ac.uk/gate/licence.html).
10   *
11   *  Hamish Cunningham, 24/07/98
12   *
13   *  $Id: SinglePhaseTransducer.java,v 1.82 2006/03/27 13:48:08 andrey_shafirin Exp $
14   */
15  
16  
17  package gate.jape;
18  
19  import java.util.*;
20  
21  import gate.*;
22  import gate.annotation.AnnotationSetImpl;
23  import gate.creole.ExecutionException;
24  import gate.creole.ExecutionInterruptedException;
25  import gate.event.ProgressListener;
26  import gate.fsm.*;
27  import gate.util.*;
28  
29  // by Shafirin Andrey start
30  import debugger.resources.pr.TraceContainer;
31  import debugger.resources.pr.RuleTrace;
32  import debugger.resources.SPTLock;
33  import debugger.resources.PhaseController;
34  // by Shafirin Andrey end
35  
36  /**
37    * Represents a complete CPSL grammar, with a phase name, options and
38    * rule set (accessible by name and by sequence).
39    * Implements a transduce method taking a Document as input.
40    * Constructs from String or File.
41    */
42  public class SinglePhaseTransducer
43  extends Transducer implements JapeConstants, java.io.Serializable
44  {
45    /* A structure to pass information to/from the fireRule() method.  Since
46     * Java won't let us return multiple values, we stuff them into a
47     * 'state' object that fireRule() can update.
48     */
49    protected static class SearchState {
50        Node startNode;
51        long startNodeOff;
52        long oldStartNodeOff;
53  
54        SearchState (Node startNode, long startNodeOff, long oldStartNodeOff) {
55      this.startNode = startNode;
56      this.startNodeOff = startNodeOff;
57      this.oldStartNodeOff = oldStartNodeOff;
58        }
59    }
60  
61    /** Debug flag */
62    private static final boolean DEBUG = false;
63    
64  // by Shafirin Andrey start
65      PhaseController phaseController = null;
66      TraceContainer rulesTrace = null;
67      RuleTrace currRuleTrace = null;
68  
69      public PhaseController getPhaseController() {
70          return phaseController;
71      }
72  
73      public void setPhaseController(PhaseController phaseController) {
74          this.phaseController = phaseController;
75      }
76  // by Shafirin Andrey end
77  
78  
79    /** Construction from name. */
80    public SinglePhaseTransducer(String name) {
81      this.name = name;
82      rules = new PrioritisedRuleList();
83      finishedAlready = false;
84    } // Construction from name
85  
86    /** Type of rule application (constants defined in JapeConstants). */
87    protected int ruleApplicationStyle = BRILL_STYLE;
88  
89    /** Set the type of rule application (types defined in JapeConstants). */
90    public void setRuleApplicationStyle(int style) {
91      ruleApplicationStyle = style;
92    }
93  
94    /** The list of rules in this transducer. Ordered by priority and
95      * addition sequence (which will be file position if they come from
96      * a file).
97      */
98    protected PrioritisedRuleList rules;
99  
100   protected FSM fsm;
101 
102   public FSM getFSM(){
103     return fsm;
104   }
105 
106   /** Add a rule. */
107   public void addRule(Rule rule) {
108     rules.add(rule);
109   } // addRule
110 
111   /** The values of any option settings given. */
112   private java.util.HashMap optionSettings = new java.util.HashMap();
113 
114   /** Add an option setting. If this option is set already, the new
115     * value overwrites the previous one.
116     */
117   public void setOption(String name, String setting) {
118     optionSettings.put(name, setting);
119   } // setOption
120 
121   /** Get the value for a particular option. */
122   public String getOption(String name) {
123     return (String) optionSettings.get(name);
124   } // getOption
125 
126   /** Whether the finish method has been called or not. */
127   protected boolean finishedAlready;
128 
129   /** Finish: replace dynamic data structures with Java arrays; called
130     * after parsing.
131     */
132   public void finish(){
133     // both MPT and SPT have finish called on them by the parser...
134      if (finishedAlready)
135        return;
136      finishedAlready = true;
137 
138     //each rule has a RHS which has a string for java code
139     //those strings need to be compiled now
140     Map actionClasses = new HashMap(rules.size());
141     for(Iterator i = rules.iterator(); i.hasNext(); ){
142       Rule rule = (Rule)i.next();
143       rule.finish();
144       actionClasses.put(rule.getRHS().getActionClassName(),
145                         rule.getRHS().getActionClassString());
146     } 
147     try{
148       gate.util.Javac.loadClasses(actionClasses);
149     }catch(Exception e){
150       throw new GateRuntimeException (e);
151     }
152 
153     //build the finite state machine transition graph
154     fsm = createFSM();
155     //clear the old style data structures
156     rules.clear();
157     rules = null;
158   } // finish
159   
160   protected FSM createFSM() {
161       return new FSM(this);
162   }
163 
164 //dam: was
165 //  private void addAnnotationsByOffset(Map map, SortedSet keys, Set annotations){
166   private void addAnnotationsByOffset(/*Map map,*/ SimpleSortedSet keys, Set annotations){
167     Iterator annIter = annotations.iterator();
168     while(annIter.hasNext()){
169       Annotation ann = (Annotation)annIter.next();
170       //ignore empty annotations
171       long offset = ann.getStartNode().getOffset().longValue();
172       if(offset == ann.getEndNode().getOffset().longValue())
173         continue;
174 //dam: was
175 /*
176 //      Long offset = ann.getStartNode().getOffset();
177 
178       List annsAtThisOffset = null;
179       if(keys.add(offset)){
180         annsAtThisOffset = new LinkedList();
181         map.put(offset, annsAtThisOffset);
182       }else{
183         annsAtThisOffset = (List)map.get(offset);
184       }
185       annsAtThisOffset.add(ann);
186 */
187 //dam: end
188       keys.add(offset, ann);
189     }
190   }//private void addAnnotationsByOffset()
191 
192 
193   /**
194     * Transduce a document using the annotation set provided and the current
195     * rule application style.
196     */
197   public void transduce(Document doc, AnnotationSet inputAS,
198                         AnnotationSet outputAS) throws JapeException,
199                                                        ExecutionException {
200     interrupted = false;
201     fireProgressChanged(0);
202 
203     //the input annotations will be read from this map
204     //maps offset to list of annotations
205     SimpleSortedSet offsets = new SimpleSortedSet();
206     SimpleSortedSet annotationsByOffset = offsets;
207 
208     //select only the annotations of types specified in the input list
209     if(input.isEmpty()) {
210         addAnnotationsByOffset(offsets, inputAS);
211     } else {
212   Iterator typesIter = input.iterator();
213   AnnotationSet ofOneType = null;
214   while(typesIter.hasNext()){
215       ofOneType = inputAS.get((String)typesIter.next());
216       if(ofOneType != null){
217     addAnnotationsByOffset(offsets, ofOneType);
218       }
219   }
220     }
221 
222     if(annotationsByOffset.isEmpty()){
223   fireProcessFinished();
224   return;
225     }
226 
227     annotationsByOffset.sort();
228     //define data structures
229     //FSM instances that haven't blocked yet
230     java.util.ArrayList activeFSMInstances = new java.util.ArrayList();
231 
232     // FSM instances that have reached a final state
233     // This is a list and the contained objects are sorted by the length
234     // of the document content covered by the matched annotations
235     java.util.ArrayList acceptingFSMInstances = new ArrayList();
236     FSMInstance currentFSM;
237 
238 
239     //find the first node of the document
240     Node startNode = ((Annotation)
241             ((ArrayList)annotationsByOffset.get(offsets.first())).get(0)).
242                       getStartNode();
243 
244     //used to calculate the percentage of processing done
245     long lastNodeOff = doc.getContent().size().longValue();
246 
247     //the offset of the node where the matching currently starts
248     //the value -1 marks no more annotations to parse
249     long startNodeOff = startNode.getOffset().longValue();
250 
251     // The structure that fireRule() will update
252     SearchState state = new SearchState(startNode, startNodeOff, 0);
253 
254     // by Shafirin Andrey start (according to Vladimir Karasev)
255     if (gate.Gate.isEnableJapeDebug()) {
256       // by Shafirin Andrey --> if (null != phaseController) {
257       if (null != phaseController) {
258         rulesTrace = new TraceContainer();
259         rulesTrace.putPhaseCut(this, inputAS);
260       }
261     }
262     // by Shafirin Andrey end
263 
264     //the big while for the actual parsing
265     while(state.startNodeOff != -1){
266   //while there are more annotations to parse
267   //create initial active FSM instance starting parsing from new startNode
268   //currentFSM = FSMInstance.getNewInstance(
269   currentFSM = new FSMInstance(
270                   fsm,
271                   fsm.getInitialState(),//fresh start
272                   state.startNode,//the matching starts form the current startNode
273                   state.startNode,//current position in AG is the start position
274                   new java.util.HashMap(),//no bindings yet!
275                   doc
276                   );
277 
278   // at this point ActiveFSMInstances should always be empty!
279   activeFSMInstances.clear();
280   acceptingFSMInstances.clear();
281   activeFSMInstances.add(currentFSM);
282 
283   //far each active FSM Instance, try to advance
284   while(!activeFSMInstances.isEmpty()){
285       
286       boolean isFinal = attemptAdvance(activeFSMInstances, acceptingFSMInstances,
287                offsets, annotationsByOffset, doc);
288 
289       //if we're only looking for the shortest stop here
290       if ( isFinal && ruleApplicationStyle == FIRST_STYLE )
291     break;
292   }
293 
294 
295   boolean keepGoing = fireRule(acceptingFSMInstances, state,
296              lastNodeOff, offsets,
297              inputAS, outputAS, doc, annotationsByOffset);
298   if (!keepGoing)
299       return;
300 
301     }//while(state.startNodeOff != -1)
302     fireProcessFinished();
303   } // transduce
304 
305   /**
306    * Try to advance the activeFSMInstances.
307    * @return true if we ended in a 'final' state, false otherwise.
308    */
309 
310   protected boolean attemptAdvance (java.util.ArrayList activeFSMInstances,
311             java.util.ArrayList acceptingFSMInstances,
312             SimpleSortedSet offsets,
313             SimpleSortedSet annotationsByOffset,
314             Document doc
315             ) throws ExecutionInterruptedException {
316 
317 
318       if(interrupted) throw new ExecutionInterruptedException(
319             "The execution of the \"" + getName() +
320             "\" Jape transducer has been abruptly interrupted!");
321 
322       // take the first active FSM instance
323       FSMInstance currentFSM = (FSMInstance)activeFSMInstances.remove(0);
324     
325       // process the current FSM instance
326       if(currentFSM.getFSMPosition().isFinal()){
327     //the current FSM is in a final state
328     acceptingFSMInstances.add(currentFSM.clone());
329     
330     // if we're only looking for the shortest stop here
331     if (ruleApplicationStyle == FIRST_STYLE) return true; // Ended in a final state
332       }
333 
334       //get all the annotations that start where the current FSM finishes
335         SimpleSortedSet offsetsTailSet = offsets.tailSet(currentFSM.
336                 getAGPosition().getOffset().longValue());
337         ArrayList paths;
338       long theFirst = offsetsTailSet.first();
339       if(theFirst <0) return false;
340 
341       paths = (ArrayList)annotationsByOffset.get(theFirst);
342 
343       if(paths.isEmpty()) return false;
344 
345       Iterator pathsIter = paths.iterator();
346       Annotation onePath;
347       State currentState = currentFSM.getFSMPosition();
348       Iterator transitionsIter;
349       //foreach possible annotation
350       while(pathsIter.hasNext()){
351     onePath = (Annotation)pathsIter.next();
352     transitionsIter = currentState.getTransitions().iterator();
353     Transition currentTransition;
354     Constraint[] currentConstraints;
355     transitionsWhile:
356     while(transitionsIter.hasNext()){
357         currentTransition = (Transition)transitionsIter.next();
358             //check if the current transition can use the current annotation (path)
359         currentConstraints =
360       currentTransition.getConstraints().getConstraints();
361 
362       // We initially only check the first constraint for a match. If it
363       // does match, we go on to check the others with the other annotations
364       // that exist at this point in the doc.
365       if (!onePath.getType().equals(currentConstraints[0].getAnnotType()) ||
366     !onePath.getFeatures().subsumes( ontology, currentConstraints[0].getAttributeSeq() )) {
367     continue transitionsWhile;
368       }
369       
370       Constraint oneConstraint = currentConstraints[0];
371 
372       // The first constraint matches. Now check the other constraints,
373       // which are of a different type.
374       if (currentConstraints.length > 1) {
375     /*
376      * TODO - if there are multiple constraints matching, which
377      * matched constraint do we bind to? For the moment, bind to the
378      * longest one. To be completely correct, we should actually fire
379      * off a new FSMInstance for each potential bind.
380      */
381   
382     int maxEnding = onePath.getEndNode().getOffset().intValue();
383             
384     otherConstraints:
385     for (int i = 1; i < currentConstraints.length; i++) {
386         Constraint c = currentConstraints[i];
387                 
388         // Look for a path that matches c
389         for (Iterator j = paths.iterator(); j.hasNext();) {
390       Annotation a = (Annotation) j.next();
391       if (a.getType().equals(c.getAnnotType()) &&
392           a.getFeatures().subsumes( ontology, c.getAttributeSeq())) {
393                         
394           if (a.getEndNode().getOffset().intValue() > maxEnding) {
395         onePath = a;
396         oneConstraint = c;
397         maxEnding = a.getEndNode().getOffset().intValue();
398           }
399           continue otherConstraints;
400       }
401         }
402         // No match found for c, go to the next transition
403         continue transitionsWhile;
404     }
405       }
406         
407         //we have a match
408         //create a new FSMInstance, advance it over the current annotation
409         //take care of the bindings  and add it to ActiveFSM
410         FSMInstance newFSMI = (FSMInstance)currentFSM.clone();
411         newFSMI.setAGPosition(onePath.getEndNode());
412         newFSMI.setFSMPosition(currentTransition.getTarget());
413 
414               // by Shafirin Andrey start (according to Vladimir Karasev)
415               if(gate.Gate.isEnableJapeDebug()) {
416                 if (null != phaseController) {
417                   currRuleTrace = rulesTrace.getStateContainer(currentFSM.
418                       getFSMPosition());
419                   if (currRuleTrace == null) {
420                     currRuleTrace = new RuleTrace(newFSMI.getFSMPosition(), doc);
421                     currRuleTrace.addAnnotation(onePath);
422                     currRuleTrace.putPattern(onePath,
423                                      oneConstraint.getAttributeSeq());
424                     rulesTrace.add(currRuleTrace);
425                   }
426                   else {
427                     currRuleTrace.addState(newFSMI.getFSMPosition());
428                     currRuleTrace.addAnnotation(onePath);
429                     currRuleTrace.putPattern(onePath,
430                                      oneConstraint.getAttributeSeq());
431                   }
432                 }
433               }
434               // by Shafirin Andrey end
435 
436         //bindings
437         java.util.Map binds = newFSMI.getBindings();
438         java.util.Iterator labelsIter =
439       currentTransition.getBindings().iterator();
440         String oneLabel;
441         AnnotationSet boundAnnots, newSet;
442         while(labelsIter.hasNext()){
443       oneLabel = (String)labelsIter.next();
444       boundAnnots = (AnnotationSet)binds.get(oneLabel);
445                 if(boundAnnots != null)
446                   newSet = new AnnotationSetImpl(boundAnnots);
447                 else
448                   newSet = new AnnotationSetImpl(doc);
449       newSet.add(onePath);
450       binds.put(oneLabel, newSet);
451 
452         }//while(labelsIter.hasNext())
453         activeFSMInstances.add(newFSMI);
454     }//while(transitionsIter.hasNext())
455       }//while(pathsIter.hasNext())
456 
457       return false;
458   } // attemptAdvance
459 
460 
461   /**
462    * Fire the rule that matched.
463    * @return true if processing should keep going, false otherwise.
464    */
465 
466   protected boolean fireRule (java.util.ArrayList acceptingFSMInstances, 
467             SearchState state,
468             long lastNodeOff,
469             SimpleSortedSet offsets,
470             AnnotationSet inputAS,
471             AnnotationSet outputAS,
472             Document doc,
473             SimpleSortedSet annotationsByOffset
474             ) throws JapeException, ExecutionException {
475 
476       Node startNode = state.startNode;
477       long startNodeOff = state.startNodeOff;
478       long oldStartNodeOff = state.oldStartNodeOff;
479 
480       //FIRE THE RULE
481       long lastAGPosition = -1;
482       if(acceptingFSMInstances.isEmpty()){
483     //no rule to fire, advance to the next input offset
484         lastAGPosition = startNodeOff + 1;
485       } else if(ruleApplicationStyle == BRILL_STYLE || 
486                 ruleApplicationStyle == ALL_STYLE) {
487         // fire the rules corresponding to all accepting FSM instances
488         java.util.Iterator accFSMIter = acceptingFSMInstances.iterator();
489     FSMInstance currentAcceptor;
490     RightHandSide currentRHS;
491     lastAGPosition = startNode.getOffset().longValue();
492       
493         while(accFSMIter.hasNext()){
494           currentAcceptor = (FSMInstance) accFSMIter.next();
495           currentRHS = currentAcceptor.getFSMPosition().getAction();
496 
497           // by Shafirin Andrey start
498           // debugger callback
499           if (gate.Gate.isEnableJapeDebug()) {
500             if (null != phaseController) {
501               SPTLock lock = new SPTLock();
502               phaseController.TraceTransit(rulesTrace);
503               rulesTrace = new TraceContainer();
504               phaseController.RuleMatched(lock, this, currentRHS, doc,
505                                           currentAcceptor.getBindings(),
506                                           inputAS, outputAS);
507             }
508           }
509           // by Shafirin Andrey end
510 
511         currentRHS.transduce(doc, currentAcceptor.getBindings(),
512            inputAS, outputAS, ontology);
513 
514           // by Shafirin Andrey start
515           // debugger callback
516           if (gate.Gate.isEnableJapeDebug()) {
517             if (null != phaseController) {
518               SPTLock lock = new SPTLock();
519               phaseController.RuleFinished(lock, this, currentRHS, doc,
520                                            currentAcceptor.getBindings(),
521                                            inputAS, outputAS);
522             }
523           }
524           // by Shafirin Andrey end
525           if(ruleApplicationStyle == BRILL_STYLE){
526       //find the maximal next position
527       long currentAGPosition = currentAcceptor.getAGPosition().getOffset().longValue();
528       if(currentAGPosition > lastAGPosition)
529         lastAGPosition = currentAGPosition;
530           }
531         }
532         if(ruleApplicationStyle == ALL_STYLE){
533           //simply advance to next offset
534           lastAGPosition = lastAGPosition + 1;
535         }
536         
537       } else if(ruleApplicationStyle == APPELT_STYLE ||
538     ruleApplicationStyle == FIRST_STYLE ||
539     ruleApplicationStyle == ONCE_STYLE) {
540 
541     // AcceptingFSMInstances is an ordered structure:
542     // just execute the longest (last) rule
543     Collections.sort(acceptingFSMInstances, Collections.reverseOrder());
544         Iterator accFSMIter = acceptingFSMInstances.iterator();
545         FSMInstance currentAcceptor = (FSMInstance)accFSMIter.next();
546     if(isDebugMode()){
547         //see if we have any conflicts
548         Iterator accIter = acceptingFSMInstances.iterator();
549         FSMInstance anAcceptor;
550         List conflicts = new ArrayList();
551         while(accIter.hasNext()){
552       anAcceptor = (FSMInstance)accIter.next();
553       if(anAcceptor.equals(currentAcceptor)){
554           conflicts.add(anAcceptor);
555       }else{
556           break;
557       }
558         }
559         if(conflicts.size() > 1){
560       Out.prln("\nConflicts found during matching:" +
561          "\n================================");
562       accIter = conflicts.iterator();
563       int i = 0;
564       while(accIter.hasNext()){
565           Out.prln(i++ + ") " + accIter.next().toString());
566       }
567         }
568     }
569         RightHandSide currentRHS = currentAcceptor.getFSMPosition().getAction();
570 
571         // by Shafirin Andrey start
572         // debugger callback
573         if(gate.Gate.isEnableJapeDebug()) {
574           if (null != phaseController) {
575             SPTLock lock = new SPTLock();
576             rulesTrace.leaveLast(currentRHS);
577             phaseController.TraceTransit(rulesTrace);
578             rulesTrace = new TraceContainer();
579             phaseController.RuleMatched(lock, this, currentRHS, doc,
580                                         currentAcceptor.getBindings(),
581                                         inputAS, outputAS);
582           }
583         }
584         // by Shafirin Andrey end
585 
586     currentRHS.transduce(doc, currentAcceptor.getBindings(),
587              inputAS, outputAS, ontology);
588     
589         // by Shafirin Andrey start
590         // debugger callback
591         if(gate.Gate.isEnableJapeDebug()) {
592           if (null != phaseController) {
593             SPTLock lock = new SPTLock();
594             phaseController.RuleFinished(lock, this, currentRHS, doc,
595                                          currentAcceptor.getBindings(),
596                                          inputAS, outputAS);
597           }
598         }
599         // by Shafirin Andrey end
600 
601         //if in matchGroup mode check other possible patterns in this span
602         if(isMatchGroupMode()) {
603           //Out.prln("Jape grammar in MULTI application style.");
604           // ~bp:  check for other matching fsm instances with same length,
605           // priority and rule index : if such execute them also.
606           String currentAcceptorString = null;
607           multiModeWhile: while(accFSMIter.hasNext()) {
608             FSMInstance rivalAcceptor =(FSMInstance) accFSMIter.next();
609             //get rivals that match the same document segment
610             //makes use of the semantic difference between the compareTo and 
611             //equals methods on FSMInstance
612             if(rivalAcceptor.compareTo(currentAcceptor)==0){
613               // gets the rivals that are NOT COMPLETELY IDENTICAL with the
614               // current acceptor.
615               if(!rivalAcceptor.equals(currentAcceptor)){
616                 if (isDebugMode()){ /*depends on the debug option in the transducer */
617                   if (currentAcceptorString == null) {
618                     // first rival
619                     currentAcceptorString = currentAcceptor.toString();
620                     Out.prln("~Jape Grammar Transducer : "+
621                     "\nConcurrent Patterns by length,priority and index (all transduced):");
622                     Out.prln(currentAcceptorString);
623                     Out.prln("bindings : "+currentAcceptor.getBindings());
624                     Out.prln("Rivals Follow: ");
625                   }
626                   Out.prln(rivalAcceptor);
627                   Out.prln("bindings : "+rivalAcceptor.getBindings());
628                 }// DEBUG
629                 currentRHS = rivalAcceptor.getFSMPosition().getAction();
630   
631                 // by Shafirin Andrey start
632                 // debugger callback
633                 if(gate.Gate.isEnableJapeDebug()) {
634                   if (null != phaseController) {
635                     SPTLock lock = new SPTLock();
636                     rulesTrace.leaveLast(currentRHS);
637                     phaseController.TraceTransit(rulesTrace);
638                     rulesTrace = new TraceContainer();
639                     phaseController.RuleMatched(lock, this, currentRHS, doc,
640                                                 rivalAcceptor.getBindings(),
641                                                 inputAS, outputAS);
642                   }
643                 }
644                 // by Shafirin Andrey end
645   
646                 currentRHS.transduce(doc, rivalAcceptor.getBindings(),
647                                      inputAS, outputAS, ontology);
648   
649                 // by Shafirin Andrey start
650                 // debugger callback
651                 if(gate.Gate.isEnableJapeDebug()) {
652                   if (null != phaseController) {
653                     SPTLock lock = new SPTLock();
654                     phaseController.RuleFinished(lock, this, currentRHS, doc,
655                                                  rivalAcceptor.getBindings(),
656                                                  inputAS, outputAS);
657                   }
658                 }
659                 // by Shafirin Andrey end
660               } // equal rival
661             }else{
662               //if rival is not equal this means that there are no further
663               // equal rivals (since the list is sorted)
664               break multiModeWhile;
665             }
666           } // while there are fsm instances
667         } // matchGroupMode
668 
669     //if in ONCE mode stop after first match
670     if(ruleApplicationStyle == ONCE_STYLE) {
671         state.startNodeOff = startNodeOff;
672         return false;
673     }
674     
675     //advance in AG
676     lastAGPosition = currentAcceptor.getAGPosition().getOffset().longValue();
677       }else throw new RuntimeException("Unknown rule application style!");
678 
679 
680       //advance on input
681       SimpleSortedSet OffsetsTailSet = offsets.tailSet(lastAGPosition);
682       long theFirst = OffsetsTailSet.first();
683       if( theFirst < 0){
684     //no more input, phew! :)
685     startNodeOff = -1;
686     fireProcessFinished();
687       }else{
688     long nextKey = theFirst;
689     startNode = ((Annotation)
690            ((ArrayList)annotationsByOffset.get(nextKey)).get(0)). //nextKey
691         getStartNode();
692     startNodeOff = startNode.getOffset().longValue();
693     
694     //eliminate the possibility for infinite looping
695     if(oldStartNodeOff == startNodeOff){
696         //we are about to step twice in the same place, ...skip ahead
697         lastAGPosition = startNodeOff + 1;
698         OffsetsTailSet = offsets.tailSet(lastAGPosition);
699         theFirst = OffsetsTailSet.first();
700         if(theFirst < 0){
701       //no more input, phew! :)
702       startNodeOff = -1;
703       fireProcessFinished();
704         }else{
705       nextKey = theFirst;
706       startNode = ((Annotation)
707              ((List)annotationsByOffset.get(theFirst)).get(0)).
708           getStartNode();
709       startNodeOff =startNode.getOffset().longValue();
710         }
711     }//if(oldStartNodeOff == startNodeOff)
712     //fire the progress event
713     if(startNodeOff - oldStartNodeOff > 256){
714         if(isInterrupted()) throw new ExecutionInterruptedException(
715               "The execution of the \"" + getName() +
716               "\" Jape transducer has been abruptly interrupted!");
717 
718         fireProgressChanged((int)(100 * startNodeOff / lastNodeOff));
719         oldStartNodeOff = startNodeOff;
720     }
721       }
722     // by Shafirin Andrey start (according to Vladimir Karasev)
723     //if(gate.Gate.isEnableJapeDebug()) {
724     //  if (null != phaseController) {
725     //    phaseController.TraceTransit(rulesTrace);
726     //  }
727     //}
728     // by Shafirin Andrey end
729 
730       state.oldStartNodeOff = oldStartNodeOff;
731       state.startNodeOff = startNodeOff;
732       state.startNode = startNode;
733       return true;
734   } // fireRule
735 
736   /** Clean up (delete action class files, for e.g.). */
737   public void cleanUp() {
738 //    for(DListIterator i = rules.begin(); ! i.atEnd(); i.advance())
739 //      ((Rule) i.get()).cleanUp();
740   } // cleanUp
741 
742   /** A string representation of this object. */
743   public String toString() {
744     return toString("");
745   } // toString()
746 
747   /** A string representation of this object. */
748   public String toString(String pad) {
749     String newline = Strings.getNl();
750     String newPad = Strings.addPadding(pad, INDENT_PADDING);
751 
752     StringBuffer buf =
753       new StringBuffer(pad + "SPT: name(" + name + "); ruleApplicationStyle(");
754 
755     switch(ruleApplicationStyle) {
756       case APPELT_STYLE: buf.append("APPELT_STYLE); "); break;
757       case BRILL_STYLE:  buf.append("BRILL_STYLE); ");  break;
758       default: break;
759     }
760 
761     buf.append("rules(" + newline);
762     Iterator rulesIterator = rules.iterator();
763     while(rulesIterator.hasNext())
764       buf.append(((Rule) rulesIterator.next()).toString(newPad) + " ");
765 
766     buf.append(newline + pad + ")." + newline);
767 
768     return buf.toString();
769   } // toString(pad)
770 
771   //needed by fsm
772   public PrioritisedRuleList getRules() {
773     return rules;
774   }
775 
776   /**
777     * Adds a new type of input annotations used by this transducer.
778     * If the list of input types is empty this transducer will parse all the
779     * annotations in the document otherwise the types not found in the input
780     * list will be completely ignored! To be used with caution!
781     */
782   public void addInput(String ident) {
783     input.add(ident);
784   }
785   public synchronized void removeProgressListener(ProgressListener l) {
786     if (progressListeners != null && progressListeners.contains(l)) {
787       Vector v = (Vector) progressListeners.clone();
788       v.removeElement(l);
789       progressListeners = v;
790     }
791   }
792   public synchronized void addProgressListener(ProgressListener l) {
793     Vector v = progressListeners == null ? new Vector(2) : (Vector) progressListeners.clone();
794     if (!v.contains(l)) {
795       v.addElement(l);
796       progressListeners = v;
797     }
798   }
799 
800   /**
801     * Defines the types of input annotations that this transducer reads. If this
802     * set is empty the transducer will read all the annotations otherwise it
803     * will only "see" the annotations of types found in this list ignoring all
804     * other types of annotations.
805     */
806  // by Shafirin Andrey start (modifier changed to public)
807   public java.util.Set input = new java.util.HashSet();
808   //java.util.Set input = new java.util.HashSet();
809   // by Shafirin Andrey end
810   private transient Vector progressListeners;
811 
812   protected void fireProgressChanged(int e) {
813     if (progressListeners != null) {
814       Vector listeners = progressListeners;
815       int count = listeners.size();
816       for (int i = 0; i < count; i++) {
817         ((ProgressListener) listeners.elementAt(i)).progressChanged(e);
818       }
819     }
820   }
821   protected void fireProcessFinished() {
822     if (progressListeners != null) {
823       Vector listeners = progressListeners;
824       int count = listeners.size();
825       for (int i = 0; i < count; i++) {
826         ((ProgressListener) listeners.elementAt(i)).processFinished();
827       }
828     }
829   }
830   public int getRuleApplicationStyle() {
831     return ruleApplicationStyle;
832   }
833 
834   /*
835   private void writeObject(ObjectOutputStream oos) throws IOException {
836     Out.prln("writing spt");
837     oos.defaultWriteObject();
838     Out.prln("finished writing spt");
839   } // writeObject
840   */
841 
842 
843 } // class SinglePhaseTransducer
844 
845 /*
846 class SimpleSortedSet {
847 
848     static final int INCREMENT = 1023;
849     int[] theArray = new int[INCREMENT];
850     Object[] theObject = new Object[INCREMENT];
851     int tsindex = 0;
852     int size = 0;
853     public static int avesize = 0;
854     public static int maxsize = 0;
855     public static int avecount = 0;
856     public SimpleSortedSet()
857     {
858         avecount++;
859         java.util.Arrays.fill(theArray, Integer.MAX_VALUE);
860     }
861 
862     public Object get(int elValue)
863     {
864         int index = java.util.Arrays.binarySearch(theArray, elValue);
865         if (index >=0)
866             return theObject[index];
867         return null;
868     }
869 
870     public boolean add(int elValue, Object o)
871     {
872         int index = java.util.Arrays.binarySearch(theArray, elValue);
873         if (index >=0)
874         {
875             ((ArrayList)theObject[index]).add(o);
876             return false;
877         }
878         if (size == theArray.length)
879         {
880             int[] temp = new int[theArray.length + INCREMENT];
881             Object[] tempO = new Object[theArray.length + INCREMENT];
882             System.arraycopy(theArray, 0, temp, 0, theArray.length);
883             System.arraycopy(theObject, 0, tempO, 0, theArray.length);
884             java.util.Arrays.fill(temp, theArray.length, temp.length , Integer.MAX_VALUE);
885             theArray = temp;
886             theObject = tempO;
887         }
888         index = ~index;
889         System.arraycopy(theArray, index, theArray, index+1, size - index );
890         System.arraycopy(theObject, index, theObject, index+1, size - index );
891         theArray[index] = elValue;
892         theObject[index] = new ArrayList();
893         ((ArrayList)theObject[index]).add(o);
894         size++;
895         return true;
896     }
897     public int first()
898     {
899         if (tsindex >= size) return -1;
900         return theArray[tsindex];
901     }
902 
903     public Object getFirst()
904     {
905         if (tsindex >= size) return null;
906         return theObject[tsindex];
907     }
908 
909     public SimpleSortedSet tailSet(int elValue)
910     {
911         if (tsindex < theArray.length && elValue != theArray[tsindex])
912         {
913             if (tsindex<(size-1) && elValue > theArray[tsindex] &&
914                 elValue <= theArray[tsindex+1])
915                 {
916                     tsindex++;
917                    return this;
918                 }
919             int index = java.util.Arrays.binarySearch(theArray, elValue);
920             if (index < 0)
921                 index = ~index;
922             tsindex = index;
923         }
924         return this;
925     }
926 
927     public boolean isEmpty()
928     {
929         return size ==0;
930     }
931 };
932 */
933