KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > sablecc > sablecc > automaton > Nfa


1 /* This file is part of SableCC ( http://sablecc.org ).
2  *
3  * Copyright 2007 Etienne M. Gagnon <egagnon@j-meg.com>
4  * Copyright 2007 Patrick Pelletier <pp.pelletier@gmail.com>
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */

18
19 package org.sablecc.sablecc.automaton;
20
21 import java.util.Collections JavaDoc;
22 import java.util.Comparator JavaDoc;
23 import java.util.Map JavaDoc;
24 import java.util.SortedMap JavaDoc;
25 import java.util.SortedSet JavaDoc;
26 import java.util.TreeMap JavaDoc;
27 import java.util.TreeSet JavaDoc;
28
29 import org.sablecc.sablecc.alphabet.Alphabet;
30 import org.sablecc.sablecc.alphabet.AlphabetMergeResult;
31 import org.sablecc.sablecc.alphabet.Interval;
32 import org.sablecc.sablecc.alphabet.Symbol;
33 import org.sablecc.sablecc.exception.InternalException;
34
35 /**
36  * A non-deterministic finite automaton (or Nfa) is a state machine which as a
37  * starting state and an accept state. It also have an alphabet of its available
38  * symbols.
39  */

40 public final class Nfa<T extends Comparable JavaDoc<? super T>> {
41
42     /** Only used for line separation in method toString. */
43     private static final String JavaDoc lineSeparator = System
44             .getProperty("line.separator");
45
46     /** The alphabet for this <code>Nfa</code>. */
47     private Alphabet<T> alphabet;
48
49     /** The states of this <code>Nfa</code>. */
50     private SortedSet JavaDoc<NfaState<T>> states;
51
52     /** The starting state of this <code>Nfa</code>. */
53     private NfaState<T> startState;
54
55     /** The acceptation state of this <code>Nfa</code>. */
56     private NfaState<T> acceptState;
57
58     /** A stability status for this <code>Nfa</code>. */
59     private boolean isStable;
60
61     /**
62      * Cached string representation. Is <code>null</code> when not yet
63      * computed.
64      */

65     private String JavaDoc toString;
66
67     /** A comparator for symbols. */
68     private final Comparator JavaDoc<Symbol<T>> symbolComparator = new Comparator JavaDoc<Symbol<T>>() {
69
70         // allows comparison of null symbols
71
public int compare(
72                 Symbol<T> symbol1,
73                 Symbol<T> symbol2) {
74
75             if (symbol1 == null) {
76                 return symbol2 == null ? 0 : -1;
77             }
78
79             if (symbol2 == null) {
80                 return 1;
81             }
82
83             return symbol1.compareTo(symbol2);
84         }
85     };
86
87     /**
88      * Constructs a <code>Nfa</code> for the language <code>{""}</code>,
89      * containing the empty string.
90      */

91     public Nfa() {
92
93         init();
94
95         // empty alphabet
96
this.alphabet = new Alphabet<T>();
97
98         // transition: start->(epsilon)->accept
99
this.startState.addTransition(null, this.acceptState);
100
101         stabilize();
102     }
103
104     /**
105      * Constructs a <code>Nfa</code> for the language <code>{"s"}</code>
106      * where <code>s</code> is a symbol representing a single interval.
107      *
108      * @param interval
109      * the interval.
110      * @throws InternalException
111      * if the interval is <code>null</code>.
112      */

113     public Nfa(
114             Interval<T> interval) {
115
116         if (interval == null) {
117             throw new InternalException("interval may not be null");
118         }
119
120         init();
121
122         Symbol<T> symbol = new Symbol<T>(interval);
123         this.alphabet = new Alphabet<T>(symbol);
124
125         // transition: start->(symbol)->accept
126
this.startState.addTransition(symbol, this.acceptState);
127
128         stabilize();
129     }
130
131     /**
132      * Constructs a <code>Nfa</code> for the language <code>{"s"}</code>
133      * where <code>s</code> is the provided symbol.
134      *
135      * @param symbol
136      * the symbol.
137      * @throws InternalException
138      * if the symbol is <code>null</code>.
139      */

140     public Nfa(
141             Symbol<T> symbol) {
142
143         if (symbol == null) {
144             throw new InternalException("symbol may not be null");
145         }
146
147         init();
148
149         this.alphabet = new Alphabet<T>(symbol);
150
151         // transition: start->(symbol)->accept
152
this.startState.addTransition(symbol, this.acceptState);
153
154         stabilize();
155     }
156
157     /**
158      * Constructs a <code>Nfa</code> which is similar to the provided
159      * <code>Dfa</code>.
160      *
161      * @param dfa
162      * the <code>Dfa</code>.
163      * @throws InternalException
164      * if the <code>Dfa</code> is <code>null</code>.
165      */

166     public Nfa(
167             Dfa<T> dfa) {
168
169         if (dfa == null) {
170             throw new InternalException("dfa may not be null");
171         }
172
173         init();
174
175         this.alphabet = dfa.getAlphabet();
176
177         SortedMap JavaDoc<DfaState<T>, NfaState<T>> dfaToNfaStateMap = new TreeMap JavaDoc<DfaState<T>, NfaState<T>>();
178
179         // Map dfa start to this start.
180
dfaToNfaStateMap.put(dfa.getStartState(), this.startState);
181
182         // Create a state for every dfa state, except start and dead-end.
183
for (DfaState<T> dfaState : dfa.getStates()) {
184
185             if (dfaState == dfa.getDeadEndState()
186                     || dfaState == dfa.getStartState()) {
187                 continue;
188             }
189
190             // add mapping to new state
191
dfaToNfaStateMap.put(dfaState, new NfaState<T>(this));
192         }
193
194         // Create transitions
195
for (Map.Entry JavaDoc<DfaState<T>, NfaState<T>> stateEntry : dfaToNfaStateMap
196                 .entrySet()) {
197             DfaState<T> startDfaState = stateEntry.getKey();
198             NfaState<T> startNfaState = stateEntry.getValue();
199
200             for (Map.Entry JavaDoc<Symbol<T>, DfaState<T>> transitionEntry : startDfaState
201                     .getTransitions().entrySet()) {
202                 Symbol<T> symbol = transitionEntry.getKey();
203                 DfaState<T> destinationDfaState = transitionEntry.getValue();
204                 NfaState<T> destinationNfaState = dfaToNfaStateMap
205                         .get(destinationDfaState);
206
207                 startNfaState.addTransition(symbol, destinationNfaState);
208             }
209         }
210
211         // Add transitions to accept state
212
for (DfaState<T> dfaState : dfa.getAcceptStates()) {
213             NfaState<T> nfaState = dfaToNfaStateMap.get(dfaState);
214
215             nfaState.addTransition(null, this.acceptState);
216         }
217
218         stabilize();
219     }
220
221     /**
222      * Constructs a NFA which is similar to the provided minimal DFA.
223      *
224      * @param minimalDfa
225      * the minimal DFA.
226      * @throws InternalException
227      * if the minimal DFA is <code>null</code>.
228      */

229     public Nfa(
230             MinimalDfa<T> minimalDfa) {
231
232         if (minimalDfa == null) {
233             throw new InternalException("minimalDfa may not be null");
234         }
235
236         init();
237
238         this.alphabet = minimalDfa.getAlphabet();
239
240         SortedMap JavaDoc<MinimalDfaState<T>, NfaState<T>> minimalDfaToNfaStateMap = new TreeMap JavaDoc<MinimalDfaState<T>, NfaState<T>>();
241
242         // Map minimalDfa start to this start.
243
minimalDfaToNfaStateMap
244                 .put(minimalDfa.getStartState(), this.startState);
245
246         // Create a state for every minimalDfa state, except start and dead-end.
247
for (MinimalDfaState<T> minimalDfaState : minimalDfa.getStates()) {
248
249             if (minimalDfaState == minimalDfa.getDeadEndState()
250                     || minimalDfaState == minimalDfa.getStartState()) {
251                 continue;
252             }
253
254             // add mapping to new state
255
minimalDfaToNfaStateMap.put(minimalDfaState, new NfaState<T>(this));
256         }
257
258         // Create transitions
259
for (Map.Entry JavaDoc<MinimalDfaState<T>, NfaState<T>> stateEntry : minimalDfaToNfaStateMap
260                 .entrySet()) {
261             MinimalDfaState<T> startMinimalDfaState = stateEntry.getKey();
262             NfaState<T> startNfaState = stateEntry.getValue();
263
264             for (Map.Entry JavaDoc<Symbol<T>, MinimalDfaState<T>> transitionEntry : startMinimalDfaState
265                     .getTransitions().entrySet()) {
266                 Symbol<T> symbol = transitionEntry.getKey();
267                 MinimalDfaState<T> destinationMinimalDfaState = transitionEntry
268                         .getValue();
269                 NfaState<T> destinationNfaState = minimalDfaToNfaStateMap
270                         .get(destinationMinimalDfaState);
271
272                 startNfaState.addTransition(symbol, destinationNfaState);
273             }
274         }
275
276         // Add transitions to accept state
277
for (MinimalDfaState<T> minimalDfaState : minimalDfa.getAcceptStates()) {
278             NfaState<T> nfaState = minimalDfaToNfaStateMap.get(minimalDfaState);
279
280             nfaState.addTransition(null, this.acceptState);
281         }
282
283         stabilize();
284     }
285
286     /**
287      * Constructs an incomplete <code>Nfa</code>. This private constructor
288      * returns a <code>Nfa</code> to which new states can be added. The
289      * <code>stabilize()</code> method should be called on this instance
290      * before exposing it publicly.
291      *
292      * @param alphabet
293      * the alphabet.
294      */

295     private Nfa(
296             Alphabet<T> alphabet) {
297
298         init();
299
300         this.alphabet = alphabet;
301     }
302
303     /**
304      * Initializes this <code>Nfa</code>. This method must be called by all
305      * constructors.
306      */

307     private void init() {
308
309         this.states = new TreeSet JavaDoc<NfaState<T>>();
310
311         this.startState = new NfaState<T>(this);
312         this.acceptState = new NfaState<T>(this);
313
314         this.isStable = false;
315     }
316
317     /**
318      * Returns the alphabet of this <code>Nfa</code>.
319      *
320      * @return the alphabet.
321      */

322     public Alphabet<T> getAlphabet() {
323
324         return this.alphabet;
325     }
326
327     /**
328      * Returns the states of this <code>Nfa</code>.
329      *
330      * @return the set of states.
331      * @throws InternalException
332      * if this instance is not stable.
333      */

334     public SortedSet JavaDoc<NfaState<T>> getStates() {
335
336         if (!this.isStable) {
337             throw new InternalException("this Nfa is not stable yet");
338         }
339
340         return this.states;
341     }
342
343     /**
344      * Returns the starting state of this <code>Nfa</code>.
345      *
346      * @return the starting state.
347      * @throws InternalException
348      * if this instance is not stable.
349      */

350     public NfaState<T> getStartState() {
351
352         if (!this.isStable) {
353             throw new InternalException("this Nfa is not stable yet");
354         }
355
356         return this.startState;
357     }
358
359     /**
360      * Returns the starting state of this <code>Nfa</code> if it is unstable.
361      *
362      * @return the starting state.
363      */

364     NfaState<T> getUnstableStartState() {
365
366         return this.startState;
367     }
368
369     /**
370      * Returns the acceptation state of this <code>Nfa</code>.
371      *
372      * @return the acceptation state.
373      * @throws InternalException
374      * if this instance is not stable.
375      */

376     public NfaState<T> getAcceptState() {
377
378         if (!this.isStable) {
379             throw new InternalException("this Nfa is not stable yet");
380         }
381
382         return this.acceptState;
383     }
384
385     /**
386      * Returns the symbols comparator for <code>Nfa</code> instances.
387      *
388      * @return the symbol comparator.
389      */

390     Comparator JavaDoc<Symbol<T>> getSymbolComparator() {
391
392         return this.symbolComparator;
393     }
394
395     /**
396      * Returns the string representation of this <code>Nfa</code>.
397      *
398      * @return the string representation.
399      * @throws InternalException
400      * if this instance is not stable.
401      */

402     @Override JavaDoc
403     public String JavaDoc toString() {
404
405         if (this.toString == null) {
406
407             if (!this.isStable) {
408                 throw new InternalException("this Nfa is not stable yet");
409             }
410
411             StringBuilder JavaDoc sb = new StringBuilder JavaDoc();
412
413             sb.append("Nfa:{");
414
415             for (NfaState<T> state : this.states) {
416                 sb.append(lineSeparator);
417                 sb.append(" ");
418                 sb.append(state);
419
420                 if (state == this.startState) {
421                     sb.append("(start)");
422                 }
423
424                 if (state == this.acceptState) {
425                     sb.append("(accept)");
426                 }
427
428                 sb.append(":");
429                 for (Map.Entry JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> entry : state
430                         .getTransitions().entrySet()) {
431                     Symbol<T> symbol = entry.getKey();
432                     SortedSet JavaDoc<NfaState<T>> targets = entry.getValue();
433
434                     for (NfaState<T> target : targets) {
435                         sb.append(lineSeparator);
436                         sb.append(" ");
437                         sb.append(symbol);
438                         sb.append(" -> ");
439                         sb.append(target);
440                     }
441                 }
442             }
443
444             sb.append(lineSeparator);
445             sb.append("}");
446
447             this.toString = sb.toString();
448         }
449
450         return this.toString;
451     }
452
453     /**
454      * Stabilizes this <code>Nfa</code> by stabilizing each of its states.
455      */

456     void stabilize() {
457
458         if (this.isStable) {
459             throw new InternalException("this Nfa is already stable");
460         }
461
462         for (NfaState<T> state : this.states) {
463             state.stabilize();
464         }
465
466         this.states = Collections.unmodifiableSortedSet(this.states);
467
468         this.isStable = true;
469     }
470
471     /**
472      * Returns a new <code>Nfa</code> instance which represents the union of
473      * this <code>Nfa</code> instance with the provided <code>Nfa</code>
474      * instance.
475      *
476      * @param nfa
477      * the nfa.
478      * @return the new <code>Nfa</code> after union.
479      * @throws InternalException
480      * if one of the two <code>Nfa</code> instances is not stable
481      * or if the provided one is <code>null</code>.
482      */

483     public Nfa<T> unionWith(
484             Nfa<T> nfa) {
485
486         if (nfa == null) {
487             throw new InternalException("nfa may not be null");
488         }
489
490         if (!this.isStable) {
491             throw new InternalException("this Nfa is not stable yet");
492         }
493
494         if (!nfa.isStable) {
495             throw new InternalException("nfa is not stable yet");
496         }
497
498         NfaCombineResult<T> nfaCombineResult = this.combineWith(nfa);
499         Nfa<T> newNfa = nfaCombineResult.getNewNfa();
500
501         // add epsilon transitions from start to oldStart
502
newNfa.startState.addTransition(null, nfaCombineResult
503                 .getNewNfa1StartState());
504         newNfa.startState.addTransition(null, nfaCombineResult
505                 .getNewNfa2StartState());
506
507         // add epsilon transitions from oldAccept to accept
508
nfaCombineResult.getNewNfa1AcceptState().addTransition(null,
509                 newNfa.acceptState);
510         nfaCombineResult.getNewNfa2AcceptState().addTransition(null,
511                 newNfa.acceptState);
512
513         newNfa.stabilize();
514         return newNfa;
515     }
516
517     /**
518      * Returns a new <code>Nfa</code> instance which represents the
519      * concatenation of this <code>Nfa</code> instance with the provided
520      * <code>Nfa</code> instance.
521      *
522      * @param nfa
523      * the nfa.
524      * @return the new <code>Nfa</code> after concatenation.
525      * @throws InternalException
526      * if one of the two <code>Nfa</code> instances is not stable
527      * or if the provided one is <code>null</code>.
528      */

529     public Nfa<T> concatenateWith(
530             Nfa<T> nfa) {
531
532         if (nfa == null) {
533             throw new InternalException("nfa may not be null");
534         }
535
536         if (!this.isStable) {
537             throw new InternalException("this Nfa is not stable yet");
538         }
539
540         if (!nfa.isStable) {
541             throw new InternalException("nfa is not stable yet");
542         }
543
544         NfaCombineResult<T> nfaCombineResult = this.combineWith(nfa);
545         Nfa<T> newNfa = nfaCombineResult.getNewNfa();
546
547         // add epsilon transition from start to start(this)
548
newNfa.startState.addTransition(null, nfaCombineResult
549                 .getNewNfa1StartState());
550
551         // add epsilon transition from this accept(this) to start(nfa)
552
nfaCombineResult.getNewNfa1AcceptState().addTransition(null,
553                 nfaCombineResult.getNewNfa2StartState());
554
555         // add epsilon transition from accept(nfa) to accept
556
nfaCombineResult.getNewNfa2AcceptState().addTransition(null,
557                 newNfa.acceptState);
558
559         newNfa.stabilize();
560         return newNfa;
561     }
562
563     /**
564      * Returns a new <code>Nfa</code> instance which represents the repetition
565      * of zero or more of this <code>Nfa</code> instance.
566      *
567      * @return the new <code>Nfa</code>.
568      * @throws InternalException
569      * if this <code>Nfa</code> is not stable.
570      */

571     public Nfa<T> zeroOrMore() {
572
573         if (!this.isStable) {
574             throw new InternalException("this Nfa is not stable yet");
575         }
576
577         Nfa<T> newNfa = new Nfa<T>(this.alphabet);
578
579         // add old states and transitions to new Nfa
580
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
581         this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
582
583         NfaState<T> startThis = oldNfaStateMap.get(this.startState);
584         NfaState<T> acceptThis = oldNfaStateMap.get(this.acceptState);
585
586         // add epsilon transition from start to accept
587
newNfa.startState.addTransition(null, newNfa.acceptState);
588
589         // add epsilon transition from start to start(this)
590
newNfa.startState.addTransition(null, startThis);
591
592         // add epsilon transition from accept(this) to accept
593
acceptThis.addTransition(null, newNfa.acceptState);
594
595         // add epsilon transition from accept(this) to start(this)
596
acceptThis.addTransition(null, startThis);
597
598         newNfa.stabilize();
599         return newNfa;
600     }
601
602     /**
603      * Returns a new <code>Nfa</code> instance which represents the presence
604      * of zero or one of this <code>Nfa</code> instance.
605      *
606      * @return the new <code>Nfa</code>.
607      * @throws InternalException
608      * if this <code>Nfa</code> is not stable.
609      */

610     public Nfa<T> zeroOrOne() {
611
612         if (!this.isStable) {
613             throw new InternalException("this Nfa is not stable yet");
614         }
615
616         Nfa<T> newNfa = new Nfa<T>(this.alphabet);
617
618         // add old states and transitions to new Nfa
619
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
620         this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
621
622         NfaState<T> startThis = oldNfaStateMap.get(this.startState);
623         NfaState<T> acceptThis = oldNfaStateMap.get(this.acceptState);
624
625         // add epsilon transition from start to accept
626
newNfa.startState.addTransition(null, newNfa.acceptState);
627
628         // add epsilon transition from start to start(this)
629
newNfa.startState.addTransition(null, startThis);
630
631         // add epsilon transition from accept(this) to accept
632
acceptThis.addTransition(null, newNfa.acceptState);
633
634         newNfa.stabilize();
635         return newNfa;
636     }
637
638     /**
639      * Returns a new <code>Nfa</code> instance which represents the repetition
640      * of at least one or more of this <code>Nfa</code> instance.
641      *
642      * @return the new <code>Nfa</code>.
643      * @throws InternalException
644      * if this <code>Nfa</code> is not stable.
645      */

646     public Nfa<T> oneOrMore() {
647
648         if (!this.isStable) {
649             throw new InternalException("this Nfa is not stable yet");
650         }
651
652         Nfa<T> newNfa = new Nfa<T>(this.alphabet);
653
654         // add old states and transitions to new Nfa
655
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
656         this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
657
658         NfaState<T> startThis = oldNfaStateMap.get(this.startState);
659         NfaState<T> acceptThis = oldNfaStateMap.get(this.acceptState);
660
661         // add epsilon transition from start to start(this)
662
newNfa.startState.addTransition(null, startThis);
663
664         // add epsilon transition from accept(this) to accept
665
acceptThis.addTransition(null, newNfa.acceptState);
666
667         // add epsilon transition from accept(this) to start(this)
668
acceptThis.addTransition(null, startThis);
669
670         newNfa.stabilize();
671         return newNfa;
672     }
673
674     /**
675      * Returns a new <code>Nfa</code> instance which represents <code>n</code>
676      * repetitions of this <code>Nfa</code> instance.
677      *
678      * @param n
679      * the number of repetitions.
680      * @return the new <code>Nfa</code>.
681      * @throws InternalException
682      * if this <code>Nfa</code> is not stable, or if
683      * <code>n</code> is negative.
684      */

685     public Nfa<T> simpleExponent(
686             int n) {
687
688         if (!this.isStable) {
689             throw new InternalException("this Nfa is not stable yet");
690         }
691
692         if (n < 0) {
693             throw new InternalException("n must be greater or equal to zero");
694         }
695
696         Nfa<T> newNfa = new Nfa<T>(this.alphabet);
697
698         // initialize "last state"
699
NfaState<T> lastState = newNfa.startState;
700
701         for (int i = 0; i < n; i++) {
702
703             // add old states and transitions
704
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
705             this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
706
707             // link from "last state" to newly added "old start"
708
lastState.addTransition(null, oldNfaStateMap.get(this.startState));
709
710             // update "last state"
711
lastState = oldNfaStateMap.get(this.acceptState);
712         }
713
714         // link from "last state" to accept state.
715
lastState.addTransition(null, newNfa.acceptState);
716
717         newNfa.stabilize();
718         return newNfa;
719     }
720
721     /**
722      * Returns a new <code>Nfa</code> instance which represents at least
723      * <code>lowerBound</code> and at most <code>upperBound</code>
724      * repetitions of this <code>Nfa</code> instance.
725      *
726      * @param lowerBound
727      * the minimal number of repetitions.
728      * @param upperBound
729      * the maximal number of repetitions.
730      * @return the new <code>Nfa</code>.
731      * @throws InternalException
732      * if this <code>Nfa</code> is not stable, if any bound is
733      * negative, or if <code>lowerBound</code> is greater than
734      * <code>upperBound</code>.
735      */

736     public Nfa<T> rangeExponent(
737             int lowerBound,
738             int upperBound) {
739
740         if (!this.isStable) {
741             throw new InternalException("this Nfa is not stable yet");
742         }
743
744         if (lowerBound < 0) {
745             throw new InternalException(
746                     "lowerBound must be greater or equal to zero");
747         }
748
749         if (upperBound < 0) {
750             throw new InternalException(
751                     "upperBound must be greater or equal to zero");
752         }
753
754         if (upperBound < lowerBound) {
755             throw new InternalException(
756                     "upperBound must be greater or equal to lowerBound");
757         }
758
759         Nfa<T> newNfa = new Nfa<T>(this.alphabet);
760
761         // initialize "last state"
762
NfaState<T> lastState = newNfa.startState;
763
764         for (int i = 0; i < lowerBound; i++) {
765
766             // add old states and transitions
767
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
768             this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
769
770             // link from "last state" to newly added "old start"
771
lastState.addTransition(null, oldNfaStateMap.get(this.startState));
772
773             // update "last state"
774
lastState = oldNfaStateMap.get(this.acceptState);
775         }
776
777         for (int i = lowerBound; i < upperBound; i++) {
778
779             // link from "last state" to accept state.
780
lastState.addTransition(null, newNfa.acceptState);
781
782             // add old states and transitions
783
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
784             this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
785
786             // link from "last state" to newly added "old start"
787
lastState.addTransition(null, oldNfaStateMap.get(this.startState));
788
789             // update "last state"
790
lastState = oldNfaStateMap.get(this.acceptState);
791         }
792
793         // link from "last state" to accept state.
794
lastState.addTransition(null, newNfa.acceptState);
795
796         newNfa.stabilize();
797         return newNfa;
798     }
799
800     /**
801      * Returns a new <code>Nfa</code> instance which represents at least
802      * <code>n</code> repetitions of this <code>Nfa</code> instance.
803      *
804      * @param n
805      * the minimal number of repetitions.
806      * @return the new <code>Nfa</code>.
807      * @throws InternalException
808      * if this <code>Nfa</code> is not stable, if any bound is
809      * negative, or if <code>lowerBound</code> is greater than
810      * <code>upperBound</code>.
811      */

812     public Nfa<T> atLeastExponent(
813             int n) {
814
815         if (!this.isStable) {
816             throw new InternalException("this Nfa is not stable yet");
817         }
818
819         if (n < 0) {
820             throw new InternalException(
821                     "lowerBound must be greater or equal to zero");
822         }
823
824         Nfa<T> newNfa = new Nfa<T>(this.alphabet);
825
826         // initialize "last state"
827
NfaState<T> lastState = newNfa.startState;
828
829         for (int i = 0; i < n; i++) {
830
831             // add old states and transitions
832
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
833             this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
834
835             // link from "last state" to newly added "old start"
836
lastState.addTransition(null, oldNfaStateMap.get(this.startState));
837
838             // update "last state"
839
lastState = oldNfaStateMap.get(this.acceptState);
840         }
841
842         {
843             // link from "last state" to accept state.
844
lastState.addTransition(null, newNfa.acceptState);
845
846             // add old states and transitions
847
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfaStateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
848             this.addStatesAndTransitionsTo(newNfa, oldNfaStateMap);
849
850             // link from "last state" to newly added "old start"
851
lastState.addTransition(null, oldNfaStateMap.get(this.startState));
852
853             // link from "old accept" to "old start"
854
oldNfaStateMap.get(this.acceptState).addTransition(null,
855                     oldNfaStateMap.get(this.startState));
856
857             // update "last state"
858
lastState = oldNfaStateMap.get(this.acceptState);
859         }
860
861         // link from "last state" to accept state.
862
lastState.addTransition(null, newNfa.acceptState);
863
864         newNfa.stabilize();
865         return newNfa;
866     }
867
868     /**
869      * Returns a <code>Dfa</code> instance which represents the shortest
870      * possible <code>Dfa</code> for this <code>Nfa</code> instance.
871      *
872      * @return the new <code>Dfa</code>.
873      */

874     public Dfa<T> shortest() {
875
876         return Dfa.shortest(this);
877     }
878
879     /**
880      * Returns a <code>Dfa</code> instance which represents the substraction
881      * of this <code>Nfa</code> with the provided one.
882      *
883      * @param nfa
884      * the nfa to substract.
885      * @return the new <code>Dfa</code>.
886      * @throws InternalException
887      * if the provided <code>Nfa</code> is <code>null</code>.
888      */

889     public Dfa<T> subtract(
890             Nfa<T> nfa) {
891
892         if (nfa == null) {
893             throw new InternalException("nfa may not be null");
894         }
895
896         return Dfa.difference(this, nfa);
897     }
898
899     /**
900      * Returns a <code>Dfa</code> instance which represents the intersection
901      * of this <code>Nfa</code> with the provided one.
902      *
903      * @param nfa
904      * the nfa to substract.
905      * @return the new <code>Dfa</code>.
906      * @throws InternalException
907      * if the provided <code>Nfa</code> is <code>null</code>.
908      */

909     public Dfa<T> intersect(
910             Nfa<T> nfa) {
911
912         if (nfa == null) {
913             throw new InternalException("nfa may not be null");
914         }
915
916         return Dfa.intersection(this, nfa);
917     }
918
919     /**
920      * Returns a new <code>NfaCombineResult</code>, the result of the
921      * combination of this <code>Nfa</code> with the provided one.
922      *
923      * @param nfa
924      * the nfa to combine with.
925      * @return the new <code>NfaCombineResult</code>.
926      * @throws InternalException
927      * if one of the two <code>Nfa</code> instances is not stable
928      * or if the provided one is <code>null</code>.
929      */

930     NfaCombineResult<T> combineWith(
931             Nfa<T> nfa) {
932
933         if (nfa == null) {
934             throw new InternalException("nfa may not be null");
935         }
936
937         if (!this.isStable) {
938             throw new InternalException("this Nfa is not stable yet");
939         }
940
941         if (!nfa.isStable) {
942             throw new InternalException("nfa is not stable yet");
943         }
944
945         // Create a new Nfa
946
AlphabetMergeResult<T> alphabetMergeResult = this.alphabet
947                 .mergeWith(nfa.getAlphabet());
948         Nfa<T> newNfa = new Nfa<T>(alphabetMergeResult.getNewAlphabet());
949
950         // add old states and transitions to new Nfa
951
SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfa1StateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
952         this.addStatesAndTransitionsTo(newNfa, oldNfa1StateMap,
953                 alphabetMergeResult);
954
955         SortedMap JavaDoc<NfaState<T>, NfaState<T>> oldNfa2StateMap = new TreeMap JavaDoc<NfaState<T>, NfaState<T>>();
956         nfa.addStatesAndTransitionsTo(newNfa, oldNfa2StateMap,
957                 alphabetMergeResult);
958
959         return new NfaCombineResult<T>(newNfa, this, oldNfa1StateMap, nfa,
960                 oldNfa2StateMap);
961     }
962
963     /**
964      * Adds the states and transitions of this <code>Nfa</code> instance to
965      * the new one provided.
966      *
967      * @param newNfa
968      * the new nfa to add states and transitions.
969      * @param nfaStateMap
970      * a map of states.
971      * @throws InternalException
972      * if the two <code>Nfa</code> instances does not have the
973      * same alphabet.
974      */

975     private void addStatesAndTransitionsTo(
976             Nfa<T> newNfa,
977             SortedMap JavaDoc<NfaState<T>, NfaState<T>> nfaStateMap) {
978
979         if (newNfa.alphabet != this.alphabet) {
980             throw new InternalException(
981                     "this Nfa and newNfa must share the same alphabet");
982         }
983
984         for (NfaState<T> oldState : this.states) {
985
986             NfaState<T> newState = new NfaState<T>(newNfa);
987             nfaStateMap.put(oldState, newState);
988         }
989
990         for (NfaState<T> oldState : this.states) {
991             for (Map.Entry JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> entry : oldState
992                     .getTransitions().entrySet()) {
993
994                 Symbol<T> symbol = entry.getKey();
995                 SortedSet JavaDoc<NfaState<T>> oldTargets = entry.getValue();
996
997                 for (NfaState<T> oldTarget : oldTargets) {
998
999                     nfaStateMap.get(oldState).addTransition(symbol,
1000                            nfaStateMap.get(oldTarget));
1001                }
1002            }
1003        }
1004    }
1005
1006    /**
1007     * Adds the states and transitions of this <code>Nfa</code> instance to
1008     * the new one provided.
1009     *
1010     * @param newNfa
1011     * the new nfa to add states and transitions.
1012     * @param nfaStateMap
1013     * a map of states.
1014     * @param alphabetMergeResult
1015     * the merge result of the alphabets of the two <code>Nfa</code>
1016     * instances.
1017     */

1018    private void addStatesAndTransitionsTo(
1019            Nfa<T> newNfa,
1020            SortedMap JavaDoc<NfaState<T>, NfaState<T>> nfaStateMap,
1021            AlphabetMergeResult<T> alphabetMergeResult) {
1022
1023        for (NfaState<T> oldState : this.states) {
1024
1025            NfaState<T> newState = new NfaState<T>(newNfa);
1026            nfaStateMap.put(oldState, newState);
1027        }
1028
1029        for (NfaState<T> oldState : this.states) {
1030            for (Map.Entry JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> entry : oldState
1031                    .getTransitions().entrySet()) {
1032
1033                Symbol<T> oldSymbol = entry.getKey();
1034                SortedSet JavaDoc<NfaState<T>> oldTargets = entry.getValue();
1035
1036                for (NfaState<T> oldTarget : oldTargets) {
1037
1038                    if (oldSymbol != null) {
1039                        for (Symbol<T> newSymbol : alphabetMergeResult
1040                                .getNewSymbols(oldSymbol, this.alphabet)) {
1041
1042                            nfaStateMap.get(oldState).addTransition(newSymbol,
1043                                    nfaStateMap.get(oldTarget));
1044                        }
1045                    }
1046                    else {
1047                        nfaStateMap.get(oldState).addTransition(null,
1048                                nfaStateMap.get(oldTarget));
1049                    }
1050                }
1051            }
1052        }
1053    }
1054
1055    /**
1056     * Returns the ID for the following state.
1057     *
1058     * @return the ID of the next state.
1059     * @throws InternalException
1060     * if this <code>Nfa</code> instance is stable.
1061     */

1062    int getNextStateId() {
1063
1064        if (this.isStable) {
1065            throw new InternalException("a stable Nfa may not be modified");
1066        }
1067
1068        return this.states.size();
1069    }
1070
1071    /**
1072     * Adds a state to this <code>Nfa</code>.
1073     *
1074     * @param state
1075     * the state to add.
1076     * @throws InternalException
1077     * if this <code>Nfa</code> is stable or or if the state is
1078     * already in the state set.
1079     */

1080    void addState(
1081            NfaState<T> state) {
1082
1083        if (this.isStable) {
1084            throw new InternalException("a stable Nfa may not be modified");
1085        }
1086
1087        if (!this.states.add(state)) {
1088            throw new InternalException("state is already in state set");
1089        }
1090    }
1091
1092}
1093
Popular Tags