jars/icu4j-52_1/main/tests/framework/src/com/ibm/icu/dev/util/UnicodeMap.java

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