KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* This file is part of SableCC ( http://sablecc.org ).
2  *
3  * Copyright 2007 Etienne M. Gagnon <egagnon@j-meg.com>
4  * Copyright 2007 Raymond Audet <raymond.audet@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.SortedMap JavaDoc;
23 import java.util.TreeMap JavaDoc;
24
25 import org.sablecc.sablecc.alphabet.Symbol;
26 import org.sablecc.sablecc.exception.InternalException;
27
28 /**
29  * A deterministic finite automaton (DFA) is a state machine which permit one
30  * and only one transition from one state to another with an input symbol. A
31  * DfaState is a state for this kind of automaton.
32  */
33 public final class DfaState<T extends Comparable JavaDoc<? super T>>
34         implements Comparable JavaDoc<DfaState<T>> {
35
36     /** The <code>Dfa</code> related to this <code>DfaState</code>. */
37     private final Dfa<T> dfa;
38
39     /** The identification number of this <code>DfaState</code>. */
40     private final int id;
41
42     /** The sorted map of transitions for this <code>DfaState</code>. */
43     private SortedMap JavaDoc<Symbol<T>, DfaState<T>> transitions;
44
45     /** A stability status for this <code>DfaState</code>. */
46     private boolean isStable;
47
48     /**
49      * Cached string representation. Is <code>null</code> when not yet
50      * computed.
51      */
52     private String JavaDoc toString;
53
54     /**
55      * Construct a new <code>DfaState</code> into a provided <code>Dfa</code>.
56      *
57      * @param dfa
58      * the <code>Dfa</code>.
59      * @throws InternalException
60      * if the provided <code>Dfa</code> is <code>null</code>.
61      */
62     DfaState(
63             Dfa<T> dfa) {
64
65         if (dfa == null) {
66             throw new InternalException("dfa may not be null");
67         }
68
69         this.dfa = dfa;
70
71         this.id = dfa.getNextStateId();
72         dfa.addState(this);
73
74         this.transitions = new TreeMap JavaDoc<Symbol<T>, DfaState<T>>();
75
76         this.isStable = false;
77     }
78
79     /**
80      * Returns the <code>Dfa</code> of this <code>DfaState</code>.
81      *
82      * @return the <code>Dfa</code>.
83      */
84     public Dfa<T> getDfa() {
85
86         return this.dfa;
87     }
88
89     /**
90      * Returns the identification number of this <code>DfaState</code>.
91      *
92      * @return the identification number.
93      */
94     public int getId() {
95
96         return this.id;
97     }
98
99     /**
100      * Returns the transitions of this <code>DfaState</code>.
101      *
102      * @return the map of transitions.
103      * @throws InternalException
104      * if this <code>DfaState</code> is not stable.
105      */
106     public SortedMap JavaDoc<Symbol<T>, DfaState<T>> getTransitions() {
107
108         if (!this.isStable) {
109             throw new InternalException("the state is not stable yet");
110         }
111
112         return this.transitions;
113     }
114
115     /**
116      * Returns the unstable transitions of this <code>DfaState</code>.
117      *
118      * @return the map of unstable transitions.
119      */
120     SortedMap JavaDoc<Symbol<T>, DfaState<T>> getUnstableTransitions() {
121
122         return this.transitions;
123     }
124
125     /**
126      * Returns the target of this <code>DfaState</code> with a provided
127      * symbol.
128      *
129      * @param symbol
130      * the provided symbol.
131      *
132      * @return the target.
133      *
134      * @throws InternalException
135      * if this <code>DfaState</code> is not stable, if the
136      * provided symbol is <code>null</code> or if the symbol is
137      * not contained in the alphabet of the <code>Dfa</code>.
138      */
139     public DfaState<T> getTarget(
140             Symbol<T> symbol) {
141
142         if (!this.isStable) {
143             throw new InternalException("the state is not stable yet");
144         }
145
146         if (symbol == null) {
147             throw new InternalException("symbol may not be null");
148         }
149
150         if (!this.dfa.getAlphabet().getSymbols().contains(symbol)) {
151             throw new InternalException("invalid symbol");
152         }
153
154         DfaState<T> target = this.transitions.get(symbol);
155
156         if (target == null) {
157             target = this.dfa.getDeadEndState();
158         }
159
160         return target;
161     }
162
163     /**
164      * Returns whether this instance is equal to the provided object. They are
165      * equal if they have an identical identification number.
166      *
167      * @param obj
168      * the object to compare with.
169      * @return <code>true</code> if this <code>DfaState</code> and the
170      * object are equal; <code>false</code> otherwise.
171      */
172     @Override JavaDoc
173     public boolean equals(
174             Object JavaDoc obj) {
175
176         if (this == obj) {
177             return true;
178         }
179
180         if (obj == null) {
181             return false;
182         }
183
184         if (getClass() != obj.getClass()) {
185             return false;
186         }
187
188         DfaState nfaState = (DfaState) obj;
189
190         return this.id == nfaState.id;
191     }
192
193     /**
194      * Return the hashCode of this <code>DfaState</code>, based on its
195      * identification number.
196      *
197      * @return the hashCode.
198      */
199     @Override JavaDoc
200     public int hashCode() {
201
202         return this.id;
203     }
204
205     /**
206      * Returns the string representation of this <code>DfaState</code>.
207      *
208      * @return the string representation.
209      */
210     @Override JavaDoc
211     public String JavaDoc toString() {
212
213         if (this.toString == null) {
214             this.toString = "dfaState" + this.id;
215         }
216
217         return this.toString;
218     }
219
220     /**
221      * Compares this <code>DfaState</code> to the provided one. It compares
222      * the identification number.
223      *
224      * @param dfaState
225      * the <code>DfaState</code> to compare with.
226      * @return an <code>int</code> value: 0 if the two <code>DfaState</code>
227      * are equals, a negative value if this <code>DfaState</code> is
228      * smaller, and a positive value if it is bigger.
229      */
230     public int compareTo(
231             DfaState<T> dfaState) {
232
233         if (this.dfa != dfaState.dfa) {
234             throw new InternalException(
235                     "cannot compare states from distinct DFAs");
236         }
237
238         return this.id - dfaState.id;
239     }
240
241     /**
242      * Adds a new transition to this <code>DfaState</code>.
243      *
244      * @param symbol
245      * the symbol for the new transition.
246      *
247      * @param dfaState
248      * the destination of the new transition.
249      *
250      * @throws InternalException
251      * if this <code>DfaState</code> is already stable, if the
252      * provided symbol is <code>null</code> or invalid, if the
253      * provided <code>DfaState</code> is <code>null</code> or
254      * invalid, or if the transition already exists.
255      */
256     void addTransition(
257             Symbol<T> symbol,
258             DfaState<T> dfaState) {
259
260         if (this.isStable) {
261             throw new InternalException("a stable state may not be modified");
262         }
263
264         if (symbol == null) {
265             throw new InternalException("symbol may not be null");
266         }
267
268         if (dfaState == null) {
269             throw new InternalException("dfaState may not be null");
270         }
271
272         if (!this.dfa.getAlphabet().getSymbols().contains(symbol)) {
273             throw new InternalException("invalid symbol");
274         }
275
276         if (this.dfa != dfaState.dfa) {
277             throw new InternalException("invalid dfaState");
278         }
279
280         if (dfaState == this.dfa.getUnstableDeadEndState()) {
281             // Don't add transition to dead-end state
282 if (this.transitions.get(symbol) != null) {
283                 throw new InternalException("target was already set");
284             }
285         }
286         else if (this.transitions.put(symbol, dfaState) != null) {
287             throw new InternalException("target was already set");
288         }
289     }
290
291     /**
292      * Removes all the transitions of this <code>DfaState</code>.
293      *
294      * @throws InternalException
295      * if this <code>DfaState</code> is already stable.
296      */
297     void removeTransitions() {
298
299         if (this.isStable) {
300             throw new InternalException("a stable state may not be modified");
301         }
302
303         this.transitions.clear();
304     }
305
306     /**
307      * Stabilize this <code>DfaState</code>.
308      *
309      * @throws InternalException
310      * if this <code>DfaState</code> is already stable.
311      */
312     void stabilize() {
313
314         if (this.isStable) {
315             throw new InternalException("state is already stable");
316         }
317
318         this.transitions = Collections.unmodifiableSortedMap(this.transitions);
319
320         this.isStable = true;
321     }
322 }
323
Popular Tags