001: /*
002: * @(#)BreadthPathGenerator.java
003: *
004: * Copyright (C) 2002-2003 Matt Albrecht
005: * groboclown@users.sourceforge.net
006: * http://groboutils.sourceforge.net
007: *
008: * Part of the GroboUtils package at:
009: * http://groboutils.sourceforge.net
010: *
011: * Permission is hereby granted, free of charge, to any person obtaining a
012: * copy of this software and associated documentation files (the "Software"),
013: * to deal in the Software without restriction, including without limitation
014: * the rights to use, copy, modify, merge, publish, distribute, sublicense,
015: * and/or sell copies of the Software, and to permit persons to whom the
016: * Software is furnished to do so, subject to the following conditions:
017: *
018: * The above copyright notice and this permission notice shall be included in
019: * all copies or substantial portions of the Software.
020: *
021: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
022: * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
023: * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
024: * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
025: * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
026: * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
027: * DEALINGS IN THE SOFTWARE.
028: */
029: package net.sourceforge.groboutils.mbtf.v1.engine;
030:
031: import java.util.Vector;
032: import java.util.Stack;
033: import java.util.Hashtable;
034:
035: import net.sourceforge.groboutils.mbtf.v1.IPath;
036: import net.sourceforge.groboutils.mbtf.v1.IState;
037: import net.sourceforge.groboutils.mbtf.v1.ITransition;
038: import net.sourceforge.groboutils.mbtf.v1.IPathGenerator;
039:
040: import org.apache.log4j.Logger;
041:
042: /**
043: * Implements breadth-first path generation.
044: * <P>
045: * @todo Complete the discover end-state transition paths for states.
046: * @todo Add in depth-related-terminal-node ability to add in end-state
047: * paths. Q: how should it handle multiple end-state paths, in
048: * the case of multiple end-states?
049: *
050: * @author Matt Albrecht <a href="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
051: * @version $Date: 2003/02/10 22:52:26 $
052: * @since June 12, 2002
053: */
054: public class BreadthPathGenerator implements IPathGenerator {
055: private static final Logger LOG = Logger
056: .getLogger(BreadthPathGenerator.class);
057:
058: /**
059: * Parsed form of an IState instance. This is a self-populating list.
060: * It will also populate the constructor hashtable with all enterable
061: * states from this node.
062: */
063: static class InnerState {
064: private IState state;
065: private InnerTransition[] dest;
066: private Vector sources = new Vector();
067: private Vector endStatePaths = new Vector();
068:
069: public InnerState(IState s, Hashtable stateHash) {
070: if (s == null || stateHash == null) {
071: throw new IllegalArgumentException("no null args");
072: }
073: LOG
074: .debug("Adding state '" + s.getName()
075: + "' to inner set");
076:
077: this .state = s;
078:
079: // add ourself to the hash BEFORE parsing the transitions.
080: stateHash.put(s, this );
081:
082: // generate the transition table using pre-generated states
083: ITransition t[] = s.getTransitions();
084: if (t == null) {
085: throw new IllegalStateException("state " + s
086: + " getTransitions() returned null.");
087: }
088: int len = t.length;
089: this .dest = new InnerTransition[len];
090: for (int i = len; --i >= 0;) {
091: if (t[i] == null) {
092: throw new IllegalStateException("Transition " + i
093: + " for state " + s.getName() + " is null.");
094: }
095: IState nextState = t[i].getDestinationState();
096: if (nextState == null) {
097: throw new IllegalStateException("Transition " + i
098: + " for state " + s.getName()
099: + " has null destination state.");
100: }
101:
102: InnerState ns = (InnerState) stateHash.get(nextState);
103: if (ns == null) {
104: ns = new InnerState(nextState, stateHash);
105: }
106: LOG.debug("Adding transition " + t[i] + " from " + this
107: + " to " + ns);
108: this .dest[i] = new InnerTransition(t[i], ns, this );
109:
110: // we link to that state, so add ourself as a source transition
111: ns.addSourceTransition(this .dest[i]);
112: }
113: }
114:
115: public InnerStatePath createStatePath() {
116: return new InnerStatePath(this );
117: }
118:
119: public InnerTransition[] getDestinations() {
120: return this .dest;
121: }
122:
123: public InnerTransition[] getSources() {
124: InnerTransition[] t = new InnerTransition[this .sources
125: .size()];
126: this .sources.copyInto(t);
127: return t;
128: }
129:
130: public IState getState() {
131: return this .state;
132: }
133:
134: private void addSourceTransition(InnerTransition it) {
135: if (it != null && !this .sources.contains(it)) {
136: this .sources.addElement(it);
137: }
138: }
139:
140: public String toString() {
141: if (getState() != null) {
142: return getState().toString();
143: }
144: return "[initial state]";
145: }
146: }
147:
148: private static class InnerTransition {
149: private ITransition trans;
150: private InnerState nextState;
151: private InnerState prevState;
152:
153: public InnerTransition(ITransition trans, InnerState next,
154: InnerState prev) {
155: this .trans = trans;
156: this .nextState = next;
157: this .prevState = prev;
158: }
159:
160: public ITransition getTransition() {
161: return this .trans;
162: }
163:
164: public InnerState getNextState() {
165: return this .nextState;
166: }
167:
168: public InnerState getSourceState() {
169: return this .prevState;
170: }
171:
172: public String toString() {
173: return "[" + this .trans + " from " + getSourceState()
174: + " to " + getNextState() + "]";
175: }
176: }
177:
178: /**
179: * A path-generation state for a state which:
180: * 1. knows how to generate all sub-paths
181: * 2. keeps the current next-transition position
182: */
183: private static class InnerStatePath {
184: private InnerState is;
185: private InnerTransition[] trans;
186: private InnerStatePath[] nextPaths;
187: private int currentIndex;
188:
189: protected InnerStatePath(InnerState is) {
190: this .is = is;
191:
192: // ensure we keep the same ordering of the transitions
193: this .trans = is.getDestinations();
194: if (this .trans == null) {
195: this .trans = new InnerTransition[0];
196: }
197:
198: reset();
199: }
200:
201: // only used for the very first pseudo-node
202: protected InnerStatePath(InnerState[] states) {
203: this .is = null;
204: int len = states.length;
205: this .trans = new InnerTransition[len];
206: for (int i = len; --i >= 0;) {
207: this .trans[i] = new InnerTransition(null, states[i],
208: null);
209: }
210:
211: reset();
212: }
213:
214: public InnerStatePath getCurrentPath() {
215: if (this .nextPaths.length <= 0) {
216: return null;
217: }
218: int index = this .currentIndex;
219: // integrity assertion - should never be true
220: if (index >= this .nextPaths.length) {
221: throw new IllegalStateException(
222: "Inner index is outside expected range.");
223: }
224:
225: if (this .nextPaths[index] == null) {
226: this .nextPaths[index] = getCurrentTransition()
227: .getNextState().createStatePath();
228: }
229: LOG.debug("current path index = " + (index + 1) + " / "
230: + this .nextPaths.length);
231: return this .nextPaths[index];
232: }
233:
234: public InnerTransition getCurrentTransition() {
235: if (this .trans.length <= 0) {
236: return null;
237: }
238: // integrity assertion - should never be true
239: if (this .currentIndex >= this .trans.length) {
240: throw new IllegalStateException(
241: "Inner index is outside expected range.");
242: }
243:
244: return this .trans[this .currentIndex];
245: }
246:
247: /**
248: * Logic for advancing to the next transition item. If the advance
249: * causes a reset in the loop, then this returns true, otherwise
250: * false.
251: */
252: public boolean advanceTransition() {
253: boolean ret = false;
254:
255: ++this .currentIndex;
256:
257: if (this .currentIndex >= this .trans.length) {
258: // reset our list to correctly start from 0 again.
259: reset();
260:
261: // we flipped over back to the beginning again.
262: ret = true;
263: }
264: if (this .currentIndex < this .trans.length) {
265: LOG.debug("advanced path to " + getCurrentTransition());
266: }
267:
268: return ret;
269: }
270:
271: /**
272: * This is the core logic for breadth-first searching. The other
273: * piece required is current depth handling.
274: *
275: * @return true if no paths were added or if the current state node
276: * encountered the end of its list (that is, added the last trans
277: * in its list, then reset its list pointer).
278: */
279: public boolean addPath(int remainingDepth, Vector path) {
280: // keep our current index until the child's addPath returns true.
281:
282: // test if we're a terminating node
283: if (this .trans.length <= 0) {
284: return true;
285: }
286:
287: LOG.debug("Entering addPath with state " + this .is);
288:
289: boolean ret = false;
290: InnerTransition it = getCurrentTransition();
291: ITransition trans = it.getTransition();
292: int nextDepth = remainingDepth;
293:
294: // this condition only really covers the very first pseudo-node
295: if (trans != null) {
296: path.addElement(trans);
297: --nextDepth;
298: }
299:
300: // if the depth allows it, add another transition to the path
301: if (remainingDepth > 0) {
302: if (getCurrentPath().addPath(nextDepth, path)) {
303: // child said it reached its end, so increment our
304: // index
305: LOG.debug("addPath state " + this .is
306: + " advancing Transition");
307: ret = advanceTransition();
308: }
309: } else {
310: // for this depth, this node acts as a terminating node.
311: LOG.debug("no remaining depth to enter");
312: ret = true;
313:
314: // XXXXXXXXXXXXXXXXXXXXXXXXX
315: // TODO: add in path-to-end node.
316: }
317:
318: LOG.debug("Leaving addPath with state " + this .is
319: + " and return code " + ret);
320:
321: return ret;
322: }
323:
324: protected void reset() {
325: int len = this .trans.length;
326:
327: // keep the state path list empty - these are
328: // only created on an as-needed basis
329: this .nextPaths = new InnerStatePath[len];
330: this .currentIndex = 0;
331: }
332: }
333:
334: // translated all the IState start states into our InnerState format
335: private InnerState startStates[];
336:
337: // this will contain all start states as children, and dummy transitions
338: // to them.
339: private InnerStatePath startNode;
340:
341: // the current max-depth to search
342: private int currentDepth;
343:
344: /**
345: * Capable of generating all paths from the set of all startStates to the
346: * set of all endStates. If there are no endStates, then the generated
347: * paths are not required to end on at least one. If there is at least
348: * one endState, then each path will be guaranteed to terminate with
349: * an endState. If there is no possible path between any startState and
350: * at least one endState, then an error is generated.
351: *
352: * @param startStates list of all possible starting states. This cannot
353: * be empty.
354: * @param endStates list of all possible end states. This may be empty
355: * or <tt>null</tt>.
356: */
357: public BreadthPathGenerator(IState startStates[],
358: IState endStates[]) {
359: // check easy-to-check parts first
360: if (startStates == null) {
361: throw new IllegalArgumentException(
362: "no null start states allowed");
363: }
364: if (endStates == null) {
365: endStates = new IState[0];
366: }
367:
368: // Create all reachable InnerState objects in the hashtable.
369: Hashtable knownStates = new Hashtable();
370: int startLen = startStates.length;
371: this .startStates = new InnerState[startLen];
372: for (int i = startLen; --i >= 0;) {
373: this .startStates[i] = new InnerState(startStates[i],
374: knownStates);
375: }
376:
377: // ensure that all end-states are reachable, somehow
378: int endLen = endStates.length;
379: for (int i = endLen; --i >= 0;) {
380: if (!knownStates.contains(endStates[i])) {
381: throw new IllegalArgumentException("End state "
382: + endStates[i].getName() + " is unreachable.");
383: }
384: }
385:
386: // XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
387: // TODO:
388: // create paths in all known states to the endStates, where possible.
389:
390: }
391:
392: /**
393: * Return the next path in the generator's sequence.
394: */
395: public IPath getNextPath() {
396: LOG.debug("enter getNextPath()");
397: if (this .startNode == null) {
398: reset();
399: }
400:
401: // capture the next transition before it is incremented
402: InnerTransition it = this .startNode.getCurrentTransition();
403: if (it == null) {
404: throw new IllegalStateException("No known start states.");
405: }
406: InnerState is = it.getNextState();
407: if (is == null) {
408: throw new IllegalStateException(
409: "Transition destination state is null.");
410: }
411:
412: Vector v = new Vector(this .currentDepth);
413: LOG.debug("forming path");
414: if (this .startNode.addPath(this .currentDepth, v)) {
415: // the node reset itself, so we must increment our depth
416: ++this .currentDepth;
417: }
418:
419: ITransition t[] = new ITransition[v.size()];
420: v.copyInto(t);
421: LOG.debug("creating IPath");
422: IPath p = new PathImpl(is.getState(), t);
423:
424: LOG.debug("leaving getNextPath()");
425: return p;
426: }
427:
428: /**
429: * Reset the generator's sequence. There is no guarantee that the
430: * order of returned IPath instances will be identical as the previous
431: * generation sequence.
432: */
433: public void reset() {
434: LOG.debug("Entering reset()");
435: this .startNode = new InnerStatePath(startStates);
436:
437: // there needs to be at least one transition. Just testing the
438: // start states doesn't really do anything.
439: // Perhaps this should be configurable.
440: this .currentDepth = 1;
441:
442: LOG.debug("Leaving reset()");
443: }
444: }
|