001/*
002 *  Copyright 2001-2010 Stephen Colebourne
003 *
004 *  Licensed under the Apache License, Version 2.0 (the "License");
005 *  you may not use this file except in compliance with the License.
006 *  You may obtain a copy of the License at
007 *
008 *      http://www.apache.org/licenses/LICENSE-2.0
009 *
010 *  Unless required by applicable law or agreed to in writing, software
011 *  distributed under the License is distributed on an "AS IS" BASIS,
012 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 *  See the License for the specific language governing permissions and
014 *  limitations under the License.
015 */
016package org.joda.time.tz;
017
018import java.io.DataInput;
019import java.io.DataInputStream;
020import java.io.DataOutput;
021import java.io.DataOutputStream;
022import java.io.IOException;
023import java.io.InputStream;
024import java.io.OutputStream;
025import java.text.DateFormatSymbols;
026import java.util.ArrayList;
027import java.util.Arrays;
028import java.util.HashSet;
029import java.util.Iterator;
030import java.util.Locale;
031import java.util.Set;
032
033import org.joda.time.Chronology;
034import org.joda.time.DateTime;
035import org.joda.time.DateTimeUtils;
036import org.joda.time.DateTimeZone;
037import org.joda.time.Period;
038import org.joda.time.PeriodType;
039import org.joda.time.chrono.ISOChronology;
040
041/**
042 * DateTimeZoneBuilder allows complex DateTimeZones to be constructed. Since
043 * creating a new DateTimeZone this way is a relatively expensive operation,
044 * built zones can be written to a file. Reading back the encoded data is a
045 * quick operation.
046 * <p>
047 * DateTimeZoneBuilder itself is mutable and not thread-safe, but the
048 * DateTimeZone objects that it builds are thread-safe and immutable.
049 * <p>
050 * It is intended that {@link ZoneInfoCompiler} be used to read time zone data
051 * files, indirectly calling DateTimeZoneBuilder. The following complex
052 * example defines the America/Los_Angeles time zone, with all historical
053 * transitions:
054 * 
055 * <pre>
056 * DateTimeZone America_Los_Angeles = new DateTimeZoneBuilder()
057 *     .addCutover(-2147483648, 'w', 1, 1, 0, false, 0)
058 *     .setStandardOffset(-28378000)
059 *     .setFixedSavings("LMT", 0)
060 *     .addCutover(1883, 'w', 11, 18, 0, false, 43200000)
061 *     .setStandardOffset(-28800000)
062 *     .addRecurringSavings("PDT", 3600000, 1918, 1919, 'w',  3, -1, 7, false, 7200000)
063 *     .addRecurringSavings("PST",       0, 1918, 1919, 'w', 10, -1, 7, false, 7200000)
064 *     .addRecurringSavings("PWT", 3600000, 1942, 1942, 'w',  2,  9, 0, false, 7200000)
065 *     .addRecurringSavings("PPT", 3600000, 1945, 1945, 'u',  8, 14, 0, false, 82800000)
066 *     .addRecurringSavings("PST",       0, 1945, 1945, 'w',  9, 30, 0, false, 7200000)
067 *     .addRecurringSavings("PDT", 3600000, 1948, 1948, 'w',  3, 14, 0, false, 7200000)
068 *     .addRecurringSavings("PST",       0, 1949, 1949, 'w',  1,  1, 0, false, 7200000)
069 *     .addRecurringSavings("PDT", 3600000, 1950, 1966, 'w',  4, -1, 7, false, 7200000)
070 *     .addRecurringSavings("PST",       0, 1950, 1961, 'w',  9, -1, 7, false, 7200000)
071 *     .addRecurringSavings("PST",       0, 1962, 1966, 'w', 10, -1, 7, false, 7200000)
072 *     .addRecurringSavings("PST",       0, 1967, 2147483647, 'w', 10, -1, 7, false, 7200000)
073 *     .addRecurringSavings("PDT", 3600000, 1967, 1973, 'w', 4, -1,  7, false, 7200000)
074 *     .addRecurringSavings("PDT", 3600000, 1974, 1974, 'w', 1,  6,  0, false, 7200000)
075 *     .addRecurringSavings("PDT", 3600000, 1975, 1975, 'w', 2, 23,  0, false, 7200000)
076 *     .addRecurringSavings("PDT", 3600000, 1976, 1986, 'w', 4, -1,  7, false, 7200000)
077 *     .addRecurringSavings("PDT", 3600000, 1987, 2147483647, 'w', 4, 1, 7, true, 7200000)
078 *     .toDateTimeZone("America/Los_Angeles", true);
079 * </pre>
080 *
081 * @author Brian S O'Neill
082 * @see ZoneInfoCompiler
083 * @see ZoneInfoProvider
084 * @since 1.0
085 */
086public class DateTimeZoneBuilder {
087    /**
088     * Decodes a built DateTimeZone from the given stream, as encoded by
089     * writeTo.
090     *
091     * @param in input stream to read encoded DateTimeZone from.
092     * @param id time zone id to assign
093     */
094    public static DateTimeZone readFrom(InputStream in, String id) throws IOException {
095        if (in instanceof DataInput) {
096            return readFrom((DataInput)in, id);
097        } else {
098            return readFrom((DataInput)new DataInputStream(in), id);
099        }
100    }
101
102    /**
103     * Decodes a built DateTimeZone from the given stream, as encoded by
104     * writeTo.
105     *
106     * @param in input stream to read encoded DateTimeZone from.
107     * @param id time zone id to assign
108     */
109    public static DateTimeZone readFrom(DataInput in, String id) throws IOException {
110        switch (in.readUnsignedByte()) {
111        case 'F':
112            DateTimeZone fixed = new FixedDateTimeZone
113                (id, in.readUTF(), (int)readMillis(in), (int)readMillis(in));
114            if (fixed.equals(DateTimeZone.UTC)) {
115                fixed = DateTimeZone.UTC;
116            }
117            return fixed;
118        case 'C':
119            return CachedDateTimeZone.forZone(PrecalculatedZone.readFrom(in, id));
120        case 'P':
121            return PrecalculatedZone.readFrom(in, id);
122        default:
123            throw new IOException("Invalid encoding");
124        }
125    }
126
127    /**
128     * Millisecond encoding formats:
129     *
130     * upper two bits  units       field length  approximate range
131     * ---------------------------------------------------------------
132     * 00              30 minutes  1 byte        +/- 16 hours
133     * 01              minutes     4 bytes       +/- 1020 years
134     * 10              seconds     5 bytes       +/- 4355 years
135     * 11              millis      9 bytes       +/- 292,000,000 years
136     *
137     * Remaining bits in field form signed offset from 1970-01-01T00:00:00Z.
138     */
139    static void writeMillis(DataOutput out, long millis) throws IOException {
140        if (millis % (30 * 60000L) == 0) {
141            // Try to write in 30 minute units.
142            long units = millis / (30 * 60000L);
143            if (((units << (64 - 6)) >> (64 - 6)) == units) {
144                // Form 00 (6 bits effective precision)
145                out.writeByte((int)(units & 0x3f));
146                return;
147            }
148        }
149
150        if (millis % 60000L == 0) {
151            // Try to write minutes.
152            long minutes = millis / 60000L;
153            if (((minutes << (64 - 30)) >> (64 - 30)) == minutes) {
154                // Form 01 (30 bits effective precision)
155                out.writeInt(0x40000000 | (int)(minutes & 0x3fffffff));
156                return;
157            }
158        }
159        
160        if (millis % 1000L == 0) {
161            // Try to write seconds.
162            long seconds = millis / 1000L;
163            if (((seconds << (64 - 38)) >> (64 - 38)) == seconds) {
164                // Form 10 (38 bits effective precision)
165                out.writeByte(0x80 | (int)((seconds >> 32) & 0x3f));
166                out.writeInt((int)(seconds & 0xffffffff));
167                return;
168            }
169        }
170
171        // Write milliseconds either because the additional precision is
172        // required or the minutes didn't fit in the field.
173        
174        // Form 11 (64 bits effective precision, but write as if 70 bits)
175        out.writeByte(millis < 0 ? 0xff : 0xc0);
176        out.writeLong(millis);
177    }
178
179    /**
180     * Reads encoding generated by writeMillis.
181     */
182    static long readMillis(DataInput in) throws IOException {
183        int v = in.readUnsignedByte();
184        switch (v >> 6) {
185        case 0: default:
186            // Form 00 (6 bits effective precision)
187            v = (v << (32 - 6)) >> (32 - 6);
188            return v * (30 * 60000L);
189
190        case 1:
191            // Form 01 (30 bits effective precision)
192            v = (v << (32 - 6)) >> (32 - 30);
193            v |= (in.readUnsignedByte()) << 16;
194            v |= (in.readUnsignedByte()) << 8;
195            v |= (in.readUnsignedByte());
196            return v * 60000L;
197
198        case 2:
199            // Form 10 (38 bits effective precision)
200            long w = (((long)v) << (64 - 6)) >> (64 - 38);
201            w |= (in.readUnsignedByte()) << 24;
202            w |= (in.readUnsignedByte()) << 16;
203            w |= (in.readUnsignedByte()) << 8;
204            w |= (in.readUnsignedByte());
205            return w * 1000L;
206
207        case 3:
208            // Form 11 (64 bits effective precision)
209            return in.readLong();
210        }
211    }
212
213    private static DateTimeZone buildFixedZone(String id, String nameKey,
214                                               int wallOffset, int standardOffset) {
215        if ("UTC".equals(id) && id.equals(nameKey) &&
216            wallOffset == 0 && standardOffset == 0) {
217            return DateTimeZone.UTC;
218        }
219        return new FixedDateTimeZone(id, nameKey, wallOffset, standardOffset);
220    }
221
222    // List of RuleSets.
223    private final ArrayList<RuleSet> iRuleSets;
224
225    public DateTimeZoneBuilder() {
226        iRuleSets = new ArrayList<RuleSet>(10);
227    }
228
229    /**
230     * Adds a cutover for added rules. The standard offset at the cutover
231     * defaults to 0. Call setStandardOffset afterwards to change it.
232     *
233     * @param year  the year of cutover
234     * @param mode 'u' - cutover is measured against UTC, 'w' - against wall
235     *  offset, 's' - against standard offset
236     * @param monthOfYear  the month from 1 (January) to 12 (December)
237     * @param dayOfMonth  if negative, set to ((last day of month) - ~dayOfMonth).
238     *  For example, if -1, set to last day of month
239     * @param dayOfWeek  from 1 (Monday) to 7 (Sunday), if 0 then ignore
240     * @param advanceDayOfWeek  if dayOfMonth does not fall on dayOfWeek, advance to
241     *  dayOfWeek when true, retreat when false.
242     * @param millisOfDay  additional precision for specifying time of day of cutover
243     */
244    public DateTimeZoneBuilder addCutover(int year,
245                                          char mode,
246                                          int monthOfYear,
247                                          int dayOfMonth,
248                                          int dayOfWeek,
249                                          boolean advanceDayOfWeek,
250                                          int millisOfDay)
251    {
252        if (iRuleSets.size() > 0) {
253            OfYear ofYear = new OfYear
254                (mode, monthOfYear, dayOfMonth, dayOfWeek, advanceDayOfWeek, millisOfDay);
255            RuleSet lastRuleSet = iRuleSets.get(iRuleSets.size() - 1);
256            lastRuleSet.setUpperLimit(year, ofYear);
257        }
258        iRuleSets.add(new RuleSet());
259        return this;
260    }
261
262    /**
263     * Sets the standard offset to use for newly added rules until the next
264     * cutover is added.
265     * @param standardOffset  the standard offset in millis
266     */
267    public DateTimeZoneBuilder setStandardOffset(int standardOffset) {
268        getLastRuleSet().setStandardOffset(standardOffset);
269        return this;
270    }
271
272    /**
273     * Set a fixed savings rule at the cutover.
274     */
275    public DateTimeZoneBuilder setFixedSavings(String nameKey, int saveMillis) {
276        getLastRuleSet().setFixedSavings(nameKey, saveMillis);
277        return this;
278    }
279
280    /**
281     * Add a recurring daylight saving time rule.
282     *
283     * @param nameKey  the name key of new rule
284     * @param saveMillis  the milliseconds to add to standard offset
285     * @param fromYear  the first year that rule is in effect, MIN_VALUE indicates
286     * beginning of time
287     * @param toYear  the last year (inclusive) that rule is in effect, MAX_VALUE
288     *  indicates end of time
289     * @param mode  'u' - transitions are calculated against UTC, 'w' -
290     *  transitions are calculated against wall offset, 's' - transitions are
291     *  calculated against standard offset
292     * @param monthOfYear  the month from 1 (January) to 12 (December)
293     * @param dayOfMonth  if negative, set to ((last day of month) - ~dayOfMonth).
294     *  For example, if -1, set to last day of month
295     * @param dayOfWeek  from 1 (Monday) to 7 (Sunday), if 0 then ignore
296     * @param advanceDayOfWeek  if dayOfMonth does not fall on dayOfWeek, advance to
297     *  dayOfWeek when true, retreat when false.
298     * @param millisOfDay  additional precision for specifying time of day of transitions
299     */
300    public DateTimeZoneBuilder addRecurringSavings(String nameKey, int saveMillis,
301                                                   int fromYear, int toYear,
302                                                   char mode,
303                                                   int monthOfYear,
304                                                   int dayOfMonth,
305                                                   int dayOfWeek,
306                                                   boolean advanceDayOfWeek,
307                                                   int millisOfDay)
308    {
309        if (fromYear <= toYear) {
310            OfYear ofYear = new OfYear
311                (mode, monthOfYear, dayOfMonth, dayOfWeek, advanceDayOfWeek, millisOfDay);
312            Recurrence recurrence = new Recurrence(ofYear, nameKey, saveMillis);
313            Rule rule = new Rule(recurrence, fromYear, toYear);
314            getLastRuleSet().addRule(rule);
315        }
316        return this;
317    }
318
319    private RuleSet getLastRuleSet() {
320        if (iRuleSets.size() == 0) {
321            addCutover(Integer.MIN_VALUE, 'w', 1, 1, 0, false, 0);
322        }
323        return iRuleSets.get(iRuleSets.size() - 1);
324    }
325    
326    /**
327     * Processes all the rules and builds a DateTimeZone.
328     *
329     * @param id  time zone id to assign
330     * @param outputID  true if the zone id should be output
331     */
332    public DateTimeZone toDateTimeZone(String id, boolean outputID) {
333        if (id == null) {
334            throw new IllegalArgumentException();
335        }
336
337        // Discover where all the transitions occur and store the results in
338        // these lists.
339        ArrayList<Transition> transitions = new ArrayList<Transition>();
340
341        // Tail zone picks up remaining transitions in the form of an endless
342        // DST cycle.
343        DSTZone tailZone = null;
344
345        long millis = Long.MIN_VALUE;
346        int saveMillis = 0;
347            
348        int ruleSetCount = iRuleSets.size();
349        for (int i=0; i<ruleSetCount; i++) {
350            RuleSet rs = iRuleSets.get(i);
351            Transition next = rs.firstTransition(millis);
352            if (next == null) {
353                continue;
354            }
355            addTransition(transitions, next);
356            millis = next.getMillis();
357            saveMillis = next.getSaveMillis();
358
359            // Copy it since we're going to destroy it.
360            rs = new RuleSet(rs);
361
362            while ((next = rs.nextTransition(millis, saveMillis)) != null) {
363                if (addTransition(transitions, next)) {
364                    if (tailZone != null) {
365                        // Got the extra transition before DSTZone.
366                        break;
367                    }
368                }
369                millis = next.getMillis();
370                saveMillis = next.getSaveMillis();
371                if (tailZone == null && i == ruleSetCount - 1) {
372                    tailZone = rs.buildTailZone(id);
373                    // If tailZone is not null, don't break out of main loop until
374                    // at least one more transition is calculated. This ensures a
375                    // correct 'seam' to the DSTZone.
376                }
377            }
378
379            millis = rs.getUpperLimit(saveMillis);
380        }
381
382        // Check if a simpler zone implementation can be returned.
383        if (transitions.size() == 0) {
384            if (tailZone != null) {
385                // This shouldn't happen, but handle just in case.
386                return tailZone;
387            }
388            return buildFixedZone(id, "UTC", 0, 0);
389        }
390        if (transitions.size() == 1 && tailZone == null) {
391            Transition tr = transitions.get(0);
392            return buildFixedZone(id, tr.getNameKey(),
393                                  tr.getWallOffset(), tr.getStandardOffset());
394        }
395
396        PrecalculatedZone zone = PrecalculatedZone.create(id, outputID, transitions, tailZone);
397        if (zone.isCachable()) {
398            return CachedDateTimeZone.forZone(zone);
399        }
400        return zone;
401    }
402
403    private boolean addTransition(ArrayList<Transition> transitions, Transition tr) {
404        int size = transitions.size();
405        if (size == 0) {
406            transitions.add(tr);
407            return true;
408        }
409
410        Transition last = transitions.get(size - 1);
411        if (!tr.isTransitionFrom(last)) {
412            return false;
413        }
414
415        // If local time of new transition is same as last local time, just
416        // replace last transition with new one.
417        int offsetForLast = 0;
418        if (size >= 2) {
419            offsetForLast = transitions.get(size - 2).getWallOffset();
420        }
421        int offsetForNew = last.getWallOffset();
422
423        long lastLocal = last.getMillis() + offsetForLast;
424        long newLocal = tr.getMillis() + offsetForNew;
425
426        if (newLocal != lastLocal) {
427            transitions.add(tr);
428            return true;
429        }
430
431        transitions.remove(size - 1);
432        return addTransition(transitions, tr);
433    }
434
435    /**
436     * Encodes a built DateTimeZone to the given stream. Call readFrom to
437     * decode the data into a DateTimeZone object.
438     *
439     * @param out  the output stream to receive the encoded DateTimeZone
440     * @since 1.5 (parameter added)
441     */
442    public void writeTo(String zoneID, OutputStream out) throws IOException {
443        if (out instanceof DataOutput) {
444            writeTo(zoneID, (DataOutput)out);
445        } else {
446            writeTo(zoneID, (DataOutput)new DataOutputStream(out));
447        }
448    }
449
450    /**
451     * Encodes a built DateTimeZone to the given stream. Call readFrom to
452     * decode the data into a DateTimeZone object.
453     *
454     * @param out  the output stream to receive the encoded DateTimeZone
455     * @since 1.5 (parameter added)
456     */
457    public void writeTo(String zoneID, DataOutput out) throws IOException {
458        // pass false so zone id is not written out
459        DateTimeZone zone = toDateTimeZone(zoneID, false);
460
461        if (zone instanceof FixedDateTimeZone) {
462            out.writeByte('F'); // 'F' for fixed
463            out.writeUTF(zone.getNameKey(0));
464            writeMillis(out, zone.getOffset(0));
465            writeMillis(out, zone.getStandardOffset(0));
466        } else {
467            if (zone instanceof CachedDateTimeZone) {
468                out.writeByte('C'); // 'C' for cached, precalculated
469                zone = ((CachedDateTimeZone)zone).getUncachedZone();
470            } else {
471                out.writeByte('P'); // 'P' for precalculated, uncached
472            }
473            ((PrecalculatedZone)zone).writeTo(out);
474        }
475    }
476
477    /**
478     * Supports setting fields of year and moving between transitions.
479     */
480    private static final class OfYear {
481        static OfYear readFrom(DataInput in) throws IOException {
482            return new OfYear((char)in.readUnsignedByte(),
483                              (int)in.readUnsignedByte(),
484                              (int)in.readByte(),
485                              (int)in.readUnsignedByte(),
486                              in.readBoolean(),
487                              (int)readMillis(in));
488        }
489
490        // Is 'u', 'w', or 's'.
491        final char iMode;
492
493        final int iMonthOfYear;
494        final int iDayOfMonth;
495        final int iDayOfWeek;
496        final boolean iAdvance;
497        final int iMillisOfDay;
498
499        OfYear(char mode,
500               int monthOfYear,
501               int dayOfMonth,
502               int dayOfWeek, boolean advanceDayOfWeek,
503               int millisOfDay)
504        {
505            if (mode != 'u' && mode != 'w' && mode != 's') {
506                throw new IllegalArgumentException("Unknown mode: " + mode);
507            }
508
509            iMode = mode;
510            iMonthOfYear = monthOfYear;
511            iDayOfMonth = dayOfMonth;
512            iDayOfWeek = dayOfWeek;
513            iAdvance = advanceDayOfWeek;
514            iMillisOfDay = millisOfDay;
515        }
516
517        /**
518         * @param standardOffset standard offset just before instant
519         */
520        public long setInstant(int year, int standardOffset, int saveMillis) {
521            int offset;
522            if (iMode == 'w') {
523                offset = standardOffset + saveMillis;
524            } else if (iMode == 's') {
525                offset = standardOffset;
526            } else {
527                offset = 0;
528            }
529
530            Chronology chrono = ISOChronology.getInstanceUTC();
531            long millis = chrono.year().set(0, year);
532            millis = chrono.monthOfYear().set(millis, iMonthOfYear);
533            millis = chrono.millisOfDay().set(millis, iMillisOfDay);
534            millis = setDayOfMonth(chrono, millis);
535
536            if (iDayOfWeek != 0) {
537                millis = setDayOfWeek(chrono, millis);
538            }
539
540            // Convert from local time to UTC.
541            return millis - offset;
542        }
543
544        /**
545         * @param standardOffset standard offset just before next recurrence
546         */
547        public long next(long instant, int standardOffset, int saveMillis) {
548            int offset;
549            if (iMode == 'w') {
550                offset = standardOffset + saveMillis;
551            } else if (iMode == 's') {
552                offset = standardOffset;
553            } else {
554                offset = 0;
555            }
556
557            // Convert from UTC to local time.
558            instant += offset;
559
560            Chronology chrono = ISOChronology.getInstanceUTC();
561            long next = chrono.monthOfYear().set(instant, iMonthOfYear);
562            // Be lenient with millisOfDay.
563            next = chrono.millisOfDay().set(next, 0);
564            next = chrono.millisOfDay().add(next, iMillisOfDay);
565            next = setDayOfMonthNext(chrono, next);
566
567            if (iDayOfWeek == 0) {
568                if (next <= instant) {
569                    next = chrono.year().add(next, 1);
570                    next = setDayOfMonthNext(chrono, next);
571                }
572            } else {
573                next = setDayOfWeek(chrono, next);
574                if (next <= instant) {
575                    next = chrono.year().add(next, 1);
576                    next = chrono.monthOfYear().set(next, iMonthOfYear);
577                    next = setDayOfMonthNext(chrono, next);
578                    next = setDayOfWeek(chrono, next);
579                }
580            }
581
582            // Convert from local time to UTC.
583            return next - offset;
584        }
585
586        /**
587         * @param standardOffset standard offset just before previous recurrence
588         */
589        public long previous(long instant, int standardOffset, int saveMillis) {
590            int offset;
591            if (iMode == 'w') {
592                offset = standardOffset + saveMillis;
593            } else if (iMode == 's') {
594                offset = standardOffset;
595            } else {
596                offset = 0;
597            }
598
599            // Convert from UTC to local time.
600            instant += offset;
601
602            Chronology chrono = ISOChronology.getInstanceUTC();
603            long prev = chrono.monthOfYear().set(instant, iMonthOfYear);
604            // Be lenient with millisOfDay.
605            prev = chrono.millisOfDay().set(prev, 0);
606            prev = chrono.millisOfDay().add(prev, iMillisOfDay);
607            prev = setDayOfMonthPrevious(chrono, prev);
608
609            if (iDayOfWeek == 0) {
610                if (prev >= instant) {
611                    prev = chrono.year().add(prev, -1);
612                    prev = setDayOfMonthPrevious(chrono, prev);
613                }
614            } else {
615                prev = setDayOfWeek(chrono, prev);
616                if (prev >= instant) {
617                    prev = chrono.year().add(prev, -1);
618                    prev = chrono.monthOfYear().set(prev, iMonthOfYear);
619                    prev = setDayOfMonthPrevious(chrono, prev);
620                    prev = setDayOfWeek(chrono, prev);
621                }
622            }
623
624            // Convert from local time to UTC.
625            return prev - offset;
626        }
627
628        public boolean equals(Object obj) {
629            if (this == obj) {
630                return true;
631            }
632            if (obj instanceof OfYear) {
633                OfYear other = (OfYear)obj;
634                return
635                    iMode == other.iMode &&
636                    iMonthOfYear == other.iMonthOfYear &&
637                    iDayOfMonth == other.iDayOfMonth &&
638                    iDayOfWeek == other.iDayOfWeek &&
639                    iAdvance == other.iAdvance &&
640                    iMillisOfDay == other.iMillisOfDay;
641            }
642            return false;
643        }
644
645        /*
646        public String toString() {
647            return
648                "[OfYear]\n" + 
649                "Mode: " + iMode + '\n' +
650                "MonthOfYear: " + iMonthOfYear + '\n' +
651                "DayOfMonth: " + iDayOfMonth + '\n' +
652                "DayOfWeek: " + iDayOfWeek + '\n' +
653                "AdvanceDayOfWeek: " + iAdvance + '\n' +
654                "MillisOfDay: " + iMillisOfDay + '\n';
655        }
656        */
657
658        public void writeTo(DataOutput out) throws IOException {
659            out.writeByte(iMode);
660            out.writeByte(iMonthOfYear);
661            out.writeByte(iDayOfMonth);
662            out.writeByte(iDayOfWeek);
663            out.writeBoolean(iAdvance);
664            writeMillis(out, iMillisOfDay);
665        }
666
667        /**
668         * If month-day is 02-29 and year isn't leap, advances to next leap year.
669         */
670        private long setDayOfMonthNext(Chronology chrono, long next) {
671            try {
672                next = setDayOfMonth(chrono, next);
673            } catch (IllegalArgumentException e) {
674                if (iMonthOfYear == 2 && iDayOfMonth == 29) {
675                    while (chrono.year().isLeap(next) == false) {
676                        next = chrono.year().add(next, 1);
677                    }
678                    next = setDayOfMonth(chrono, next);
679                } else {
680                    throw e;
681                }
682            }
683            return next;
684        }
685
686        /**
687         * If month-day is 02-29 and year isn't leap, retreats to previous leap year.
688         */
689        private long setDayOfMonthPrevious(Chronology chrono, long prev) {
690            try {
691                prev = setDayOfMonth(chrono, prev);
692            } catch (IllegalArgumentException e) {
693                if (iMonthOfYear == 2 && iDayOfMonth == 29) {
694                    while (chrono.year().isLeap(prev) == false) {
695                        prev = chrono.year().add(prev, -1);
696                    }
697                    prev = setDayOfMonth(chrono, prev);
698                } else {
699                    throw e;
700                }
701            }
702            return prev;
703        }
704
705        private long setDayOfMonth(Chronology chrono, long instant) {
706            if (iDayOfMonth >= 0) {
707                instant = chrono.dayOfMonth().set(instant, iDayOfMonth);
708            } else {
709                instant = chrono.dayOfMonth().set(instant, 1);
710                instant = chrono.monthOfYear().add(instant, 1);
711                instant = chrono.dayOfMonth().add(instant, iDayOfMonth);
712            }
713            return instant;
714        }
715
716        private long setDayOfWeek(Chronology chrono, long instant) {
717            int dayOfWeek = chrono.dayOfWeek().get(instant);
718            int daysToAdd = iDayOfWeek - dayOfWeek;
719            if (daysToAdd != 0) {
720                if (iAdvance) {
721                    if (daysToAdd < 0) {
722                        daysToAdd += 7;
723                    }
724                } else {
725                    if (daysToAdd > 0) {
726                        daysToAdd -= 7;
727                    }
728                }
729                instant = chrono.dayOfWeek().add(instant, daysToAdd);
730            }
731            return instant;
732        }
733    }
734
735    /**
736     * Extends OfYear with a nameKey and savings.
737     */
738    private static final class Recurrence {
739        static Recurrence readFrom(DataInput in) throws IOException {
740            return new Recurrence(OfYear.readFrom(in), in.readUTF(), (int)readMillis(in));
741        }
742
743        final OfYear iOfYear;
744        final String iNameKey;
745        final int iSaveMillis;
746
747        Recurrence(OfYear ofYear, String nameKey, int saveMillis) {
748            iOfYear = ofYear;
749            iNameKey = nameKey;
750            iSaveMillis = saveMillis;
751        }
752
753        public OfYear getOfYear() {
754            return iOfYear;
755        }
756
757        /**
758         * @param standardOffset standard offset just before next recurrence
759         */
760        public long next(long instant, int standardOffset, int saveMillis) {
761            return iOfYear.next(instant, standardOffset, saveMillis);
762        }
763
764        /**
765         * @param standardOffset standard offset just before previous recurrence
766         */
767        public long previous(long instant, int standardOffset, int saveMillis) {
768            return iOfYear.previous(instant, standardOffset, saveMillis);
769        }
770
771        public String getNameKey() {
772            return iNameKey;
773        }
774
775        public int getSaveMillis() {
776            return iSaveMillis;
777        }
778
779        public boolean equals(Object obj) {
780            if (this == obj) {
781                return true;
782            }
783            if (obj instanceof Recurrence) {
784                Recurrence other = (Recurrence)obj;
785                return
786                    iSaveMillis == other.iSaveMillis &&
787                    iNameKey.equals(other.iNameKey) &&
788                    iOfYear.equals(other.iOfYear);
789            }
790            return false;
791        }
792
793        public void writeTo(DataOutput out) throws IOException {
794            iOfYear.writeTo(out);
795            out.writeUTF(iNameKey);
796            writeMillis(out, iSaveMillis);
797        }
798
799        Recurrence rename(String nameKey) {
800            return new Recurrence(iOfYear, nameKey, iSaveMillis);
801        }
802
803        Recurrence renameAppend(String appendNameKey) {
804            return rename((iNameKey + appendNameKey).intern());
805        }
806    }
807
808    /**
809     * Extends Recurrence with inclusive year limits.
810     */
811    private static final class Rule {
812        final Recurrence iRecurrence;
813        final int iFromYear; // inclusive
814        final int iToYear;   // inclusive
815
816        Rule(Recurrence recurrence, int fromYear, int toYear) {
817            iRecurrence = recurrence;
818            iFromYear = fromYear;
819            iToYear = toYear;
820        }
821
822        public int getFromYear() {
823            return iFromYear;
824        }
825
826        public int getToYear() {
827            return iToYear;
828        }
829
830        public OfYear getOfYear() {
831            return iRecurrence.getOfYear();
832        }
833
834        public String getNameKey() {
835            return iRecurrence.getNameKey();
836        }
837
838        public int getSaveMillis() {
839            return iRecurrence.getSaveMillis();
840        }
841
842        public long next(final long instant, int standardOffset, int saveMillis) {
843            Chronology chrono = ISOChronology.getInstanceUTC();
844
845            final int wallOffset = standardOffset + saveMillis;
846            long testInstant = instant;
847
848            int year;
849            if (instant == Long.MIN_VALUE) {
850                year = Integer.MIN_VALUE;
851            } else {
852                year = chrono.year().get(instant + wallOffset);
853            }
854
855            if (year < iFromYear) {
856                // First advance instant to start of from year.
857                testInstant = chrono.year().set(0, iFromYear) - wallOffset;
858                // Back off one millisecond to account for next recurrence
859                // being exactly at the beginning of the year.
860                testInstant -= 1;
861            }
862
863            long next = iRecurrence.next(testInstant, standardOffset, saveMillis);
864
865            if (next > instant) {
866                year = chrono.year().get(next + wallOffset);
867                if (year > iToYear) {
868                    // Out of range, return original value.
869                    next = instant;
870                }
871            }
872
873            return next;
874        }
875    }
876
877    private static final class Transition {
878        private final long iMillis;
879        private final String iNameKey;
880        private final int iWallOffset;
881        private final int iStandardOffset;
882
883        Transition(long millis, Transition tr) {
884            iMillis = millis;
885            iNameKey = tr.iNameKey;
886            iWallOffset = tr.iWallOffset;
887            iStandardOffset = tr.iStandardOffset;
888        }
889
890        Transition(long millis, Rule rule, int standardOffset) {
891            iMillis = millis;
892            iNameKey = rule.getNameKey();
893            iWallOffset = standardOffset + rule.getSaveMillis();
894            iStandardOffset = standardOffset;
895        }
896
897        Transition(long millis, String nameKey,
898                   int wallOffset, int standardOffset) {
899            iMillis = millis;
900            iNameKey = nameKey;
901            iWallOffset = wallOffset;
902            iStandardOffset = standardOffset;
903        }
904
905        public long getMillis() {
906            return iMillis;
907        }
908
909        public String getNameKey() {
910            return iNameKey;
911        }
912
913        public int getWallOffset() {
914            return iWallOffset;
915        }
916
917        public int getStandardOffset() {
918            return iStandardOffset;
919        }
920
921        public int getSaveMillis() {
922            return iWallOffset - iStandardOffset;
923        }
924
925        /**
926         * There must be a change in the millis, wall offsets or name keys.
927         */
928        public boolean isTransitionFrom(Transition other) {
929            if (other == null) {
930                return true;
931            }
932            return iMillis > other.iMillis &&
933                (iWallOffset != other.iWallOffset ||
934                 //iStandardOffset != other.iStandardOffset ||
935                 !(iNameKey.equals(other.iNameKey)));
936        }
937    }
938
939    private static final class RuleSet {
940        private static final int YEAR_LIMIT;
941
942        static {
943            // Don't pre-calculate more than 100 years into the future. Almost
944            // all zones will stop pre-calculating far sooner anyhow. Either a
945            // simple DST cycle is detected or the last rule is a fixed
946            // offset. If a zone has a fixed offset set more than 100 years
947            // into the future, then it won't be observed.
948            long now = DateTimeUtils.currentTimeMillis();
949            YEAR_LIMIT = ISOChronology.getInstanceUTC().year().get(now) + 100;
950        }
951
952        private int iStandardOffset;
953        private ArrayList<Rule> iRules;
954
955        // Optional.
956        private String iInitialNameKey;
957        private int iInitialSaveMillis;
958
959        // Upper limit is exclusive.
960        private int iUpperYear;
961        private OfYear iUpperOfYear;
962
963        RuleSet() {
964            iRules = new ArrayList<Rule>(10);
965            iUpperYear = Integer.MAX_VALUE;
966        }
967
968        /**
969         * Copy constructor.
970         */
971        RuleSet(RuleSet rs) {
972            iStandardOffset = rs.iStandardOffset;
973            iRules = new ArrayList<Rule>(rs.iRules);
974            iInitialNameKey = rs.iInitialNameKey;
975            iInitialSaveMillis = rs.iInitialSaveMillis;
976            iUpperYear = rs.iUpperYear;
977            iUpperOfYear = rs.iUpperOfYear;
978        }
979
980        public int getStandardOffset() {
981            return iStandardOffset;
982        }
983
984        public void setStandardOffset(int standardOffset) {
985            iStandardOffset = standardOffset;
986        }
987
988        public void setFixedSavings(String nameKey, int saveMillis) {
989            iInitialNameKey = nameKey;
990            iInitialSaveMillis = saveMillis;
991        }
992
993        public void addRule(Rule rule) {
994            if (!iRules.contains(rule)) {
995                iRules.add(rule);
996            }
997        }
998
999        public void setUpperLimit(int year, OfYear ofYear) {
1000            iUpperYear = year;
1001            iUpperOfYear = ofYear;
1002        }
1003
1004        /**
1005         * Returns a transition at firstMillis with the first name key and
1006         * offsets for this rule set. This method may return null.
1007         *
1008         * @param firstMillis millis of first transition
1009         */
1010        public Transition firstTransition(final long firstMillis) {
1011            if (iInitialNameKey != null) {
1012                // Initial zone info explicitly set, so don't search the rules.
1013                return new Transition(firstMillis, iInitialNameKey,
1014                                      iStandardOffset + iInitialSaveMillis, iStandardOffset);
1015            }
1016
1017            // Make a copy before we destroy the rules.
1018            ArrayList<Rule> copy = new ArrayList<Rule>(iRules);
1019
1020            // Iterate through all the transitions until firstMillis is
1021            // reached. Use the name key and savings for whatever rule reaches
1022            // the limit.
1023
1024            long millis = Long.MIN_VALUE;
1025            int saveMillis = 0;
1026            Transition first = null;
1027
1028            Transition next;
1029            while ((next = nextTransition(millis, saveMillis)) != null) {
1030                millis = next.getMillis();
1031
1032                if (millis == firstMillis) {
1033                    first = new Transition(firstMillis, next);
1034                    break;
1035                }
1036
1037                if (millis > firstMillis) {
1038                    if (first == null) {
1039                        // Find first rule without savings. This way a more
1040                        // accurate nameKey is found even though no rule
1041                        // extends to the RuleSet's lower limit.
1042                        for (Rule rule : copy) {
1043                            if (rule.getSaveMillis() == 0) {
1044                                first = new Transition(firstMillis, rule, iStandardOffset);
1045                                break;
1046                            }
1047                        }
1048                    }
1049                    if (first == null) {
1050                        // Found no rule without savings. Create a transition
1051                        // with no savings anyhow, and use the best available
1052                        // name key.
1053                        first = new Transition(firstMillis, next.getNameKey(),
1054                                               iStandardOffset, iStandardOffset);
1055                    }
1056                    break;
1057                }
1058                
1059                // Set first to the best transition found so far, but next
1060                // iteration may find something closer to lower limit.
1061                first = new Transition(firstMillis, next);
1062
1063                saveMillis = next.getSaveMillis();
1064            }
1065
1066            iRules = copy;
1067            return first;
1068        }
1069
1070        /**
1071         * Returns null if RuleSet is exhausted or upper limit reached. Calling
1072         * this method will throw away rules as they each become
1073         * exhausted. Copy the RuleSet before using it to compute transitions.
1074         *
1075         * Returned transition may be a duplicate from previous
1076         * transition. Caller must call isTransitionFrom to filter out
1077         * duplicates.
1078         *
1079         * @param saveMillis savings before next transition
1080         */
1081        public Transition nextTransition(final long instant, final int saveMillis) {
1082            Chronology chrono = ISOChronology.getInstanceUTC();
1083
1084            // Find next matching rule.
1085            Rule nextRule = null;
1086            long nextMillis = Long.MAX_VALUE;
1087            
1088            Iterator<Rule> it = iRules.iterator();
1089            while (it.hasNext()) {
1090                Rule rule = it.next();
1091                long next = rule.next(instant, iStandardOffset, saveMillis);
1092                if (next <= instant) {
1093                    it.remove();
1094                    continue;
1095                }
1096                // Even if next is same as previous next, choose the rule
1097                // in order for more recently added rules to override.
1098                if (next <= nextMillis) {
1099                    // Found a better match.
1100                    nextRule = rule;
1101                    nextMillis = next;
1102                }
1103            }
1104            
1105            if (nextRule == null) {
1106                return null;
1107            }
1108            
1109            // Stop precalculating if year reaches some arbitrary limit.
1110            if (chrono.year().get(nextMillis) >= YEAR_LIMIT) {
1111                return null;
1112            }
1113            
1114            // Check if upper limit reached or passed.
1115            if (iUpperYear < Integer.MAX_VALUE) {
1116                long upperMillis =
1117                    iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
1118                if (nextMillis >= upperMillis) {
1119                    // At or after upper limit.
1120                    return null;
1121                }
1122            }
1123            
1124            return new Transition(nextMillis, nextRule, iStandardOffset);
1125        }
1126
1127        /**
1128         * @param saveMillis savings before upper limit
1129         */
1130        public long getUpperLimit(int saveMillis) {
1131            if (iUpperYear == Integer.MAX_VALUE) {
1132                return Long.MAX_VALUE;
1133            }
1134            return iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
1135        }
1136
1137        /**
1138         * Returns null if none can be built.
1139         */
1140        public DSTZone buildTailZone(String id) {
1141            if (iRules.size() == 2) {
1142                Rule startRule = iRules.get(0);
1143                Rule endRule = iRules.get(1);
1144                if (startRule.getToYear() == Integer.MAX_VALUE &&
1145                    endRule.getToYear() == Integer.MAX_VALUE) {
1146
1147                    // With exactly two infinitely recurring rules left, a
1148                    // simple DSTZone can be formed.
1149
1150                    // The order of rules can come in any order, and it doesn't
1151                    // really matter which rule was chosen the 'start' and
1152                    // which is chosen the 'end'. DSTZone works properly either
1153                    // way.
1154                    return new DSTZone(id, iStandardOffset,
1155                                       startRule.iRecurrence, endRule.iRecurrence);
1156                }
1157            }
1158            return null;
1159        }
1160    }
1161
1162    private static final class DSTZone extends DateTimeZone {
1163        private static final long serialVersionUID = 6941492635554961361L;
1164
1165        static DSTZone readFrom(DataInput in, String id) throws IOException {
1166            return new DSTZone(id, (int)readMillis(in), 
1167                               Recurrence.readFrom(in), Recurrence.readFrom(in));
1168        }
1169
1170        final int iStandardOffset;
1171        final Recurrence iStartRecurrence;
1172        final Recurrence iEndRecurrence;
1173
1174        DSTZone(String id, int standardOffset,
1175                Recurrence startRecurrence, Recurrence endRecurrence) {
1176            super(id);
1177            iStandardOffset = standardOffset;
1178            iStartRecurrence = startRecurrence;
1179            iEndRecurrence = endRecurrence;
1180        }
1181
1182        public String getNameKey(long instant) {
1183            return findMatchingRecurrence(instant).getNameKey();
1184        }
1185
1186        public int getOffset(long instant) {
1187            return iStandardOffset + findMatchingRecurrence(instant).getSaveMillis();
1188        }
1189
1190        public int getStandardOffset(long instant) {
1191            return iStandardOffset;
1192        }
1193
1194        public boolean isFixed() {
1195            return false;
1196        }
1197
1198        public long nextTransition(long instant) {
1199            int standardOffset = iStandardOffset;
1200            Recurrence startRecurrence = iStartRecurrence;
1201            Recurrence endRecurrence = iEndRecurrence;
1202
1203            long start, end;
1204
1205            try {
1206                start = startRecurrence.next
1207                    (instant, standardOffset, endRecurrence.getSaveMillis());
1208                if (instant > 0 && start < 0) {
1209                    // Overflowed.
1210                    start = instant;
1211                }
1212            } catch (IllegalArgumentException e) {
1213                // Overflowed.
1214                start = instant;
1215            } catch (ArithmeticException e) {
1216                // Overflowed.
1217                start = instant;
1218            }
1219
1220            try {
1221                end = endRecurrence.next
1222                    (instant, standardOffset, startRecurrence.getSaveMillis());
1223                if (instant > 0 && end < 0) {
1224                    // Overflowed.
1225                    end = instant;
1226                }
1227            } catch (IllegalArgumentException e) {
1228                // Overflowed.
1229                end = instant;
1230            } catch (ArithmeticException e) {
1231                // Overflowed.
1232                end = instant;
1233            }
1234
1235            return (start > end) ? end : start;
1236        }
1237
1238        public long previousTransition(long instant) {
1239            // Increment in order to handle the case where instant is exactly at
1240            // a transition.
1241            instant++;
1242
1243            int standardOffset = iStandardOffset;
1244            Recurrence startRecurrence = iStartRecurrence;
1245            Recurrence endRecurrence = iEndRecurrence;
1246
1247            long start, end;
1248
1249            try {
1250                start = startRecurrence.previous
1251                    (instant, standardOffset, endRecurrence.getSaveMillis());
1252                if (instant < 0 && start > 0) {
1253                    // Overflowed.
1254                    start = instant;
1255                }
1256            } catch (IllegalArgumentException e) {
1257                // Overflowed.
1258                start = instant;
1259            } catch (ArithmeticException e) {
1260                // Overflowed.
1261                start = instant;
1262            }
1263
1264            try {
1265                end = endRecurrence.previous
1266                    (instant, standardOffset, startRecurrence.getSaveMillis());
1267                if (instant < 0 && end > 0) {
1268                    // Overflowed.
1269                    end = instant;
1270                }
1271            } catch (IllegalArgumentException e) {
1272                // Overflowed.
1273                end = instant;
1274            } catch (ArithmeticException e) {
1275                // Overflowed.
1276                end = instant;
1277            }
1278
1279            return ((start > end) ? start : end) - 1;
1280        }
1281
1282        public boolean equals(Object obj) {
1283            if (this == obj) {
1284                return true;
1285            }
1286            if (obj instanceof DSTZone) {
1287                DSTZone other = (DSTZone)obj;
1288                return
1289                    getID().equals(other.getID()) &&
1290                    iStandardOffset == other.iStandardOffset &&
1291                    iStartRecurrence.equals(other.iStartRecurrence) &&
1292                    iEndRecurrence.equals(other.iEndRecurrence);
1293            }
1294            return false;
1295        }
1296
1297        public void writeTo(DataOutput out) throws IOException {
1298            writeMillis(out, iStandardOffset);
1299            iStartRecurrence.writeTo(out);
1300            iEndRecurrence.writeTo(out);
1301        }
1302
1303        private Recurrence findMatchingRecurrence(long instant) {
1304            int standardOffset = iStandardOffset;
1305            Recurrence startRecurrence = iStartRecurrence;
1306            Recurrence endRecurrence = iEndRecurrence;
1307
1308            long start, end;
1309
1310            try {
1311                start = startRecurrence.next
1312                    (instant, standardOffset, endRecurrence.getSaveMillis());
1313            } catch (IllegalArgumentException e) {
1314                // Overflowed.
1315                start = instant;
1316            } catch (ArithmeticException e) {
1317                // Overflowed.
1318                start = instant;
1319            }
1320
1321            try {
1322                end = endRecurrence.next
1323                    (instant, standardOffset, startRecurrence.getSaveMillis());
1324            } catch (IllegalArgumentException e) {
1325                // Overflowed.
1326                end = instant;
1327            } catch (ArithmeticException e) {
1328                // Overflowed.
1329                end = instant;
1330            }
1331
1332            return (start > end) ? startRecurrence : endRecurrence;
1333        }
1334    }
1335
1336    private static final class PrecalculatedZone extends DateTimeZone {
1337        private static final long serialVersionUID = 7811976468055766265L;
1338
1339        static PrecalculatedZone readFrom(DataInput in, String id) throws IOException {
1340            // Read string pool.
1341            int poolSize = in.readUnsignedShort();
1342            String[] pool = new String[poolSize];
1343            for (int i=0; i<poolSize; i++) {
1344                pool[i] = in.readUTF();
1345            }
1346
1347            int size = in.readInt();
1348            long[] transitions = new long[size];
1349            int[] wallOffsets = new int[size];
1350            int[] standardOffsets = new int[size];
1351            String[] nameKeys = new String[size];
1352            
1353            for (int i=0; i<size; i++) {
1354                transitions[i] = readMillis(in);
1355                wallOffsets[i] = (int)readMillis(in);
1356                standardOffsets[i] = (int)readMillis(in);
1357                try {
1358                    int index;
1359                    if (poolSize < 256) {
1360                        index = in.readUnsignedByte();
1361                    } else {
1362                        index = in.readUnsignedShort();
1363                    }
1364                    nameKeys[i] = pool[index];
1365                } catch (ArrayIndexOutOfBoundsException e) {
1366                    throw new IOException("Invalid encoding");
1367                }
1368            }
1369
1370            DSTZone tailZone = null;
1371            if (in.readBoolean()) {
1372                tailZone = DSTZone.readFrom(in, id);
1373            }
1374
1375            return new PrecalculatedZone
1376                (id, transitions, wallOffsets, standardOffsets, nameKeys, tailZone);
1377        }
1378
1379        /**
1380         * Factory to create instance from builder.
1381         * 
1382         * @param id  the zone id
1383         * @param outputID  true if the zone id should be output
1384         * @param transitions  the list of Transition objects
1385         * @param tailZone  optional zone for getting info beyond precalculated tables
1386         */
1387        static PrecalculatedZone create(String id, boolean outputID, ArrayList<Transition> transitions,
1388                                        DSTZone tailZone) {
1389            int size = transitions.size();
1390            if (size == 0) {
1391                throw new IllegalArgumentException();
1392            }
1393
1394            long[] trans = new long[size];
1395            int[] wallOffsets = new int[size];
1396            int[] standardOffsets = new int[size];
1397            String[] nameKeys = new String[size];
1398
1399            Transition last = null;
1400            for (int i=0; i<size; i++) {
1401                Transition tr = transitions.get(i);
1402
1403                if (!tr.isTransitionFrom(last)) {
1404                    throw new IllegalArgumentException(id);
1405                }
1406
1407                trans[i] = tr.getMillis();
1408                wallOffsets[i] = tr.getWallOffset();
1409                standardOffsets[i] = tr.getStandardOffset();
1410                nameKeys[i] = tr.getNameKey();
1411
1412                last = tr;
1413            }
1414
1415            // Some timezones (Australia) have the same name key for
1416            // summer and winter which messes everything up. Fix it here.
1417            String[] zoneNameData = new String[5];
1418            String[][] zoneStrings = new DateFormatSymbols(Locale.ENGLISH).getZoneStrings();
1419            for (int j = 0; j < zoneStrings.length; j++) {
1420                String[] set = zoneStrings[j];
1421                if (set != null && set.length == 5 && id.equals(set[0])) {
1422                    zoneNameData = set;
1423                }
1424            }
1425
1426            Chronology chrono = ISOChronology.getInstanceUTC();
1427
1428            for (int i = 0; i < nameKeys.length - 1; i++) {
1429                String curNameKey = nameKeys[i];
1430                String nextNameKey = nameKeys[i + 1];
1431                long curOffset = wallOffsets[i];
1432                long nextOffset = wallOffsets[i + 1];
1433                long curStdOffset = standardOffsets[i];
1434                long nextStdOffset = standardOffsets[i + 1];
1435                Period p = new Period(trans[i], trans[i + 1], PeriodType.yearMonthDay(), chrono);
1436                if (curOffset != nextOffset &&
1437                        curStdOffset == nextStdOffset &&
1438                        curNameKey.equals(nextNameKey) &&
1439                        p.getYears() == 0 && p.getMonths() > 4 && p.getMonths() < 8 &&
1440                        curNameKey.equals(zoneNameData[2]) &&
1441                        curNameKey.equals(zoneNameData[4])) {
1442                    
1443                    if (ZoneInfoCompiler.verbose()) {
1444                        System.out.println("Fixing duplicate name key - " + nextNameKey);
1445                        System.out.println("     - " + new DateTime(trans[i], chrono) +
1446                                           " - " + new DateTime(trans[i + 1], chrono));
1447                    }
1448                    if (curOffset > nextOffset) {
1449                        nameKeys[i] = (curNameKey + "-Summer").intern();
1450                    } else if (curOffset < nextOffset) {
1451                        nameKeys[i + 1] = (nextNameKey + "-Summer").intern();
1452                        i++;
1453                    }
1454                }
1455            }
1456
1457            if (tailZone != null) {
1458                if (tailZone.iStartRecurrence.getNameKey()
1459                    .equals(tailZone.iEndRecurrence.getNameKey())) {
1460                    if (ZoneInfoCompiler.verbose()) {
1461                        System.out.println("Fixing duplicate recurrent name key - " +
1462                                           tailZone.iStartRecurrence.getNameKey());
1463                    }
1464                    if (tailZone.iStartRecurrence.getSaveMillis() > 0) {
1465                        tailZone = new DSTZone(
1466                            tailZone.getID(),
1467                            tailZone.iStandardOffset,
1468                            tailZone.iStartRecurrence.renameAppend("-Summer"),
1469                            tailZone.iEndRecurrence);
1470                    } else {
1471                        tailZone = new DSTZone(
1472                            tailZone.getID(),
1473                            tailZone.iStandardOffset,
1474                            tailZone.iStartRecurrence,
1475                            tailZone.iEndRecurrence.renameAppend("-Summer"));
1476                    }
1477                }
1478            }
1479            
1480            return new PrecalculatedZone
1481                ((outputID ? id : ""), trans, wallOffsets, standardOffsets, nameKeys, tailZone);
1482        }
1483
1484        // All array fields have the same length.
1485
1486        private final long[] iTransitions;
1487
1488        private final int[] iWallOffsets;
1489        private final int[] iStandardOffsets;
1490        private final String[] iNameKeys;
1491
1492        private final DSTZone iTailZone;
1493
1494        /**
1495         * Constructor used ONLY for valid input, loaded via static methods.
1496         */
1497        private PrecalculatedZone(String id, long[] transitions, int[] wallOffsets,
1498                          int[] standardOffsets, String[] nameKeys, DSTZone tailZone)
1499        {
1500            super(id);
1501            iTransitions = transitions;
1502            iWallOffsets = wallOffsets;
1503            iStandardOffsets = standardOffsets;
1504            iNameKeys = nameKeys;
1505            iTailZone = tailZone;
1506        }
1507
1508        public String getNameKey(long instant) {
1509            long[] transitions = iTransitions;
1510            int i = Arrays.binarySearch(transitions, instant);
1511            if (i >= 0) {
1512                return iNameKeys[i];
1513            }
1514            i = ~i;
1515            if (i < transitions.length) {
1516                if (i > 0) {
1517                    return iNameKeys[i - 1];
1518                }
1519                return "UTC";
1520            }
1521            if (iTailZone == null) {
1522                return iNameKeys[i - 1];
1523            }
1524            return iTailZone.getNameKey(instant);
1525        }
1526
1527        public int getOffset(long instant) {
1528            long[] transitions = iTransitions;
1529            int i = Arrays.binarySearch(transitions, instant);
1530            if (i >= 0) {
1531                return iWallOffsets[i];
1532            }
1533            i = ~i;
1534            if (i < transitions.length) {
1535                if (i > 0) {
1536                    return iWallOffsets[i - 1];
1537                }
1538                return 0;
1539            }
1540            if (iTailZone == null) {
1541                return iWallOffsets[i - 1];
1542            }
1543            return iTailZone.getOffset(instant);
1544        }
1545
1546        public int getStandardOffset(long instant) {
1547            long[] transitions = iTransitions;
1548            int i = Arrays.binarySearch(transitions, instant);
1549            if (i >= 0) {
1550                return iStandardOffsets[i];
1551            }
1552            i = ~i;
1553            if (i < transitions.length) {
1554                if (i > 0) {
1555                    return iStandardOffsets[i - 1];
1556                }
1557                return 0;
1558            }
1559            if (iTailZone == null) {
1560                return iStandardOffsets[i - 1];
1561            }
1562            return iTailZone.getStandardOffset(instant);
1563        }
1564
1565        public boolean isFixed() {
1566            return false;
1567        }
1568
1569        public long nextTransition(long instant) {
1570            long[] transitions = iTransitions;
1571            int i = Arrays.binarySearch(transitions, instant);
1572            i = (i >= 0) ? (i + 1) : ~i;
1573            if (i < transitions.length) {
1574                return transitions[i];
1575            }
1576            if (iTailZone == null) {
1577                return instant;
1578            }
1579            long end = transitions[transitions.length - 1];
1580            if (instant < end) {
1581                instant = end;
1582            }
1583            return iTailZone.nextTransition(instant);
1584        }
1585
1586        public long previousTransition(long instant) {
1587            long[] transitions = iTransitions;
1588            int i = Arrays.binarySearch(transitions, instant);
1589            if (i >= 0) {
1590                if (instant > Long.MIN_VALUE) {
1591                    return instant - 1;
1592                }
1593                return instant;
1594            }
1595            i = ~i;
1596            if (i < transitions.length) {
1597                if (i > 0) {
1598                    long prev = transitions[i - 1];
1599                    if (prev > Long.MIN_VALUE) {
1600                        return prev - 1;
1601                    }
1602                }
1603                return instant;
1604            }
1605            if (iTailZone != null) {
1606                long prev = iTailZone.previousTransition(instant);
1607                if (prev < instant) {
1608                    return prev;
1609                }
1610            }
1611            long prev = transitions[i - 1];
1612            if (prev > Long.MIN_VALUE) {
1613                return prev - 1;
1614            }
1615            return instant;
1616        }
1617
1618        public boolean equals(Object obj) {
1619            if (this == obj) {
1620                return true;
1621            }
1622            if (obj instanceof PrecalculatedZone) {
1623                PrecalculatedZone other = (PrecalculatedZone)obj;
1624                return
1625                    getID().equals(other.getID()) &&
1626                    Arrays.equals(iTransitions, other.iTransitions) &&
1627                    Arrays.equals(iNameKeys, other.iNameKeys) &&
1628                    Arrays.equals(iWallOffsets, other.iWallOffsets) &&
1629                    Arrays.equals(iStandardOffsets, other.iStandardOffsets) &&
1630                    ((iTailZone == null)
1631                     ? (null == other.iTailZone)
1632                     : (iTailZone.equals(other.iTailZone)));
1633            }
1634            return false;
1635        }
1636
1637        public void writeTo(DataOutput out) throws IOException {
1638            int size = iTransitions.length;
1639
1640            // Create unique string pool.
1641            Set<String> poolSet = new HashSet<String>();
1642            for (int i=0; i<size; i++) {
1643                poolSet.add(iNameKeys[i]);
1644            }
1645
1646            int poolSize = poolSet.size();
1647            if (poolSize > 65535) {
1648                throw new UnsupportedOperationException("String pool is too large");
1649            }
1650            String[] pool = new String[poolSize];
1651            Iterator<String> it = poolSet.iterator();
1652            for (int i=0; it.hasNext(); i++) {
1653                pool[i] = it.next();
1654            }
1655
1656            // Write out the pool.
1657            out.writeShort(poolSize);
1658            for (int i=0; i<poolSize; i++) {
1659                out.writeUTF(pool[i]);
1660            }
1661
1662            out.writeInt(size);
1663
1664            for (int i=0; i<size; i++) {
1665                writeMillis(out, iTransitions[i]);
1666                writeMillis(out, iWallOffsets[i]);
1667                writeMillis(out, iStandardOffsets[i]);
1668                
1669                // Find pool index and write it out.
1670                String nameKey = iNameKeys[i];
1671                for (int j=0; j<poolSize; j++) {
1672                    if (pool[j].equals(nameKey)) {
1673                        if (poolSize < 256) {
1674                            out.writeByte(j);
1675                        } else {
1676                            out.writeShort(j);
1677                        }
1678                        break;
1679                    }
1680                }
1681            }
1682
1683            out.writeBoolean(iTailZone != null);
1684            if (iTailZone != null) {
1685                iTailZone.writeTo(out);
1686            }
1687        }
1688
1689        public boolean isCachable() {
1690            if (iTailZone != null) {
1691                return true;
1692            }
1693            long[] transitions = iTransitions;
1694            if (transitions.length <= 1) {
1695                return false;
1696            }
1697
1698            // Add up all the distances between transitions that are less than
1699            // about two years.
1700            double distances = 0;
1701            int count = 0;
1702
1703            for (int i=1; i<transitions.length; i++) {
1704                long diff = transitions[i] - transitions[i - 1];
1705                if (diff < ((366L + 365) * 24 * 60 * 60 * 1000)) {
1706                    distances += (double)diff;
1707                    count++;
1708                }
1709            }
1710
1711            if (count > 0) {
1712                double avg = distances / count;
1713                avg /= 24 * 60 * 60 * 1000;
1714                if (avg >= 25) {
1715                    // Only bother caching if average distance between
1716                    // transitions is at least 25 days. Why 25?
1717                    // CachedDateTimeZone is more efficient if the distance
1718                    // between transitions is large. With an average of 25, it
1719                    // will on average perform about 2 tests per cache
1720                    // hit. (49.7 / 25) is approximately 2.
1721                    return true;
1722                }
1723            }
1724
1725            return false;
1726        }
1727    }
1728}