KickJava   Java API By Example, From Geeks To Geeks.

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


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.HashMap JavaDoc;
23 import java.util.LinkedHashSet JavaDoc;
24 import java.util.Map JavaDoc;
25 import java.util.Set JavaDoc;
26
27 import org.sablecc.sablecc.exception.InternalException;
28
29 /**
30  * A partition is the division of states of a <code>Dfa</code> into groups.
31  * The minimisation of a <code>Dfa</code> tries to generate the partition
32  * which contains the less number of groups possible.
33  */
34 class Partition<T extends Comparable JavaDoc<? super T>> {
35
36     /** The <code>Dfa</code> of this partition. */
37     private final Dfa<T> dfa;
38
39     /** The set of groups of this partition. */
40     private final Set JavaDoc<Group<T>> groups = new LinkedHashSet JavaDoc<Group<T>>();
41
42     /** The elements of this partition. */
43     private Set JavaDoc<Element<T>> elements = new LinkedHashSet JavaDoc<Element<T>>();
44
45     /**
46      * A <code>Map</code> that maps each states of this partition's
47      * <code>Dfa</code> to it's corresponding element.
48      */
49     private final Map JavaDoc<DfaState<T>, Element<T>> stateToElementMap = new HashMap JavaDoc<DfaState<T>, Element<T>>();
50
51     /**
52      * Constructs a partition for the provided <code>Dfa<code>.
53      *
54      * @param dfa the <code>Dfa</code>.
55      * @throws InternalException
56      * if the provided <code>Dfa</code> is <code>null</code>.
57      */
58     Partition(
59             Dfa<T> dfa) {
60
61         if (dfa == null) {
62             throw new InternalException("dfa may not be null");
63         }
64
65         this.dfa = dfa;
66
67         // create elements
68 for (DfaState<T> state : dfa.getStates()) {
69             new Element<T>(this, state);
70         }
71
72         // prevent against accidental creation of other elements
73 this.elements = Collections.unmodifiableSet(this.elements);
74
75         // create initial partition
76
77         // non-accept group has at least one element, the dead-end state
78 Group<T> nonAcceptGroup = new Group<T>(this);
79
80         // we don't want empty groups; beware of empty accept group
81 Group<T> acceptGroup = null;
82
83         if (!dfa.getAcceptStates().isEmpty()) {
84             acceptGroup = new Group<T>(this);
85         }
86
87         for (Element<T> element : this.elements) {
88             if (dfa.getAcceptStates().contains(element.getState())) {
89                 element.setGroup(acceptGroup);
90             }
91             else {
92                 element.setGroup(nonAcceptGroup);
93             }
94         }
95
96         // refine partition
97
98         int groupSize;
99
100         do {
101             groupSize = this.groups.size();
102             refine();
103         }
104         while (this.groups.size() != groupSize);
105     }
106
107     /**
108      * Refines this partition by refining all of it's groups.
109      */
110     private void refine() {
111
112         // we get a copy so that modifications to this.groups won't disturb the
113 // iterator
114 for (Group<T> group : new LinkedHashSet JavaDoc<Group<T>>(this.groups)) {
115             group.refine();
116         }
117     }
118
119     /**
120      * Returns the <code>Dfa</code> of this partition.
121      *
122      * @return the <code>Dfa</code>.
123      */
124     Dfa<T> getDfa() {
125
126         return this.dfa;
127     }
128
129     /**
130      * Returns the a set of the groups of this partition.
131      *
132      * @return the set of groups.
133      */
134     Set JavaDoc<Group<T>> getGroups() {
135
136         return Collections.unmodifiableSet(this.groups);
137     }
138
139     /**
140      * Returns the string representation of this partition.
141      *
142      * @return the string representation.
143      */
144     @Override JavaDoc
145     public String JavaDoc toString() {
146
147         StringBuilder JavaDoc sb = new StringBuilder JavaDoc();
148         sb.append("Partition:");
149         sb.append(System.getProperty("line.separator"));
150         for (Group<T> group : this.groups) {
151             sb.append(" ");
152             sb.append(group);
153             sb.append(System.getProperty("line.separator"));
154         }
155
156         return sb.toString();
157     }
158
159     /**
160      * Adds the provided group to this partition.
161      *
162      * @param group
163      * the group to add.
164      * @throws InternalException
165      * if the provided group is <code>null</code>, if it's
166      * partition is not this instance or if it is already in this
167      * partition.
168      */
169     void addGroup(
170             Group<T> group) {
171
172         if (group == null) {
173             throw new InternalException("group may not be null");
174         }
175
176         if (group.getPartition() != this) {
177             throw new InternalException("invalid group");
178         }
179
180         if (!this.groups.add(group)) {
181             throw new InternalException("group is already in this partition");
182         }
183     }
184
185     /**
186      * Returns an element of this partition corresponding to the provided
187      * <code>DfaState</code>.
188      *
189      * @param state
190      * the <code>DfaState</code>.
191      * @return the element.
192      * @throws InternalException
193      * if the provided <code>DfaState</code> is <code>null</code>,
194      * if it's not in this partition's <code>Dfa</code> or if
195      * corruption is detected.
196      */
197     Element<T> getElement(
198             DfaState<T> state) {
199
200         if (state == null) {
201             throw new InternalException("state may not be null");
202         }
203
204         if (state.getDfa() != this.dfa) {
205             throw new InternalException("invalid state");
206         }
207
208         Element<T> element = this.stateToElementMap.get(state);
209
210         if (element == null) {
211             throw new InternalException("corruption detected");
212         }
213
214         return element;
215     }
216
217     /**
218      * Adds the provided element to this partition.
219      *
220      * @param element
221      * the element to add.
222      * @throws InternalException
223      * if the provided element is <code>null</code>, if it's
224      * partition is not this one, if it's <code>Dfa</code> is not
225      * the same as the one of this partition or if this element is
226      * already in this partition.
227      *
228      */
229     void addElement(
230             Element<T> element) {
231
232         if (element == null) {
233             throw new InternalException("element may not be null");
234         }
235
236         if (element.getPartition() != this) {
237             throw new InternalException("invalid element");
238         }
239
240         if (element.getState().getDfa() != this.dfa) {
241             throw new InternalException("invalid element");
242         }
243
244         if (!this.elements.add(element)) {
245             throw new InternalException("element is already in this partition");
246         }
247
248         this.stateToElementMap.put(element.getState(), element);
249     }
250
251 }
252
Popular Tags