001 /*
002 * Copyleft notice: This is public-domain software and documentation
003 * with no restrictions of any kind.
004 * Please feel free to use any of it in any way you want.
005 * This work is distributed in the hope that it will be useful,
006 * but WITHOUT ANY WARRANTY; without even the implied warranty of
007 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
008 */
009
010
011 package time;
012
013 import java.util.*;
014
015 /**
016 * Interval is the implementation of an immutable time interval.
017 *
018 * A time interval represents a period of time between two instants.
019 *
020 * <p>
021 * An <tt>Interval</tt> contains all <tt>Instant</tt> that are greater than the
022 * start instant (inclusive) and lower than the end instant (exclusive), using the
023 * natural order of <tt>Instant</tt> (that is the chronological order). So
024 * the end instant is always greater than or equal to the start instant.
025 *
026 * <p>
027 * As an <tt>Interval</tt> can be seen as a sorted set of instant, it implements the
028 * <tt>java.util.SortedSet<Instant></tt> interface. And as an <tt>Interval</tt> is
029 * immutable, the <tt>SortedSet</tt> is also immutable: every mutative method of
030 * the <tt>SortedSet</tt> interface throws an <tt>UnsupportedOperationException</tt>
031 * as the <tt>Collection</tt> interface allows it.
032 *
033 * <p>
034 * The <tt>Interval</tt> has not been designed to be iterated through <tt>Iterator</tt>,
035 * because it can contain a lot of <tt>Instant</tt> objects.
036 * For example, if an interval has a
037 * duration of one simple day, since the current implementation of <tt>Instant</tt> is
038 * millisecond accurate, it means that it contains 86 400 000 instants. Iterating such
039 * an interval will be likely unappropriate (but possible if really needed). And as
040 * <tt>Instant</tt> may be in the future event more accurate (nanoseconds), <tt>
041 * Interval</tt> may contain event more <tt>Instant</tt>, so you should also not
042 * use the <tt>size()</tt> method.
043 * The <a href=#getDuration()><tt>getDuration()</tt></a> is the appropriate method
044 * to know the duration of an Interval.
045 *
046 *
047 * <p>
048 * Interval have an natural order, which is consistent with <tt>equals</tt>: they are
049 * sorted by their starting intant first. If two intervals have the same starting instant,
050 * they are sorted by their ending instant.
051 * Other <tt>Comparator</tt> are also provided:
052 * <ul>
053 * <li><a href=#COMPARATOR_BY_STARTING_ONLY><tt>COMPARATOR_BY_STARTING_ONLY</tt></a>
054 * <li><a href=#COMPARATOR_BY_ENDING_ONLY><tt>COMPARATOR_BY_ENDING_ONLY</tt></a>
055 * <li><a href=#COMPARATOR_BY_ENDING_THEN_STARTING><tt>COMPARATOR_BY_ENDING_THEN_STARTING</tt></a>
056 * </ul>
057 *
058 * @see Instant
059 *
060 *
061 * @author Arnaud Roques
062 *
063 * @has - has 2 time.Instant
064 * @stereotype "SortedSet"
065 * @stereotype "Comparable"
066 *
067 */
068 public final class Interval /*extends AbstractSet<Instant>*/ implements Comparable<Interval>, SortedSet<Instant>
069 {
070 private final Instant start;
071 private final Instant end;
072
073 /**
074 * Comparator that compares Intervals by their starting instant.
075 * <br>
076 * Please not that this comparator is not consistent with <tt>equals</tt>, since all Intervals
077 * that have the same starting instant are equals according to this comparator,
078 * even if they have different ending instants.
079 */
080 public static final Comparator<Interval> COMPARATOR_BY_STARTING_ONLY = new Comparator<Interval>()
081 {
082 public int compare(Interval i1, Interval i2)
083 {
084 return i1.start.compareTo(i2.start);
085 }
086 };
087
088
089 /**
090 * Comparator that compares Intervals by their ending instant.
091 * <br>
092 * Please not that this comparator is not consistent with <tt>equals</tt>, since all Intervals
093 * that have the same ending instant are equals according to this comparator,
094 * even if they have different starting instants.
095 */
096 public static final Comparator<Interval> COMPARATOR_BY_ENDING_ONLY = new Comparator<Interval>()
097 {
098 public int compare(Interval i1, Interval i2)
099 {
100 return i1.end.compareTo(i2.end);
101 }
102 };
103
104 /**
105 * Comparator that compares Intervals by their starting instant first,
106 * then their ending instant
107 * (natural order of <tt>Interval</tt>).
108 * <br>
109 * This comparator is consistent with <tt>equals</tt>.
110 */
111 public static final Comparator<Interval> COMPARATOR_BY_STARTING_THEN_ENDING = new Comparator<Interval>()
112 {
113 public int compare(Interval i1, Interval i2)
114 {
115 int r1 = COMPARATOR_BY_STARTING_ONLY.compare(i1, i2);
116 if (r1!=0) return r1;
117 int r2 = COMPARATOR_BY_ENDING_ONLY.compare(i1, i2);
118 assert(r2!=0 || i1.equals(i2));
119 return r2;
120
121 }
122 };
123
124 /**
125 * Comparator that compares Intervals by their ending instant first, then their starting instant.
126 * <br>
127 * This comparator is consistent with <tt>equals</tt>.
128 */
129 public static final Comparator<Interval> COMPARATOR_BY_ENDING_THEN_STARTING = new Comparator<Interval>()
130 {
131 public int compare(Interval i1, Interval i2)
132 {
133 int r1 = COMPARATOR_BY_ENDING_ONLY.compare(i1, i2);
134 if (r1!=0) return r1;
135 int r2 = COMPARATOR_BY_STARTING_ONLY.compare(i1, i2);
136 assert(r2!=0 || i1.equals(i2));
137 return r2;
138
139 }
140 };
141
142
143 /**
144 * An interval that contains the whole representation of time.
145 * Its beginning is the BigBang and its ending is the Apocalypse.
146 * So all interval are contained in this one.
147 *
148 * <p>This interval contains all known <tt>Instant</tt> objects except
149 * the Apocalypse, as
150 * the end instant is not included in an interval. (The Apocalypse
151 * cannot belong to any interval).
152 *
153 * <p>It can be used with <tt>headSet()</tt> or <tt>tailSet()</tt>.
154 *
155 * For example:
156 * <pre>
157 * Interval allBefore = WHOLE_TIME.headSet(limit);</pre>Represents
158 * an Interval which contains all Instants strictly before <tt>limit</tt>.
159 *
160 * <p>
161 * And another example:
162 * <pre>
163 * Interval allAfter = WHOLE_TIME.tailSet(limit);</pre>Represents
164 * an Interval which contains all Instants after <tt>limit</tt>, including limit.
165 *
166 * @see Instant#BIG_BANG
167 * @see Instant#APOCALYPSE
168 */
169 public static final Interval WHOLE_TIME = new Interval(Instant.BIG_BANG, Instant.APOCALYPSE);
170
171 /**
172 * Create a new Interval.
173 *
174 * @throws NullPointerException if end or start are <tt>null</tt>
175 * @throws IllegalArgumentException if the ending instant is before the starting instant.
176 *
177 * @param start the starting instant of the new interval
178 * @param end the ending instant of the new interval
179 */
180 public Interval(Instant start, Instant end)
181 {
182 if (end.getMillis()<start.getMillis()) throw new IllegalArgumentException("end before start "+start+" "+end);
183
184 this.start = start;
185 this.end = end;
186 }
187
188
189 /**
190 * Compute the duration in milliseconds of the Interval.
191 * If the duration is bigger than <tt>Long.MAX_VALUE</tt>, return
192 * <tt>Long.MAX_VALUE</tt> (which happens for <tt>WHOLE_TIME</tt> for example).
193 *
194 * @return the duration in milliseconds of the Interval
195 *
196 * @see #WHOLE_TIME
197 */
198 public long getDuration()
199 {
200 long d = end.getMillis() - start.getMillis();
201
202 assert(end.getMillis()>=start.getMillis()) : d;
203 if (d<0) d = Long.MAX_VALUE;
204 return d;
205 }
206
207 /**
208 * Convert the interval in a <tt>String</tt>.
209 *
210 * @return the <tt>String</tt> describing the interval.
211 * @hidden
212 */
213 @Override
214 public String toString()
215 {
216 return super.toString()+"["+start.toString()+"-"+end.toString()+"]";
217 }
218
219
220 /**
221 * Compare two interval for equality.
222 * The result is <tt>true</tt> if and only if the argument is not
223 * <tt>null</tt> and is a <tt>Interval</tt> object that represents
224 * the same Interval, as this object.
225 *
226 * @param obj the object to compare with.
227 * @return <tt>true</tt> if the objects are the same; <tt>false</tt> otherwise.
228 * @hidden
229 */
230 @Override
231 public boolean equals(Object obj)
232 {
233 if (obj==null) return false;
234 if (obj.getClass().equals(getClass())) return false;
235 Interval i2 = (Interval) obj;
236 return start.equals(i2.start) && end.equals(i2.end);
237 }
238
239
240 /**
241 * Returns a hash code value for this object.
242 * @hidden
243 */
244 @Override
245 public int hashCode()
246 {
247 return start.hashCode()+end.hashCode();
248 }
249
250
251 /**
252 * Compare two interval chronogically.
253 *
254 * <p>The order is the same as the one used by COMPARATOR_BY_STARTING_THEN_ENDING.
255 * The interval are sorted by their starting instant first, then by their ending instant.
256 *
257 * @param otherInterval the instant to be compared.
258 *
259 * @return the value 0 if the argument interval is equal to this interval;
260 * a value less than 0 if this interval is before the interval argument;
261 * and a value greater than 0 if this interval is after than the interval argument.
262 *
263 * @throws NullPointerException if <tt>otherInterval</tt> is null.
264 *
265 * @see #COMPARATOR_BY_STARTING_THEN_ENDING
266 */
267 public int compareTo(Interval otherInterval)
268 {
269 return COMPARATOR_BY_STARTING_THEN_ENDING.compare(this, otherInterval);
270 }
271
272 /**
273 * Returns the last (highest) Instant currently in this Interval.
274 * <p>
275 * If the interval is not empty, it differs from 1 milliseconds from the instant
276 * returned by <tt>getEnd()</tt>, as the Instant returned by <tt>last()</tt>
277 * belongs to this interval and the Instant returned by <tt>getEnd()</tt> does
278 * not.
279 *
280 * @throws NoSuchElementException if the interval is empty.
281 * @see #getEnd()
282 * @hidden
283 */
284 public Instant last()
285 {
286 if (getDuration()==0L) throw new NoSuchElementException();
287 return new Instant(end.getMillis()-1);
288 }
289
290 /**
291 * Returns the first (lowest) Instant currently in this Interval.
292 * <p>
293 * If the interval is not empty, it is the same instant as the one
294 * returned by the <tt>getStart()</tt> method.
295 *
296 * @throws NoSuchElementException if the interval is empty.
297 * @see #getStart()
298 * @hidden
299 */
300 public Instant first()
301 {
302 if (getDuration()==0L) throw new NoSuchElementException();
303 return start;
304 }
305
306 /**
307 * Return the number of <tt>Instant</tt> in this Interval.
308 * <p>As <tt>Instant</tt> are millisecond accurate, an <tt>Interval</tt> can
309 * contain a lot of <tt>Instant</tt>.
310 * If the <tt>Interval</tt> is larger than about 24 days, it will contains more
311 * than <tt>Integer.MAX_VALUE</tt> elements, so this method will return
312 * <tt>Integer.MAX_VALUE</tt>, as specified in <tt>Collection</tt> interface.
313 *
314 * <p>Since future implementations of <tt>Instant</tt> may be more accurate than
315 * millisecond, the value returned by this method may be even larger in
316 * the future. Please considere the usage of <tt>getDuration()</tt> instead.
317 *
318 * @return the number of Instants in this interval, or <tt>Integer.MAX_VALUE</tt>.
319 *
320 * @see #getDuration()
321 * @hidden
322 */
323 public int size()
324 {
325 long d = getDuration();
326 if (d>Integer.MAX_VALUE) return Integer.MAX_VALUE;
327 return (int)d;
328 }
329
330 class MyIterator implements Iterator<Instant>
331 {
332 private long current = start.getMillis();
333 public void remove() { throw new UnsupportedOperationException(); }
334
335 public Instant next()
336 {
337 if (current>=end.getMillis()) throw new NoSuchElementException();
338 assert(hasNext());
339 return new Instant(current++);
340 }
341
342 public boolean hasNext()
343 {
344 if (current<end.getMillis()) return true;
345 return false;
346 }
347 }
348
349 /**
350 * Returns an iterator over the instants in this interval.
351 * The instants are returned in chronological order.
352 *
353 * @return an iterator over the instants in this interval.
354 * @hidden
355 */
356 public Iterator<Instant> iterator()
357 {
358 return new MyIterator();
359 }
360
361
362 /**
363 * Return a new interval that contains all instants of this interval greater than
364 * or equals to <tt>fromInstant</tt>.
365 *
366 * @param fromInstant starting instant (inclusive) of the new interval.
367 *
368 * @return new interval that contains all instants of this interval greater than
369 * or equals to <tt>fromInstant</tt>.
370 *
371 * @throws NullPointerException if <tt>fromInstant</tt> is <tt>null</tt>.
372 * @throws IllegalArgumentException if <tt>fromInstant</tt> is not in the interval.
373 * @hidden
374 *
375 */
376 public Interval tailSet(Instant fromInstant)
377 {
378 return new Interval(fromInstant, end);
379 }
380
381
382 /**
383 * Return a new interval that contains all instants of this interval
384 * strictly less than <tt>toInstant</tt>.
385 *
386 * @param toInstant ending instant (exclusive) of the new interval.
387 *
388 * @return new interval that contains all instants of this interval
389 * strictly less than <tt>toInstant</tt>.
390 *
391 * @throws NullPointerException if <tt>toInstant</tt> is <tt>null</tt>.
392 * @throws IllegalArgumentException if <tt>toInstant</tt> is not in the interval.
393 * @hidden
394 *
395 */
396 public Interval headSet(Instant toInstant)
397 {
398 return new Interval(start, toInstant);
399 }
400
401 /**
402 * Return a new interval that contains all instants of this interval
403 * greater than or equals to <tt>fromInstant</tt> and
404 * strictly less than <tt>toInstant</tt>.
405 *
406 * @param fromInstant starting instant (inclusive) of the new interval.
407 * @param toInstant ending instant (exclusive) of the new interval.
408 *
409 * @return a new subinterval of this interval
410 *
411 * @throws NullPointerException if <tt>fromInstant</tt> or <tt>toInstant</tt> are <tt>null</tt>.
412 * @throws IllegalArgumentException if <tt>fromInstant</tt> or <tt>toInstant</tt> are not in the interval.
413 * @throws IllegalArgumentException if <tt>toInstant</tt> is greater than <tt>fromInstant</tt>.
414 * @hidden
415 *
416 */
417 public Interval subSet(Instant fromInstant, Instant toInstant)
418 {
419 return new Interval(fromInstant, toInstant);
420 }
421
422 /**
423 * Returns <tt>null</tt>, as Interval uses the natural order of Instant.
424 * @hidden
425 */
426 public Comparator<? super Instant> comparator()
427 {
428 return null;
429 }
430
431 /**
432 * Return the starting instant of this interval.
433 * This method is almost the same as the <tt>first()</tt> method,
434 * except that even if the interval is empty (which means that the
435 * starting and ending instants are the same), this method will return
436 * the starting instant.
437 *
438 * @see #first()
439 */
440 public Instant getStart()
441 {
442 return start;
443 }
444
445
446 /**
447 * Return the ending instant of this interval.
448 * This method is almost the same as the <tt>last()</tt> method,
449 * with two exception:
450 *
451 * <ul>
452 * <li>if the interval is not empty, the following test :
453 * <pre> getEnding().millisBetween(last())==1L</pre>is always <tt>true</tt>,
454 * <li>if the interval is empty, (which means that the
455 * starting and ending instants are the same), this method will return
456 * the ending instant.
457 * </ul>
458 *
459 * @see #last()
460 */
461 public Instant getEnd()
462 {
463 return end;
464 }
465
466 /**
467 * As <tt>Interval</tt> are immutable, throws a <tt>UnsupportedOperationException</tt>.
468 * @hidden
469 */
470 public void clear()
471 {
472 throw new UnsupportedOperationException();
473 }
474
475 /**
476 * As <tt>Interval</tt> are immutable, throws a <tt>UnsupportedOperationException</tt>.
477 * @hidden
478 */
479 public boolean removeAll(Collection<?> c)
480 {
481 throw new UnsupportedOperationException();
482 }
483
484 /**
485 * As <tt>Interval</tt> are immutable, throws a <tt>UnsupportedOperationException</tt>.
486 * @hidden
487 */
488 public boolean retainAll(Collection<?> c)
489 {
490 throw new UnsupportedOperationException();
491 }
492
493 /**
494 * As <tt>Interval</tt> are immutable, throws a <tt>UnsupportedOperationException</tt>.
495 * @hidden
496 */
497 public boolean addAll(Collection<? extends Instant> c)
498 {
499 throw new UnsupportedOperationException();
500 }
501
502
503 /**
504 * As <tt>Interval</tt> are immutable, throws a <tt>UnsupportedOperationException</tt>.
505 * @hidden
506 */
507 public boolean remove(Object o)
508 {
509 throw new UnsupportedOperationException();
510 }
511
512 /**
513 * As <tt>Interval</tt> are immutable, throws a <tt>UnsupportedOperationException</tt>.
514 * @hidden
515 */
516 public boolean add(Instant o)
517 {
518 throw new UnsupportedOperationException();
519 }
520
521 /**
522 * Returns an array containing all of the instants in this interval.
523 *
524 * <p>As the interval may contain a lot of instants, the returned array
525 * may be very big, so this method should be used
526 * very carefully.
527 *
528 * @return an array containing the instants of this interval.
529 *
530 * @throws OutOfMemoryError if the interval is too big.
531 * @hidden
532 */
533 public <T> T[] toArray(T[] a)
534 {
535 throw new UnsupportedOperationException();
536 }
537
538 /**
539 * Returns an array containing all of the instants in this interval.
540 * Obeys the general contract of the <tt>Collection.toArray</tt> method.
541 *
542 * <p>As the interval may contain a lot of instants, the returned array
543 * may be very big, so this method should be used
544 * very carefully.
545 *
546 * @return an array containing the instants of this interval.
547 *
548 * @throws OutOfMemoryError if the interval is too big.
549 * @hidden
550 */
551 public Object[] toArray()
552 {
553 Object[] result = new Object[size()];
554 int i = 0;
555 for (Instant ins : this)
556 result[i++] = ins;
557 return result;
558 }
559
560 /**
561 * Returns <tt>true</tt> if this set contains all of the elements of the
562 * specified collection.
563 *
564 * <ul>
565 * <li>If the specified collection is an <tt>Interval</tt> object,
566 * this method returns <tt>true</tt>
567 * if it is a subintervall of this interval. The method is in this case executed
568 * in constant time
569 * <li>If the specified collection is a set, this method returns <tt>true</tt>
570 * if it is a subset of this interval.
571 * </ul>
572 *
573 * @param c collection to be checked for containment in this interval.
574 *
575 * @return <tt>true</tt> if this interval contains all of the
576 * elements of the specified collection.
577 *
578 * @throws NullPointerException if <tt>c</tt> is <tt>null</tt>.
579 * @throws NullPointerException if <tt>c</tt> contains one or more null elements.
580 * @throws ClassCastException if <tt>c</tt> contains one or more elements that are
581 * not <tt>Instant</tt>.
582 * @hidden
583 */
584 public boolean containsAll(Collection<?> c)
585 {
586 if (c instanceof Interval)
587 {
588 Interval i = (Interval) c;
589 if (i.start.getMillis()>=start.getMillis() &&
590 i.end.getMillis()<=end.getMillis()) return true;
591 return false;
592 }
593 for (Object o : c)
594 {
595 if (contains(o)==false) return false;
596 }
597 return true;
598 }
599
600
601 /**
602 * Returns true if this set contains the specified Instant.
603 * <ul>
604 * <li>If <tt>obj</tt> is <tt>null</tt>, a <tt>NullPointerException</tt> is thrown.
605 * <li>If <tt>obj</tt> is not an <tt>Instant</tt>, a <tt>ClassCastException</tt> is thrown.
606 * <li>If <tt>obj</tt> is an <tt>Instant</tt> which occurs after the starting instant
607 * of the interval (not
608 * strictly) and before the ending instant (strictly), return <tt>true</tt>. Return
609 * <tt>false</tt> otherwise.
610 * </ul>
611 *
612 * @throws NullPointerException if <tt>obj</tt> is <tt>null</tt>.
613 * @throws ClassCastException if <tt>obj</tt> is not an <tt>Instant</tt>.
614 * @hidden
615 */
616 public boolean contains(Object obj)
617 {
618 if (obj==null) throw new NullPointerException();
619 if (obj instanceof Instant==false) throw new ClassCastException();
620 Instant i = (Instant) obj;
621 if (i.getMillis()<start.getMillis()) return false;
622 if (i.getMillis()>=end.getMillis()) return false;
623 return true;
624 }
625
626 /**
627 * Test if the Interval is empty (has a duration of <tt>0L</tt>).
628 *
629 * @return <tt>true</tt> if the duration is 0L.
630 * @hidden
631 */
632 public boolean isEmpty()
633 {
634 return getDuration()==0L;
635 }
636
637 /**
638 * Return the intersection between this interval and another interval.
639 * More formally, return the larger interval that are contained by both this
640 * interval and the other interval.
641 * <br>
642 * Return <tt>null</tt> if there is no intersection, ie the two intervals
643 * do not intersect at all.
644 * <br>If the ending of an interval is the starting of the other, return
645 * an interval that have a duration of 0.
646 *
647 * @return the intersection or <tt>null</tt> is there is no intersection.
648 *
649 * @throws NullPointerException if <tt>otherInterval</tt> is null.
650 *
651 */
652 public Interval getIntersection(Interval otherInterval)
653 {
654 assert(start.getMillis() <= end.getMillis()) : this;
655 assert(otherInterval.start.getMillis() <= otherInterval.end.getMillis()) : otherInterval;
656
657 // Is our interval after the interval otherInterval?
658 if (start.getMillis() > otherInterval.end.getMillis()) {
659 assert(!contains(otherInterval.getStart()));
660 assert(!contains(otherInterval.getEnd()));
661 assert(!otherInterval.contains(getStart()));
662 assert(!otherInterval.contains(getEnd()));
663 return null; // Yes, -> no intersection
664 }
665
666 // Is our interval before the interval otherInterval?
667 if (end.getMillis() < otherInterval.start.getMillis()) {
668 assert(!contains(otherInterval.getStart()));
669 assert(!contains(otherInterval.getEnd()));
670 assert(!otherInterval.contains(getStart()));
671 assert(!otherInterval.contains(getEnd()));
672 return null; // Yes, -> no intersection
673 }
674
675 // Is our interval in the interval otherInterval?
676 if (otherInterval.containsAll(this)) {
677 return this; // Yes -> we are the intersection
678 }
679
680 // Is the interval otherInterval in our interval?
681 if (this.containsAll(otherInterval)) {
682 return otherInterval; // Yes -> otherInterval is the intersection
683 }
684
685 // Does our interval begin in otherInterval?
686 if (otherInterval.contains(getStart())) {
687 assert(contains(otherInterval.getEnd()));
688 // The intersection starts with us and ends when p2 end
689 return new Interval(getStart(), otherInterval.getEnd());
690 }
691
692 // Does p2 begin in out period;
693 if (contains(otherInterval.getStart())) {
694 assert(otherInterval.contains(getEnd()));
695 // The instersection starts with otherInterval and ends with us
696 return new Interval(otherInterval.getStart(), getEnd());
697 }
698
699 // Should never append
700 assert(false);
701 return null;
702
703 }
704
705 }
706