001 package org.expasy.jpl.commons.collection;
002
003
004 import java.math.BigDecimal;
005 import java.util.Comparator;
006 import org.expasy.jpl.commons.base.DomainOfDefinition;
007 import org.expasy.jpl.commons.base.ExplicitlyCloneable;
008 import org.expasy.jpl.commons.base.builder.BuilderException;
009 import org.expasy.jpl.commons.base.builder.InstanceBuilder;
010
011
012 /**
013 * An interval is a set of numbers with the property that any number that lies
014 * between two numbers is included in the set.
015 *
016 * An interval is said to be opened ("[]"), closed ("][")or semi-opened ("[[" or
017 * "]]") depending on the possible inclusion of bounds. For example, the set of
018 * all numbers x satisfying 0 ≤ x < 1 is a semi-opened interval [0, 1[ which
019 * contains 0 and not 1, as well as all real numbers between them.
020 *
021 * @author nikitin
022 *
023 * @version 1.0
024 *
025 */
026 public final class Interval implements ExplicitlyCloneable,
027 DomainOfDefinition<Number> {
028
029 private static Interval CACHE = emptyInstance();
030
031 private static final OverlapFinder OVERLAP_FINDER =
032 OverlapFinder.getInstance();
033
034 private static final int DEFAULT_PRECISION = 6;
035 private static final int DEFAULT_ROUNDING_MODE = BigDecimal.ROUND_HALF_UP;
036 private static final BigDecimal DEFAULT_TWO_VALUE = BigDecimal.valueOf(2);
037
038 /** the fractional digit precision */
039 private int precision;
040
041 /** the lower bound */
042 private BigDecimal lower;
043
044 /** the upper bound */
045 private BigDecimal upper;
046
047 /** the center of the interval */
048 private BigDecimal center;
049
050 @SuppressWarnings("unused")
051 private double range;
052
053 /** true if the lower bound is included in interval */
054 private boolean includeLowerBound;
055
056 /** true if the upper bound is included in interval */
057 private boolean includeUpperBound;
058
059 public static class Builder implements InstanceBuilder<Interval> {
060
061 private int precision = DEFAULT_PRECISION;
062 private double upper;
063 private double lower;
064 private boolean isLowerIncluded = true;
065 private boolean isUpperIncluded = false;
066 private boolean cached = false;
067
068 public Builder(final double from, final double to) {
069 this.lower = from;
070 this.upper = to;
071 }
072
073 public Builder cache() {
074 cached = true;
075 return this;
076 }
077
078 public Builder excludeLowerBound() {
079 this.isLowerIncluded = false;
080 return this;
081 }
082
083 public Builder includeUpperBound() {
084 this.isUpperIncluded = true;
085 return this;
086 }
087
088 public Builder precision(int precision) {
089 this.precision = precision;
090 return this;
091 }
092
093 public Interval build() throws BuilderException {
094
095 if (lower > upper) {
096 throw new BuilderException(lower + ">" + upper
097 + ": lower bound cannot be greater than upper bound");
098 }
099
100 if (cached) {
101 CACHE.setInstance(this);
102
103 return CACHE;
104 }
105 return new Interval(this);
106 }
107 }
108
109 private void setInstance(Builder builder) {
110 precision = builder.precision;
111
112 // scale bounds
113 if (!Double.isInfinite(builder.lower)) {
114 lower =
115 new BigDecimal(builder.lower).setScale(precision,
116 DEFAULT_ROUNDING_MODE);
117 includeLowerBound = builder.isLowerIncluded;
118 } else {
119 lower = new BigDecimal(Double.MIN_VALUE);
120 includeLowerBound = false;
121 }
122
123 if (!Double.isInfinite(builder.upper)) {
124 upper =
125 new BigDecimal(builder.upper).setScale(precision,
126 DEFAULT_ROUNDING_MODE);
127 includeUpperBound = builder.isUpperIncluded;
128 } else {
129 upper = new BigDecimal(Double.MAX_VALUE);
130 includeUpperBound = false;
131 }
132
133 // compute center
134 if (Double.isInfinite(builder.lower)
135 && Double.isInfinite(builder.upper)) {
136 center = BigDecimal.ZERO;
137 } else if (Double.isInfinite(builder.lower)) {
138 center = new BigDecimal(Double.MIN_VALUE);
139 } else if (Double.isInfinite(builder.upper)) {
140 center = new BigDecimal(Double.MAX_VALUE);
141 } else {
142 center = lower.add(upper).divide(DEFAULT_TWO_VALUE);
143 }
144 }
145
146 private Interval(Builder builder) {
147 setInstance(builder);
148 }
149
150 /**
151 * Empty interval: ]0, 0[
152 */
153 private Interval() {
154 lower = BigDecimal.ZERO;
155 upper = BigDecimal.ZERO;
156 center = BigDecimal.ZERO;
157 includeLowerBound = false;
158 includeUpperBound = false;
159 // todo: compute range at building time
160 // range = computeRange();
161 }
162
163 public static Interval emptyInstance() {
164 return new Interval();
165 }
166
167 public Interval clone() {
168 Interval clone = null;
169 try {
170 clone = (Interval) super.clone();
171 clone.includeLowerBound = includeLowerBound;
172 clone.includeUpperBound = includeUpperBound;
173
174 // have to normally clone the following Numbers
175 clone.lower = lower;
176 clone.upper = upper;
177 clone.center = center;
178
179 clone.precision = precision;
180 } catch (CloneNotSupportedException e) {
181 throw new IllegalStateException("cannot clone interval");
182 }
183 return clone;
184 }
185
186 /**
187 * Get the lower bound number (included).
188 *
189 * @return the lower bound.
190 */
191 public final double getLowerBound() {
192 return lower.doubleValue();
193 }
194
195 /**
196 * Get the upper bound number (excluded).
197 *
198 * @return the upper bound.
199 */
200 public final double getUpperBound() {
201 return upper.doubleValue();
202 }
203
204 /**
205 * Get the center value.
206 *
207 * @return the center value.
208 */
209 public final double getCenter() {
210 return center.doubleValue();
211 }
212
213 /**
214 * @return true if left open interval
215 */
216 public final boolean isLowerBoundIncluded() {
217 return includeLowerBound;
218 }
219
220 /**
221 * @return true if right open interval
222 */
223 public final boolean isUpperBoundIncluded() {
224 return includeUpperBound;
225 }
226
227 /**
228 * Return true if the given number is found in {@code this} interval.
229 *
230 * @param number the number to test in interval.
231 * @return true if the number is contained in the interval.
232 */
233 public boolean contains(Number number) {
234 boolean ret = false;
235
236 BigDecimal bd = null;
237
238 if (number instanceof BigDecimal) {
239 bd = (BigDecimal) number;
240 } else {
241 bd =
242 new BigDecimal(number.doubleValue()).setScale(precision,
243 DEFAULT_ROUNDING_MODE);
244 }
245
246 int retVsLower = bd.compareTo(lower);
247 int retVsUpper = bd.compareTo(upper);
248
249 if (includeLowerBound) {
250 ret = retVsLower >= 0;
251 } else {
252 ret = retVsLower == 1;
253 }
254
255 if (ret) {
256 if (includeUpperBound) {
257 return retVsUpper <= 0;
258 } else {
259 return retVsUpper == -1;
260 }
261 }
262
263 return ret;
264 }
265
266 /**
267 * Compute the range of the interval.
268 */
269 private final double computeRange() {
270 if (lower.doubleValue() == Double.MIN_VALUE
271 || upper.doubleValue() == Double.MAX_VALUE) {
272 return Double.POSITIVE_INFINITY;
273 }
274 return upper.subtract(lower).doubleValue();
275 }
276
277 /**
278 * @return the range of the interval.
279 */
280 public double getRange() {
281 return computeRange();
282 }
283
284 /**
285 * @return the maximum significant number of fractional digits.
286 */
287 public int getPrecision() {
288 return precision;
289 }
290
291 /**
292 * @return true if empty interval.
293 */
294 public boolean isEmpty() {
295
296 if (upper.compareTo(lower) == -1) {
297 return true;
298 } else if (upper.equals(lower)) {
299
300 // ]i, i[ => empty
301 if (!includeLowerBound && !includeUpperBound) {
302 return true;
303 }
304 // [i, i[, ]i, i] or [i, i] => i included => non empty
305 }
306 return false;
307 }
308
309 public boolean hasOverlap(Interval i) {
310 return OVERLAP_FINDER.hasCommonInterval(this, i);
311 }
312
313 public String toString() {
314 StringBuilder sb = new StringBuilder();
315
316 if (includeLowerBound) {
317 sb.append("[");
318 } else {
319 sb.append("]");
320 }
321 if (lower.doubleValue() == Double.MIN_VALUE) {
322 sb.append(Double.NEGATIVE_INFINITY);
323 } else {
324 sb.append(lower);
325 }
326 sb.append(", ");
327 if (upper.doubleValue() == Double.MAX_VALUE) {
328 sb.append(Double.POSITIVE_INFINITY);
329 } else {
330 sb.append(upper);
331 }
332 if (includeUpperBound) {
333 sb.append("]");
334 } else {
335 sb.append("[");
336 }
337
338 return sb.toString();
339 }
340
341 public static class IntervalComparator implements Comparator<Interval> {
342
343 private static final IntervalComparator INSTANCE =
344 new IntervalComparator(true);
345
346 private static final IntervalComparator NO_OVERLAP_INSTANCE =
347 new IntervalComparator(false);
348
349 private boolean isOverlapAllowed;
350
351 private IntervalComparator(boolean isOverlapAllowed) {
352 this.isOverlapAllowed = isOverlapAllowed;
353 }
354
355 public static IntervalComparator getInstance() {
356 return INSTANCE;
357 }
358
359 public static IntervalComparator noOverlapping() {
360 return NO_OVERLAP_INSTANCE;
361 }
362
363 public int compare(Interval o1, Interval o2) {
364
365 if (!isOverlapAllowed && o1.hasOverlap(o2)) {
366 throw new IntervalOverlapException(
367 "cannot strictly compare intervals " + o1 + " and " + o2);
368 }
369
370 return o1.center.compareTo(o2.center);
371 }
372 }
373
374 public static class OverlapFinder {
375
376 private static final OverlapFinder INSTANCE = new OverlapFinder();
377
378 enum AllenRelation {
379 X_LT_Y(),
380 X_MEETS_Y(),
381 X_OVERLAPS_Y(),
382 X_STARTS_Y(),
383 X_DURING_Y(),
384 X_FINISH_Y(),
385 EQUALS(),
386 Y_LT_X(),
387 Y_MEETS_X(),
388 Y_OVERLAPS_X(),
389 Y_STARTS_X(),
390 Y_DURING_X(),
391 Y_FINISH_X()
392 };
393
394 private OverlapFinder() {}
395
396 public static OverlapFinder getInstance() {
397 return INSTANCE;
398 }
399
400 public boolean hasCommonInterval(Interval i1, Interval i2) {
401 return (during(i1, i2) || during(i2, i1) || starts(i1, i2)
402 || starts(i2, i1) || finishes(i1, i2) || finishes(i2, i1)
403 || overlaps(i1, i2) || overlaps(i2, i1));
404 }
405
406 /**
407 * The < relation
408 */
409 public boolean precedes(Interval i1, Interval i2) {
410 return i1.getUpperBound() < i2.getLowerBound();
411 }
412
413 /**
414 * The > relation
415 */
416 public boolean follows(Interval i1, Interval i2) {
417 return i1.getLowerBound() > i2.getUpperBound();
418 }
419
420 /**
421 * The "m" relation
422 */
423 public boolean meets(Interval i1, Interval i2) {
424 return i1.getUpperBound() == i2.getLowerBound();
425 }
426
427 /**
428 * The "mi" relation
429 */
430 public boolean meetsInverse(Interval i1, Interval i2) {
431 return meets(i2, i1);
432 }
433
434 /**
435 * The "d" relation
436 */
437 public boolean during(Interval i1, Interval i2) {
438 return i1.getLowerBound() > i2.getLowerBound()
439 && i1.getUpperBound() < i2.getUpperBound();
440 }
441
442 /**
443 * The "di" relation
444 */
445 public boolean duringInverse(Interval i1, Interval i2) {
446 return during(i2, i1);
447 }
448
449 /**
450 * The "s" relation
451 */
452 public boolean starts(Interval i1, Interval i2) {
453 return i1.getLowerBound() == i2.getLowerBound()
454 && i1.getUpperBound() < i2.getUpperBound();
455 }
456
457 /**
458 * The "si" relation
459 */
460 public boolean startsInverse(Interval i1, Interval i2) {
461 return starts(i2, i1);
462 }
463
464 /**
465 * The "f" relation
466 */
467 public boolean finishes(Interval i1, Interval i2) {
468 return i1.getLowerBound() > i2.getLowerBound()
469 && i1.getUpperBound() == i2.getUpperBound();
470 }
471
472 /**
473 * The "fi" relation
474 */
475 public boolean finishesInverse(Interval i1, Interval i2) {
476 return finishes(i2, i1);
477 }
478
479 /**
480 * The "o" relation
481 */
482 public boolean overlaps(Interval i1, Interval i2) {
483 return i1.getLowerBound() < i2.getLowerBound()
484 && i2.contains(i1.getUpperBound());
485 }
486
487 /**
488 * The "oi" relation
489 */
490 public boolean overlapsInverse(Interval i1, Interval i2) {
491 return overlaps(i2, i1);
492 }
493
494 }
495
496 public static class IntervalOverlapException extends RuntimeException {
497
498 private static final long serialVersionUID = -1907037439513935537L;
499
500 public IntervalOverlapException() {}
501
502 public IntervalOverlapException(final String message) {
503 super(message);
504 }
505 }
506
507 }