001    /*
002     *  Copyright 2001-2005 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     */
016    package org.joda.time.tz;
017    
018    import java.io.DataInput;
019    import java.io.DataInputStream;
020    import java.io.DataOutput;
021    import java.io.DataOutputStream;
022    import java.io.IOException;
023    import java.io.InputStream;
024    import java.io.OutputStream;
025    import java.text.DateFormatSymbols;
026    import java.util.ArrayList;
027    import java.util.Arrays;
028    import java.util.HashSet;
029    import java.util.Iterator;
030    import java.util.Locale;
031    import java.util.Set;
032    
033    import org.joda.time.Chronology;
034    import org.joda.time.DateTime;
035    import org.joda.time.DateTimeUtils;
036    import org.joda.time.DateTimeZone;
037    import org.joda.time.Period;
038    import org.joda.time.PeriodType;
039    import 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     */
086    public 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 iRuleSets;
224    
225        public DateTimeZoneBuilder() {
226            iRuleSets = new ArrayList(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            OfYear ofYear = new OfYear
253                (mode, monthOfYear, dayOfMonth, dayOfWeek, advanceDayOfWeek, millisOfDay);
254            if (iRuleSets.size() > 0) {
255                RuleSet lastRuleSet = (RuleSet)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 (RuleSet)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 transitions = new ArrayList();
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 = (RuleSet)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 = (Transition)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 transitions, Transition tr) {
404            int size = transitions.size();
405            if (size == 0) {
406                transitions.add(tr);
407                return true;
408            }
409    
410            Transition last = (Transition)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 = ((Transition)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 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(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(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 copy = new ArrayList(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                            Iterator it = copy.iterator();
1043                            while (it.hasNext()) {
1044                                Rule rule = (Rule)it.next();
1045                                if (rule.getSaveMillis() == 0) {
1046                                    first = new Transition(firstMillis, rule, iStandardOffset);
1047                                    break;
1048                                }
1049                            }
1050                        }
1051                        if (first == null) {
1052                            // Found no rule without savings. Create a transition
1053                            // with no savings anyhow, and use the best available
1054                            // name key.
1055                            first = new Transition(firstMillis, next.getNameKey(),
1056                                                   iStandardOffset, iStandardOffset);
1057                        }
1058                        break;
1059                    }
1060                    
1061                    // Set first to the best transition found so far, but next
1062                    // iteration may find something closer to lower limit.
1063                    first = new Transition(firstMillis, next);
1064    
1065                    saveMillis = next.getSaveMillis();
1066                }
1067    
1068                iRules = copy;
1069                return first;
1070            }
1071    
1072            /**
1073             * Returns null if RuleSet is exhausted or upper limit reached. Calling
1074             * this method will throw away rules as they each become
1075             * exhausted. Copy the RuleSet before using it to compute transitions.
1076             *
1077             * Returned transition may be a duplicate from previous
1078             * transition. Caller must call isTransitionFrom to filter out
1079             * duplicates.
1080             *
1081             * @param saveMillis savings before next transition
1082             */
1083            public Transition nextTransition(final long instant, final int saveMillis) {
1084                Chronology chrono = ISOChronology.getInstanceUTC();
1085    
1086                // Find next matching rule.
1087                Rule nextRule = null;
1088                long nextMillis = Long.MAX_VALUE;
1089                
1090                Iterator it = iRules.iterator();
1091                while (it.hasNext()) {
1092                    Rule rule = (Rule)it.next();
1093                    long next = rule.next(instant, iStandardOffset, saveMillis);
1094                    if (next <= instant) {
1095                        it.remove();
1096                        continue;
1097                    }
1098                    // Even if next is same as previous next, choose the rule
1099                    // in order for more recently added rules to override.
1100                    if (next <= nextMillis) {
1101                        // Found a better match.
1102                        nextRule = rule;
1103                        nextMillis = next;
1104                    }
1105                }
1106                
1107                if (nextRule == null) {
1108                    return null;
1109                }
1110                
1111                // Stop precalculating if year reaches some arbitrary limit.
1112                if (chrono.year().get(nextMillis) >= YEAR_LIMIT) {
1113                    return null;
1114                }
1115                
1116                // Check if upper limit reached or passed.
1117                if (iUpperYear < Integer.MAX_VALUE) {
1118                    long upperMillis =
1119                        iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
1120                    if (nextMillis >= upperMillis) {
1121                        // At or after upper limit.
1122                        return null;
1123                    }
1124                }
1125                
1126                return new Transition(nextMillis, nextRule, iStandardOffset);
1127            }
1128    
1129            /**
1130             * @param saveMillis savings before upper limit
1131             */
1132            public long getUpperLimit(int saveMillis) {
1133                if (iUpperYear == Integer.MAX_VALUE) {
1134                    return Long.MAX_VALUE;
1135                }
1136                return iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
1137            }
1138    
1139            /**
1140             * Returns null if none can be built.
1141             */
1142            public DSTZone buildTailZone(String id) {
1143                if (iRules.size() == 2) {
1144                    Rule startRule = (Rule)iRules.get(0);
1145                    Rule endRule = (Rule)iRules.get(1);
1146                    if (startRule.getToYear() == Integer.MAX_VALUE &&
1147                        endRule.getToYear() == Integer.MAX_VALUE) {
1148    
1149                        // With exactly two infinitely recurring rules left, a
1150                        // simple DSTZone can be formed.
1151    
1152                        // The order of rules can come in any order, and it doesn't
1153                        // really matter which rule was chosen the 'start' and
1154                        // which is chosen the 'end'. DSTZone works properly either
1155                        // way.
1156                        return new DSTZone(id, iStandardOffset,
1157                                           startRule.iRecurrence, endRule.iRecurrence);
1158                    }
1159                }
1160                return null;
1161            }
1162        }
1163    
1164        private static final class DSTZone extends DateTimeZone {
1165            private static final long serialVersionUID = 6941492635554961361L;
1166    
1167            static DSTZone readFrom(DataInput in, String id) throws IOException {
1168                return new DSTZone(id, (int)readMillis(in), 
1169                                   Recurrence.readFrom(in), Recurrence.readFrom(in));
1170            }
1171    
1172            final int iStandardOffset;
1173            final Recurrence iStartRecurrence;
1174            final Recurrence iEndRecurrence;
1175    
1176            DSTZone(String id, int standardOffset,
1177                    Recurrence startRecurrence, Recurrence endRecurrence) {
1178                super(id);
1179                iStandardOffset = standardOffset;
1180                iStartRecurrence = startRecurrence;
1181                iEndRecurrence = endRecurrence;
1182            }
1183    
1184            public String getNameKey(long instant) {
1185                return findMatchingRecurrence(instant).getNameKey();
1186            }
1187    
1188            public int getOffset(long instant) {
1189                return iStandardOffset + findMatchingRecurrence(instant).getSaveMillis();
1190            }
1191    
1192            public int getStandardOffset(long instant) {
1193                return iStandardOffset;
1194            }
1195    
1196            public boolean isFixed() {
1197                return false;
1198            }
1199    
1200            public long nextTransition(long instant) {
1201                int standardOffset = iStandardOffset;
1202                Recurrence startRecurrence = iStartRecurrence;
1203                Recurrence endRecurrence = iEndRecurrence;
1204    
1205                long start, end;
1206    
1207                try {
1208                    start = startRecurrence.next
1209                        (instant, standardOffset, endRecurrence.getSaveMillis());
1210                    if (instant > 0 && start < 0) {
1211                        // Overflowed.
1212                        start = instant;
1213                    }
1214                } catch (IllegalArgumentException e) {
1215                    // Overflowed.
1216                    start = instant;
1217                } catch (ArithmeticException e) {
1218                    // Overflowed.
1219                    start = instant;
1220                }
1221    
1222                try {
1223                    end = endRecurrence.next
1224                        (instant, standardOffset, startRecurrence.getSaveMillis());
1225                    if (instant > 0 && end < 0) {
1226                        // Overflowed.
1227                        end = instant;
1228                    }
1229                } catch (IllegalArgumentException e) {
1230                    // Overflowed.
1231                    end = instant;
1232                } catch (ArithmeticException e) {
1233                    // Overflowed.
1234                    end = instant;
1235                }
1236    
1237                return (start > end) ? end : start;
1238            }
1239    
1240            public long previousTransition(long instant) {
1241                // Increment in order to handle the case where instant is exactly at
1242                // a transition.
1243                instant++;
1244    
1245                int standardOffset = iStandardOffset;
1246                Recurrence startRecurrence = iStartRecurrence;
1247                Recurrence endRecurrence = iEndRecurrence;
1248    
1249                long start, end;
1250    
1251                try {
1252                    start = startRecurrence.previous
1253                        (instant, standardOffset, endRecurrence.getSaveMillis());
1254                    if (instant < 0 && start > 0) {
1255                        // Overflowed.
1256                        start = instant;
1257                    }
1258                } catch (IllegalArgumentException e) {
1259                    // Overflowed.
1260                    start = instant;
1261                } catch (ArithmeticException e) {
1262                    // Overflowed.
1263                    start = instant;
1264                }
1265    
1266                try {
1267                    end = endRecurrence.previous
1268                        (instant, standardOffset, startRecurrence.getSaveMillis());
1269                    if (instant < 0 && end > 0) {
1270                        // Overflowed.
1271                        end = instant;
1272                    }
1273                } catch (IllegalArgumentException e) {
1274                    // Overflowed.
1275                    end = instant;
1276                } catch (ArithmeticException e) {
1277                    // Overflowed.
1278                    end = instant;
1279                }
1280    
1281                return ((start > end) ? start : end) - 1;
1282            }
1283    
1284            public boolean equals(Object obj) {
1285                if (this == obj) {
1286                    return true;
1287                }
1288                if (obj instanceof DSTZone) {
1289                    DSTZone other = (DSTZone)obj;
1290                    return
1291                        getID().equals(other.getID()) &&
1292                        iStandardOffset == other.iStandardOffset &&
1293                        iStartRecurrence.equals(other.iStartRecurrence) &&
1294                        iEndRecurrence.equals(other.iEndRecurrence);
1295                }
1296                return false;
1297            }
1298    
1299            public void writeTo(DataOutput out) throws IOException {
1300                writeMillis(out, iStandardOffset);
1301                iStartRecurrence.writeTo(out);
1302                iEndRecurrence.writeTo(out);
1303            }
1304    
1305            private Recurrence findMatchingRecurrence(long instant) {
1306                int standardOffset = iStandardOffset;
1307                Recurrence startRecurrence = iStartRecurrence;
1308                Recurrence endRecurrence = iEndRecurrence;
1309    
1310                long start, end;
1311    
1312                try {
1313                    start = startRecurrence.next
1314                        (instant, standardOffset, endRecurrence.getSaveMillis());
1315                } catch (IllegalArgumentException e) {
1316                    // Overflowed.
1317                    start = instant;
1318                } catch (ArithmeticException e) {
1319                    // Overflowed.
1320                    start = instant;
1321                }
1322    
1323                try {
1324                    end = endRecurrence.next
1325                        (instant, standardOffset, startRecurrence.getSaveMillis());
1326                } catch (IllegalArgumentException e) {
1327                    // Overflowed.
1328                    end = instant;
1329                } catch (ArithmeticException e) {
1330                    // Overflowed.
1331                    end = instant;
1332                }
1333    
1334                return (start > end) ? startRecurrence : endRecurrence;
1335            }
1336        }
1337    
1338        private static final class PrecalculatedZone extends DateTimeZone {
1339            private static final long serialVersionUID = 7811976468055766265L;
1340    
1341            static PrecalculatedZone readFrom(DataInput in, String id) throws IOException {
1342                // Read string pool.
1343                int poolSize = in.readUnsignedShort();
1344                String[] pool = new String[poolSize];
1345                for (int i=0; i<poolSize; i++) {
1346                    pool[i] = in.readUTF();
1347                }
1348    
1349                int size = in.readInt();
1350                long[] transitions = new long[size];
1351                int[] wallOffsets = new int[size];
1352                int[] standardOffsets = new int[size];
1353                String[] nameKeys = new String[size];
1354                
1355                for (int i=0; i<size; i++) {
1356                    transitions[i] = readMillis(in);
1357                    wallOffsets[i] = (int)readMillis(in);
1358                    standardOffsets[i] = (int)readMillis(in);
1359                    try {
1360                        int index;
1361                        if (poolSize < 256) {
1362                            index = in.readUnsignedByte();
1363                        } else {
1364                            index = in.readUnsignedShort();
1365                        }
1366                        nameKeys[i] = pool[index];
1367                    } catch (ArrayIndexOutOfBoundsException e) {
1368                        throw new IOException("Invalid encoding");
1369                    }
1370                }
1371    
1372                DSTZone tailZone = null;
1373                if (in.readBoolean()) {
1374                    tailZone = DSTZone.readFrom(in, id);
1375                }
1376    
1377                return new PrecalculatedZone
1378                    (id, transitions, wallOffsets, standardOffsets, nameKeys, tailZone);
1379            }
1380    
1381            /**
1382             * Factory to create instance from builder.
1383             * 
1384             * @param id  the zone id
1385             * @param outputID  true if the zone id should be output
1386             * @param transitions  the list of Transition objects
1387             * @param tailZone  optional zone for getting info beyond precalculated tables
1388             */
1389            static PrecalculatedZone create(String id, boolean outputID, ArrayList transitions,
1390                                            DSTZone tailZone) {
1391                int size = transitions.size();
1392                if (size == 0) {
1393                    throw new IllegalArgumentException();
1394                }
1395    
1396                long[] trans = new long[size];
1397                int[] wallOffsets = new int[size];
1398                int[] standardOffsets = new int[size];
1399                String[] nameKeys = new String[size];
1400    
1401                Transition last = null;
1402                for (int i=0; i<size; i++) {
1403                    Transition tr = (Transition)transitions.get(i);
1404    
1405                    if (!tr.isTransitionFrom(last)) {
1406                        throw new IllegalArgumentException(id);
1407                    }
1408    
1409                    trans[i] = tr.getMillis();
1410                    wallOffsets[i] = tr.getWallOffset();
1411                    standardOffsets[i] = tr.getStandardOffset();
1412                    nameKeys[i] = tr.getNameKey();
1413    
1414                    last = tr;
1415                }
1416    
1417                // Some timezones (Australia) have the same name key for
1418                // summer and winter which messes everything up. Fix it here.
1419                String[] zoneNameData = new String[5];
1420                String[][] zoneStrings = new DateFormatSymbols(Locale.ENGLISH).getZoneStrings();
1421                for (int j = 0; j < zoneStrings.length; j++) {
1422                    String[] set = zoneStrings[j];
1423                    if (set != null && set.length == 5 && id.equals(set[0])) {
1424                        zoneNameData = set;
1425                    }
1426                }
1427    
1428                Chronology chrono = ISOChronology.getInstanceUTC();
1429    
1430                for (int i = 0; i < nameKeys.length - 1; i++) {
1431                    String curNameKey = nameKeys[i];
1432                    String nextNameKey = nameKeys[i + 1];
1433                    long curOffset = wallOffsets[i];
1434                    long nextOffset = wallOffsets[i + 1];
1435                    long curStdOffset = standardOffsets[i];
1436                    long nextStdOffset = standardOffsets[i + 1];
1437                    Period p = new Period(trans[i], trans[i + 1], PeriodType.yearMonthDay(), chrono);
1438                    if (curOffset != nextOffset &&
1439                            curStdOffset == nextStdOffset &&
1440                            curNameKey.equals(nextNameKey) &&
1441                            p.getYears() == 0 && p.getMonths() > 4 && p.getMonths() < 8 &&
1442                            curNameKey.equals(zoneNameData[2]) &&
1443                            curNameKey.equals(zoneNameData[4])) {
1444                        
1445                        System.out.println("Fixing duplicate name key - " + nextNameKey);
1446                        System.out.println("     - " + new DateTime(trans[i], chrono) +
1447                                           " - " + new DateTime(trans[i + 1], chrono));
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                        System.out.println("Fixing duplicate recurrent name key - " +
1461                                           tailZone.iStartRecurrence.getNameKey());
1462                        if (tailZone.iStartRecurrence.getSaveMillis() > 0) {
1463                            tailZone = new DSTZone(
1464                                tailZone.getID(),
1465                                tailZone.iStandardOffset,
1466                                tailZone.iStartRecurrence.renameAppend("-Summer"),
1467                                tailZone.iEndRecurrence);
1468                        } else {
1469                            tailZone = new DSTZone(
1470                                tailZone.getID(),
1471                                tailZone.iStandardOffset,
1472                                tailZone.iStartRecurrence,
1473                                tailZone.iEndRecurrence.renameAppend("-Summer"));
1474                        }
1475                    }
1476                }
1477                
1478                return new PrecalculatedZone
1479                    ((outputID ? id : ""), trans, wallOffsets, standardOffsets, nameKeys, tailZone);
1480            }
1481    
1482            // All array fields have the same length.
1483    
1484            private final long[] iTransitions;
1485    
1486            private final int[] iWallOffsets;
1487            private final int[] iStandardOffsets;
1488            private final String[] iNameKeys;
1489    
1490            private final DSTZone iTailZone;
1491    
1492            /**
1493             * Constructor used ONLY for valid input, loaded via static methods.
1494             */
1495            private PrecalculatedZone(String id, long[] transitions, int[] wallOffsets,
1496                              int[] standardOffsets, String[] nameKeys, DSTZone tailZone)
1497            {
1498                super(id);
1499                iTransitions = transitions;
1500                iWallOffsets = wallOffsets;
1501                iStandardOffsets = standardOffsets;
1502                iNameKeys = nameKeys;
1503                iTailZone = tailZone;
1504            }
1505    
1506            public String getNameKey(long instant) {
1507                long[] transitions = iTransitions;
1508                int i = Arrays.binarySearch(transitions, instant);
1509                if (i >= 0) {
1510                    return iNameKeys[i];
1511                }
1512                i = ~i;
1513                if (i < transitions.length) {
1514                    if (i > 0) {
1515                        return iNameKeys[i - 1];
1516                    }
1517                    return "UTC";
1518                }
1519                if (iTailZone == null) {
1520                    return iNameKeys[i - 1];
1521                }
1522                return iTailZone.getNameKey(instant);
1523            }
1524    
1525            public int getOffset(long instant) {
1526                long[] transitions = iTransitions;
1527                int i = Arrays.binarySearch(transitions, instant);
1528                if (i >= 0) {
1529                    return iWallOffsets[i];
1530                }
1531                i = ~i;
1532                if (i < transitions.length) {
1533                    if (i > 0) {
1534                        return iWallOffsets[i - 1];
1535                    }
1536                    return 0;
1537                }
1538                if (iTailZone == null) {
1539                    return iWallOffsets[i - 1];
1540                }
1541                return iTailZone.getOffset(instant);
1542            }
1543    
1544            public int getStandardOffset(long instant) {
1545                long[] transitions = iTransitions;
1546                int i = Arrays.binarySearch(transitions, instant);
1547                if (i >= 0) {
1548                    return iStandardOffsets[i];
1549                }
1550                i = ~i;
1551                if (i < transitions.length) {
1552                    if (i > 0) {
1553                        return iStandardOffsets[i - 1];
1554                    }
1555                    return 0;
1556                }
1557                if (iTailZone == null) {
1558                    return iStandardOffsets[i - 1];
1559                }
1560                return iTailZone.getStandardOffset(instant);
1561            }
1562    
1563            public boolean isFixed() {
1564                return false;
1565            }
1566    
1567            public long nextTransition(long instant) {
1568                long[] transitions = iTransitions;
1569                int i = Arrays.binarySearch(transitions, instant);
1570                i = (i >= 0) ? (i + 1) : ~i;
1571                if (i < transitions.length) {
1572                    return transitions[i];
1573                }
1574                if (iTailZone == null) {
1575                    return instant;
1576                }
1577                long end = transitions[transitions.length - 1];
1578                if (instant < end) {
1579                    instant = end;
1580                }
1581                return iTailZone.nextTransition(instant);
1582            }
1583    
1584            public long previousTransition(long instant) {
1585                long[] transitions = iTransitions;
1586                int i = Arrays.binarySearch(transitions, instant);
1587                if (i >= 0) {
1588                    if (instant > Long.MIN_VALUE) {
1589                        return instant - 1;
1590                    }
1591                    return instant;
1592                }
1593                i = ~i;
1594                if (i < transitions.length) {
1595                    if (i > 0) {
1596                        long prev = transitions[i - 1];
1597                        if (prev > Long.MIN_VALUE) {
1598                            return prev - 1;
1599                        }
1600                    }
1601                    return instant;
1602                }
1603                if (iTailZone != null) {
1604                    long prev = iTailZone.previousTransition(instant);
1605                    if (prev < instant) {
1606                        return prev;
1607                    }
1608                }
1609                long prev = transitions[i - 1];
1610                if (prev > Long.MIN_VALUE) {
1611                    return prev - 1;
1612                }
1613                return instant;
1614            }
1615    
1616            public boolean equals(Object obj) {
1617                if (this == obj) {
1618                    return true;
1619                }
1620                if (obj instanceof PrecalculatedZone) {
1621                    PrecalculatedZone other = (PrecalculatedZone)obj;
1622                    return
1623                        getID().equals(other.getID()) &&
1624                        Arrays.equals(iTransitions, other.iTransitions) &&
1625                        Arrays.equals(iNameKeys, other.iNameKeys) &&
1626                        Arrays.equals(iWallOffsets, other.iWallOffsets) &&
1627                        Arrays.equals(iStandardOffsets, other.iStandardOffsets) &&
1628                        ((iTailZone == null)
1629                         ? (null == other.iTailZone)
1630                         : (iTailZone.equals(other.iTailZone)));
1631                }
1632                return false;
1633            }
1634    
1635            public void writeTo(DataOutput out) throws IOException {
1636                int size = iTransitions.length;
1637    
1638                // Create unique string pool.
1639                Set poolSet = new HashSet();
1640                for (int i=0; i<size; i++) {
1641                    poolSet.add(iNameKeys[i]);
1642                }
1643    
1644                int poolSize = poolSet.size();
1645                if (poolSize > 65535) {
1646                    throw new UnsupportedOperationException("String pool is too large");
1647                }
1648                String[] pool = new String[poolSize];
1649                Iterator it = poolSet.iterator();
1650                for (int i=0; it.hasNext(); i++) {
1651                    pool[i] = (String)it.next();
1652                }
1653    
1654                // Write out the pool.
1655                out.writeShort(poolSize);
1656                for (int i=0; i<poolSize; i++) {
1657                    out.writeUTF(pool[i]);
1658                }
1659    
1660                out.writeInt(size);
1661    
1662                for (int i=0; i<size; i++) {
1663                    writeMillis(out, iTransitions[i]);
1664                    writeMillis(out, iWallOffsets[i]);
1665                    writeMillis(out, iStandardOffsets[i]);
1666                    
1667                    // Find pool index and write it out.
1668                    String nameKey = iNameKeys[i];
1669                    for (int j=0; j<poolSize; j++) {
1670                        if (pool[j].equals(nameKey)) {
1671                            if (poolSize < 256) {
1672                                out.writeByte(j);
1673                            } else {
1674                                out.writeShort(j);
1675                            }
1676                            break;
1677                        }
1678                    }
1679                }
1680    
1681                out.writeBoolean(iTailZone != null);
1682                if (iTailZone != null) {
1683                    iTailZone.writeTo(out);
1684                }
1685            }
1686    
1687            public boolean isCachable() {
1688                if (iTailZone != null) {
1689                    return true;
1690                }
1691                long[] transitions = iTransitions;
1692                if (transitions.length <= 1) {
1693                    return false;
1694                }
1695    
1696                // Add up all the distances between transitions that are less than
1697                // about two years.
1698                double distances = 0;
1699                int count = 0;
1700    
1701                for (int i=1; i<transitions.length; i++) {
1702                    long diff = transitions[i] - transitions[i - 1];
1703                    if (diff < ((366L + 365) * 24 * 60 * 60 * 1000)) {
1704                        distances += (double)diff;
1705                        count++;
1706                    }
1707                }
1708    
1709                if (count > 0) {
1710                    double avg = distances / count;
1711                    avg /= 24 * 60 * 60 * 1000;
1712                    if (avg >= 25) {
1713                        // Only bother caching if average distance between
1714                        // transitions is at least 25 days. Why 25?
1715                        // CachedDateTimeZone is more efficient if the distance
1716                        // between transitions is large. With an average of 25, it
1717                        // will on average perform about 2 tests per cache
1718                        // hit. (49.7 / 25) is approximately 2.
1719                        return true;
1720                    }
1721                }
1722    
1723                return false;
1724            }
1725        }
1726    }