/* ===========================================================
 * JFreeChart : a free chart library for the Java(tm) platform
 * ===========================================================
 *
 * (C) Copyright 2000-2013, by Object Refinery Limited and Contributors.
 *
 * Project Info:  http://www.jfree.org/jfreechart/index.html
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
 * USA.
 *
 * [Oracle and Java are registered trademarks of Oracle and/or its affiliates. 
 * Other names may be trademarks of their respective owners.]
 *
 * -----------------------
 * SegmentedTimeline.java
 * -----------------------
 * (C) Copyright 2003-2008, by Bill Kelemen and Contributors.
 *
 * Original Author:  Bill Kelemen;
 * Contributor(s):   David Gilbert (for Object Refinery Limited);
 *
 * Changes
 * -------
 * 23-May-2003 : Version 1 (BK);
 * 15-Aug-2003 : Implemented Cloneable (DG);
 * 01-Jun-2004 : Modified to compile with JDK 1.2.2 (DG);
 * 30-Sep-2004 : Replaced getTime().getTime() with getTimeInMillis() (DG);
 * 04-Nov-2004 : Reverted change of 30-Sep-2004, won't work with JDK 1.3 (DG);
 * 11-Jan-2005 : Removed deprecated code in preparation for 1.0.0 release (DG);
 * ------------- JFREECHART 1.0.x ---------------------------------------------
 * 14-Nov-2006 : Fix in toTimelineValue(long) to avoid stack overflow (DG);
 * 02-Feb-2007 : Removed author tags all over JFreeChart sources (DG);
 * 11-Jul-2007 : Fixed time zone bugs (DG);
 * 06-Jun-2008 : Performance enhancement posted in forum (DG);
 *
 */

package org.jfree.chart.axis;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collections;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.Iterator;
import java.util.List;
import java.util.Locale;
import java.util.SimpleTimeZone;
import java.util.TimeZone;

/**
 * A {@link Timeline} that implements a "segmented" timeline with included,
 * excluded and exception segments.
 * <P>
 * A Timeline will present a series of values to be used for an axis. Each
 * Timeline must provide transformation methods between domain values and
 * timeline values.
 * <P>
 * A timeline can be used as parameter to a
 * {@link org.jfree.chart.axis.DateAxis} to define the values that this axis
 * supports. This class implements a timeline formed by segments of equal
 * length (ex. days, hours, minutes) where some segments can be included in the
 * timeline and others excluded. Therefore timelines like "working days" or
 * "working hours" can be created where non-working days or non-working hours
 * respectively can be removed from the timeline, and therefore from the axis.
 * This creates a smooth plot with equal separation between all included
 * segments.
 * <P>
 * Because Timelines were created mainly for Date related axis, values are
 * represented as longs instead of doubles. In this case, the domain value is
 * just the number of milliseconds since January 1, 1970, 00:00:00 GMT as
 * defined by the getTime() method of {@link java.util.Date}.
 * <P>
 * In this class, a segment is defined as a unit of time of fixed length.
 * Examples of segments are: days, hours, minutes, etc. The size of a segment
 * is defined as the number of milliseconds in the segment. Some useful segment
 * sizes are defined as constants in this class: DAY_SEGMENT_SIZE,
 * HOUR_SEGMENT_SIZE, FIFTEEN_MINUTE_SEGMENT_SIZE and MINUTE_SEGMENT_SIZE.
 * <P>
 * Segments are group together to form a Segment Group. Each Segment Group will
 * contain a number of Segments included and a number of Segments excluded. This
 * Segment Group structure will repeat for the whole timeline.
 * <P>
 * For example, a working days SegmentedTimeline would be formed by a group of
 * 7 daily segments, where there are 5 included (Monday through Friday) and 2
 * excluded (Saturday and Sunday) segments.
 * <P>
 * Following is a diagram that explains the major attributes that define a
 * segment.  Each box is one segment and must be of fixed length (ms, second,
 * hour, day, etc).
 * <p>
 * <pre>
 * start time
 *   |
 *   v
 *   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...
 * +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+...
 * |  |  |  |  |  |EE|EE|  |  |  |  |  |EE|EE|  |  |  |  |  |EE|EE|
 * +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+...
 *  \____________/ \___/            \_/
 *        \/         |               |
 *     included   excluded        segment
 *     segments   segments         size
 *  \_________  _______/
 *            \/
 *       segment group
 * </pre>
 * Legend:<br>
 * &lt;space&gt; = Included segment<br>
 * EE      = Excluded segments in the base timeline<br>
 * <p>
 * In the example, the following segment attributes are presented:
 * <ul>
 * <li>segment size: the size of each segment in ms.
 * <li>start time: the start of the first segment of the first segment group to
 *     consider.
 * <li>included segments: the number of segments to include in the group.
 * <li>excluded segments: the number of segments to exclude in the group.
 * </ul>
 * <p>
 * Exception Segments are allowed. These exception segments are defined as
 * segments that would have been in the included segments of the Segment Group,
 * but should be excluded for special reasons. In the previous working days
 * SegmentedTimeline example, holidays would be considered exceptions.
 * <P>
 * Additionally the <code>startTime</code>, or start of the first Segment of
 * the smallest segment group needs to be defined. This startTime could be
 * relative to January 1, 1970, 00:00:00 GMT or any other date. This creates a
 * point of reference to start counting Segment Groups. For example, for the
 * working days SegmentedTimeline, the <code>startTime</code> could be
 * 00:00:00 GMT of the first Monday after January 1, 1970. In this class, the
 * constant FIRST_MONDAY_AFTER_1900 refers to a reference point of the first
 * Monday of the last century.
 * <p>
 * A SegmentedTimeline can include a baseTimeline. This combination of
 * timelines allows the creation of more complex timelines. For example, in
 * order to implement a SegmentedTimeline for an intraday stock trading
 * application, where the trading period is defined as 9:00 AM through 4:00 PM
 * Monday through Friday, two SegmentedTimelines are used. The first one (the
 * baseTimeline) would be a working day SegmentedTimeline (daily timeline
 * Monday through Friday). On top of this baseTimeline, a second one is defined
 * that maps the 9:00 AM to 4:00 PM period. Because the baseTimeline defines a
 * timeline of Monday through Friday, the resulting (combined) timeline will
 * expose the period 9:00 AM through 4:00 PM only on Monday through Friday,
 * and will remove all other intermediate intervals.
 * <P>
 * Two factory methods newMondayThroughFridayTimeline() and
 * newFifteenMinuteTimeline() are provided as examples to create special
 * SegmentedTimelines.
 *
 * @see org.jfree.chart.axis.DateAxis
 */
public class SegmentedTimeline implements Timeline, Cloneable, Serializable {

    /** For serialization. */
    private static final long serialVersionUID = 1093779862539903110L;

    ////////////////////////////////////////////////////////////////////////////
    // predetermined segments sizes
    ////////////////////////////////////////////////////////////////////////////

    /** Defines a day segment size in ms. */
    public static final long DAY_SEGMENT_SIZE = 24 * 60 * 60 * 1000;

    /** Defines a one hour segment size in ms. */
    public static final long HOUR_SEGMENT_SIZE = 60 * 60 * 1000;

    /** Defines a 15-minute segment size in ms. */
    public static final long FIFTEEN_MINUTE_SEGMENT_SIZE = 15 * 60 * 1000;

    /** Defines a one-minute segment size in ms. */
    public static final long MINUTE_SEGMENT_SIZE = 60 * 1000;

    ////////////////////////////////////////////////////////////////////////////
    // other constants
    ////////////////////////////////////////////////////////////////////////////

    /**
     * Utility constant that defines the startTime as the first monday after
     * 1/1/1970.  This should be used when creating a SegmentedTimeline for
     * Monday through Friday. See static block below for calculation of this
     * constant.
     *
     * @deprecated As of 1.0.7.  This field doesn't take into account changes
     *         to the default time zone.
     */
    public static long FIRST_MONDAY_AFTER_1900;

    /**
     * Utility TimeZone object that has no DST and an offset equal to the
     * default TimeZone. This allows easy arithmetic between days as each one
     * will have equal size.
     *
     * @deprecated As of 1.0.7.  This field is initialised based on the
     *         default time zone, and doesn't take into account subsequent
     *         changes to the default.
     */
    public static TimeZone NO_DST_TIME_ZONE;

    /**
     * This is the default time zone where the application is running. See
     * getTime() below where we make use of certain transformations between
     * times in the default time zone and the no-dst time zone used for our
     * calculations.
     *
     * @deprecated As of 1.0.7.  When the default time zone is required,
     *         just call <code>TimeZone.getDefault()</code>.
     */
    public static TimeZone DEFAULT_TIME_ZONE = TimeZone.getDefault();

    /**
     * This will be a utility calendar that has no DST but is shifted relative
     * to the default time zone's offset.
     */
    private Calendar workingCalendarNoDST;

    /**
     * This will be a utility calendar that used the default time zone.
     */
    private Calendar workingCalendar = Calendar.getInstance();

    ////////////////////////////////////////////////////////////////////////////
    // private attributes
    ////////////////////////////////////////////////////////////////////////////

    /** Segment size in ms. */
    private long segmentSize;

    /** Number of consecutive segments to include in a segment group. */
    private int segmentsIncluded;

    /** Number of consecutive segments to exclude in a segment group. */
    private int segmentsExcluded;

    /** Number of segments in a group (segmentsIncluded + segmentsExcluded). */
    private int groupSegmentCount;

    /**
     * Start of time reference from time zero (1/1/1970).
     * This is the start of segment #0.
     */
    private long startTime;

    /** Consecutive ms in segmentsIncluded (segmentsIncluded * segmentSize). */
    private long segmentsIncludedSize;

    /** Consecutive ms in segmentsExcluded (segmentsExcluded * segmentSize). */
    private long segmentsExcludedSize;

    /** ms in a segment group (segmentsIncludedSize + segmentsExcludedSize). */
    private long segmentsGroupSize;

    /**
     * List of exception segments (exceptions segments that would otherwise be
     * included based on the periodic (included, excluded) grouping).
     */
    private List exceptionSegments = new ArrayList();

    /**
     * This base timeline is used to specify exceptions at a higher level. For
     * example, if we are a intraday timeline and want to exclude holidays,
     * instead of having to exclude all intraday segments for the holiday,
     * segments from this base timeline can be excluded. This baseTimeline is
     * always optional and is only a convenience method.
     * <p>
     * Additionally, all excluded segments from this baseTimeline will be
     * considered exceptions at this level.
     */
    private SegmentedTimeline baseTimeline;

    /** A flag that controls whether or not to adjust for daylight saving. */
    private boolean adjustForDaylightSaving = false;

    ////////////////////////////////////////////////////////////////////////////
    // static block
    ////////////////////////////////////////////////////////////////////////////

    static {
        // make a time zone with no DST for our Calendar calculations
        int offset = TimeZone.getDefault().getRawOffset();
        NO_DST_TIME_ZONE = new SimpleTimeZone(offset, "UTC-" + offset);

        // calculate midnight of first monday after 1/1/1900 relative to
        // current locale
        Calendar cal = new GregorianCalendar(NO_DST_TIME_ZONE);
        cal.set(1900, 0, 1, 0, 0, 0);
        cal.set(Calendar.MILLISECOND, 0);
        while (cal.get(Calendar.DAY_OF_WEEK) != Calendar.MONDAY) {
            cal.add(Calendar.DATE, 1);
        }
        // FIRST_MONDAY_AFTER_1900 = cal.getTime().getTime();
        // preceding code won't work with JDK 1.3
        FIRST_MONDAY_AFTER_1900 = cal.getTime().getTime();
    }

    ////////////////////////////////////////////////////////////////////////////
    // constructors and factory methods
    ////////////////////////////////////////////////////////////////////////////

    /**
     * Constructs a new segmented timeline, optionaly using another segmented
     * timeline as its base. This chaining of SegmentedTimelines allows further
     * segmentation into smaller timelines.
     *
     * If a base
     *
     * @param segmentSize the size of a segment in ms. This time unit will be
     *        used to compute the included and excluded segments of the
     *        timeline.
     * @param segmentsIncluded Number of consecutive segments to include.
     * @param segmentsExcluded Number of consecutive segments to exclude.
     */
    public SegmentedTimeline(long segmentSize,
                             int segmentsIncluded,
                             int segmentsExcluded) {

        this.segmentSize = segmentSize;
        this.segmentsIncluded = segmentsIncluded;
        this.segmentsExcluded = segmentsExcluded;

        this.groupSegmentCount = this.segmentsIncluded + this.segmentsExcluded;
        this.segmentsIncludedSize = this.segmentsIncluded * this.segmentSize;
        this.segmentsExcludedSize = this.segmentsExcluded * this.segmentSize;
        this.segmentsGroupSize = this.segmentsIncludedSize
                                 + this.segmentsExcludedSize;
        int offset = TimeZone.getDefault().getRawOffset();
        TimeZone z = new SimpleTimeZone(offset, "UTC-" + offset);
        this.workingCalendarNoDST = new GregorianCalendar(z,
                Locale.getDefault());
    }

    /**
     * Returns the milliseconds for midnight of the first Monday after
     * 1-Jan-1900, ignoring daylight savings.
     *
     * @return The milliseconds.
     *
     * @since 1.0.7
     */
    public static long firstMondayAfter1900() {
        int offset = TimeZone.getDefault().getRawOffset();
        TimeZone z = new SimpleTimeZone(offset, "UTC-" + offset);

        // calculate midnight of first monday after 1/1/1900 relative to
        // current locale
        Calendar cal = new GregorianCalendar(z);
        cal.set(1900, 0, 1, 0, 0, 0);
        cal.set(Calendar.MILLISECOND, 0);
        while (cal.get(Calendar.DAY_OF_WEEK) != Calendar.MONDAY) {
            cal.add(Calendar.DATE, 1);
        }
        //return cal.getTimeInMillis();
        // preceding code won't work with JDK 1.3
        return cal.getTime().getTime();
    }

    /**
     * Factory method to create a Monday through Friday SegmentedTimeline.
     * <P>
     * The <code>startTime</code> of the resulting timeline will be midnight
     * of the first Monday after 1/1/1900.
     *
     * @return A fully initialized SegmentedTimeline.
     */
    public static SegmentedTimeline newMondayThroughFridayTimeline() {
        SegmentedTimeline timeline
            = new SegmentedTimeline(DAY_SEGMENT_SIZE, 5, 2);
        timeline.setStartTime(firstMondayAfter1900());
        return timeline;
    }

    /**
     * Factory method to create a 15-min, 9:00 AM thought 4:00 PM, Monday
     * through Friday SegmentedTimeline.
     * <P>
     * This timeline uses a segmentSize of FIFTEEN_MIN_SEGMENT_SIZE. The
     * segment group is defined as 28 included segments (9:00 AM through
     * 4:00 PM) and 68 excluded segments (4:00 PM through 9:00 AM the next day).
     * <P>
     * In order to exclude Saturdays and Sundays it uses a baseTimeline that
     * only includes Monday through Friday days.
     * <P>
     * The <code>startTime</code> of the resulting timeline will be 9:00 AM
     * after the startTime of the baseTimeline. This will correspond to 9:00 AM
     * of the first Monday after 1/1/1900.
     *
     * @return A fully initialized SegmentedTimeline.
     */
    public static SegmentedTimeline newFifteenMinuteTimeline() {
        SegmentedTimeline timeline = new SegmentedTimeline(
                FIFTEEN_MINUTE_SEGMENT_SIZE, 28, 68);
        timeline.setStartTime(firstMondayAfter1900() + 36
                * timeline.getSegmentSize());
        timeline.setBaseTimeline(newMondayThroughFridayTimeline());
        return timeline;
    }

    /**
     * Returns the flag that controls whether or not the daylight saving
     * adjustment is applied.
     *
     * @return A boolean.
     */
    public boolean getAdjustForDaylightSaving() {
        return this.adjustForDaylightSaving;
    }

    /**
     * Sets the flag that controls whether or not the daylight saving adjustment
     * is applied.
     *
     * @param adjust  the flag.
     */
    public void setAdjustForDaylightSaving(boolean adjust) {
        this.adjustForDaylightSaving = adjust;
    }

    ////////////////////////////////////////////////////////////////////////////
    // operations
    ////////////////////////////////////////////////////////////////////////////

    /**
     * Sets the start time for the timeline. This is the beginning of segment
     * zero.
     *
     * @param millisecond  the start time (encoded as in java.util.Date).
     */
    public void setStartTime(long millisecond) {
        this.startTime = millisecond;
    }

    /**
     * Returns the start time for the timeline. This is the beginning of
     * segment zero.
     *
     * @return The start time.
     */
    public long getStartTime() {
        return this.startTime;
    }

    /**
     * Returns the number of segments excluded per segment group.
     *
     * @return The number of segments excluded.
     */
    public int getSegmentsExcluded() {
        return this.segmentsExcluded;
    }

    /**
     * Returns the size in milliseconds of the segments excluded per segment
     * group.
     *
     * @return The size in milliseconds.
     */
    public long getSegmentsExcludedSize() {
        return this.segmentsExcludedSize;
    }

    /**
     * Returns the number of segments in a segment group. This will be equal to
     * segments included plus segments excluded.
     *
     * @return The number of segments.
     */
    public int getGroupSegmentCount() {
        return this.groupSegmentCount;
    }

    /**
     * Returns the size in milliseconds of a segment group. This will be equal
     * to size of the segments included plus the size of the segments excluded.
     *
     * @return The segment group size in milliseconds.
     */
    public long getSegmentsGroupSize() {
        return this.segmentsGroupSize;
    }

    /**
     * Returns the number of segments included per segment group.
     *
     * @return The number of segments.
     */
    public int getSegmentsIncluded() {
        return this.segmentsIncluded;
    }

    /**
     * Returns the size in ms of the segments included per segment group.
     *
     * @return The segment size in milliseconds.
     */
    public long getSegmentsIncludedSize() {
        return this.segmentsIncludedSize;
    }

    /**
     * Returns the size of one segment in ms.
     *
     * @return The segment size in milliseconds.
     */
    public long getSegmentSize() {
        return this.segmentSize;
    }

    /**
     * Returns a list of all the exception segments. This list is not
     * modifiable.
     *
     * @return The exception segments.
     */
    public List getExceptionSegments() {
        return Collections.unmodifiableList(this.exceptionSegments);
    }

    /**
     * Sets the exception segments list.
     *
     * @param exceptionSegments  the exception segments.
     */
    public void setExceptionSegments(List exceptionSegments) {
        this.exceptionSegments = exceptionSegments;
    }

    /**
     * Returns our baseTimeline, or <code>null</code> if none.
     *
     * @return The base timeline.
     */
    public SegmentedTimeline getBaseTimeline() {
        return this.baseTimeline;
    }

    /**
     * Sets the base timeline.
     *
     * @param baseTimeline  the timeline.
     */
    public void setBaseTimeline(SegmentedTimeline baseTimeline) {

        // verify that baseTimeline is compatible with us
        if (baseTimeline != null) {
            if (baseTimeline.getSegmentSize() < this.segmentSize) {
                throw new IllegalArgumentException(
                        "baseTimeline.getSegmentSize() "
                        + "is smaller than segmentSize");
            }
            else if (baseTimeline.getStartTime() > this.startTime) {
                throw new IllegalArgumentException(
                        "baseTimeline.getStartTime() is after startTime");
            }
            else if ((baseTimeline.getSegmentSize() % this.segmentSize) != 0) {
                throw new IllegalArgumentException(
                        "baseTimeline.getSegmentSize() is not multiple of "
                        + "segmentSize");
            }
            else if (((this.startTime
                    - baseTimeline.getStartTime()) % this.segmentSize) != 0) {
                throw new IllegalArgumentException(
                        "baseTimeline is not aligned");
            }
        }

        this.baseTimeline = baseTimeline;
    }

    /**
     * Translates a value relative to the domain value (all Dates) into a value
     * relative to the segmented timeline. The values relative to the segmented
     * timeline are all consecutives starting at zero at the startTime.
     *
     * @param millisecond  the millisecond (as encoded by java.util.Date).
     *
     * @return The timeline value.
     */
    @Override
    public long toTimelineValue(long millisecond) {

        long result;
        long rawMilliseconds = millisecond - this.startTime;
        long groupMilliseconds = rawMilliseconds % this.segmentsGroupSize;
        long groupIndex = rawMilliseconds / this.segmentsGroupSize;

        if (groupMilliseconds >= this.segmentsIncludedSize) {
            result = toTimelineValue(this.startTime + this.segmentsGroupSize
                    * (groupIndex + 1));
        }
        else {
            Segment segment = getSegment(millisecond);
            if (segment.inExceptionSegments()) {
                int p;
                while ((p = binarySearchExceptionSegments(segment)) >= 0) {
                    segment = getSegment(millisecond = ((Segment)
                            this.exceptionSegments.get(p)).getSegmentEnd() + 1);
                }
                result = toTimelineValue(millisecond);
            }
            else {
                long shiftedSegmentedValue = millisecond - this.startTime;
                long x = shiftedSegmentedValue % this.segmentsGroupSize;
                long y = shiftedSegmentedValue / this.segmentsGroupSize;

                long wholeExceptionsBeforeDomainValue =
                    getExceptionSegmentCount(this.startTime, millisecond - 1);

//                long partialTimeInException = 0;
//                Segment ss = getSegment(millisecond);
//                if (ss.inExceptionSegments()) {
//                    partialTimeInException = millisecond
                //     - ss.getSegmentStart();
//                }

                if (x < this.segmentsIncludedSize) {
                    result = this.segmentsIncludedSize * y
                             + x - wholeExceptionsBeforeDomainValue
                             * this.segmentSize;
                             // - partialTimeInException;
                }
                else {
                    result = this.segmentsIncludedSize * (y + 1)
                             - wholeExceptionsBeforeDomainValue
                             * this.segmentSize;
                             // - partialTimeInException;
                }
            }
        }

        return result;
    }

    /**
     * Translates a date into a value relative to the segmented timeline. The
     * values relative to the segmented timeline are all consecutives starting
     * at zero at the startTime.
     *
     * @param date  date relative to the domain.
     *
     * @return The timeline value (in milliseconds).
     */
    @Override
    public long toTimelineValue(Date date) {
        return toTimelineValue(getTime(date));
        //return toTimelineValue(dateDomainValue.getTime());
    }

    /**
     * Translates a value relative to the timeline into a millisecond.
     *
     * @param timelineValue  the timeline value (in milliseconds).
     *
     * @return The domain value (in milliseconds).
     */
    @Override
    public long toMillisecond(long timelineValue) {

        // calculate the result as if no exceptions
        Segment result = new Segment(this.startTime + timelineValue
                + (timelineValue / this.segmentsIncludedSize)
                * this.segmentsExcludedSize);

        long lastIndex = this.startTime;

        // adjust result for any exceptions in the result calculated
        while (lastIndex <= result.segmentStart) {

            // skip all whole exception segments in the range
            long exceptionSegmentCount;
            while ((exceptionSegmentCount = getExceptionSegmentCount(
                 lastIndex, (result.millisecond / this.segmentSize)
                 * this.segmentSize - 1)) > 0
            ) {
                lastIndex = result.segmentStart;
                // move forward exceptionSegmentCount segments skipping
                // excluded segments
                for (int i = 0; i < exceptionSegmentCount; i++) {
                    do {
                        result.inc();
                    }
                    while (result.inExcludeSegments());
                }
            }
            lastIndex = result.segmentStart;

            // skip exception or excluded segments we may fall on
            while (result.inExceptionSegments() || result.inExcludeSegments()) {
                result.inc();
                lastIndex += this.segmentSize;
            }

            lastIndex++;
        }

        return getTimeFromLong(result.millisecond);
    }

    /**
     * Converts a date/time value to take account of daylight savings time.
     *
     * @param date  the milliseconds.
     *
     * @return The milliseconds.
     */
    public long getTimeFromLong(long date) {
        long result = date;
        if (this.adjustForDaylightSaving) {
            this.workingCalendarNoDST.setTime(new Date(date));
            this.workingCalendar.set(
                this.workingCalendarNoDST.get(Calendar.YEAR),
                this.workingCalendarNoDST.get(Calendar.MONTH),
                this.workingCalendarNoDST.get(Calendar.DATE),
                this.workingCalendarNoDST.get(Calendar.HOUR_OF_DAY),
                this.workingCalendarNoDST.get(Calendar.MINUTE),
                this.workingCalendarNoDST.get(Calendar.SECOND)
            );
            this.workingCalendar.set(Calendar.MILLISECOND,
                    this.workingCalendarNoDST.get(Calendar.MILLISECOND));
            // result = this.workingCalendar.getTimeInMillis();
            // preceding code won't work with JDK 1.3
            result = this.workingCalendar.getTime().getTime();
        }
        return result;
    }

    /**
     * Returns <code>true</code> if a value is contained in the timeline.
     *
     * @param millisecond  the value to verify.
     *
     * @return <code>true</code> if value is contained in the timeline.
     */
    @Override
    public boolean containsDomainValue(long millisecond) {
        Segment segment = getSegment(millisecond);
        return segment.inIncludeSegments();
    }

    /**
     * Returns <code>true</code> if a value is contained in the timeline.
     *
     * @param date  date to verify
     *
     * @return <code>true</code> if value is contained in the timeline
     */
    @Override
    public boolean containsDomainValue(Date date) {
        return containsDomainValue(getTime(date));
    }

    /**
     * Returns <code>true</code> if a range of values are contained in the
     * timeline. This is implemented verifying that all segments are in the
     * range.
     *
     * @param domainValueStart start of the range to verify
     * @param domainValueEnd end of the range to verify
     *
     * @return <code>true</code> if the range is contained in the timeline
     */
    @Override
    public boolean containsDomainRange(long domainValueStart,
            long domainValueEnd) {
        if (domainValueEnd < domainValueStart) {
            throw new IllegalArgumentException(
                    "domainValueEnd (" + domainValueEnd
                    + ") < domainValueStart (" + domainValueStart + ")");
        }
        Segment segment = getSegment(domainValueStart);
        boolean contains = true;
        do {
            contains = (segment.inIncludeSegments());
            if (segment.contains(domainValueEnd)) {
                break;
            }
            else {
                segment.inc();
            }
        }
        while (contains);
        return (contains);
    }

    /**
     * Returns <code>true</code> if a range of values are contained in the
     * timeline. This is implemented verifying that all segments are in the
     * range.
     *
     * @param dateDomainValueStart start of the range to verify
     * @param dateDomainValueEnd end of the range to verify
     *
     * @return <code>true</code> if the range is contained in the timeline
     */
    @Override
    public boolean containsDomainRange(Date dateDomainValueStart,
            Date dateDomainValueEnd) {
        return containsDomainRange(getTime(dateDomainValueStart),
                getTime(dateDomainValueEnd));
    }

    /**
     * Adds a segment as an exception. An exception segment is defined as a
     * segment to exclude from what would otherwise be considered a valid
     * segment of the timeline.  An exception segment can not be contained
     * inside an already excluded segment.  If so, no action will occur (the
     * proposed exception segment will be discarded).
     * <p>
     * The segment is identified by a domainValue into any part of the segment.
     * Therefore the segmentStart <= domainValue <= segmentEnd.
     *
     * @param millisecond  domain value to treat as an exception
     */
    public void addException(long millisecond) {
        addException(new Segment(millisecond));
    }

    /**
     * Adds a segment range as an exception. An exception segment is defined as
     * a segment to exclude from what would otherwise be considered a valid
     * segment of the timeline.  An exception segment can not be contained
     * inside an already excluded segment.  If so, no action will occur (the
     * proposed exception segment will be discarded).
     * <p>
     * The segment range is identified by a domainValue that begins a valid
     * segment and ends with a domainValue that ends a valid segment.
     * Therefore the range will contain all segments whose segmentStart
     * <= domainValue and segmentEnd <= toDomainValue.
     *
     * @param fromDomainValue  start of domain range to treat as an exception
     * @param toDomainValue  end of domain range to treat as an exception
     */
    public void addException(long fromDomainValue, long toDomainValue) {
        addException(new SegmentRange(fromDomainValue, toDomainValue));
    }

    /**
     * Adds a segment as an exception. An exception segment is defined as a
     * segment to exclude from what would otherwise be considered a valid
     * segment of the timeline.  An exception segment can not be contained
     * inside an already excluded segment.  If so, no action will occur (the
     * proposed exception segment will be discarded).
     * <p>
     * The segment is identified by a Date into any part of the segment.
     *
     * @param exceptionDate  Date into the segment to exclude.
     */
    public void addException(Date exceptionDate) {
        addException(getTime(exceptionDate));
        //addException(exceptionDate.getTime());
    }

    /**
     * Adds a list of dates as segment exceptions. Each exception segment is
     * defined as a segment to exclude from what would otherwise be considered
     * a valid segment of the timeline.  An exception segment can not be
     * contained inside an already excluded segment.  If so, no action will
     * occur (the proposed exception segment will be discarded).
     * <p>
     * The segment is identified by a Date into any part of the segment.
     *
     * @param exceptionList  List of Date objects that identify the segments to
     *                       exclude.
     */
    public void addExceptions(List exceptionList) {
        for (Iterator iter = exceptionList.iterator(); iter.hasNext();) {
            addException((Date) iter.next());
        }
    }

    /**
     * Adds a segment as an exception. An exception segment is defined as a
     * segment to exclude from what would otherwise be considered a valid
     * segment of the timeline.  An exception segment can not be contained
     * inside an already excluded segment.  This is verified inside this
     * method, and if so, no action will occur (the proposed exception segment
     * will be discarded).
     *
     * @param segment  the segment to exclude.
     */
    private void addException(Segment segment) {
         if (segment.inIncludeSegments()) {
             int p = binarySearchExceptionSegments(segment);
             this.exceptionSegments.add(-(p + 1), segment);
         }
    }

    /**
     * Adds a segment relative to the baseTimeline as an exception. Because a
     * base segment is normally larger than our segments, this may add one or
     * more segment ranges to the exception list.
     * <p>
     * An exception segment is defined as a segment
     * to exclude from what would otherwise be considered a valid segment of
     * the timeline.  An exception segment can not be contained inside an
     * already excluded segment.  If so, no action will occur (the proposed
     * exception segment will be discarded).
     * <p>
     * The segment is identified by a domainValue into any part of the
     * baseTimeline segment.
     *
     * @param domainValue  domain value to teat as a baseTimeline exception.
     */
    public void addBaseTimelineException(long domainValue) {

        Segment baseSegment = this.baseTimeline.getSegment(domainValue);
        if (baseSegment.inIncludeSegments()) {

            // cycle through all the segments contained in the BaseTimeline
            // exception segment
            Segment segment = getSegment(baseSegment.getSegmentStart());
            while (segment.getSegmentStart() <= baseSegment.getSegmentEnd()) {
                if (segment.inIncludeSegments()) {

                    // find all consecutive included segments
                    long fromDomainValue = segment.getSegmentStart();
                    long toDomainValue;
                    do {
                        toDomainValue = segment.getSegmentEnd();
                        segment.inc();
                    }
                    while (segment.inIncludeSegments());

                    // add the interval as an exception
                    addException(fromDomainValue, toDomainValue);

                }
                else {
                    // this is not one of our included segment, skip it
                    segment.inc();
                }
            }
        }
    }

    /**
     * Adds a segment relative to the baseTimeline as an exception. An
     * exception segment is defined as a segment to exclude from what would
     * otherwise be considered a valid segment of the timeline.  An exception
     * segment can not be contained inside an already excluded segment. If so,
     * no action will occure (the proposed exception segment will be discarded).
     * <p>
     * The segment is identified by a domainValue into any part of the segment.
     * Therefore the segmentStart <= domainValue <= segmentEnd.
     *
     * @param date  date domain value to treat as a baseTimeline exception
     */
    public void addBaseTimelineException(Date date) {
        addBaseTimelineException(getTime(date));
    }

    /**
     * Adds all excluded segments from the BaseTimeline as exceptions to our
     * timeline. This allows us to combine two timelines for more complex
     * calculations.
     *
     * @param fromBaseDomainValue Start of the range where exclusions will be
     *                            extracted.
     * @param toBaseDomainValue End of the range to process.
     */
    public void addBaseTimelineExclusions(long fromBaseDomainValue,
                                          long toBaseDomainValue) {

        // find first excluded base segment starting fromDomainValue
        Segment baseSegment = this.baseTimeline.getSegment(fromBaseDomainValue);
        while (baseSegment.getSegmentStart() <= toBaseDomainValue
               && !baseSegment.inExcludeSegments()) {

            baseSegment.inc();

        }

        // cycle over all the base segments groups in the range
        while (baseSegment.getSegmentStart() <= toBaseDomainValue) {

            long baseExclusionRangeEnd = baseSegment.getSegmentStart()
                 + this.baseTimeline.getSegmentsExcluded()
                 * this.baseTimeline.getSegmentSize() - 1;

            // cycle through all the segments contained in the base exclusion
            // area
            Segment segment = getSegment(baseSegment.getSegmentStart());
            while (segment.getSegmentStart() <= baseExclusionRangeEnd) {
                if (segment.inIncludeSegments()) {

                    // find all consecutive included segments
                    long fromDomainValue = segment.getSegmentStart();
                    long toDomainValue;
                    do {
                        toDomainValue = segment.getSegmentEnd();
                        segment.inc();
                    }
                    while (segment.inIncludeSegments());

                    // add the interval as an exception
                    addException(new BaseTimelineSegmentRange(
                            fromDomainValue, toDomainValue));
                }
                else {
                    // this is not one of our included segment, skip it
                    segment.inc();
                }
            }

            // go to next base segment group
            baseSegment.inc(this.baseTimeline.getGroupSegmentCount());
        }
    }

    /**
     * Returns the number of exception segments wholly contained in the
     * (fromDomainValue, toDomainValue) interval.
     *
     * @param fromMillisecond  the beginning of the interval.
     * @param toMillisecond  the end of the interval.
     *
     * @return Number of exception segments contained in the interval.
     */
    public long getExceptionSegmentCount(long fromMillisecond,
                                         long toMillisecond) {
        if (toMillisecond < fromMillisecond) {
            return (0);
        }

        int n = 0;
        for (Iterator iter = this.exceptionSegments.iterator();
             iter.hasNext();) {
            Segment segment = (Segment) iter.next();
            Segment intersection = segment.intersect(fromMillisecond,
                    toMillisecond);
            if (intersection != null) {
                n += intersection.getSegmentCount();
            }
        }

        return (n);
    }

    /**
     * Returns a segment that contains a domainValue. If the domainValue is
     * not contained in the timeline (because it is not contained in the
     * baseTimeline), a Segment that contains
     * <code>index + segmentSize*m</code> will be returned for the smallest
     * <code>m</code> possible.
     *
     * @param millisecond  index into the segment
     *
     * @return A Segment that contains index, or the next possible Segment.
     */
    public Segment getSegment(long millisecond) {
        return new Segment(millisecond);
    }

    /**
     * Returns a segment that contains a date. For accurate calculations,
     * the calendar should use TIME_ZONE for its calculation (or any other
     * similar time zone).
     *
     * If the date is not contained in the timeline (because it is not
     * contained in the baseTimeline), a Segment that contains
     * <code>date + segmentSize*m</code> will be returned for the smallest
     * <code>m</code> possible.
     *
     * @param date date into the segment
     *
     * @return A Segment that contains date, or the next possible Segment.
     */
    public Segment getSegment(Date date) {
        return (getSegment(getTime(date)));
    }

    /**
     * Convenient method to test equality in two objects, taking into account
     * nulls.
     *
     * @param o first object to compare
     * @param p second object to compare
     *
     * @return <code>true</code> if both objects are equal or both
     *         <code>null</code>, <code>false</code> otherwise.
     */
    private boolean equals(Object o, Object p) {
        return (o == p || ((o != null) && o.equals(p)));
    }

    /**
     * Returns true if we are equal to the parameter
     *
     * @param o Object to verify with us
     *
     * @return <code>true</code> or <code>false</code>
     */
    @Override
    public boolean equals(Object o) {
        if (o instanceof SegmentedTimeline) {
            SegmentedTimeline other = (SegmentedTimeline) o;

            boolean b0 = (this.segmentSize == other.getSegmentSize());
            boolean b1 = (this.segmentsIncluded == other.getSegmentsIncluded());
            boolean b2 = (this.segmentsExcluded == other.getSegmentsExcluded());
            boolean b3 = (this.startTime == other.getStartTime());
            boolean b4 = equals(this.exceptionSegments,
                    other.getExceptionSegments());
            return b0 && b1 && b2 && b3 && b4;
        }
        else {
            return (false);
        }
    }

    /**
     * Returns a hash code for this object.
     *
     * @return A hash code.
     */
    @Override
    public int hashCode() {
        int result = 19;
        result = 37 * result
                 + (int) (this.segmentSize ^ (this.segmentSize >>> 32));
        result = 37 * result + (int) (this.startTime ^ (this.startTime >>> 32));
        return result;
    }

    /**
     * Preforms a binary serach in the exceptionSegments sorted array. This
     * array can contain Segments or SegmentRange objects.
     *
     * @param  segment the key to be searched for.
     *
     * @return index of the search segment, if it is contained in the list;
     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
     *         <i>insertion point</i> is defined as the point at which the
     *         segment would be inserted into the list: the index of the first
     *         element greater than the key, or <tt>list.size()</tt>, if all
     *         elements in the list are less than the specified segment.  Note
     *         that this guarantees that the return value will be &gt;= 0 if
     *         and only if the key is found.
     */
    private int binarySearchExceptionSegments(Segment segment) {
        int low = 0;
        int high = this.exceptionSegments.size() - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            Segment midSegment = (Segment) this.exceptionSegments.get(mid);

            // first test for equality (contains or contained)
            if (segment.contains(midSegment) || midSegment.contains(segment)) {
                return mid;
            }

            if (midSegment.before(segment)) {
                low = mid + 1;
            }
            else if (midSegment.after(segment)) {
                high = mid - 1;
            }
            else {
                throw new IllegalStateException("Invalid condition.");
            }
        }
        return -(low + 1);  // key not found
    }

    /**
     * Special method that handles conversion between the Default Time Zone and
     * a UTC time zone with no DST. This is needed so all days have the same
     * size. This method is the prefered way of converting a Data into
     * milliseconds for usage in this class.
     *
     * @param date Date to convert to long.
     *
     * @return The milliseconds.
     */
    public long getTime(Date date) {
        long result = date.getTime();
        if (this.adjustForDaylightSaving) {
            this.workingCalendar.setTime(date);
            this.workingCalendarNoDST.set(
                    this.workingCalendar.get(Calendar.YEAR),
                    this.workingCalendar.get(Calendar.MONTH),
                    this.workingCalendar.get(Calendar.DATE),
                    this.workingCalendar.get(Calendar.HOUR_OF_DAY),
                    this.workingCalendar.get(Calendar.MINUTE),
                    this.workingCalendar.get(Calendar.SECOND));
            this.workingCalendarNoDST.set(Calendar.MILLISECOND,
                    this.workingCalendar.get(Calendar.MILLISECOND));
            Date revisedDate = this.workingCalendarNoDST.getTime();
            result = revisedDate.getTime();
        }

        return result;
    }

    /**
     * Converts a millisecond value into a {@link Date} object.
     *
     * @param value  the millisecond value.
     *
     * @return The date.
     */
    public Date getDate(long value) {
        this.workingCalendarNoDST.setTime(new Date(value));
        return (this.workingCalendarNoDST.getTime());
    }

    /**
     * Returns a clone of the timeline.
     *
     * @return A clone.
     *
     * @throws CloneNotSupportedException ??.
     */
    @Override
    public Object clone() throws CloneNotSupportedException {
        SegmentedTimeline clone = (SegmentedTimeline) super.clone();
        return clone;
    }

    /**
     * Internal class to represent a valid segment for this timeline. A segment
     * is valid on a timeline if it is part of its included, excluded or
     * exception segments.
     * <p>
     * Each segment will know its segment number, segmentStart, segmentEnd and
     * index inside the segment.
     */
    public class Segment implements Comparable, Cloneable, Serializable {

        /** The segment number. */
        protected long segmentNumber;

        /** The segment start. */
        protected long segmentStart;

        /** The segment end. */
        protected long segmentEnd;

        /** A reference point within the segment. */
        protected long millisecond;

        /**
         * Protected constructor only used by sub-classes.
         */
        protected Segment() {
            // empty
        }

        /**
         * Creates a segment for a given point in time.
         *
         * @param millisecond  the millisecond (as encoded by java.util.Date).
         */
        protected Segment(long millisecond) {
            this.segmentNumber = calculateSegmentNumber(millisecond);
            this.segmentStart = SegmentedTimeline.this.startTime
                + this.segmentNumber * SegmentedTimeline.this.segmentSize;
            this.segmentEnd
                = this.segmentStart + SegmentedTimeline.this.segmentSize - 1;
            this.millisecond = millisecond;
        }

        /**
         * Calculates the segment number for a given millisecond.
         *
         * @param millis  the millisecond (as encoded by java.util.Date).
         *
         * @return The segment number.
         */
        public long calculateSegmentNumber(long millis) {
            if (millis >= SegmentedTimeline.this.startTime) {
                return (millis - SegmentedTimeline.this.startTime)
                    / SegmentedTimeline.this.segmentSize;
            }
            else {
                return ((millis - SegmentedTimeline.this.startTime)
                    / SegmentedTimeline.this.segmentSize) - 1;
            }
        }

        /**
         * Returns the segment number of this segment. Segments start at 0.
         *
         * @return The segment number.
         */
        public long getSegmentNumber() {
            return this.segmentNumber;
        }

        /**
         * Returns always one (the number of segments contained in this
         * segment).
         *
         * @return The segment count (always 1 for this class).
         */
        public long getSegmentCount() {
            return 1;
        }

        /**
         * Gets the start of this segment in ms.
         *
         * @return The segment start.
         */
        public long getSegmentStart() {
            return this.segmentStart;
        }

        /**
         * Gets the end of this segment in ms.
         *
         * @return The segment end.
         */
        public long getSegmentEnd() {
            return this.segmentEnd;
        }

        /**
         * Returns the millisecond used to reference this segment (always
         * between the segmentStart and segmentEnd).
         *
         * @return The millisecond.
         */
        public long getMillisecond() {
            return this.millisecond;
        }

        /**
         * Returns a {@link java.util.Date} that represents the reference point
         * for this segment.
         *
         * @return The date.
         */
        public Date getDate() {
            return SegmentedTimeline.this.getDate(this.millisecond);
        }

        /**
         * Returns true if a particular millisecond is contained in this
         * segment.
         *
         * @param millis  the millisecond to verify.
         *
         * @return <code>true</code> if the millisecond is contained in the
         *         segment.
         */
        public boolean contains(long millis) {
            return (this.segmentStart <= millis && millis <= this.segmentEnd);
        }

        /**
         * Returns <code>true</code> if an interval is contained in this
         * segment.
         *
         * @param from  the start of the interval.
         * @param to  the end of the interval.
         *
         * @return <code>true</code> if the interval is contained in the
         *         segment.
         */
        public boolean contains(long from, long to) {
            return (this.segmentStart <= from && to <= this.segmentEnd);
        }

        /**
         * Returns <code>true</code> if a segment is contained in this segment.
         *
         * @param segment  the segment to test for inclusion
         *
         * @return <code>true</code> if the segment is contained in this
         *         segment.
         */
        public boolean contains(Segment segment) {
            return contains(segment.getSegmentStart(), segment.getSegmentEnd());
        }

        /**
         * Returns <code>true</code> if this segment is contained in an
         * interval.
         *
         * @param from  the start of the interval.
         * @param to  the end of the interval.
         *
         * @return <code>true</code> if this segment is contained in the
         *         interval.
         */
        public boolean contained(long from, long to) {
            return (from <= this.segmentStart && this.segmentEnd <= to);
        }

        /**
         * Returns a segment that is the intersection of this segment and the
         * interval.
         *
         * @param from  the start of the interval.
         * @param to  the end of the interval.
         *
         * @return A segment.
         */
        public Segment intersect(long from, long to) {
            if (from <= this.segmentStart && this.segmentEnd <= to) {
                return this;
            }
            else {
                return null;
            }
        }

        /**
         * Returns <code>true</code> if this segment is wholly before another
         * segment.
         *
         * @param other  the other segment.
         *
         * @return A boolean.
         */
        public boolean before(Segment other) {
            return (this.segmentEnd < other.getSegmentStart());
        }

        /**
         * Returns <code>true</code> if this segment is wholly after another
         * segment.
         *
         * @param other  the other segment.
         *
         * @return A boolean.
         */
        public boolean after(Segment other) {
            return (this.segmentStart > other.getSegmentEnd());
        }

        /**
         * Tests an object (usually another <code>Segment</code>) for equality
         * with this segment.
         *
         * @param object The other segment to compare with us
         *
         * @return <code>true</code> if we are the same segment
         */
        @Override
        public boolean equals(Object object) {
            if (object instanceof Segment) {
                Segment other = (Segment) object;
                return (this.segmentNumber == other.getSegmentNumber()
                        && this.segmentStart == other.getSegmentStart()
                        && this.segmentEnd == other.getSegmentEnd()
                        && this.millisecond == other.getMillisecond());
            }
            else {
                return false;
            }
        }

        /**
         * Returns a copy of ourselves or <code>null</code> if there was an
         * exception during cloning.
         *
         * @return A copy of this segment.
         */
        public Segment copy() {
            try {
                return (Segment) this.clone();
            }
            catch (CloneNotSupportedException e) {
                return null;
            }
        }

        /**
         * Will compare this Segment with another Segment (from Comparable
         * interface).
         *
         * @param object The other Segment to compare with
         *
         * @return -1: this < object, 0: this.equal(object) and
         *         +1: this > object
         */
        @Override
        public int compareTo(Object object) {
            Segment other = (Segment) object;
            if (this.before(other)) {
                return -1;
            }
            else if (this.after(other)) {
                return +1;
            }
            else {
                return 0;
            }
        }

        /**
         * Returns true if we are an included segment and we are not an
         * exception.
         *
         * @return <code>true</code> or <code>false</code>.
         */
        public boolean inIncludeSegments() {
            if (getSegmentNumberRelativeToGroup()
                    < SegmentedTimeline.this.segmentsIncluded) {
                return !inExceptionSegments();
            }
            else {
                return false;
            }
        }

        /**
         * Returns true if we are an excluded segment.
         *
         * @return <code>true</code> or <code>false</code>.
         */
        public boolean inExcludeSegments() {
            return getSegmentNumberRelativeToGroup()
                    >= SegmentedTimeline.this.segmentsIncluded;
        }

        /**
         * Calculate the segment number relative to the segment group. This
         * will be a number between 0 and segmentsGroup-1. This value is
         * calculated from the segmentNumber. Special care is taken for
         * negative segmentNumbers.
         *
         * @return The segment number.
         */
        private long getSegmentNumberRelativeToGroup() {
            long p = (this.segmentNumber
                    % SegmentedTimeline.this.groupSegmentCount);
            if (p < 0) {
                p += SegmentedTimeline.this.groupSegmentCount;
            }
            return p;
        }

        /**
         * Returns true if we are an exception segment. This is implemented via
         * a binary search on the exceptionSegments sorted list.
         *
         * If the segment is not listed as an exception in our list and we have
         * a baseTimeline, a check is performed to see if the segment is inside
         * an excluded segment from our base. If so, it is also considered an
         * exception.
         *
         * @return <code>true</code> if we are an exception segment.
         */
        public boolean inExceptionSegments() {
            return binarySearchExceptionSegments(this) >= 0;
        }

        /**
         * Increments the internal attributes of this segment by a number of
         * segments.
         *
         * @param n Number of segments to increment.
         */
        public void inc(long n) {
            this.segmentNumber += n;
            long m = n * SegmentedTimeline.this.segmentSize;
            this.segmentStart += m;
            this.segmentEnd += m;
            this.millisecond += m;
        }

        /**
         * Increments the internal attributes of this segment by one segment.
         * The exact time incremented is segmentSize.
         */
        public void inc() {
            inc(1);
        }

        /**
         * Decrements the internal attributes of this segment by a number of
         * segments.
         *
         * @param n Number of segments to decrement.
         */
        public void dec(long n) {
            this.segmentNumber -= n;
            long m = n * SegmentedTimeline.this.segmentSize;
            this.segmentStart -= m;
            this.segmentEnd -= m;
            this.millisecond -= m;
        }

        /**
         * Decrements the internal attributes of this segment by one segment.
         * The exact time decremented is segmentSize.
         */
        public void dec() {
            dec(1);
        }

        /**
         * Moves the index of this segment to the beginning if the segment.
         */
        public void moveIndexToStart() {
            this.millisecond = this.segmentStart;
        }

        /**
         * Moves the index of this segment to the end of the segment.
         */
        public void moveIndexToEnd() {
            this.millisecond = this.segmentEnd;
        }

    }

    /**
     * Private internal class to represent a range of segments. This class is
     * mainly used to store in one object a range of exception segments. This
     * optimizes certain timelines that use a small segment size (like an
     * intraday timeline) allowing them to express a day exception as one
     * SegmentRange instead of multi Segments.
     */
    protected class SegmentRange extends Segment {

        /** The number of segments in the range. */
        private long segmentCount;

        /**
         * Creates a SegmentRange between a start and end domain values.
         *
         * @param fromMillisecond  start of the range
         * @param toMillisecond  end of the range
         */
        public SegmentRange(long fromMillisecond, long toMillisecond) {

            Segment start = getSegment(fromMillisecond);
            Segment end = getSegment(toMillisecond);
//            if (start.getSegmentStart() != fromMillisecond
//                || end.getSegmentEnd() != toMillisecond) {
//                throw new IllegalArgumentException("Invalid Segment Range ["
//                    + fromMillisecond + "," + toMillisecond + "]");
//            }

            this.millisecond = fromMillisecond;
            this.segmentNumber = calculateSegmentNumber(fromMillisecond);
            this.segmentStart = start.segmentStart;
            this.segmentEnd = end.segmentEnd;
            this.segmentCount
                = (end.getSegmentNumber() - start.getSegmentNumber() + 1);
        }

        /**
         * Returns the number of segments contained in this range.
         *
         * @return The segment count.
         */
        @Override
        public long getSegmentCount() {
            return this.segmentCount;
        }

        /**
         * Returns a segment that is the intersection of this segment and the
         * interval.
         *
         * @param from  the start of the interval.
         * @param to  the end of the interval.
         *
         * @return The intersection.
         */
        @Override
        public Segment intersect(long from, long to) {

            // Segment fromSegment = getSegment(from);
            // fromSegment.inc();
            // Segment toSegment = getSegment(to);
            // toSegment.dec();
            long start = Math.max(from, this.segmentStart);
            long end = Math.min(to, this.segmentEnd);
            // long start = Math.max(
            //     fromSegment.getSegmentStart(), this.segmentStart
            // );
            // long end = Math.min(toSegment.getSegmentEnd(), this.segmentEnd);
            if (start <= end) {
                return new SegmentRange(start, end);
            }
            else {
                return null;
            }
        }

        /**
         * Returns true if all Segments of this SegmentRenge are an included
         * segment and are not an exception.
         *
         * @return <code>true</code> or </code>false</code>.
         */
        @Override
        public boolean inIncludeSegments() {
            for (Segment segment = getSegment(this.segmentStart);
                segment.getSegmentStart() < this.segmentEnd;
                segment.inc()) {
                if (!segment.inIncludeSegments()) {
                    return (false);
                }
            }
            return true;
        }

        /**
         * Returns true if we are an excluded segment.
         *
         * @return <code>true</code> or </code>false</code>.
         */
        @Override
        public boolean inExcludeSegments() {
            for (Segment segment = getSegment(this.segmentStart);
                segment.getSegmentStart() < this.segmentEnd;
                segment.inc()) {
                if (!segment.inExceptionSegments()) {
                    return (false);
                }
            }
            return true;
        }

        /**
         * Not implemented for SegmentRange. Always throws
         * IllegalArgumentException.
         *
         * @param n Number of segments to increment.
         */
        @Override
        public void inc(long n) {
            throw new IllegalArgumentException(
                    "Not implemented in SegmentRange");
        }

    }

    /**
     * Special <code>SegmentRange</code> that came from the BaseTimeline.
     */
    protected class BaseTimelineSegmentRange extends SegmentRange {

        /**
         * Constructor.
         *
         * @param fromDomainValue  the start value.
         * @param toDomainValue  the end value.
         */
        public BaseTimelineSegmentRange(long fromDomainValue,
                                        long toDomainValue) {
            super(fromDomainValue, toDomainValue);
        }

    }

}
