// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html#License
 /*
  *******************************************************************************
  * Copyright (C) 2005-2016, International Business Machines Corporation and
  * others. All Rights Reserved.
  *******************************************************************************
  */
package com.ibm.icu.impl;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.util.Arrays;
import java.util.Date;
import java.util.MissingResourceException;

import com.ibm.icu.util.AnnualTimeZoneRule;
import com.ibm.icu.util.BasicTimeZone;
import com.ibm.icu.util.Calendar;
import com.ibm.icu.util.DateTimeRule;
import com.ibm.icu.util.GregorianCalendar;
import com.ibm.icu.util.InitialTimeZoneRule;
import com.ibm.icu.util.SimpleTimeZone;
import com.ibm.icu.util.TimeArrayTimeZoneRule;
import com.ibm.icu.util.TimeZone;
import com.ibm.icu.util.TimeZoneRule;
import com.ibm.icu.util.TimeZoneTransition;
import com.ibm.icu.util.UResourceBundle;

/**
 * A time zone based on the Olson tz database.  Olson time zones change
 * behavior over time.  The raw offset, rules, presence or absence of
 * daylight savings time, and even the daylight savings amount can all
 * vary.
 *
 * This class uses a resource bundle named "zoneinfo".  Zoneinfo is a
 * table containing different kinds of resources.  In several places,
 * zones are referred to using integers.  A zone's integer is a number
 * from 0..n-1, where n is the number of zones, with the zones sorted
 * in lexicographic order.
 *
 * 1. Zones.  These have keys corresponding to the Olson IDs, e.g.,
 * "Asia/Shanghai".  Each resource describes the behavior of the given
 * zone.  Zones come in two different formats.
 *
 *   a. Zone (table).  A zone is a table resource contains several
 *   type of resources below:
 *  
 *   - typeOffsets:intvector (Required)
 *  
 *   Sets of UTC raw/dst offset pairs in seconds.  Entries at
 *   2n represents raw offset and 2n+1 represents dst offset
 *   paired with the raw offset at 2n.  The very first pair represents
 *   the initial zone offset (before the first transition) always.
 *
 *   - trans:intvector (Optional) 
 *  
 *   List of transition times represented by 32bit seconds from the
 *   epoch (1970-01-01T00:00Z) in ascending order.
 *  
 *   - transPre32/transPost32:intvector (Optional)
 *  
 *   List of transition times before/after 32bit minimum seconds.
 *   Each time is represented by a pair of 32bit integer.
 * 
 *   - typeMap:bin (Optional)
 *  
 *   Array of bytes representing the mapping between each transition
 *   time (transPre32/trans/transPost32) and its corresponding offset
 *   data (typeOffsets).
 *  
 *   - finalRule:string (Optional)
 *  
 *   If a recurrent transition rule is applicable to a zone forever
 *   after the final transition time, finalRule represents the rule
 *   in Rules data.
 *  
 *   - finalRaw:int (Optional)
 *   
 *   When finalRule is available, finalRaw is required and specifies
 *   the raw (base) offset of the rule.
 *   
 *   - finalYear:int (Optional)
 *   
 *   When finalRule is available, finalYear is required and specifies
 *   the start year of the rule.
 *   
 *   - links:intvector (Optional)
 *   
 *   When this zone data is shared with other zones, links specifies
 *   all zones including the zone itself.  Each zone is referenced by
 *   integer index.
 * 
 *  b. Link (int, length 1).  A link zone is an int resource.  The
 *  integer is the zone number of the target zone.  The key of this
 *  resource is an alternate name for the target zone.  This data
 *  is corresponding to Link data in the tz database.
 *
 *
 * 2. Rules.  These have keys corresponding to the Olson rule IDs,
 * with an underscore prepended, e.g., "_EU".  Each resource describes
 * the behavior of the given rule using an intvector, containing the
 * onset list, the cessation list, and the DST savings.  The onset and
 * cessation lists consist of the month, dowim, dow, time, and time
 * mode.  The end result is that the 11 integers describing the rule
 * can be passed directly into the SimpleTimeZone 13-argument
 * constructor (the other two arguments will be the raw offset, taken
 * from the complex zone element 5, and the ID string, which is not
 * used), with the times and the DST savings multiplied by 1000 to
 * scale from seconds to milliseconds.
 *
 * 3. Regions.  An array specifies mapping between zones and regions.
 * Each item is either a 2-letter ISO country code or "001"
 * (UN M.49 - World).  This data is generated from "zone.tab"
 * in the tz database.
 */
public class OlsonTimeZone extends BasicTimeZone {

    // Generated by serialver from JDK 1.4.1_01
    static final long serialVersionUID = -6281977362477515376L;

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#getOffset(int, int, int, int, int, int)
     */
    @Override
    public int getOffset(int era, int year, int month, int day, int dayOfWeek, int milliseconds) {
        if (month < Calendar.JANUARY || month > Calendar.DECEMBER) {
            throw new IllegalArgumentException("Month is not in the legal range: " +month);
        } else {
            return getOffset(era, year, month, day, dayOfWeek, milliseconds, Grego.monthLength(year, month));
        }
    }

    /**
     * TimeZone API.
     */
    public int getOffset(int era, int year, int month,int dom, int dow, int millis, int monthLength){

        if ((era != GregorianCalendar.AD && era != GregorianCalendar.BC)
            || month < Calendar.JANUARY
            || month > Calendar.DECEMBER
            || dom < 1
            || dom > monthLength
            || dow < Calendar.SUNDAY
            || dow > Calendar.SATURDAY
            || millis < 0
            || millis >= Grego.MILLIS_PER_DAY
            || monthLength < 28
            || monthLength > 31) {
            throw new IllegalArgumentException();
        }

        if (era == GregorianCalendar.BC) {
            year = -year;
        }

        if (finalZone != null && year >= finalStartYear) {
            return finalZone.getOffset(era, year, month, dom, dow, millis);
        }

        // Compute local epoch millis from input fields
        long time = Grego.fieldsToDay(year, month, dom) * Grego.MILLIS_PER_DAY + millis;

        int[] offsets = new int[2];
        getHistoricalOffset(time, true, LOCAL_DST, LOCAL_STD, offsets);
        return offsets[0] + offsets[1];
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#setRawOffset(int)
     */
    @Override
    public void setRawOffset(int offsetMillis) {
        if (isFrozen()) {
            throw new UnsupportedOperationException("Attempt to modify a frozen OlsonTimeZone instance.");
        }

        if (getRawOffset() == offsetMillis) {
            return;
        }
        long current = System.currentTimeMillis();

        if (current < finalStartMillis) {
            SimpleTimeZone stz = new SimpleTimeZone(offsetMillis, getID());

            boolean bDst = useDaylightTime();
            if (bDst) {
                TimeZoneRule[] currentRules = getSimpleTimeZoneRulesNear(current);
                if (currentRules.length != 3) {
                    // DST was observed at the beginning of this year, so useDaylightTime
                    // returned true.  getSimpleTimeZoneRulesNear requires at least one
                    // future transition for making a pair of rules.  This implementation
                    // rolls back the time before the latest offset transition.
                    TimeZoneTransition tzt = getPreviousTransition(current, false);
                    if (tzt != null) {
                        currentRules = getSimpleTimeZoneRulesNear(tzt.getTime() - 1);
                    }
                }
                if (currentRules.length == 3
                        && (currentRules[1] instanceof AnnualTimeZoneRule)
                        && (currentRules[2] instanceof AnnualTimeZoneRule)) {
                    // A pair of AnnualTimeZoneRule
                    AnnualTimeZoneRule r1 = (AnnualTimeZoneRule)currentRules[1];
                    AnnualTimeZoneRule r2 = (AnnualTimeZoneRule)currentRules[2];
                    DateTimeRule start, end;
                    int offset1 = r1.getRawOffset() + r1.getDSTSavings();
                    int offset2 = r2.getRawOffset() + r2.getDSTSavings();
                    int sav;
                    if (offset1 > offset2) {
                        start = r1.getRule();
                        end = r2.getRule();
                        sav = offset1 - offset2;
                    } else {
                        start = r2.getRule();
                        end = r1.getRule();
                        sav = offset2 - offset1;
                    }
                    // getSimpleTimeZoneRulesNear always return rules using DOW / WALL_TIME
                    stz.setStartRule(start.getRuleMonth(), start.getRuleWeekInMonth(), start.getRuleDayOfWeek(),
                                            start.getRuleMillisInDay());
                    stz.setEndRule(end.getRuleMonth(), end.getRuleWeekInMonth(), end.getRuleDayOfWeek(),
                                            end.getRuleMillisInDay());
                    // set DST saving amount and start year
                    stz.setDSTSavings(sav);
                } else {
                    // This could only happen if last rule is DST
                    // and the rule used forever.  For example, Asia/Dhaka
                    // in tzdata2009i stays in DST forever.

                    // Hack - set DST starting at midnight on Jan 1st,
                    // ending 23:59:59.999 on Dec 31st
                    stz.setStartRule(0, 1, 0);
                    stz.setEndRule(11, 31, Grego.MILLIS_PER_DAY - 1);
                }
            }

            int[] fields = Grego.timeToFields(current, null);

            finalStartYear = fields[0];
            finalStartMillis = Grego.fieldsToDay(fields[0], 0, 1);

            if (bDst) {
                // we probably do not need to set start year of final rule
                // to finalzone itself, but we always do this for now.
                stz.setStartYear(finalStartYear);
            }

            finalZone = stz;

        } else {
            finalZone.setRawOffset(offsetMillis);
        }

        transitionRulesInitialized = false;
    }

    @Override
    public Object clone() {
        if (isFrozen()) {
            return this;
        }
        return cloneAsThawed();
    }

    /**
     * TimeZone API.
     */
    @Override
    public void getOffset(long date, boolean local, int[] offsets)  {
        if (finalZone != null && date >= finalStartMillis) {
            finalZone.getOffset(date, local, offsets);
        } else {
            getHistoricalOffset(date, local,
                    LOCAL_FORMER, LOCAL_LATTER, offsets);
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void getOffsetFromLocal(long date,
            int nonExistingTimeOpt, int duplicatedTimeOpt, int[] offsets) {
        if (finalZone != null && date >= finalStartMillis) {
            finalZone.getOffsetFromLocal(date, nonExistingTimeOpt, duplicatedTimeOpt, offsets);
        } else {
            getHistoricalOffset(date, true, nonExistingTimeOpt, duplicatedTimeOpt, offsets);
        }
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#getRawOffset()
     */
    @Override
    public int getRawOffset() {
        int[] ret = new int[2];
        getOffset(System.currentTimeMillis(), false, ret);
        return ret[0];
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#useDaylightTime()
     */
    @Override
    public boolean useDaylightTime() {
        // If DST was observed in 1942 (for example) but has never been
        // observed from 1943 to the present, most clients will expect
        // this method to return FALSE.  This method determines whether
        // DST is in use in the current year (at any point in the year)
        // and returns TRUE if so.
        long current = System.currentTimeMillis();

        if (finalZone != null && current >= finalStartMillis) {
            return (finalZone != null && finalZone.useDaylightTime());
        }

        int[] fields = Grego.timeToFields(current, null);

        // Find start of this year, and start of next year
        long start = Grego.fieldsToDay(fields[0], 0, 1) * SECONDS_PER_DAY;    
        long limit = Grego.fieldsToDay(fields[0] + 1, 0, 1) * SECONDS_PER_DAY;    

        // Return TRUE if DST is observed at any time during the current
        // year.
        for (int i = 0; i < transitionCount; ++i) {
            if (transitionTimes64[i] >= limit) {
                break;
            }
            if ((transitionTimes64[i] >= start && dstOffsetAt(i) != 0)
                    || (transitionTimes64[i] > start && i > 0 && dstOffsetAt(i - 1) != 0)) {
                return true;
            }
        }
        return false;
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#observesDaylightTime()
     */
    @Override
    public boolean observesDaylightTime() {
        long current = System.currentTimeMillis();

        if (finalZone != null) {
            if (finalZone.useDaylightTime()) {
                return true;
            } else if (current >= finalStartMillis) {
                return false;
            }
        }

        // Return TRUE if DST is observed at any future time
        long currentSec = Grego.floorDivide(current, Grego.MILLIS_PER_SECOND);
        int trsIdx = transitionCount - 1;
        if (dstOffsetAt(trsIdx) != 0) {
            return true;
        }
        while (trsIdx >= 0) {
            if (transitionTimes64[trsIdx] <= currentSec) {
                break;
            }
            if (dstOffsetAt(trsIdx - 1) != 0) {
                return true;
            }
            trsIdx--;
        }
        return false;
    }
    /**
     * TimeZone API
     * Returns the amount of time to be added to local standard time
     * to get local wall clock time.
     */
    @Override
    public int getDSTSavings() {
        if (finalZone != null){
            return finalZone.getDSTSavings();
        }
        return super.getDSTSavings();
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#inDaylightTime(java.util.Date)
     */
    @Override
    public boolean inDaylightTime(Date date) {
        int[] temp = new int[2];
        getOffset(date.getTime(), false, temp);
        return temp[1] != 0;
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#hasSameRules(com.ibm.icu.util.TimeZone)
     */
    @Override
    public boolean hasSameRules(TimeZone other) {
        if (this == other) {
            return true;
        }
        // The super class implementation only check raw offset and
        // use of daylight saving time.
        if (!super.hasSameRules(other)) {
            return false;
        }

        if (!(other instanceof OlsonTimeZone)) {
            // We cannot reasonably compare rules in different types
            return false;
        }

        // Check final zone
        OlsonTimeZone o = (OlsonTimeZone)other;
        if (finalZone == null) {
            if (o.finalZone != null) {
                return false;
            }
        } else {
            if (o.finalZone == null
                    || finalStartYear != o.finalStartYear
                    || !(finalZone.hasSameRules(o.finalZone))) {
                return false;
            }
        }
        // Check transitions
        // Note: The code below actually fails to compare two equivalent rules in
        // different representation properly.
        if (transitionCount != o.transitionCount ||
                !Arrays.equals(transitionTimes64, o.transitionTimes64) ||
                typeCount != o.typeCount ||
                !Arrays.equals(typeMapData, o.typeMapData) ||
                !Arrays.equals(typeOffsets, o.typeOffsets)){
            return false;
        }
        return true;
    }

    /**
     * Returns the canonical ID of this system time zone
     */
    public String getCanonicalID() {
        if (canonicalID == null) {
            synchronized(this) {
                if (canonicalID == null) {
                    canonicalID = getCanonicalID(getID());

                    assert(canonicalID != null);
                    if (canonicalID == null) {
                        // This should never happen...
                        canonicalID = getID();
                    }
                }
            }
        }
        return canonicalID;
    }

    /**
     * Construct a GMT+0 zone with no transitions.  This is done when a
     * constructor fails so the resultant object is well-behaved.
     */
    private void constructEmpty(){
        transitionCount = 0;
        transitionTimes64 = null;
        typeMapData =  null;

        typeCount = 1;
        typeOffsets = new int[]{0,0};
        finalZone = null;
        finalStartYear = Integer.MAX_VALUE;
        finalStartMillis = Double.MAX_VALUE;

        transitionRulesInitialized = false;
    }

    /**
     * Construct from a resource bundle
     * @param top the top-level zoneinfo resource bundle.  This is used
     * to lookup the rule that `res' may refer to, if there is one.
     * @param res the resource bundle of the zone to be constructed
     * @param id time zone ID
     */
    public OlsonTimeZone(UResourceBundle top, UResourceBundle res, String id){
        super(id);
        construct(top, res);
    }

    private void construct(UResourceBundle top, UResourceBundle res){
        
        if ((top == null || res == null)) {
            throw new IllegalArgumentException();
        }
        if(DEBUG) System.out.println("OlsonTimeZone(" + res.getKey() +")");

        UResourceBundle r;
        int[] transPre32, trans32, transPost32;
        transPre32 = trans32 = transPost32 = null;

        transitionCount = 0;

        // Pre-32bit second transitions
        try {
            r = res.get("transPre32");
            transPre32 = r.getIntVector();
            if (transPre32.length % 2 != 0) {
                // elements in the pre-32bit must be an even number
                throw new IllegalArgumentException("Invalid Format");
            }
            transitionCount += transPre32.length / 2;
        } catch (MissingResourceException e) {
            // Pre-32bit transition data is optional
        }

        // 32bit second transitions
        try {
            r = res.get("trans");
            trans32 = r.getIntVector();
            transitionCount += trans32.length;
        } catch (MissingResourceException e) {
            // 32bit transition data is optional
        }

        // Post-32bit second transitions
        try {
            r = res.get("transPost32");
            transPost32 = r.getIntVector();
            if (transPost32.length % 2 != 0) {
                // elements in the post-32bit must be an even number
                throw new IllegalArgumentException("Invalid Format");
            }
            transitionCount += transPost32.length / 2;
        } catch (MissingResourceException e) {
            // Post-32bit transition data is optional
        }

        if (transitionCount > 0) {
            transitionTimes64 = new long[transitionCount];
            int idx = 0;
            if (transPre32 != null) {
                for (int i = 0; i < transPre32.length / 2; i++, idx++) {
                    transitionTimes64[idx] = 
                        (((long)transPre32[i * 2]) & 0x00000000FFFFFFFFL) << 32
                        | (((long)transPre32[i * 2 + 1]) & 0x00000000FFFFFFFFL);
                }
            }
            if (trans32 != null) {
                for (int i = 0; i < trans32.length; i++, idx++) {
                    transitionTimes64[idx] = (long)trans32[i];
                }
            }
            if (transPost32 != null) {
                for (int i = 0; i < transPost32.length / 2; i++, idx++) {
                    transitionTimes64[idx] = 
                        (((long)transPost32[i * 2]) & 0x00000000FFFFFFFFL) << 32
                        | (((long)transPost32[i * 2 + 1]) & 0x00000000FFFFFFFFL);
                }
            }
        } else {
            transitionTimes64 = null;
        }

        // Type offsets list must be of even size, with size >= 2
        r = res.get("typeOffsets");
        typeOffsets = r.getIntVector();
        if ((typeOffsets.length < 2 || typeOffsets.length > 0x7FFE || typeOffsets.length % 2 != 0)) {
            throw new IllegalArgumentException("Invalid Format");
        }
        typeCount = typeOffsets.length / 2;

        // Type map data must be of the same size as the transition count
        if (transitionCount > 0) {
            r = res.get("typeMap");
            typeMapData = r.getBinary(null);
            if (typeMapData.length != transitionCount) {
                throw new IllegalArgumentException("Invalid Format");
            }
        } else {
            typeMapData = null;
        }

        // Process final rule and data, if any
        finalZone = null;
        finalStartYear = Integer.MAX_VALUE;
        finalStartMillis = Double.MAX_VALUE;

        String ruleID = null;
        try {
            ruleID = res.getString("finalRule");

            r = res.get("finalRaw");
            int ruleRaw = r.getInt() * Grego.MILLIS_PER_SECOND;
            r = loadRule(top, ruleID);
            int[] ruleData = r.getIntVector();

            if (ruleData == null || ruleData.length != 11) {
                throw new IllegalArgumentException("Invalid Format");
            }
            finalZone = new SimpleTimeZone(ruleRaw, "",
                    ruleData[0], ruleData[1], ruleData[2],
                    ruleData[3] * Grego.MILLIS_PER_SECOND,
                    ruleData[4],
                    ruleData[5], ruleData[6], ruleData[7],
                    ruleData[8] * Grego.MILLIS_PER_SECOND,
                    ruleData[9],
                    ruleData[10] * Grego.MILLIS_PER_SECOND);

            r = res.get("finalYear");
            finalStartYear = r.getInt();

            // Note: Setting finalStartYear to the finalZone is problematic.  When a date is around
            // year boundary, SimpleTimeZone may return false result when DST is observed at the 
            // beginning of year.  We could apply safe margin (day or two), but when one of recurrent
            // rules falls around year boundary, it could return false result.  Without setting the
            // start year, finalZone works fine around the year boundary of the start year.

            // finalZone.setStartYear(finalStartYear);

            // Compute the millis for Jan 1, 0:00 GMT of the finalYear

            // Note: finalStartMillis is used for detecting either if
            // historic transition data or finalZone to be used.  In an
            // extreme edge case - for example, two transitions fall into
            // small windows of time around the year boundary, this may
            // result incorrect offset computation.  But I think it will
            // never happen practically.  Yoshito - Feb 20, 2010
            finalStartMillis = Grego.fieldsToDay(finalStartYear, 0, 1) * Grego.MILLIS_PER_DAY;
        } catch (MissingResourceException e) {
            if (ruleID != null) {
                // ruleID is found, but missing other data required for
                // creating finalZone
                throw new IllegalArgumentException("Invalid Format");
            }
        }
    }

    // This constructor is used for testing purpose only
    public OlsonTimeZone(String id){
        super(id);
        UResourceBundle top = UResourceBundle.getBundleInstance(ICUData.ICU_BASE_NAME,
                ZONEINFORES, ICUResourceBundle.ICU_DATA_CLASS_LOADER);
        UResourceBundle res = ZoneMeta.openOlsonResource(top, id);
        construct(top, res);
        if (finalZone != null){
            finalZone.setID(id);
        }
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#setID(java.lang.String)
     */
    @Override
    public void setID(String id){
        if (isFrozen()) {
            throw new UnsupportedOperationException("Attempt to modify a frozen OlsonTimeZone instance.");
        }

        // Before updating the ID, preserve the original ID's canonical ID.
        if (canonicalID == null) {
            canonicalID = getCanonicalID(getID());
            assert(canonicalID != null);
            if (canonicalID == null) {
                // This should never happen...
                canonicalID = getID();
            }
        }

        if (finalZone != null){
            finalZone.setID(id);
        }
        super.setID(id);
        transitionRulesInitialized = false;
    }

    // Maximum absolute offset in seconds = 1 day.
    // getHistoricalOffset uses this constant as safety margin of
    // quick zone transition checking.
    private static final int MAX_OFFSET_SECONDS = 86400; // 60 * 60 * 24;

    private void getHistoricalOffset(long date, boolean local,
            int NonExistingTimeOpt, int DuplicatedTimeOpt, int[] offsets) {
        if (transitionCount != 0) {
            long sec = Grego.floorDivide(date, Grego.MILLIS_PER_SECOND);
            if (!local && sec < transitionTimes64[0]) {
                // Before the first transition time
                offsets[0] = initialRawOffset() * Grego.MILLIS_PER_SECOND;
                offsets[1] = initialDstOffset() * Grego.MILLIS_PER_SECOND;
            } else {
                // Linear search from the end is the fastest approach, since
                // most lookups will happen at/near the end.
                int transIdx;
                for (transIdx = transitionCount - 1; transIdx >= 0; transIdx--) {
                    long transition = transitionTimes64[transIdx];
                    if (local && (sec >= (transition - MAX_OFFSET_SECONDS))) {
                        int offsetBefore = zoneOffsetAt(transIdx - 1);
                        boolean dstBefore = dstOffsetAt(transIdx - 1) != 0;

                        int offsetAfter = zoneOffsetAt(transIdx);
                        boolean dstAfter = dstOffsetAt(transIdx) != 0;

                        boolean dstToStd = dstBefore && !dstAfter;
                        boolean stdToDst = !dstBefore && dstAfter;

                        if (offsetAfter - offsetBefore >= 0) {
                            // Positive transition, which makes a non-existing local time range
                            if (((NonExistingTimeOpt & STD_DST_MASK) == LOCAL_STD && dstToStd)
                                    || ((NonExistingTimeOpt & STD_DST_MASK) == LOCAL_DST && stdToDst)) {
                                transition += offsetBefore;
                            } else if (((NonExistingTimeOpt & STD_DST_MASK) == LOCAL_STD && stdToDst)
                                    || ((NonExistingTimeOpt & STD_DST_MASK) == LOCAL_DST && dstToStd)) {
                                transition += offsetAfter;
                            } else if ((NonExistingTimeOpt & FORMER_LATTER_MASK) == LOCAL_LATTER) {
                                transition += offsetBefore;
                            } else {
                                // Interprets the time with rule before the transition,
                                // default for non-existing time range
                                transition += offsetAfter;
                            }
                        } else {
                            // Negative transition, which makes a duplicated local time range
                            if (((DuplicatedTimeOpt & STD_DST_MASK) == LOCAL_STD && dstToStd)
                                    || ((DuplicatedTimeOpt & STD_DST_MASK) == LOCAL_DST && stdToDst)) {
                                transition += offsetAfter;
                            } else if (((DuplicatedTimeOpt & STD_DST_MASK) == LOCAL_STD && stdToDst)
                                    || ((DuplicatedTimeOpt & STD_DST_MASK) == LOCAL_DST && dstToStd)) {
                                transition += offsetBefore;
                            } else if ((DuplicatedTimeOpt & FORMER_LATTER_MASK) == LOCAL_FORMER) {
                                transition += offsetBefore;
                            } else {
                                // Interprets the time with rule after the transition,
                                // default for duplicated local time range
                                transition += offsetAfter;
                            }
                        }
                    }
                    if (sec >= transition) {
                        break;
                    }
                }
                // transIdx could be -1 when local=true
                offsets[0] = rawOffsetAt(transIdx) * Grego.MILLIS_PER_SECOND;
                offsets[1] = dstOffsetAt(transIdx) * Grego.MILLIS_PER_SECOND;
            }
        } else {
            // No transitions, single pair of offsets only
            offsets[0] = initialRawOffset() * Grego.MILLIS_PER_SECOND;
            offsets[1] = initialDstOffset() * Grego.MILLIS_PER_SECOND;
        }
    }

    private int getInt(byte val){
        return val & 0xFF; 
    }

    /*
     * Following 3 methods return an offset at the given transition time index.
     * When the index is negative, return the initial offset.
     */
    private int zoneOffsetAt(int transIdx) {
        int typeIdx = transIdx >= 0 ? getInt(typeMapData[transIdx]) * 2 : 0;
        return typeOffsets[typeIdx] + typeOffsets[typeIdx + 1];
    }

    private int rawOffsetAt(int transIdx) {
        int typeIdx = transIdx >= 0 ? getInt(typeMapData[transIdx]) * 2 : 0;
        return typeOffsets[typeIdx];
    }

    private int dstOffsetAt(int transIdx) {
        int typeIdx = transIdx >= 0 ? getInt(typeMapData[transIdx]) * 2 : 0;
        return typeOffsets[typeIdx + 1];
    }

    private int initialRawOffset() {
        return typeOffsets[0];
    }

    private int initialDstOffset() {
        return typeOffsets[1];
    }

    // temp
    @Override
    public String toString() {
        StringBuilder buf = new StringBuilder();
        buf.append(super.toString());
        buf.append('[');
        buf.append("transitionCount=" + transitionCount);
        buf.append(",typeCount=" + typeCount);
        buf.append(",transitionTimes=");
        if (transitionTimes64 != null) {
            buf.append('[');
            for (int i = 0; i < transitionTimes64.length; ++i) {
                if (i > 0) {
                    buf.append(',');
                }
                buf.append(Long.toString(transitionTimes64[i]));
            }
            buf.append(']');
        } else {
            buf.append("null");
        }
        buf.append(",typeOffsets=");
        if (typeOffsets != null) {
            buf.append('[');
            for (int i = 0; i < typeOffsets.length; ++i) {
                if (i > 0) {
                    buf.append(',');
                }
                buf.append(Integer.toString(typeOffsets[i]));
            }
            buf.append(']');
        } else {
            buf.append("null");
        }
        buf.append(",typeMapData=");
        if (typeMapData != null) {
            buf.append('[');
            for (int i = 0; i < typeMapData.length; ++i) {
                if (i > 0) {
                    buf.append(',');
                }
                buf.append(Byte.toString(typeMapData[i]));
            }
        } else {
            buf.append("null");
        }
        buf.append(",finalStartYear=" + finalStartYear);
        buf.append(",finalStartMillis=" + finalStartMillis);
        buf.append(",finalZone=" + finalZone);
        buf.append(']');
        
        return buf.toString();
    }

    /**
     * Number of transitions, 0..~370
     */
    private int transitionCount;

    /**
     * Number of types, 1..255
     */
    private int typeCount;

    /**
     * Time of each transition in seconds from 1970 epoch.
     */
    private long[] transitionTimes64;

    /**
     * Offset from GMT in seconds for each type.
     * Length is equal to typeCount
     */
    private int[] typeOffsets;

    /**
     * Type description data, consisting of transitionCount uint8_t
     * type indices (from 0..typeCount-1).
     * Length is equal to transitionCount
     */
    private byte[] typeMapData;

    /**
     * For year >= finalStartYear, the finalZone will be used.
     */
    private int finalStartYear = Integer.MAX_VALUE;

    /**
     * For date >= finalStartMillis, the finalZone will be used.
     */
    private double finalStartMillis = Double.MAX_VALUE;

    /**
     * A SimpleTimeZone that governs the behavior for years >= finalYear.
     * If and only if finalYear == INT32_MAX then finalZone == 0.
     */
    private SimpleTimeZone finalZone = null; // owned, may be NULL
 
    /**
     * The canonical ID of this zone. Initialized when {@link #getCanonicalID()}
     * is invoked first time, or {@link #setID(String)} is called.
     */
    private volatile String canonicalID = null;

    private static final String ZONEINFORES = "zoneinfo64";

    private static final boolean DEBUG = ICUDebug.enabled("olson");
    private static final int SECONDS_PER_DAY = 24*60*60;
    
    private static UResourceBundle loadRule(UResourceBundle top, String ruleid) {
        UResourceBundle r = top.get("Rules");
        r = r.get(ruleid);
        return r;
    }

    @Override
    public boolean equals(Object obj){
        if (!super.equals(obj)) return false; // super does class check

        OlsonTimeZone z = (OlsonTimeZone) obj;

        return (Utility.arrayEquals(typeMapData, z.typeMapData) ||
                 // If the pointers are not equal, the zones may still
                 // be equal if their rules and transitions are equal
                 (finalStartYear == z.finalStartYear &&
                  // Don't compare finalMillis; if finalYear is ==, so is finalMillis
                  ((finalZone == null && z.finalZone == null) ||
                   (finalZone != null && z.finalZone != null &&
                    finalZone.equals(z.finalZone)) &&
                  transitionCount == z.transitionCount &&
                  typeCount == z.typeCount &&
                  Utility.arrayEquals(transitionTimes64, z.transitionTimes64) &&
                  Utility.arrayEquals(typeOffsets, z.typeOffsets) &&
                  Utility.arrayEquals(typeMapData, z.typeMapData)
                  )));

    }

    @Override
    public int hashCode(){
        int ret =   (int)  (finalStartYear ^ (finalStartYear>>>4) +
                   transitionCount ^ (transitionCount>>>6) +
                   typeCount ^ (typeCount>>>8) + 
                   Double.doubleToLongBits(finalStartMillis)+
                   (finalZone == null ? 0 : finalZone.hashCode()) + 
                   super.hashCode());
        if (transitionTimes64 != null) {
            for(int i=0; i<transitionTimes64.length; i++){
                ret+=transitionTimes64[i]^(transitionTimes64[i]>>>8);
            }
        }
        for(int i=0; i<typeOffsets.length; i++){
            ret+=typeOffsets[i]^(typeOffsets[i]>>>8);
        }
        if (typeMapData != null) {
            for(int i=0; i<typeMapData.length; i++){
                ret+=typeMapData[i] & 0xFF;
            } 
        }
        return ret;
    }

    //
    // BasicTimeZone methods
    //

    /* (non-Javadoc)
     * @see com.ibm.icu.util.BasicTimeZone#getNextTransition(long, boolean)
     */
    @Override
    public TimeZoneTransition getNextTransition(long base, boolean inclusive) {
        initTransitionRules();

        if (finalZone != null) {
            if (inclusive && base == firstFinalTZTransition.getTime()) {
                return firstFinalTZTransition;
            } else if (base >= firstFinalTZTransition.getTime()) {
                if (finalZone.useDaylightTime()) {
                    //return finalZone.getNextTransition(base, inclusive);
                    return finalZoneWithStartYear.getNextTransition(base, inclusive);
                } else {
                    // No more transitions
                    return null;
                }
            }
        }
        if (historicRules != null) {
            // Find a historical transition
            int ttidx = transitionCount - 1;
            for (; ttidx >= firstTZTransitionIdx; ttidx--) {
                long t = transitionTimes64[ttidx] * Grego.MILLIS_PER_SECOND;
                if (base > t || (!inclusive && base == t)) {
                    break;
                }
            }
            if (ttidx == transitionCount - 1)  {
                return firstFinalTZTransition;
            } else if (ttidx < firstTZTransitionIdx) {
                return firstTZTransition;
            } else {
                // Create a TimeZoneTransition
                TimeZoneRule to = historicRules[getInt(typeMapData[ttidx + 1])];
                TimeZoneRule from = historicRules[getInt(typeMapData[ttidx])];
                long startTime = transitionTimes64[ttidx+1] * Grego.MILLIS_PER_SECOND;

                // The transitions loaded from zoneinfo.res may contain non-transition data
                if (from.getName().equals(to.getName()) && from.getRawOffset() == to.getRawOffset()
                        && from.getDSTSavings() == to.getDSTSavings()) {
                    return getNextTransition(startTime, false);
                }

                return new TimeZoneTransition(startTime, from, to);
            }
        }
        return null;
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.BasicTimeZone#getPreviousTransition(long, boolean)
     */
    @Override
    public TimeZoneTransition getPreviousTransition(long base, boolean inclusive) {
        initTransitionRules();

        if (finalZone != null) {
            if (inclusive && base == firstFinalTZTransition.getTime()) {
                return firstFinalTZTransition;
            } else if (base > firstFinalTZTransition.getTime()) {
                if (finalZone.useDaylightTime()) {
                    //return finalZone.getPreviousTransition(base, inclusive);
                    return finalZoneWithStartYear.getPreviousTransition(base, inclusive);
                } else {
                    return firstFinalTZTransition;
                }                
            }
        }

        if (historicRules != null) {
            // Find a historical transition
            int ttidx = transitionCount - 1;
            for (; ttidx >= firstTZTransitionIdx; ttidx--) {
                long t = transitionTimes64[ttidx] * Grego.MILLIS_PER_SECOND;
                if (base > t || (inclusive && base == t)) {
                    break;
                }
            }
            if (ttidx < firstTZTransitionIdx) {
                // No more transitions
                return null;
            } else if (ttidx == firstTZTransitionIdx) {
                return firstTZTransition;
            } else {
                // Create a TimeZoneTransition
                TimeZoneRule to = historicRules[getInt(typeMapData[ttidx])];
                TimeZoneRule from = historicRules[getInt(typeMapData[ttidx-1])];
                long startTime = transitionTimes64[ttidx] * Grego.MILLIS_PER_SECOND;

                // The transitions loaded from zoneinfo.res may contain non-transition data
                if (from.getName().equals(to.getName()) && from.getRawOffset() == to.getRawOffset()
                        && from.getDSTSavings() == to.getDSTSavings()) {
                    return getPreviousTransition(startTime, false);
                }

                return new TimeZoneTransition(startTime, from, to);
            }
        }
        return null;
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.BasicTimeZone#getTimeZoneRules()
     */
    @Override
    public TimeZoneRule[] getTimeZoneRules() {
        initTransitionRules();
        int size = 1;
        if (historicRules != null) {
            // historicRules may contain null entries when original zoneinfo data
            // includes non transition data.
            for (int i = 0; i < historicRules.length; i++) {
                if (historicRules[i] != null) {
                    size++;
                }
            }
        }
        if (finalZone != null) {
            if (finalZone.useDaylightTime()) {
                size += 2;
            } else {
                size++;
            }
        }

        TimeZoneRule[] rules = new TimeZoneRule[size];
        int idx = 0;
        rules[idx++] = initialRule;

        if (historicRules != null) {
            for (int i = 0; i < historicRules.length; i++) {
                if (historicRules[i] != null) {
                    rules[idx++] = historicRules[i];
                }
            }
         }

        if (finalZone != null) {
            if (finalZone.useDaylightTime()) {
                TimeZoneRule[] stzr = finalZoneWithStartYear.getTimeZoneRules();
                // Adding only transition rules
                rules[idx++] = stzr[1];
                rules[idx++] = stzr[2];
            } else {
                // Create a TimeArrayTimeZoneRule at finalMillis
                rules[idx++] = new TimeArrayTimeZoneRule(getID() + "(STD)", finalZone.getRawOffset(), 0,
                        new long[] {(long)finalStartMillis}, DateTimeRule.UTC_TIME);                
            }
        }
        return rules;
    }

    private transient InitialTimeZoneRule initialRule;
    private transient TimeZoneTransition firstTZTransition;
    private transient int firstTZTransitionIdx;
    private transient TimeZoneTransition firstFinalTZTransition;
    private transient TimeArrayTimeZoneRule[] historicRules;
    private transient SimpleTimeZone finalZoneWithStartYear; // hack

    private transient boolean transitionRulesInitialized;

    private synchronized void initTransitionRules() {
        if (transitionRulesInitialized) {
            return;
        }

        initialRule = null;
        firstTZTransition = null;
        firstFinalTZTransition = null;
        historicRules = null;
        firstTZTransitionIdx = 0;
        finalZoneWithStartYear = null;

        String stdName = getID() + "(STD)";
        String dstName = getID() + "(DST)";

        int raw, dst;

        // Create initial rule
        raw = initialRawOffset() * Grego.MILLIS_PER_SECOND;
        dst = initialDstOffset() * Grego.MILLIS_PER_SECOND;
        initialRule = new InitialTimeZoneRule((dst == 0 ? stdName : dstName), raw, dst);

        if (transitionCount > 0) {
            int transitionIdx, typeIdx;

            // We probably no longer need to check the first "real" transition
            // here, because the new tzcode remove such transitions already.
            // For now, keeping this code for just in case. Feb 19, 2010 Yoshito
            for (transitionIdx = 0; transitionIdx < transitionCount; transitionIdx++) {
                if (getInt(typeMapData[transitionIdx]) != 0) { // type 0 is the initial type
                    break;
                }
                firstTZTransitionIdx++;
            }
            if (transitionIdx == transitionCount) {
                // Actually no transitions...
            } else {
                // Build historic rule array
                long[] times = new long[transitionCount];
                for (typeIdx = 0; typeIdx < typeCount; typeIdx++) {
                    // Gather all start times for each pair of offsets
                    int nTimes = 0;
                    for (transitionIdx = firstTZTransitionIdx; transitionIdx < transitionCount; transitionIdx++) {
                        if (typeIdx == getInt(typeMapData[transitionIdx])) {
                            long tt = transitionTimes64[transitionIdx] * Grego.MILLIS_PER_SECOND;
                            if (tt < finalStartMillis) {
                                // Exclude transitions after finalMillis
                                times[nTimes++] = tt;
                            }
                        }
                    }
                    if (nTimes > 0) {
                        long[] startTimes = new long[nTimes];
                        System.arraycopy(times, 0, startTimes, 0, nTimes);
                        // Create a TimeArrayTimeZoneRule
                        raw = typeOffsets[typeIdx*2]*Grego.MILLIS_PER_SECOND;
                        dst = typeOffsets[typeIdx*2 + 1]*Grego.MILLIS_PER_SECOND;
                        if (historicRules == null) {
                            historicRules = new TimeArrayTimeZoneRule[typeCount];
                        }
                        historicRules[typeIdx] = new TimeArrayTimeZoneRule((dst == 0 ? stdName : dstName),
                                raw, dst, startTimes, DateTimeRule.UTC_TIME);
                    }
                }

                // Create initial transition
                typeIdx = getInt(typeMapData[firstTZTransitionIdx]);
                firstTZTransition = new TimeZoneTransition(transitionTimes64[firstTZTransitionIdx] * Grego.MILLIS_PER_SECOND,
                        initialRule, historicRules[typeIdx]);
                
            }
        }

        if (finalZone != null) {
            // Get the first occurrence of final rule starts
            long startTime = (long)finalStartMillis;
            TimeZoneRule firstFinalRule;
            if (finalZone.useDaylightTime()) {
                /*
                 * Note: When an OlsonTimeZone is constructed, we should set the final year
                 * as the start year of finalZone.  However, the boundary condition used for
                 * getting offset from finalZone has some problems.  So setting the start year
                 * in the finalZone will cause a problem.  For now, we do not set the valid
                 * start year when the construction time and create a clone and set the
                 * start year when extracting rules.
                 */
                finalZoneWithStartYear = (SimpleTimeZone)finalZone.clone();
                finalZoneWithStartYear.setStartYear(finalStartYear);

                TimeZoneTransition tzt = finalZoneWithStartYear.getNextTransition(startTime, false);
                firstFinalRule  = tzt.getTo();
                startTime = tzt.getTime();
            } else {
                finalZoneWithStartYear = finalZone;
                firstFinalRule = new TimeArrayTimeZoneRule(finalZone.getID(),
                        finalZone.getRawOffset(), 0, new long[] {startTime}, DateTimeRule.UTC_TIME);
            }
            TimeZoneRule prevRule = null;
            if (transitionCount > 0) {
                prevRule = historicRules[getInt(typeMapData[transitionCount - 1])];
            }
            if (prevRule == null) {
                // No historic transitions, but only finalZone available
                prevRule = initialRule;
            }
            firstFinalTZTransition = new TimeZoneTransition(startTime, prevRule, firstFinalRule);
        }

        transitionRulesInitialized = true;
    }

    // Note: This class does not support back level serialization compatibility
    // very well.  ICU 4.4 introduced the 64bit transition data.  It is probably
    // possible to implement this class to make old version of ICU to deserialize
    // object stream serialized by ICU 4.4+.  However, such implementation will
    // introduce unnecessary complexity other than serialization support.
    // I decided to provide minimum level of backward compatibility, which
    // only support ICU 4.4+ to create an instance of OlsonTimeZone by reloading
    // the zone rules from bundles.  ICU 4.2 or older version of ICU cannot
    // deserialize object stream created by ICU 4.4+.  Yoshito -Feb 22, 2010

    private static final int currentSerialVersion = 1;
    private int serialVersionOnStream = currentSerialVersion;

    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
        stream.defaultReadObject();

        if (serialVersionOnStream < 1) {
            // No version - 4.2 or older
            // Just reloading the rule from bundle
            boolean initialized = false;
            String tzid = getID();
            if (tzid != null) {
                try {
                    UResourceBundle top = UResourceBundle.getBundleInstance(ICUData.ICU_BASE_NAME,
                            ZONEINFORES, ICUResourceBundle.ICU_DATA_CLASS_LOADER);
                    UResourceBundle res = ZoneMeta.openOlsonResource(top, tzid);
                    construct(top, res);
                    if (finalZone != null){
                        finalZone.setID(tzid);
                    }
                    initialized = true;
                } catch (Exception e) {
                    // throw away
                }
            }
            if (!initialized) {
                // final resort
                constructEmpty();
            }
        }

        // need to rebuild transition rules when requested
        transitionRulesInitialized = false;
    }

    // Freezable stuffs
    private transient volatile boolean isFrozen = false;

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#isFrozen()
     */
    public boolean isFrozen() {
        return isFrozen;
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#freeze()
     */
    public TimeZone freeze() {
        isFrozen = true;
        return this;
    }

    /* (non-Javadoc)
     * @see com.ibm.icu.util.TimeZone#cloneAsThawed()
     */
    public TimeZone cloneAsThawed() {
        OlsonTimeZone tz = (OlsonTimeZone)super.cloneAsThawed();
        if (finalZone != null) {
            // TODO Do we really need this?
            finalZone.setID(getID());
            tz.finalZone = (SimpleTimeZone) finalZone.clone();
        }

        // Following data are read-only and never changed.
        // Therefore, shallow copies should be sufficient.
        //
        // transitionTimes64
        // typeMapData
        // typeOffsets

        tz.isFrozen = false;
        return tz;
    }
}