1 /*
2  **********************************************************************
3  * Copyright (c) 2002-2012, International Business Machines
4  * Corporation and others.  All Rights Reserved.
5  **********************************************************************
6  * Author: Mark Davis
7  **********************************************************************
8  */
9 package org.unicode.cldr.util;
10 
11 import java.util.ArrayList;
12 import java.util.Calendar;
13 import java.util.Date;
14 import java.util.List;
15 
16 import com.ibm.icu.text.NumberFormat;
17 import com.ibm.icu.util.TimeZone;
18 import com.ibm.icu.util.ULocale;
19 
20 /*
21  * ZoneInflections is an ordered list of inflection points between two dates,
22  * typically 1970 and current year + 5. An inflection point is where the offset
23  * from GMT changes; its offset is valid up until the next inflection point.
24  * <p> Internally the inflection points are stored from highest
25  * (at offset 0) to lowest. The ZoneInflections has no knowledge of the
26  * internals of TimeZones -- public API is queried to get the information.
27  */
28 public class ZoneInflections implements Comparable<ZoneInflections> {
29     static private final long SECOND = 1000;
30 
31     static private final long MINUTE = 60 * SECOND;
32 
33     static private final long HOUR = 60 * MINUTE;
34 
35     static private final double DHOUR = HOUR;
36 
37     static private final long DAY = 24 * HOUR;
38 
39     static private final long GROSS_PERIOD = 15 * DAY; // assumption is that no
40     // zones shift is less
41     // than this period
42 
43     static private final long EPSILON = 15 * MINUTE; // smallest interval we test
44     // to
45     static private final int currentYear = Calendar.getInstance().get(Calendar.YEAR);
46 
47     static private final long endDate = getDateLong(currentYear + 5, 1, 1);
48 
49     static private final long startDate = getDateLong(1970, 1, 1);
50 
51     // computed below
52     private int minOffset;
53 
54     private int maxOffset;
55 
56     // ordered most recently first
57     List<InflectionPoint> inflectionPoints = new ArrayList<>();
58 
59     public int getMaxOffset() {
60         return maxOffset;
61     }
62 
63     public int getMinOffset() {
64         return minOffset;
65     }
66 
67     public int getMaxOffset(long afterDateTime) {
68         long minSoFar = Integer.MAX_VALUE;
69         for (int i = 0; i < inflectionPoints.size(); ++i) {
70             InflectionPoint ip = inflectionPoints.get(i);
71             if (ip.utcDateTime < afterDateTime)
72                 break;
73             if (ip.offset < minSoFar)
74                 minSoFar = ip.offset;
75         }
76         return (int) minSoFar;
77     }
78 
79     public int getMinOffset(long afterDateTime) {
80         long maxSoFar = Integer.MIN_VALUE;
81         for (int i = 0; i < inflectionPoints.size(); ++i) {
82             InflectionPoint ip = inflectionPoints.get(i);
83             if (ip.utcDateTime < afterDateTime)
84                 break;
85             if (ip.offset > maxSoFar)
86                 maxSoFar = ip.offset;
87         }
88         return (int) maxSoFar;
89     }
90 
91     @Override
92     public String toString() {
93         return inflectionPoints.toString();
94     }
95 
96     public ZoneInflections(TimeZone zone) {
97         // System.out.println("Creating Inflection Points for: " + zone.getID());
98         // find inflexion points; times where the offset changed
99         // if (zone.getOffset(lastDate) != zone.getOffset(endDate2)) lastDate =
100         // endDate2;
101 
102         // System.out.println("\tAdding: " + dtf.format(new Date(lastDate)));
103         int lastOffset = zone.getOffset(endDate);
104         inflectionPoints.add(new InflectionPoint(endDate, zone.getOffset(endDate)));
105 
106         // we do a gross search, then narrow in when we find a difference from the
107         // last one
108         long lastDate = endDate;
109         minOffset = maxOffset = zone.getOffset(lastDate);
110         for (long currentDate = endDate; currentDate >= startDate; currentDate -= GROSS_PERIOD) {
111             int currentOffset = zone.getOffset(currentDate);
112             if (currentOffset != lastOffset) { // Binary Search
113                 if (currentOffset < minOffset)
114                     minOffset = currentOffset;
115                 if (currentOffset > maxOffset)
116                     maxOffset = currentOffset;
117                 long low = currentDate;
118                 int lowOffset = currentOffset;
119                 long high = lastDate;
120                 int highOffset = lastOffset;
121                 while (high - low > EPSILON) {
122                     long mid = (high + low) / 2;
123                     mid = (mid / EPSILON) * EPSILON; // round to nearest possible point
124                     if (mid <= low)
125                         mid += EPSILON;
126                     int midOffset = zone.getOffset(mid);
127                     if (midOffset == lowOffset) {
128                         low = mid;
129                     } else {
130                         high = mid;
131                     }
132                 }
133 
134                 // System.out.println("\tAdding*: " + dtf.format(new Date(low)));
135                 inflectionPoints.add(new InflectionPoint(high, highOffset));
136             }
137             lastOffset = currentOffset;
138             lastDate = currentDate;
139         }
140         // System.out.println("\tAdding: " + dtf.format(new Date(startDate)));
141         inflectionPoints.add(new InflectionPoint(startDate, zone
142             .getOffset(startDate)));
143     }
144 
145     public int compareTo(ZoneInflections other, OutputLong mostRecentDateTime) {
146         mostRecentDateTime.value = 0;
147         if (other == null) {
148             mostRecentDateTime.value = get(0).utcDateTime;
149             return 1;
150         }
151         ZoneInflections that = other;
152         int minLength = inflectionPoints.size();
153         if (minLength < that.inflectionPoints.size())
154             minLength = that.inflectionPoints.size();
155         for (int i = 0; i < minLength; ++i) {
156             InflectionPoint ip1 = get(i);
157             InflectionPoint ip2 = that.get(i);
158             if (ip1.offset == ip2.offset && ip1.utcDateTime == ip2.utcDateTime)
159                 continue;
160             if (ip1.offset != ip2.offset) {
161                 // back up a bit
162                 mostRecentDateTime.value = Math.max(ip1.utcDateTime, ip2.utcDateTime)
163                     - EPSILON;
164             } else if (ip1.utcDateTime > ip2.utcDateTime) {
165                 // offsets are the same, but start times are different
166                 // in that case, find the next inflection point for the shorter one.
167                 mostRecentDateTime.value = ip1.utcDateTime - EPSILON;
168                 ip1 = get(i + 1);
169             } else {
170                 // ditto but reversed
171                 mostRecentDateTime.value = ip2.utcDateTime - EPSILON;
172                 ip2 = that.get(i + 1);
173             }
174             return ip1.offset > ip2.offset ? 1 : ip1.offset < ip2.offset ? -1 : 0;
175         }
176         mostRecentDateTime.value = Long.MIN_VALUE;
177         return 0;
178     }
179 
180     InflectionPoint get(int i) {
181         return inflectionPoints.get(i);
182     }
183 
184     int size() {
185         return inflectionPoints.size();
186     }
187 
188     private transient OutputLong temp = new OutputLong(0);
189 
190     @Override
191     public int compareTo(ZoneInflections o) {
192         return compareTo(o, temp);
193     }
194 
195     public static class InflectionPoint implements Comparable<InflectionPoint> {
196         static final long NONE = Long.MIN_VALUE;
197 
198         public long utcDateTime;
199 
200         public int offset;
201 
202         @Override
203         public String toString() {
204             return ICUServiceBuilder.isoDateFormat(new Date(utcDateTime)) + ";"
205                 + formatHours(offset);
206         }
207 
208         public InflectionPoint(long utcDateTime, int offset) {
209             this.utcDateTime = utcDateTime;
210             this.offset = offset;
211         }
212 
213         /*
214          * public long mostRecentDifference(InflectionPoint other) { InflectionPoint
215          * that = (InflectionPoint) other; if (utcDateTime != that.utcDateTime ||
216          * offset != that.offset) { return Math.max(utcDateTime, that.utcDateTime); }
217          * return NONE; }
218          */
219         @Override
220         public int compareTo(InflectionPoint that) {
221             if (utcDateTime < that.utcDateTime)
222                 return -1;
223             if (utcDateTime > that.utcDateTime)
224                 return 1;
225             if (offset < that.offset)
226                 return -1;
227             if (offset > that.offset)
228                 return 1;
229             return 0;
230         }
231     }
232 
233     public static long getDateLong(int year, int month, int day) {
234         Calendar cal = Calendar.getInstance();
235         cal.set(year, month - 1, day);
236         return cal.getTimeInMillis();
237     }
238 
239     static private final NumberFormat nf = NumberFormat.getInstance(ULocale.US);
240 
241     static public String formatHours(int hours) {
242         return nf.format(hours / ZoneInflections.DHOUR);
243     }
244 
245     public static class OutputLong implements Comparable<Object> {
246         public long value;
247 
248         public OutputLong(long value) {
249             this.value = value;
250         }
251 
252         @Override
253         public int compareTo(Object o) {
254             OutputLong that = (OutputLong) o;
255             return value < that.value ? -1 : value > that.value ? 1 : 0;
256         }
257     }
258 
259     /**
260      * Return the inflection points during a given period. The points are copies
261      * of what is in the data, so it is safe to modify them
262      *
263      * @param inflections2
264      * @param time
265      * @param time2
266      * @return
267      */
268     public List<InflectionPoint> getInflectionPoints(long start, long end) {
269         List<InflectionPoint> results = new ArrayList<>();
270         for (InflectionPoint inflectionPoint : inflectionPoints) {
271             if (inflectionPoint.utcDateTime <= start) {
272                 results.add(new InflectionPoint(start, inflectionPoint.offset));
273                 break;
274             } else if (inflectionPoint.utcDateTime < end) {
275                 results.add(new InflectionPoint(inflectionPoint.utcDateTime,
276                     inflectionPoint.offset));
277             }
278         }
279         return results;
280     }
281 }