KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > sablecc > sablecc > alphabet > Symbol


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.alphabet;
20
21 import java.util.Collection JavaDoc;
22 import java.util.Collections JavaDoc;
23 import java.util.Iterator JavaDoc;
24 import java.util.LinkedList JavaDoc;
25 import java.util.SortedSet JavaDoc;
26 import java.util.TreeSet JavaDoc;
27
28 import org.sablecc.sablecc.exception.InternalException;
29
30 /**
31  * A symbol is a non-empty set of non-overlapped, non-adjacent intervals. This
32  * class provides various methods to maniplutate symbols.
33  */

34 public final class Symbol<T extends Comparable JavaDoc<? super T>>
35         implements Comparable JavaDoc<Symbol<T>> {
36
37     /**
38      * The sorted set of non-overlapping, non-adjacent intervals. Is
39      * <code>null</code> if the symbol is a complement symbol.
40      */

41     private final SortedSet JavaDoc<Interval<T>> intervals;
42
43     /** Cached hashcode. Is <code>null</code> when not yet computed. */
44     private Integer JavaDoc hashCode;
45
46     /**
47      * Cached string representation. Is <code>null</code> when not yet
48      * computed.
49      */

50     private String JavaDoc toString;
51
52     /**
53      * Constructs a symbol with the provided collection of intervals. Adjacent
54      * intervals are merged. Fails if two intervals intersect.
55      *
56      * @param intervals
57      * the collection of intervals.
58      * @throws InternalException
59      * if the collection is <code>null</code>, if the interval is
60      * empty, if an interval within the collection is
61      * <code>null</code>, or if two intervals intersect.
62      */

63     public Symbol(
64             Collection JavaDoc<Interval<T>> intervals) {
65
66         if (intervals == null) {
67             throw new InternalException("intervals may not be null");
68         }
69
70         if (intervals.isEmpty()) {
71             throw new InternalException(
72                     "intervals must contain at least one element");
73         }
74
75         // sort intervals
76
SortedSet JavaDoc<Interval<T>> originalSet = new TreeSet JavaDoc<Interval<T>>(intervals);
77
78         // compute minimal set
79
SortedSet JavaDoc<Interval<T>> minimalSet = new TreeSet JavaDoc<Interval<T>>();
80
81         Interval<T> previous = null;
82         Interval<T> combinedInterval = null;
83         for (Interval<T> current : originalSet) {
84             if (current == null) {
85                 throw new InternalException("null is not a valid interval");
86             }
87
88             if (previous != null && previous.intersects(current)) {
89                 throw new InternalException("intervals may not intersect");
90             }
91
92             if (combinedInterval != null) {
93                 if (combinedInterval.isAdjacentTo(current)) {
94                     combinedInterval = combinedInterval.mergeWith(current);
95                 }
96                 else {
97                     minimalSet.add(combinedInterval);
98                     combinedInterval = current;
99                 }
100             }
101             else {
102                 combinedInterval = current;
103             }
104
105             previous = current;
106         }
107
108         minimalSet.add(combinedInterval);
109
110         this.intervals = Collections.unmodifiableSortedSet(minimalSet);
111     }
112
113     /**
114      * Constructs a symbol with the provided interval.
115      *
116      * @param interval
117      * the interval.
118      * @throws InternalException
119      * if the interval is <code>null</code>.
120      */

121     public Symbol(
122             Interval<T> interval) {
123
124         if (interval == null) {
125             throw new InternalException("interval must be provided");
126         }
127
128         SortedSet JavaDoc<Interval<T>> set = new TreeSet JavaDoc<Interval<T>>();
129         set.add(interval);
130         this.intervals = Collections.unmodifiableSortedSet(set);
131     }
132
133     /**
134      * Constructs a special symbol representing the complement symbol of a
135      * grammar.
136      */

137     public Symbol() {
138
139         this.intervals = null;
140     }
141
142     /**
143      * Returns the set of intervals of this symbol.
144      *
145      * @return the set of intervals.
146      */

147     public SortedSet JavaDoc<Interval<T>> getIntervals() {
148
149         if (this.intervals == null) {
150             throw new InternalException("complement symbols have no intervals");
151         }
152
153         return this.intervals;
154     }
155
156     /**
157      * Returns whether this instance is equal to the provided object. They are
158      * equal if they have an identical set of intervals.
159      *
160      * @param obj
161      * the object to compare with.
162      * @return <code>true</code> if this symbol and the object are equal;
163      * <code>false</code> otherwise.
164      */

165     @Override JavaDoc
166     public boolean equals(
167             Object JavaDoc obj) {
168
169         if (this == obj) {
170             return true;
171         }
172
173         if (obj == null) {
174             return false;
175         }
176
177         if (getClass() != obj.getClass()) {
178             return false;
179         }
180
181         Symbol symbol = (Symbol) obj;
182
183         if (this.intervals == null || symbol.intervals == null) {
184             return this.intervals == symbol.intervals;
185         }
186
187         if (this.intervals.size() != symbol.intervals.size()) {
188             return false;
189         }
190
191         Iterator JavaDoc i = symbol.intervals.iterator();
192         for (Interval<T> interval : this.intervals) {
193             if (!interval.equals(i.next())) {
194                 return false;
195             }
196         }
197
198         return true;
199     }
200
201     /**
202      * Returns the hash code of this symbol.
203      *
204      * @return the hash code.
205      */

206     @Override JavaDoc
207     public int hashCode() {
208
209         if (this.hashCode == null) {
210             int hashCode = 0;
211
212             if (this.intervals != null) {
213                 for (Interval<T> interval : this.intervals) {
214                     hashCode *= 7;
215                     hashCode += interval.hashCode();
216                 }
217             }
218
219             this.hashCode = hashCode;
220         }
221
222         return this.hashCode;
223     }
224
225     /**
226      * Returns the string representation of this symbol.
227      *
228      * @return the string representation.
229      */

230     @Override JavaDoc
231     public String JavaDoc toString() {
232
233         if (this.toString == null) {
234             StringBuilder JavaDoc sb = new StringBuilder JavaDoc();
235
236             sb.append("{");
237
238             if (this.intervals != null) {
239                 boolean first = true;
240                 for (Interval<T> interval : this.intervals) {
241                     if (first) {
242                         first = false;
243                     }
244                     else {
245                         sb.append(",");
246                     }
247
248                     sb.append(interval);
249                 }
250             }
251             else {
252                 sb.append("Complement");
253             }
254
255             sb.append("}");
256
257             this.toString = sb.toString();
258         }
259
260         return this.toString;
261     }
262
263     /**
264      * Compares this symbol to the provided one. The comparison proceeds by
265      * iteratively comparing the intervals of both symbols until a difference is
266      * found. If no difference is found, the size of interval sets is compared.
267      *
268      * @param symbol
269      * the symbol to compare with.
270      * @return an <code>int</code> value: 0 if the two symbols are equals, a
271      * negative value if this symbol is smaller, and a positive value if
272      * it is bigger.
273      */

274     public int compareTo(
275             Symbol<T> symbol) {
276
277         if (this.intervals == null || symbol.intervals == null) {
278
279             if (this.intervals == symbol.intervals) {
280                 return 0;
281             }
282
283             if (this.intervals == null) {
284                 return -1;
285             }
286
287             return 1;
288         }
289
290         int result = 0;
291
292         Iterator JavaDoc<Interval<T>> i1 = this.intervals.iterator();
293         Iterator JavaDoc<Interval<T>> i2 = symbol.intervals.iterator();
294
295         while (result == 0 && i1.hasNext() && i2.hasNext()) {
296             Interval<T> interval1 = i1.next();
297             Interval<T> interval2 = i2.next();
298
299             result = interval1.compareTo(interval2);
300
301             if (result != 0) {
302                 break;
303             }
304         }
305
306         if (result == 0 && (i1.hasNext() || i2.hasNext())) {
307             result = this.intervals.size() - symbol.intervals.size();
308         }
309
310         return result;
311     }
312
313     /**
314      * Returns whether this symbol is a complement symbol or not.
315      *
316      * @return <code>true</code> if this symbol is a complement symbol.
317      */

318     public boolean isComplement() {
319
320         return this.intervals == null;
321     }
322
323     /**
324      * Creates a new symbol by merging together the symbols in the provided
325      * collection. The new symbol includes all the intervals of merged symbols.
326      * Adjacent intervals are merged. Fails if two intervals intersect.
327      * <p>
328      * If one of the symbols is a complement symbol, the result is a complement
329      * symbol.
330      *
331      * @param symbols
332      * a collection of symbols to merge.
333      * @return the new symbol.
334      * @throws InternalException
335      * if the collection is <code>null</code>, if it is empty, or
336      * if it contains more than one complement symbol.
337      */

338     public static <T extends Comparable JavaDoc<? super T>> Symbol<T> merge(
339             Collection JavaDoc<Symbol<T>> symbols) {
340
341         if (symbols == null) {
342             throw new InternalException("symbols may not be null");
343         }
344
345         if (symbols.isEmpty()) {
346             throw new InternalException(
347                     "symbols must contain at least one element");
348         }
349
350         // look for complement symbols
351

352         boolean containsComplementSymbol = false;
353
354         for (Symbol<T> symbol : symbols) {
355             if (symbol.isComplement()) {
356
357                 if (containsComplementSymbol) {
358                     throw new InternalException(
359                             "multiple complement symbols may not be merged.");
360                 }
361
362                 containsComplementSymbol = true;
363             }
364         }
365
366         if (containsComplementSymbol) {
367             return new Symbol<T>();
368         }
369
370         // merge non-complement symbols.
371

372         Collection JavaDoc<Interval<T>> intervals = new LinkedList JavaDoc<Interval<T>>();
373
374         for (Symbol<T> symbol : symbols) {
375             intervals.addAll(symbol.getIntervals());
376         }
377
378         return new Symbol<T>(intervals);
379     }
380
381     /**
382      * Returns the minimum of two symbols.
383      *
384      * @param symbol1
385      * the first symbol.
386      * @param symbol2
387      * the second symbol.
388      * @return the smallest of the two symbols, or <code>symbol1</code> in
389      * case of equality.
390      * @throws InternalException
391      * if one of the two symbols is <code>null</code>.
392      */

393     public static <T extends Comparable JavaDoc<? super T>> Symbol<T> min(
394             Symbol<T> symbol1,
395             Symbol<T> symbol2) {
396
397         if (symbol1 == null) {
398             throw new InternalException("symbol1 may not be null");
399         }
400
401         if (symbol2 == null) {
402             throw new InternalException("symbol2 may not be null");
403         }
404
405         if (symbol1.compareTo(symbol2) <= 0) {
406             return symbol1;
407         }
408
409         return symbol2;
410     }
411
412     /**
413      * Returns the maximum of two symbols.
414      *
415      * @param symbol1
416      * the first symbol.
417      * @param symbol2
418      * the second symbol.
419      * @return the biggest of the two symbols, or <code>symbol1</code> in case
420      * of equality.
421      * @throws InternalException
422      * if one of the two symbols is <code>null</code>.
423      */

424     public static <T extends Comparable JavaDoc<? super T>> Symbol<T> max(
425             Symbol<T> symbol1,
426             Symbol<T> symbol2) {
427
428         if (symbol1 == null) {
429             throw new InternalException("symbol1 may not be null");
430         }
431
432         if (symbol2 == null) {
433             throw new InternalException("symbol2 may not be null");
434         }
435
436         if (symbol1.compareTo(symbol2) >= 0) {
437             return symbol1;
438         }
439
440         return symbol2;
441     }
442 }
443
Popular Tags