jars/icu4j-4_4_2-src/main/tests/translit/src/com/ibm/icu/dev/test/util/UnicodeMap.java

   1 /*\r
   2  *******************************************************************************\r
   3  * Copyright (C) 1996-2010, International Business Machines Corporation and    *\r
   4  * others. All Rights Reserved.                                                *\r
   5  *******************************************************************************\r
   6  */\r
   7 package com.ibm.icu.dev.test.util;\r
   8 \r
   9 import java.util.ArrayList;\r
  10 import java.util.Collection;\r
  11 import java.util.Collections;\r
  12 import java.util.Comparator;\r
  13 import java.util.HashSet;\r
  14 import java.util.Iterator;\r
  15 import java.util.LinkedHashSet;\r
  16 import java.util.Map;\r
  17 import java.util.Set;\r
  18 import java.util.TreeMap;\r
  19 import java.util.TreeSet;\r
  20 import java.util.Map.Entry;\r
  21 \r
  22 import com.ibm.icu.impl.Utility;\r
  23 import com.ibm.icu.text.StringTransform;\r
  24 import com.ibm.icu.text.UTF16;\r
  25 import com.ibm.icu.text.UnicodeSet;\r
  26 import com.ibm.icu.text.UnicodeSetIterator;\r
  27 import com.ibm.icu.util.Freezable;\r
  28 \r
  29 /**\r
  30  * Class for mapping Unicode characters and strings to values, optimized for single code points, \r
  31  * where ranges of code points have the same value.\r
  32  * Much smaller storage than using HashMap, and much faster and more compact than\r
  33  * a list of UnicodeSets. The API design mimics Map<String,T> but can't extend it due to some\r
  34  * necessary changes (much as UnicodeSet mimics Set<String>). Note that nulls are not permitted as values;\r
  35  * that is, a put(x,null) is the same as remove(x).<br>\r
  36  * At this point "" is also not allowed as a key, although that may change.\r
  37  * @author markdavis\r
  38  */\r
  39 \r
  40 public final class UnicodeMap<T> implements Cloneable, Freezable, StringTransform, Iterable<String> {\r
  41     /**\r
  42      * For serialization\r
  43      */\r
  44     //private static final long serialVersionUID = -6540936876295804105L;\r
  45     static final boolean ASSERTIONS = false;\r
  46     static final long GROWTH_PERCENT = 200; // 100 is no growth!\r
  47     static final long GROWTH_GAP = 10; // extra bump!\r
  48 \r
  49     private int length;\r
  50     // two parallel arrays to save memory. Wish Java had structs.\r
  51     private int[] transitions;\r
  52     /* package private */ T[] values;\r
  53 \r
  54     private LinkedHashSet<T> availableValues = new LinkedHashSet<T>();\r
  55     private transient boolean staleAvailableValues;\r
  56 \r
  57     private transient boolean errorOnReset;\r
  58     private transient boolean locked;\r
  59     private int lastIndex;\r
  60     private Map<String,T> stringMap;\r
  61 \r
  62     { clear(); }\r
  63 \r
  64     public UnicodeMap<T> clear() {\r
  65         if (locked) {\r
  66             throw new UnsupportedOperationException("Attempt to modify locked object");\r
  67         }\r
  68         length = 2;\r
  69         transitions = new int[] {0,0x110000,0,0,0,0,0,0,0,0};\r
  70         values = (T[]) new Object[10];\r
  71 \r
  72         availableValues.clear();\r
  73         staleAvailableValues = false;\r
  74 \r
  75         errorOnReset = false;\r
  76         lastIndex = 0;\r
  77         stringMap = null;\r
  78         return this;\r
  79     }\r
  80 \r
  81     /* Boilerplate */\r
  82     public boolean equals(Object other) {\r
  83         if (other == null) return false;\r
  84         try {\r
  85             UnicodeMap that = (UnicodeMap) other;\r
  86             if (length != that.length) return false;\r
  87             for (int i = 0; i < length-1; ++i) {\r
  88                 if (transitions[i] != that.transitions[i]) return false;\r
  89                 if (!areEqual(values[i], that.values[i])) return false;\r
  90             }\r
  91             return true;\r
  92         } catch (ClassCastException e) {\r
  93             return false;\r
  94         }\r
  95     }\r
  96 \r
  97     public static boolean areEqual(Object a , Object b) {\r
  98         if (a == b) return true;\r
  99         if (a == null || b == null) return false;\r
 100         return a.equals(b);\r
 101     }\r
 102 \r
 103     public int hashCode() {\r
 104         int result = length;\r
 105         // TODO might want to abbreviate this for speed.\r
 106         for (int i = 0; i < length-1; ++i) {\r
 107             result = 37*result + transitions[i];\r
 108             result = 37*result + values[i].hashCode();\r
 109         }\r
 110         return result;\r
 111     }\r
 112 \r
 113     /**\r
 114      * Standard clone. Warning, as with Collections, does not do deep clone.\r
 115      */\r
 116     public UnicodeMap<T> cloneAsThawed() {\r
 117         UnicodeMap<T> that = new UnicodeMap<T>();\r
 118         that.length = length;\r
 119         that.transitions = (int[]) transitions.clone();\r
 120         that.values = (T[]) values.clone();\r
 121         that.availableValues = new LinkedHashSet<T>(availableValues);\r
 122         that.locked = false;\r
 123         return that;\r
 124     }\r
 125 \r
 126     /* for internal consistency checking */\r
 127 \r
 128     void _checkInvariants() {\r
 129         if (length < 2\r
 130                 || length > transitions.length\r
 131                 || transitions.length != values.length) {\r
 132             throw new IllegalArgumentException("Invariant failed: Lengths bad");\r
 133         }\r
 134         for (int i = 1; i < length-1; ++i) {\r
 135             if (areEqual(values[i-1], values[i])) {\r
 136                 throw new IllegalArgumentException("Invariant failed: values shared at " \r
 137                         + "\t" + Utility.hex(i-1) + ": <" + values[i-1] + ">"\r
 138                         + "\t" + Utility.hex(i) + ": <" + values[i] + ">"\r
 139                 );\r
 140             }\r
 141         }\r
 142         if (transitions[0] != 0 || transitions[length-1] != 0x110000) {\r
 143             throw new IllegalArgumentException("Invariant failed: bounds set wrong");\r
 144         }\r
 145         for (int i = 1; i < length-1; ++i) {\r
 146             if (transitions[i-1] >= transitions[i]) {\r
 147                 throw new IllegalArgumentException("Invariant failed: not monotonic"\r
 148                         + "\t" + Utility.hex(i-1) + ": " + transitions[i-1]\r
 149                                                                        + "\t" + Utility.hex(i) + ": " + transitions[i]\r
 150                 );\r
 151             }\r
 152         }\r
 153     }\r
 154 \r
 155     /**\r
 156      * Finds an index such that inversionList[i] <= codepoint < inversionList[i+1]\r
 157      * Assumes that 0 <= codepoint <= 0x10FFFF\r
 158      * @param codepoint\r
 159      * @return the index\r
 160      */\r
 161     private int _findIndex(int c) {\r
 162         int lo = 0;\r
 163         int hi = length - 1;\r
 164         int i = (lo + hi) >>> 1;\r
 165         // invariant: c >= list[lo]\r
 166         // invariant: c < list[hi]\r
 167         while (i != lo) {\r
 168             if (c < transitions[i]) {\r
 169                 hi = i;\r
 170             } else {\r
 171                 lo = i;\r
 172             }\r
 173             i = (lo + hi) >>> 1;\r
 174         }\r
 175         if (ASSERTIONS) _checkFind(c, lo);\r
 176         return lo;\r
 177     }\r
 178 \r
 179     private void _checkFind(int codepoint, int value) {\r
 180         int other = __findIndex(codepoint);\r
 181         if (other != value) {\r
 182             throw new IllegalArgumentException("Invariant failed: binary search"\r
 183                     + "\t" + Utility.hex(codepoint) + ": " + value\r
 184                     + "\tshould be: " + other);            \r
 185         }\r
 186     }\r
 187 \r
 188     private int __findIndex(int codepoint) {\r
 189         for (int i = length-1; i > 0; --i) {\r
 190             if (transitions[i] <= codepoint) return i;\r
 191         }\r
 192         return 0;\r
 193     }\r
 194 \r
 195     /*\r
 196      * Try indexed lookup\r
 197 \r
 198     static final int SHIFT = 8;\r
 199     int[] starts = new int[0x10FFFF>>SHIFT]; // lowest transition index where codepoint>>x can be found\r
 200     boolean startsValid = false;\r
 201     private int findIndex(int codepoint) {\r
 202         if (!startsValid) {\r
 203             int start = 0;\r
 204             for (int i = 1; i < length; ++i) {\r
 205 \r
 206             }\r
 207         }\r
 208         for (int i = length-1; i > 0; --i) {\r
 209            if (transitions[i] <= codepoint) return i;\r
 210        }\r
 211        return 0;\r
 212    }\r
 213      */\r
 214 \r
 215     /**\r
 216      * Remove the items from index through index+count-1.\r
 217      * Logically reduces the size of the internal arrays.\r
 218      * @param index\r
 219      * @param count\r
 220      */\r
 221     private void _removeAt(int index, int count) {\r
 222         for (int i = index + count; i < length; ++i) {\r
 223             transitions[i-count] = transitions[i];\r
 224             values[i-count] = values[i];\r
 225         }\r
 226         length -= count;\r
 227     }\r
 228     /**\r
 229      * Add a gap from index to index+count-1.\r
 230      * The values there are undefined, and must be set.\r
 231      * Logically grows arrays to accomodate. Actual growth is limited\r
 232      * @param index\r
 233      * @param count\r
 234      */\r
 235     private void _insertGapAt(int index, int count) {\r
 236         int newLength = length + count;\r
 237         int[] oldtransitions = transitions;\r
 238         T[] oldvalues = values;\r
 239         if (newLength > transitions.length) {\r
 240             int allocation = (int) (GROWTH_GAP + (newLength * GROWTH_PERCENT) / 100);\r
 241             transitions = new int[allocation];\r
 242             values = (T[]) new Object[allocation];\r
 243             for (int i = 0; i < index; ++i) {\r
 244                 transitions[i] = oldtransitions[i];\r
 245                 values[i] = oldvalues[i];\r
 246             }\r
 247         } \r
 248         for (int i = length - 1; i >= index; --i) {\r
 249             transitions[i+count] = oldtransitions[i];\r
 250             values[i+count] = oldvalues[i];\r
 251         }\r
 252         length = newLength;\r
 253     }\r
 254 \r
 255     /**\r
 256      * Associates code point with value. Removes any previous association.\r
 257      * All code that calls this MUST check for frozen first!\r
 258      * @param codepoint\r
 259      * @param value\r
 260      * @return this, for chaining\r
 261      */\r
 262     private UnicodeMap _put(int codepoint, T value) {\r
 263         // Warning: baseIndex is an invariant; must\r
 264         // be defined such that transitions[baseIndex] < codepoint\r
 265         // at end of this routine.\r
 266         int baseIndex;\r
 267         if (transitions[lastIndex] <= codepoint \r
 268                 && codepoint < transitions[lastIndex+1]) {\r
 269             baseIndex = lastIndex;\r
 270         } else { \r
 271             baseIndex = _findIndex(codepoint);\r
 272         }\r
 273         int limitIndex = baseIndex + 1;\r
 274         // cases are (a) value is already set\r
 275         if (areEqual(values[baseIndex], value)) return this;\r
 276         if (locked) {\r
 277             throw new UnsupportedOperationException("Attempt to modify locked object");\r
 278         }\r
 279         if (errorOnReset && values[baseIndex] != null) {\r
 280             throw new IllegalArgumentException("Attempt to reset value for " + Utility.hex(codepoint)\r
 281                     + " when that is disallowed. Old: " + values[baseIndex] + "; New: " + value);\r
 282         }\r
 283 \r
 284         // adjust the available values\r
 285         staleAvailableValues = true;\r
 286         availableValues.add(value); // add if not there already      \r
 287 \r
 288         int baseCP = transitions[baseIndex];\r
 289         int limitCP = transitions[limitIndex];\r
 290         // we now start walking through the difference case,\r
 291         // based on whether we are at the start or end of range\r
 292         // and whether the range is a single character or multiple\r
 293 \r
 294         if (baseCP == codepoint) {\r
 295             // CASE: At very start of range\r
 296             boolean connectsWithPrevious = \r
 297                 baseIndex != 0 && areEqual(value, values[baseIndex-1]);               \r
 298 \r
 299             if (limitCP == codepoint + 1) {\r
 300                 // CASE: Single codepoint range\r
 301                 boolean connectsWithFollowing =\r
 302                     baseIndex < length - 2 && areEqual(value, values[limitIndex]); // was -1\r
 303 \r
 304                 if (connectsWithPrevious) {\r
 305                     // A1a connects with previous & following, so remove index\r
 306                     if (connectsWithFollowing) {\r
 307                         _removeAt(baseIndex, 2);\r
 308                     } else {\r
 309                         _removeAt(baseIndex, 1); // extend previous\r
 310                     }\r
 311                     --baseIndex; // fix up\r
 312                 } else if (connectsWithFollowing) {\r
 313                     _removeAt(baseIndex, 1); // extend following backwards\r
 314                     transitions[baseIndex] = codepoint; \r
 315                 } else {\r
 316                     // doesn't connect on either side, just reset\r
 317                     values[baseIndex] = value;\r
 318                 }\r
 319             } else if (connectsWithPrevious) {             \r
 320                 // A.1: start of multi codepoint range\r
 321                 // if connects\r
 322                 ++transitions[baseIndex]; // extend previous\r
 323             } else {\r
 324                 // otherwise insert new transition\r
 325                 transitions[baseIndex] = codepoint+1; // fix following range\r
 326                 _insertGapAt(baseIndex, 1);\r
 327                 values[baseIndex] = value;\r
 328                 transitions[baseIndex] = codepoint;\r
 329             }\r
 330         } else if (limitCP == codepoint + 1) {\r
 331             // CASE: at end of range        \r
 332             // if connects, just back up range\r
 333             boolean connectsWithFollowing =\r
 334                 baseIndex < length - 2 && areEqual(value, values[limitIndex]); // was -1\r
 335 \r
 336             if (connectsWithFollowing) {\r
 337                 --transitions[limitIndex]; \r
 338                 return this;                \r
 339             } else {\r
 340                 _insertGapAt(limitIndex, 1);\r
 341                 transitions[limitIndex] = codepoint;\r
 342                 values[limitIndex] = value;\r
 343             }\r
 344         } else {\r
 345             // CASE: in middle of range\r
 346             // insert gap, then set the new range\r
 347             _insertGapAt(++baseIndex,2);\r
 348             transitions[baseIndex] = codepoint;\r
 349             values[baseIndex] = value;\r
 350             transitions[baseIndex+1] = codepoint + 1;\r
 351             values[baseIndex+1] = values[baseIndex-1]; // copy lower range values\r
 352         }\r
 353         lastIndex = baseIndex; // store for next time\r
 354         return this;\r
 355     }\r
 356 \r
 357     private UnicodeMap _putAll(int startCodePoint, int endCodePoint, T value) {\r
 358         // TODO optimize\r
 359         for (int i = startCodePoint; i <= endCodePoint; ++i) {\r
 360             _put(i, value);\r
 361             if (ASSERTIONS) _checkInvariants();\r
 362         }\r
 363         return this;\r
 364     }\r
 365 \r
 366     /**\r
 367      * Sets the codepoint value.\r
 368      * @param codepoint\r
 369      * @param value\r
 370      * @return this (for chaining)\r
 371      */\r
 372     public UnicodeMap<T> put(int codepoint, T value) {\r
 373         if (codepoint < 0 || codepoint > 0x10FFFF) {\r
 374             throw new IllegalArgumentException("Codepoint out of range: " + codepoint);\r
 375         }\r
 376         _put(codepoint, value);\r
 377         if (ASSERTIONS) _checkInvariants();\r
 378         return this;\r
 379     }\r
 380 \r
 381     /**\r
 382      * Sets the codepoint value.\r
 383      * @param codepoint\r
 384      * @param value\r
 385      * @return this (for chaining)\r
 386      */\r
 387     public UnicodeMap<T> put(String string, T value) {\r
 388         int v = UnicodeSet.getSingleCodePoint(string);\r
 389         if (v == Integer.MAX_VALUE) {\r
 390             if (value != null) {\r
 391                 if (stringMap == null) {\r
 392                     stringMap = new TreeMap<String,T>();\r
 393                 }\r
 394                 stringMap.put(string, value);\r
 395                 staleAvailableValues = true;\r
 396             } else if (stringMap != null) {\r
 397                 if (stringMap.remove(string) != null) {\r
 398                     staleAvailableValues = true;\r
 399                 }\r
 400             }\r
 401             return this;\r
 402         }\r
 403         return put(v, value);\r
 404     }\r
 405 \r
 406     /**\r
 407      * Adds bunch o' codepoints; otherwise like put.\r
 408      * @param codepoints\r
 409      * @param value\r
 410      * @return this (for chaining)\r
 411      */\r
 412     public UnicodeMap<T> putAll(UnicodeSet codepoints, T value) {\r
 413         UnicodeSetIterator it = new UnicodeSetIterator(codepoints);\r
 414         while (it.nextRange()) {\r
 415             _putAll(it.codepoint, it.codepointEnd, value);\r
 416         }\r
 417         for (String key : codepoints.strings()) {\r
 418             put(key, value);\r
 419         }\r
 420         return this;\r
 421     }\r
 422 \r
 423     /**\r
 424      * Adds bunch o' codepoints; otherwise like add.\r
 425      * @param startCodePoint\r
 426      * @param endCodePoint\r
 427      * @param value\r
 428      * @return this (for chaining)\r
 429      */\r
 430     public UnicodeMap<T> putAll(int startCodePoint, int endCodePoint, T value) {\r
 431         if (locked) {\r
 432             throw new UnsupportedOperationException("Attempt to modify locked object");\r
 433         }\r
 434         if (startCodePoint < 0 || endCodePoint > 0x10FFFF) {\r
 435             throw new IllegalArgumentException("Codepoint out of range: "\r
 436                     + Utility.hex(startCodePoint) + ".." + Utility.hex(endCodePoint));\r
 437         }\r
 438         return _putAll(startCodePoint, endCodePoint, value);\r
 439     }\r
 440 \r
 441     /**\r
 442      * Add all the (main) values from a UnicodeMap\r
 443      * @param unicodeMap the property to add to the map\r
 444      * @return this (for chaining)\r
 445      */\r
 446     public UnicodeMap<T> putAll(UnicodeMap<T> unicodeMap) {    \r
 447         for (int i = 0; i < unicodeMap.length; ++i) {\r
 448             T value = unicodeMap.values[i];\r
 449             if (value != null) {\r
 450                 _putAll(unicodeMap.transitions[i], unicodeMap.transitions[i+1]-1, value);\r
 451             }\r
 452             if (ASSERTIONS) _checkInvariants();\r
 453         }\r
 454         if (unicodeMap.stringMap != null && !unicodeMap.stringMap.isEmpty()) {\r
 455             if (stringMap == null) {\r
 456                 stringMap = new TreeMap<String,T>();\r
 457             }\r
 458             stringMap.putAll(unicodeMap.stringMap);\r
 459         }\r
 460         return this;\r
 461     }\r
 462 \r
 463     /**\r
 464      * Add all the (main) values from a Unicode property\r
 465      * @param prop the property to add to the map\r
 466      * @return this (for chaining)\r
 467      */\r
 468     public UnicodeMap<T> putAllFiltered(UnicodeMap<T> prop, UnicodeSet filter) {\r
 469         // TODO optimize\r
 470         for (UnicodeSetIterator it = new UnicodeSetIterator(filter); it.next();) {\r
 471             if (it.codepoint != UnicodeSetIterator.IS_STRING) {\r
 472                 T value = prop.getValue(it.codepoint);\r
 473                 if (value != null) {\r
 474                     _put(it.codepoint, value);\r
 475                 }\r
 476             }\r
 477         }\r
 478         // now do the strings\r
 479         for (String key : filter.strings()) {\r
 480             T value = prop.get(key);\r
 481             if (value != null) {\r
 482                 put(key, value);\r
 483             }\r
 484         }\r
 485         return this;\r
 486     }\r
 487 \r
 488     /**\r
 489      * Set the currently unmapped Unicode code points to the given value.\r
 490      * @param value the value to set\r
 491      * @return this (for chaining)\r
 492      */\r
 493     public UnicodeMap<T> setMissing(T value) {\r
 494         // fast path, if value not yet present\r
 495         if (!getAvailableValues().contains(value)) {\r
 496             staleAvailableValues = true;\r
 497             availableValues.add(value);\r
 498             for (int i = 0; i < length; ++i) {\r
 499                 if (values[i] == null) values[i] = value;\r
 500             }\r
 501             return this;\r
 502         } else {\r
 503             return putAll(keySet(null), value);\r
 504         }\r
 505     }\r
 506     /**\r
 507      * Returns the keyset consisting of all the keys that would produce the given value. Deposits into\r
 508      * result if it is not null. Remember to clear if you just want\r
 509      * the new values.\r
 510      */\r
 511     public UnicodeSet keySet(T value, UnicodeSet result) {\r
 512         if (result == null) result = new UnicodeSet();\r
 513         for (int i = 0; i < length - 1; ++i) {\r
 514             if (areEqual(value, values[i])) {\r
 515                 result.add(transitions[i], transitions[i+1]-1);\r
 516             } \r
 517         }\r
 518         if (value != null && stringMap != null) {\r
 519             for (String key : stringMap.keySet()) {\r
 520                 T newValue = stringMap.get(key);\r
 521                 if (value.equals(newValue)) {\r
 522                     result.add((String)key);\r
 523                 }\r
 524             }\r
 525         }\r
 526         return result;\r
 527     }\r
 528 \r
 529     /**\r
 530      * Returns the keyset consisting of all the keys that would produce the given value.\r
 531      * the new values.\r
 532      */\r
 533     public UnicodeSet keySet(T value) {\r
 534         return keySet(value,null);\r
 535     }\r
 536     \r
 537     /**\r
 538      * Returns the keyset consisting of all the keys that would produce (non-null) values.\r
 539      */\r
 540     public UnicodeSet keySet() {\r
 541         UnicodeSet result = new UnicodeSet();\r
 542         for (int i = 0; i < length - 1; ++i) {\r
 543             if (values[i] != null) {\r
 544                 result.add(transitions[i], transitions[i+1]-1);\r
 545             } \r
 546         }\r
 547         if (stringMap != null) {\r
 548             result.addAll(stringMap.keySet());\r
 549         }\r
 550         return result;\r
 551     }\r
 552 \r
 553     /**\r
 554      * Returns the list of possible values. Deposits each non-null value into\r
 555      * result. Creates result if it is null. Remember to clear result if\r
 556      * you are not appending to existing collection.\r
 557      * @param result\r
 558      * @return result\r
 559      */\r
 560     public <U extends Collection<T>> U values(U result) {\r
 561         if (staleAvailableValues) {\r
 562             // collect all the current values\r
 563             // retain them in the availableValues\r
 564             Set<T> temp = new HashSet<T>();\r
 565             for (int i = 0; i < length - 1; ++i) {\r
 566                 if (values[i] != null) temp.add(values[i]);\r
 567             }\r
 568             availableValues.retainAll(temp);\r
 569             if (stringMap != null) {\r
 570                 availableValues.addAll(stringMap.values());\r
 571             }\r
 572             staleAvailableValues = false;\r
 573         }\r
 574         if (result == null) {\r
 575             result = (U) new ArrayList<T>(availableValues.size());\r
 576         }\r
 577         result.addAll(availableValues);\r
 578         return result;\r
 579     }\r
 580 \r
 581     /**\r
 582      * Convenience method\r
 583      */\r
 584     public Collection<T> values() {\r
 585         return getAvailableValues(null);\r
 586     }\r
 587     /**\r
 588      * Gets the value associated with a given code point.\r
 589      * Returns null, if there is no such value.\r
 590      * @param codepoint\r
 591      * @return the value\r
 592      */\r
 593     public T get(int codepoint) {\r
 594         if (codepoint < 0 || codepoint > 0x10FFFF) {\r
 595             throw new IllegalArgumentException("Codepoint out of range: " + codepoint);\r
 596         }\r
 597         return values[_findIndex(codepoint)];\r
 598     }\r
 599 \r
 600     /**\r
 601      * Gets the value associated with a given code point.\r
 602      * Returns null, if there is no such value.\r
 603      * @param codepoint\r
 604      * @return the value\r
 605      */\r
 606     public T get(String value) {\r
 607         if (UTF16.hasMoreCodePointsThan(value, 1)) {\r
 608             if (stringMap == null) {\r
 609                 return null;\r
 610             }\r
 611             return stringMap.get(value);\r
 612         }\r
 613         return getValue(UTF16.charAt(value, 0));\r
 614     }\r
 615 \r
 616 \r
 617     /**\r
 618      * Change a new string from the source string according to the mappings.\r
 619      * For each code point cp, if getValue(cp) is null, append the character, otherwise append getValue(cp).toString()\r
 620      * TODO: extend to strings\r
 621      * @param source\r
 622      * @return\r
 623      */\r
 624     public String transform(String source) {\r
 625         StringBuffer result = new StringBuffer();\r
 626         int cp;\r
 627         for (int i = 0; i < source.length(); i += UTF16.getCharCount(cp)) {\r
 628             cp = UTF16.charAt(source, i);\r
 629             T mResult = getValue(cp);\r
 630             if (mResult != null) {\r
 631                 result.append(mResult);\r
 632             } else {\r
 633                 UTF16.append(result, cp);\r
 634             }\r
 635         }\r
 636         return result.toString();\r
 637     }\r
 638 \r
 639     /**\r
 640      * Used to add complex values, where the value isn't replaced but in some sense composed\r
 641      * @author markdavis\r
 642      */\r
 643     public abstract static class Composer<T> {\r
 644         /**\r
 645          * This will be called with either a string or a code point. The result is the new value for that item.\r
 646          * If the codepoint is used, the string is null; if the string is used, the codepoint is -1.\r
 647          * @param a\r
 648          * @param b\r
 649          */\r
 650         public abstract T compose(int codePoint, String string, T a, T b);\r
 651     }\r
 652 \r
 653     public UnicodeMap<T> composeWith(UnicodeMap<T> other, Composer<T> composer) {\r
 654         for (T value : other.getAvailableValues()) {\r
 655             UnicodeSet set = other.keySet(value);\r
 656             composeWith(set, value, composer);\r
 657         }\r
 658         return this;\r
 659     }\r
 660 \r
 661     public UnicodeMap<T> composeWith(UnicodeSet set, T value, Composer<T> composer) {\r
 662         for (UnicodeSetIterator it = new UnicodeSetIterator(set); it.next();) {\r
 663             int i = it.codepoint;\r
 664             if (i == UnicodeSetIterator.IS_STRING) {\r
 665                 String s = it.string;\r
 666                 T v1 = getValue(s);\r
 667                 T v3 = composer.compose(-1, s, v1, value);\r
 668                 if (v1 != v3 && (v1 == null || !v1.equals(v3))) {\r
 669                     put(s, v3);\r
 670                 }                \r
 671             } else {\r
 672                 T v1 = getValue(i);\r
 673                 T v3 = composer.compose(i, null, v1, value);\r
 674                 if (v1 != v3 && (v1 == null || !v1.equals(v3))) {\r
 675                     put(i, v3);\r
 676                 }\r
 677             }\r
 678         }\r
 679         return this;\r
 680     }\r
 681 \r
 682     public String toString() {\r
 683         return toString(null);\r
 684     }\r
 685 \r
 686     public String toString(Comparator<T> collected) {\r
 687         StringBuffer result = new StringBuffer();       \r
 688         if (collected == null) {\r
 689             for (int i = 0; i < length-1; ++i) {\r
 690                 T value = values[i];\r
 691                 if (value == null) continue;\r
 692                 int start = transitions[i];\r
 693                 int end = transitions[i+1]-1;\r
 694                 result.append(Utility.hex(start));\r
 695                 if (start != end) result.append("-").append(Utility.hex(end));\r
 696                 result.append("=").append(value.toString()).append("\n");\r
 697             }\r
 698             if (stringMap != null) {\r
 699                 for (String s : stringMap.keySet()) {\r
 700                     result.append(Utility.hex(s)).append("=").append(stringMap.get(s).toString()).append("\n");\r
 701                 }\r
 702             }\r
 703         } else {\r
 704             Set<T> set = values(new TreeSet<T>(collected));\r
 705             for (Iterator<T> it = set.iterator(); it.hasNext();) {\r
 706                 T value = it.next();\r
 707                 UnicodeSet s = keySet(value);\r
 708                 result.append(value).append("=").append(s.toString()).append("\n");\r
 709             }\r
 710         }\r
 711         return result.toString();\r
 712     }\r
 713     /**\r
 714      * @return Returns the errorOnReset value.\r
 715      */\r
 716     public boolean getErrorOnReset() {\r
 717         return errorOnReset;\r
 718     }\r
 719     /**\r
 720      * Puts the UnicodeMap into a state whereby new mappings are accepted, but changes to old mappings cause an exception.\r
 721      * @param errorOnReset The errorOnReset to set.\r
 722      */\r
 723     public UnicodeMap<T> setErrorOnReset(boolean errorOnReset) {\r
 724         this.errorOnReset = errorOnReset;\r
 725         return this;\r
 726     }\r
 727 \r
 728     /* (non-Javadoc)\r
 729      * @see com.ibm.icu.dev.test.util.Freezable#isFrozen()\r
 730      */\r
 731     public boolean isFrozen() {\r
 732         // TODO Auto-generated method stub\r
 733         return locked;\r
 734     }\r
 735 \r
 736     /* (non-Javadoc)\r
 737      * @see com.ibm.icu.dev.test.util.Freezable#lock()\r
 738      */\r
 739     public UnicodeMap<T> freeze() {\r
 740         locked = true;\r
 741         return this;\r
 742     }\r
 743 \r
 744     /**\r
 745      * Utility to find the maximal common prefix of two strings.\r
 746      * TODO: fix supplemental support\r
 747      */\r
 748     static public int findCommonPrefix(String last, String s) {\r
 749         int minLen = Math.min(last.length(), s.length());\r
 750         for (int i = 0; i < minLen; ++i) {\r
 751             if (last.charAt(i) != s.charAt(i)) return i;\r
 752         }\r
 753         return minLen;\r
 754     }\r
 755 \r
 756     /**\r
 757      * Get the number of ranges; used for getRangeStart/End. The ranges together cover all of the single-codepoint keys in the UnicodeMap. Other keys can be gotten with getStrings().\r
 758      */\r
 759     public int getRangeCount() {\r
 760         return length-1;\r
 761     }\r
 762 \r
 763     /**\r
 764      * Get the start of a range. All code points between start and end are in the UnicodeMap's keyset.\r
 765      */\r
 766     public int getRangeStart(int range) {\r
 767         return transitions[range];\r
 768     }\r
 769 \r
 770     /**\r
 771      * Get the start of a range. All code points between start and end are in the UnicodeMap's keyset.\r
 772      */\r
 773     public int getRangeEnd(int range) {\r
 774         return transitions[range+1] - 1;\r
 775     }\r
 776 \r
 777     /**\r
 778      * Get the value for the range.\r
 779      */\r
 780     public T getRangeValue(int range) {\r
 781         return values[range];\r
 782     }\r
 783 \r
 784     /**\r
 785      * Get the strings that are not in the ranges. Returns null if there are none.\r
 786      * @return\r
 787      */\r
 788     public Set<String> getNonRangeStrings() {\r
 789         if (stringMap == null || stringMap.isEmpty()) {\r
 790             return null;\r
 791         }\r
 792         return Collections.unmodifiableSet(stringMap.keySet());\r
 793     }\r
 794 \r
 795     static final boolean DEBUG_WRITE = false;\r
 796 \r
 797     /* (non-Javadoc)\r
 798      * @see java.util.Map#containsKey(java.lang.Object)\r
 799      */\r
 800     public boolean containsKey(String key) {\r
 801         return getValue(key) != null;\r
 802     }\r
 803 \r
 804     /* (non-Javadoc)\r
 805      * @see java.util.Map#containsKey(java.lang.Object)\r
 806      */\r
 807     public boolean containsKey(int key) {\r
 808         return getValue(key) != null;\r
 809     }\r
 810 \r
 811     /* (non-Javadoc)\r
 812      * @see java.util.Map#containsValue(java.lang.Object)\r
 813      */\r
 814     public boolean containsValue(T value) {\r
 815         // TODO Optimize\r
 816         return getAvailableValues().contains(value);\r
 817     }\r
 818 \r
 819     /* (non-Javadoc)\r
 820      * @see java.util.Map#isEmpty()\r
 821      */\r
 822     public boolean isEmpty() {\r
 823         return size() == 0;\r
 824     }\r
 825 \r
 826     /* (non-Javadoc)\r
 827      * @see java.util.Map#putAll(java.util.Map)\r
 828      */\r
 829     public UnicodeMap<T> putAll(Map<? extends String, ? extends T> map) {\r
 830         for (String key : map.keySet()) {\r
 831             put(key,map.get(key));\r
 832         }\r
 833         return this;\r
 834     }\r
 835 \r
 836     /**\r
 837      * Utility for extracting map\r
 838      */\r
 839     public UnicodeMap<T> putAllIn(Map<? super String, ? super T> map) {\r
 840         for (String key : keySet()) {\r
 841             map.put(key, get(key));\r
 842         }\r
 843         return this;\r
 844     }\r
 845 \r
 846     /* (non-Javadoc)\r
 847      * @see java.util.Map#remove(java.lang.Object)\r
 848      */\r
 849     public UnicodeMap<T> remove(String key) {\r
 850         return put(key, null);\r
 851     }\r
 852 \r
 853     /* (non-Javadoc)\r
 854      * @see java.util.Map#remove(java.lang.Object)\r
 855      */\r
 856     public UnicodeMap<T> remove(int key) {\r
 857         return put(key, null);\r
 858     }\r
 859 \r
 860     /* (non-Javadoc)\r
 861      * @see java.util.Map#size()\r
 862      */\r
 863     public int size() {\r
 864         int result = stringMap == null ? 0 : stringMap.size();\r
 865         for (int i = 0; i < length-1; ++i) {\r
 866             T value = values[i];\r
 867             if (value == null) continue;\r
 868             result += transitions[i+1] - transitions[i];\r
 869         }\r
 870         return result;\r
 871     }\r
 872 \r
 873     /* (non-Javadoc)\r
 874      * @see java.util.Map#entrySet()\r
 875      */\r
 876     public Iterable<Entry<String,T>> entrySet() {\r
 877         return new EntrySetX();\r
 878     }\r
 879 \r
 880     private class EntrySetX implements Iterable<Entry<String, T>> {\r
 881         public Iterator<Entry<String, T>> iterator() {\r
 882             return new IteratorX();\r
 883         }\r
 884         public String toString() {\r
 885             StringBuffer b = new StringBuffer();\r
 886             for (Iterator it = iterator(); it.hasNext();) {\r
 887                 Object item = it.next();\r
 888                 b.append(item.toString()).append(' ');\r
 889             }\r
 890             return b.toString();\r
 891         }\r
 892     }\r
 893 \r
 894     private class IteratorX implements Iterator<Entry<String, T>> {\r
 895         Iterator<String> iterator = keySet().iterator();\r
 896 \r
 897         /* (non-Javadoc)\r
 898          * @see java.util.Iterator#hasNext()\r
 899          */\r
 900         public boolean hasNext() {\r
 901             return iterator.hasNext();\r
 902         }\r
 903 \r
 904         /* (non-Javadoc)\r
 905          * @see java.util.Iterator#next()\r
 906          */\r
 907         public Entry<String, T> next() {\r
 908             String key = iterator.next();\r
 909             return new ImmutableEntry(key, get(key));\r
 910         }\r
 911 \r
 912         /* (non-Javadoc)\r
 913          * @see java.util.Iterator#remove()\r
 914          */\r
 915         public void remove() {\r
 916             throw new UnsupportedOperationException();\r
 917         }\r
 918 \r
 919     }\r
 920 \r
 921     /* (non-Javadoc)\r
 922      * @see java.lang.Iterable#iterator()\r
 923      */\r
 924     public Iterator<String> iterator() {\r
 925         return keySet().iterator();\r
 926     }\r
 927 \r
 928     /**\r
 929      * Old form for compatibility\r
 930      */\r
 931     public T getValue(String key) {\r
 932         return get(key);\r
 933     }\r
 934 \r
 935     /**\r
 936      * Old form for compatibility\r
 937      */\r
 938     public T getValue(int key) {\r
 939         // TODO Auto-generated method stub\r
 940         return get(key);\r
 941     }\r
 942 \r
 943     /**\r
 944      * Old form for compatibility\r
 945      */\r
 946     public Collection<T> getAvailableValues() {\r
 947         return values();\r
 948     }\r
 949 \r
 950     /**\r
 951      * Old form for compatibility\r
 952      */\r
 953     public <U extends Collection<T>> U getAvailableValues(U result) {\r
 954         return values(result);\r
 955     }\r
 956 \r
 957     /**\r
 958      * Old form for compatibility\r
 959      */\r
 960     public UnicodeSet getSet(T value) {\r
 961         return keySet(value);\r
 962     }\r
 963 \r
 964     /**\r
 965      * Old form for compatibility\r
 966      */\r
 967     public UnicodeSet getSet(T value, UnicodeSet result) {\r
 968         return keySet(value, result);\r
 969     }\r
 970 \r
 971     // This is to support compressed serialization. It works; just commented out for now as we shift to Generics\r
 972     // TODO Fix once generics are cleaned up.\r
 973     //    // TODO Fix to serialize more than just strings.\r
 974     //    // Only if all the items are strings will we do the following compression\r
 975     //    // Otherwise we'll just use Java Serialization, bulky as it is\r
 976     //    public void writeExternal(ObjectOutput out1) throws IOException {\r
 977     //        DataOutputCompressor sc = new DataOutputCompressor(out1);\r
 978     //        // if all objects are strings\r
 979     //        Collection<T> availableVals = getAvailableValues();\r
 980     //        boolean allStrings = allAreString(availableVals);\r
 981     //        sc.writeBoolean(allStrings);\r
 982     //        Map object_index = new LinkedHashMap();\r
 983     //        if (allAreString(availableVals)) {\r
 984     //            sc.writeStringSet(new TreeSet(availableVals), object_index);\r
 985     //        } else {\r
 986     //            sc.writeCollection(availableVals, object_index);           \r
 987     //        }\r
 988     //        sc.writeUInt(length);\r
 989     //        int lastTransition = -1;\r
 990     //        int lastValueNumber = 0;\r
 991     //        if (DEBUG_WRITE) System.out.println("Trans count: " + length);\r
 992     //        for (int i = 0; i < length; ++i) {\r
 993     //            int valueNumber = ((Integer)object_index.get(values[i])).intValue();\r
 994     //            if (DEBUG_WRITE) System.out.println("Trans: " + transitions[i] + ",\t" + valueNumber);\r
 995     //\r
 996     //            int deltaTransition = transitions[i] - lastTransition;\r
 997     //            lastTransition = transitions[i];\r
 998     //            int deltaValueNumber = valueNumber - lastValueNumber;\r
 999     //            lastValueNumber = valueNumber;\r
1000     //\r
1001     //            deltaValueNumber <<= 1; // make room for one bit\r
1002     //            boolean canCombine = deltaTransition == 1;\r
1003     //            if (canCombine) deltaValueNumber |= 1;\r
1004     //            sc.writeInt(deltaValueNumber);\r
1005     //            if (DEBUG_WRITE) System.out.println("deltaValueNumber: " + deltaValueNumber);\r
1006     //            if (!canCombine) {\r
1007     //                sc.writeUInt(deltaTransition);\r
1008     //                if (DEBUG_WRITE) System.out.println("deltaTransition: " + deltaTransition);\r
1009     //            }\r
1010     //        }\r
1011     //        sc.flush();\r
1012     //    }\r
1013     //\r
1014     //    /**\r
1015     //     * \r
1016     //     */\r
1017     //    private boolean allAreString(Collection<T> availableValues2) {\r
1018     //        //if (true) return false;\r
1019     //        for (Iterator<T> it = availableValues2.iterator(); it.hasNext();) {\r
1020     //            if (!(it.next() instanceof String)) return false;\r
1021     //        }\r
1022     //        return true;\r
1023     //    }\r
1024     //\r
1025     //    public void readExternal(ObjectInput in1) throws IOException, ClassNotFoundException {\r
1026     //        DataInputCompressor sc = new DataInputCompressor(in1);\r
1027     //        boolean allStrings = sc.readBoolean();\r
1028     //        T[] valuesList;\r
1029     //        availableValues = new LinkedHashSet();\r
1030     //        if (allStrings) {\r
1031     //            valuesList = sc.readStringSet(availableValues);\r
1032     //        } else {\r
1033     //            valuesList = sc.readCollection(availableValues);            \r
1034     //        }\r
1035     //        length = sc.readUInt();\r
1036     //        transitions = new int[length];\r
1037     //        if (DEBUG_WRITE) System.out.println("Trans count: " + length);\r
1038     //        values = (T[]) new Object[length];\r
1039     //        int currentTransition = -1;\r
1040     //        int currentValue = 0;\r
1041     //        int deltaTransition;\r
1042     //        for (int i = 0; i < length; ++i) {\r
1043     //            int temp = sc.readInt();\r
1044     //            if (DEBUG_WRITE) System.out.println("deltaValueNumber: " + temp);\r
1045     //            boolean combined = (temp & 1) != 0;\r
1046     //            temp >>= 1;\r
1047     //        values[i] = valuesList[currentValue += temp];\r
1048     //        if (!combined) {\r
1049     //            deltaTransition = sc.readUInt();\r
1050     //            if (DEBUG_WRITE) System.out.println("deltaTransition: " + deltaTransition);\r
1051     //        } else {\r
1052     //            deltaTransition = 1;\r
1053     //        }\r
1054     //        transitions[i] = currentTransition += deltaTransition; // delta value\r
1055     //        if (DEBUG_WRITE) System.out.println("Trans: " + transitions[i] + ",\t" + currentValue);\r
1056     //        }\r
1057     //    }\r
1058 }\r