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