Group


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  ;
22  import java.util.LinkedHashMap  ;
23  import java.util.LinkedHashSet  ;
24  import java.util.Map  ;
25  import java.util.Set  ;
26  import java.util.SortedMap  ;
27  import java.util.TreeMap  ;
28  
29  import org.sablecc.sablecc.alphabet.Symbol;
30  import org.sablecc.sablecc.exception.InternalException;
31  
32  /**
33   * A group is a collection of state or element which have the same transitions,
34   * so we can merge them.
35   */
36  class Group<T extends Comparable  <? super T>> {
37  
38      /** The partition related to this group. */
39      private final Partition<T> partition;
40  
41      /** The set of elements in this group. */
42      private final Set  <Element<T>> elements = new LinkedHashSet  <Element<T>>();
43  
44      /** The minimal state of this group. */
45      private MinimalDfaState<T> state;
46  
47      /** The map of transitions of this group. */
48      private final SortedMap  <Symbol<T>, Group<T>> transitions = new TreeMap  <Symbol<T>, Group<T>>();
49  
50      /**
51       * Constructs a new group with a provided partition.
52       * 
53       * @param partition
54       *            the partition.
55       * 
56       * @throws InternalException
57       *             if the partition is <code>null</code>
58       */
59      Group(
60              final Partition<T> partition) {
61  
62          if (partition == null) {
63              throw new InternalException("partition may not be null");
64          }
65  
66          this.partition = partition;
67  
68          this.partition.addGroup(this);
69      }
70  
71      /**
72       * Returns the partition of this group.
73       * 
74       * @return the partition.
75       */
76      Partition<T> getPartition() {
77  
78          return this.partition;
79      }
80  
81      /**
82       * Returns the set of elements of this group.
83       * 
84       * @return the set of elements.
85       */
86      Set  <Element<T>> getElements() {
87  
88          return Collections.unmodifiableSet(this.elements);
89      }
90  
91      /**
92       * Returns the state of this group.
93       * 
94       * @return the state.
95       */
96      MinimalDfaState<T> getState() {
97  
98          return this.state;
99      }
100 
101     /**
102      * Returns the transitions of this group.
103      * 
104      * @return the map of transitions.
105      */
106     SortedMap  <Symbol<T>, Group<T>> getTransitions() {
107 
108         return Collections.unmodifiableSortedMap(this.transitions);
109     }
110 
111     /**
112      * Returns the string representation of this group.
113      * 
114      * @return the string representation.
115      */
116     @Override  
117     public String   toString() {
118 
119         StringBuilder   sb = new StringBuilder  ();
120         sb.append("Group: {");
121         for (Element<T> element : this.elements) {
122             sb.append(element.getState());
123             sb.append(",");
124         }
125         sb.append("}");
126 
127         return sb.toString();
128     }
129 
130     /**
131      * Set the state of this group with the provided state.
132      * 
133      * @param state
134      *            the provided state.
135      */
136     void setState(
137             MinimalDfaState<T> state) {
138 
139         this.state = state;
140     }
141 
142     /**
143      * Adds a new element to this group.
144      * 
145      * @param element
146      *            the provided element.
147      * 
148      * @throws InternalException
149      *             if the element is <code>null</code>, invalid, or already
150      *             added in this group.
151      */
152     void addElement(
153             Element<T> element) {
154 
155         if (element == null) {
156             throw new InternalException("element may not be null");
157         }
158 
159         if (element.getGroup() != this) {
160             throw new InternalException("invalid element");
161         }
162 
163         if (!this.elements.add(element)) {
164             throw new InternalException("element is already in this group");
165         }
166     }
167 
168     /**
169      * Removes an element of this group.
170      * 
171      * @param element
172      *            the element we want to remove.
173      * 
174      * @throws InternalException
175      *             if the element is <code>null</code> of if it not in this
176      *             group.
177      */
178     void removeElement(
179             Element<T> element) {
180 
181         if (element == null) {
182             throw new InternalException("element may not be null");
183         }
184 
185         if (!this.elements.remove(element)) {
186             throw new InternalException("element is not in this group");
187         }
188     }
189 
190     /**
191      * Adds a new transition to this group.
192      * 
193      * @param symbol
194      *            the symbol of the transition.
195      * 
196      * @param group
197      *            the destination group of the transition.
198      * 
199      * @throws InternalException
200      *             if the symbol or the group is <code>null</code>, or if the
201      *             transition is invalid.
202      */
203     void addTransition(
204             Symbol<T> symbol,
205             Group<T> group) {
206 
207         if (symbol == null) {
208             throw new InternalException("symbol may not be null");
209         }
210 
211         if (group == null) {
212             throw new InternalException("group may not be null");
213         }
214 
215         if (this.transitions.containsKey(symbol)
216                 && !this.transitions.get(symbol).equals(group)) {
217             throw new InternalException(
218                     "distinct transitions on a single symbol are not allowed");
219         }
220 
221         this.transitions.put(symbol, group);
222     }
223 
224     /**
225      * Refine this group by making a copy of it.
226      * 
227      * @throws InternalException
228      *             if corruption has been detected in this group.
229      */
230     void refine() {
231 
232         for (Symbol<T> symbol : this.partition.getDfa().getAlphabet()
233                 .getSymbols()) {
234 
235             // for each new target, remember the first source (or
236             // representative) element that targeted to it
237             Map  <Group<T>, Element<T>> targetToRepresentative = new LinkedHashMap  <Group<T>, Element<T>>();
238             Map  <Element<T>, Element<T>> elementToRepresentative = new LinkedHashMap  <Element<T>, Element<T>>();
239 
240             for (Element<T> element : this.elements) {
241                 Group<T> target = element.getTarget(symbol);
242 
243                 Element<T> representative = targetToRepresentative.get(target);
244 
245                 if (representative == null) {
246                     representative = element;
247                     targetToRepresentative.put(target, representative);
248                 }
249 
250                 elementToRepresentative.put(element, representative);
251             }
252 
253             if (targetToRepresentative.isEmpty()) {
254                 throw new InternalException("corruption detected");
255             }
256 
257             // if there were many targets, we must split the group
258             if (targetToRepresentative.size() > 1) {
259 
260                 // create the new groups
261                 boolean first = true;
262                 for (Map.Entry  <Group<T>, Element<T>> entry : targetToRepresentative
263                         .entrySet()) {
264                     if (first) {
265                         // skip
266                         first = false;
267                     }
268                     else {
269                         entry.getValue().setGroup(new Group<T>(this.partition));
270                     }
271                 }
272 
273                 // attach elements to new groups
274 
275                 // we get a copy so that modifications to this.elements won't
276                 // disturb the iterator
277                 for (Element<T> element : new LinkedHashSet  <Element<T>>(
278                         this.elements)) {
279                     // set the group to the represetative's group
280                     element.setGroup(elementToRepresentative.get(element)
281                             .getGroup());
282                 }
283 
284                 break;
285             }
286         }
287     }
288 }
289
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags