/*

 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code 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 General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Copyright (c) 2009-2012, Stephen Colebourne & Michael Nascimento Santos

 *

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are met:

 *

 *  * Redistributions of source code must retain the above copyright notice,

 *    this list of conditions and the following disclaimer.

 *

 *  * Redistributions in binary form must reproduce the above copyright notice,

 *    this list of conditions and the following disclaimer in the documentation

 *    and/or other materials provided with the distribution.

 *

 *  * Neither the name of JSR-310 nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF

 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING

 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

package java.time.zone;

import java.io.DataInput;

import java.io.DataOutput;

import java.io.IOException;

import java.io.Serializable;

import java.time.Duration;

import java.time.Instant;

import java.time.LocalDate;

import java.time.LocalDateTime;

import java.time.ZoneId;

import java.time.ZoneOffset;

import java.time.Year;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.List;

import java.util.Objects;

import java.util.concurrent.ConcurrentHashMap;

import java.util.concurrent.ConcurrentMap;

/**

 * The rules defining how the zone offset varies for a single time-zone.

 * <p>

 * The rules model all the historic and future transitions for a time-zone.

 * {@link ZoneOffsetTransition} is used for known transitions, typically historic.

 * {@link ZoneOffsetTransitionRule} is used for future transitions that are based

 * on the result of an algorithm.

 * <p>

 * The rules are loaded via {@link ZoneRulesProvider} using a {@link ZoneId}.

 * The same rules may be shared internally between multiple zone IDs.

 * <p>

 * Serializing an instance of {@code ZoneRules} will store the entire set of rules.

 * It does not store the zone ID as it is not part of the state of this object.

 * <p>

 * A rule implementation may or may not store full information about historic

 * and future transitions, and the information stored is only as accurate as

 * that supplied to the implementation by the rules provider.

 * Applications should treat the data provided as representing the best information

 * available to the implementation of this rule.

 *

 * This class is immutable and thread-safe.

 *

 * @since 1.8

 */

public final class ZoneRules implements Serializable {

    /**

     * Serialization version.

     */

    private static final long serialVersionUID = 3044319355680032515L;

    /**

     * The last year to have its transitions cached.

     */

    private static final int LAST_CACHED_YEAR = 2100;

    /**

     * The transitions between standard offsets (epoch seconds), sorted.

     */

    private final long[] standardTransitions;

    /**

     * The standard offsets.

     */

    private final ZoneOffset[] standardOffsets;

    /**

     * The transitions between instants (epoch seconds), sorted.

     */

    private final long[] savingsInstantTransitions;

    /**

     * The transitions between local date-times, sorted.

     * This is a paired array, where the first entry is the start of the transition

     * and the second entry is the end of the transition.

     */

    private final LocalDateTime[] savingsLocalTransitions;

    /**

     * The wall offsets.

     */

    private final ZoneOffset[] wallOffsets;

    /**

     * The last rule.

     */

    private final ZoneOffsetTransitionRule[] lastRules;

    /**

     * The map of recent transitions.

     */

    private final ConcurrentMap<Integer, ZoneOffsetTransition[]> lastRulesCache =

                new ConcurrentHashMap<Integer, ZoneOffsetTransition[]>();

    /**

     * The zero-length long array.

     */

    private static final long[] EMPTY_LONG_ARRAY = new long[0];

    /**

     * The zero-length lastrules array.

     */

    private static final ZoneOffsetTransitionRule[] EMPTY_LASTRULES =

        new ZoneOffsetTransitionRule[0];

    /**

     * The zero-length ldt array.

     */

    private static final LocalDateTime[] EMPTY_LDT_ARRAY = new LocalDateTime[0];

    /**

     * Obtains an instance of a ZoneRules.

     *

     * @param baseStandardOffset  the standard offset to use before legal rules were set, not null

     * @param baseWallOffset  the wall offset to use before legal rules were set, not null

     * @param standardOffsetTransitionList  the list of changes to the standard offset, not null

     * @param transitionList  the list of transitions, not null

     * @param lastRules  the recurring last rules, size 16 or less, not null

     * @return the zone rules, not null

     */

    public static ZoneRules of(ZoneOffset baseStandardOffset,

                               ZoneOffset baseWallOffset,

                               List<ZoneOffsetTransition> standardOffsetTransitionList,

                               List<ZoneOffsetTransition> transitionList,

                               List<ZoneOffsetTransitionRule> lastRules) {

        Objects.requireNonNull(baseStandardOffset, "baseStandardOffset");

        Objects.requireNonNull(baseWallOffset, "baseWallOffset");

        Objects.requireNonNull(standardOffsetTransitionList, "standardOffsetTransitionList");

        Objects.requireNonNull(transitionList, "transitionList");

        Objects.requireNonNull(lastRules, "lastRules");

        return new ZoneRules(baseStandardOffset, baseWallOffset,

                             standardOffsetTransitionList, transitionList, lastRules);

    }

    /**

     * Obtains an instance of ZoneRules that has fixed zone rules.

     *

     * @param offset  the offset this fixed zone rules is based on, not null

     * @return the zone rules, not null

     * @see #isFixedOffset()

     */

    public static ZoneRules of(ZoneOffset offset) {

        Objects.requireNonNull(offset, "offset");

        return new ZoneRules(offset);

    }

    /**

     * Creates an instance.

     *

     * @param baseStandardOffset  the standard offset to use before legal rules were set, not null

     * @param baseWallOffset  the wall offset to use before legal rules were set, not null

     * @param standardOffsetTransitionList  the list of changes to the standard offset, not null

     * @param transitionList  the list of transitions, not null

     * @param lastRules  the recurring last rules, size 16 or less, not null

     */

    ZoneRules(ZoneOffset baseStandardOffset,

              ZoneOffset baseWallOffset,

              List<ZoneOffsetTransition> standardOffsetTransitionList,

              List<ZoneOffsetTransition> transitionList,

              List<ZoneOffsetTransitionRule> lastRules) {

        super();

        // convert standard transitions

        this.standardTransitions = new long[standardOffsetTransitionList.size()];

        this.standardOffsets = new ZoneOffset[standardOffsetTransitionList.size() + 1];

        this.standardOffsets[0] = baseStandardOffset;

        for (int i = 0; i < standardOffsetTransitionList.size(); i++) {

            this.standardTransitions[i] = standardOffsetTransitionList.get(i).toEpochSecond();

            this.standardOffsets[i + 1] = standardOffsetTransitionList.get(i).getOffsetAfter();

        }

        // convert savings transitions to locals

        List<LocalDateTime> localTransitionList = new ArrayList<>();

        List<ZoneOffset> localTransitionOffsetList = new ArrayList<>();

        localTransitionOffsetList.add(baseWallOffset);

        for (ZoneOffsetTransition trans : transitionList) {

            if (trans.isGap()) {

                localTransitionList.add(trans.getDateTimeBefore());

                localTransitionList.add(trans.getDateTimeAfter());

            } else {

                localTransitionList.add(trans.getDateTimeAfter());

                localTransitionList.add(trans.getDateTimeBefore());

            }

            localTransitionOffsetList.add(trans.getOffsetAfter());

        }

        this.savingsLocalTransitions = localTransitionList.toArray(new LocalDateTime[localTransitionList.size()]);

        this.wallOffsets = localTransitionOffsetList.toArray(new ZoneOffset[localTransitionOffsetList.size()]);

        // convert savings transitions to instants

        this.savingsInstantTransitions = new long[transitionList.size()];

        for (int i = 0; i < transitionList.size(); i++) {

            this.savingsInstantTransitions[i] = transitionList.get(i).toEpochSecond();

        }

        // last rules

        if (lastRules.size() > 16) {

            throw new IllegalArgumentException("Too many transition rules");

        }

        this.lastRules = lastRules.toArray(new ZoneOffsetTransitionRule[lastRules.size()]);

    }

    /**

     * Constructor.

     *

     * @param standardTransitions  the standard transitions, not null

     * @param standardOffsets  the standard offsets, not null

     * @param savingsInstantTransitions  the standard transitions, not null

     * @param wallOffsets  the wall offsets, not null

     * @param lastRules  the recurring last rules, size 15 or less, not null

     */

    private ZoneRules(long[] standardTransitions,

                      ZoneOffset[] standardOffsets,

                      long[] savingsInstantTransitions,

                      ZoneOffset[] wallOffsets,

                      ZoneOffsetTransitionRule[] lastRules) {

        super();

        this.standardTransitions = standardTransitions;

        this.standardOffsets = standardOffsets;

        this.savingsInstantTransitions = savingsInstantTransitions;

        this.wallOffsets = wallOffsets;

        this.lastRules = lastRules;

        if (savingsInstantTransitions.length == 0) {

            this.savingsLocalTransitions = EMPTY_LDT_ARRAY;

        } else {

            // convert savings transitions to locals

            List<LocalDateTime> localTransitionList = new ArrayList<>();

            for (int i = 0; i < savingsInstantTransitions.length; i++) {

                ZoneOffset before = wallOffsets[i];

                ZoneOffset after = wallOffsets[i + 1];

                ZoneOffsetTransition trans = new ZoneOffsetTransition(savingsInstantTransitions[i], before, after);

                if (trans.isGap()) {

                    localTransitionList.add(trans.getDateTimeBefore());

                    localTransitionList.add(trans.getDateTimeAfter());

                } else {

                    localTransitionList.add(trans.getDateTimeAfter());

                    localTransitionList.add(trans.getDateTimeBefore());

               }

            }

            this.savingsLocalTransitions = localTransitionList.toArray(new LocalDateTime[localTransitionList.size()]);

        }

    }

    /**

     * Creates an instance of ZoneRules that has fixed zone rules.

     *

     * @param offset  the offset this fixed zone rules is based on, not null

     * @return the zone rules, not null

     * @see #isFixedOffset()

     */

    private ZoneRules(ZoneOffset offset) {

        this.standardOffsets = new ZoneOffset[1];

        this.standardOffsets[0] = offset;

        this.standardTransitions = EMPTY_LONG_ARRAY;

        this.savingsInstantTransitions = EMPTY_LONG_ARRAY;

        this.savingsLocalTransitions = EMPTY_LDT_ARRAY;

        this.wallOffsets = standardOffsets;

        this.lastRules = EMPTY_LASTRULES;

    }

    /**

     * Uses a serialization delegate.

     *

     * @return the replacing object, not null

     */

    private Object writeReplace() {

        return new Ser(Ser.ZRULES, this);

    }

    /**

     * Writes the state to the stream.

     *

     * @param out  the output stream, not null

     * @throws IOException if an error occurs

     */

    void writeExternal(DataOutput out) throws IOException {

        out.writeInt(standardTransitions.length);

        for (long trans : standardTransitions) {

            Ser.writeEpochSec(trans, out);

        }

        for (ZoneOffset offset : standardOffsets) {

            Ser.writeOffset(offset, out);

        }

        out.writeInt(savingsInstantTransitions.length);

        for (long trans : savingsInstantTransitions) {

            Ser.writeEpochSec(trans, out);

        }

        for (ZoneOffset offset : wallOffsets) {

            Ser.writeOffset(offset, out);

        }

        out.writeByte(lastRules.length);

        for (ZoneOffsetTransitionRule rule : lastRules) {

            rule.writeExternal(out);

        }

    }

    /**

     * Reads the state from the stream.

     *

     * @param in  the input stream, not null

     * @return the created object, not null

     * @throws IOException if an error occurs

     */

    static ZoneRules readExternal(DataInput in) throws IOException, ClassNotFoundException {

        int stdSize = in.readInt();

        long[] stdTrans = (stdSize == 0) ? EMPTY_LONG_ARRAY

                                         : new long[stdSize];

        for (int i = 0; i < stdSize; i++) {

            stdTrans[i] = Ser.readEpochSec(in);

        }

        ZoneOffset[] stdOffsets = new ZoneOffset[stdSize + 1];

        for (int i = 0; i < stdOffsets.length; i++) {

            stdOffsets[i] = Ser.readOffset(in);

        }

        int savSize = in.readInt();

        long[] savTrans = (savSize == 0) ? EMPTY_LONG_ARRAY

                                         : new long[savSize];

        for (int i = 0; i < savSize; i++) {

            savTrans[i] = Ser.readEpochSec(in);

        }

        ZoneOffset[] savOffsets = new ZoneOffset[savSize + 1];

        for (int i = 0; i < savOffsets.length; i++) {

            savOffsets[i] = Ser.readOffset(in);

        }

        int ruleSize = in.readByte();

        ZoneOffsetTransitionRule[] rules = (ruleSize == 0) ?

            EMPTY_LASTRULES : new ZoneOffsetTransitionRule[ruleSize];

        for (int i = 0; i < ruleSize; i++) {

            rules[i] = ZoneOffsetTransitionRule.readExternal(in);

        }

        return new ZoneRules(stdTrans, stdOffsets, savTrans, savOffsets, rules);

    }

    /**

     * Checks of the zone rules are fixed, such that the offset never varies.

     *

     * @return true if the time-zone is fixed and the offset never changes

     */

    public boolean isFixedOffset() {

        return savingsInstantTransitions.length == 0;

    }

    /**

     * Gets the offset applicable at the specified instant in these rules.

     * <p>

     * The mapping from an instant to an offset is simple, there is only

     * one valid offset for each instant.

     * This method returns that offset.

     *

     * @param instant  the instant to find the offset for, not null, but null

     *  may be ignored if the rules have a single offset for all instants

     * @return the offset, not null

     */

    public ZoneOffset getOffset(Instant instant) {

        if (savingsInstantTransitions.length == 0) {

            return standardOffsets[0];

        }

        long epochSec = instant.getEpochSecond();

        // check if using last rules

        if (lastRules.length > 0 &&

                epochSec > savingsInstantTransitions[savingsInstantTransitions.length - 1]) {

            int year = findYear(epochSec, wallOffsets[wallOffsets.length - 1]);

            ZoneOffsetTransition[] transArray = findTransitionArray(year);

            ZoneOffsetTransition trans = null;

            for (int i = 0; i < transArray.length; i++) {

                trans = transArray[i];

                if (epochSec < trans.toEpochSecond()) {

                    return trans.getOffsetBefore();

                }

            }

            return trans.getOffsetAfter();

        }

        // using historic rules

        int index  = Arrays.binarySearch(savingsInstantTransitions, epochSec);

        if (index < 0) {

            // switch negative insert position to start of matched range

            index = -index - 2;

        }

        return wallOffsets[index + 1];

    }

    /**

     * Gets a suitable offset for the specified local date-time in these rules.

     * <p>

     * The mapping from a local date-time to an offset is not straightforward.

     * There are three cases:

     * <p><ul>

     * <li>Normal, with one valid offset. For the vast majority of the year, the normal

     *  case applies, where there is a single valid offset for the local date-time.</li>

     * <li>Gap, with zero valid offsets. This is when clocks jump forward typically

     *  due to the spring daylight savings change from "winter" to "summer".

     *  In a gap there are local date-time values with no valid offset.</li>

     * <li>Overlap, with two valid offsets. This is when clocks are set back typically

     *  due to the autumn daylight savings change from "summer" to "winter".

     *  In an overlap there are local date-time values with two valid offsets.</li>

     * </ul><p>

     * Thus, for any given local date-time there can be zero, one or two valid offsets.

     * This method returns the single offset in the Normal case, and in the Gap or Overlap

     * case it returns the offset before the transition.

     * <p>

     * Since, in the case of Gap and Overlap, the offset returned is a "best" value, rather

     * than the "correct" value, it should be treated with care. Applications that care

     * about the correct offset should use a combination of this method,

     * {@link #getValidOffsets(LocalDateTime)} and {@link #getTransition(LocalDateTime)}.

     *

     * @param localDateTime  the local date-time to query, not null, but null

     *  may be ignored if the rules have a single offset for all instants

     * @return the best available offset for the local date-time, not null

     */

    public ZoneOffset getOffset(LocalDateTime localDateTime) {

        Object info = getOffsetInfo(localDateTime);

        if (info instanceof ZoneOffsetTransition) {

            return ((ZoneOffsetTransition) info).getOffsetBefore();

        }

        return (ZoneOffset) info;

    }

    /**

     * Gets the offset applicable at the specified local date-time in these rules.

     * <p>

     * The mapping from a local date-time to an offset is not straightforward.

     * There are three cases:

     * <p><ul>

     * <li>Normal, with one valid offset. For the vast majority of the year, the normal

     *  case applies, where there is a single valid offset for the local date-time.</li>

     * <li>Gap, with zero valid offsets. This is when clocks jump forward typically

     *  due to the spring daylight savings change from "winter" to "summer".

     *  In a gap there are local date-time values with no valid offset.</li>

     * <li>Overlap, with two valid offsets. This is when clocks are set back typically

     *  due to the autumn daylight savings change from "summer" to "winter".

     *  In an overlap there are local date-time values with two valid offsets.</li>

     * </ul><p>

     * Thus, for any given local date-time there can be zero, one or two valid offsets.

     * This method returns that list of valid offsets, which is a list of size 0, 1 or 2.

     * In the case where there are two offsets, the earlier offset is returned at index 0

     * and the later offset at index 1.

     * <p>

     * There are various ways to handle the conversion from a {@code LocalDateTime}.

     * One technique, using this method, would be:

     * <pre>

     *  List<ZoneOffset> validOffsets = rules.getOffset(localDT);

     *  if (validOffsets.size() == 1) {

     *    // Normal case: only one valid offset

     *    zoneOffset = validOffsets.get(0);

     *  } else {

     *    // Gap or Overlap: determine what to do from transition (which will be non-null)

     *    ZoneOffsetTransition trans = rules.getTransition(localDT);

     *  }

     * </pre>

     * <p>

     * In theory, it is possible for there to be more than two valid offsets.

     * This would happen if clocks to be put back more than once in quick succession.

     * This has never happened in the history of time-zones and thus has no special handling.

     * However, if it were to happen, then the list would return more than 2 entries.

     *

     * @param localDateTime  the local date-time to query for valid offsets, not null, but null

     *  may be ignored if the rules have a single offset for all instants

     * @return the list of valid offsets, may be immutable, not null

     */

    public List<ZoneOffset> getValidOffsets(LocalDateTime localDateTime) {

        // should probably be optimized

        Object info = getOffsetInfo(localDateTime);

        if (info instanceof ZoneOffsetTransition) {

            return ((ZoneOffsetTransition) info).getValidOffsets();

        }

        return Collections.singletonList((ZoneOffset) info);

    }

    /**

     * Gets the offset transition applicable at the specified local date-time in these rules.

     * <p>