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