1 /*
2  *  Copyright 2001-2013 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         @SuppressWarnings("unused")
823         public int getFromYear() {
824             return iFromYear;
825         }
826
827         public int getToYear() {
828             return iToYear;
829         }
830
831         @SuppressWarnings("unused")
832         public OfYear getOfYear() {
833             return iRecurrence.getOfYear();
834         }
835
836         public String getNameKey() {
837             return iRecurrence.getNameKey();
838         }
839
840         public int getSaveMillis() {
841             return iRecurrence.getSaveMillis();
842         }
843
844         public long next(final long instant, int standardOffset, int saveMillis) {
845             Chronology chrono = ISOChronology.getInstanceUTC();
846
847             final int wallOffset = standardOffset + saveMillis;
848             long testInstant = instant;
849
850             int year;
851             if (instant == Long.MIN_VALUE) {
852                 year = Integer.MIN_VALUE;
853             } else {
854                 year = chrono.year().get(instant + wallOffset);
855             }
856
857             if (year < iFromYear) {
858                 // First advance instant to start of from year.
859                 testInstant = chrono.year().set(0, iFromYear) - wallOffset;
860                 // Back off one millisecond to account for next recurrence
861                 // being exactly at the beginning of the year.
862                 testInstant -= 1;
863             }
864
865             long next = iRecurrence.next(testInstant, standardOffset, saveMillis);
866
867             if (next > instant) {
868                 year = chrono.year().get(next + wallOffset);
869                 if (year > iToYear) {
870                     // Out of range, return original value.
871                     next = instant;
872                 }
873             }
874
875             return next;
876         }
877     }
878
879     private static final class Transition {
880         private final long iMillis;
881         private final String iNameKey;
882         private final int iWallOffset;
883         private final int iStandardOffset;
884
885         Transition(long millis, Transition tr) {
886             iMillis = millis;
887             iNameKey = tr.iNameKey;
888             iWallOffset = tr.iWallOffset;
889             iStandardOffset = tr.iStandardOffset;
890         }
891
892         Transition(long millis, Rule rule, int standardOffset) {
893             iMillis = millis;
894             iNameKey = rule.getNameKey();
895             iWallOffset = standardOffset + rule.getSaveMillis();
896             iStandardOffset = standardOffset;
897         }
898
899         Transition(long millis, String nameKey,
900                    int wallOffset, int standardOffset) {
901             iMillis = millis;
902             iNameKey = nameKey;
903             iWallOffset = wallOffset;
904             iStandardOffset = standardOffset;
905         }
906
907         public long getMillis() {
908             return iMillis;
909         }
910
911         public String getNameKey() {
912             return iNameKey;
913         }
914
915         public int getWallOffset() {
916             return iWallOffset;
917         }
918
919         public int getStandardOffset() {
920             return iStandardOffset;
921         }
922
923         public int getSaveMillis() {
924             return iWallOffset - iStandardOffset;
925         }
926
927         /**
928          * There must be a change in the millis, wall offsets or name keys.
929          */
930         public boolean isTransitionFrom(Transition other) {
931             if (other == null) {
932                 return true;
933             }
934             return iMillis > other.iMillis &&
935                 (iWallOffset != other.iWallOffset ||
936                  //iStandardOffset != other.iStandardOffset ||
937                  !(iNameKey.equals(other.iNameKey)));
938         }
939     }
940
941     private static final class RuleSet {
942         private static final int YEAR_LIMIT;
943
944         static {
945             // Don't pre-calculate more than 100 years into the future. Almost
946             // all zones will stop pre-calculating far sooner anyhow. Either a
947             // simple DST cycle is detected or the last rule is a fixed
948             // offset. If a zone has a fixed offset set more than 100 years
949             // into the future, then it won't be observed.
950             long now = DateTimeUtils.currentTimeMillis();
951             YEAR_LIMIT = ISOChronology.getInstanceUTC().year().get(now) + 100;
952         }
953
954         private int iStandardOffset;
955         private ArrayList<Rule> iRules;
956
957         // Optional.
958         private String iInitialNameKey;
959         private int iInitialSaveMillis;
960
961         // Upper limit is exclusive.
962         private int iUpperYear;
963         private OfYear iUpperOfYear;
964
965         RuleSet() {
966             iRules = new ArrayList<Rule>(10);
967             iUpperYear = Integer.MAX_VALUE;
968         }
969
970         /**
971          * Copy constructor.
972          */
973         RuleSet(RuleSet rs) {
974             iStandardOffset = rs.iStandardOffset;
975             iRules = new ArrayList<Rule>(rs.iRules);
976             iInitialNameKey = rs.iInitialNameKey;
977             iInitialSaveMillis = rs.iInitialSaveMillis;
978             iUpperYear = rs.iUpperYear;
979             iUpperOfYear = rs.iUpperOfYear;
980         }
981
982         @SuppressWarnings("unused")
983         public int getStandardOffset() {
984             return iStandardOffset;
985         }
986
987         public void setStandardOffset(int standardOffset) {
988             iStandardOffset = standardOffset;
989         }
990
991         public void setFixedSavings(String nameKey, int saveMillis) {
992             iInitialNameKey = nameKey;
993             iInitialSaveMillis = saveMillis;
994         }
995
996         public void addRule(Rule rule) {
997             if (!iRules.contains(rule)) {
998                 iRules.add(rule);
999             }
1000         }
1001
1002         public void setUpperLimit(int year, OfYear ofYear) {
1003             iUpperYear = year;
1004             iUpperOfYear = ofYear;
1005         }
1006
1007         /**
1008          * Returns a transition at firstMillis with the first name key and
1009          * offsets for this rule set. This method may return null.
1010          *
1011          * @param firstMillis millis of first transition
1012          */
1013         public Transition firstTransition(final long firstMillis) {
1014             if (iInitialNameKey != null) {
1015                 // Initial zone info explicitly set, so don't search the rules.
1016                 return new Transition(firstMillis, iInitialNameKey,
1017                                       iStandardOffset + iInitialSaveMillis, iStandardOffset);
1018             }
1019
1020             // Make a copy before we destroy the rules.
1021             ArrayList<Rule> copy = new ArrayList<Rule>(iRules);
1022
1023             // Iterate through all the transitions until firstMillis is
1024             // reached. Use the name key and savings for whatever rule reaches
1025             // the limit.
1026
1027             long millis = Long.MIN_VALUE;
1028             int saveMillis = 0;
1029             Transition first = null;
1030
1031             Transition next;
1032             while ((next = nextTransition(millis, saveMillis)) != null) {
1033                 millis = next.getMillis();
1034
1035                 if (millis == firstMillis) {
1036                     first = new Transition(firstMillis, next);
1037                     break;
1038                 }
1039
1040                 if (millis > firstMillis) {
1041                     if (first == null) {
1042                         // Find first rule without savings. This way a more
1043                         // accurate nameKey is found even though no rule
1044                         // extends to the RuleSet's lower limit.
1045                         for (Rule rule : copy) {
1046                             if (rule.getSaveMillis() == 0) {
1047                                 first = new Transition(firstMillis, rule, iStandardOffset);
1048                                 break;
1049                             }
1050                         }
1051                     }
1052                     if (first == null) {
1053                         // Found no rule without savings. Create a transition
1054                         // with no savings anyhow, and use the best available
1055                         // name key.
1056                         first = new Transition(firstMillis, next.getNameKey(),
1057                                                iStandardOffset, iStandardOffset);
1058                     }
1059                     break;
1060                 }
1061                 
1062                 // Set first to the best transition found so far, but next
1063                 // iteration may find something closer to lower limit.
1064                 first = new Transition(firstMillis, next);
1065
1066                 saveMillis = next.getSaveMillis();
1067             }
1068
1069             iRules = copy;
1070             return first;
1071         }
1072
1073         /**
1074          * Returns null if RuleSet is exhausted or upper limit reached. Calling
1075          * this method will throw away rules as they each become
1076          * exhausted. Copy the RuleSet before using it to compute transitions.
1077          *
1078          * Returned transition may be a duplicate from previous
1079          * transition. Caller must call isTransitionFrom to filter out
1080          * duplicates.
1081          *
1082          * @param saveMillis savings before next transition
1083          */
1084         public Transition nextTransition(final long instant, final int saveMillis) {
1085             Chronology chrono = ISOChronology.getInstanceUTC();
1086
1087             // Find next matching rule.
1088             Rule nextRule = null;
1089             long nextMillis = Long.MAX_VALUE;
1090             
1091             Iterator<Rule> it = iRules.iterator();
1092             while (it.hasNext()) {
1093                 Rule rule = it.next();
1094                 long next = rule.next(instant, iStandardOffset, saveMillis);
1095                 if (next <= instant) {
1096                     it.remove();
1097                     continue;
1098                 }
1099                 // Even if next is same as previous next, choose the rule
1100                 // in order for more recently added rules to override.
1101                 if (next <= nextMillis) {
1102                     // Found a better match.
1103                     nextRule = rule;
1104                     nextMillis = next;
1105                 }
1106             }
1107             
1108             if (nextRule == null) {
1109                 return null;
1110             }
1111             
1112             // Stop precalculating if year reaches some arbitrary limit.
1113             if (chrono.year().get(nextMillis) >= YEAR_LIMIT) {
1114                 return null;
1115             }
1116             
1117             // Check if upper limit reached or passed.
1118             if (iUpperYear < Integer.MAX_VALUE) {
1119                 long upperMillis =
1120                     iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
1121                 if (nextMillis >= upperMillis) {
1122                     // At or after upper limit.
1123                     return null;
1124                 }
1125             }
1126             
1127             return new Transition(nextMillis, nextRule, iStandardOffset);
1128         }
1129
1130         /**
1131          * @param saveMillis savings before upper limit
1132          */
1133         public long getUpperLimit(int saveMillis) {
1134             if (iUpperYear == Integer.MAX_VALUE) {
1135                 return Long.MAX_VALUE;
1136             }
1137             return iUpperOfYear.setInstant(iUpperYear, iStandardOffset, saveMillis);
1138         }
1139
1140         /**
1141          * Returns null if none can be built.
1142          */
1143         public DSTZone buildTailZone(String id) {
1144             if (iRules.size() == 2) {
1145                 Rule startRule = iRules.get(0);
1146                 Rule endRule = iRules.get(1);
1147                 if (startRule.getToYear() == Integer.MAX_VALUE &&
1148                     endRule.getToYear() == Integer.MAX_VALUE) {
1149
1150                     // With exactly two infinitely recurring rules left, a
1151                     // simple DSTZone can be formed.
1152
1153                     // The order of rules can come in any order, and it doesn't
1154                     // really matter which rule was chosen the 'start' and
1155                     // which is chosen the 'end'. DSTZone works properly either
1156                     // way.
1157                     return new DSTZone(id, iStandardOffset,
1158                                        startRule.iRecurrence, endRule.iRecurrence);
1159                 }
1160             }
1161             return null;
1162         }
1163     }
1164
1165     private static final class DSTZone extends DateTimeZone {
1166         private static final long serialVersionUID = 6941492635554961361L;
1167
1168         static DSTZone readFrom(DataInput in, String id) throws IOException {
1169             return new DSTZone(id, (int)readMillis(in), 
1170                                Recurrence.readFrom(in), Recurrence.readFrom(in));
1171         }
1172
1173         final int iStandardOffset;
1174         final Recurrence iStartRecurrence;
1175         final Recurrence iEndRecurrence;
1176
1177         DSTZone(String id, int standardOffset,
1178                 Recurrence startRecurrence, Recurrence endRecurrence) {
1179             super(id);
1180             iStandardOffset = standardOffset;
1181             iStartRecurrence = startRecurrence;
1182             iEndRecurrence = endRecurrence;
1183         }
1184
1185         public String getNameKey(long instant) {
1186             return findMatchingRecurrence(instant).getNameKey();
1187         }
1188
1189         public int getOffset(long instant) {
1190             return iStandardOffset + findMatchingRecurrence(instant).getSaveMillis();
1191         }
1192
1193         public int getStandardOffset(long instant) {
1194             return iStandardOffset;
1195         }
1196
1197         public boolean isFixed() {
1198             return false;
1199         }
1200
1201         public long nextTransition(long instant) {
1202             int standardOffset = iStandardOffset;
1203             Recurrence startRecurrence = iStartRecurrence;
1204             Recurrence endRecurrence = iEndRecurrence;
1205
1206             long start, end;
1207
1208             try {
1209                 start = startRecurrence.next
1210                     (instant, standardOffset, endRecurrence.getSaveMillis());
1211                 if (instant > 0 && start < 0) {
1212                     // Overflowed.
1213                     start = instant;
1214                 }
1215             } catch (IllegalArgumentException e) {
1216                 // Overflowed.
1217                 start = instant;
1218             } catch (ArithmeticException e) {
1219                 // Overflowed.
1220                 start = instant;
1221             }
1222
1223             try {
1224                 end = endRecurrence.next
1225                     (instant, standardOffset, startRecurrence.getSaveMillis());
1226                 if (instant > 0 && end < 0) {
1227                     // Overflowed.
1228                     end = instant;
1229                 }
1230             } catch (IllegalArgumentException e) {
1231                 // Overflowed.
1232                 end = instant;
1233             } catch (ArithmeticException e) {
1234                 // Overflowed.
1235                 end = instant;
1236             }
1237
1238             return (start > end) ? end : start;
1239         }
1240
1241         public long previousTransition(long instant) {
1242             // Increment in order to handle the case where instant is exactly at
1243             // a transition.
1244             instant++;
1245
1246             int standardOffset = iStandardOffset;
1247             Recurrence startRecurrence = iStartRecurrence;
1248             Recurrence endRecurrence = iEndRecurrence;
1249
1250             long start, end;
1251
1252             try {
1253                 start = startRecurrence.previous
1254                     (instant, standardOffset, endRecurrence.getSaveMillis());
1255                 if (instant < 0 && start > 0) {
1256                     // Overflowed.
1257                     start = instant;
1258                 }
1259             } catch (IllegalArgumentException e) {
1260                 // Overflowed.
1261                 start = instant;
1262             } catch (ArithmeticException e) {
1263                 // Overflowed.
1264                 start = instant;
1265             }
1266
1267             try {
1268                 end = endRecurrence.previous
1269                     (instant, standardOffset, startRecurrence.getSaveMillis());
1270                 if (instant < 0 && end > 0) {
1271                     // Overflowed.
1272                     end = instant;
1273                 }
1274             } catch (IllegalArgumentException e) {
1275                 // Overflowed.
1276                 end = instant;
1277             } catch (ArithmeticException e) {
1278                 // Overflowed.
1279                 end = instant;
1280             }
1281
1282             return ((start > end) ? start : end) - 1;
1283         }
1284
1285         public boolean equals(Object obj) {
1286             if (this == obj) {
1287                 return true;
1288             }
1289             if (obj instanceof DSTZone) {
1290                 DSTZone other = (DSTZone)obj;
1291                 return
1292                     getID().equals(other.getID()) &&
1293                     iStandardOffset == other.iStandardOffset &&
1294                     iStartRecurrence.equals(other.iStartRecurrence) &&
1295                     iEndRecurrence.equals(other.iEndRecurrence);
1296             }
1297             return false;
1298         }
1299
1300         public void writeTo(DataOutput out) throws IOException {
1301             writeMillis(out, iStandardOffset);
1302             iStartRecurrence.writeTo(out);
1303             iEndRecurrence.writeTo(out);
1304         }
1305
1306         private Recurrence findMatchingRecurrence(long instant) {
1307             int standardOffset = iStandardOffset;
1308             Recurrence startRecurrence = iStartRecurrence;
1309             Recurrence endRecurrence = iEndRecurrence;
1310
1311             long start, end;
1312
1313             try {
1314                 start = startRecurrence.next
1315                     (instant, standardOffset, endRecurrence.getSaveMillis());
1316             } catch (IllegalArgumentException e) {
1317                 // Overflowed.
1318                 start = instant;
1319             } catch (ArithmeticException e) {
1320                 // Overflowed.
1321                 start = instant;
1322             }
1323
1324             try {
1325                 end = endRecurrence.next
1326                     (instant, standardOffset, startRecurrence.getSaveMillis());
1327             } catch (IllegalArgumentException e) {
1328                 // Overflowed.
1329                 end = instant;
1330             } catch (ArithmeticException e) {
1331                 // Overflowed.
1332                 end = instant;
1333             }
1334
1335             return (start > end) ? startRecurrence : endRecurrence;
1336         }
1337     }
1338
1339     private static final class PrecalculatedZone extends DateTimeZone {
1340         private static final long serialVersionUID = 7811976468055766265L;
1341
1342         static PrecalculatedZone readFrom(DataInput in, String id) throws IOException {
1343             // Read string pool.
1344             int poolSize = in.readUnsignedShort();
1345             String[] pool = new String[poolSize];
1346             for (int i=0; i<poolSize; i++) {
1347                 pool[i] = in.readUTF();
1348             }
1349
1350             int size = in.readInt();
1351             long[] transitions = new long[size];
1352             int[] wallOffsets = new int[size];
1353             int[] standardOffsets = new int[size];
1354             String[] nameKeys = new String[size];
1355             
1356             for (int i=0; i<size; i++) {
1357                 transitions[i] = readMillis(in);
1358                 wallOffsets[i] = (int)readMillis(in);
1359                 standardOffsets[i] = (int)readMillis(in);
1360                 try {
1361                     int index;
1362                     if (poolSize < 256) {
1363                         index = in.readUnsignedByte();
1364                     } else {
1365                         index = in.readUnsignedShort();
1366                     }
1367                     nameKeys[i] = pool[index];
1368                 } catch (ArrayIndexOutOfBoundsException e) {
1369                     throw new IOException("Invalid encoding");
1370                 }
1371             }
1372
1373             DSTZone tailZone = null;
1374             if (in.readBoolean()) {
1375                 tailZone = DSTZone.readFrom(in, id);
1376             }
1377
1378             return new PrecalculatedZone
1379                 (id, transitions, wallOffsets, standardOffsets, nameKeys, tailZone);
1380         }
1381
1382         /**
1383          * Factory to create instance from builder.
1384          * 
1385          * @param id  the zone id
1386          * @param outputID  true if the zone id should be output
1387          * @param transitions  the list of Transition objects
1388          * @param tailZone  optional zone for getting info beyond precalculated tables
1389          */
1390         static PrecalculatedZone create(String id, boolean outputID, ArrayList<Transition> transitions,
1391                                         DSTZone tailZone) {
1392             int size = transitions.size();
1393             if (size == 0) {
1394                 throw new IllegalArgumentException();
1395             }
1396
1397             long[] trans = new long[size];
1398             int[] wallOffsets = new int[size];
1399             int[] standardOffsets = new int[size];
1400             String[] nameKeys = new String[size];
1401
1402             Transition last = null;
1403             for (int i=0; i<size; i++) {
1404                 Transition tr = transitions.get(i);
1405
1406                 if (!tr.isTransitionFrom(last)) {
1407                     throw new IllegalArgumentException(id);
1408                 }
1409
1410                 trans[i] = tr.getMillis();
1411                 wallOffsets[i] = tr.getWallOffset();
1412                 standardOffsets[i] = tr.getStandardOffset();
1413                 nameKeys[i] = tr.getNameKey();
1414
1415                 last = tr;
1416             }
1417
1418             // Some timezones (Australia) have the same name key for
1419             // summer and winter which messes everything up. Fix it here.
1420             String[] zoneNameData = new String[5];
1421             String[][] zoneStrings = new DateFormatSymbols(Locale.ENGLISH).getZoneStrings();
1422             for (int j = 0; j < zoneStrings.length; j++) {
1423                 String[] set = zoneStrings[j];
1424                 if (set != null && set.length == 5 && id.equals(set[0])) {
1425                     zoneNameData = set;
1426                 }
1427             }
1428
1429             Chronology chrono = ISOChronology.getInstanceUTC();
1430
1431             for (int i = 0; i < nameKeys.length - 1; i++) {
1432                 String curNameKey = nameKeys[i];
1433                 String nextNameKey = nameKeys[i + 1];
1434                 long curOffset = wallOffsets[i];
1435                 long nextOffset = wallOffsets[i + 1];
1436                 long curStdOffset = standardOffsets[i];
1437                 long nextStdOffset = standardOffsets[i + 1];
1438                 Period p = new Period(trans[i], trans[i + 1], PeriodType.yearMonthDay(), chrono);
1439                 if (curOffset != nextOffset &&
1440                         curStdOffset == nextStdOffset &&
1441                         curNameKey.equals(nextNameKey) &&
1442                         p.getYears() == 0 && p.getMonths() > 4 && p.getMonths() < 8 &&
1443                         curNameKey.equals(zoneNameData[2]) &&
1444                         curNameKey.equals(zoneNameData[4])) {
1445                     
1446                     if (ZoneInfoLogger.verbose()) {
1447                         System.out.println("Fixing duplicate name key - " + nextNameKey);
1448                         System.out.println("     - " + new DateTime(trans[i], chrono) +
1449                                            " - " + new DateTime(trans[i + 1], chrono));
1450                     }
1451                     if (curOffset > nextOffset) {
1452                         nameKeys[i] = (curNameKey + "-Summer").intern();
1453                     } else if (curOffset < nextOffset) {
1454                         nameKeys[i + 1] = (nextNameKey + "-Summer").intern();
1455                         i++;
1456                     }
1457                 }
1458             }
1459
1460             if (tailZone != null) {
1461                 if (tailZone.iStartRecurrence.getNameKey()
1462                     .equals(tailZone.iEndRecurrence.getNameKey())) {
1463                     if (ZoneInfoLogger.verbose()) {
1464                         System.out.println("Fixing duplicate recurrent name key - " +
1465                                            tailZone.iStartRecurrence.getNameKey());
1466                     }
1467                     if (tailZone.iStartRecurrence.getSaveMillis() > 0) {
1468                         tailZone = new DSTZone(
1469                             tailZone.getID(),
1470                             tailZone.iStandardOffset,
1471                             tailZone.iStartRecurrence.renameAppend("-Summer"),
1472                             tailZone.iEndRecurrence);
1473                     } else {
1474                         tailZone = new DSTZone(
1475                             tailZone.getID(),
1476                             tailZone.iStandardOffset,
1477                             tailZone.iStartRecurrence,
1478                             tailZone.iEndRecurrence.renameAppend("-Summer"));
1479                     }
1480                 }
1481             }
1482             
1483             return new PrecalculatedZone
1484                 ((outputID ? id : ""), trans, wallOffsets, standardOffsets, nameKeys, tailZone);
1485         }
1486
1487         // All array fields have the same length.
1488
1489         private final long[] iTransitions;
1490
1491         private final int[] iWallOffsets;
1492         private final int[] iStandardOffsets;
1493         private final String[] iNameKeys;
1494
1495         private final DSTZone iTailZone;
1496
1497         /**
1498          * Constructor used ONLY for valid input, loaded via static methods.
1499          */
1500         private PrecalculatedZone(String id, long[] transitions, int[] wallOffsets,
1501                           int[] standardOffsets, String[] nameKeys, DSTZone tailZone)
1502         {
1503             super(id);
1504             iTransitions = transitions;
1505             iWallOffsets = wallOffsets;
1506             iStandardOffsets = standardOffsets;
1507             iNameKeys = nameKeys;
1508             iTailZone = tailZone;
1509         }
1510
1511         public String getNameKey(long instant) {
1512             long[] transitions = iTransitions;
1513             int i = Arrays.binarySearch(transitions, instant);
1514             if (i >= 0) {
1515                 return iNameKeys[i];
1516             }
1517             i = ~i;
1518             if (i < transitions.length) {
1519                 if (i > 0) {
1520                     return iNameKeys[i - 1];
1521                 }
1522                 return "UTC";
1523             }
1524             if (iTailZone == null) {
1525                 return iNameKeys[i - 1];
1526             }
1527             return iTailZone.getNameKey(instant);
1528         }
1529
1530         public int getOffset(long instant) {
1531             long[] transitions = iTransitions;
1532             int i = Arrays.binarySearch(transitions, instant);
1533             if (i >= 0) {
1534                 return iWallOffsets[i];
1535             }
1536             i = ~i;
1537             if (i < transitions.length) {
1538                 if (i > 0) {
1539                     return iWallOffsets[i - 1];
1540                 }
1541                 return 0;
1542             }
1543             if (iTailZone == null) {
1544                 return iWallOffsets[i - 1];
1545             }
1546             return iTailZone.getOffset(instant);
1547         }
1548
1549         public int getStandardOffset(long instant) {
1550             long[] transitions = iTransitions;
1551             int i = Arrays.binarySearch(transitions, instant);
1552             if (i >= 0) {
1553                 return iStandardOffsets[i];
1554             }
1555             i = ~i;
1556             if (i < transitions.length) {
1557                 if (i > 0) {
1558                     return iStandardOffsets[i - 1];
1559                 }
1560                 return 0;
1561             }
1562             if (iTailZone == null) {
1563                 return iStandardOffsets[i - 1];
1564             }
1565             return iTailZone.getStandardOffset(instant);
1566         }
1567
1568         public boolean isFixed() {
1569             return false;
1570         }
1571
1572         public long nextTransition(long instant) {
1573             long[] transitions = iTransitions;
1574             int i = Arrays.binarySearch(transitions, instant);
1575             i = (i >= 0) ? (i + 1) : ~i;
1576             if (i < transitions.length) {
1577                 return transitions[i];
1578             }
1579             if (iTailZone == null) {
1580                 return instant;
1581             }
1582             long end = transitions[transitions.length - 1];
1583             if (instant < end) {
1584                 instant = end;
1585             }
1586             return iTailZone.nextTransition(instant);
1587         }
1588
1589         public long previousTransition(long instant) {
1590             long[] transitions = iTransitions;
1591             int i = Arrays.binarySearch(transitions, instant);
1592             if (i >= 0) {
1593                 if (instant > Long.MIN_VALUE) {
1594                     return instant - 1;
1595                 }
1596                 return instant;
1597             }
1598             i = ~i;
1599             if (i < transitions.length) {
1600                 if (i > 0) {
1601                     long prev = transitions[i - 1];
1602                     if (prev > Long.MIN_VALUE) {
1603                         return prev - 1;
1604                     }
1605                 }
1606                 return instant;
1607             }
1608             if (iTailZone != null) {
1609                 long prev = iTailZone.previousTransition(instant);
1610                 if (prev < instant) {
1611                     return prev;
1612                 }
1613             }
1614             long prev = transitions[i - 1];
1615             if (prev > Long.MIN_VALUE) {
1616                 return prev - 1;
1617             }
1618             return instant;
1619         }
1620
1621         public boolean equals(Object obj) {
1622             if (this == obj) {
1623                 return true;
1624             }
1625             if (obj instanceof PrecalculatedZone) {
1626                 PrecalculatedZone other = (PrecalculatedZone)obj;
1627                 return
1628                     getID().equals(other.getID()) &&
1629                     Arrays.equals(iTransitions, other.iTransitions) &&
1630                     Arrays.equals(iNameKeys, other.iNameKeys) &&
1631                     Arrays.equals(iWallOffsets, other.iWallOffsets) &&
1632                     Arrays.equals(iStandardOffsets, other.iStandardOffsets) &&
1633                     ((iTailZone == null)
1634                      ? (null == other.iTailZone)
1635                      : (iTailZone.equals(other.iTailZone)));
1636             }
1637             return false;
1638         }
1639
1640         public void writeTo(DataOutput out) throws IOException {
1641             int size = iTransitions.length;
1642
1643             // Create unique string pool.
1644             Set<String> poolSet = new HashSet<String>();
1645             for (int i=0; i<size; i++) {
1646                 poolSet.add(iNameKeys[i]);
1647             }
1648
1649             int poolSize = poolSet.size();
1650             if (poolSize > 65535) {
1651                 throw new UnsupportedOperationException("String pool is too large");
1652             }
1653             String[] pool = new String[poolSize];
1654             Iterator<String> it = poolSet.iterator();
1655             for (int i=0; it.hasNext(); i++) {
1656                 pool[i] = it.next();
1657             }
1658
1659             // Write out the pool.
1660             out.writeShort(poolSize);
1661             for (int i=0; i<poolSize; i++) {
1662                 out.writeUTF(pool[i]);
1663             }
1664
1665             out.writeInt(size);
1666
1667             for (int i=0; i<size; i++) {
1668                 writeMillis(out, iTransitions[i]);
1669                 writeMillis(out, iWallOffsets[i]);
1670                 writeMillis(out, iStandardOffsets[i]);
1671                 
1672                 // Find pool index and write it out.
1673                 String nameKey = iNameKeys[i];
1674                 for (int j=0; j<poolSize; j++) {
1675                     if (pool[j].equals(nameKey)) {
1676                         if (poolSize < 256) {
1677                             out.writeByte(j);
1678                         } else {
1679                             out.writeShort(j);
1680                         }
1681                         break;
1682                     }
1683                 }
1684             }
1685
1686             out.writeBoolean(iTailZone != null);
1687             if (iTailZone != null) {
1688                 iTailZone.writeTo(out);
1689             }
1690         }
1691
1692         public boolean isCachable() {
1693             if (iTailZone != null) {
1694                 return true;
1695             }
1696             long[] transitions = iTransitions;
1697             if (transitions.length <= 1) {
1698                 return false;
1699             }
1700
1701             // Add up all the distances between transitions that are less than
1702             // about two years.
1703             double distances = 0;
1704             int count = 0;
1705
1706             for (int i=1; i<transitions.length; i++) {
1707                 long diff = transitions[i] - transitions[i - 1];
1708                 if (diff < ((366L + 365) * 24 * 60 * 60 * 1000)) {
1709                     distances += (double)diff;
1710                     count++;
1711                 }
1712             }
1713
1714             if (count > 0) {
1715                 double avg = distances / count;
1716                 avg /= 24 * 60 * 60 * 1000;
1717                 if (avg >= 25) {
1718                     // Only bother caching if average distance between
1719                     // transitions is at least 25 days. Why 25?
1720                     // CachedDateTimeZone is more efficient if the distance
1721                     // between transitions is large. With an average of 25, it
1722                     // will on average perform about 2 tests per cache
1723                     // hit. (49.7 / 25) is approximately 2.
1724                     return true;
1725                 }
1726             }
1727
1728             return false;
1729         }
1730     }
1731 }
1732