001/* ===========================================================
002 * JFreeChart : a free chart library for the Java(tm) platform
003 * ===========================================================
004 *
005 * (C) Copyright 2000-2008, 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 * [Java is a trademark or registered trademark of Sun Microsystems, Inc.
025 * in the United States and other countries.]
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    public long toTimelineValue(long millisecond) {
593
594        long result;
595        long rawMilliseconds = millisecond - this.startTime;
596        long groupMilliseconds = rawMilliseconds % this.segmentsGroupSize;
597        long groupIndex = rawMilliseconds / this.segmentsGroupSize;
598
599        if (groupMilliseconds >= this.segmentsIncludedSize) {
600            result = toTimelineValue(this.startTime + this.segmentsGroupSize
601                    * (groupIndex + 1));
602        }
603        else {
604            Segment segment = getSegment(millisecond);
605            if (segment.inExceptionSegments()) {
606                int p;
607                while ((p = binarySearchExceptionSegments(segment)) >= 0) {
608                    segment = getSegment(millisecond = ((Segment)
609                            this.exceptionSegments.get(p)).getSegmentEnd() + 1);
610                }
611                result = toTimelineValue(millisecond);
612            }
613            else {
614                long shiftedSegmentedValue = millisecond - this.startTime;
615                long x = shiftedSegmentedValue % this.segmentsGroupSize;
616                long y = shiftedSegmentedValue / this.segmentsGroupSize;
617
618                long wholeExceptionsBeforeDomainValue =
619                    getExceptionSegmentCount(this.startTime, millisecond - 1);
620
621//                long partialTimeInException = 0;
622//                Segment ss = getSegment(millisecond);
623//                if (ss.inExceptionSegments()) {
624//                    partialTimeInException = millisecond
625                //     - ss.getSegmentStart();
626//                }
627
628                if (x < this.segmentsIncludedSize) {
629                    result = this.segmentsIncludedSize * y
630                             + x - wholeExceptionsBeforeDomainValue
631                             * this.segmentSize;
632                             // - partialTimeInException;
633                }
634                else {
635                    result = this.segmentsIncludedSize * (y + 1)
636                             - wholeExceptionsBeforeDomainValue
637                             * this.segmentSize;
638                             // - partialTimeInException;
639                }
640            }
641        }
642
643        return result;
644    }
645
646    /**
647     * Translates a date into a value relative to the segmented timeline. The
648     * values relative to the segmented timeline are all consecutives starting
649     * at zero at the startTime.
650     *
651     * @param date  date relative to the domain.
652     *
653     * @return The timeline value (in milliseconds).
654     */
655    public long toTimelineValue(Date date) {
656        return toTimelineValue(getTime(date));
657        //return toTimelineValue(dateDomainValue.getTime());
658    }
659
660    /**
661     * Translates a value relative to the timeline into a millisecond.
662     *
663     * @param timelineValue  the timeline value (in milliseconds).
664     *
665     * @return The domain value (in milliseconds).
666     */
667    public long toMillisecond(long timelineValue) {
668
669        // calculate the result as if no exceptions
670        Segment result = new Segment(this.startTime + timelineValue
671                + (timelineValue / this.segmentsIncludedSize)
672                * this.segmentsExcludedSize);
673
674        long lastIndex = this.startTime;
675
676        // adjust result for any exceptions in the result calculated
677        while (lastIndex <= result.segmentStart) {
678
679            // skip all whole exception segments in the range
680            long exceptionSegmentCount;
681            while ((exceptionSegmentCount = getExceptionSegmentCount(
682                 lastIndex, (result.millisecond / this.segmentSize)
683                 * this.segmentSize - 1)) > 0
684            ) {
685                lastIndex = result.segmentStart;
686                // move forward exceptionSegmentCount segments skipping
687                // excluded segments
688                for (int i = 0; i < exceptionSegmentCount; i++) {
689                    do {
690                        result.inc();
691                    }
692                    while (result.inExcludeSegments());
693                }
694            }
695            lastIndex = result.segmentStart;
696
697            // skip exception or excluded segments we may fall on
698            while (result.inExceptionSegments() || result.inExcludeSegments()) {
699                result.inc();
700                lastIndex += this.segmentSize;
701            }
702
703            lastIndex++;
704        }
705
706        return getTimeFromLong(result.millisecond);
707    }
708
709    /**
710     * Converts a date/time value to take account of daylight savings time.
711     *
712     * @param date  the milliseconds.
713     *
714     * @return The milliseconds.
715     */
716    public long getTimeFromLong(long date) {
717        long result = date;
718        if (this.adjustForDaylightSaving) {
719            this.workingCalendarNoDST.setTime(new Date(date));
720            this.workingCalendar.set(
721                this.workingCalendarNoDST.get(Calendar.YEAR),
722                this.workingCalendarNoDST.get(Calendar.MONTH),
723                this.workingCalendarNoDST.get(Calendar.DATE),
724                this.workingCalendarNoDST.get(Calendar.HOUR_OF_DAY),
725                this.workingCalendarNoDST.get(Calendar.MINUTE),
726                this.workingCalendarNoDST.get(Calendar.SECOND)
727            );
728            this.workingCalendar.set(Calendar.MILLISECOND,
729                    this.workingCalendarNoDST.get(Calendar.MILLISECOND));
730            // result = this.workingCalendar.getTimeInMillis();
731            // preceding code won't work with JDK 1.3
732            result = this.workingCalendar.getTime().getTime();
733        }
734        return result;
735    }
736
737    /**
738     * Returns <code>true</code> if a value is contained in the timeline.
739     *
740     * @param millisecond  the value to verify.
741     *
742     * @return <code>true</code> if value is contained in the timeline.
743     */
744    public boolean containsDomainValue(long millisecond) {
745        Segment segment = getSegment(millisecond);
746        return segment.inIncludeSegments();
747    }
748
749    /**
750     * Returns <code>true</code> if a value is contained in the timeline.
751     *
752     * @param date  date to verify
753     *
754     * @return <code>true</code> if value is contained in the timeline
755     */
756    public boolean containsDomainValue(Date date) {
757        return containsDomainValue(getTime(date));
758    }
759
760    /**
761     * Returns <code>true</code> if a range of values are contained in the
762     * timeline. This is implemented verifying that all segments are in the
763     * range.
764     *
765     * @param domainValueStart start of the range to verify
766     * @param domainValueEnd end of the range to verify
767     *
768     * @return <code>true</code> if the range is contained in the timeline
769     */
770    public boolean containsDomainRange(long domainValueStart,
771                                       long domainValueEnd) {
772        if (domainValueEnd < domainValueStart) {
773            throw new IllegalArgumentException(
774                    "domainValueEnd (" + domainValueEnd
775                    + ") < domainValueStart (" + domainValueStart + ")");
776        }
777        Segment segment = getSegment(domainValueStart);
778        boolean contains = true;
779        do {
780            contains = (segment.inIncludeSegments());
781            if (segment.contains(domainValueEnd)) {
782                break;
783            }
784            else {
785                segment.inc();
786            }
787        }
788        while (contains);
789        return (contains);
790    }
791
792    /**
793     * Returns <code>true</code> if a range of values are contained in the
794     * timeline. This is implemented verifying that all segments are in the
795     * range.
796     *
797     * @param dateDomainValueStart start of the range to verify
798     * @param dateDomainValueEnd end of the range to verify
799     *
800     * @return <code>true</code> if the range is contained in the timeline
801     */
802    public boolean containsDomainRange(Date dateDomainValueStart,
803                                       Date dateDomainValueEnd) {
804        return containsDomainRange(getTime(dateDomainValueStart),
805                getTime(dateDomainValueEnd));
806    }
807
808    /**
809     * Adds a segment as an exception. An exception segment is defined as a
810     * segment to exclude from what would otherwise be considered a valid
811     * segment of the timeline.  An exception segment can not be contained
812     * inside an already excluded segment.  If so, no action will occur (the
813     * proposed exception segment will be discarded).
814     * <p>
815     * The segment is identified by a domainValue into any part of the segment.
816     * Therefore the segmentStart <= domainValue <= segmentEnd.
817     *
818     * @param millisecond  domain value to treat as an exception
819     */
820    public void addException(long millisecond) {
821        addException(new Segment(millisecond));
822    }
823
824    /**
825     * Adds a segment range as an exception. An exception segment is defined as
826     * a segment to exclude from what would otherwise be considered a valid
827     * segment of the timeline.  An exception segment can not be contained
828     * inside an already excluded segment.  If so, no action will occur (the
829     * proposed exception segment will be discarded).
830     * <p>
831     * The segment range is identified by a domainValue that begins a valid
832     * segment and ends with a domainValue that ends a valid segment.
833     * Therefore the range will contain all segments whose segmentStart
834     * <= domainValue and segmentEnd <= toDomainValue.
835     *
836     * @param fromDomainValue  start of domain range to treat as an exception
837     * @param toDomainValue  end of domain range to treat as an exception
838     */
839    public void addException(long fromDomainValue, long toDomainValue) {
840        addException(new SegmentRange(fromDomainValue, toDomainValue));
841    }
842
843    /**
844     * Adds a segment as an exception. An exception segment is defined as a
845     * segment to exclude from what would otherwise be considered a valid
846     * segment of the timeline.  An exception segment can not be contained
847     * inside an already excluded segment.  If so, no action will occur (the
848     * proposed exception segment will be discarded).
849     * <p>
850     * The segment is identified by a Date into any part of the segment.
851     *
852     * @param exceptionDate  Date into the segment to exclude.
853     */
854    public void addException(Date exceptionDate) {
855        addException(getTime(exceptionDate));
856        //addException(exceptionDate.getTime());
857    }
858
859    /**
860     * Adds a list of dates as segment exceptions. Each exception segment is
861     * defined as a segment to exclude from what would otherwise be considered
862     * a valid segment of the timeline.  An exception segment can not be
863     * contained inside an already excluded segment.  If so, no action will
864     * occur (the proposed exception segment will be discarded).
865     * <p>
866     * The segment is identified by a Date into any part of the segment.
867     *
868     * @param exceptionList  List of Date objects that identify the segments to
869     *                       exclude.
870     */
871    public void addExceptions(List exceptionList) {
872        for (Iterator iter = exceptionList.iterator(); iter.hasNext();) {
873            addException((Date) iter.next());
874        }
875    }
876
877    /**
878     * Adds a segment as an exception. An exception segment is defined as a
879     * segment to exclude from what would otherwise be considered a valid
880     * segment of the timeline.  An exception segment can not be contained
881     * inside an already excluded segment.  This is verified inside this
882     * method, and if so, no action will occur (the proposed exception segment
883     * will be discarded).
884     *
885     * @param segment  the segment to exclude.
886     */
887    private void addException(Segment segment) {
888         if (segment.inIncludeSegments()) {
889             int p = binarySearchExceptionSegments(segment);
890             this.exceptionSegments.add(-(p + 1), segment);
891         }
892    }
893
894    /**
895     * Adds a segment relative to the baseTimeline as an exception. Because a
896     * base segment is normally larger than our segments, this may add one or
897     * more segment ranges to the exception list.
898     * <p>
899     * An exception segment is defined as a segment
900     * to exclude from what would otherwise be considered a valid segment of
901     * the timeline.  An exception segment can not be contained inside an
902     * already excluded segment.  If so, no action will occur (the proposed
903     * exception segment will be discarded).
904     * <p>
905     * The segment is identified by a domainValue into any part of the
906     * baseTimeline segment.
907     *
908     * @param domainValue  domain value to teat as a baseTimeline exception.
909     */
910    public void addBaseTimelineException(long domainValue) {
911
912        Segment baseSegment = this.baseTimeline.getSegment(domainValue);
913        if (baseSegment.inIncludeSegments()) {
914
915            // cycle through all the segments contained in the BaseTimeline
916            // exception segment
917            Segment segment = getSegment(baseSegment.getSegmentStart());
918            while (segment.getSegmentStart() <= baseSegment.getSegmentEnd()) {
919                if (segment.inIncludeSegments()) {
920
921                    // find all consecutive included segments
922                    long fromDomainValue = segment.getSegmentStart();
923                    long toDomainValue;
924                    do {
925                        toDomainValue = segment.getSegmentEnd();
926                        segment.inc();
927                    }
928                    while (segment.inIncludeSegments());
929
930                    // add the interval as an exception
931                    addException(fromDomainValue, toDomainValue);
932
933                }
934                else {
935                    // this is not one of our included segment, skip it
936                    segment.inc();
937                }
938            }
939        }
940    }
941
942    /**
943     * Adds a segment relative to the baseTimeline as an exception. An
944     * exception segment is defined as a segment to exclude from what would
945     * otherwise be considered a valid segment of the timeline.  An exception
946     * segment can not be contained inside an already excluded segment. If so,
947     * no action will occure (the proposed exception segment will be discarded).
948     * <p>
949     * The segment is identified by a domainValue into any part of the segment.
950     * Therefore the segmentStart <= domainValue <= segmentEnd.
951     *
952     * @param date  date domain value to treat as a baseTimeline exception
953     */
954    public void addBaseTimelineException(Date date) {
955        addBaseTimelineException(getTime(date));
956    }
957
958    /**
959     * Adds all excluded segments from the BaseTimeline as exceptions to our
960     * timeline. This allows us to combine two timelines for more complex
961     * calculations.
962     *
963     * @param fromBaseDomainValue Start of the range where exclusions will be
964     *                            extracted.
965     * @param toBaseDomainValue End of the range to process.
966     */
967    public void addBaseTimelineExclusions(long fromBaseDomainValue,
968                                          long toBaseDomainValue) {
969
970        // find first excluded base segment starting fromDomainValue
971        Segment baseSegment = this.baseTimeline.getSegment(fromBaseDomainValue);
972        while (baseSegment.getSegmentStart() <= toBaseDomainValue
973               && !baseSegment.inExcludeSegments()) {
974
975            baseSegment.inc();
976
977        }
978
979        // cycle over all the base segments groups in the range
980        while (baseSegment.getSegmentStart() <= toBaseDomainValue) {
981
982            long baseExclusionRangeEnd = baseSegment.getSegmentStart()
983                 + this.baseTimeline.getSegmentsExcluded()
984                 * this.baseTimeline.getSegmentSize() - 1;
985
986            // cycle through all the segments contained in the base exclusion
987            // area
988            Segment segment = getSegment(baseSegment.getSegmentStart());
989            while (segment.getSegmentStart() <= baseExclusionRangeEnd) {
990                if (segment.inIncludeSegments()) {
991
992                    // find all consecutive included segments
993                    long fromDomainValue = segment.getSegmentStart();
994                    long toDomainValue;
995                    do {
996                        toDomainValue = segment.getSegmentEnd();
997                        segment.inc();
998                    }
999                    while (segment.inIncludeSegments());
1000
1001                    // add the interval as an exception
1002                    addException(new BaseTimelineSegmentRange(
1003                            fromDomainValue, toDomainValue));
1004                }
1005                else {
1006                    // this is not one of our included segment, skip it
1007                    segment.inc();
1008                }
1009            }
1010
1011            // go to next base segment group
1012            baseSegment.inc(this.baseTimeline.getGroupSegmentCount());
1013        }
1014    }
1015
1016    /**
1017     * Returns the number of exception segments wholly contained in the
1018     * (fromDomainValue, toDomainValue) interval.
1019     *
1020     * @param fromMillisecond  the beginning of the interval.
1021     * @param toMillisecond  the end of the interval.
1022     *
1023     * @return Number of exception segments contained in the interval.
1024     */
1025    public long getExceptionSegmentCount(long fromMillisecond,
1026                                         long toMillisecond) {
1027        if (toMillisecond < fromMillisecond) {
1028            return (0);
1029        }
1030
1031        int n = 0;
1032        for (Iterator iter = this.exceptionSegments.iterator();
1033             iter.hasNext();) {
1034            Segment segment = (Segment) iter.next();
1035            Segment intersection = segment.intersect(fromMillisecond,
1036                    toMillisecond);
1037            if (intersection != null) {
1038                n += intersection.getSegmentCount();
1039            }
1040        }
1041
1042        return (n);
1043    }
1044
1045    /**
1046     * Returns a segment that contains a domainValue. If the domainValue is
1047     * not contained in the timeline (because it is not contained in the
1048     * baseTimeline), a Segment that contains
1049     * <code>index + segmentSize*m</code> will be returned for the smallest
1050     * <code>m</code> possible.
1051     *
1052     * @param millisecond  index into the segment
1053     *
1054     * @return A Segment that contains index, or the next possible Segment.
1055     */
1056    public Segment getSegment(long millisecond) {
1057        return new Segment(millisecond);
1058    }
1059
1060    /**
1061     * Returns a segment that contains a date. For accurate calculations,
1062     * the calendar should use TIME_ZONE for its calculation (or any other
1063     * similar time zone).
1064     *
1065     * If the date is not contained in the timeline (because it is not
1066     * contained in the baseTimeline), a Segment that contains
1067     * <code>date + segmentSize*m</code> will be returned for the smallest
1068     * <code>m</code> possible.
1069     *
1070     * @param date date into the segment
1071     *
1072     * @return A Segment that contains date, or the next possible Segment.
1073     */
1074    public Segment getSegment(Date date) {
1075        return (getSegment(getTime(date)));
1076    }
1077
1078    /**
1079     * Convenient method to test equality in two objects, taking into account
1080     * nulls.
1081     *
1082     * @param o first object to compare
1083     * @param p second object to compare
1084     *
1085     * @return <code>true</code> if both objects are equal or both
1086     *         <code>null</code>, <code>false</code> otherwise.
1087     */
1088    private boolean equals(Object o, Object p) {
1089        return (o == p || ((o != null) && o.equals(p)));
1090    }
1091
1092    /**
1093     * Returns true if we are equal to the parameter
1094     *
1095     * @param o Object to verify with us
1096     *
1097     * @return <code>true</code> or <code>false</code>
1098     */
1099    public boolean equals(Object o) {
1100        if (o instanceof SegmentedTimeline) {
1101            SegmentedTimeline other = (SegmentedTimeline) o;
1102
1103            boolean b0 = (this.segmentSize == other.getSegmentSize());
1104            boolean b1 = (this.segmentsIncluded == other.getSegmentsIncluded());
1105            boolean b2 = (this.segmentsExcluded == other.getSegmentsExcluded());
1106            boolean b3 = (this.startTime == other.getStartTime());
1107            boolean b4 = equals(this.exceptionSegments,
1108                    other.getExceptionSegments());
1109            return b0 && b1 && b2 && b3 && b4;
1110        }
1111        else {
1112            return (false);
1113        }
1114    }
1115
1116    /**
1117     * Returns a hash code for this object.
1118     *
1119     * @return A hash code.
1120     */
1121    public int hashCode() {
1122        int result = 19;
1123        result = 37 * result
1124                 + (int) (this.segmentSize ^ (this.segmentSize >>> 32));
1125        result = 37 * result + (int) (this.startTime ^ (this.startTime >>> 32));
1126        return result;
1127    }
1128
1129    /**
1130     * Preforms a binary serach in the exceptionSegments sorted array. This
1131     * array can contain Segments or SegmentRange objects.
1132     *
1133     * @param  segment the key to be searched for.
1134     *
1135     * @return index of the search segment, if it is contained in the list;
1136     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1137     *         <i>insertion point</i> is defined as the point at which the
1138     *         segment would be inserted into the list: the index of the first
1139     *         element greater than the key, or <tt>list.size()</tt>, if all
1140     *         elements in the list are less than the specified segment.  Note
1141     *         that this guarantees that the return value will be &gt;= 0 if
1142     *         and only if the key is found.
1143     */
1144    private int binarySearchExceptionSegments(Segment segment) {
1145        int low = 0;
1146        int high = this.exceptionSegments.size() - 1;
1147
1148        while (low <= high) {
1149            int mid = (low + high) / 2;
1150            Segment midSegment = (Segment) this.exceptionSegments.get(mid);
1151
1152            // first test for equality (contains or contained)
1153            if (segment.contains(midSegment) || midSegment.contains(segment)) {
1154                return mid;
1155            }
1156
1157            if (midSegment.before(segment)) {
1158                low = mid + 1;
1159            }
1160            else if (midSegment.after(segment)) {
1161                high = mid - 1;
1162            }
1163            else {
1164                throw new IllegalStateException("Invalid condition.");
1165            }
1166        }
1167        return -(low + 1);  // key not found
1168    }
1169
1170    /**
1171     * Special method that handles conversion between the Default Time Zone and
1172     * a UTC time zone with no DST. This is needed so all days have the same
1173     * size. This method is the prefered way of converting a Data into
1174     * milliseconds for usage in this class.
1175     *
1176     * @param date Date to convert to long.
1177     *
1178     * @return The milliseconds.
1179     */
1180    public long getTime(Date date) {
1181        long result = date.getTime();
1182        if (this.adjustForDaylightSaving) {
1183            this.workingCalendar.setTime(date);
1184            this.workingCalendarNoDST.set(
1185                    this.workingCalendar.get(Calendar.YEAR),
1186                    this.workingCalendar.get(Calendar.MONTH),
1187                    this.workingCalendar.get(Calendar.DATE),
1188                    this.workingCalendar.get(Calendar.HOUR_OF_DAY),
1189                    this.workingCalendar.get(Calendar.MINUTE),
1190                    this.workingCalendar.get(Calendar.SECOND));
1191            this.workingCalendarNoDST.set(Calendar.MILLISECOND,
1192                    this.workingCalendar.get(Calendar.MILLISECOND));
1193            Date revisedDate = this.workingCalendarNoDST.getTime();
1194            result = revisedDate.getTime();
1195        }
1196
1197        return result;
1198    }
1199
1200    /**
1201     * Converts a millisecond value into a {@link Date} object.
1202     *
1203     * @param value  the millisecond value.
1204     *
1205     * @return The date.
1206     */
1207    public Date getDate(long value) {
1208        this.workingCalendarNoDST.setTime(new Date(value));
1209        return (this.workingCalendarNoDST.getTime());
1210    }
1211
1212    /**
1213     * Returns a clone of the timeline.
1214     *
1215     * @return A clone.
1216     *
1217     * @throws CloneNotSupportedException ??.
1218     */
1219    public Object clone() throws CloneNotSupportedException {
1220        SegmentedTimeline clone = (SegmentedTimeline) super.clone();
1221        return clone;
1222    }
1223
1224    /**
1225     * Internal class to represent a valid segment for this timeline. A segment
1226     * is valid on a timeline if it is part of its included, excluded or
1227     * exception segments.
1228     * <p>
1229     * Each segment will know its segment number, segmentStart, segmentEnd and
1230     * index inside the segment.
1231     */
1232    public class Segment implements Comparable, Cloneable, Serializable {
1233
1234        /** The segment number. */
1235        protected long segmentNumber;
1236
1237        /** The segment start. */
1238        protected long segmentStart;
1239
1240        /** The segment end. */
1241        protected long segmentEnd;
1242
1243        /** A reference point within the segment. */
1244        protected long millisecond;
1245
1246        /**
1247         * Protected constructor only used by sub-classes.
1248         */
1249        protected Segment() {
1250            // empty
1251        }
1252
1253        /**
1254         * Creates a segment for a given point in time.
1255         *
1256         * @param millisecond  the millisecond (as encoded by java.util.Date).
1257         */
1258        protected Segment(long millisecond) {
1259            this.segmentNumber = calculateSegmentNumber(millisecond);
1260            this.segmentStart = SegmentedTimeline.this.startTime
1261                + this.segmentNumber * SegmentedTimeline.this.segmentSize;
1262            this.segmentEnd
1263                = this.segmentStart + SegmentedTimeline.this.segmentSize - 1;
1264            this.millisecond = millisecond;
1265        }
1266
1267        /**
1268         * Calculates the segment number for a given millisecond.
1269         *
1270         * @param millis  the millisecond (as encoded by java.util.Date).
1271         *
1272         * @return The segment number.
1273         */
1274        public long calculateSegmentNumber(long millis) {
1275            if (millis >= SegmentedTimeline.this.startTime) {
1276                return (millis - SegmentedTimeline.this.startTime)
1277                    / SegmentedTimeline.this.segmentSize;
1278            }
1279            else {
1280                return ((millis - SegmentedTimeline.this.startTime)
1281                    / SegmentedTimeline.this.segmentSize) - 1;
1282            }
1283        }
1284
1285        /**
1286         * Returns the segment number of this segment. Segments start at 0.
1287         *
1288         * @return The segment number.
1289         */
1290        public long getSegmentNumber() {
1291            return this.segmentNumber;
1292        }
1293
1294        /**
1295         * Returns always one (the number of segments contained in this
1296         * segment).
1297         *
1298         * @return The segment count (always 1 for this class).
1299         */
1300        public long getSegmentCount() {
1301            return 1;
1302        }
1303
1304        /**
1305         * Gets the start of this segment in ms.
1306         *
1307         * @return The segment start.
1308         */
1309        public long getSegmentStart() {
1310            return this.segmentStart;
1311        }
1312
1313        /**
1314         * Gets the end of this segment in ms.
1315         *
1316         * @return The segment end.
1317         */
1318        public long getSegmentEnd() {
1319            return this.segmentEnd;
1320        }
1321
1322        /**
1323         * Returns the millisecond used to reference this segment (always
1324         * between the segmentStart and segmentEnd).
1325         *
1326         * @return The millisecond.
1327         */
1328        public long getMillisecond() {
1329            return this.millisecond;
1330        }
1331
1332        /**
1333         * Returns a {@link java.util.Date} that represents the reference point
1334         * for this segment.
1335         *
1336         * @return The date.
1337         */
1338        public Date getDate() {
1339            return SegmentedTimeline.this.getDate(this.millisecond);
1340        }
1341
1342        /**
1343         * Returns true if a particular millisecond is contained in this
1344         * segment.
1345         *
1346         * @param millis  the millisecond to verify.
1347         *
1348         * @return <code>true</code> if the millisecond is contained in the
1349         *         segment.
1350         */
1351        public boolean contains(long millis) {
1352            return (this.segmentStart <= millis && millis <= this.segmentEnd);
1353        }
1354
1355        /**
1356         * Returns <code>true</code> if an interval is contained in this
1357         * segment.
1358         *
1359         * @param from  the start of the interval.
1360         * @param to  the end of the interval.
1361         *
1362         * @return <code>true</code> if the interval is contained in the
1363         *         segment.
1364         */
1365        public boolean contains(long from, long to) {
1366            return (this.segmentStart <= from && to <= this.segmentEnd);
1367        }
1368
1369        /**
1370         * Returns <code>true</code> if a segment is contained in this segment.
1371         *
1372         * @param segment  the segment to test for inclusion
1373         *
1374         * @return <code>true</code> if the segment is contained in this
1375         *         segment.
1376         */
1377        public boolean contains(Segment segment) {
1378            return contains(segment.getSegmentStart(), segment.getSegmentEnd());
1379        }
1380
1381        /**
1382         * Returns <code>true</code> if this segment is contained in an
1383         * interval.
1384         *
1385         * @param from  the start of the interval.
1386         * @param to  the end of the interval.
1387         *
1388         * @return <code>true</code> if this segment is contained in the
1389         *         interval.
1390         */
1391        public boolean contained(long from, long to) {
1392            return (from <= this.segmentStart && this.segmentEnd <= to);
1393        }
1394
1395        /**
1396         * Returns a segment that is the intersection of this segment and the
1397         * interval.
1398         *
1399         * @param from  the start of the interval.
1400         * @param to  the end of the interval.
1401         *
1402         * @return A segment.
1403         */
1404        public Segment intersect(long from, long to) {
1405            if (from <= this.segmentStart && this.segmentEnd <= to) {
1406                return this;
1407            }
1408            else {
1409                return null;
1410            }
1411        }
1412
1413        /**
1414         * Returns <code>true</code> if this segment is wholly before another
1415         * segment.
1416         *
1417         * @param other  the other segment.
1418         *
1419         * @return A boolean.
1420         */
1421        public boolean before(Segment other) {
1422            return (this.segmentEnd < other.getSegmentStart());
1423        }
1424
1425        /**
1426         * Returns <code>true</code> if this segment is wholly after another
1427         * segment.
1428         *
1429         * @param other  the other segment.
1430         *
1431         * @return A boolean.
1432         */
1433        public boolean after(Segment other) {
1434            return (this.segmentStart > other.getSegmentEnd());
1435        }
1436
1437        /**
1438         * Tests an object (usually another <code>Segment</code>) for equality
1439         * with this segment.
1440         *
1441         * @param object The other segment to compare with us
1442         *
1443         * @return <code>true</code> if we are the same segment
1444         */
1445        public boolean equals(Object object) {
1446            if (object instanceof Segment) {
1447                Segment other = (Segment) object;
1448                return (this.segmentNumber == other.getSegmentNumber()
1449                        && this.segmentStart == other.getSegmentStart()
1450                        && this.segmentEnd == other.getSegmentEnd()
1451                        && this.millisecond == other.getMillisecond());
1452            }
1453            else {
1454                return false;
1455            }
1456        }
1457
1458        /**
1459         * Returns a copy of ourselves or <code>null</code> if there was an
1460         * exception during cloning.
1461         *
1462         * @return A copy of this segment.
1463         */
1464        public Segment copy() {
1465            try {
1466                return (Segment) this.clone();
1467            }
1468            catch (CloneNotSupportedException e) {
1469                return null;
1470            }
1471        }
1472
1473        /**
1474         * Will compare this Segment with another Segment (from Comparable
1475         * interface).
1476         *
1477         * @param object The other Segment to compare with
1478         *
1479         * @return -1: this < object, 0: this.equal(object) and
1480         *         +1: this > object
1481         */
1482        public int compareTo(Object object) {
1483            Segment other = (Segment) object;
1484            if (this.before(other)) {
1485                return -1;
1486            }
1487            else if (this.after(other)) {
1488                return +1;
1489            }
1490            else {
1491                return 0;
1492            }
1493        }
1494
1495        /**
1496         * Returns true if we are an included segment and we are not an
1497         * exception.
1498         *
1499         * @return <code>true</code> or <code>false</code>.
1500         */
1501        public boolean inIncludeSegments() {
1502            if (getSegmentNumberRelativeToGroup()
1503                    < SegmentedTimeline.this.segmentsIncluded) {
1504                return !inExceptionSegments();
1505            }
1506            else {
1507                return false;
1508            }
1509        }
1510
1511        /**
1512         * Returns true if we are an excluded segment.
1513         *
1514         * @return <code>true</code> or <code>false</code>.
1515         */
1516        public boolean inExcludeSegments() {
1517            return getSegmentNumberRelativeToGroup()
1518                    >= SegmentedTimeline.this.segmentsIncluded;
1519        }
1520
1521        /**
1522         * Calculate the segment number relative to the segment group. This
1523         * will be a number between 0 and segmentsGroup-1. This value is
1524         * calculated from the segmentNumber. Special care is taken for
1525         * negative segmentNumbers.
1526         *
1527         * @return The segment number.
1528         */
1529        private long getSegmentNumberRelativeToGroup() {
1530            long p = (this.segmentNumber
1531                    % SegmentedTimeline.this.groupSegmentCount);
1532            if (p < 0) {
1533                p += SegmentedTimeline.this.groupSegmentCount;
1534            }
1535            return p;
1536        }
1537
1538        /**
1539         * Returns true if we are an exception segment. This is implemented via
1540         * a binary search on the exceptionSegments sorted list.
1541         *
1542         * If the segment is not listed as an exception in our list and we have
1543         * a baseTimeline, a check is performed to see if the segment is inside
1544         * an excluded segment from our base. If so, it is also considered an
1545         * exception.
1546         *
1547         * @return <code>true</code> if we are an exception segment.
1548         */
1549        public boolean inExceptionSegments() {
1550            return binarySearchExceptionSegments(this) >= 0;
1551        }
1552
1553        /**
1554         * Increments the internal attributes of this segment by a number of
1555         * segments.
1556         *
1557         * @param n Number of segments to increment.
1558         */
1559        public void inc(long n) {
1560            this.segmentNumber += n;
1561            long m = n * SegmentedTimeline.this.segmentSize;
1562            this.segmentStart += m;
1563            this.segmentEnd += m;
1564            this.millisecond += m;
1565        }
1566
1567        /**
1568         * Increments the internal attributes of this segment by one segment.
1569         * The exact time incremented is segmentSize.
1570         */
1571        public void inc() {
1572            inc(1);
1573        }
1574
1575        /**
1576         * Decrements the internal attributes of this segment by a number of
1577         * segments.
1578         *
1579         * @param n Number of segments to decrement.
1580         */
1581        public void dec(long n) {
1582            this.segmentNumber -= n;
1583            long m = n * SegmentedTimeline.this.segmentSize;
1584            this.segmentStart -= m;
1585            this.segmentEnd -= m;
1586            this.millisecond -= m;
1587        }
1588
1589        /**
1590         * Decrements the internal attributes of this segment by one segment.
1591         * The exact time decremented is segmentSize.
1592         */
1593        public void dec() {
1594            dec(1);
1595        }
1596
1597        /**
1598         * Moves the index of this segment to the beginning if the segment.
1599         */
1600        public void moveIndexToStart() {
1601            this.millisecond = this.segmentStart;
1602        }
1603
1604        /**
1605         * Moves the index of this segment to the end of the segment.
1606         */
1607        public void moveIndexToEnd() {
1608            this.millisecond = this.segmentEnd;
1609        }
1610
1611    }
1612
1613    /**
1614     * Private internal class to represent a range of segments. This class is
1615     * mainly used to store in one object a range of exception segments. This
1616     * optimizes certain timelines that use a small segment size (like an
1617     * intraday timeline) allowing them to express a day exception as one
1618     * SegmentRange instead of multi Segments.
1619     */
1620    protected class SegmentRange extends Segment {
1621
1622        /** The number of segments in the range. */
1623        private long segmentCount;
1624
1625        /**
1626         * Creates a SegmentRange between a start and end domain values.
1627         *
1628         * @param fromMillisecond  start of the range
1629         * @param toMillisecond  end of the range
1630         */
1631        public SegmentRange(long fromMillisecond, long toMillisecond) {
1632
1633            Segment start = getSegment(fromMillisecond);
1634            Segment end = getSegment(toMillisecond);
1635//            if (start.getSegmentStart() != fromMillisecond
1636//                || end.getSegmentEnd() != toMillisecond) {
1637//                throw new IllegalArgumentException("Invalid Segment Range ["
1638//                    + fromMillisecond + "," + toMillisecond + "]");
1639//            }
1640
1641            this.millisecond = fromMillisecond;
1642            this.segmentNumber = calculateSegmentNumber(fromMillisecond);
1643            this.segmentStart = start.segmentStart;
1644            this.segmentEnd = end.segmentEnd;
1645            this.segmentCount
1646                = (end.getSegmentNumber() - start.getSegmentNumber() + 1);
1647        }
1648
1649        /**
1650         * Returns the number of segments contained in this range.
1651         *
1652         * @return The segment count.
1653         */
1654        public long getSegmentCount() {
1655            return this.segmentCount;
1656        }
1657
1658        /**
1659         * Returns a segment that is the intersection of this segment and the
1660         * interval.
1661         *
1662         * @param from  the start of the interval.
1663         * @param to  the end of the interval.
1664         *
1665         * @return The intersection.
1666         */
1667        public Segment intersect(long from, long to) {
1668
1669            // Segment fromSegment = getSegment(from);
1670            // fromSegment.inc();
1671            // Segment toSegment = getSegment(to);
1672            // toSegment.dec();
1673            long start = Math.max(from, this.segmentStart);
1674            long end = Math.min(to, this.segmentEnd);
1675            // long start = Math.max(
1676            //     fromSegment.getSegmentStart(), this.segmentStart
1677            // );
1678            // long end = Math.min(toSegment.getSegmentEnd(), this.segmentEnd);
1679            if (start <= end) {
1680                return new SegmentRange(start, end);
1681            }
1682            else {
1683                return null;
1684            }
1685        }
1686
1687        /**
1688         * Returns true if all Segments of this SegmentRenge are an included
1689         * segment and are not an exception.
1690         *
1691         * @return <code>true</code> or </code>false</code>.
1692         */
1693        public boolean inIncludeSegments() {
1694            for (Segment segment = getSegment(this.segmentStart);
1695                segment.getSegmentStart() < this.segmentEnd;
1696                segment.inc()) {
1697                if (!segment.inIncludeSegments()) {
1698                    return (false);
1699                }
1700            }
1701            return true;
1702        }
1703
1704        /**
1705         * Returns true if we are an excluded segment.
1706         *
1707         * @return <code>true</code> or </code>false</code>.
1708         */
1709        public boolean inExcludeSegments() {
1710            for (Segment segment = getSegment(this.segmentStart);
1711                segment.getSegmentStart() < this.segmentEnd;
1712                segment.inc()) {
1713                if (!segment.inExceptionSegments()) {
1714                    return (false);
1715                }
1716            }
1717            return true;
1718        }
1719
1720        /**
1721         * Not implemented for SegmentRange. Always throws
1722         * IllegalArgumentException.
1723         *
1724         * @param n Number of segments to increment.
1725         */
1726        public void inc(long n) {
1727            throw new IllegalArgumentException(
1728                    "Not implemented in SegmentRange");
1729        }
1730
1731    }
1732
1733    /**
1734     * Special <code>SegmentRange</code> that came from the BaseTimeline.
1735     */
1736    protected class BaseTimelineSegmentRange extends SegmentRange {
1737
1738        /**
1739         * Constructor.
1740         *
1741         * @param fromDomainValue  the start value.
1742         * @param toDomainValue  the end value.
1743         */
1744        public BaseTimelineSegmentRange(long fromDomainValue,
1745                                        long toDomainValue) {
1746            super(fromDomainValue, toDomainValue);
1747        }
1748
1749    }
1750
1751}