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    
051    package org.jfree.chart.axis;
052    
053    import java.io.Serializable;
054    import java.util.ArrayList;
055    import java.util.Calendar;
056    import java.util.Collections;
057    import java.util.Date;
058    import java.util.GregorianCalendar;
059    import java.util.Iterator;
060    import java.util.List;
061    import java.util.Locale;
062    import java.util.SimpleTimeZone;
063    import 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     */
167    public 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    }