/*
 * Joda Software License, Version 1.0
 *
 *
 * Copyright (c) 2001-2004 Stephen Colebourne.  
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. 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.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:  
 *       "This product includes software developed by the
 *        Joda project (http://www.joda.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The name "Joda" must not be used to endorse or promote products
 *    derived from this software without prior written permission. For
 *    written permission, please contact licence@joda.org.
 *
 * 5. Products derived from this software may not be called "Joda",
 *    nor may "Joda" appear in their name, without prior written
 *    permission of the Joda project.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED 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 JODA AUTHORS OR THE PROJECT
 * 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.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Joda project and was originally 
 * created by Stephen Colebourne <scolebourne@joda.org>. For more
 * information on the Joda project, please see <http://www.joda.org/>.
 */
package org.joda.time.tz;

import java.io.DataInput;
import java.io.DataInputStream;
import java.io.DataOutput;
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.joda.time.Chronology;
import org.joda.time.DateTimeUtils;
import org.joda.time.DateTimeZone;
import org.joda.time.chrono.ISOChronology;

/**
 * DateTimeZoneBuilder allows complex DateTimeZones to be constructed. Since
 * creating a new DateTimeZone this way is a relatively expensive operation,
 * built zones can be written to a file. Reading back the encoded data is a
 * quick operation.
 * <p>
 * DateTimeZoneBuilder itself is mutable and not thread-safe, but the
 * DateTimeZone objects that it builds are thread-safe and immutable.
 *
 * @author Brian S O'Neill
 * @see ZoneInfoCompiler
 * @see ZoneInfoProvider
 */
public class DateTimeZoneBuilder {
    /**
     * Decodes a built DateTimeZone from the given stream, as encoded by
     * writeTo.
     *
     * @param in input stream to read encoded DateTimeZone from.
     * @param id time zone id to assign
     */
    public static DateTimeZone readFrom(InputStream in, String id) throws IOException {
        if (in instanceof DataInput) {
            return readFrom((DataInput)in, id);
        } else {
            return readFrom((DataInput)new DataInputStream(in), id);
        }
    }

    /**
     * Decodes a built DateTimeZone from the given stream, as encoded by
     * writeTo.
     *
     * @param in input stream to read encoded DateTimeZone from.
     * @param id time zone id to assign
     */
    public static DateTimeZone readFrom(DataInput in, String id) throws IOException {
        switch (in.readUnsignedByte()) {
        case 'F':
            DateTimeZone fixed = new FixedDateTimeZone
                (id, in.readUTF(), (int)readMillis(in), (int)readMillis(in));
            if (fixed.equals(DateTimeZone.UTC)) {
                fixed = DateTimeZone.UTC;
            }
            return fixed;
        case 'C':
            return CachedDateTimeZone.forZone(PrecalculatedZone.readFrom(in, id));
        case 'P':
            return PrecalculatedZone.readFrom(in, id);
        default:
            throw new IOException("Invalid encoding");
        }
    }

    /**
     * Millisecond encoding formats:
     *
     * upper two bits  units       field length  approximate range
     * ---------------------------------------------------------------
     * 00              30 minutes  1 byte        +/- 16 hours
     * 01              minutes     4 bytes       +/- 1020 years
     * 10              seconds     5 bytes       +/- 4355 years
     * 11              millis      9 bytes       +/- 292,000,000 years
     *
     * Remaining bits in field form signed offset from 1970-01-01T00:00:00Z.
     */
    static void writeMillis(DataOutput out, long millis) throws IOException {
        if (millis % (30 * 60000L) == 0) {
            // Try to write in 30 minute units.
            long units = millis / (30 * 60000L);
            if (((units << (64 - 6)) >> (64 - 6)) == units) {
                // Form 00 (6 bits effective precision)
                out.writeByte((int)(units & 0x3f));
                return;
            }
        }

        if (millis % 60000L == 0) {
            // Try to write minutes.
            long minutes = millis / 60000L;
            if (((minutes << (64 - 30)) >> (64 - 30)) == minutes) {
                // Form 01 (30 bits effective precision)
                out.writeInt(0x40000000 | (int)(minutes & 0x3fffffff));
                return;
            }
        }
        
        if (millis % 1000L == 0) {
            // Try to write seconds.
            long seconds = millis / 1000L;
            if (((seconds << (64 - 38)) >> (64 - 38)) == seconds) {
                // Form 10 (38 bits effective precision)
                out.writeByte(0x80 | (int)((seconds >> 32) & 0x3f));
                out.writeInt((int)(seconds & 0xffffffff));
                return;
            }
        }

        // Write milliseconds either because the additional precision is
        // required or the minutes didn't fit in the field.
        
        // Form 11 (64 bits effective precision, but write as if 70 bits)
        out.writeByte(millis < 0 ? 0xff : 0xc0);
        out.writeLong(millis);
    }

    /**
     * Reads encoding generated by writeMillis.
     */
    static long readMillis(DataInput in) throws IOException {
        int v = in.readUnsignedByte();
        switch (v >> 6) {
        case 0: default:
            // Form 00 (6 bits effective precision)
            v = (v << (32 - 6)) >> (32 - 6);
            return v * (30 * 60000L);

        case 1:
            // Form 01 (30 bits effective precision)
            v = (v << (32 - 6)) >> (32 - 30);
            v |= (in.readUnsignedByte()) << 16;
            v |= (in.readUnsignedByte()) << 8;
            v |= (in.readUnsignedByte());
            return v * 60000L;

        case 2:
            // Form 10 (38 bits effective precision)
            long w = (((long)v) << (64 - 6)) >> (64 - 38);
            w |= (in.readUnsignedByte()) << 24;
            w |= (in.readUnsignedByte()) << 16;
            w |= (in.readUnsignedByte()) << 8;
            w |= (in.readUnsignedByte());
            return w * 1000L;

        case 3:
            // Form 11 (64 bits effective precision)
            return in.readLong();
        }
    }

    private static DateTimeZone buildFixedZone(String id, String nameKey,
                                               int wallOffset, int standardOffset) {
        if ("UTC".equals(id) && id.equals(nameKey) &&
            wallOffset == 0 && standardOffset == 0) {
            return DateTimeZone.UTC;
        }
        return new FixedDateTimeZone(id, nameKey, wallOffset, standardOffset);
    }

    // List of RuleSets.
    private final ArrayList iRuleSets;

    public DateTimeZoneBuilder() {
        iRuleSets = new ArrayList(10);
    }

    /**
     * Adds a cutover for added rules. The standard offset at the cutover
     * defaults to 0. Call setStandardOffset afterwards to change it.
     *
     * @param year year of cutover
     * @param mode 'u' - cutover is measured against UTC, 'w' - against wall
     * offset, 's' - against standard offset.
     * @param dayOfMonth if negative, set to ((last day of month) - ~dayOfMonth).
     * For example, if -1, set to last day of month
     * @param dayOfWeek if 0, ignore
     * @param advanceDayOfWeek if dayOfMonth does not fall on dayOfWeek, advance to
     * dayOfWeek when true, retreat when false.
     * @param millisOfDay additional precision for specifying time of day of
     * cutover
     */
    public DateTimeZoneBuilder addCutover(int year,
                                          char mode,
                                          int monthOfYear,
                                          int dayOfMonth,
                                          int dayOfWeek,
                                          boolean advanceDayOfWeek,
                                          int millisOfDay)
    {
        OfYear ofYear = new OfYear
            (mode, monthOfYear, dayOfMonth, dayOfWeek, advanceDayOfWeek, millisOfDay);
        if (iRuleSets.size() > 0) {
            RuleSet lastRuleSet = (RuleSet)iRuleSets.get(iRuleSets.size() - 1);
            lastRuleSet.setUpperLimit(year, ofYear);
        }
        iRuleSets.add(new RuleSet());
        return this;
    }

    /**
     * Sets the standard offset to use for newly added rules until the next
     * cutover is added.
     */
    public DateTimeZoneBuilder setStandardOffset(int standardOffset) {
        getLastRuleSet().setStandardOffset(standardOffset);
        return this;
    }

    /**
     * Set a fixed savings rule at the cutover.
     */
    public DateTimeZoneBuilder setFixedSavings(String nameKey, int saveMillis) {
        getLastRuleSet().setFixedSavings(nameKey, saveMillis);
        return this;
    }

    /**
     * Add a recurring daylight saving time rule.
     *
     * @param nameKey name key of new rule
     * @param saveMillis milliseconds to add to standard offset
     * @param fromYear First year that rule is in effect. MIN_VALUE indicates
     * beginning of time.
     * @param toYear Last year (inclusive) that rule is in effect. MAX_VALUE
     * indicates end of time.
     * @param mode 'u' - transitions are calculated against UTC, 'w' -
     * transitions are calculated against wall offset, 's' - transitions are
     * calculated against standard offset.
     * @param dayOfMonth if negative, set to ((last day of month) - ~dayOfMonth).
     * For example, if -1, set to last day of month
     * @param dayOfWeek if 0, ignore
     * @param advanceDayOfWeek if dayOfMonth does not fall on dayOfWeek, advance to
     * dayOfWeek when true, retreat when false.
     * @param millisOfDay additional precision for specifying time of day of
     * transitions
     */
    public DateTimeZoneBuilder addRecurringSavings(String nameKey, int saveMillis,
                                                   int fromYear, int toYear,
                                                   char mode,
                                                   int monthOfYear,
                                                   int dayOfMonth,
                                                   int dayOfWeek,
                                                   boolean advanceDayOfWeek,
                                                   int millisOfDay)
    {
        if (fromYear <= toYear) {
            OfYear ofYear = new OfYear
                (mode, monthOfYear, dayOfMonth, dayOfWeek, advanceDayOfWeek, millisOfDay);
            Recurrence recurrence = new Recurrence(ofYear, nameKey, saveMillis);
            Rule rule = new Rule(recurrence, fromYear, toYear);
            getLastRuleSet().addRule(rule);
        }
        return this;
    }

    private RuleSet getLastRuleSet() {
        if (iRuleSets.size() == 0) {
            addCutover(Integer.MIN_VALUE, 'w', 1, 1, 0, false, 0);
        }
        return (RuleSet)iRuleSets.get(iRuleSets.size() - 1);
    }
    
    /**
     * Processes all the rules and builds a DateTimeZone.
     *
     * @param id time zone id to assign
     */
    public DateTimeZone toDateTimeZone(String id) {
        if (id == null) {
            throw new IllegalArgumentException();
        }

        // Discover where all the transitions occur and store the results in
        // these lists.
        ArrayList transitions = new ArrayList();

        // Tail zone picks up remaining transitions in the form of an endless
        // DST cycle.
        DSTZone tailZone = null;

        long millis = Long.MIN_VALUE;
        int saveMillis = 0;
            
        int ruleSetCount = iRuleSets.size();
        for (int i=0; i<ruleSetCount; i++) {
            RuleSet rs = (RuleSet)iRuleSets.get(i);
            Transition next = rs.firstTransition(millis);
            if (next == null) {
                continue;
            }
            addTransition(transitions, next);
            millis = next.getMillis();
            saveMillis = next.getSaveMillis();

            // Copy it since we're going to destroy it.
            rs = new RuleSet(rs);

            while ((next = rs.nextTransition(millis, saveMillis)) != null) {
                if (addTransition(transitions, next)) {
                    if (tailZone != null) {
                        // Got the extra transition before DSTZone.
                        break;
                    }
                }
                millis = next.getMillis();
                saveMillis = next.getSaveMillis();
                if (tailZone == null && i == ruleSetCount - 1) {
                    tailZone = rs.buildTailZone(id);
                    // If tailZone is not null, don't break out of main loop until
                    // at least one more transition is calculated. This ensures a
                    // correct 'seam' to the DSTZone.
                }
            }

            millis = rs.getUpperLimit(saveMillis);
        }

        // Check if a simpler zone implementation can be returned.
        if (transitions.size() == 0) {
            if (tailZone != null) {
                // This shouldn't happen, but handle just in case.
                return tailZone;
            }
            return buildFixedZone(id, "UTC", 0, 0);
        }
        if (transitions.size() == 1 && tailZone == null) {
            Transition tr = (Transition)transitions.get(0);
            return buildFixedZone(id, tr.getNameKey(),
                                  tr.getWallOffset(), tr.getStandardOffset());
        }

        PrecalculatedZone zone = new PrecalculatedZone(id, transitions, tailZone);
        if (zone.isCachable()) {
            return CachedDateTimeZone.forZone(zone);
        }
        return zone;
    }

    private boolean addTransition(ArrayList transitions, Transition tr) {
        int size = transitions.size();
        if (size == 0) {
            transitions.add(tr);
            return true;
        }

        Transition last = (Transition)transitions.get(size - 1);
        if (!tr.isTransitionFrom(last)) {
            return false;
        }

        // If local time of new transition is same as last local time, just
        // replace last transition with new one.
        int offsetForLast = 0;
        if (size >= 2) {
            offsetForLast = ((Transition)transitions.get(size - 2)).getWallOffset();
        }
        int offsetForNew = last.getWallOffset();

        long lastLocal = last.getMillis() + offsetForLast;
        long newLocal = tr.getMillis() + offsetForNew;

        if (newLocal != lastLocal) {
            transitions.add(tr);
            return true;
        }

        transitions.remove(size - 1);
        return addTransition(transitions, tr);
    }

    /**
     * Encodes a built DateTimeZone to the given stream. Call readFrom to
     * decode the data into a DateTimeZone object.
     *
     * @param out output stream to receive encoded DateTimeZone.
     */
    public void writeTo(OutputStream out) throws IOException {
        if (out instanceof DataOutput) {
            writeTo((DataOutput)out);
        } else {
            writeTo((DataOutput)new DataOutputStream(out));
        }
    }

    /**
     * Encodes a built DateTimeZone to the given stream. Call readFrom to
     * decode the data into a DateTimeZone object.
     *
     * @param out output stream to receive encoded DateTimeZone.
     */
    public void writeTo(DataOutput out) throws IOException {
        // The zone id is not written out, so the empty string is okay.
        DateTimeZone zone = toDateTimeZone("");

        if (zone instanceof FixedDateTimeZone) {
            out.writeByte('F'); // 'F' for fixed
            out.writeUTF(zone.getNameKey(0));
            writeMillis(out, zone.getOffset(0));
            writeMillis(out, zone.getStandardOffset(0));
        } else {
            if (zone instanceof CachedDateTimeZone) {
                out.writeByte('C'); // 'C' for cached, precalculated
                zone = ((CachedDateTimeZone)zone).getUncachedZone();
            } else {
                out.writeByte('P'); // 'P' for precalculated, uncached
            }
            ((PrecalculatedZone)zone).writeTo(out);
        }
    }

    /**
     * Supports setting fields of year and moving between transitions.
     */
    private static final class OfYear {
        static OfYear readFrom(DataInput in) throws IOException {
            return new OfYear((char)in.readUnsignedByte(),
                              (int)in.readUnsignedByte(),
                              (int)in.readByte(),
                              (int)in.readUnsignedByte(),
                              in.readBoolean(),
                              (int)readMillis(in));
        }

        // Is 'u', 'w', or 's'.
        final char iMode;

        final int iMonthOfYear;
        final int iDayOfMonth;
        final int iDayOfWeek;
        final boolean iAdvance;
        final int iMillisOfDay;

        OfYear(char mode,
               int monthOfYear,
               int dayOfMonth,
               int dayOfWeek, boolean advanceDayOfWeek,
               int millisOfDay)
        {
            if (mode != 'u' && mode != 'w' && mode != 's') {
                throw new IllegalArgumentException("Unknown mode: " + mode);
            }

            iMode = mode;
            iMonthOfYear = monthOfYear;
            iDayOfMonth = dayOfMonth;
            iDayOfWeek = dayOfWeek;
            iAdvance = advanceDayOfWeek;
            iMillisOfDay = millisOfDay;
        }

        /**
         * @param standardOffset standard offset just before instant
         */
        public long setInstant(int year, int standardOffset, int saveMillis) {
            int offset;
            if (iMode == 'w') {
                offset = standardOffset + saveMillis;
            } else if (iMode == 's') {
                offset = standardOffset;
            } else {
                offset = 0;
            }

            Chronology chrono = ISOChronology.getInstanceUTC();
            long millis = chrono.year().set(0, year);
            millis = chrono.monthOfYear().set(millis, iMonthOfYear);
            millis = chrono.millisOfDay().set(millis, iMillisOfDay);
            millis = setDayOfMonth(chrono, millis);

            if (iDayOfWeek != 0) {
                millis = setDayOfWeek(chrono, millis);
            }

            // Convert from local time to UTC.
            return millis - offset;
        }

        /**
         * @param standardOffset standard offset just before next recurrence
         */
        public long next(long instant, int standardOffset, int saveMillis) {
            int offset;
            if (iMode == 'w') {
                offset = standardOffset + saveMillis;
            } else if (iMode == 's') {
                offset = standardOffset;
            } else {
                offset = 0;
            }

            // Convert from UTC to local time.
            instant += offset;

            Chronology chrono = ISOChronology.getInstanceUTC();
            long next = chrono.monthOfYear().set(instant, iMonthOfYear);
            // Be lenient with millisOfDay.
            next = chrono.millisOfDay().set(next, 0);
            next = chrono.millisOfDay().add(next, iMillisOfDay);
            next = setDayOfMonthNext(chrono, next);

            if (iDayOfWeek == 0) {
                if (next <= instant) {
                    next = chrono.year().add(next, 1);
                    next = setDayOfMonthNext(chrono, next);
                }
            } else {
                next = setDayOfWeek(chrono, next);
                if (next <= instant) {
                    next = chrono.year().add(next, 1);
                    next = chrono.monthOfYear().set(next, iMonthOfYear);
                    next = setDayOfMonthNext(chrono, next);
                    next = setDayOfWeek(chrono, next);
                }
            }

            // Convert from local time to UTC.
            return next - offset;
        }

        /**
         * @param standardOffset standard offset just before previous recurrence
         */
        public long previous(long instant, int standardOffset, int saveMillis) {
            int offset;
            if (iMode == 'w') {
                offset = standardOffset + saveMillis;
            } else if (iMode == 's') {
                offset = standardOffset;
            } else {
                offset = 0;
            }

            // Convert from UTC to local time.
            instant += offset;

            Chronology chrono = ISOChronology.getInstanceUTC();
            long prev = chrono.monthOfYear().set(instant, iMonthOfYear);
            // Be lenient with millisOfDay.
            prev = chrono.millisOfDay().set(prev, 0);
            prev = chrono.millisOfDay().add(prev, iMillisOfDay);
            prev = setDayOfMonthPrevious(chrono, prev);

            if (iDayOfWeek == 0) {
                if (prev >= instant) {
                    prev = chrono.year().add(prev, -1);
                    prev = setDayOfMonthPrevious(chrono, prev);
                }
            } else {
                prev = setDayOfWeek(chrono, prev);
                if (prev >= instant) {
                    prev = chrono.year().add(prev, -1);
                    prev = chrono.monthOfYear().set(prev, iMonthOfYear);
                    prev = setDayOfMonthPrevious(chrono, prev);
                    prev = setDayOfWeek(chrono, prev);
                }
            }

            // Convert from local time to UTC.
            return prev - offset;
        }

        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj instanceof OfYear) {
                OfYear other = (OfYear)obj;
                return
                    iMode == other.iMode &&
                    iMonthOfYear == other.iMonthOfYear &&
                    iDayOfMonth == other.iDayOfMonth &&
                    iDayOfWeek == other.iDayOfWeek &&
                    iAdvance == other.iAdvance &&
                    iMillisOfDay == other.iMillisOfDay;
            }
            return false;
        }

        /*
        public String toString() {
            return
                "[OfYear]\n" + 
                "Mode: " + iMode + '\n' +
                "MonthOfYear: " + iMonthOfYear + '\n' +
                "DayOfMonth: " + iDayOfMonth + '\n' +
                "DayOfWeek: " + iDayOfWeek + '\n' +
                "AdvanceDayOfWeek: " + iAdvance + '\n' +
                "MillisOfDay: " + iMillisOfDay + '\n';
        }
        */

        public void writeTo(DataOutput out) throws IOException {
            out.writeByte(iMode);
            out.writeByte(iMonthOfYear);
            out.writeByte(iDayOfMonth);
            out.writeByte(iDayOfWeek);
            out.writeBoolean(iAdvance);
            writeMillis(out, iMillisOfDay);
        }

        /**
         * If month-day is 02-29 and year isn't leap, advances to next leap year.
         */
        private long setDayOfMonthNext(Chronology chrono, long next) {
            try {
                next = setDayOfMonth(chrono, next);
            } catch (IllegalArgumentException e) {
                if (iMonthOfYear == 2 && iDayOfMonth == 29) {
                    while (chrono.year().isLeap(next) == false) {
                        next = chrono.year().add(next, 1);
                    }
                    next = setDayOfMonth(chrono, next);
                } else {
                    throw e;
                }
            }
            return next;
        }

        /**
         * If month-day is 02-29 and year isn't leap, retreats to previous leap year.
         */
        private long setDayOfMonthPrevious(Chronology chrono, long prev) {
            try {
                prev = setDayOfMonth(chrono, prev);
            } catch (IllegalArgumentException e) {
                if (iMonthOfYear == 2 && iDayOfMonth == 29) {
                    while (chrono.year().isLeap(prev) == false) {
                        prev = chrono.year().add(prev, -1);
                    }
                    prev = setDayOfMonth(chrono, prev);
                } else {
                    throw e;
                }
            }
            return prev;
        }

        private long setDayOfMonth(Chronology chrono, long instant) {
            if (iDayOfMonth >= 0) {
                instant = chrono.dayOfMonth().set(instant, iDayOfMonth);
            } else {
                instant = chrono.dayOfMonth().set(instant, 1);
                instant = chrono.monthOfYear().add(instant, 1);
                instant = chrono.dayOfMonth().add(instant, iDayOfMonth);
            }
            return instant;
        }

        private long setDayOfWeek(Chronology chrono, long instant) {
            int dayOfWeek = chrono.dayOfWeek().get(instant);
            int daysToAdd = iDayOfWeek - dayOfWeek;
            if (daysToAdd != 0) {
                if (iAdvance) {
                    if (daysToAdd < 0) {
                        daysToAdd += 7;
                    }
                } else {
                    if (daysToAdd > 0) {
                        daysToAdd -= 7;
                    }
                }
                instant = chrono.dayOfWeek().add(instant, daysToAdd);
            }
            return instant;
        }
    }

    /**
     * Extends OfYear with a nameKey and savings.
     */
    private static final class Recurrence {
        static Recurrence readFrom(DataInput in) throws IOException {
            return new Recurrence(OfYear.readFrom(in), in.readUTF(), (int)readMillis(in));
        }

        final OfYear iOfYear;
        final String iNameKey;
        final int iSaveMillis;

        Recurrence(OfYear ofYear, String nameKey, int saveMillis) {
            iOfYear = ofYear;
            iNameKey = nameKey;
            iSaveMillis = saveMillis;
        }

        public OfYear getOfYear() {
            return iOfYear;
        }

        /**
         * @param standardOffset standard offset just before next recurrence
         */
        public long next(long instant, int standardOffset, int saveMillis) {
            return iOfYear.next(instant, standardOffset, saveMillis);
        }

        /**
         * @param standardOffset standard offset just before previous recurrence
         */
        public long previous(long instant, int standardOffset, int saveMillis) {
            return iOfYear.previous(instant, standardOffset, saveMillis);
        }

        public String getNameKey() {
            return iNameKey;
        }

        public int getSaveMillis() {
            return iSaveMillis;
        }

        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj instanceof Recurrence) {
                Recurrence other = (Recurrence)obj;
                return
                    iSaveMillis == other.iSaveMillis &&
                    iNameKey.equals(other.iNameKey) &&
                    iOfYear.equals(other.iOfYear);
            }
            return false;
        }

        public void writeTo(DataOutput out) throws IOException {
            iOfYear.writeTo(out);
            out.writeUTF(iNameKey);
            writeMillis(out, iSaveMillis);
        }
    }

    /**
     * Extends Recurrence with inclusive year limits.
     */
    private static final class Rule {
        final Recurrence iRecurrence;
        final int iFromYear; // inclusive
        final int iToYear;   // inclusive

        Rule(Recurrence recurrence, int fromYear, int toYear) {
            iRecurrence = recurrence;
            iFromYear = fromYear;
            iToYear = toYear;
        }

        public int getFromYear() {
            return iFromYear;
        }

        public int getToYear() {
            return iToYear;
        }

        public OfYear getOfYear() {
            return iRecurrence.getOfYear();
        }

        public String getNameKey() {
            return iRecurrence.getNameKey();
        }

        public int getSaveMillis() {
            return iRecurrence.getSaveMillis();
        }

        public long next(final long instant, int standardOffset, int saveMillis) {
            Chronology chrono = ISOChronology.getInstanceUTC();

            final int wallOffset = standardOffset + saveMillis;
            long testInstant = instant;

            int year;
            if (instant == Long.MIN_VALUE) {
                year = Integer.MIN_VALUE;
            } else {
                year = chrono.year().get(instant + wallOffset);
            }

            if (year < iFromYear) {
                // First advance instant to start of from year.
                testInstant = chrono.year().set(0, iFromYear) - wallOffset;
                // Back off one millisecond to account for next recurrence
                // being exactly at the beginning of the year.
                testInstant -= 1;
            }

            long next = iRecurrence.next(testInstant, standardOffset, saveMillis);

            if (next > instant) {
                year = chrono.year().get(next + wallOffset);
                if (year > iToYear) {
                    // Out of range, return original value.
                    next = instant;
                }
            }

            return next;
        }
    }

    private static final class Transition {
        private final long iMillis;
        private final String iNameKey;
        private final int iWallOffset;
        private final int iStandardOffset;

        Transition(long millis, Transition tr) {
            iMillis = millis;
            iNameKey = tr.iNameKey;
            iWallOffset = tr.iWallOffset;
            iStandardOffset = tr.iStandardOffset;
        }

        Transition(long millis, Rule rule, int standardOffset) {
            iMillis = millis;
            iNameKey = rule.getNameKey();
            iWallOffset = standardOffset + rule.getSaveMillis();
            iStandardOffset = standardOffset;
        }

        Transition(long millis, String nameKey,
                   int wallOffset, int standardOffset) {
            iMillis = millis;
            iNameKey = nameKey;
            iWallOffset = wallOffset;
            iStandardOffset = standardOffset;
        }

        public long getMillis() {
            return iMillis;
        }

        public String getNameKey() {
            return iNameKey;
        }

        public int getWallOffset() {
            return iWallOffset;
        }

        public int getStandardOffset() {
            return iStandardOffset;
        }

        public int getSaveMillis() {
            return iWallOffset - iStandardOffset;
        }

        /**
         * There must be a change in the millis, wall offsets or name keys.
         */
        public boolean isTransitionFrom(Transition other) {
            if (other == null) {
                return true;
            }
            return iMillis > other.iMillis &&
                (iWallOffset != other.iWallOffset ||
                 //iStandardOffset != other.iStandardOffset ||
                 !(iNameKey.equals(other.iNameKey)));
        }
    }

    private static final class RuleSet {
        private static final int YEAR_LIMIT;

        static {
            // Don't pre-calculate more than 100 years into the future. Almost
            // all zones will stop pre-calculating far sooner anyhow. Either a
            // simple DST cycle is detected or the last rule is a fixed
            // offset. If a zone has a fixed offset set more than 100 years
            // into the future, then it won't be observed.
            long now = DateTimeUtils.currentTimeMillis();
            YEAR_LIMIT = ISOChronology.getInstanceUTC().year().get(now) + 100;
        }

        private int iStandardOffset;
        private ArrayList iRules;

        // Optional.
        private String iInitialNameKey;
        private int iInitialSaveMillis;

        // Upper limit is exclusive.
        private int iUpperYear;
        private OfYear iUpperOfYear;

        RuleSet() {
            iRules = new ArrayList(10);
            iUpperYear = Integer.MAX_VALUE;
        }

        /**
         * Copy constructor.
         */
        RuleSet(RuleSet rs) {
            iStandardOffset = rs.iStandardOffset;
            iRules = new ArrayList(rs.iRules);
            iInitialNameKey = rs.iInitialNameKey;
            iInitialSaveMillis = rs.iInitialSaveMillis;
            iUpperYear = rs.iUpperYear;
            iUpperOfYear = rs.iUpperOfYear;
        }

        public int getStandardOffset() {
            return iStandardOffset;
        }

        public void setStandardOffset(int standardOffset) {
            iStandardOffset = standardOffset;
        }

        public void setFixedSavings(String nameKey, int saveMillis) {
            iInitialNameKey = nameKey;
            iInitialSaveMillis = saveMillis;
        }

        public void addRule(Rule rule) {
            if (!iRules.contains(rule)) {
                iRules.add(rule);
            }
        }

        public void setUpperLimit(int year, OfYear ofYear) {
            iUpperYear = year;
            iUpperOfYear = ofYear;
        }

        /**
         * Returns a transition at firstMillis with the first name key and
         * offsets for this rule set. This method may return null.
         *
         * @param firstMillis millis of first transition
         */
        public Transition firstTransition(final long firstMillis) {
            if (iInitialNameKey != null) {
                // Initial zone info explicitly set, so don't search the rules.
                return new Transition(firstMillis, iInitialNameKey,
                                      iStandardOffset + iInitialSaveMillis, iStandardOffset);
            }

            // Make a copy before we destroy the rules.
            ArrayList copy = new ArrayList(iRules);

            // Iterate through all the transitions until firstMillis is
            // reached. Use the name key and savings for whatever rule reaches
            // the limit.

            long millis = Long.MIN_VALUE;
            int saveMillis = 0;
            Transition first = null;

            Transition next;
            while ((next = nextTransition(millis, saveMillis)) != null) {
                millis = next.getMillis();

                if (millis == firstMillis) {
                    first = new Transition(firstMillis, next);
                    break;
                }

                if (millis > firstMillis) {
                    if (first == null) {
                        // Find first rule without savings. This way a more
                        // accurate nameKey is found even though no rule
                        // extends to the RuleSet's lower limit.
                        Iterator it = copy.iterator();
                        while (it.hasNext()) {
                            Rule rule = (Rule)it.next();
                            if (rule.getSaveMillis() == 0) {
                                first = new Transition(firstMillis, rule, iStandardOffset);
                                break;
                            }
                        }
                    }
                    if (first == null) {
                        // Found no rule without savings. Create a transition
                        // with no savings anyhow, and use the best available
                        // name key.
                        first = new Transition(firstMillis, next.getNameKey(),
                                               iStandardOffset, iStandardOffset);
                    }
                    break;
                }
                
                // Set first to the best transition found so far, but next
                // iteration may find something closer to lower limit.
                first = new Transition(firstMillis, next);

                saveMillis = next.getSaveMillis();
            }

            iRules = copy;
            return first;
        }

        /**
         * Returns null if RuleSet is exhausted or upper limit reached. Calling
         * this method will throw away rules as they each become
         * exhausted. Copy the RuleSet before using it to compute transitions.
         *
         * Returned transition may be a duplicate from previous
         * transition. Caller must call isTransitionFrom to filter out
         * duplicates.
         *
         * @param saveMillis savings before next transition
         */
        public Transition nextTransition(final long instant, final int saveMillis) {
            Chronology chrono = ISOChronology.getInstanceUTC();

            // Find next matching rule.
            Rule nextRule = null;
            long nextMillis = Long.MAX_VALUE;
            
            Iterator it = iRules.iterator();
            while (it.hasNext()) {
                Rule rule = (Rule)it.next();
                long next = rule.next(instant, iStandardOffset, saveMillis);
                if (next <= instant) {
                    it.remove();
                    continue;
                }
                // Even if next is same as previous next, choose the rule
                // in order for more recently added rules to override.
                if (next <= nextMillis) {
                    // Found a better match.
                    nextRule = rule;
                    nextMillis = next;
                }
            }
            
            if (nextRule == null) {
                return null;
            }
            
            // Stop precalculating if year reaches some arbitrary limit.
            if (chrono.year().get(nextMillis) >= YEAR_LIMIT) {
                return null;
            }
            
            // Check if upper limit reached or passed.
            if (iUpperYear < Integer.MAX_VALUE) {
                long upperMillis =
                    iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
                if (nextMillis >= upperMillis) {
                    // At or after upper limit.
                    return null;
                }
            }
            
            return new Transition(nextMillis, nextRule, iStandardOffset);
        }

        /**
         * @param saveMillis savings before upper limit
         */
        public long getUpperLimit(int saveMillis) {
            if (iUpperYear == Integer.MAX_VALUE) {
                return Long.MAX_VALUE;
            }
            return iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
        }

        /**
         * Returns null if none can be built.
         */
        public DSTZone buildTailZone(String id) {
            if (iRules.size() == 2) {
                Rule startRule = (Rule)iRules.get(0);
                Rule endRule = (Rule)iRules.get(1);
                if (startRule.getToYear() == Integer.MAX_VALUE &&
                    endRule.getToYear() == Integer.MAX_VALUE) {

                    // With exactly two infinitely recurring rules left, a
                    // simple DSTZone can be formed.

                    // The order of rules can come in any order, and it doesn't
                    // really matter which rule was chosen the 'start' and
                    // which is chosen the 'end'. DSTZone works properly either
                    // way.
                    return new DSTZone(id, iStandardOffset,
                                       startRule.iRecurrence, endRule.iRecurrence);
                }
            }
            return null;
        }
    }

    private static final class DSTZone extends DateTimeZone {
        private static final long serialVersionUID = 6941492635554961361L;

        static DSTZone readFrom(DataInput in, String id) throws IOException {
            return new DSTZone(id, (int)readMillis(in), 
                               Recurrence.readFrom(in), Recurrence.readFrom(in));
        }

        private final int iStandardOffset;
        private final Recurrence iStartRecurrence;
        private final Recurrence iEndRecurrence;

        DSTZone(String id, int standardOffset,
                Recurrence startRecurrence, Recurrence endRecurrence) {
            super(id);
            iStandardOffset = standardOffset;
            iStartRecurrence = startRecurrence;
            iEndRecurrence = endRecurrence;
        }

        public String getNameKey(long instant) {
            return findMatchingRecurrence(instant).getNameKey();
        }

        public int getOffset(long instant) {
            return iStandardOffset + findMatchingRecurrence(instant).getSaveMillis();
        }

        public int getStandardOffset(long instant) {
            return iStandardOffset;
        }

        public boolean isFixed() {
            return false;
        }

        public long nextTransition(long instant) {
            int standardOffset = iStandardOffset;
            Recurrence startRecurrence = iStartRecurrence;
            Recurrence endRecurrence = iEndRecurrence;

            long start, end;

            try {
                start = startRecurrence.next
                    (instant, standardOffset, endRecurrence.getSaveMillis());
                if (instant > 0 && start < 0) {
                    // Overflowed.
                    start = instant;
                }
            } catch (IllegalArgumentException e) {
                // Overflowed.
                start = instant;
            }

            try {
                end = endRecurrence.next
                    (instant, standardOffset, startRecurrence.getSaveMillis());
                if (instant > 0 && end < 0) {
                    // Overflowed.
                    end = instant;
                }
            } catch (IllegalArgumentException e) {
                // Overflowed.
                end = instant;
            }

            return (start > end) ? end : start;
        }

        public long previousTransition(long instant) {
            // Increment in order to handle the case where instant is exactly at
            // a transition.
            instant++;

            int standardOffset = iStandardOffset;
            Recurrence startRecurrence = iStartRecurrence;
            Recurrence endRecurrence = iEndRecurrence;

            long start, end;

            try {
                start = startRecurrence.previous
                    (instant, standardOffset, endRecurrence.getSaveMillis());
                if (instant < 0 && start > 0) {
                    // Overflowed.
                    start = instant;
                }
            } catch (IllegalArgumentException e) {
                // Overflowed.
                start = instant;
            }

            try {
                end = endRecurrence.previous
                    (instant, standardOffset, startRecurrence.getSaveMillis());
                if (instant < 0 && end > 0) {
                    // Overflowed.
                    end = instant;
                }
            } catch (IllegalArgumentException e) {
                // Overflowed.
                end = instant;
            }

            return ((start > end) ? start : end) - 1;
        }

        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj instanceof DSTZone) {
                DSTZone other = (DSTZone)obj;
                return
                    getID().equals(other.getID()) &&
                    iStandardOffset == other.iStandardOffset &&
                    iStartRecurrence.equals(other.iStartRecurrence) &&
                    iEndRecurrence.equals(other.iEndRecurrence);
            }
            return false;
        }

        public void writeTo(DataOutput out) throws IOException {
            writeMillis(out, iStandardOffset);
            iStartRecurrence.writeTo(out);
            iEndRecurrence.writeTo(out);
        }

        private Recurrence findMatchingRecurrence(long instant) {
            int standardOffset = iStandardOffset;
            Recurrence startRecurrence = iStartRecurrence;
            Recurrence endRecurrence = iEndRecurrence;

            long start, end;

            try {
                start = startRecurrence.next
                    (instant, standardOffset, endRecurrence.getSaveMillis());
            } catch (IllegalArgumentException e) {
                // Overflowed.
                start = instant;
            }

            try {
                end = endRecurrence.next
                    (instant, standardOffset, startRecurrence.getSaveMillis());
            } catch (IllegalArgumentException e) {
                // Overflowed.
                end = instant;
            }

            return (start > end) ? startRecurrence : endRecurrence;
        }
    }

    private static final class PrecalculatedZone extends DateTimeZone {
        private static final long serialVersionUID = 7811976468055766265L;

        static PrecalculatedZone readFrom(DataInput in, String id) throws IOException {
            // Read string pool.
            int poolSize = in.readUnsignedShort();
            String[] pool = new String[poolSize];
            for (int i=0; i<poolSize; i++) {
                pool[i] = in.readUTF();
            }

            int size = in.readInt();
            long[] transitions = new long[size];
            int[] wallOffsets = new int[size];
            int[] standardOffsets = new int[size];
            String[] nameKeys = new String[size];
            
            for (int i=0; i<size; i++) {
                transitions[i] = readMillis(in);
                wallOffsets[i] = (int)readMillis(in);
                standardOffsets[i] = (int)readMillis(in);
                try {
                    int index;
                    if (poolSize < 256) {
                        index = in.readUnsignedByte();
                    } else {
                        index = in.readUnsignedShort();
                    }
                    nameKeys[i] = pool[index];
                } catch (ArrayIndexOutOfBoundsException e) {
                    throw new IOException("Invalid encoding");
                }
            }

            DSTZone tailZone = null;
            if (in.readBoolean()) {
                tailZone = DSTZone.readFrom(in, id);
            }

            return new PrecalculatedZone
                (id, transitions, wallOffsets, standardOffsets, nameKeys, tailZone);
        }

        // All array fields have the same length.

        private final long[] iTransitions;

        private final int[] iWallOffsets;
        private final int[] iStandardOffsets;
        private final String[] iNameKeys;

        private final DSTZone iTailZone;

        PrecalculatedZone(String id, long[] transitions, int[] wallOffsets,
                          int[] standardOffsets, String[] nameKeys, DSTZone tailZone)
        {
            super(id);
            iTransitions = transitions;
            iWallOffsets = wallOffsets;
            iStandardOffsets = standardOffsets;
            iNameKeys = nameKeys;
            iTailZone = tailZone;
        }

        /**
         * @param tailZone optional zone for getting info beyond precalculated
         * tables.
         */
        PrecalculatedZone(String id, ArrayList transitions, DSTZone tailZone) {
            super(id);

            int size = transitions.size();
            if (size == 0) {
                throw new IllegalArgumentException();
            }

            iTransitions = new long[size];
            iWallOffsets = new int[size];
            iStandardOffsets = new int[size];
            iNameKeys = new String[size];

            Transition last = null;
            for (int i=0; i<size; i++) {
                Transition tr = (Transition)transitions.get(i);

                if (!tr.isTransitionFrom(last)) {
                    throw new IllegalArgumentException(id);
                }

                iTransitions[i] = tr.getMillis();
                iWallOffsets[i] = tr.getWallOffset();
                iStandardOffsets[i] = tr.getStandardOffset();
                iNameKeys[i] = tr.getNameKey();

                last = tr;
            }

            iTailZone = tailZone;
        }

        public String getNameKey(long instant) {
            long[] transitions = iTransitions;
            int i = Arrays.binarySearch(transitions, instant);
            if (i >= 0) {
                return iNameKeys[i];
            }
            i = ~i;
            if (i < transitions.length) {
                if (i > 0) {
                    return iNameKeys[i - 1];
                }
                return "UTC";
            }
            if (iTailZone == null) {
                return iNameKeys[i - 1];
            }
            return iTailZone.getNameKey(instant);
        }

        public int getOffset(long instant) {
            long[] transitions = iTransitions;
            int i = Arrays.binarySearch(transitions, instant);
            if (i >= 0) {
                return iWallOffsets[i];
            }
            i = ~i;
            if (i < transitions.length) {
                if (i > 0) {
                    return iWallOffsets[i - 1];
                }
                return 0;
            }
            if (iTailZone == null) {
                return iWallOffsets[i - 1];
            }
            return iTailZone.getOffset(instant);
        }

        public int getStandardOffset(long instant) {
            long[] transitions = iTransitions;
            int i = Arrays.binarySearch(transitions, instant);
            if (i >= 0) {
                return iStandardOffsets[i];
            }
            i = ~i;
            if (i < transitions.length) {
                if (i > 0) {
                    return iStandardOffsets[i - 1];
                }
                return 0;
            }
            if (iTailZone == null) {
                return iStandardOffsets[i - 1];
            }
            return iTailZone.getStandardOffset(instant);
        }

        public boolean isFixed() {
            return false;
        }

        public long nextTransition(long instant) {
            long[] transitions = iTransitions;
            int i = Arrays.binarySearch(transitions, instant);
            i = (i >= 0) ? (i + 1) : ~i;
            if (i < transitions.length) {
                return transitions[i];
            }
            if (iTailZone == null) {
                return instant;
            }
            long end = transitions[transitions.length - 1];
            if (instant < end) {
                instant = end;
            }
            return iTailZone.nextTransition(instant);
        }

        public long previousTransition(long instant) {
            long[] transitions = iTransitions;
            int i = Arrays.binarySearch(transitions, instant);
            if (i >= 0) {
                if (instant > Long.MIN_VALUE) {
                    return instant - 1;
                }
                return instant;
            }
            i = ~i;
            if (i < transitions.length) {
                if (i > 0) {
                    long prev = transitions[i - 1];
                    if (prev > Long.MIN_VALUE) {
                        return prev - 1;
                    }
                }
                return instant;
            }
            if (iTailZone != null) {
                long prev = iTailZone.previousTransition(instant);
                if (prev < instant) {
                    return prev;
                }
            }
            long prev = transitions[i - 1];
            if (prev > Long.MIN_VALUE) {
                return prev - 1;
            }
            return instant;
        }

        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj instanceof PrecalculatedZone) {
                PrecalculatedZone other = (PrecalculatedZone)obj;
                return
                    getID().equals(other.getID()) &&
                    Arrays.equals(iTransitions, other.iTransitions) &&
                    Arrays.equals(iNameKeys, other.iNameKeys) &&
                    Arrays.equals(iWallOffsets, other.iWallOffsets) &&
                    Arrays.equals(iStandardOffsets, other.iStandardOffsets) &&
                    ((iTailZone == null)
                     ? (null == other.iTailZone)
                     : (iTailZone.equals(other.iTailZone)));
            }
            return false;
        }

        public void writeTo(DataOutput out) throws IOException {
            int size = iTransitions.length;

            // Create unique string pool.
            Set poolSet = new HashSet();
            for (int i=0; i<size; i++) {
                poolSet.add(iNameKeys[i]);
            }

            int poolSize = poolSet.size();
            if (poolSize > 65535) {
                throw new UnsupportedOperationException("String pool is too large");
            }
            String[] pool = new String[poolSize];
            Iterator it = poolSet.iterator();
            for (int i=0; it.hasNext(); i++) {
                pool[i] = (String)it.next();
            }

            // Write out the pool.
            out.writeShort(poolSize);
            for (int i=0; i<poolSize; i++) {
                out.writeUTF(pool[i]);
            }

            out.writeInt(size);

            for (int i=0; i<size; i++) {
                writeMillis(out, iTransitions[i]);
                writeMillis(out, iWallOffsets[i]);
                writeMillis(out, iStandardOffsets[i]);
                
                // Find pool index and write it out.
                String nameKey = iNameKeys[i];
                for (int j=0; j<poolSize; j++) {
                    if (pool[j].equals(nameKey)) {
                        if (poolSize < 256) {
                            out.writeByte(j);
                        } else {
                            out.writeShort(j);
                        }
                        break;
                    }
                }
            }

            out.writeBoolean(iTailZone != null);
            if (iTailZone != null) {
                iTailZone.writeTo(out);
            }
        }

        public boolean isCachable() {
            if (iTailZone != null) {
                return true;
            }
            long[] transitions = iTransitions;
            if (transitions.length <= 1) {
                return false;
            }

            // Add up all the distances between transitions that are less than
            // about two years.
            double distances = 0;
            int count = 0;

            for (int i=1; i<transitions.length; i++) {
                long diff = transitions[i] - transitions[i - 1];
                if (diff < ((366L + 365) * 24 * 60 * 60 * 1000)) {
                    distances += (double)diff;
                    count++;
                }
            }

            if (count > 0) {
                double avg = distances / count;
                avg /= 24 * 60 * 60 * 1000;
                if (avg >= 25) {
                    // Only bother caching if average distance between
                    // transitions is at least 25 days. Why 25?
                    // CachedDateTimeZone is more efficient if the distance
                    // between transitions is large. With an average of 25, it
                    // will on average perform about 2 tests per cache
                    // hit. (49.7 / 25) is approximately 2.
                    return true;
                }
            }

            return false;
        }
    }
}