SegmentedTimeline


1   /* ===========================================================
2    * JFreeChart : a free chart library for the Java(tm) platform
3    * ===========================================================
4    *
5    * (C) Copyright 2000-2005, by Object Refinery Limited and Contributors.
6    *
7    * Project Info:  http://www.jfree.org/jfreechart/index.html
8    *
9    * This library is free software; you can redistribute it and/or modify it 
10   * under the terms of the GNU Lesser General Public License as published by 
11   * the Free Software Foundation; either version 2.1 of the License, or 
12   * (at your option) any later version.
13   *
14   * This library is distributed in the hope that it will be useful, but 
15   * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
16   * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
17   * License for more details.
18   *
19   * You should have received a copy of the GNU Lesser General Public License 
20   * along with this library; if not, write to the Free Software Foundation, 
21   * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
22   *
23   * [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
24   * in the United States and other countries.]
25   *
26   * -----------------------
27   * SegmentedTimeline.java
28   * -----------------------
29   * (C) Copyright 2003-2005, by Bill Kelemen and Contributors.
30   *
31   * Original Author:  Bill Kelemen;
32   * Contributor(s):   David Gilbert (for Object Refinery Limited);
33   *
34   * $Id: SegmentedTimeline.java,v 1.9 2005/05/19 13:58:11 mungady Exp $
35   *
36   * Changes
37   * -------
38   * 23-May-2003 : Version 1 (BK);
39   * 15-Aug-2003 : Implemented Cloneable (DG);
40   * 01-Jun-2004 : Modified to compile with JDK 1.2.2 (DG);
41   * 30-Sep-2004 : Replaced getTime().getTime() with getTimeInMillis() (DG);
42   * 04-Nov-2004 : Reverted change of 30-Sep-2004, won't work with JDK 1.3 (DG);
43   * 11-Jan-2005 : Removed deprecated code in preparation for 1.0.0 release (DG);
44   * 
45   */
46  
47  package org.jfree.chart.axis;
48  
49  import java.io.Serializable  ;
50  import java.util.ArrayList  ;
51  import java.util.Calendar  ;
52  import java.util.Collections  ;
53  import java.util.Date  ;
54  import java.util.GregorianCalendar  ;
55  import java.util.Iterator  ;
56  import java.util.List  ;
57  import java.util.SimpleTimeZone  ;
58  import java.util.TimeZone  ;
59  
60  /**
61   * A {@link Timeline} that implements a "segmented" timeline with included, 
62   * excluded and exception segments.
63   * <P>
64   * A Timeline will present a series of values to be used for an axis. Each
65   * Timeline must provide transformation methods between domain values and
66   * timeline values.
67   * <P>
68   * A timeline can be used as parameter to a 
69   * {@link org.jfree.chart.axis.DateAxis} to define the values that this axis 
70   * supports. This class implements a timeline formed by segments of equal 
71   * length (ex. days, hours, minutes) where some segments can be included in the
72   * timeline and others excluded. Therefore timelines like "working days" or
73   * "working hours" can be created where non-working days or non-working hours 
74   * respectively can be removed from the timeline, and therefore from the axis.
75   * This creates a smooth plot with equal separation between all included 
76   * segments.
77   * <P>
78   * Because Timelines were created mainly for Date related axis, values are
79   * represented as longs instead of doubles. In this case, the domain value is
80   * just the number of milliseconds since January 1, 1970, 00:00:00 GMT as 
81   * defined by the getTime() method of {@link java.util.Date}.
82   * <P>
83   * In this class, a segment is defined as a unit of time of fixed length. 
84   * Examples of segments are: days, hours, minutes, etc. The size of a segment 
85   * is defined as the number of milliseconds in the segment. Some useful segment
86   * sizes are defined as constants in this class: DAY_SEGMENT_SIZE, 
87   * HOUR_SEGMENT_SIZE, FIFTEEN_MINUTE_SEGMENT_SIZE and MINUTE_SEGMENT_SIZE.
88   * <P>
89   * Segments are group together to form a Segment Group. Each Segment Group will
90   * contain a number of Segments included and a number of Segments excluded. This
91   * Segment Group structure will repeat for the whole timeline.
92   * <P>
93   * For example, a working days SegmentedTimeline would be formed by a group of
94   * 7 daily segments, where there are 5 included (Monday through Friday) and 2
95   * excluded (Saturday and Sunday) segments.
96   * <P>
97   * Following is a diagram that explains the major attributes that define a 
98   * segment.  Each box is one segment and must be of fixed length (ms, second, 
99   * hour, day, etc).
100  * <p>
101  * <pre>
102  * start time
103  *   |
104  *   v
105  *   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...
106  * +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+...
107  * |  |  |  |  |  |EE|EE|  |  |  |  |  |EE|EE|  |  |  |  |  |EE|EE|
108  * +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+...
109  *  \____________/ \___/            \_/
110  *        \/         |               |
111  *     included   excluded        segment
112  *     segments   segments         size
113  *  \_________  _______/
114  *            \/
115  *       segment group
116  * </pre>
117  * Legend:<br>
118  * &lt;space&gt; = Included segment<br>
119  * EE      = Excluded segments in the base timeline<br>
120  * <p>
121  * In the example, the following segment attributes are presented:
122  * <ul>
123  * <li>segment size: the size of each segment in ms.
124  * <li>start time: the start of the first segment of the first segment group to
125  *     consider.
126  * <li>included segments: the number of segments to include in the group.
127  * <li>excluded segments: the number of segments to exclude in the group.
128  * </ul>
129  * <p>
130  * Exception Segments are allowed. These exception segments are defined as
131  * segments that would have been in the included segments of the Segment Group,
132  * but should be excluded for special reasons. In the previous working days
133  * SegmentedTimeline example, holidays would be considered exceptions.
134  * <P>
135  * Additionally the <code>startTime</code>, or start of the first Segment of 
136  * the smallest segment group needs to be defined. This startTime could be 
137  * relative to January 1, 1970, 00:00:00 GMT or any other date. This creates a 
138  * point of reference to start counting Segment Groups. For example, for the 
139  * working days SegmentedTimeline, the <code>startTime</code> could be 
140  * 00:00:00 GMT of the first Monday after January 1, 1970. In this class, the 
141  * constant FIRST_MONDAY_AFTER_1900 refers to a reference point of the first 
142  * Monday of the last century.
143  * <p>
144  * A SegmentedTimeline can include a baseTimeline. This combination of 
145  * timelines allows the creation of more complex timelines. For example, in 
146  * order to implement a SegmentedTimeline for an intraday stock trading 
147  * application, where the trading period is defined as 9:00 AM through 4:00 PM 
148  * Monday through Friday, two SegmentedTimelines are used. The first one (the 
149  * baseTimeline) would be a working day SegmentedTimeline (daily timeline 
150  * Monday through Friday). On top of this baseTimeline, a second one is defined
151  * that maps the 9:00 AM to 4:00 PM period. Because the baseTimeline defines a 
152  * timeline of Monday through Friday, the resulting (combined) timeline will 
153  * expose the period 9:00 AM through 4:00 PM only on Monday through Friday, 
154  * and will remove all other intermediate intervals.
155  * <P>
156  * Two factory methods newMondayThroughFridayTimeline() and
157  * newFifteenMinuteTimeline() are provided as examples to create special
158  * SegmentedTimelines.
159  *
160  * @see org.jfree.chart.axis.DateAxis
161  *
162  * @author Bill Kelemen
163  */
164 public class SegmentedTimeline implements Timeline, Cloneable  , Serializable   {
165 
166     /** For serialization. */
167     private static final long serialVersionUID = 1093779862539903110L;
168     
169     ////////////////////////////////////////////////////////////////////////////
170     // predetermined segments sizes
171     ////////////////////////////////////////////////////////////////////////////
172 
173     /** Defines a day segment size in ms. */
174     public static final long DAY_SEGMENT_SIZE = 24 * 60 * 60 * 1000;
175 
176     /** Defines a one hour segment size in ms. */
177     public static final long HOUR_SEGMENT_SIZE = 60 * 60 * 1000;
178 
179     /** Defines a 15-minute segment size in ms. */
180     public static final long FIFTEEN_MINUTE_SEGMENT_SIZE = 15 * 60 * 1000;
181 
182     /** Defines a one-minute segment size in ms. */
183     public static final long MINUTE_SEGMENT_SIZE = 60 * 1000;
184 
185     ////////////////////////////////////////////////////////////////////////////
186     // other constants
187     ////////////////////////////////////////////////////////////////////////////
188 
189     /**
190      * Utility constant that defines the startTime as the first monday after 
191      * 1/1/1970.  This should be used when creating a SegmentedTimeline for 
192      * Monday through Friday. See static block below for calculation of this 
193      * constant.
194      */
195     public static long FIRST_MONDAY_AFTER_1900;
196 
197     /**
198      * Utility TimeZone object that has no DST and an offset equal to the 
199      * default TimeZone. This allows easy arithmetic between days as each one 
200      * will have equal size.
201      */
202     public static TimeZone   NO_DST_TIME_ZONE;
203 
204     /**
205      * This is the default time zone where the application is running. See 
206      * getTime() below where we make use of certain transformations between 
207      * times in the default time zone and the no-dst time zone used for our 
208      * calculations.
209      */
210     public static TimeZone   DEFAULT_TIME_ZONE = TimeZone.getDefault();
211 
212     /**
213      * This will be a utility calendar that has no DST but is shifted relative 
214      * to the default time zone's offset.
215      */
216     private Calendar   workingCalendarNoDST 
217         = new GregorianCalendar  (NO_DST_TIME_ZONE);
218 
219     /**
220      * This will be a utility calendar that used the default time zone.
221      */
222     private Calendar   workingCalendar = Calendar.getInstance();
223 
224     ////////////////////////////////////////////////////////////////////////////
225     // private attributes
226     ////////////////////////////////////////////////////////////////////////////
227 
228     /** Segment size in ms. */
229     private long segmentSize;
230 
231     /** Number of consecutive segments to include in a segment group. */
232     private int segmentsIncluded;
233 
234     /** Number of consecutive segments to exclude in a segment group. */
235     private int segmentsExcluded;
236 
237     /** Number of segments in a group (segmentsIncluded + segmentsExcluded). */
238     private int groupSegmentCount;
239 
240     /** 
241      * Start of time reference from time zero (1/1/1970). 
242      * This is the start of segment #0. 
243      */
244     private long startTime;
245 
246     /** Consecutive ms in segmentsIncluded (segmentsIncluded * segmentSize). */
247     private long segmentsIncludedSize;
248 
249     /** Consecutive ms in segmentsExcluded (segmentsExcluded * segmentSize). */
250     private long segmentsExcludedSize;
251 
252     /** ms in a segment group (segmentsIncludedSize + segmentsExcludedSize). */
253     private long segmentsGroupSize;
254 
255     /**
256      * List of exception segments (exceptions segments that would otherwise be
257      * included based on the periodic (included, excluded) grouping).
258      */
259     private List   exceptionSegments = new ArrayList  ();
260 
261     /**
262      * This base timeline is used to specify exceptions at a higher level. For 
263      * example, if we are a intraday timeline and want to exclude holidays, 
264      * instead of having to exclude all intraday segments for the holiday, 
265      * segments from this base timeline can be excluded. This baseTimeline is 
266      * always optional and is only a convenience method.
267      * <p>
268      * Additionally, all excluded segments from this baseTimeline will be 
269      * considered exceptions at this level.
270      */
271     private SegmentedTimeline baseTimeline;
272 
273     /** A flag that controls whether or not to adjust for daylight saving. */
274     private boolean adjustForDaylightSaving = false;
275     
276     ////////////////////////////////////////////////////////////////////////////
277     // static block
278     ////////////////////////////////////////////////////////////////////////////
279 
280     static {
281         // make a time zone with no DST for our Calendar calculations
282         int offset = TimeZone.getDefault().getRawOffset();
283         NO_DST_TIME_ZONE = new SimpleTimeZone  (offset, "UTC-" + offset);
284         
285         // calculate midnight of first monday after 1/1/1900 relative to 
286         // current locale
287         Calendar   cal = new GregorianCalendar  (NO_DST_TIME_ZONE);
288         cal.set(1900, 0, 1, 0, 0, 0);
289         cal.set(Calendar.MILLISECOND, 0);
290         while (cal.get(Calendar.DAY_OF_WEEK) != Calendar.MONDAY) {
291             cal.add(Calendar.DATE, 1);
292         }
293         // FIRST_MONDAY_AFTER_1900 = cal.getTime().getTime();  
294         // preceding code won't work with JDK 1.3
295         FIRST_MONDAY_AFTER_1900 = cal.getTime().getTime();
296     }
297 
298     ////////////////////////////////////////////////////////////////////////////
299     // constructors and factory methods
300     ////////////////////////////////////////////////////////////////////////////
301 
302     /**
303      * Constructs a new segmented timeline, optionaly using another segmented
304      * timeline as its base. This chaining of SegmentedTimelines allows further
305      * segmentation into smaller timelines.
306      *
307      * If a base
308      *
309      * @param segmentSize the size of a segment in ms. This time unit will be
310      *        used to compute the included and excluded segments of the 
311      *        timeline.
312      * @param segmentsIncluded Number of consecutive segments to include.
313      * @param segmentsExcluded Number of consecutive segments to exclude.
314      */
315     public SegmentedTimeline(long segmentSize,
316                              int segmentsIncluded,
317                              int segmentsExcluded) {
318 
319         this.segmentSize = segmentSize;
320         this.segmentsIncluded = segmentsIncluded;
321         this.segmentsExcluded = segmentsExcluded;
322 
323         this.groupSegmentCount = this.segmentsIncluded + this.segmentsExcluded;
324         this.segmentsIncludedSize = this.segmentsIncluded * this.segmentSize;
325         this.segmentsExcludedSize = this.segmentsExcluded * this.segmentSize;
326         this.segmentsGroupSize = this.segmentsIncludedSize 
327                                  + this.segmentsExcludedSize;
328 
329     }
330 
331     /**
332      * Factory method to create a Monday through Friday SegmentedTimeline.
333      * <P>
334      * The <code>startTime</code> of the resulting timeline will be midnight 
335      * of the first Monday after 1/1/1900.
336      *
337      * @return A fully initialized SegmentedTimeline.
338      */
339     public static SegmentedTimeline newMondayThroughFridayTimeline() {
340         SegmentedTimeline timeline 
341             = new SegmentedTimeline(DAY_SEGMENT_SIZE, 5, 2);
342         timeline.setStartTime(FIRST_MONDAY_AFTER_1900);
343         return timeline;
344     }
345 
346     /**
347      * Factory method to create a 15-min, 9:00 AM thought 4:00 PM, Monday 
348      * through Friday SegmentedTimeline.
349      * <P>
350      * This timeline uses a segmentSize of FIFTEEN_MIN_SEGMENT_SIZE. The 
351      * segment group is defined as 28 included segments (9:00 AM through 
352      * 4:00 PM) and 68 excluded segments (4:00 PM through 9:00 AM the next day).
353      * <P>
354      * In order to exclude Saturdays and Sundays it uses a baseTimeline that 
355      * only includes Monday through Friday days.
356      * <P>
357      * The <code>startTime</code> of the resulting timeline will be 9:00 AM 
358      * after the startTime of the baseTimeline. This will correspond to 9:00 AM
359      * of the first Monday after 1/1/1900.
360      *
361      * @return A fully initialized SegmentedTimeline.
362      */
363     public static SegmentedTimeline newFifteenMinuteTimeline() {
364         SegmentedTimeline timeline 
365             = new SegmentedTimeline(FIFTEEN_MINUTE_SEGMENT_SIZE, 28, 68);
366         timeline.setStartTime(
367             FIRST_MONDAY_AFTER_1900 + 36 * timeline.getSegmentSize()
368         );
369         timeline.setBaseTimeline(newMondayThroughFridayTimeline());
370         return timeline;
371     }
372     
373     /**
374      * Returns the flag that controls whether or not the daylight saving 
375      * adjustment is applied.
376      * 
377      * @return A boolean.
378      */
379     public boolean getAdjustForDaylightSaving() {
380         return this.adjustForDaylightSaving;   
381     }
382     
383     /**
384      * Sets the flag that controls whether or not the daylight saving adjustment
385      * is applied.
386      * 
387      * @param adjust  the flag.
388      */
389     public void setAdjustForDaylightSaving(boolean adjust) {
390         this.adjustForDaylightSaving = adjust;   
391     }
392 
393     ////////////////////////////////////////////////////////////////////////////
394     // operations
395     ////////////////////////////////////////////////////////////////////////////
396 
397     /**
398      * Sets the start time for the timeline. This is the beginning of segment 
399      * zero.
400      *
401      * @param millisecond  the start time (encoded as in java.util.Date).
402      */
403     public void setStartTime(long millisecond) {
404         this.startTime = millisecond;
405     }
406 
407     /**
408      * Returns the start time for the timeline. This is the beginning of 
409      * segment zero.
410      * 
411      * @return The start time.
412      */
413     public long getStartTime() {
414         return this.startTime;
415     }
416 
417     /**
418      * Returns the number of segments excluded per segment group.
419      * 
420      * @return The number of segments excluded.
421      */
422     public int getSegmentsExcluded() {
423         return this.segmentsExcluded;
424     }
425 
426     /**
427      * Returns the size in milliseconds of the segments excluded per segment 
428      * group.
429      * 
430      * @return The size in milliseconds.
431      */
432     public long getSegmentsExcludedSize() {
433         return this.segmentsExcludedSize;
434     }
435 
436     /**
437      * Returns the number of segments in a segment group. This will be equal to
438      * segments included plus segments excluded.
439      * 
440      * @return The number of segments.
441      */
442     public int getGroupSegmentCount() {
443         return this.groupSegmentCount;
444     }
445 
446     /**
447      * Returns the size in milliseconds of a segment group. This will be equal 
448      * to size of the segments included plus the size of the segments excluded.
449      * 
450      * @return The segment group size in milliseconds.
451      */
452     public long getSegmentsGroupSize() {
453         return this.segmentsGroupSize;
454     }
455 
456     /**
457      * Returns the number of segments included per segment group.
458      * 
459      * @return The number of segments.
460      */
461     public int getSegmentsIncluded() {
462         return this.segmentsIncluded;
463     }
464 
465     /**
466      * Returns the size in ms of the segments included per segment group.
467      * 
468      * @return The segment size in milliseconds.
469      */
470     public long getSegmentsIncludedSize() {
471         return this.segmentsIncludedSize;
472     }
473 
474     /**
475      * Returns the size of one segment in ms.
476      * 
477      * @return The segment size in milliseconds.
478      */
479     public long getSegmentSize() {
480         return this.segmentSize;
481     }
482 
483     /**
484      * Returns a list of all the exception segments. This list is not 
485      * modifiable.
486      * 
487      * @return The exception segments.
488      */
489     public List   getExceptionSegments() {
490         return Collections.unmodifiableList(this.exceptionSegments);
491     }
492 
493     /**
494      * Sets the exception segments list.
495      * 
496      * @param exceptionSegments  the exception segments.
497      */
498     public void setExceptionSegments(List   exceptionSegments) {
499         this.exceptionSegments = exceptionSegments;
500     }
501 
502     /**
503      * Returns our baseTimeline, or <code>null</code> if none.
504      * 
505      * @return The base timeline.
506      */
507     public SegmentedTimeline getBaseTimeline() {
508         return this.baseTimeline;
509     }
510 
511     /**
512      * Sets the base timeline.
513      * 
514      * @param baseTimeline  the timeline.
515      */
516     public void setBaseTimeline(SegmentedTimeline baseTimeline) {
517 
518         // verify that baseTimeline is compatible with us
519         if (baseTimeline != null) {
520             if (baseTimeline.getSegmentSize() < this.segmentSize) {
521                 throw new IllegalArgumentException  (
522                     "baseTimeline.getSegmentSize() is smaller than segmentSize"
523                 );
524             } 
525             else if (baseTimeline.getStartTime() > this.startTime) {
526                 throw new IllegalArgumentException  (
527                     "baseTimeline.getStartTime() is after startTime"
528                 );
529             } 
530             else if ((baseTimeline.getSegmentSize() % this.segmentSize) != 0) {
531                 throw new IllegalArgumentException  (
532                     "baseTimeline.getSegmentSize() is not multiple of "
533                     + "segmentSize"
534                 );
535             } 
536             else if (((this.startTime 
537                     - baseTimeline.getStartTime()) % this.segmentSize) != 0) {
538                 throw new IllegalArgumentException  (
539                     "baseTimeline is not aligned"
540                 );
541             }
542         }
543 
544         this.baseTimeline = baseTimeline;
545     }
546 
547     /**
548      * Translates a value relative to the domain value (all Dates) into a value
549      * relative to the segmented timeline. The values relative to the segmented
550      * timeline are all consecutives starting at zero at the startTime.
551      *
552      * @param millisecond  the millisecond (as encoded by java.util.Date).
553      * 
554      * @return The timeline value.
555      */
556     public long toTimelineValue(long millisecond) {
557   
558         long result;
559         long rawMilliseconds = millisecond - this.startTime;
560         long groupMilliseconds = rawMilliseconds % this.segmentsGroupSize;
561         long groupIndex = rawMilliseconds / this.segmentsGroupSize;
562         
563         if (groupMilliseconds >= this.segmentsIncludedSize) {
564             result = toTimelineValue(
565                 this.startTime + this.segmentsGroupSize * (groupIndex + 1)
566             );
567         } 
568         else {       
569             Segment segment = getSegment(millisecond);
570             if (segment.inExceptionSegments()) {
571                 result = toTimelineValue(segment.getSegmentEnd() + 1);
572             }      
573             else {
574                 long shiftedSegmentedValue = millisecond - this.startTime;
575                 long x = shiftedSegmentedValue % this.segmentsGroupSize;
576                 long y = shiftedSegmentedValue / this.segmentsGroupSize;
577 
578                 long wholeExceptionsBeforeDomainValue =
579                     getExceptionSegmentCount(this.startTime, millisecond - 1);
580 
581 //                long partialTimeInException = 0;
582 //                Segment ss = getSegment(millisecond);
583 //                if (ss.inExceptionSegments()) {
584 //                    partialTimeInException = millisecond 
585                 //     - ss.getSegmentStart();
586 //                }
587 
588                 if (x < this.segmentsIncludedSize) {
589                     result = this.segmentsIncludedSize * y 
590                              + x - wholeExceptionsBeforeDomainValue 
591                              * this.segmentSize;
592                              // - partialTimeInException;; 
593                 }
594                 else {
595                     result = this.segmentsIncludedSize * (y + 1) 
596                              - wholeExceptionsBeforeDomainValue 
597                              * this.segmentSize;
598                              // - partialTimeInException;
599                 }
600             }
601         }
602 
603         return result;
604     }
605 
606     /**
607      * Translates a date into a value relative to the segmented timeline. The 
608      * values relative to the segmented timeline are all consecutives starting 
609      * at zero at the startTime.
610      *
611      * @param date  date relative to the domain.
612      * 
613      * @return The timeline value (in milliseconds).
614      */
615     public long toTimelineValue(Date   date) {
616         return toTimelineValue(getTime(date));
617         //return toTimelineValue(dateDomainValue.getTime());
618     }
619 
620     /**
621      * Translates a value relative to the timeline into a millisecond.
622      *
623      * @param timelineValue  the timeline value (in milliseconds).
624      * 
625      * @return The domain value (in milliseconds).
626      */
627     public long toMillisecond(long timelineValue) {
628         
629         // calculate the result as if no exceptions
630         Segment result = new Segment(this.startTime + timelineValue 
631             + (timelineValue / this.segmentsIncludedSize) 
632             * this.segmentsExcludedSize);
633         
634         long lastIndex = this.startTime;
635 
636         // adjust result for any exceptions in the result calculated
637         while (lastIndex <= result.segmentStart) {
638 
639             // skip all whole exception segments in the range
640             long exceptionSegmentCount;
641             while ((exceptionSegmentCount = getExceptionSegmentCount(
642                  lastIndex, (result.millisecond / this.segmentSize) 
643                  * this.segmentSize - 1)) > 0
644             ) { 
645                 lastIndex = result.segmentStart;
646                 // move forward exceptionSegmentCount segments skipping 
647                 // excluded segments
648                 for (int i = 0; i < exceptionSegmentCount; i++) {
649                     do {
650                         result.inc();
651                     }
652                     while (result.inExcludeSegments());
653                 }
654             }
655             lastIndex = result.segmentStart;
656 
657             // skip exception or excluded segments we may fall on
658             while (result.inExceptionSegments() || result.inExcludeSegments()) {
659                 result.inc();
660                 lastIndex += this.segmentSize;
661             }
662 
663             lastIndex++;
664         }
665 
666         return getTimeFromLong(result.millisecond); 
667     }
668 
669     /**
670      * Converts a date/time value to take account of daylight savings time.
671      * 
672      * @param date  the milliseconds.
673      * 
674      * @return The milliseconds.
675      */
676     public long getTimeFromLong(long date) {
677         long result = date;
678         if (this.adjustForDaylightSaving) {
679             this.workingCalendarNoDST.setTime(new Date  (date));
680             this.workingCalendar.set(
681                 this.workingCalendarNoDST.get(Calendar.YEAR),
682                 this.workingCalendarNoDST.get(Calendar.MONTH),
683                 this.workingCalendarNoDST.get(Calendar.DATE),
684                 this.workingCalendarNoDST.get(Calendar.HOUR_OF_DAY),
685                 this.workingCalendarNoDST.get(Calendar.MINUTE),
686                 this.workingCalendarNoDST.get(Calendar.SECOND)
687             );
688             this.workingCalendar.set(
689                 Calendar.MILLISECOND, 
690                 this.workingCalendarNoDST.get(Calendar.MILLISECOND)
691             );
692             // result = this.workingCalendar.getTimeInMillis();  
693             // preceding code won't work with JDK 1.3
694             result = this.workingCalendar.getTime().getTime();
695         }
696         return result;
697     } 
698     
699     /**
700      * Returns <code>true</code> if a value is contained in the timeline.
701      * 
702      * @param millisecond  the value to verify.
703      * 
704      * @return <code>true</code> if value is contained in the timeline.
705      */
706     public boolean containsDomainValue(long millisecond) {
707         Segment segment = getSegment(millisecond);
708         return segment.inIncludeSegments();
709     }
710 
711     /**
712      * Returns <code>true</code> if a value is contained in the timeline.
713      * 
714      * @param date  date to verify
715      * 
716      * @return <code>true</code> if value is contained in the timeline
717      */
718     public boolean containsDomainValue(Date   date) {
719         return containsDomainValue(getTime(date));
720     }
721 
722     /**
723      * Returns <code>true</code> if a range of values are contained in the 
724      * timeline. This is implemented verifying that all segments are in the 
725      * range.
726      *
727      * @param domainValueStart start of the range to verify
728      * @param domainValueEnd end of the range to verify
729      * 
730      * @return <code>true</code> if the range is contained in the timeline
731      */
732     public boolean containsDomainRange(long domainValueStart, 
733                                        long domainValueEnd) {
734         if (domainValueEnd < domainValueStart) {
735             throw new IllegalArgumentException  (
736                 "domainValueEnd (" + domainValueEnd
737                 + ") < domainValueStart (" + domainValueStart + ")"
738             );
739         }
740         Segment segment = getSegment(domainValueStart);
741         boolean contains = true;
742         do {
743             contains = (segment.inIncludeSegments());
744             if (segment.contains(domainValueEnd)) {
745                 break;
746             } 
747             else {
748                 segment.inc();
749             }
750         } 
751         while (contains);
752         return (contains);
753     }
754 
755     /**
756      * Returns <code>true</code> if a range of values are contained in the 
757      * timeline. This is implemented verifying that all segments are in the 
758      * range.
759      *
760      * @param dateDomainValueStart start of the range to verify
761      * @param dateDomainValueEnd end of the range to verify
762      * 
763      * @return <code>true</code> if the range is contained in the timeline
764      */
765     public boolean containsDomainRange(Date   dateDomainValueStart, 
766                                        Date   dateDomainValueEnd) {
767         return containsDomainRange(
768             getTime(dateDomainValueStart), getTime(dateDomainValueEnd)
769         );
770     }
771 
772     /**
773      * Adds a segment as an exception. An exception segment is defined as a 
774      * segment to exclude from what would otherwise be considered a valid 
775      * segment of the timeline.  An exception segment can not be contained 
776      * inside an already excluded segment.  If so, no action will occur (the 
777      * proposed exception segment will be discarded).
778      * <p>
779      * The segment is identified by a domainValue into any part of the segment.
780      * Therefore the segmentStart <= domainValue <= segmentEnd.
781      *
782      * @param millisecond  domain value to treat as an exception
783      */
784     public void addException(long millisecond) {
785         addException(new Segment(millisecond));
786     }
787 
788     /**
789      * Adds a segment range as an exception. An exception segment is defined as
790      * a segment to exclude from what would otherwise be considered a valid 
791      * segment of the timeline.  An exception segment can not be contained 
792      * inside an already excluded segment.  If so, no action will occur (the 
793      * proposed exception segment will be discarded).
794      * <p>
795      * The segment range is identified by a domainValue that begins a valid 
796      * segment and ends with a domainValue that ends a valid segment. 
797      * Therefore the range will contain all segments whose segmentStart 
798      * <= domainValue and segmentEnd <= toDomainValue.
799      *
800      * @param fromDomainValue  start of domain range to treat as an exception
801      * @param toDomainValue  end of domain range to treat as an exception
802      */
803     public void addException(long fromDomainValue, long toDomainValue) {
804         addException(new SegmentRange(fromDomainValue, toDomainValue));
805     }
806 
807     /**
808      * Adds a segment as an exception. An exception segment is defined as a 
809      * segment to exclude from what would otherwise be considered a valid 
810      * segment of the timeline.  An exception segment can not be contained 
811      * inside an already excluded segment.  If so, no action will occur (the 
812      * proposed exception segment will be discarded).
813      * <p>
814      * The segment is identified by a Date into any part of the segment.
815      *
816      * @param exceptionDate  Date into the segment to exclude.
817      */
818     public void addException(Date   exceptionDate) {
819         addException(getTime(exceptionDate));
820         //addException(exceptionDate.getTime());
821     }
822 
823     /**
824      * Adds a list of dates as segment exceptions. Each exception segment is 
825      * defined as a segment to exclude from what would otherwise be considered 
826      * a valid segment of the timeline.  An exception segment can not be 
827      * contained inside an already excluded segment.  If so, no action will 
828      * occur (the proposed exception segment will be discarded).
829      * <p>
830      * The segment is identified by a Date into any part of the segment.
831      *
832      * @param exceptionList  List of Date objects that identify the segments to
833      *                       exclude.
834      */
835     public void addExceptions(List   exceptionList) {
836         for (Iterator   iter = exceptionList.iterator(); iter.hasNext();) {
837             addException((Date  ) iter.next());
838         }
839     }
840 
841     /**
842      * Adds a segment as an exception. An exception segment is defined as a 
843      * segment to exclude from what would otherwise be considered a valid 
844      * segment of the timeline.  An exception segment can not be contained 
845      * inside an already excluded segment.  This is verified inside this 
846      * method, and if so, no action will occur (the proposed exception segment 
847      * will be discarded).
848      *
849      * @param segment  the segment to exclude.
850      */
851     private void addException(Segment segment) {
852          if (segment.inIncludeSegments()) {
853              int p = binarySearchExceptionSegments(segment);
854              this.exceptionSegments.add(-(p + 1), segment);
855          }
856     }
857 
858     /**
859      * Adds a segment relative to the baseTimeline as an exception. Because a 
860      * base segment is normally larger than our segments, this may add one or 
861      * more segment ranges to the exception list.
862      * <p>
863      * An exception segment is defined as a segment
864      * to exclude from what would otherwise be considered a valid segment of 
865      * the timeline.  An exception segment can not be contained inside an 
866      * already excluded segment.  If so, no action will occur (the proposed 
867      * exception segment will be discarded).
868      * <p>
869      * The segment is identified by a domainValue into any part of the 
870      * baseTimeline segment.
871      *
872      * @param domainValue  domain value to teat as a baseTimeline exception.
873      */
874     public void addBaseTimelineException(long domainValue) {
875 
876         Segment baseSegment = this.baseTimeline.getSegment(domainValue);
877         if (baseSegment.inIncludeSegments()) {
878 
879             // cycle through all the segments contained in the BaseTimeline 
880             // exception segment
881             Segment segment = getSegment(baseSegment.getSegmentStart());
882             while (segment.getSegmentStart() <= baseSegment.getSegmentEnd()) {
883                 if (segment.inIncludeSegments()) {
884 
885                     // find all consecutive included segments
886                     long fromDomainValue = segment.getSegmentStart();
887                     long toDomainValue;
888                     do {
889                         toDomainValue = segment.getSegmentEnd();
890                         segment.inc();
891                     }
892                     while (segment.inIncludeSegments());
893 
894                     // add the interval as an exception
895                     addException(fromDomainValue, toDomainValue);
896 
897                 }
898                 else {
899                     // this is not one of our included segment, skip it
900                     segment.inc();
901                 }
902             }
903         }
904     }
905 
906     /**
907      * Adds a segment relative to the baseTimeline as an exception. An 
908      * exception segment is defined as a segment to exclude from what would 
909      * otherwise be considered a valid segment of the timeline.  An exception 
910      * segment can not be contained inside an already excluded segment. If so, 
911      * no action will occure (the proposed exception segment will be discarded).
912      * <p>
913      * The segment is identified by a domainValue into any part of the segment.
914      * Therefore the segmentStart <= domainValue <= segmentEnd.
915      *
916      * @param date  date domain value to treat as a baseTimeline exception
917      */
918     public void addBaseTimelineException(Date   date) {
919         addBaseTimelineException(getTime(date));
920     }
921 
922     /**
923      * Adds all excluded segments from the BaseTimeline as exceptions to our 
924      * timeline. This allows us to combine two timelines for more complex 
925      * calculations.
926      *
927      * @param fromBaseDomainValue Start of the range where exclusions will be 
928      *                            extracted.
929      * @param toBaseDomainValue End of the range to process.
930      */
931     public void addBaseTimelineExclusions(long fromBaseDomainValue, 
932                                           long toBaseDomainValue) {
933 
934         // find first excluded base segment starting fromDomainValue
935         Segment baseSegment = this.baseTimeline.getSegment(fromBaseDomainValue);
936         while (baseSegment.getSegmentStart() <= toBaseDomainValue 
937                && !baseSegment.inExcludeSegments()) {
938                    
939             baseSegment.inc();
940             
941         }
942 
943         // cycle over all the base segments groups in the range
944         while (baseSegment.getSegmentStart() <= toBaseDomainValue) {
945 
946             long baseExclusionRangeEnd = baseSegment.getSegmentStart() 
947                  + this.baseTimeline.getSegmentsExcluded() 
948                  * this.baseTimeline.getSegmentSize() - 1;
949 
950             // cycle through all the segments contained in the base exclusion 
951             // area
952             Segment segment = getSegment(baseSegment.getSegmentStart());
953             while (segment.getSegmentStart() <= baseExclusionRangeEnd) {
954     &nbs