1 /* GENERATED SOURCE. DO NOT MODIFY. */ 2 // 2016 and later: Unicode, Inc. and others. 3 // License & terms of use: http://www.unicode.org/copyright.html#License 4 /* 5 ******************************************************************************* 6 * Copyright (C) 1996-2015, Google, Inc., International Business Machines Corporation and 7 * others. All Rights Reserved. 8 ******************************************************************************* 9 */ 10 package android.icu.impl; 11 12 import java.util.Collection; 13 import java.util.Comparator; 14 import java.util.Iterator; 15 import java.util.LinkedList; 16 import java.util.Map.Entry; 17 import java.util.Set; 18 import java.util.TreeMap; 19 import java.util.TreeSet; 20 21 import android.icu.lang.CharSequences; 22 import android.icu.util.ICUException; 23 24 /** 25 * @hide Only a subset of ICU is exposed in Android 26 */ 27 @SuppressWarnings("deprecation") 28 public class StringRange { 29 private static final boolean DEBUG = false; 30 31 public interface Adder { 32 /** 33 * @param start 34 * @param end may be null, for adding single string 35 */ 36 void add(String start, String end); 37 } 38 39 public static final Comparator<int[]> COMPARE_INT_ARRAYS = new Comparator<int[]>() { 40 @Override 41 public int compare(int[] o1, int[] o2) { 42 int minIndex = Math.min(o1.length, o2.length); 43 for (int i = 0; i < minIndex; ++i) { 44 int diff = o1[i] - o2[i]; 45 if (diff != 0) { 46 return diff; 47 } 48 } 49 return o1.length - o2.length; 50 } 51 }; 52 53 /** 54 * Compact the set of strings. 55 * @param source set of strings 56 * @param adder adds each pair to the output. See the {@link Adder} interface. 57 * @param shorterPairs use abc-d instead of abc-abd 58 * @param moreCompact use a more compact form, at the expense of more processing. If false, source must be sorted. 59 */ 60 public static void compact(Set<String> source, Adder adder, boolean shorterPairs, boolean moreCompact) { 61 if (!moreCompact) { 62 String start = null; 63 String end = null; 64 int lastCp = 0; 65 int prefixLen = 0; 66 for (String s : source) { 67 if (start != null) { // We have something queued up 68 if (s.regionMatches(0, start, 0, prefixLen)) { 69 int currentCp = s.codePointAt(prefixLen); 70 if (currentCp == 1+lastCp && s.length() == prefixLen + Character.charCount(currentCp)) { 71 end = s; 72 lastCp = currentCp; 73 continue; 74 } 75 } 76 // We failed to find continuation. Add what we have and restart 77 adder.add(start, end == null ? null 78 : !shorterPairs ? end 79 : end.substring(prefixLen, end.length())); 80 } 81 // new possible range 82 start = s; 83 end = null; 84 lastCp = s.codePointBefore(s.length()); 85 prefixLen = s.length() - Character.charCount(lastCp); 86 } 87 adder.add(start, end == null ? null 88 : !shorterPairs ? end 89 : end.substring(prefixLen, end.length())); 90 } else { 91 // not a fast algorithm, but ok for now 92 // TODO rewire to use the first (slower) algorithm to generate the ranges, then compact them from there. 93 // first sort by lengths 94 Relation<Integer,Ranges> lengthToArrays = Relation.of(new TreeMap<Integer,Set<Ranges>>(), TreeSet.class); 95 for (String s : source) { 96 Ranges item = new Ranges(s); 97 lengthToArrays.put(item.size(), item); 98 } 99 // then compact items of each length and emit compacted sets 100 for (Entry<Integer, Set<Ranges>> entry : lengthToArrays.keyValuesSet()) { 101 LinkedList<Ranges> compacted = compact(entry.getKey(), entry.getValue()); 102 for (Ranges ranges : compacted) { 103 adder.add(ranges.start(), ranges.end(shorterPairs)); 104 } 105 } 106 } 107 } 108 109 /** 110 * Faster but not as good compaction. Only looks at final codepoint. 111 * @param source set of strings 112 * @param adder adds each pair to the output. See the {@link Adder} interface. 113 * @param shorterPairs use abc-d instead of abc-abd 114 */ 115 public static void compact(Set<String> source, Adder adder, boolean shorterPairs) { 116 compact(source,adder,shorterPairs,false); 117 } 118 119 private static LinkedList<Ranges> compact(int size, Set<Ranges> inputRanges) { 120 LinkedList<Ranges> ranges = new LinkedList<Ranges>(inputRanges); 121 for (int i = size-1; i >= 0; --i) { 122 Ranges last = null; 123 for (Iterator<Ranges> it = ranges.iterator(); it.hasNext();) { 124 Ranges item = it.next(); 125 if (last == null) { 126 last = item; 127 } else if (last.merge(i, item)) { 128 it.remove(); 129 } else { 130 last = item; // go to next 131 } 132 } 133 }; 134 return ranges; 135 } 136 137 static final class Range implements Comparable<Range>{ 138 int min; 139 int max; 140 public Range(int min, int max) { 141 this.min = min; 142 this.max = max; 143 } 144 @Override 145 public boolean equals(Object obj) { 146 return this == obj || (obj != null && obj instanceof Range && compareTo((Range)obj) == 0); 147 } 148 @Override 149 public int compareTo(Range that) { 150 int diff = min - that.min; 151 if (diff != 0) { 152 return diff; 153 } 154 return max - that.max; 155 } 156 @Override 157 public int hashCode() { 158 return min * 37 + max; 159 } 160 @Override 161 public String toString() { 162 StringBuilder result = new StringBuilder().appendCodePoint(min); 163 return min == max ? result.toString() : result.append('~').appendCodePoint(max).toString(); 164 } 165 } 166 167 static final class Ranges implements Comparable<Ranges> { 168 private final Range[] ranges; 169 public Ranges(String s) { 170 int[] array = CharSequences.codePoints(s); 171 ranges = new Range[array.length]; 172 for (int i = 0; i < array.length; ++i) { 173 ranges[i] = new Range(array[i], array[i]); 174 } 175 } 176 public boolean merge(int pivot, Ranges other) { 177 // We merge items if the pivot is adjacent, and all later ranges are equal. 178 for (int i = ranges.length-1; i >= 0; --i) { 179 if (i == pivot) { 180 if (ranges[i].max != other.ranges[i].min-1) { // not adjacent 181 return false; 182 } 183 } else { 184 if (!ranges[i].equals(other.ranges[i])) { 185 return false; 186 } 187 } 188 } 189 if (DEBUG) System.out.print("Merging: " + this + ", " + other); 190 ranges[pivot].max = other.ranges[pivot].max; 191 if (DEBUG) System.out.println(" => " + this); 192 return true; 193 } 194 195 public String start() { 196 StringBuilder result = new StringBuilder(); 197 for (int i = 0; i < ranges.length; ++i) { 198 result.appendCodePoint(ranges[i].min); 199 } 200 return result.toString(); 201 } 202 public String end(boolean mostCompact) { 203 int firstDiff = firstDifference(); 204 if (firstDiff == ranges.length) { 205 return null; 206 } 207 StringBuilder result = new StringBuilder(); 208 for (int i = mostCompact ? firstDiff : 0; i < ranges.length; ++i) { 209 result.appendCodePoint(ranges[i].max); 210 } 211 return result.toString(); 212 } 213 public int firstDifference() { 214 for (int i = 0; i < ranges.length; ++i) { 215 if (ranges[i].min != ranges[i].max){ 216 return i; 217 } 218 } 219 return ranges.length; 220 } 221 public Integer size() { 222 return ranges.length; 223 } 224 @Override 225 public int compareTo(Ranges other) { 226 int diff = ranges.length - other.ranges.length; 227 if (diff != 0) { 228 return diff; 229 } 230 for (int i = 0; i < ranges.length; ++i) { 231 diff = ranges[i].compareTo(other.ranges[i]); 232 if (diff != 0) { 233 return diff; 234 } 235 } 236 return 0; 237 } 238 @Override 239 public String toString() { 240 String start = start(); 241 String end = end(false); 242 return end == null ? start : start + "~" + end; 243 } 244 } 245 246 public static Collection<String> expand(String start, String end, boolean requireSameLength, Collection<String> output) { 247 if (start == null || end == null) { 248 throw new ICUException("Range must have 2 valid strings"); 249 } 250 int[] startCps = CharSequences.codePoints(start); 251 int[] endCps = CharSequences.codePoints(end); 252 int startOffset = startCps.length - endCps.length; 253 254 if (requireSameLength && startOffset != 0) { 255 throw new ICUException("Range must have equal-length strings"); 256 } else if (startOffset < 0) { 257 throw new ICUException("Range must have start-length end-length"); 258 } else if (endCps.length == 0) { 259 throw new ICUException("Range must have end-length > 0"); 260 } 261 262 StringBuilder builder = new StringBuilder(); 263 for (int i = 0; i < startOffset; ++i) { 264 builder.appendCodePoint(startCps[i]); 265 } 266 add(0, startOffset, startCps, endCps, builder, output); 267 return output; 268 } 269 270 private static void add(int endIndex, int startOffset, int[] starts, int[] ends, StringBuilder builder, Collection<String> output) { 271 int start = starts[endIndex+startOffset]; 272 int end = ends[endIndex]; 273 if (start > end) { 274 throw new ICUException("Range must have x y for each index i"); 275 } 276 boolean last = endIndex == ends.length - 1; 277 int startLen = builder.length(); 278 for (int i = start; i <= end; ++i) { 279 builder.appendCodePoint(i); 280 if (last) { 281 output.add(builder.toString()); 282 } else { 283 add(endIndex+1, startOffset, starts, ends, builder, output); 284 } 285 builder.setLength(startLen); 286 } 287 } 288 } 289