001/* ===========================================================
002 * JFreeChart : a free chart library for the Java(tm) platform
003 * ===========================================================
004 *
005 * (C) Copyright 2000-2013, by Object Refinery Limited and Contributors.
006 *
007 * Project Info:  http://www.jfree.org/jfreechart/index.html
008 *
009 * This library is free software; you can redistribute it and/or modify it
010 * under the terms of the GNU Lesser General Public License as published by
011 * the Free Software Foundation; either version 2.1 of the License, or
012 * (at your option) any later version.
013 *
014 * This library is distributed in the hope that it will be useful, but
015 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
016 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
017 * License for more details.
018 *
019 * You should have received a copy of the GNU Lesser General Public
020 * License along with this library; if not, write to the Free Software
021 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
022 * USA.
023 *
024 * [Oracle and Java are registered trademarks of Oracle and/or its affiliates. 
025 * Other names may be trademarks of their respective owners.]
026 *
027 * -----------------------
028 * SegmentedTimeline.java
029 * -----------------------
030 * (C) Copyright 2003-2008, by Bill Kelemen and Contributors.
031 *
032 * Original Author:  Bill Kelemen;
033 * Contributor(s):   David Gilbert (for Object Refinery Limited);
034 *
035 * Changes
036 * -------
037 * 23-May-2003 : Version 1 (BK);
038 * 15-Aug-2003 : Implemented Cloneable (DG);
039 * 01-Jun-2004 : Modified to compile with JDK 1.2.2 (DG);
040 * 30-Sep-2004 : Replaced getTime().getTime() with getTimeInMillis() (DG);
041 * 04-Nov-2004 : Reverted change of 30-Sep-2004, won't work with JDK 1.3 (DG);
042 * 11-Jan-2005 : Removed deprecated code in preparation for 1.0.0 release (DG);
043 * ------------- JFREECHART 1.0.x ---------------------------------------------
044 * 14-Nov-2006 : Fix in toTimelineValue(long) to avoid stack overflow (DG);
045 * 02-Feb-2007 : Removed author tags all over JFreeChart sources (DG);
046 * 11-Jul-2007 : Fixed time zone bugs (DG);
047 * 06-Jun-2008 : Performance enhancement posted in forum (DG);
048 *
049 */
050
051package org.jfree.chart.axis;
052
053import java.io.Serializable;
054import java.util.ArrayList;
055import java.util.Calendar;
056import java.util.Collections;
057import java.util.Date;
058import java.util.GregorianCalendar;
059import java.util.Iterator;
060import java.util.List;
061import java.util.Locale;
062import java.util.SimpleTimeZone;
063import java.util.TimeZone;
064
065/**
066 * A {@link Timeline} that implements a "segmented" timeline with included,
067 * excluded and exception segments.
068 * <P>
069 * A Timeline will present a series of values to be used for an axis. Each
070 * Timeline must provide transformation methods between domain values and
071 * timeline values.
072 * <P>
073 * A timeline can be used as parameter to a
074 * {@link org.jfree.chart.axis.DateAxis} to define the values that this axis
075 * supports. This class implements a timeline formed by segments of equal
076 * length (ex. days, hours, minutes) where some segments can be included in the
077 * timeline and others excluded. Therefore timelines like "working days" or
078 * "working hours" can be created where non-working days or non-working hours
079 * respectively can be removed from the timeline, and therefore from the axis.
080 * This creates a smooth plot with equal separation between all included
081 * segments.
082 * <P>
083 * Because Timelines were created mainly for Date related axis, values are
084 * represented as longs instead of doubles. In this case, the domain value is
085 * just the number of milliseconds since January 1, 1970, 00:00:00 GMT as
086 * defined by the getTime() method of {@link java.util.Date}.
087 * <P>
088 * In this class, a segment is defined as a unit of time of fixed length.
089 * Examples of segments are: days, hours, minutes, etc. The size of a segment
090 * is defined as the number of milliseconds in the segment. Some useful segment
091 * sizes are defined as constants in this class: DAY_SEGMENT_SIZE,
092 * HOUR_SEGMENT_SIZE, FIFTEEN_MINUTE_SEGMENT_SIZE and MINUTE_SEGMENT_SIZE.
093 * <P>
094 * Segments are group together to form a Segment Group. Each Segment Group will
095 * contain a number of Segments included and a number of Segments excluded. This
096 * Segment Group structure will repeat for the whole timeline.
097 * <P>
098 * For example, a working days SegmentedTimeline would be formed by a group of
099 * 7 daily segments, where there are 5 included (Monday through Friday) and 2
100 * excluded (Saturday and Sunday) segments.
101 * <P>
102 * Following is a diagram that explains the major attributes that define a
103 * segment.  Each box is one segment and must be of fixed length (ms, second,
104 * hour, day, etc).
105 * <p>
106 * <pre>
107 * start time
108 *   |
109 *   v
110 *   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...
111 * +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+...
112 * |  |  |  |  |  |EE|EE|  |  |  |  |  |EE|EE|  |  |  |  |  |EE|EE|
113 * +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+...
114 *  \____________/ \___/            \_/
115 *        \/         |               |
116 *     included   excluded        segment
117 *     segments   segments         size
118 *  \_________  _______/
119 *            \/
120 *       segment group
121 * </pre>
122 * Legend:<br>
123 * &lt;space&gt; = Included segment<br>
124 * EE      = Excluded segments in the base timeline<br>
125 * <p>
126 * In the example, the following segment attributes are presented:
127 * <ul>
128 * <li>segment size: the size of each segment in ms.
129 * <li>start time: the start of the first segment of the first segment group to
130 *     consider.
131 * <li>included segments: the number of segments to include in the group.
132 * <li>excluded segments: the number of segments to exclude in the group.
133 * </ul>
134 * <p>
135 * Exception Segments are allowed. These exception segments are defined as
136 * segments that would have been in the included segments of the Segment Group,
137 * but should be excluded for special reasons. In the previous working days
138 * SegmentedTimeline example, holidays would be considered exceptions.
139 * <P>
140 * Additionally the <code>startTime</code>, or start of the first Segment of
141 * the smallest segment group needs to be defined. This startTime could be
142 * relative to January 1, 1970, 00:00:00 GMT or any other date. This creates a
143 * point of reference to start counting Segment Groups. For example, for the
144 * working days SegmentedTimeline, the <code>startTime</code> could be
145 * 00:00:00 GMT of the first Monday after January 1, 1970. In this class, the
146 * constant FIRST_MONDAY_AFTER_1900 refers to a reference point of the first
147 * Monday of the last century.
148 * <p>
149 * A SegmentedTimeline can include a baseTimeline. This combination of
150 * timelines allows the creation of more complex timelines. For example, in
151 * order to implement a SegmentedTimeline for an intraday stock trading
152 * application, where the trading period is defined as 9:00 AM through 4:00 PM
153 * Monday through Friday, two SegmentedTimelines are used. The first one (the
154 * baseTimeline) would be a working day SegmentedTimeline (daily timeline
155 * Monday through Friday). On top of this baseTimeline, a second one is defined
156 * that maps the 9:00 AM to 4:00 PM period. Because the baseTimeline defines a
157 * timeline of Monday through Friday, the resulting (combined) timeline will
158 * expose the period 9:00 AM through 4:00 PM only on Monday through Friday,
159 * and will remove all other intermediate intervals.
160 * <P>
161 * Two factory methods newMondayThroughFridayTimeline() and
162 * newFifteenMinuteTimeline() are provided as examples to create special
163 * SegmentedTimelines.
164 *
165 * @see org.jfree.chart.axis.DateAxis
166 */
167public class SegmentedTimeline implements Timeline, Cloneable, Serializable {
168
169    /** For serialization. */
170    private static final long serialVersionUID = 1093779862539903110L;
171
172    ////////////////////////////////////////////////////////////////////////////
173    // predetermined segments sizes
174    ////////////////////////////////////////////////////////////////////////////
175
176    /** Defines a day segment size in ms. */
177    public static final long DAY_SEGMENT_SIZE = 24 * 60 * 60 * 1000;
178
179    /** Defines a one hour segment size in ms. */
180    public static final long HOUR_SEGMENT_SIZE = 60 * 60 * 1000;
181
182    /** Defines a 15-minute segment size in ms. */
183    public static final long FIFTEEN_MINUTE_SEGMENT_SIZE = 15 * 60 * 1000;
184
185    /** Defines a one-minute segment size in ms. */
186    public static final long MINUTE_SEGMENT_SIZE = 60 * 1000;
187
188    ////////////////////////////////////////////////////////////////////////////
189    // other constants
190    ////////////////////////////////////////////////////////////////////////////
191
192    /**
193     * Utility constant that defines the startTime as the first monday after
194     * 1/1/1970.  This should be used when creating a SegmentedTimeline for
195     * Monday through Friday. See static block below for calculation of this
196     * constant.
197     *
198     * @deprecated As of 1.0.7.  This field doesn't take into account changes
199     *         to the default time zone.
200     */
201    public static long FIRST_MONDAY_AFTER_1900;
202
203    /**
204     * Utility TimeZone object that has no DST and an offset equal to the
205     * default TimeZone. This allows easy arithmetic between days as each one
206     * will have equal size.
207     *
208     * @deprecated As of 1.0.7.  This field is initialised based on the
209     *         default time zone, and doesn't take into account subsequent
210     *         changes to the default.
211     */
212    public static TimeZone NO_DST_TIME_ZONE;
213
214    /**
215     * This is the default time zone where the application is running. See
216     * getTime() below where we make use of certain transformations between
217     * times in the default time zone and the no-dst time zone used for our
218     * calculations.
219     *
220     * @deprecated As of 1.0.7.  When the default time zone is required,
221     *         just call <code>TimeZone.getDefault()</code>.
222     */
223    public static TimeZone DEFAULT_TIME_ZONE = TimeZone.getDefault();
224
225    /**
226     * This will be a utility calendar that has no DST but is shifted relative
227     * to the default time zone's offset.
228     */
229    private Calendar workingCalendarNoDST;
230
231    /**
232     * This will be a utility calendar that used the default time zone.
233     */
234    private Calendar workingCalendar = Calendar.getInstance();
235
236    ////////////////////////////////////////////////////////////////////////////
237    // private attributes
238    ////////////////////////////////////////////////////////////////////////////
239
240    /** Segment size in ms. */
241    private long segmentSize;
242
243    /** Number of consecutive segments to include in a segment group. */
244    private int segmentsIncluded;
245
246    /** Number of consecutive segments to exclude in a segment group. */
247    private int segmentsExcluded;
248
249    /** Number of segments in a group (segmentsIncluded + segmentsExcluded). */
250    private int groupSegmentCount;
251
252    /**
253     * Start of time reference from time zero (1/1/1970).
254     * This is the start of segment #0.
255     */
256    private long startTime;
257
258    /** Consecutive ms in segmentsIncluded (segmentsIncluded * segmentSize). */
259    private long segmentsIncludedSize;
260
261    /** Consecutive ms in segmentsExcluded (segmentsExcluded * segmentSize). */
262    private long segmentsExcludedSize;
263
264    /** ms in a segment group (segmentsIncludedSize + segmentsExcludedSize). */
265    private long segmentsGroupSize;
266
267    /**
268     * List of exception segments (exceptions segments that would otherwise be
269     * included based on the periodic (included, excluded) grouping).
270     */
271    private List exceptionSegments = new ArrayList();
272
273    /**
274     * This base timeline is used to specify exceptions at a higher level. For
275     * example, if we are a intraday timeline and want to exclude holidays,
276     * instead of having to exclude all intraday segments for the holiday,
277     * segments from this base timeline can be excluded. This baseTimeline is
278     * always optional and is only a convenience method.
279     * <p>
280     * Additionally, all excluded segments from this baseTimeline will be
281     * considered exceptions at this level.
282     */
283    private SegmentedTimeline baseTimeline;
284
285    /** A flag that controls whether or not to adjust for daylight saving. */
286    private boolean adjustForDaylightSaving = false;
287
288    ////////////////////////////////////////////////////////////////////////////
289    // static block
290    ////////////////////////////////////////////////////////////////////////////
291
292    static {
293        // make a time zone with no DST for our Calendar calculations
294        int offset = TimeZone.getDefault().getRawOffset();
295        NO_DST_TIME_ZONE = new SimpleTimeZone(offset, "UTC-" + offset);
296
297        // calculate midnight of first monday after 1/1/1900 relative to
298        // current locale
299        Calendar cal = new GregorianCalendar(NO_DST_TIME_ZONE);
300        cal.set(1900, 0, 1, 0, 0, 0);
301        cal.set(Calendar.MILLISECOND, 0);
302        while (cal.get(Calendar.DAY_OF_WEEK) != Calendar.MONDAY) {
303            cal.add(Calendar.DATE, 1);
304        }
305        // FIRST_MONDAY_AFTER_1900 = cal.getTime().getTime();
306        // preceding code won't work with JDK 1.3
307        FIRST_MONDAY_AFTER_1900 = cal.getTime().getTime();
308    }
309
310    ////////////////////////////////////////////////////////////////////////////
311    // constructors and factory methods
312    ////////////////////////////////////////////////////////////////////////////
313
314    /**
315     * Constructs a new segmented timeline, optionaly using another segmented
316     * timeline as its base. This chaining of SegmentedTimelines allows further
317     * segmentation into smaller timelines.
318     *
319     * If a base
320     *
321     * @param segmentSize the size of a segment in ms. This time unit will be
322     *        used to compute the included and excluded segments of the
323     *        timeline.
324     * @param segmentsIncluded Number of consecutive segments to include.
325     * @param segmentsExcluded Number of consecutive segments to exclude.
326     */
327    public SegmentedTimeline(long segmentSize,
328                             int segmentsIncluded,
329                             int segmentsExcluded) {
330
331        this.segmentSize = segmentSize;
332        this.segmentsIncluded = segmentsIncluded;
333        this.segmentsExcluded = segmentsExcluded;
334
335        this.groupSegmentCount = this.segmentsIncluded + this.segmentsExcluded;
336        this.segmentsIncludedSize = this.segmentsIncluded * this.segmentSize;
337        this.segmentsExcludedSize = this.segmentsExcluded * this.segmentSize;
338        this.segmentsGroupSize = this.segmentsIncludedSize
339                                 + this.segmentsExcludedSize;
340        int offset = TimeZone.getDefault().getRawOffset();
341        TimeZone z = new SimpleTimeZone(offset, "UTC-" + offset);
342        this.workingCalendarNoDST = new GregorianCalendar(z,
343                Locale.getDefault());
344    }
345
346    /**
347     * Returns the milliseconds for midnight of the first Monday after
348     * 1-Jan-1900, ignoring daylight savings.
349     *
350     * @return The milliseconds.
351     *
352     * @since 1.0.7
353     */
354    public static long firstMondayAfter1900() {
355        int offset = TimeZone.getDefault().getRawOffset();
356        TimeZone z = new SimpleTimeZone(offset, "UTC-" + offset);
357
358        // calculate midnight of first monday after 1/1/1900 relative to
359        // current locale
360        Calendar cal = new GregorianCalendar(z);
361        cal.set(1900, 0, 1, 0, 0, 0);
362        cal.set(Calendar.MILLISECOND, 0);
363        while (cal.get(Calendar.DAY_OF_WEEK) != Calendar.MONDAY) {
364            cal.add(Calendar.DATE, 1);
365        }
366        //return cal.getTimeInMillis();
367        // preceding code won't work with JDK 1.3
368        return cal.getTime().getTime();
369    }
370
371    /**
372     * Factory method to create a Monday through Friday SegmentedTimeline.
373     * <P>
374     * The <code>startTime</code> of the resulting timeline will be midnight
375     * of the first Monday after 1/1/1900.
376     *
377     * @return A fully initialized SegmentedTimeline.
378     */
379    public static SegmentedTimeline newMondayThroughFridayTimeline() {
380        SegmentedTimeline timeline
381            = new SegmentedTimeline(DAY_SEGMENT_SIZE, 5, 2);
382        timeline.setStartTime(firstMondayAfter1900());
383        return timeline;
384    }
385
386    /**
387     * Factory method to create a 15-min, 9:00 AM thought 4:00 PM, Monday
388     * through Friday SegmentedTimeline.
389     * <P>
390     * This timeline uses a segmentSize of FIFTEEN_MIN_SEGMENT_SIZE. The
391     * segment group is defined as 28 included segments (9:00 AM through
392     * 4:00 PM) and 68 excluded segments (4:00 PM through 9:00 AM the next day).
393     * <P>
394     * In order to exclude Saturdays and Sundays it uses a baseTimeline that
395     * only includes Monday through Friday days.
396     * <P>
397     * The <code>startTime</code> of the resulting timeline will be 9:00 AM
398     * after the startTime of the baseTimeline. This will correspond to 9:00 AM
399     * of the first Monday after 1/1/1900.
400     *
401     * @return A fully initialized SegmentedTimeline.
402     */
403    public static SegmentedTimeline newFifteenMinuteTimeline() {
404        SegmentedTimeline timeline = new SegmentedTimeline(
405                FIFTEEN_MINUTE_SEGMENT_SIZE, 28, 68);
406        timeline.setStartTime(firstMondayAfter1900() + 36
407                * timeline.getSegmentSize());
408        timeline.setBaseTimeline(newMondayThroughFridayTimeline());
409        return timeline;
410    }
411
412    /**
413     * Returns the flag that controls whether or not the daylight saving
414     * adjustment is applied.
415     *
416     * @return A boolean.
417     */
418    public boolean getAdjustForDaylightSaving() {
419        return this.adjustForDaylightSaving;
420    }
421
422    /**
423     * Sets the flag that controls whether or not the daylight saving adjustment
424     * is applied.
425     *
426     * @param adjust  the flag.
427     */
428    public void setAdjustForDaylightSaving(boolean adjust) {
429        this.adjustForDaylightSaving = adjust;
430    }
431
432    ////////////////////////////////////////////////////////////////////////////
433    // operations
434    ////////////////////////////////////////////////////////////////////////////
435
436    /**
437     * Sets the start time for the timeline. This is the beginning of segment
438     * zero.
439     *
440     * @param millisecond  the start time (encoded as in java.util.Date).
441     */
442    public void setStartTime(long millisecond) {
443        this.startTime = millisecond;
444    }
445
446    /**
447     * Returns the start time for the timeline. This is the beginning of
448     * segment zero.
449     *
450     * @return The start time.
451     */
452    public long getStartTime() {
453        return this.startTime;
454    }
455
456    /**
457     * Returns the number of segments excluded per segment group.
458     *
459     * @return The number of segments excluded.
460     */
461    public int getSegmentsExcluded() {
462        return this.segmentsExcluded;
463    }
464
465    /**
466     * Returns the size in milliseconds of the segments excluded per segment
467     * group.
468     *
469     * @return The size in milliseconds.
470     */
471    public long getSegmentsExcludedSize() {
472        return this.segmentsExcludedSize;
473    }
474
475    /**
476     * Returns the number of segments in a segment group. This will be equal to
477     * segments included plus segments excluded.
478     *
479     * @return The number of segments.
480     */
481    public int getGroupSegmentCount() {
482        return this.groupSegmentCount;
483    }
484
485    /**
486     * Returns the size in milliseconds of a segment group. This will be equal
487     * to size of the segments included plus the size of the segments excluded.
488     *
489     * @return The segment group size in milliseconds.
490     */
491    public long getSegmentsGroupSize() {
492        return this.segmentsGroupSize;
493    }
494
495    /**
496     * Returns the number of segments included per segment group.
497     *
498     * @return The number of segments.
499     */
500    public int getSegmentsIncluded() {
501        return this.segmentsIncluded;
502    }
503
504    /**
505     * Returns the size in ms of the segments included per segment group.
506     *
507     * @return The segment size in milliseconds.
508     */
509    public long getSegmentsIncludedSize() {
510        return this.segmentsIncludedSize;
511    }
512
513    /**
514     * Returns the size of one segment in ms.
515     *
516     * @return The segment size in milliseconds.
517     */
518    public long getSegmentSize() {
519        return this.segmentSize;
520    }
521
522    /**
523     * Returns a list of all the exception segments. This list is not
524     * modifiable.
525     *
526     * @return The exception segments.
527     */
528    public List getExceptionSegments() {
529        return Collections.unmodifiableList(this.exceptionSegments);
530    }
531
532    /**
533     * Sets the exception segments list.
534     *
535     * @param exceptionSegments  the exception segments.
536     */
537    public void setExceptionSegments(List exceptionSegments) {
538        this.exceptionSegments = exceptionSegments;
539    }
540
541    /**
542     * Returns our baseTimeline, or <code>null</code> if none.
543     *
544     * @return The base timeline.
545     */
546    public SegmentedTimeline getBaseTimeline() {
547        return this.baseTimeline;
548    }
549
550    /**
551     * Sets the base timeline.
552     *
553     * @param baseTimeline  the timeline.
554     */
555    public void setBaseTimeline(SegmentedTimeline baseTimeline) {
556
557        // verify that baseTimeline is compatible with us
558        if (baseTimeline != null) {
559            if (baseTimeline.getSegmentSize() < this.segmentSize) {
560                throw new IllegalArgumentException(
561                        "baseTimeline.getSegmentSize() "
562                        + "is smaller than segmentSize");
563            }
564            else if (baseTimeline.getStartTime() > this.startTime) {
565                throw new IllegalArgumentException(
566                        "baseTimeline.getStartTime() is after startTime");
567            }
568            else if ((baseTimeline.getSegmentSize() % this.segmentSize) != 0) {
569                throw new IllegalArgumentException(
570                        "baseTimeline.getSegmentSize() is not multiple of "
571                        + "segmentSize");
572            }
573            else if (((this.startTime
574                    - baseTimeline.getStartTime()) % this.segmentSize) != 0) {
575                throw new IllegalArgumentException(
576                        "baseTimeline is not aligned");
577            }
578        }
579
580        this.baseTimeline = baseTimeline;
581    }
582
583    /**
584     * Translates a value relative to the domain value (all Dates) into a value
585     * relative to the segmented timeline. The values relative to the segmented
586     * timeline are all consecutives starting at zero at the startTime.
587     *
588     * @param millisecond  the millisecond (as encoded by java.util.Date).
589     *
590     * @return The timeline value.
591     */
592    @Override
593    public long toTimelineValue(long millisecond) {
594
595        long result;
596        long rawMilliseconds = millisecond - this.startTime;
597        long groupMilliseconds = rawMilliseconds % this.segmentsGroupSize;
598        long groupIndex = rawMilliseconds / this.segmentsGroupSize;
599
600        if (groupMilliseconds >= this.segmentsIncludedSize) {
601            result = toTimelineValue(this.startTime + this.segmentsGroupSize
602                    * (groupIndex + 1));
603        }
604        else {
605            Segment segment = getSegment(millisecond);
606            if (segment.inExceptionSegments()) {
607                int p;
608                while ((p = binarySearchExceptionSegments(segment)) >= 0) {
609                    segment = getSegment(millisecond = ((Segment)
610                            this.exceptionSegments.get(p)).getSegmentEnd() + 1);
611                }
612                result = toTimelineValue(millisecond);
613            }
614            else {
615                long shiftedSegmentedValue = millisecond - this.startTime;
616                long x = shiftedSegmentedValue % this.segmentsGroupSize;
617                long y = shiftedSegmentedValue / this.segmentsGroupSize;
618
619                long wholeExceptionsBeforeDomainValue =
620                    getExceptionSegmentCount(this.startTime, millisecond - 1);
621
622//                long partialTimeInException = 0;
623//                Segment ss = getSegment(millisecond);
624//                if (ss.inExceptionSegments()) {
625//                    partialTimeInException = millisecond
626                //     - ss.getSegmentStart();
627//                }
628
629                if (x < this.segmentsIncludedSize) {
630                    result = this.segmentsIncludedSize * y
631                             + x - wholeExceptionsBeforeDomainValue
632                             * this.segmentSize;
633                             // - partialTimeInException;
634                }
635                else {
636                    result = this.segmentsIncludedSize * (y + 1)
637                             - wholeExceptionsBeforeDomainValue
638                             * this.segmentSize;
639                             // - partialTimeInException;
640                }
641            }
642        }
643
644        return result;
645    }
646
647    /**
648     * Translates a date into a value relative to the segmented timeline. The
649     * values relative to the segmented timeline are all consecutives starting
650     * at zero at the startTime.
651     *
652     * @param date  date relative to the domain.
653     *
654     * @return The timeline value (in milliseconds).
655     */
656    @Override
657    public long toTimelineValue(Date date) {
658        return toTimelineValue(getTime(date));
659        //return toTimelineValue(dateDomainValue.getTime());
660    }
661
662    /**
663     * Translates a value relative to the timeline into a millisecond.
664     *
665     * @param timelineValue  the timeline value (in milliseconds).
666     *
667     * @return The domain value (in milliseconds).
668     */
669    @Override
670    public long toMillisecond(long timelineValue) {
671
672        // calculate the result as if no exceptions
673        Segment result = new Segment(this.startTime + timelineValue
674                + (timelineValue / this.segmentsIncludedSize)
675                * this.segmentsExcludedSize);
676
677        long lastIndex = this.startTime;
678
679        // adjust result for any exceptions in the result calculated
680        while (lastIndex <= result.segmentStart) {
681
682            // skip all whole exception segments in the range
683            long exceptionSegmentCount;
684            while ((exceptionSegmentCount = getExceptionSegmentCount(
685                 lastIndex, (result.millisecond / this.segmentSize)
686                 * this.segmentSize - 1)) > 0
687            ) {
688                lastIndex = result.segmentStart;
689                // move forward exceptionSegmentCount segments skipping
690                // excluded segments
691                for (int i = 0; i < exceptionSegmentCount; i++) {
692                    do {
693                        result.inc();
694                    }
695                    while (result.inExcludeSegments());
696                }
697            }
698            lastIndex = result.segmentStart;
699
700            // skip exception or excluded segments we may fall on
701            while (result.inExceptionSegments() || result.inExcludeSegments()) {
702                result.inc();
703                lastIndex += this.segmentSize;
704            }
705
706            lastIndex++;
707        }
708
709        return getTimeFromLong(result.millisecond);
710    }
711
712    /**
713     * Converts a date/time value to take account of daylight savings time.
714     *
715     * @param date  the milliseconds.
716     *
717     * @return The milliseconds.
718     */
719    public long getTimeFromLong(long date) {
720        long result = date;
721        if (this.adjustForDaylightSaving) {
722            this.workingCalendarNoDST.setTime(new Date(date));
723            this.workingCalendar.set(
724                this.workingCalendarNoDST.get(Calendar.YEAR),
725                this.workingCalendarNoDST.get(Calendar.MONTH),
726                this.workingCalendarNoDST.get(Calendar.DATE),
727                this.workingCalendarNoDST.get(Calendar.HOUR_OF_DAY),
728                this.workingCalendarNoDST.get(Calendar.MINUTE),
729                this.workingCalendarNoDST.get(Calendar.SECOND)
730            );
731            this.workingCalendar.set(Calendar.MILLISECOND,
732                    this.workingCalendarNoDST.get(Calendar.MILLISECOND));
733            // result = this.workingCalendar.getTimeInMillis();
734            // preceding code won't work with JDK 1.3
735            result = this.workingCalendar.getTime().getTime();
736        }
737        return result;
738    }
739
740    /**
741     * Returns <code>true</code> if a value is contained in the timeline.
742     *
743     * @param millisecond  the value to verify.
744     *
745     * @return <code>true</code> if value is contained in the timeline.
746     */
747    @Override
748    public boolean containsDomainValue(long millisecond) {
749        Segment segment = getSegment(millisecond);
750        return segment.inIncludeSegments();
751    }
752
753    /**
754     * Returns <code>true</code> if a value is contained in the timeline.
755     *
756     * @param date  date to verify
757     *
758     * @return <code>true</code> if value is contained in the timeline
759     */
760    @Override
761    public boolean containsDomainValue(Date date) {
762        return containsDomainValue(getTime(date));
763    }
764
765    /**
766     * Returns <code>true</code> if a range of values are contained in the
767     * timeline. This is implemented verifying that all segments are in the
768     * range.
769     *
770     * @param domainValueStart start of the range to verify
771     * @param domainValueEnd end of the range to verify
772     *
773     * @return <code>true</code> if the range is contained in the timeline
774     */
775    @Override
776    public boolean containsDomainRange(long domainValueStart,
777            long domainValueEnd) {
778        if (domainValueEnd < domainValueStart) {
779            throw new IllegalArgumentException(
780                    "domainValueEnd (" + domainValueEnd
781                    + ") < domainValueStart (" + domainValueStart + ")");
782        }
783        Segment segment = getSegment(domainValueStart);
784        boolean contains = true;
785        do {
786            contains = (segment.inIncludeSegments());
787            if (segment.contains(domainValueEnd)) {
788                break;
789            }
790            else {
791                segment.inc();
792            }
793        }
794        while (contains);
795        return (contains);
796    }
797
798    /**
799     * Returns <code>true</code> if a range of values are contained in the
800     * timeline. This is implemented verifying that all segments are in the
801     * range.
802     *
803     * @param dateDomainValueStart start of the range to verify
804     * @param dateDomainValueEnd end of the range to verify
805     *
806     * @return <code>true</code> if the range is contained in the timeline
807     */
808    @Override
809    public boolean containsDomainRange(Date dateDomainValueStart,
810            Date dateDomainValueEnd) {
811        return containsDomainRange(getTime(dateDomainValueStart),
812                getTime(dateDomainValueEnd));
813    }
814
815    /**
816     * Adds a segment as an exception. An exception segment is defined as a
817     * segment to exclude from what would otherwise be considered a valid
818     * segment of the timeline.  An exception segment can not be contained
819     * inside an already excluded segment.  If so, no action will occur (the
820     * proposed exception segment will be discarded).
821     * <p>
822     * The segment is identified by a domainValue into any part of the segment.
823     * Therefore the segmentStart <= domainValue <= segmentEnd.
824     *
825     * @param millisecond  domain value to treat as an exception
826     */
827    public void addException(long millisecond) {
828        addException(new Segment(millisecond));
829    }
830
831    /**
832     * Adds a segment range as an exception. An exception segment is defined as
833     * a segment to exclude from what would otherwise be considered a valid
834     * segment of the timeline.  An exception segment can not be contained
835     * inside an already excluded segment.  If so, no action will occur (the
836     * proposed exception segment will be discarded).
837     * <p>
838     * The segment range is identified by a domainValue that begins a valid
839     * segment and ends with a domainValue that ends a valid segment.
840     * Therefore the range will contain all segments whose segmentStart
841     * <= domainValue and segmentEnd <= toDomainValue.
842     *
843     * @param fromDomainValue  start of domain range to treat as an exception
844     * @param toDomainValue  end of domain range to treat as an exception
845     */
846    public void addException(long fromDomainValue, long toDomainValue) {
847        addException(new SegmentRange(fromDomainValue, toDomainValue));
848    }
849
850    /**
851     * Adds a segment as an exception. An exception segment is defined as a
852     * segment to exclude from what would otherwise be considered a valid
853     * segment of the timeline.  An exception segment can not be contained
854     * inside an already excluded segment.  If so, no action will occur (the
855     * proposed exception segment will be discarded).
856     * <p>
857     * The segment is identified by a Date into any part of the segment.
858     *
859     * @param exceptionDate  Date into the segment to exclude.
860     */
861    public void addException(Date exceptionDate) {
862        addException(getTime(exceptionDate));
863        //addException(exceptionDate.getTime());
864    }
865
866    /**
867     * Adds a list of dates as segment exceptions. Each exception segment is
868     * defined as a segment to exclude from what would otherwise be considered
869     * a valid segment of the timeline.  An exception segment can not be
870     * contained inside an already excluded segment.  If so, no action will
871     * occur (the proposed exception segment will be discarded).
872     * <p>
873     * The segment is identified by a Date into any part of the segment.
874     *
875     * @param exceptionList  List of Date objects that identify the segments to
876     *                       exclude.
877     */
878    public void addExceptions(List exceptionList) {
879        for (Iterator iter = exceptionList.iterator(); iter.hasNext();) {
880            addException((Date) iter.next());
881        }
882    }
883
884    /**
885     * Adds a segment as an exception. An exception segment is defined as a
886     * segment to exclude from what would otherwise be considered a valid
887     * segment of the timeline.  An exception segment can not be contained
888     * inside an already excluded segment.  This is verified inside this
889     * method, and if so, no action will occur (the proposed exception segment
890     * will be discarded).
891     *
892     * @param segment  the segment to exclude.
893     */
894    private void addException(Segment segment) {
895         if (segment.inIncludeSegments()) {
896             int p = binarySearchExceptionSegments(segment);
897             this.exceptionSegments.add(-(p + 1), segment);
898         }
899    }
900
901    /**
902     * Adds a segment relative to the baseTimeline as an exception. Because a
903     * base segment is normally larger than our segments, this may add one or
904     * more segment ranges to the exception list.
905     * <p>
906     * An exception segment is defined as a segment
907     * to exclude from what would otherwise be considered a valid segment of
908     * the timeline.  An exception segment can not be contained inside an
909     * already excluded segment.  If so, no action will occur (the proposed
910     * exception segment will be discarded).
911     * <p>
912     * The segment is identified by a domainValue into any part of the
913     * baseTimeline segment.
914     *
915     * @param domainValue  domain value to teat as a baseTimeline exception.
916     */
917    public void addBaseTimelineException(long domainValue) {
918
919        Segment baseSegment = this.baseTimeline.getSegment(domainValue);
920        if (baseSegment.inIncludeSegments()) {
921
922            // cycle through all the segments contained in the BaseTimeline
923            // exception segment
924            Segment segment = getSegment(baseSegment.getSegmentStart());
925            while (segment.getSegmentStart() <= baseSegment.getSegmentEnd()) {
926                if (segment.inIncludeSegments()) {
927
928                    // find all consecutive included segments
929                    long fromDomainValue = segment.getSegmentStart();
930                    long toDomainValue;
931                    do {
932                        toDomainValue = segment.getSegmentEnd();
933                        segment.inc();
934                    }
935                    while (segment.inIncludeSegments());
936
937                    // add the interval as an exception
938                    addException(fromDomainValue, toDomainValue);
939
940                }
941                else {
942                    // this is not one of our included segment, skip it
943                    segment.inc();
944                }
945            }
946        }
947    }
948
949    /**
950     * Adds a segment relative to the baseTimeline as an exception. An
951     * exception segment is defined as a segment to exclude from what would
952     * otherwise be considered a valid segment of the timeline.  An exception
953     * segment can not be contained inside an already excluded segment. If so,
954     * no action will occure (the proposed exception segment will be discarded).
955     * <p>
956     * The segment is identified by a domainValue into any part of the segment.
957     * Therefore the segmentStart <= domainValue <= segmentEnd.
958     *
959     * @param date  date domain value to treat as a baseTimeline exception
960     */
961    public void addBaseTimelineException(Date date) {
962        addBaseTimelineException(getTime(date));
963    }
964
965    /**
966     * Adds all excluded segments from the BaseTimeline as exceptions to our
967     * timeline. This allows us to combine two timelines for more complex
968     * calculations.
969     *
970     * @param fromBaseDomainValue Start of the range where exclusions will be
971     *                            extracted.
972     * @param toBaseDomainValue End of the range to process.
973     */
974    public void addBaseTimelineExclusions(long fromBaseDomainValue,
975                                          long toBaseDomainValue) {
976
977        // find first excluded base segment starting fromDomainValue
978        Segment baseSegment = this.baseTimeline.getSegment(fromBaseDomainValue);
979        while (baseSegment.getSegmentStart() <= toBaseDomainValue
980               && !baseSegment.inExcludeSegments()) {
981
982            baseSegment.inc();
983
984        }
985
986        // cycle over all the base segments groups in the range
987        while (baseSegment.getSegmentStart() <= toBaseDomainValue) {
988
989            long baseExclusionRangeEnd = baseSegment.getSegmentStart()
990                 + this.baseTimeline.getSegmentsExcluded()
991                 * this.baseTimeline.getSegmentSize() - 1;
992
993            // cycle through all the segments contained in the base exclusion
994            // area
995            Segment segment = getSegment(baseSegment.getSegmentStart());
996            while (segment.getSegmentStart() <= baseExclusionRangeEnd) {
997                if (segment.inIncludeSegments()) {
998
999                    // find all consecutive included segments
1000                    long fromDomainValue = segment.getSegmentStart();
1001                    long toDomainValue;
1002                    do {
1003                        toDomainValue = segment.getSegmentEnd();
1004                        segment.inc();
1005                    }
1006                    while (segment.inIncludeSegments());
1007
1008                    // add the interval as an exception
1009                    addException(new BaseTimelineSegmentRange(
1010                            fromDomainValue, toDomainValue));
1011                }
1012                else {
1013                    // this is not one of our included segment, skip it
1014                    segment.inc();
1015                }
1016            }
1017
1018            // go to next base segment group
1019            baseSegment.inc(this.baseTimeline.getGroupSegmentCount());
1020        }
1021    }
1022
1023    /**
1024     * Returns the number of exception segments wholly contained in the
1025     * (fromDomainValue, toDomainValue) interval.
1026     *
1027     * @param fromMillisecond  the beginning of the interval.
1028     * @param toMillisecond  the end of the interval.
1029     *
1030     * @return Number of exception segments contained in the interval.
1031     */
1032    public long getExceptionSegmentCount(long fromMillisecond,
1033                                         long toMillisecond) {
1034        if (toMillisecond < fromMillisecond) {
1035            return (0);
1036        }
1037
1038        int n = 0;
1039        for (Iterator iter = this.exceptionSegments.iterator();
1040             iter.hasNext();) {
1041            Segment segment = (Segment) iter.next();
1042            Segment intersection = segment.intersect(fromMillisecond,
1043                    toMillisecond);
1044            if (intersection != null) {
1045                n += intersection.getSegmentCount();
1046            }
1047        }
1048
1049        return (n);
1050    }
1051
1052    /**
1053     * Returns a segment that contains a domainValue. If the domainValue is
1054     * not contained in the timeline (because it is not contained in the
1055     * baseTimeline), a Segment that contains
1056     * <code>index + segmentSize*m</code> will be returned for the smallest
1057     * <code>m</code> possible.
1058     *
1059     * @param millisecond  index into the segment
1060     *
1061     * @return A Segment that contains index, or the next possible Segment.
1062     */
1063    public Segment getSegment(long millisecond) {
1064        return new Segment(millisecond);
1065    }
1066
1067    /**
1068     * Returns a segment that contains a date. For accurate calculations,
1069     * the calendar should use TIME_ZONE for its calculation (or any other
1070     * similar time zone).
1071     *
1072     * If the date is not contained in the timeline (because it is not
1073     * contained in the baseTimeline), a Segment that contains
1074     * <code>date + segmentSize*m</code> will be returned for the smallest
1075     * <code>m</code> possible.
1076     *
1077     * @param date date into the segment
1078     *
1079     * @return A Segment that contains date, or the next possible Segment.
1080     */
1081    public Segment getSegment(Date date) {
1082        return (getSegment(getTime(date)));
1083    }
1084
1085    /**
1086     * Convenient method to test equality in two objects, taking into account
1087     * nulls.
1088     *
1089     * @param o first object to compare
1090     * @param p second object to compare
1091     *
1092     * @return <code>true</code> if both objects are equal or both
1093     *         <code>null</code>, <code>false</code> otherwise.
1094     */
1095    private boolean equals(Object o, Object p) {
1096        return (o == p || ((o != null) && o.equals(p)));
1097    }
1098
1099    /**
1100     * Returns true if we are equal to the parameter
1101     *
1102     * @param o Object to verify with us
1103     *
1104     * @return <code>true</code> or <code>false</code>
1105     */
1106    @Override
1107    public boolean equals(Object o) {
1108        if (o instanceof SegmentedTimeline) {
1109            SegmentedTimeline other = (SegmentedTimeline) o;
1110
1111            boolean b0 = (this.segmentSize == other.getSegmentSize());
1112            boolean b1 = (this.segmentsIncluded == other.getSegmentsIncluded());
1113            boolean b2 = (this.segmentsExcluded == other.getSegmentsExcluded());
1114            boolean b3 = (this.startTime == other.getStartTime());
1115            boolean b4 = equals(this.exceptionSegments,
1116                    other.getExceptionSegments());
1117            return b0 && b1 && b2 && b3 && b4;
1118        }
1119        else {
1120            return (false);
1121        }
1122    }
1123
1124    /**
1125     * Returns a hash code for this object.
1126     *
1127     * @return A hash code.
1128     */
1129    @Override
1130    public int hashCode() {
1131        int result = 19;
1132        result = 37 * result
1133                 + (int) (this.segmentSize ^ (this.segmentSize >>> 32));
1134        result = 37 * result + (int) (this.startTime ^ (this.startTime >>> 32));
1135        return result;
1136    }
1137
1138    /**
1139     * Preforms a binary serach in the exceptionSegments sorted array. This
1140     * array can contain Segments or SegmentRange objects.
1141     *
1142     * @param  segment the key to be searched for.
1143     *
1144     * @return index of the search segment, if it is contained in the list;
1145     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1146     *         <i>insertion point</i> is defined as the point at which the
1147     *         segment would be inserted into the list: the index of the first
1148     *         element greater than the key, or <tt>list.size()</tt>, if all
1149     *         elements in the list are less than the specified segment.  Note
1150     *         that this guarantees that the return value will be &gt;= 0 if
1151     *         and only if the key is found.
1152     */
1153    private int binarySearchExceptionSegments(Segment segment) {
1154        int low = 0;
1155        int high = this.exceptionSegments.size() - 1;
1156
1157        while (low <= high) {
1158            int mid = (low + high) / 2;
1159            Segment midSegment = (Segment) this.exceptionSegments.get(mid);
1160
1161            // first test for equality (contains or contained)
1162            if (segment.contains(midSegment) || midSegment.contains(segment)) {
1163                return mid;
1164            }
1165
1166            if (midSegment.before(segment)) {
1167                low = mid + 1;
1168            }
1169            else if (midSegment.after(segment)) {
1170                high = mid - 1;
1171            }
1172            else {
1173                throw new IllegalStateException("Invalid condition.");
1174            }
1175        }
1176        return -(low + 1);  // key not found
1177    }
1178
1179    /**
1180     * Special method that handles conversion between the Default Time Zone and
1181     * a UTC time zone with no DST. This is needed so all days have the same
1182     * size. This method is the prefered way of converting a Data into
1183     * milliseconds for usage in this class.
1184     *
1185     * @param date Date to convert to long.
1186     *
1187     * @return The milliseconds.
1188     */
1189    public long getTime(Date date) {
1190        long result = date.getTime();
1191        if (this.adjustForDaylightSaving) {
1192            this.workingCalendar.setTime(date);
1193            this.workingCalendarNoDST.set(
1194                    this.workingCalendar.get(Calendar.YEAR),
1195                    this.workingCalendar.get(Calendar.MONTH),
1196                    this.workingCalendar.get(Calendar.DATE),
1197                    this.workingCalendar.get(Calendar.HOUR_OF_DAY),
1198                    this.workingCalendar.get(Calendar.MINUTE),
1199                    this.workingCalendar.get(Calendar.SECOND));
1200            this.workingCalendarNoDST.set(Calendar.MILLISECOND,
1201                    this.workingCalendar.get(Calendar.MILLISECOND));
1202            Date revisedDate = this.workingCalendarNoDST.getTime();
1203            result = revisedDate.getTime();
1204        }
1205
1206        return result;
1207    }
1208
1209    /**
1210     * Converts a millisecond value into a {@link Date} object.
1211     *
1212     * @param value  the millisecond value.
1213     *
1214     * @return The date.
1215     */
1216    public Date getDate(long value) {
1217        this.workingCalendarNoDST.setTime(new Date(value));
1218        return (this.workingCalendarNoDST.getTime());
1219    }
1220
1221    /**
1222     * Returns a clone of the timeline.
1223     *
1224     * @return A clone.
1225     *
1226     * @throws CloneNotSupportedException ??.
1227     */
1228    @Override
1229    public Object clone() throws CloneNotSupportedException {
1230        SegmentedTimeline clone = (SegmentedTimeline) super.clone();
1231        return clone;
1232    }
1233
1234    /**
1235     * Internal class to represent a valid segment for this timeline. A segment
1236     * is valid on a timeline if it is part of its included, excluded or
1237     * exception segments.
1238     * <p>
1239     * Each segment will know its segment number, segmentStart, segmentEnd and
1240     * index inside the segment.
1241     */
1242    public class Segment implements Comparable, Cloneable, Serializable {
1243
1244        /** The segment number. */
1245        protected long segmentNumber;
1246
1247        /** The segment start. */
1248        protected long segmentStart;
1249
1250        /** The segment end. */
1251        protected long segmentEnd;
1252
1253        /** A reference point within the segment. */
1254        protected long millisecond;
1255
1256        /**
1257         * Protected constructor only used by sub-classes.
1258         */
1259        protected Segment() {
1260            // empty
1261        }
1262
1263        /**
1264         * Creates a segment for a given point in time.
1265         *
1266         * @param millisecond  the millisecond (as encoded by java.util.Date).
1267         */
1268        protected Segment(long millisecond) {
1269            this.segmentNumber = calculateSegmentNumber(millisecond);
1270            this.segmentStart = SegmentedTimeline.this.startTime
1271                + this.segmentNumber * SegmentedTimeline.this.segmentSize;
1272            this.segmentEnd
1273                = this.segmentStart + SegmentedTimeline.this.segmentSize - 1;
1274            this.millisecond = millisecond;
1275        }
1276
1277        /**
1278         * Calculates the segment number for a given millisecond.
1279         *
1280         * @param millis  the millisecond (as encoded by java.util.Date).
1281         *
1282         * @return The segment number.
1283         */
1284        public long calculateSegmentNumber(long millis) {
1285            if (millis >= SegmentedTimeline.this.startTime) {
1286                return (millis - SegmentedTimeline.this.startTime)
1287                    / SegmentedTimeline.this.segmentSize;
1288            }
1289            else {
1290                return ((millis - SegmentedTimeline.this.startTime)
1291                    / SegmentedTimeline.this.segmentSize) - 1;
1292            }
1293        }
1294
1295        /**
1296         * Returns the segment number of this segment. Segments start at 0.
1297         *
1298         * @return The segment number.
1299         */
1300        public long getSegmentNumber() {
1301            return this.segmentNumber;
1302        }
1303
1304        /**
1305         * Returns always one (the number of segments contained in this
1306         * segment).
1307         *
1308         * @return The segment count (always 1 for this class).
1309         */
1310        public long getSegmentCount() {
1311            return 1;
1312        }
1313
1314        /**
1315         * Gets the start of this segment in ms.
1316         *
1317         * @return The segment start.
1318         */
1319        public long getSegmentStart() {
1320            return this.segmentStart;
1321        }
1322
1323        /**
1324         * Gets the end of this segment in ms.
1325         *
1326         * @return The segment end.
1327         */
1328        public long getSegmentEnd() {
1329            return this.segmentEnd;
1330        }
1331
1332        /**
1333         * Returns the millisecond used to reference this segment (always
1334         * between the segmentStart and segmentEnd).
1335         *
1336         * @return The millisecond.
1337         */
1338        public long getMillisecond() {
1339            return this.millisecond;
1340        }
1341
1342        /**
1343         * Returns a {@link java.util.Date} that represents the reference point
1344         * for this segment.
1345         *
1346         * @return The date.
1347         */
1348        public Date getDate() {
1349            return SegmentedTimeline.this.getDate(this.millisecond);
1350        }
1351
1352        /**
1353         * Returns true if a particular millisecond is contained in this
1354         * segment.
1355         *
1356         * @param millis  the millisecond to verify.
1357         *
1358         * @return <code>true</code> if the millisecond is contained in the
1359         *         segment.
1360         */
1361        public boolean contains(long millis) {
1362            return (this.segmentStart <= millis && millis <= this.segmentEnd);
1363        }
1364
1365        /**
1366         * Returns <code>true</code> if an interval is contained in this
1367         * segment.
1368         *
1369         * @param from  the start of the interval.
1370         * @param to  the end of the interval.
1371         *
1372         * @return <code>true</code> if the interval is contained in the
1373         *         segment.
1374         */
1375        public boolean contains(long from, long to) {
1376            return (this.segmentStart <= from && to <= this.segmentEnd);
1377        }
1378
1379        /**
1380         * Returns <code>true</code> if a segment is contained in this segment.
1381         *
1382         * @param segment  the segment to test for inclusion
1383         *
1384         * @return <code>true</code> if the segment is contained in this
1385         *         segment.
1386         */
1387        public boolean contains(Segment segment) {
1388            return contains(segment.getSegmentStart(), segment.getSegmentEnd());
1389        }
1390
1391        /**
1392         * Returns <code>true</code> if this segment is contained in an
1393         * interval.
1394         *
1395         * @param from  the start of the interval.
1396         * @param to  the end of the interval.
1397         *
1398         * @return <code>true</code> if this segment is contained in the
1399         *         interval.
1400         */
1401        public boolean contained(long from, long to) {
1402            return (from <= this.segmentStart && this.segmentEnd <= to);
1403        }
1404
1405        /**
1406         * Returns a segment that is the intersection of this segment and the
1407         * interval.
1408         *
1409         * @param from  the start of the interval.
1410         * @param to  the end of the interval.
1411         *
1412         * @return A segment.
1413         */
1414        public Segment intersect(long from, long to) {
1415            if (from <= this.segmentStart && this.segmentEnd <= to) {
1416                return this;
1417            }
1418            else {
1419                return null;
1420            }
1421        }
1422
1423        /**
1424         * Returns <code>true</code> if this segment is wholly before another
1425         * segment.
1426         *
1427         * @param other  the other segment.
1428         *
1429         * @return A boolean.
1430         */
1431        public boolean before(Segment other) {
1432            return (this.segmentEnd < other.getSegmentStart());
1433        }
1434
1435        /**
1436         * Returns <code>true</code> if this segment is wholly after another
1437         * segment.
1438         *
1439         * @param other  the other segment.
1440         *
1441         * @return A boolean.
1442         */
1443        public boolean after(Segment other) {
1444            return (this.segmentStart > other.getSegmentEnd());
1445        }
1446
1447        /**
1448         * Tests an object (usually another <code>Segment</code>) for equality
1449         * with this segment.
1450         *
1451         * @param object The other segment to compare with us
1452         *
1453         * @return <code>true</code> if we are the same segment
1454         */
1455        @Override
1456        public boolean equals(Object object) {
1457            if (object instanceof Segment) {
1458                Segment other = (Segment) object;
1459                return (this.segmentNumber == other.getSegmentNumber()
1460                        && this.segmentStart == other.getSegmentStart()
1461                        && this.segmentEnd == other.getSegmentEnd()
1462                        && this.millisecond == other.getMillisecond());
1463            }
1464            else {
1465                return false;
1466            }
1467        }
1468
1469        /**
1470         * Returns a copy of ourselves or <code>null</code> if there was an
1471         * exception during cloning.
1472         *
1473         * @return A copy of this segment.
1474         */
1475        public Segment copy() {
1476            try {
1477                return (Segment) this.clone();
1478            }
1479            catch (CloneNotSupportedException e) {
1480                return null;
1481            }
1482        }
1483
1484        /**
1485         * Will compare this Segment with another Segment (from Comparable
1486         * interface).
1487         *
1488         * @param object The other Segment to compare with
1489         *
1490         * @return -1: this < object, 0: this.equal(object) and
1491         *         +1: this > object
1492         */
1493        @Override
1494        public int compareTo(Object object) {
1495            Segment other = (Segment) object;
1496            if (this.before(other)) {
1497                return -1;
1498            }
1499            else if (this.after(other)) {
1500                return +1;
1501            }
1502            else {
1503                return 0;
1504            }
1505        }
1506
1507        /**
1508         * Returns true if we are an included segment and we are not an
1509         * exception.
1510         *
1511         * @return <code>true</code> or <code>false</code>.
1512         */
1513        public boolean inIncludeSegments() {
1514            if (getSegmentNumberRelativeToGroup()
1515                    < SegmentedTimeline.this.segmentsIncluded) {
1516                return !inExceptionSegments();
1517            }
1518            else {
1519                return false;
1520            }
1521        }
1522
1523        /**
1524         * Returns true if we are an excluded segment.
1525         *
1526         * @return <code>true</code> or <code>false</code>.
1527         */
1528        public boolean inExcludeSegments() {
1529            return getSegmentNumberRelativeToGroup()
1530                    >= SegmentedTimeline.this.segmentsIncluded;
1531        }
1532
1533        /**
1534         * Calculate the segment number relative to the segment group. This
1535         * will be a number between 0 and segmentsGroup-1. This value is
1536         * calculated from the segmentNumber. Special care is taken for
1537         * negative segmentNumbers.
1538         *
1539         * @return The segment number.
1540         */
1541        private long getSegmentNumberRelativeToGroup() {
1542            long p = (this.segmentNumber
1543                    % SegmentedTimeline.this.groupSegmentCount);
1544            if (p < 0) {
1545                p += SegmentedTimeline.this.groupSegmentCount;
1546            }
1547            return p;
1548        }
1549
1550        /**
1551         * Returns true if we are an exception segment. This is implemented via
1552         * a binary search on the exceptionSegments sorted list.
1553         *
1554         * If the segment is not listed as an exception in our list and we have
1555         * a baseTimeline, a check is performed to see if the segment is inside
1556         * an excluded segment from our base. If so, it is also considered an
1557         * exception.
1558         *
1559         * @return <code>true</code> if we are an exception segment.
1560         */
1561        public boolean inExceptionSegments() {
1562            return binarySearchExceptionSegments(this) >= 0;
1563        }
1564
1565        /**
1566         * Increments the internal attributes of this segment by a number of
1567         * segments.
1568         *
1569         * @param n Number of segments to increment.
1570         */
1571        public void inc(long n) {
1572            this.segmentNumber += n;
1573            long m = n * SegmentedTimeline.this.segmentSize;
1574            this.segmentStart += m;
1575            this.segmentEnd += m;
1576            this.millisecond += m;
1577        }
1578
1579        /**
1580         * Increments the internal attributes of this segment by one segment.
1581         * The exact time incremented is segmentSize.
1582         */
1583        public void inc() {
1584            inc(1);
1585        }
1586
1587        /**
1588         * Decrements the internal attributes of this segment by a number of
1589         * segments.
1590         *
1591         * @param n Number of segments to decrement.
1592         */
1593        public void dec(long n) {
1594            this.segmentNumber -= n;
1595            long m = n * SegmentedTimeline.this.segmentSize;
1596            this.segmentStart -= m;
1597            this.segmentEnd -= m;
1598            this.millisecond -= m;
1599        }
1600
1601        /**
1602         * Decrements the internal attributes of this segment by one segment.
1603         * The exact time decremented is segmentSize.
1604         */
1605        public void dec() {
1606            dec(1);
1607        }
1608
1609        /**
1610         * Moves the index of this segment to the beginning if the segment.
1611         */
1612        public void moveIndexToStart() {
1613            this.millisecond = this.segmentStart;
1614        }
1615
1616        /**
1617         * Moves the index of this segment to the end of the segment.
1618         */
1619        public void moveIndexToEnd() {
1620            this.millisecond = this.segmentEnd;
1621        }
1622
1623    }
1624
1625    /**
1626     * Private internal class to represent a range of segments. This class is
1627     * mainly used to store in one object a range of exception segments. This
1628     * optimizes certain timelines that use a small segment size (like an
1629     * intraday timeline) allowing them to express a day exception as one
1630     * SegmentRange instead of multi Segments.
1631     */
1632    protected class SegmentRange extends Segment {
1633
1634        /** The number of segments in the range. */
1635        private long segmentCount;
1636
1637        /**
1638         * Creates a SegmentRange between a start and end domain values.
1639         *
1640         * @param fromMillisecond  start of the range
1641         * @param toMillisecond  end of the range
1642         */
1643        public SegmentRange(long fromMillisecond, long toMillisecond) {
1644
1645            Segment start = getSegment(fromMillisecond);
1646            Segment end = getSegment(toMillisecond);
1647//            if (start.getSegmentStart() != fromMillisecond
1648//                || end.getSegmentEnd() != toMillisecond) {
1649//                throw new IllegalArgumentException("Invalid Segment Range ["
1650//                    + fromMillisecond + "," + toMillisecond + "]");
1651//            }
1652
1653            this.millisecond = fromMillisecond;
1654            this.segmentNumber = calculateSegmentNumber(fromMillisecond);
1655            this.segmentStart = start.segmentStart;
1656            this.segmentEnd = end.segmentEnd;
1657            this.segmentCount
1658                = (end.getSegmentNumber() - start.getSegmentNumber() + 1);
1659        }
1660
1661        /**
1662         * Returns the number of segments contained in this range.
1663         *
1664         * @return The segment count.
1665         */
1666        @Override
1667        public long getSegmentCount() {
1668            return this.segmentCount;
1669        }
1670
1671        /**
1672         * Returns a segment that is the intersection of this segment and the
1673         * interval.
1674         *
1675         * @param from  the start of the interval.
1676         * @param to  the end of the interval.
1677         *
1678         * @return The intersection.
1679         */
1680        @Override
1681        public Segment intersect(long from, long to) {
1682
1683            // Segment fromSegment = getSegment(from);
1684            // fromSegment.inc();
1685            // Segment toSegment = getSegment(to);
1686            // toSegment.dec();
1687            long start = Math.max(from, this.segmentStart);
1688            long end = Math.min(to, this.segmentEnd);
1689            // long start = Math.max(
1690            //     fromSegment.getSegmentStart(), this.segmentStart
1691            // );
1692            // long end = Math.min(toSegment.getSegmentEnd(), this.segmentEnd);
1693            if (start <= end) {
1694                return new SegmentRange(start, end);
1695            }
1696            else {
1697                return null;
1698            }
1699        }
1700
1701        /**
1702         * Returns true if all Segments of this SegmentRenge are an included
1703         * segment and are not an exception.
1704         *
1705         * @return <code>true</code> or </code>false</code>.
1706         */
1707        @Override
1708        public boolean inIncludeSegments() {
1709            for (Segment segment = getSegment(this.segmentStart);
1710                segment.getSegmentStart() < this.segmentEnd;
1711                segment.inc()) {
1712                if (!segment.inIncludeSegments()) {
1713                    return (false);
1714                }
1715            }
1716            return true;
1717        }
1718
1719        /**
1720         * Returns true if we are an excluded segment.
1721         *
1722         * @return <code>true</code> or </code>false</code>.
1723         */
1724        @Override
1725        public boolean inExcludeSegments() {
1726            for (Segment segment = getSegment(this.segmentStart);
1727                segment.getSegmentStart() < this.segmentEnd;
1728                segment.inc()) {
1729                if (!segment.inExceptionSegments()) {
1730                    return (false);
1731                }
1732            }
1733            return true;
1734        }
1735
1736        /**
1737         * Not implemented for SegmentRange. Always throws
1738         * IllegalArgumentException.
1739         *
1740         * @param n Number of segments to increment.
1741         */
1742        @Override
1743        public void inc(long n) {
1744            throw new IllegalArgumentException(
1745                    "Not implemented in SegmentRange");
1746        }
1747
1748    }
1749
1750    /**
1751     * Special <code>SegmentRange</code> that came from the BaseTimeline.
1752     */
1753    protected class BaseTimelineSegmentRange extends SegmentRange {
1754
1755        /**
1756         * Constructor.
1757         *
1758         * @param fromDomainValue  the start value.
1759         * @param toDomainValue  the end value.
1760         */
1761        public BaseTimelineSegmentRange(long fromDomainValue,
1762                                        long toDomainValue) {
1763            super(fromDomainValue, toDomainValue);
1764        }
1765
1766    }
1767
1768}