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 }