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