Interval


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 org.sablecc.sablecc.exception.InternalException;
22  
23  /**
24   * An interval is defined by two bounds (lower and upper). This class provides
25   * various methods to maniplutate intervals.
26   * <p>
27   * Intervals are primarily created using
28   * <code>AdjacencyRealm.createInterval()</code>.
29   */
30  public final class Interval<T extends Comparable  <? super T>>
31          implements Comparable  <Interval<T>> {
32  
33      /** The lower bound. */
34      private final T lowerBound;
35  
36      /** The upper bound. */
37      private final T upperBound;
38  
39      /** The adjacency realm of this interval. */
40      private final AdjacencyRealm<T> adjacencyRealm;
41  
42      /** Cached hashcode. Is <code>null</code> when not yet computed. */
43      private Integer   hashCode;
44  
45      /**
46       * Cached string representation. Is <code>null</code> when not yet
47       * computed.
48       */
49      private String   toString;
50  
51      /**
52       * Constructs an interval with the provided lower and upper bounds within
53       * the provided adjacency realm.
54       * 
55       * @param lowerBound
56       *            the lower bound.
57       * @param upperBound
58       *            the upper bound.
59       * @param adjacencyRealm
60       *            the adjacency realm.
61       * @throws InternalException
62       *             if any bound is <code>null</code>, if the adjacency realm
63       *             is <code>null</code>, or if <code>(lowerBound &gt;
64       *             upperBound)</code>.
65       */
66      Interval(
67              T lowerBound,
68              T upperBound,
69              AdjacencyRealm<T> adjacencyRealm) {
70  
71          if (lowerBound == null) {
72              throw new InternalException("lower bound may not be null");
73          }
74  
75          if (upperBound == null) {
76              throw new InternalException("upper bound may not be null");
77          }
78  
79          if (adjacencyRealm == null) {
80              throw new InternalException("adjacency realm may not be null");
81          }
82  
83          if (lowerBound.compareTo(upperBound) > 0) {
84              throw new InternalException(
85                      "lower bound must be smaller or equal to upper bound");
86          }
87  
88          this.lowerBound = lowerBound;
89          this.upperBound = upperBound;
90          this.adjacencyRealm = adjacencyRealm;
91      }
92  
93      /**
94       * Constructs an interval with a single bound used as both lower and upper
95       * bounds within the provided adjacency realm.
96       * 
97       * @param bound
98       *            the bound. Used as both upper and lower bound.
99       * @param adjacencyRealm
100      *            the adjacency realm.
101      */
102     Interval(
103             T bound,
104             AdjacencyRealm<T> adjacencyRealm) {
105 
106         this(bound, bound, adjacencyRealm);
107     }
108 
109     /**
110      * Returns the lower bound of this interval.
111      * 
112      * @return the lower bound.
113      */
114     public T getLowerBound() {
115 
116         return this.lowerBound;
117     }
118 
119     /**
120      * Returns the upper bound of this interval.
121      * 
122      * @return the upper bound.
123      */
124     public T getUpperBound() {
125 
126         return this.upperBound;
127     }
128 
129     /**
130      * Return the adjacency realm of this interval.
131      * 
132      * @return the adjacency realm.
133      */
134     public AdjacencyRealm<T> getAdjacencyRealm() {
135 
136         return this.adjacencyRealm;
137     }
138 
139     /**
140      * Returns whether this instance is equal to the provided object. They are
141      * equal if they have equal lower and upper bounds and they belong to the
142      * same adjacency realm.
143      * 
144      * @param obj
145      *            the object to compare with.
146      * @return <code>true</code> if this interval and the object are equal;
147      *         <code>false</code> otherwise.
148      */
149     @Override  
150     public boolean equals(
151             Object   obj) {
152 
153         if (this == obj) {
154             return true;
155         }
156 
157         if (obj == null) {
158             return false;
159         }
160 
161         if (getClass() != obj.getClass()) {
162             return false;
163         }
164 
165         Interval interval = (Interval) obj;
166 
167         return this.lowerBound.equals(interval.lowerBound)
168                 && this.upperBound.equals(interval.upperBound)
169                 && this.adjacencyRealm == interval.adjacencyRealm;
170     }
171 
172     /**
173      * Returns the hash code of this interval.
174      * 
175      * @return the hash code.
176      */
177     @Override  
178     public int hashCode() {
179 
180         if (this.hashCode == null) {
181             this.hashCode = this.lowerBound.hashCode() * 121
182                     + this.upperBound.hashCode() * 11
183                     + this.adjacencyRealm.hashCode();
184         }
185 
186         return this.hashCode;
187     }
188 
189     /**
190      * Returns the string representation of this interval.
191      * 
192      * @return the string representation.
193      */
194     @Override  
195     public String   toString() {
196 
197         if (this.toString == null) {
198             this.toString = "[" + this.lowerBound + ".." + this.upperBound
199                     + "]";
200         }
201 
202         return this.toString;
203     }
204 
205     /**
206      * Compares this interval to the provided one. This interval is smaller if
207      * its <code>lowerBound</code> is smaller, or if its
208      * <code>lowerBound</code> is equal and its <code>upperBound</code> is
209      * smaller.
210      * 
211      * @param interval
212      *            the interval to compare with.
213      * @return an <code>int</code> value: <code>0</code> if the two
214      *         intervals are the equals, a negative value if this interval is
215      *         smaller, and a positive value if it is bigger.
216      * @throws InternalException
217      *             if both intervals do not share the same adjacency realms.
218      */
219     public int compareTo(
220             Interval<T> interval) {
221 
222         if (this.adjacencyRealm != interval.adjacencyRealm) {
223             throw new InternalException(
224                     "cannot compare intervals from distinct realms");
225         }
226 
227         int result = this.lowerBound.compareTo(interval.lowerBound);
228 
229         if (result == 0) {
230             result = this.upperBound.compareTo(interval.upperBound);
231         }
232 
233         return result;
234     }
235 
236     /**
237      * Tests whether this interval is adjacent to the provided interval. It is
238      * adjacent if this interval's <code>uppeBound</code> is adjacent to the
239      * <code>lowerBound</code> of the provided interval.
240      * 
241      * @param interval
242      *            the interval to test for adjacency.
243      * @return <code>true</code> if the two intervals are adjacent;
244      *         <code>false</code> otherwise.
245      * @throws InternalException
246      *             if the interval is <code>null</code> or if both intervals
247      *             do not share the same adjacency realms.
248      */
249     public boolean isAdjacentTo(
250             Interval<T> interval) {
251 
252         if (interval == null) {
253             throw new InternalException("interval may not be null");
254         }
255 
256         if (this.adjacencyRealm != interval.adjacencyRealm) {
257             throw new InternalException(
258                     "cannot test adjacency of intervals from distinct realms");
259         }
260 
261         return this.adjacencyRealm.isAdjacent(this.upperBound,
262                 interval.lowerBound);
263     }
264 
265     /**
266      * Tests whether this interval intersects with the provided one. The two
267      * intervals intersect if they share a commun subinterval.
268      * 
269      * @param interval
270      *            the interval to compare with.
271      * @return <code>true</code> if the two intervals intersect;
272      *         <code>false</code> otherwise.
273      * @throws InternalException
274      *             if the interval is <code>null</code> or if both intervals
275      *             do not share the same adjacency realms.
276      */
277     public boolean intersects(
278             Interval<T> interval) {
279 
280         if (interval == null) {
281             throw new InternalException("interval may not be null");
282         }
283 
284         if (this.adjacencyRealm != interval.adjacencyRealm) {
285             throw new InternalException(
286                     "cannot intersect intervals from distinct realms");
287         }
288 
289         return this.lowerBound.compareTo(interval.upperBound) <= 0
290                 && this.upperBound.compareTo(interval.lowerBound) >= 0;
291     }
292 
293     /**
294      * Creates a new interval representing the intersection between this
295      * interval and the provided one. The result is <code>null</code> when
296      * both intervals do not intersect.
297      * 
298      * @param interval
299      *            the interval to intersect with.
300      * @return the intersection of the two intervals; <code>null</code> if the
301      *         intersection is empty.
302      * @throws InternalException
303      *             if the interval is <code>null</code> or if both intervals
304      *             do not share the same adjacency realms.
305      */
306     public Interval<T> intersection(
307             Interval<T> interval) {
308 
309         if (interval == null) {
310             throw new InternalException("interval may not be null");
311         }
312 
313         if (this.adjacencyRealm != interval.adjacencyRealm) {
314             throw new InternalException(
315                     "cannot intersect intervals from distinct realms");
316         }
317 
318         T lowerBound = AdjacencyRealm.max(this.lowerBound, interval.lowerBound);
319 
320         T upperBound = AdjacencyRealm.min(this.upperBound, interval.upperBound);
321 
322         if (lowerBound.compareTo(upperBound) <= 0) {
323             return new Interval<T>(lowerBound, upperBound, this.adjacencyRealm);
324         }
325 
326         return null;
327     }
328 
329     /**
330      * Creates a new interval that spans from this interval's
331      * <code>lowerBound</code> to the provided interval's
332      * <code>upperBound</code>. Merging fails if this interval is not
333      * adjacent to the provided one.
334      * 
335      * @param interval
336      *            the interval to merge this one with.
337      * @return the new interval.
338      * @throws InternalException
339      *             if the interval is <code>null</code> or not adjacent to
340      *             this one, or if both intervals do not share the same
341      *             adjacency realms.
342      */
343     public Interval<T> mergeWith(
344             Interval<T> interval) {
345 
346         if (interval == null) {
347             throw new InternalException("interval may not be null");
348         }
349 
350         if (this.adjacencyRealm != interval.adjacencyRealm) {
351             throw new InternalException(
352                     "cannot merge intervals from distinct realms");
353         }
354 
355         if (!isAdjacentTo(interval)) {
356             throw new InternalException("cannot merge non-adjacent intervals");
357         }
358 
359         return new Interval<T>(this.lowerBound, interval.upperBound,
360                 this.adjacencyRealm);
361     }
362 
363     /**
364      * Returns the minimum of two intervals.
365      * 
366      * @param interval1
367      *            the first interval.
368      * @param interval2
369      *            the second interval.
370      * @return the smallest of the two intervals, or <code>interval1</code> in
371      *         case of equality.
372      * @throws InternalException
373      *             if one of the two intervals is <code>null</code>.
374      */
375     public static <T extends Comparable  <? super T>> Interval<T> min(
376             Interval<T> interval1,
377             Interval<T> interval2) {
378 
379         if (interval1 == null) {
380             throw new InternalException("interval1 may not be null");
381         }
382 
383         if (interval2 == null) {
384             throw new InternalException("interval2 may not be null");
385         }
386 
387         if (interval1.compareTo(interval2) <= 0) {
388             return interval1;
389         }
390 
391         return interval2;
392     }
393 
394     /**
395      * Returns the maximum of two intervals.
396      * 
397      * @param interval1
398      *            the first interval.
399      * @param interval2
400      *            the second interval.
401      * @return the biggest of the two intervals, or <code>interval1</code> in
402      *         case of equality.
403      * @throws InternalException
404      *             if one of the two intervals is <code>null</code>.
405      */
406     public static <T extends Comparable  <? super T>> Interval<T> max(
407             Interval<T> interval1,
408             Interval<T> interval2) {
409 
410         if (interval1 == null) {
411             throw new InternalException("interval1 may not be null");
412         }
413 
414         if (interval2 == null) {
415             throw new InternalException("interval2 may not be null");
416         }
417 
418         if (interval1.compareTo(interval2) >= 0) {
419             return interval1;
420         }
421 
422         return interval2;
423     }
424 }
425
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags