KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sourceforge > groboutils > mbtf > v1 > engine > BreadthPathGenerator


1 /*
2  * @(#)BreadthPathGenerator.java
3  *
4  * Copyright (C) 2002-2003 Matt Albrecht
5  * groboclown@users.sourceforge.net
6  * http://groboutils.sourceforge.net
7  *
8  * Part of the GroboUtils package at:
9  * http://groboutils.sourceforge.net
10  *
11  * Permission is hereby granted, free of charge, to any person obtaining a
12  * copy of this software and associated documentation files (the "Software"),
13  * to deal in the Software without restriction, including without limitation
14  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
15  * and/or sell copies of the Software, and to permit persons to whom the
16  * Software is furnished to do so, subject to the following conditions:
17  *
18  * The above copyright notice and this permission notice shall be included in
19  * all copies or substantial portions of the Software.
20  *
21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
26  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27  * DEALINGS IN THE SOFTWARE.
28  */
29 package net.sourceforge.groboutils.mbtf.v1.engine;
30
31
32 import java.util.Vector JavaDoc;
33 import java.util.Stack JavaDoc;
34 import java.util.Hashtable JavaDoc;
35
36 import net.sourceforge.groboutils.mbtf.v1.IPath;
37 import net.sourceforge.groboutils.mbtf.v1.IState;
38 import net.sourceforge.groboutils.mbtf.v1.ITransition;
39 import net.sourceforge.groboutils.mbtf.v1.IPathGenerator;
40
41 import org.apache.log4j.Logger;
42
43
44 /**
45  * Implements breadth-first path generation.
46  * <P>
47  * @todo Complete the discover end-state transition paths for states.
48  * @todo Add in depth-related-terminal-node ability to add in end-state
49  * paths. Q: how should it handle multiple end-state paths, in
50  * the case of multiple end-states?
51  *
52  * @author Matt Albrecht <a HREF="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
53  * @version $Date: 2003/02/10 22:52:26 $
54  * @since June 12, 2002
55  */
56 public class BreadthPathGenerator implements IPathGenerator
57 {
58     private static final Logger LOG = Logger.getLogger(
59         BreadthPathGenerator.class );
60
61     /**
62      * Parsed form of an IState instance. This is a self-populating list.
63      * It will also populate the constructor hashtable with all enterable
64      * states from this node.
65      */
66     static class InnerState
67     {
68         private IState state;
69         private InnerTransition[] dest;
70         private Vector JavaDoc sources = new Vector JavaDoc();
71         private Vector JavaDoc endStatePaths = new Vector JavaDoc();
72         
73         public InnerState( IState s, Hashtable JavaDoc stateHash )
74         {
75             if (s == null || stateHash == null)
76             {
77                 throw new IllegalArgumentException JavaDoc("no null args");
78             }
79             LOG.debug("Adding state '"+s.getName()+"' to inner set");
80             
81             this.state = s;
82             
83             // add ourself to the hash BEFORE parsing the transitions.
84 stateHash.put( s, this );
85             
86             // generate the transition table using pre-generated states
87 ITransition t[] = s.getTransitions();
88             if (t == null)
89             {
90                 throw new IllegalStateException JavaDoc("state "+s+
91                     " getTransitions() returned null.");
92             }
93             int len = t.length;
94             this.dest = new InnerTransition[ len ];
95             for (int i = len; --i >= 0;)
96             {
97                 if (t[i] == null)
98                 {
99                     throw new IllegalStateException JavaDoc("Transition "+i+
100                         " for state "+s.getName()+" is null.");
101                 }
102                 IState nextState = t[i].getDestinationState();
103                 if (nextState == null)
104                 {
105                     throw new IllegalStateException JavaDoc("Transition "+i+
106                         " for state "+s.getName()+
107                         " has null destination state.");
108                 }
109                 
110                 InnerState ns = (InnerState)stateHash.get( nextState );
111                 if (ns == null)
112                 {
113                     ns = new InnerState( nextState, stateHash );
114                 }
115                 LOG.debug("Adding transition "+t[i]+" from "+this+" to "+ns);
116                 this.dest[i] = new InnerTransition( t[i], ns, this );
117                 
118                 // we link to that state, so add ourself as a source transition
119 ns.addSourceTransition( this.dest[i] );
120             }
121         }
122         
123         
124         public InnerStatePath createStatePath()
125         {
126             return new InnerStatePath( this );
127         }
128         
129         
130         public InnerTransition[] getDestinations()
131         {
132             return this.dest;
133         }
134         
135         
136         public InnerTransition[] getSources()
137         {
138             InnerTransition[] t = new InnerTransition[ this.sources.size() ];
139             this.sources.copyInto( t );
140             return t;
141         }
142         
143         
144         public IState getState()
145         {
146             return this.state;
147         }
148         
149         
150         private void addSourceTransition( InnerTransition it )
151         {
152             if (it != null && !this.sources.contains( it ))
153             {
154                 this.sources.addElement( it );
155             }
156         }
157         
158         
159         public String JavaDoc toString()
160         {
161             if (getState() != null)
162             {
163                 return getState().toString();
164             }
165             return "[initial state]";
166         }
167     }
168     
169     
170     private static class InnerTransition
171     {
172         private ITransition trans;
173         private InnerState nextState;
174         private InnerState prevState;
175         
176         
177         public InnerTransition( ITransition trans, InnerState next,
178                 InnerState prev )
179         {
180             this.trans = trans;
181             this.nextState = next;
182             this.prevState = prev;
183         }
184         
185         
186         public ITransition getTransition()
187         {
188             return this.trans;
189         }
190         
191         
192         public InnerState getNextState()
193         {
194             return this.nextState;
195         }
196         
197         
198         public InnerState getSourceState()
199         {
200             return this.prevState;
201         }
202         
203         
204         public String JavaDoc toString()
205         {
206             return "["+this.trans+" from "+getSourceState()+" to "+
207                 getNextState()+"]";
208         }
209     }
210     
211     
212     /**
213      * A path-generation state for a state which:
214      * 1. knows how to generate all sub-paths
215      * 2. keeps the current next-transition position
216      */
217     private static class InnerStatePath
218     {
219         private InnerState is;
220         private InnerTransition[] trans;
221         private InnerStatePath[] nextPaths;
222         private int currentIndex;
223         
224         protected InnerStatePath( InnerState is )
225         {
226             this.is = is;
227             
228             // ensure we keep the same ordering of the transitions
229 this.trans = is.getDestinations();
230             if (this.trans == null)
231             {
232                 this.trans = new InnerTransition[0];
233             }
234             
235             reset();
236         }
237         
238         
239         // only used for the very first pseudo-node
240 protected InnerStatePath( InnerState[] states )
241         {
242             this.is = null;
243             int len = states.length;
244             this.trans = new InnerTransition[ len ];
245             for (int i = len; --i >= 0;)
246             {
247                 this.trans[i] = new InnerTransition( null, states[i], null );
248             }
249             
250             reset();
251         }
252         
253         
254         public InnerStatePath getCurrentPath()
255         {
256             if (this.nextPaths.length <= 0)
257             {
258                 return null;
259             }
260             int index = this.currentIndex;
261             // integrity assertion - should never be true
262 if (index >= this.nextPaths.length)
263             {
264                 throw new IllegalStateException JavaDoc(
265                     "Inner index is outside expected range." );
266             }
267             
268             if (this.nextPaths[ index ] == null)
269             {
270                 this.nextPaths[ index ] = getCurrentTransition().
271                     getNextState().createStatePath();
272             }
273             LOG.debug("current path index = "+(index+1)+" / "+
274                 this.nextPaths.length);
275             return this.nextPaths[ index ];
276         }
277         
278         
279         public InnerTransition getCurrentTransition()
280         {
281             if (this.trans.length <= 0)
282             {
283                 return null;
284             }
285             // integrity assertion - should never be true
286 if (this.currentIndex >= this.trans.length)
287             {
288                 throw new IllegalStateException JavaDoc(
289                     "Inner index is outside expected range." );
290             }
291             
292             return this.trans[ this.currentIndex ];
293         }
294         
295         
296         /**
297          * Logic for advancing to the next transition item. If the advance
298          * causes a reset in the loop, then this returns true, otherwise
299          * false.
300          */
301         public boolean advanceTransition()
302         {
303             boolean ret = false;
304             
305             ++this.currentIndex;
306             
307             if (this.currentIndex >= this.trans.length)
308             {
309                 // reset our list to correctly start from 0 again.
310 reset();
311                 
312                 // we flipped over back to the beginning again.
313 ret = true;
314             }
315             if (this.currentIndex < this.trans.length)
316             {
317                 LOG.debug("advanced path to "+getCurrentTransition());
318             }
319             
320             return ret;
321         }
322         
323         
324         /**
325          * This is the core logic for breadth-first searching. The other
326          * piece required is current depth handling.
327          *
328          * @return true if no paths were added or if the current state node
329          * encountered the end of its list (that is, added the last trans
330          * in its list, then reset its list pointer).
331          */
332         public boolean addPath( int remainingDepth, Vector JavaDoc path )
333         {
334             // keep our current index until the child's addPath returns true.
335
336             // test if we're a terminating node
337 if (this.trans.length <= 0)
338             {
339                 return true;
340             }
341             
342             LOG.debug("Entering addPath with state "+this.is);
343             
344             boolean ret = false;
345             InnerTransition it = getCurrentTransition();
346             ITransition trans = it.getTransition();
347             int nextDepth = remainingDepth;
348             
349             // this condition only really covers the very first pseudo-node
350 if (trans != null)
351             {
352                 path.addElement( trans );
353                 --nextDepth;
354             }
355             
356             // if the depth allows it, add another transition to the path
357 if (remainingDepth > 0)
358             {
359                 if (getCurrentPath().addPath( nextDepth, path ))
360                 {
361                     // child said it reached its end, so increment our
362 // index
363 LOG.debug("addPath state "+this.is+
364                         " advancing Transition");
365                     ret = advanceTransition();
366                 }
367             }
368             else
369             {
370                 // for this depth, this node acts as a terminating node.
371 LOG.debug( "no remaining depth to enter" );
372                 ret = true;
373                 
374                 // XXXXXXXXXXXXXXXXXXXXXXXXX
375 // TODO: add in path-to-end node.
376 }
377             
378             LOG.debug("Leaving addPath with state "+this.is+
379                 " and return code "+ret);
380             
381             return ret;
382         }
383         
384         
385         protected void reset()
386         {
387             int len = this.trans.length;
388             
389             // keep the state path list empty - these are
390 // only created on an as-needed basis
391 this.nextPaths = new InnerStatePath[ len ];
392             this.currentIndex = 0;
393         }
394     }
395     
396     
397     // translated all the IState start states into our InnerState format
398 private InnerState startStates[];
399     
400     // this will contain all start states as children, and dummy transitions
401 // to them.
402 private InnerStatePath startNode;
403     
404     // the current max-depth to search
405 private int currentDepth;
406     
407     
408     /**
409      * Capable of generating all paths from the set of all startStates to the
410      * set of all endStates. If there are no endStates, then the generated
411      * paths are not required to end on at least one. If there is at least
412      * one endState, then each path will be guaranteed to terminate with
413      * an endState. If there is no possible path between any startState and
414      * at least one endState, then an error is generated.
415      *
416      * @param startStates list of all possible starting states. This cannot
417      * be empty.
418      * @param endStates list of all possible end states. This may be empty
419      * or <tt>null</tt>.
420      */
421     public BreadthPathGenerator( IState startStates[], IState endStates[] )
422     {
423         // check easy-to-check parts first
424 if (startStates == null)
425         {
426             throw new IllegalArgumentException JavaDoc("no null start states allowed");
427         }
428         if (endStates == null)
429         {
430             endStates = new IState[0];
431         }
432         
433         // Create all reachable InnerState objects in the hashtable.
434 Hashtable JavaDoc knownStates = new Hashtable JavaDoc();
435         int startLen = startStates.length;
436         this.startStates = new InnerState[ startLen ];
437         for (int i = startLen; --i >= 0;)
438         {
439             this.startStates[i] = new InnerState( startStates[i],
440                 knownStates );
441         }
442         
443         // ensure that all end-states are reachable, somehow
444 int endLen = endStates.length;
445         for (int i = endLen; --i >= 0;)
446         {
447             if (!knownStates.contains( endStates[i] ))
448             {
449                 throw new IllegalArgumentException JavaDoc("End state "+
450                     endStates[i].getName()+" is unreachable.");
451             }
452         }
453         
454         // XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
455 // TODO:
456 // create paths in all known states to the endStates, where possible.
457
458     }
459     
460     
461     /**
462      * Return the next path in the generator's sequence.
463      */
464     public IPath getNextPath()
465     {
466         LOG.debug( "enter getNextPath()" );
467         if (this.startNode == null)
468         {
469             reset();
470         }
471
472         // capture the next transition before it is incremented
473 InnerTransition it = this.startNode.getCurrentTransition();
474         if (it == null)
475         {
476             throw new IllegalStateException JavaDoc(
477                 "No known start states." );
478         }
479         InnerState is = it.getNextState();
480         if (is == null)
481         {
482             throw new IllegalStateException JavaDoc(
483                 "Transition destination state is null." );
484         }
485         
486         Vector JavaDoc v = new Vector JavaDoc( this.currentDepth );
487         LOG.debug( "forming path" );
488         if (this.startNode.addPath( this.currentDepth, v ))
489         {
490             // the node reset itself, so we must increment our depth
491 ++this.currentDepth;
492         }
493         
494         ITransition t[] = new ITransition[ v.size() ];
495         v.copyInto( t );
496         LOG.debug( "creating IPath" );
497         IPath p = new PathImpl( is.getState(), t );
498         
499         LOG.debug( "leaving getNextPath()" );
500         return p;
501     }
502     
503     
504     /**
505      * Reset the generator's sequence. There is no guarantee that the
506      * order of returned IPath instances will be identical as the previous
507      * generation sequence.
508      */
509     public void reset()
510     {
511         LOG.debug("Entering reset()");
512         this.startNode = new InnerStatePath( startStates );
513         
514         // there needs to be at least one transition. Just testing the
515 // start states doesn't really do anything.
516 // Perhaps this should be configurable.
517 this.currentDepth = 1;
518         
519         LOG.debug("Leaving reset()");
520     }
521 }
522
523
Popular Tags