State.java
001 /*
002  *  State.java
003  *
004  *  Copyright (c) 1995-2012, The University of Sheffield. See the file
005  *  COPYRIGHT.txt in the software or at http://gate.ac.uk/gate/COPYRIGHT.txt
006  *
007  *  This file is part of GATE (see http://gate.ac.uk/), and is free
008  *  software, licenced under the GNU Library General Public License,
009  *  Version 2, June 1991 (in the distribution as file licence.html,
010  *  and also available at http://gate.ac.uk/gate/licence.html).
011  *
012  *  Valentin Tablan, 11/Apr/2000
013  *
014  *  $Id: State.java 17699 2014-03-19 09:11:55Z markagreenwood $
015  */
016 
017 package gate.fsm;
018 
019 import gate.jape.BasicPatternElement;
020 import gate.jape.JapeConstants;
021 import gate.jape.RightHandSide;
022 import gate.util.SimpleArraySet;
023 
024 import java.util.Iterator;
025 import java.util.List;
026 import java.util.Map;
027 
028 /**
029  * This class implements a Finite State Machine state.
030  *
031  */
032 public class State implements JapeConstants {
033 
034   private static final long serialVersionUID = 1733852753275942428L;
035 
036   public static final int UNKNOWN_INDEX = 1;
037   public static final int VISITED_INDEX = -2;
038   public static final int UNVISITED_INDEX = 2;
039   public static final int INITIAL_INDEX = 0;
040   public static final String INITIAL_RULE = "_____Initial_State_for_all_rules";
041   public static final String UNKNOWN_RULE = "___UNKNOWN_RULES_TYPE_1";
042   public static final String UNVISITED_RULE = "___UNKNOWN_RULES_TYPE_2";
043   
044   // Points to the rule in the FSM which created this state
045   private int indexInRuleList = UNVISITED_INDEX;
046   
047   /**
048    
049    @return  The index of the rule in the ruleTimes ArrayList held in the FSM
050    */
051   public int getIndexInRuleList() {
052     return indexInRuleList;
053   }
054 
055   /**
056    * This should only need to be called by getRuleForState when the state is being initialized
057    @param indexInRuleList
058    */
059   void setIndexInRuleList(int indexInRuleList) {
060     this.indexInRuleList = indexInRuleList;
061   }
062   
063   /**
064    * Sets the index of the rule for this state.
065    * Determines the appropriate rule by recursively searching this state's outbound transitions until
066    * we reach a final state.  Record this state in the ruleTimes and ruleNameToIndexMap structures
067    */
068   public int getRuleForState(Map<String,Integer> ruleNameToIndexMap, List<RuleTime>ruleTimes) {
069     if (this.getIndexInRuleList() != UNVISITED_INDEX) {
070       return this.getIndexInRuleList();  
071     }
072     if (this.isFinal()) {
073       String ruleNameOfThisState = this.getAction().getRuleName();
074       int returnVal;
075       if (ruleNameToIndexMap.containsKey(ruleNameOfThisState)) {
076         returnVal =  ruleNameToIndexMap.get(ruleNameOfThisState);
077       }
078       else {
079         ruleTimes.add(new RuleTime(0,ruleNameOfThisState));
080         ruleNameToIndexMap.put(ruleNameOfThisState, ruleTimes.size() 1);
081         returnVal =  ruleTimes.size() 1;
082       }
083       this.setIndexInRuleList(returnVal);
084       return returnVal;
085     }
086     else {
087       this.setIndexInRuleList(VISITED_INDEX);
088       int returnVal = UNKNOWN_INDEX;
089       // Note that returnVal will always need to be the same for all returned elements
090       // (because a state is currently associated with only one rule), but
091       // we need to call it repeateadly to set the indexInRuleList for all states in 
092       // the tree
093       for (Transition t :this.getTransitions()) {
094         int tempReturn = t.getTarget().getRuleForState(ruleNameToIndexMap,ruleTimes);
095         if (tempReturn != UNKNOWN_INDEX && tempReturn != VISITED_INDEX) {
096           returnVal = tempReturn;
097         }
098       }
099       if (returnVal == UNKNOWN_INDEX) {
100         this.setIndexInRuleList(returnVal);
101       }
102       else {
103         this.propogateRuleForward(returnVal);
104       }
105       return returnVal;
106     }
107   }
108 
109 
110   /**
111    * This sets the rule index for every descendant of the current state
112    * Note that we only need to set the state for states whose rule is Unknown
113    * Rules whose state is "VISITED_INDEX" are my ancestors.  Their states will be set
114    * when the recursion backs out.  Rules whose index is something other than VISITED_INDEX or
115    * UNKNOWN_RULE are finished and we know that all of their descendants have been set, by
116    * the properties of this algorithm 
117    @param ruleForThisState   The rule to be associated with this state
118    */
119   private void propogateRuleForward(int ruleForThisState) {
120     this.setIndexInRuleList(ruleForThisState);
121     for (Transition t: this.getTransitions()) {
122       if (t.getTarget().getIndexInRuleList() == UNKNOWN_INDEX) {
123         t.getTarget().propogateRuleForward(ruleForThisState);
124       }
125     }
126   }
127 
128   /**
129    * Build a new state.
130    */
131   public State() {
132     myIndex = State.index++;
133     isFinal = false;
134   }
135 
136   /**
137    * Reports if this state is a final one.
138    * Note: A state has an associated action if and only if it is final.
139    */
140   public boolean isFinal() {
141     return isFinal;
142   }
143 
144   /**
145    * Gets the set of transitions for this state.
146    *
147    @return a Set contining objects of type gate.fsm.Transition
148    */
149 // >>> DAM, was Set
150 /*
151   public Set getTransitions() {
152     return transitions;
153   }
154 */
155 // >>> DAM, TransArray optimization
156   public SimpleArraySet<Transition> getTransitions() {
157     return transitions;
158   }
159 // >>> DAM, end
160   /** Sets the action associated to this FINAL state. An action is actually
161    * a gate.jape.RightHandSide object.
162    * NOTE: only a final state has an associated action so after a call to this
163    * method this state will be a final one.
164    */
165   protected void setAction(RightHandSide rhs) {
166     action = rhs;
167     isFinal = (action != null);
168   }
169 
170   /** Sets the value for fileIndex. File index is the index in the jape
171    * definition file of the rule that contains as right hand side the action
172    * associated to this state. This value is only intended for final states.
173    */
174   protected void setFileIndex(int i) { fileIndex = i; }
175 
176   /** Sets the value for priority. Priority is the priority in the jape
177    * definition file of the rule that contains as right hand side the action
178    * associated to this state. This value is only intended for final states.
179    */
180   protected void setPriority(int i) { priority = i; }
181 
182   /**
183    * Gets the action associated to this state.
184    *
185    @return a RightHandSide object
186    */
187   public RightHandSide getAction() {
188     return action;
189   }
190 
191   /**
192    * Returns the index in the definition file of the rule that generated this
193    * state.
194    * The value for fileIndex is correct only on final states!
195    */
196   protected int getFileIndex() { return fileIndex; }
197 
198   /**
199    * Returns the priority in the definition file of the rule that generated
200    * this state.
201    * This value is correct only on final states!
202    */
203   protected int getPriority() { return priority; }
204 
205   /**
206    * Adds a new transition to the list of outgoing transitions for this state.
207    *
208    @param transition the transition to be added
209    */
210   public void addTransition(Transition transition) {
211     transitions.add(transition);
212   // addTransition
213 
214   /**
215    * Gets the index of this state. Each state has a unique index (a int value).
216    * This value is not actually used by any of the algorithms. It is useful only
217    * as a way of refering to states in string representations so it is used by
218    * toString and GML related methods.
219    *
220    @return the index associated to this state
221    */
222   public int getIndex() {
223     return myIndex;
224   }// getIndex
225 
226   /**
227    * Returns a GML (graph modelling language) representation for the edges
228    * corresponding to transitions departing from this state in the
229    * transition graph of the FSM to which this state belongs
230    *
231    @return a string value contining the GML text
232    */
233   public String getEdgesGML() {
234 ///    String res = "";
235     StringBuffer res = new StringBuffer(gate.Gate.STRINGBUFFER_SIZE);
236 
237     Iterator<Transition> transIter = transitions.iterator();
238     BasicPatternElement bpe;
239 
240     while(transIter.hasNext()) {
241       Transition currentTrans = transIter.next();
242 /*      res += "edge [ source " + myIndex +
243              " target " + currentTrans.getTarget().getIndex() +
244              " label \"" + currentTrans.shortDesc() + ":";
245 */
246         res.append("edge [ source ");
247         res.append(myIndex);
248         res.append(" target ");
249         res.append(currentTrans.getTarget().getIndex());
250         res.append(" label \"");
251         res.append(currentTrans.shortDesc());
252         res.append(":");
253 
254              bpe = currentTrans.getConstraints();
255              if(bpe == null///res += "null";
256                 res.append("null");
257              else ///res += bpe.shortDesc();
258                 res.append(bpe.shortDesc());
259 ///             res += " :" + currentTrans.getBindings() +              "\" ]\n";
260              res.append(" :");
261              res.append(currentTrans.getBindings());
262              res.append("\" ]\n");
263     }
264     return res.toString();
265   // getEdgesGML
266 
267   /**
268    * Returns a textual description of this state
269    *
270    @return a String value.
271    */
272   @Override
273   public String toString() {
274 ///    String res = "State " + myIndex;
275     StringBuffer res = new StringBuffer(gate.Gate.STRINGBUFFER_SIZE);
276 
277     if(isFinal()) ///res += "\nFinal!";
278         res.append("\nFinal!");
279 
280     ///res += "\nTransitions:\n";
281     res.append("\nTransitions:\n");
282 
283     Iterator<Transition> transIter = transitions.iterator();
284     while(transIter.hasNext()){
285       ///res += transIter.next().toString();
286       res.append(transIter.next().toString());
287     }
288     return res.toString();
289   }
290 
291 
292   /**
293    * A set of objects of type gata.fsm.Transition representing the outgoing
294    * transitions.
295    */
296 // >>> DAM was
297 /*
298   private Set transitions = new HashSet();
299 */
300 // >>> DAM, TransArray optimization
301   private SimpleArraySet<Transition> transitions = new SimpleArraySet<Transition>();
302 // >>> DAM, end
303 
304   /**
305    * Is this state a final one?
306    */
307   protected boolean isFinal = false;
308 
309   /**
310    * The right hand side associated to the rule for which this state recognizes
311    * the lhs.
312    */
313   protected RightHandSide action = null;
314 
315   /**
316    * The unique index of this state.
317    */
318   protected int myIndex;
319 
320   /**
321    * The class data member used for generating unique indices for State
322    * instances.
323    */
324   protected static int index = 0;
325 
326   /**
327    * The index in the definition file of the rule that was used for creating
328    * this state.
329    * NOTE: this member is consistent only for FINAL STATES!
330    */
331   protected int fileIndex = 0;
332 
333   /**
334    * The priority of the rule from which this state derived.
335    *
336    */
337   protected int priority = -1;
338 
339 // State