/* ======================================
 * JFreeChart : a free Java chart library
 * ======================================
 *
 * Project Info:  http://www.jfree.org/jfreechart/index.html
 * Project Lead:  David Gilbert (david.gilbert@object-refinery.com);
 *
 * (C) Copyright 2000-2003, by Object Refinery Limited and Contributors.
 *
 * 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., 59 Temple Place, Suite 330,
 * Boston, MA 02111-1307, USA.
 *
 * -----------------------
 * SegmentedTimeline.java
 * -----------------------
 * (C) Copyright 2003, by Bill Kelemen and Contributors.
 *
 * Original Author:  Bill Kelemen;
 * Contributor(s):   David Gilbert (for Object Refinery Limited);
 *
 * $Id: SegmentedTimeline.java,v 1.13 2003/09/11 08:45:10 mungady Exp $
 *
 * Changes
 * -------
 * 23-May-2003 : Version 1 (BK);
 * 15-Aug-2003 : Implemented Cloneable (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.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
 * 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
 *
 * @author Bill Kelemen
 */
public class SegmentedTimeline implements Timeline, Cloneable, Serializable {

    ////////////////////////////////////////////////////////////////////////////
    // 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.
     */
    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.
     */
    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.
     */
    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 = new GregorianCalendar(NO_DST_TIME_ZONE);

    /**
     * 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;

    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();
    }

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

    /**
     * Constructs a new segmented timeline, optionaly using another segmented
     * timeline as its base. This chaning 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;

    }

    /**
     * Factory method to create a Monday through Friday SegmentedTimeline.
     * <P>
     * The <code>startTime</code> of the resulting timeline will be midnight of the
     * firt 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(FIRST_MONDAY_AFTER_1900);
        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
     * firt 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(FIRST_MONDAY_AFTER_1900 + 36 * timeline.getSegmentSize());
        timeline.setBaseTimeline(newMondayThroughFridayTimeline());
        return timeline;
    }

    ////////////////////////////////////////////////////////////////////////////
    // 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.
     *