View Javadoc

1   /*
2    *  Copyright 2001-2010 Stephen Colebourne
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package org.joda.time.tz;
17  
18  import java.io.DataInput;
19  import java.io.DataInputStream;
20  import java.io.DataOutput;
21  import java.io.DataOutputStream;
22  import java.io.IOException;
23  import java.io.InputStream;
24  import java.io.OutputStream;
25  import java.text.DateFormatSymbols;
26  import java.util.ArrayList;
27  import java.util.Arrays;
28  import java.util.HashSet;
29  import java.util.Iterator;
30  import java.util.Locale;
31  import java.util.Set;
32  
33  import org.joda.time.Chronology;
34  import org.joda.time.DateTime;
35  import org.joda.time.DateTimeUtils;
36  import org.joda.time.DateTimeZone;
37  import org.joda.time.Period;
38  import org.joda.time.PeriodType;
39  import org.joda.time.chrono.ISOChronology;
40  
41  /**
42   * DateTimeZoneBuilder allows complex DateTimeZones to be constructed. Since
43   * creating a new DateTimeZone this way is a relatively expensive operation,
44   * built zones can be written to a file. Reading back the encoded data is a
45   * quick operation.
46   * <p>
47   * DateTimeZoneBuilder itself is mutable and not thread-safe, but the
48   * DateTimeZone objects that it builds are thread-safe and immutable.
49   * <p>
50   * It is intended that {@link ZoneInfoCompiler} be used to read time zone data
51   * files, indirectly calling DateTimeZoneBuilder. The following complex
52   * example defines the America/Los_Angeles time zone, with all historical
53   * transitions:
54   * 
55   * <pre>
56   * DateTimeZone America_Los_Angeles = new DateTimeZoneBuilder()
57   *     .addCutover(-2147483648, 'w', 1, 1, 0, false, 0)
58   *     .setStandardOffset(-28378000)
59   *     .setFixedSavings("LMT", 0)
60   *     .addCutover(1883, 'w', 11, 18, 0, false, 43200000)
61   *     .setStandardOffset(-28800000)
62   *     .addRecurringSavings("PDT", 3600000, 1918, 1919, 'w',  3, -1, 7, false, 7200000)
63   *     .addRecurringSavings("PST",       0, 1918, 1919, 'w', 10, -1, 7, false, 7200000)
64   *     .addRecurringSavings("PWT", 3600000, 1942, 1942, 'w',  2,  9, 0, false, 7200000)
65   *     .addRecurringSavings("PPT", 3600000, 1945, 1945, 'u',  8, 14, 0, false, 82800000)
66   *     .addRecurringSavings("PST",       0, 1945, 1945, 'w',  9, 30, 0, false, 7200000)
67   *     .addRecurringSavings("PDT", 3600000, 1948, 1948, 'w',  3, 14, 0, false, 7200000)
68   *     .addRecurringSavings("PST",       0, 1949, 1949, 'w',  1,  1, 0, false, 7200000)
69   *     .addRecurringSavings("PDT", 3600000, 1950, 1966, 'w',  4, -1, 7, false, 7200000)
70   *     .addRecurringSavings("PST",       0, 1950, 1961, 'w',  9, -1, 7, false, 7200000)
71   *     .addRecurringSavings("PST",       0, 1962, 1966, 'w', 10, -1, 7, false, 7200000)
72   *     .addRecurringSavings("PST",       0, 1967, 2147483647, 'w', 10, -1, 7, false, 7200000)
73   *     .addRecurringSavings("PDT", 3600000, 1967, 1973, 'w', 4, -1,  7, false, 7200000)
74   *     .addRecurringSavings("PDT", 3600000, 1974, 1974, 'w', 1,  6,  0, false, 7200000)
75   *     .addRecurringSavings("PDT", 3600000, 1975, 1975, 'w', 2, 23,  0, false, 7200000)
76   *     .addRecurringSavings("PDT", 3600000, 1976, 1986, 'w', 4, -1,  7, false, 7200000)
77   *     .addRecurringSavings("PDT", 3600000, 1987, 2147483647, 'w', 4, 1, 7, true, 7200000)
78   *     .toDateTimeZone("America/Los_Angeles", true);
79   * </pre>
80   *
81   * @author Brian S O'Neill
82   * @see ZoneInfoCompiler
83   * @see ZoneInfoProvider
84   * @since 1.0
85   */
86  public class DateTimeZoneBuilder {
87      /**
88       * Decodes a built DateTimeZone from the given stream, as encoded by
89       * writeTo.
90       *
91       * @param in input stream to read encoded DateTimeZone from.
92       * @param id time zone id to assign
93       */
94      public static DateTimeZone readFrom(InputStream in, String id) throws IOException {
95          if (in instanceof DataInput) {
96              return readFrom((DataInput)in, id);
97          } else {
98              return readFrom((DataInput)new DataInputStream(in), id);
99          }
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 }