jars/icu4j-4_2_1-src/src/com/ibm/icu/impl/Utility.java

   1 //##header J2SE15
   2 /*
   3  *******************************************************************************
   4  * Copyright (C) 1996-2009, International Business Machines Corporation and    *
   5  * others. All Rights Reserved.                                                *
   6  *******************************************************************************
   7  */
   8 package com.ibm.icu.impl;
   9
  10 import java.util.ArrayList;
  11
  12 import com.ibm.icu.lang.*;
  13 import com.ibm.icu.text.*;
  14 import com.ibm.icu.impl.UCharacterProperty;
  15
  16 public final class Utility {
  17
  18     private static final char APOSTROPHE = '\'';
  19     private static final char BACKSLASH  = '\\';
  20     private static final int MAGIC_UNSIGNED = 0x80000000;
  21
  22     /**
  23      * Convenience utility to compare two Object[]s.
  24      * Ought to be in System
  25      */
  26     public final static boolean arrayEquals(Object[] source, Object target) {
  27         if (source == null) return (target == null);
  28         if (!(target instanceof Object[])) return false;
  29         Object[] targ = (Object[]) target;
  30         return (source.length == targ.length
  31                 && arrayRegionMatches(source, 0, targ, 0, source.length));
  32     }
  33
  34     /**
  35      * Convenience utility to compare two int[]s
  36      * Ought to be in System
  37      */
  38     public final static boolean arrayEquals(int[] source, Object target) {
  39         if (source == null) return (target == null);
  40         if (!(target instanceof int[])) return false;
  41         int[] targ = (int[]) target;
  42         return (source.length == targ.length
  43                 && arrayRegionMatches(source, 0, targ, 0, source.length));
  44     }
  45
  46     /**
  47      * Convenience utility to compare two double[]s
  48      * Ought to be in System
  49      */
  50     public final static boolean arrayEquals(double[] source, Object target) {
  51         if (source == null) return (target == null);
  52         if (!(target instanceof double[])) return false;
  53         double[] targ = (double[]) target;
  54         return (source.length == targ.length
  55                 && arrayRegionMatches(source, 0, targ, 0, source.length));
  56     }
  57     public final static boolean arrayEquals(byte[] source, Object target) {
  58         if (source == null) return (target == null);
  59         if (!(target instanceof byte[])) return false;
  60         byte[] targ = (byte[]) target;
  61         return (source.length == targ.length
  62                 && arrayRegionMatches(source, 0, targ, 0, source.length));
  63     }
  64
  65     /**
  66      * Convenience utility to compare two Object[]s
  67      * Ought to be in System
  68      */
  69     public final static boolean arrayEquals(Object source, Object target) {
  70         if (source == null) return (target == null);
  71         // for some reason, the correct arrayEquals is not being called
  72         // so do it by hand for now.
  73         if (source instanceof Object[])
  74             return(arrayEquals((Object[]) source,target));
  75         if (source instanceof int[])
  76             return(arrayEquals((int[]) source,target));
  77         if (source instanceof double[])
  78             return(arrayEquals((int[]) source,target));
  79         if (source instanceof byte[])
  80             return(arrayEquals((byte[]) source,target));
  81         return source.equals(target);
  82     }
  83
  84     /**
  85      * Convenience utility to compare two Object[]s
  86      * Ought to be in System.
  87      * @param len the length to compare.
  88      * The start indices and start+len must be valid.
  89      */
  90     public final static boolean arrayRegionMatches(Object[] source, int sourceStart,
  91                                             Object[] target, int targetStart,
  92                                             int len)
  93     {
  94         int sourceEnd = sourceStart + len;
  95         int delta = targetStart - sourceStart;
  96         for (int i = sourceStart; i < sourceEnd; i++) {
  97             if (!arrayEquals(source[i],target[i + delta]))
  98             return false;
  99         }
 100         return true;
 101     }
 102
 103     /**
 104      * Convenience utility to compare two Object[]s
 105      * Ought to be in System.
 106      * @param len the length to compare.
 107      * The start indices and start+len must be valid.
 108      */
 109     public final static boolean arrayRegionMatches(char[] source, int sourceStart,
 110                                             char[] target, int targetStart,
 111                                             int len)
 112     {
 113         int sourceEnd = sourceStart + len;
 114         int delta = targetStart - sourceStart;
 115         for (int i = sourceStart; i < sourceEnd; i++) {
 116             if (source[i]!=target[i + delta])
 117             return false;
 118         }
 119         return true;
 120     }
 121
 122     /**
 123      * Convenience utility to compare two int[]s.
 124      * @param len the length to compare.
 125      * The start indices and start+len must be valid.
 126      * Ought to be in System
 127      */
 128     public final static boolean arrayRegionMatches(int[] source, int sourceStart,
 129                                             int[] target, int targetStart,
 130                                             int len)
 131     {
 132         int sourceEnd = sourceStart + len;
 133         int delta = targetStart - sourceStart;
 134         for (int i = sourceStart; i < sourceEnd; i++) {
 135             if (source[i] != target[i + delta])
 136             return false;
 137         }
 138         return true;
 139     }
 140
 141     /**
 142      * Convenience utility to compare two arrays of doubles.
 143      * @param len the length to compare.
 144      * The start indices and start+len must be valid.
 145      * Ought to be in System
 146      */
 147     public final static boolean arrayRegionMatches(double[] source, int sourceStart,
 148                                             double[] target, int targetStart,
 149                                             int len)
 150     {
 151         int sourceEnd = sourceStart + len;
 152         int delta = targetStart - sourceStart;
 153         for (int i = sourceStart; i < sourceEnd; i++) {
 154             if (source[i] != target[i + delta])
 155             return false;
 156         }
 157         return true;
 158     }
 159     public final static boolean arrayRegionMatches(byte[] source, int sourceStart,
 160             byte[] target, int targetStart, int len){
 161         int sourceEnd = sourceStart + len;
 162         int delta = targetStart - sourceStart;
 163         for (int i = sourceStart; i < sourceEnd; i++) {
 164             if (source[i] != target[i + delta])
 165                 return false;
 166             }
 167         return true;
 168     }
 169
 170     /**
 171      * Convenience utility. Does null checks on objects, then calls equals.
 172      */
 173     public final static boolean objectEquals(Object source, Object target) {
 174     if (source == null)
 175             return (target == null);
 176     else
 177             return source.equals(target);
 178     }
 179
 180     /**
 181      * The ESCAPE character is used during run-length encoding.  It signals
 182      * a run of identical chars.
 183      */
 184     private static final char ESCAPE = '\uA5A5';
 185
 186     /**
 187      * The ESCAPE_BYTE character is used during run-length encoding.  It signals
 188      * a run of identical bytes.
 189      */
 190     static final byte ESCAPE_BYTE = (byte)0xA5;
 191
 192     /**
 193      * Construct a string representing an int array.  Use run-length encoding.
 194      * A character represents itself, unless it is the ESCAPE character.  Then
 195      * the following notations are possible:
 196      *   ESCAPE ESCAPE   ESCAPE literal
 197      *   ESCAPE n c      n instances of character c
 198      * Since an encoded run occupies 3 characters, we only encode runs of 4 or
 199      * more characters.  Thus we have n > 0 and n != ESCAPE and n <= 0xFFFF.
 200      * If we encounter a run where n == ESCAPE, we represent this as:
 201      *   c ESCAPE n-1 c
 202      * The ESCAPE value is chosen so as not to collide with commonly
 203      * seen values.
 204      */
 205     static public final String arrayToRLEString(int[] a) {
 206         StringBuffer buffer = new StringBuffer();
 207
 208         appendInt(buffer, a.length);
 209         int runValue = a[0];
 210         int runLength = 1;
 211         for (int i=1; i<a.length; ++i) {
 212             int s = a[i];
 213             if (s == runValue && runLength < 0xFFFF) {
 214                 ++runLength;
 215             } else {
 216                 encodeRun(buffer, runValue, runLength);
 217                 runValue = s;
 218                 runLength = 1;
 219             }
 220         }
 221         encodeRun(buffer, runValue, runLength);
 222         return buffer.toString();
 223     }
 224
 225     /**
 226      * Construct a string representing a short array.  Use run-length encoding.
 227      * A character represents itself, unless it is the ESCAPE character.  Then
 228      * the following notations are possible:
 229      *   ESCAPE ESCAPE   ESCAPE literal
 230      *   ESCAPE n c      n instances of character c
 231      * Since an encoded run occupies 3 characters, we only encode runs of 4 or
 232      * more characters.  Thus we have n > 0 and n != ESCAPE and n <= 0xFFFF.
 233      * If we encounter a run where n == ESCAPE, we represent this as:
 234      *   c ESCAPE n-1 c
 235      * The ESCAPE value is chosen so as not to collide with commonly
 236      * seen values.
 237      */
 238     static public final String arrayToRLEString(short[] a) {
 239         StringBuffer buffer = new StringBuffer();
 240         // for (int i=0; i<a.length; ++i) buffer.append((char) a[i]);
 241         buffer.append((char) (a.length >> 16));
 242         buffer.append((char) a.length);
 243         short runValue = a[0];
 244         int runLength = 1;
 245         for (int i=1; i<a.length; ++i) {
 246             short s = a[i];
 247             if (s == runValue && runLength < 0xFFFF) ++runLength;
 248             else {
 249             encodeRun(buffer, runValue, runLength);
 250             runValue = s;
 251             runLength = 1;
 252             }
 253         }
 254         encodeRun(buffer, runValue, runLength);
 255         return buffer.toString();
 256     }
 257
 258     /**
 259      * Construct a string representing a char array.  Use run-length encoding.
 260      * A character represents itself, unless it is the ESCAPE character.  Then
 261      * the following notations are possible:
 262      *   ESCAPE ESCAPE   ESCAPE literal
 263      *   ESCAPE n c      n instances of character c
 264      * Since an encoded run occupies 3 characters, we only encode runs of 4 or
 265      * more characters.  Thus we have n > 0 and n != ESCAPE and n <= 0xFFFF.
 266      * If we encounter a run where n == ESCAPE, we represent this as:
 267      *   c ESCAPE n-1 c
 268      * The ESCAPE value is chosen so as not to collide with commonly
 269      * seen values.
 270      */
 271     static public final String arrayToRLEString(char[] a) {
 272         StringBuffer buffer = new StringBuffer();
 273         buffer.append((char) (a.length >> 16));
 274         buffer.append((char) a.length);
 275         char runValue = a[0];
 276         int runLength = 1;
 277         for (int i=1; i<a.length; ++i) {
 278             char s = a[i];
 279             if (s == runValue && runLength < 0xFFFF) ++runLength;
 280             else {
 281             encodeRun(buffer, (short)runValue, runLength);
 282             runValue = s;
 283             runLength = 1;
 284             }
 285         }
 286         encodeRun(buffer, (short)runValue, runLength);
 287         return buffer.toString();
 288     }
 289
 290     /**
 291      * Construct a string representing a byte array.  Use run-length encoding.
 292      * Two bytes are packed into a single char, with a single extra zero byte at
 293      * the end if needed.  A byte represents itself, unless it is the
 294      * ESCAPE_BYTE.  Then the following notations are possible:
 295      *   ESCAPE_BYTE ESCAPE_BYTE   ESCAPE_BYTE literal
 296      *   ESCAPE_BYTE n b           n instances of byte b
 297      * Since an encoded run occupies 3 bytes, we only encode runs of 4 or
 298      * more bytes.  Thus we have n > 0 and n != ESCAPE_BYTE and n <= 0xFF.
 299      * If we encounter a run where n == ESCAPE_BYTE, we represent this as:
 300      *   b ESCAPE_BYTE n-1 b
 301      * The ESCAPE_BYTE value is chosen so as not to collide with commonly
 302      * seen values.
 303      */
 304     static public final String arrayToRLEString(byte[] a) {
 305         StringBuffer buffer = new StringBuffer();
 306         buffer.append((char) (a.length >> 16));
 307         buffer.append((char) a.length);
 308         byte runValue = a[0];
 309         int runLength = 1;
 310         byte[] state = new byte[2];
 311         for (int i=1; i<a.length; ++i) {
 312             byte b = a[i];
 313             if (b == runValue && runLength < 0xFF) ++runLength;
 314             else {
 315                 encodeRun(buffer, runValue, runLength, state);
 316                 runValue = b;
 317                 runLength = 1;
 318             }
 319         }
 320         encodeRun(buffer, runValue, runLength, state);
 321
 322         // We must save the final byte, if there is one, by padding
 323         // an extra zero.
 324         if (state[0] != 0) appendEncodedByte(buffer, (byte)0, state);
 325
 326         return buffer.toString();
 327     }
 328
 329     /**
 330      * Encode a run, possibly a degenerate run (of < 4 values).
 331      * @param length The length of the run; must be > 0 && <= 0xFFFF.
 332      */
 333     private static final void encodeRun(StringBuffer buffer, int value, int length) {
 334         if (length < 4) {
 335             for (int j=0; j<length; ++j) {
 336                 if (value == ESCAPE) {
 337                     appendInt(buffer, value);
 338                 }
 339                 appendInt(buffer, value);
 340             }
 341         }
 342         else {
 343             if (length == (int) ESCAPE) {
 344                 if (value == (int) ESCAPE) {
 345                     appendInt(buffer, ESCAPE);
 346                 }
 347                 appendInt(buffer, value);
 348                 --length;
 349             }
 350             appendInt(buffer, ESCAPE);
 351             appendInt(buffer, length);
 352             appendInt(buffer, value); // Don't need to escape this value
 353         }
 354     }
 355
 356     private static final void appendInt(StringBuffer buffer, int value) {
 357         buffer.append((char)(value >>> 16));
 358         buffer.append((char)(value & 0xFFFF));
 359     }
 360
 361     /**
 362      * Encode a run, possibly a degenerate run (of < 4 values).
 363      * @param length The length of the run; must be > 0 && <= 0xFFFF.
 364      */
 365     private static final void encodeRun(StringBuffer buffer, short value, int length) {
 366         if (length < 4) {
 367             for (int j=0; j<length; ++j) {
 368                 if (value == (int) ESCAPE) buffer.append(ESCAPE);
 369                 buffer.append((char) value);
 370             }
 371         }
 372         else {
 373             if (length == (int) ESCAPE) {
 374                 if (value == (int) ESCAPE) buffer.append(ESCAPE);
 375                 buffer.append((char) value);
 376                 --length;
 377             }
 378             buffer.append(ESCAPE);
 379             buffer.append((char) length);
 380             buffer.append((char) value); // Don't need to escape this value
 381         }
 382     }
 383
 384     /**
 385      * Encode a run, possibly a degenerate run (of < 4 values).
 386      * @param length The length of the run; must be > 0 && <= 0xFF.
 387      */
 388     private static final void encodeRun(StringBuffer buffer, byte value, int length,
 389                     byte[] state) {
 390         if (length < 4) {
 391             for (int j=0; j<length; ++j) {
 392                 if (value == ESCAPE_BYTE) appendEncodedByte(buffer, ESCAPE_BYTE, state);
 393                 appendEncodedByte(buffer, value, state);
 394             }
 395         }
 396         else {
 397             if (length == ESCAPE_BYTE) {
 398             if (value == ESCAPE_BYTE) appendEncodedByte(buffer, ESCAPE_BYTE, state);
 399             appendEncodedByte(buffer, value, state);
 400             --length;
 401             }
 402             appendEncodedByte(buffer, ESCAPE_BYTE, state);
 403             appendEncodedByte(buffer, (byte)length, state);
 404             appendEncodedByte(buffer, value, state); // Don't need to escape this value
 405         }
 406     }
 407
 408     /**
 409      * Append a byte to the given StringBuffer, packing two bytes into each
 410      * character.  The state parameter maintains intermediary data between
 411      * calls.
 412      * @param state A two-element array, with state[0] == 0 if this is the
 413      * first byte of a pair, or state[0] != 0 if this is the second byte
 414      * of a pair, in which case state[1] is the first byte.
 415      */
 416     private static final void appendEncodedByte(StringBuffer buffer, byte value,
 417                         byte[] state) {
 418         if (state[0] != 0) {
 419             char c = (char) ((state[1] << 8) | (((int) value) & 0xFF));
 420             buffer.append(c);
 421             state[0] = 0;
 422         }
 423         else {
 424             state[0] = 1;
 425             state[1] = value;
 426         }
 427     }
 428
 429     /**
 430      * Construct an array of ints from a run-length encoded string.
 431      */
 432     static public final int[] RLEStringToIntArray(String s) {
 433         int length = getInt(s, 0);
 434         int[] array = new int[length];
 435         int ai = 0, i = 1;
 436
 437         int maxI = s.length() / 2;
 438         while (ai < length && i < maxI) {
 439             int c = getInt(s, i++);
 440
 441             if (c == ESCAPE) {
 442                 c = getInt(s, i++);
 443                 if (c == ESCAPE) {
 444                     array[ai++] = c;
 445                 } else {
 446                     int runLength = c;
 447                     int runValue = getInt(s, i++);
 448                     for (int j=0; j<runLength; ++j) {
 449                         array[ai++] = runValue;
 450                     }
 451                 }
 452             }
 453             else {
 454                 array[ai++] = c;
 455             }
 456         }
 457
 458         if (ai != length || i != maxI) {
 459             throw new IllegalStateException("Bad run-length encoded int array");
 460         }
 461
 462         return array;
 463     }
 464     static final int getInt(String s, int i) {
 465         return (((int) s.charAt(2*i)) << 16) | (int) s.charAt(2*i+1);
 466     }
 467
 468     /**
 469      * Construct an array of shorts from a run-length encoded string.
 470      */
 471     static public final short[] RLEStringToShortArray(String s) {
 472         int length = (((int) s.charAt(0)) << 16) | ((int) s.charAt(1));
 473         short[] array = new short[length];
 474         int ai = 0;
 475         for (int i=2; i<s.length(); ++i) {
 476             char c = s.charAt(i);
 477             if (c == ESCAPE) {
 478                 c = s.charAt(++i);
 479                 if (c == ESCAPE) {
 480                     array[ai++] = (short) c;
 481                 } else {
 482                     int runLength = (int) c;
 483                     short runValue = (short) s.charAt(++i);
 484                     for (int j=0; j<runLength; ++j) array[ai++] = runValue;
 485                 }
 486             }
 487             else {
 488                 array[ai++] = (short) c;
 489             }
 490         }
 491
 492         if (ai != length)
 493             throw new IllegalStateException("Bad run-length encoded short array");
 494
 495         return array;
 496     }
 497
 498     /**
 499      * Construct an array of shorts from a run-length encoded string.
 500      */
 501     static public final char[] RLEStringToCharArray(String s) {
 502         int length = (((int) s.charAt(0)) << 16) | ((int) s.charAt(1));
 503         char[] array = new char[length];
 504         int ai = 0;
 505         for (int i=2; i<s.length(); ++i) {
 506             char c = s.charAt(i);
 507             if (c == ESCAPE) {
 508                 c = s.charAt(++i);
 509                 if (c == ESCAPE) {
 510                     array[ai++] = c;
 511                 } else {
 512                     int runLength = (int) c;
 513                     char runValue = s.charAt(++i);
 514                     for (int j=0; j<runLength; ++j) array[ai++] = runValue;
 515                 }
 516             }
 517             else {
 518                 array[ai++] = c;
 519             }
 520         }
 521
 522         if (ai != length)
 523             throw new IllegalStateException("Bad run-length encoded short array");
 524
 525         return array;
 526     }
 527
 528     /**
 529      * Construct an array of bytes from a run-length encoded string.
 530      */
 531     static public final byte[] RLEStringToByteArray(String s) {
 532         int length = (((int) s.charAt(0)) << 16) | ((int) s.charAt(1));
 533         byte[] array = new byte[length];
 534         boolean nextChar = true;
 535         char c = 0;
 536         int node = 0;
 537         int runLength = 0;
 538         int i = 2;
 539         for (int ai=0; ai<length; ) {
 540             // This part of the loop places the next byte into the local
 541             // variable 'b' each time through the loop.  It keeps the
 542             // current character in 'c' and uses the boolean 'nextChar'
 543             // to see if we've taken both bytes out of 'c' yet.
 544             byte b;
 545             if (nextChar) {
 546                 c = s.charAt(i++);
 547                 b = (byte) (c >> 8);
 548                 nextChar = false;
 549             }
 550             else {
 551                 b = (byte) (c & 0xFF);
 552                 nextChar = true;
 553             }
 554
 555             // This part of the loop is a tiny state machine which handles
 556             // the parsing of the run-length encoding.  This would be simpler
 557             // if we could look ahead, but we can't, so we use 'node' to
 558             // move between three nodes in the state machine.
 559             switch (node) {
 560             case 0:
 561                 // Normal idle node
 562                 if (b == ESCAPE_BYTE) {
 563                     node = 1;
 564                 }
 565                 else {
 566                     array[ai++] = b;
 567                 }
 568                 break;
 569             case 1:
 570                 // We have seen one ESCAPE_BYTE; we expect either a second
 571                 // one, or a run length and value.
 572                 if (b == ESCAPE_BYTE) {
 573                     array[ai++] = ESCAPE_BYTE;
 574                     node = 0;
 575                 }
 576                 else {
 577                     runLength = b;
 578                     // Interpret signed byte as unsigned
 579                     if (runLength < 0) runLength += 0x100;
 580                     node = 2;
 581                 }
 582                 break;
 583             case 2:
 584                 // We have seen an ESCAPE_BYTE and length byte.  We interpret
 585                 // the next byte as the value to be repeated.
 586                 for (int j=0; j<runLength; ++j) array[ai++] = b;
 587                 node = 0;
 588                 break;
 589             }
 590         }
 591
 592         if (node != 0)
 593             throw new IllegalStateException("Bad run-length encoded byte array");
 594
 595         if (i != s.length())
 596             throw new IllegalStateException("Excess data in RLE byte array string");
 597
 598         return array;
 599     }
 600
 601     static public String LINE_SEPARATOR = System.getProperty("line.separator");
 602
 603     /**
 604      * Format a String for representation in a source file.  This includes
 605      * breaking it into lines and escaping characters using octal notation
 606      * when necessary (control characters and double quotes).
 607      */
 608     static public final String formatForSource(String s) {
 609         StringBuffer buffer = new StringBuffer();
 610         for (int i=0; i<s.length();) {
 611             if (i > 0) buffer.append('+').append(LINE_SEPARATOR);
 612             buffer.append("        \"");
 613             int count = 11;
 614             while (i<s.length() && count<80) {
 615                 char c = s.charAt(i++);
 616                 if (c < '\u0020' || c == '"' || c == '\\') {
 617                     if (c == '\n') {
 618                         buffer.append("\\n");
 619                         count += 2;
 620                     } else if (c == '\t') {
 621                         buffer.append("\\t");
 622                         count += 2;
 623                     } else if (c == '\r') {
 624                         buffer.append("\\r");
 625                         count += 2;
 626                     } else {
 627                         // Represent control characters, backslash and double quote
 628                         // using octal notation; otherwise the string we form
 629                         // won't compile, since Unicode escape sequences are
 630                         // processed before tokenization.
 631                         buffer.append('\\');
 632                         buffer.append(HEX_DIGIT[(c & 0700) >> 6]); // HEX_DIGIT works for octal
 633                         buffer.append(HEX_DIGIT[(c & 0070) >> 3]);
 634                         buffer.append(HEX_DIGIT[(c & 0007)]);
 635                         count += 4;
 636                     }
 637                 }
 638                 else if (c <= '\u007E') {
 639                     buffer.append(c);
 640                     count += 1;
 641                 }
 642                 else {
 643                     buffer.append("\\u");
 644                     buffer.append(HEX_DIGIT[(c & 0xF000) >> 12]);
 645                     buffer.append(HEX_DIGIT[(c & 0x0F00) >> 8]);
 646                     buffer.append(HEX_DIGIT[(c & 0x00F0) >> 4]);
 647                     buffer.append(HEX_DIGIT[(c & 0x000F)]);
 648                     count += 6;
 649                 }
 650             }
 651             buffer.append('"');
 652         }
 653         return buffer.toString();
 654     }
 655
 656     static final char[] HEX_DIGIT = {'0','1','2','3','4','5','6','7',
 657                      '8','9','A','B','C','D','E','F'};
 658
 659     /**
 660      * Format a String for representation in a source file.  Like
 661      * formatForSource but does not do line breaking.
 662      */
 663     static public final String format1ForSource(String s) {
 664         StringBuffer buffer = new StringBuffer();
 665         buffer.append("\"");
 666         for (int i=0; i<s.length();) {
 667             char c = s.charAt(i++);
 668             if (c < '\u0020' || c == '"' || c == '\\') {
 669                 if (c == '\n') {
 670                     buffer.append("\\n");
 671                 } else if (c == '\t') {
 672                     buffer.append("\\t");
 673                 } else if (c == '\r') {
 674                     buffer.append("\\r");
 675                 } else {
 676                     // Represent control characters, backslash and double quote
 677                     // using octal notation; otherwise the string we form
 678                     // won't compile, since Unicode escape sequences are
 679                     // processed before tokenization.
 680                     buffer.append('\\');
 681                     buffer.append(HEX_DIGIT[(c & 0700) >> 6]); // HEX_DIGIT works for octal
 682                     buffer.append(HEX_DIGIT[(c & 0070) >> 3]);
 683                     buffer.append(HEX_DIGIT[(c & 0007)]);
 684                 }
 685             }
 686             else if (c <= '\u007E') {
 687                 buffer.append(c);
 688             }
 689             else {
 690                 buffer.append("\\u");
 691                 buffer.append(HEX_DIGIT[(c & 0xF000) >> 12]);
 692                 buffer.append(HEX_DIGIT[(c & 0x0F00) >> 8]);
 693                 buffer.append(HEX_DIGIT[(c & 0x00F0) >> 4]);
 694                 buffer.append(HEX_DIGIT[(c & 0x000F)]);
 695             }
 696         }
 697         buffer.append('"');
 698         return buffer.toString();
 699     }
 700
 701     /**
 702      * Convert characters outside the range U+0020 to U+007F to
 703      * Unicode escapes, and convert backslash to a double backslash.
 704      */
 705     public static final String escape(String s) {
 706         StringBuffer buf = new StringBuffer();
 707         for (int i=0; i<s.length(); ) {
 708             int c = UTF16.charAt(s, i);
 709             i += UTF16.getCharCount(c);
 710             if (c >= ' ' && c <= 0x007F) {
 711                 if (c == '\\') {
 712                     buf.append("\\\\"); // That is, "\\"
 713                 } else {
 714                     buf.append((char)c);
 715                 }
 716             } else {
 717                 boolean four = c <= 0xFFFF;
 718                 buf.append(four ? "\\u" : "\\U");
 719                 hex(c, four ? 4 : 8, buf);
 720             }
 721         }
 722         return buf.toString();
 723     }
 724
 725     /* This map must be in ASCENDING ORDER OF THE ESCAPE CODE */
 726     static private final char[] UNESCAPE_MAP = {
 727         /*"   0x22, 0x22 */
 728         /*'   0x27, 0x27 */
 729         /*?   0x3F, 0x3F */
 730         /*\   0x5C, 0x5C */
 731         /*a*/ 0x61, 0x07,
 732         /*b*/ 0x62, 0x08,
 733         /*e*/ 0x65, 0x1b,
 734         /*f*/ 0x66, 0x0c,
 735         /*n*/ 0x6E, 0x0a,
 736         /*r*/ 0x72, 0x0d,
 737         /*t*/ 0x74, 0x09,
 738         /*v*/ 0x76, 0x0b
 739     };
 740
 741     /**
 742      * Convert an escape to a 32-bit code point value.  We attempt
 743      * to parallel the icu4c unescapeAt() function.
 744      * @param offset16 an array containing offset to the character
 745      * <em>after</em> the backslash.  Upon return offset16[0] will
 746      * be updated to point after the escape sequence.
 747      * @return character value from 0 to 10FFFF, or -1 on error.
 748      */
 749     public static int unescapeAt(String s, int[] offset16) {
 750         int c;
 751         int result = 0;
 752         int n = 0;
 753         int minDig = 0;
 754         int maxDig = 0;
 755         int bitsPerDigit = 4;
 756         int dig;
 757         int i;
 758         boolean braces = false;
 759
 760         /* Check that offset is in range */
 761         int offset = offset16[0];
 762         int length = s.length();
 763         if (offset < 0 || offset >= length) {
 764             return -1;
 765         }
 766
 767         /* Fetch first UChar after '\\' */
 768         c = UTF16.charAt(s, offset);
 769         offset += UTF16.getCharCount(c);
 770
 771         /* Convert hexadecimal and octal escapes */
 772         switch (c) {
 773         case 'u':
 774             minDig = maxDig = 4;
 775             break;
 776         case 'U':
 777             minDig = maxDig = 8;
 778             break;
 779         case 'x':
 780             minDig = 1;
 781             if (offset < length && UTF16.charAt(s, offset) == 0x7B /*{*/) {
 782                 ++offset;
 783                 braces = true;
 784                 maxDig = 8;
 785             } else {
 786                 maxDig = 2;
 787             }
 788             break;
 789         default:
 790             dig = UCharacter.digit(c, 8);
 791             if (dig >= 0) {
 792                 minDig = 1;
 793                 maxDig = 3;
 794                 n = 1; /* Already have first octal digit */
 795                 bitsPerDigit = 3;
 796                 result = dig;
 797             }
 798             break;
 799         }
 800         if (minDig != 0) {
 801             while (offset < length && n < maxDig) {
 802                 c = UTF16.charAt(s, offset);
 803                 dig = UCharacter.digit(c, (bitsPerDigit == 3) ? 8 : 16);
 804                 if (dig < 0) {
 805                     break;
 806                 }
 807                 result = (result << bitsPerDigit) | dig;
 808                 offset += UTF16.getCharCount(c);
 809                 ++n;
 810             }
 811             if (n < minDig) {
 812                 return -1;
 813             }
 814             if (braces) {
 815                 if (c != 0x7D /*}*/) {
 816                     return -1;
 817                 }
 818                 ++offset;
 819             }
 820             if (result < 0 || result >= 0x110000) {
 821                 return -1;
 822             }
 823             // If an escape sequence specifies a lead surrogate, see
 824             // if there is a trail surrogate after it, either as an
 825             // escape or as a literal.  If so, join them up into a
 826             // supplementary.
 827             if (offset < length &&
 828                 UTF16.isLeadSurrogate((char) result)) {
 829                 int ahead = offset+1;
 830                 c = s.charAt(offset); // [sic] get 16-bit code unit
 831                 if (c == '\\' && ahead < length) {
 832                     int o[] = new int[] { ahead };
 833                     c = unescapeAt(s, o);
 834                     ahead = o[0];
 835                 }
 836                 if (UTF16.isTrailSurrogate((char) c)) {
 837                     offset = ahead;
 838                 result = UCharacterProperty.getRawSupplementary(
 839                                   (char) result, (char) c);
 840                 }
 841             }
 842             offset16[0] = offset;
 843             return result;
 844         }
 845
 846         /* Convert C-style escapes in table */
 847         for (i=0; i<UNESCAPE_MAP.length; i+=2) {
 848             if (c == UNESCAPE_MAP[i]) {
 849                 offset16[0] = offset;
 850                 return UNESCAPE_MAP[i+1];
 851             } else if (c < UNESCAPE_MAP[i]) {
 852                 break;
 853             }
 854         }
 855
 856         /* Map \cX to control-X: X & 0x1F */
 857         if (c == 'c' && offset < length) {
 858             c = UTF16.charAt(s, offset);
 859             offset16[0] = offset + UTF16.getCharCount(c);
 860             return 0x1F & c;
 861         }
 862
 863         /* If no special forms are recognized, then consider
 864          * the backslash to generically escape the next character. */
 865         offset16[0] = offset;
 866         return c;
 867     }
 868
 869     /**
 870      * Convert all escapes in a given string using unescapeAt().
 871      * @exception IllegalArgumentException if an invalid escape is
 872      * seen.
 873      */
 874     public static String unescape(String s) {
 875         StringBuffer buf = new StringBuffer();
 876         int[] pos = new int[1];
 877         for (int i=0; i<s.length(); ) {
 878             char c = s.charAt(i++);
 879             if (c == '\\') {
 880                 pos[0] = i;
 881                 int e = unescapeAt(s, pos);
 882                 if (e < 0) {
 883                     throw new IllegalArgumentException("Invalid escape sequence " +
 884                                                        s.substring(i-1, Math.min(i+8, s.length())));
 885                 }
 886                 UTF16.append(buf, e);
 887                 i = pos[0];
 888             } else {
 889                 buf.append(c);
 890             }
 891         }
 892         return buf.toString();
 893     }
 894
 895     /**
 896      * Convert all escapes in a given string using unescapeAt().
 897      * Leave invalid escape sequences unchanged.
 898      */
 899     public static String unescapeLeniently(String s) {
 900         StringBuffer buf = new StringBuffer();
 901         int[] pos = new int[1];
 902         for (int i=0; i<s.length(); ) {
 903             char c = s.charAt(i++);
 904             if (c == '\\') {
 905                 pos[0] = i;
 906                 int e = unescapeAt(s, pos);
 907                 if (e < 0) {
 908                     buf.append(c);
 909                 } else {
 910                     UTF16.append(buf, e);
 911                     i = pos[0];
 912                 }
 913             } else {
 914                 buf.append(c);
 915             }
 916         }
 917         return buf.toString();
 918     }
 919
 920     /**
 921      * Convert a char to 4 hex uppercase digits.  E.g., hex('a') =>
 922      * "0041".
 923      */
 924     public static String hex(char ch) {
 925         StringBuffer temp = new StringBuffer();
 926         return hex(ch, temp).toString();
 927     }
 928
 929     /**
 930      * Convert a string to comma-separated groups of 4 hex uppercase
 931      * digits.  E.g., hex('ab') => "0041,0042".
 932      */
 933     public static String hex(String s) {
 934         StringBuffer temp = new StringBuffer();
 935         return hex(s, temp).toString();
 936     }
 937
 938     /**
 939      * Convert a string to comma-separated groups of 4 hex uppercase
 940      * digits.  E.g., hex('ab') => "0041,0042".
 941      */
 942     public static String hex(StringBuffer s) {
 943         return hex(s.toString());
 944     }
 945
 946     /**
 947      * Convert a char to 4 hex uppercase digits.  E.g., hex('a') =>
 948      * "0041".  Append the output to the given StringBuffer.
 949      */
 950     public static StringBuffer hex(char ch, StringBuffer output) {
 951         return appendNumber(output, ch, 16, 4);
 952     }
 953
 954     /**
 955      * Convert a integer to size width hex uppercase digits.
 956      * E.g., hex('a', 4, str) => "0041".
 957      * Append the output to the given StringBuffer.
 958      * If width is too small to fit, nothing will be appended to output.
 959      */
 960     public static StringBuffer hex(int ch, int width, StringBuffer output) {
 961         return appendNumber(output, ch, 16, width);
 962     }
 963
 964     /**
 965      * Convert a integer to size width (minimum) hex uppercase digits.
 966      * E.g., hex('a', 4, str) => "0041".  If the integer requires more
 967      * than width digits, more will be used.
 968      */
 969     public static String hex(int ch, int width) {
 970         StringBuffer buf = new StringBuffer();
 971         return appendNumber(buf, ch, 16, width).toString();
 972     }
 973     /**
 974      * Supplies a zero-padded hex representation of an integer (without 0x)
 975      */
 976     static public String hex(long i, int places) {
 977         if (i == Long.MIN_VALUE) return "-8000000000000000";
 978         boolean negative = i < 0;
 979         if (negative) {
 980             i = -i;
 981         }
 982         String result = Long.toString(i, 16).toUpperCase();
 983         if (result.length() < places) {
 984             result = "0000000000000000".substring(result.length(),places) + result;
 985         }
 986         if (negative) {
 987             return '-' + result;
 988         }
 989         return result;
 990     }
 991
 992     public static String hex(long ch) {
 993         return hex(ch,4);
 994     }
 995
 996     /**
 997      * Convert a string to comma-separated groups of 4 hex uppercase
 998      * digits.  E.g., hex('ab') => "0041,0042".  Append the output
 999      * to the given StringBuffer.
1000      */
1001     public static StringBuffer hex(String s, StringBuffer result) {
1002         for (int i = 0; i < s.length(); ++i) {
1003             if (i != 0) result.append(',');
1004             hex(s.charAt(i), result);
1005         }
1006         return result;
1007     }
1008
1009     /**
1010      * Split a string into pieces based on the given divider character
1011      * @param s the string to split
1012      * @param divider the character on which to split.  Occurrences of
1013      * this character are not included in the output
1014      * @param output an array to receive the substrings between
1015      * instances of divider.  It must be large enough on entry to
1016      * accomodate all output.  Adjacent instances of the divider
1017      * character will place empty strings into output.  Before
1018      * returning, output is padded out with empty strings.
1019      */
1020     public static void split(String s, char divider, String[] output) {
1021         int last = 0;
1022         int current = 0;
1023         int i;
1024         for (i = 0; i < s.length(); ++i) {
1025             if (s.charAt(i) == divider) {
1026                 output[current++] = s.substring(last,i);
1027                 last = i+1;
1028             }
1029         }
1030         output[current++] = s.substring(last,i);
1031         while (current < output.length) {
1032             output[current++] = "";
1033         }
1034     }
1035
1036     /**
1037      * Split a string into pieces based on the given divider character
1038      * @param s the string to split
1039      * @param divider the character on which to split.  Occurrences of
1040      * this character are not included in the output
1041      * @return output an array to receive the substrings between
1042      * instances of divider. Adjacent instances of the divider
1043      * character will place empty strings into output.
1044      */
1045     public static String[] split(String s, char divider) {
1046         int last = 0;
1047         int i;
1048         ArrayList output = new ArrayList();
1049         for (i = 0; i < s.length(); ++i) {
1050             if (s.charAt(i) == divider) {
1051                 output.add(s.substring(last,i));
1052                 last = i+1;
1053             }
1054         }
1055         output.add( s.substring(last,i));
1056         return (String[]) output.toArray(new String[output.size()]);
1057     }
1058
1059     /**
1060      * Look up a given string in a string array.  Returns the index at
1061      * which the first occurrence of the string was found in the
1062      * array, or -1 if it was not found.
1063      * @param source the string to search for
1064      * @param target the array of zero or more strings in which to
1065      * look for source
1066      * @return the index of target at which source first occurs, or -1
1067      * if not found
1068      */
1069     public static int lookup(String source, String[] target) {
1070         for (int i = 0; i < target.length; ++i) {
1071             if (source.equals(target[i])) return i;
1072         }
1073         return -1;
1074     }
1075
1076     /**
1077      * Skip over a sequence of zero or more white space characters
1078      * at pos.  Return the index of the first non-white-space character
1079      * at or after pos, or str.length(), if there is none.
1080      */
1081     public static int skipWhitespace(String str, int pos) {
1082         while (pos < str.length()) {
1083             int c = UTF16.charAt(str, pos);
1084             if (!UCharacterProperty.isRuleWhiteSpace(c)) {
1085                 break;
1086             }
1087             pos += UTF16.getCharCount(c);
1088         }
1089         return pos;
1090     }
1091
1092     /**
1093      * Skip over a sequence of zero or more white space characters
1094      * at pos[0], advancing it.
1095      */
1096     public static void skipWhitespace(String str, int[] pos) {
1097         pos[0] = skipWhitespace(str, pos[0]);
1098     }
1099
1100     /**
1101      * Remove all rule white space from a string.
1102      */
1103     public static String deleteRuleWhiteSpace(String str) {
1104         StringBuffer buf = new StringBuffer();
1105         for (int i=0; i<str.length(); ) {
1106             int ch = UTF16.charAt(str, i);
1107             i += UTF16.getCharCount(ch);
1108             if (UCharacterProperty.isRuleWhiteSpace(ch)) {
1109                 continue;
1110             }
1111             UTF16.append(buf, ch);
1112         }
1113         return buf.toString();
1114     }
1115
1116     /**
1117      * Parse a single non-whitespace character 'ch', optionally
1118      * preceded by whitespace.
1119      * @param id the string to be parsed
1120      * @param pos INPUT-OUTPUT parameter.  On input, pos[0] is the
1121      * offset of the first character to be parsed.  On output, pos[0]
1122      * is the index after the last parsed character.  If the parse
1123      * fails, pos[0] will be unchanged.
1124      * @param ch the non-whitespace character to be parsed.
1125      * @return true if 'ch' is seen preceded by zero or more
1126      * whitespace characters.
1127      */
1128     public static boolean parseChar(String id, int[] pos, char ch) {
1129         int start = pos[0];
1130         skipWhitespace(id, pos);
1131         if (pos[0] == id.length() ||
1132             id.charAt(pos[0]) != ch) {
1133             pos[0] = start;
1134             return false;
1135         }
1136         ++pos[0];
1137         return true;
1138     }
1139
1140     /**
1141      * Parse a pattern string starting at offset pos.  Keywords are
1142      * matched case-insensitively.  Spaces may be skipped and may be
1143      * optional or required.  Integer values may be parsed, and if
1144      * they are, they will be returned in the given array.  If
1145      * successful, the offset of the next non-space character is
1146      * returned.  On failure, -1 is returned.
1147      * @param pattern must only contain lowercase characters, which
1148      * will match their uppercase equivalents as well.  A space
1149      * character matches one or more required spaces.  A '~' character
1150      * matches zero or more optional spaces.  A '#' character matches
1151      * an integer and stores it in parsedInts, which the caller must
1152      * ensure has enough capacity.
1153      * @param parsedInts array to receive parsed integers.  Caller
1154      * must ensure that parsedInts.length is >= the number of '#'
1155      * signs in 'pattern'.
1156      * @return the position after the last character parsed, or -1 if
1157      * the parse failed
1158      */
1159     public static int parsePattern(String rule, int pos, int limit,
1160                                    String pattern, int[] parsedInts) {
1161         // TODO Update this to handle surrogates
1162         int[] p = new int[1];
1163         int intCount = 0; // number of integers parsed
1164         for (int i=0; i<pattern.length(); ++i) {
1165             char cpat = pattern.charAt(i);
1166             char c;
1167             switch (cpat) {
1168             case ' ':
1169                 if (pos >= limit) {
1170                     return -1;
1171                 }
1172                 c = rule.charAt(pos++);
1173                 if (!UCharacterProperty.isRuleWhiteSpace(c)) {
1174                     return -1;
1175                 }
1176                 // FALL THROUGH to skipWhitespace
1177             case '~':
1178                 pos = skipWhitespace(rule, pos);
1179                 break;
1180             case '#':
1181                 p[0] = pos;
1182                 parsedInts[intCount++] = parseInteger(rule, p, limit);
1183                 if (p[0] == pos) {
1184                     // Syntax error; failed to parse integer
1185                     return -1;
1186                 }
1187                 pos = p[0];
1188                 break;
1189             default:
1190                 if (pos >= limit) {
1191                     return -1;
1192                 }
1193                 c = (char) UCharacter.toLowerCase(rule.charAt(pos++));
1194                 if (c != cpat) {
1195                     return -1;
1196                 }
1197                 break;
1198             }
1199         }
1200         return pos;
1201     }
1202
1203     /**
1204      * Parse a pattern string within the given Replaceable and a parsing
1205      * pattern.  Characters are matched literally and case-sensitively
1206      * except for the following special characters:
1207      *
1208      * ~  zero or more uprv_isRuleWhiteSpace chars
1209      *
1210      * If end of pattern is reached with all matches along the way,
1211      * pos is advanced to the first unparsed index and returned.
1212      * Otherwise -1 is returned.
1213      * @param pat pattern that controls parsing
1214      * @param text text to be parsed, starting at index
1215      * @param index offset to first character to parse
1216      * @param limit offset after last character to parse
1217      * @return index after last parsed character, or -1 on parse failure.
1218      */
1219     public static int parsePattern(String pat,
1220                                    Replaceable text,
1221                                    int index,
1222                                    int limit) {
1223         int ipat = 0;
1224
1225         // empty pattern matches immediately
1226         if (ipat == pat.length()) {
1227             return index;
1228         }
1229
1230         int cpat = UTF16.charAt(pat, ipat);
1231
1232         while (index < limit) {
1233             int c = text.char32At(index);
1234
1235             // parse \s*
1236             if (cpat == '~') {
1237                 if (UCharacterProperty.isRuleWhiteSpace(c)) {
1238                     index += UTF16.getCharCount(c);
1239                     continue;
1240                 } else {
1241                     if (++ipat == pat.length()) {
1242                         return index; // success; c unparsed
1243                     }
1244                     // fall thru; process c again with next cpat
1245                 }
1246             }
1247
1248             // parse literal
1249             else if (c == cpat) {
1250                 int n = UTF16.getCharCount(c);
1251                 index += n;
1252                 ipat += n;
1253                 if (ipat == pat.length()) {
1254                     return index; // success; c parsed
1255                 }
1256                 // fall thru; get next cpat
1257             }
1258
1259             // match failure of literal
1260             else {
1261                 return -1;
1262             }
1263
1264             cpat = UTF16.charAt(pat, ipat);
1265         }
1266
1267         return -1; // text ended before end of pat
1268     }
1269
1270     /**
1271      * Parse an integer at pos, either of the form \d+ or of the form
1272      * 0x[0-9A-Fa-f]+ or 0[0-7]+, that is, in standard decimal, hex,
1273      * or octal format.
1274      * @param pos INPUT-OUTPUT parameter.  On input, the first
1275      * character to parse.  On output, the character after the last
1276      * parsed character.
1277      */
1278     public static int parseInteger(String rule, int[] pos, int limit) {
1279         int count = 0;
1280         int value = 0;
1281         int p = pos[0];
1282         int radix = 10;
1283
1284         if (rule.regionMatches(true, p, "0x", 0, 2)) {
1285             p += 2;
1286             radix = 16;
1287         } else if (p < limit && rule.charAt(p) == '0') {
1288             p++;
1289             count = 1;
1290             radix = 8;
1291         }
1292
1293         while (p < limit) {
1294             int d = UCharacter.digit(rule.charAt(p++), radix);
1295             if (d < 0) {
1296                 --p;
1297                 break;
1298             }
1299             ++count;
1300             int v = (value * radix) + d;
1301             if (v <= value) {
1302                 // If there are too many input digits, at some point
1303                 // the value will go negative, e.g., if we have seen
1304                 // "0x8000000" already and there is another '0', when
1305                 // we parse the next 0 the value will go negative.
1306                 return 0;
1307             }
1308             value = v;
1309         }
1310         if (count > 0) {
1311             pos[0] = p;
1312         }
1313         return value;
1314     }
1315
1316     /**
1317      * Parse a Unicode identifier from the given string at the given
1318      * position.  Return the identifier, or null if there is no
1319      * identifier.
1320      * @param str the string to parse
1321      * @param pos INPUT-OUPUT parameter.  On INPUT, pos[0] is the
1322      * first character to examine.  It must be less than str.length(),
1323      * and it must not point to a whitespace character.  That is, must
1324      * have pos[0] < str.length() and
1325      * !UCharacterProperty.isRuleWhiteSpace(UTF16.charAt(str, pos[0])).  On
1326      * OUTPUT, the position after the last parsed character.
1327      * @return the Unicode identifier, or null if there is no valid
1328      * identifier at pos[0].
1329      */
1330     public static String parseUnicodeIdentifier(String str, int[] pos) {
1331         // assert(pos[0] < str.length());
1332         // assert(!UCharacterProperty.isRuleWhiteSpace(UTF16.charAt(str, pos[0])));
1333         StringBuffer buf = new StringBuffer();
1334         int p = pos[0];
1335         while (p < str.length()) {
1336             int ch = UTF16.charAt(str, p);
1337             if (buf.length() == 0) {
1338                 if (UCharacter.isUnicodeIdentifierStart(ch)) {
1339                     UTF16.append(buf, ch);
1340                 } else {
1341                     return null;
1342                 }
1343             } else {
1344                 if (UCharacter.isUnicodeIdentifierPart(ch)) {
1345                     UTF16.append(buf, ch);
1346                 } else {
1347                     break;
1348                 }
1349             }
1350             p += UTF16.getCharCount(ch);
1351         }
1352         pos[0] = p;
1353         return buf.toString();
1354     }
1355
1356     /**
1357      * Trim whitespace from ends of a StringBuffer.
1358      */
1359     public static StringBuffer trim(StringBuffer b) {
1360         // TODO update to handle surrogates
1361         int i;
1362         for (i=0; i<b.length() && UCharacter.isWhitespace(b.charAt(i)); ++i) {}
1363         b.delete(0, i);
1364         for (i=b.length()-1; i>=0 && UCharacter.isWhitespace(b.charAt(i)); --i) {}
1365         return b.delete(i+1, b.length());
1366     }
1367
1368     static final char DIGITS[] = {
1369         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
1370         'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
1371         'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
1372         'U', 'V', 'W', 'X', 'Y', 'Z'
1373     };
1374
1375     /**
1376      * Append a number to the given StringBuffer in the radix 10
1377      * generating at least one digit.
1378      */
1379     public static StringBuffer appendNumber(StringBuffer result, int n) {
1380         return appendNumber(result, n, 10, 1);
1381     }
1382
1383     /**
1384      * Append the digits of a positive integer to the given
1385      * <code>StringBuffer</code> in the given radix. This is
1386      * done recursively since it is easiest to generate the low-
1387      * order digit first, but it must be appended last.
1388      *
1389      * @param result is the <code>StringBuffer</code> to append to
1390      * @param n is the positive integer
1391      * @param radix is the radix, from 2 to 36 inclusive
1392      * @param minDigits is the minimum number of digits to append.
1393      */
1394     private static void recursiveAppendNumber(StringBuffer result, int n,
1395                                                 int radix, int minDigits)
1396     {
1397         int digit = n % radix;
1398
1399         if (n >= radix || minDigits > 1) {
1400             recursiveAppendNumber(result, n / radix, radix, minDigits - 1);
1401         }
1402
1403         result.append(DIGITS[digit]);
1404     }
1405
1406     /**
1407      * Append a number to the given StringBuffer in the given radix.
1408      * Standard digits '0'-'9' are used and letters 'A'-'Z' for
1409      * radices 11 through 36.
1410      * @param result the digits of the number are appended here
1411      * @param n the number to be converted to digits; may be negative.
1412      * If negative, a '-' is prepended to the digits.
1413      * @param radix a radix from 2 to 36 inclusive.
1414      * @param minDigits the minimum number of digits, not including
1415      * any '-', to produce.  Values less than 2 have no effect.  One
1416      * digit is always emitted regardless of this parameter.
1417      * @return a reference to result
1418      */
1419     public static StringBuffer appendNumber(StringBuffer result, int n,
1420                                              int radix, int minDigits)
1421         throws IllegalArgumentException
1422     {
1423         if (radix < 2 || radix > 36) {
1424             throw new IllegalArgumentException("Illegal radix " + radix);
1425         }
1426
1427
1428         int abs = n;
1429
1430         if (n < 0) {
1431             abs = -n;
1432             result.append("-");
1433         }
1434
1435         recursiveAppendNumber(result, abs, radix, minDigits);
1436
1437         return result;
1438     }
1439
1440     /**
1441      * Parse an unsigned 31-bit integer at the given offset.  Use
1442      * UCharacter.digit() to parse individual characters into digits.
1443      * @param text the text to be parsed
1444      * @param pos INPUT-OUTPUT parameter.  On entry, pos[0] is the
1445      * offset within text at which to start parsing; it should point
1446      * to a valid digit.  On exit, pos[0] is the offset after the last
1447      * parsed character.  If the parse failed, it will be unchanged on
1448      * exit.  Must be >= 0 on entry.
1449      * @param radix the radix in which to parse; must be >= 2 and <=
1450      * 36.
1451      * @return a non-negative parsed number, or -1 upon parse failure.
1452      * Parse fails if there are no digits, that is, if pos[0] does not
1453      * point to a valid digit on entry, or if the number to be parsed
1454      * does not fit into a 31-bit unsigned integer.
1455      */
1456     public static int parseNumber(String text, int[] pos, int radix) {
1457         // assert(pos[0] >= 0);
1458         // assert(radix >= 2);
1459         // assert(radix <= 36);
1460         int n = 0;
1461         int p = pos[0];
1462         while (p < text.length()) {
1463             int ch = UTF16.charAt(text, p);
1464             int d = UCharacter.digit(ch, radix);
1465             if (d < 0) {
1466                 break;
1467             }
1468             n = radix*n + d;
1469             // ASSUME that when a 32-bit integer overflows it becomes
1470             // negative.  E.g., 214748364 * 10 + 8 => negative value.
1471             if (n < 0) {
1472                 return -1;
1473             }
1474             ++p;
1475         }
1476         if (p == pos[0]) {
1477             return -1;
1478         }
1479         pos[0] = p;
1480         return n;
1481     }
1482
1483     /**
1484      * Return true if the character is NOT printable ASCII.  The tab,
1485      * newline and linefeed characters are considered unprintable.
1486      */
1487     public static boolean isUnprintable(int c) {
1488         return !(c >= 0x20 && c <= 0x7E);
1489     }
1490
1491     /**
1492      * Escape unprintable characters using <backslash>uxxxx notation
1493      * for U+0000 to U+FFFF and <backslash>Uxxxxxxxx for U+10000 and
1494      * above.  If the character is printable ASCII, then do nothing
1495      * and return FALSE.  Otherwise, append the escaped notation and
1496      * return TRUE.
1497      */
1498     public static boolean escapeUnprintable(StringBuffer result, int c) {
1499         if (isUnprintable(c)) {
1500             result.append('\\');
1501             if ((c & ~0xFFFF) != 0) {
1502                 result.append('U');
1503                 result.append(DIGITS[0xF&(c>>28)]);
1504                 result.append(DIGITS[0xF&(c>>24)]);
1505                 result.append(DIGITS[0xF&(c>>20)]);
1506                 result.append(DIGITS[0xF&(c>>16)]);
1507             } else {
1508                 result.append('u');
1509             }
1510             result.append(DIGITS[0xF&(c>>12)]);
1511             result.append(DIGITS[0xF&(c>>8)]);
1512             result.append(DIGITS[0xF&(c>>4)]);
1513             result.append(DIGITS[0xF&c]);
1514             return true;
1515         }
1516         return false;
1517     }
1518
1519     /**
1520      * Returns the index of the first character in a set, ignoring quoted text.
1521      * For example, in the string "abc'hide'h", the 'h' in "hide" will not be
1522      * found by a search for "h".  Unlike String.indexOf(), this method searches
1523      * not for a single character, but for any character of the string
1524      * <code>setOfChars</code>.
1525      * @param text text to be searched
1526      * @param start the beginning index, inclusive; <code>0 <= start
1527      * <= limit</code>.
1528      * @param limit the ending index, exclusive; <code>start <= limit
1529      * <= text.length()</code>.
1530      * @param setOfChars string with one or more distinct characters
1531      * @return Offset of the first character in <code>setOfChars</code>
1532      * found, or -1 if not found.
1533      * @see String#indexOf
1534      */
1535     public static int quotedIndexOf(String text, int start, int limit,
1536                                     String setOfChars) {
1537         for (int i=start; i<limit; ++i) {
1538             char c = text.charAt(i);
1539             if (c == BACKSLASH) {
1540                 ++i;
1541             } else if (c == APOSTROPHE) {
1542                 while (++i < limit
1543                        && text.charAt(i) != APOSTROPHE) {}
1544             } else if (setOfChars.indexOf(c) >= 0) {
1545                 return i;
1546             }
1547         }
1548         return -1;
1549     }
1550
1551     /**
1552     * Similar to StringBuffer.getChars, version 1.3.
1553     * Since JDK 1.2 implements StringBuffer.getChars differently, this method
1554     * is here to provide consistent results.
1555     * To be removed after JDK 1.2 ceased to be the reference platform.
1556     * @param src source string buffer
1557     * @param srcBegin offset to the start of the src to retrieve from
1558     * @param srcEnd offset to the end of the src to retrieve from
1559     * @param dst char array to store the retrieved chars
1560     * @param dstBegin offset to the start of the destination char array to
1561     *                 store the retrieved chars
1562     */
1563     public static void getChars(StringBuffer src, int srcBegin, int srcEnd,
1564                                 char dst[], int dstBegin)
1565     {
1566         if (srcBegin == srcEnd) {
1567             return;
1568         }
1569         src.getChars(srcBegin, srcEnd, dst, dstBegin);
1570     }
1571
1572     /**
1573      * Append a character to a rule that is being built up.  To flush
1574      * the quoteBuf to rule, make one final call with isLiteral == true.
1575      * If there is no final character, pass in (int)-1 as c.
1576      * @param rule the string to append the character to
1577      * @param c the character to append, or (int)-1 if none.
1578      * @param isLiteral if true, then the given character should not be
1579      * quoted or escaped.  Usually this means it is a syntactic element
1580      * such as > or $
1581      * @param escapeUnprintable if true, then unprintable characters
1582      * should be escaped using escapeUnprintable().  These escapes will
1583      * appear outside of quotes.
1584      * @param quoteBuf a buffer which is used to build up quoted
1585      * substrings.  The caller should initially supply an empty buffer,
1586      * and thereafter should not modify the buffer.  The buffer should be
1587      * cleared out by, at the end, calling this method with a literal
1588      * character (which may be -1).
1589      */
1590     public static void appendToRule(StringBuffer rule,
1591                                     int c,
1592                                     boolean isLiteral,
1593                                     boolean escapeUnprintable,
1594                                     StringBuffer quoteBuf) {
1595         // If we are escaping unprintables, then escape them outside
1596         // quotes.  \\u and \\U are not recognized within quotes.  The same
1597         // logic applies to literals, but literals are never escaped.
1598         if (isLiteral ||
1599             (escapeUnprintable && Utility.isUnprintable(c))) {
1600             if (quoteBuf.length() > 0) {
1601                 // We prefer backslash APOSTROPHE to double APOSTROPHE
1602                 // (more readable, less similar to ") so if there are
1603                 // double APOSTROPHEs at the ends, we pull them outside
1604                 // of the quote.
1605
1606                 // If the first thing in the quoteBuf is APOSTROPHE
1607                 // (doubled) then pull it out.
1608                 while (quoteBuf.length() >= 2 &&
1609                        quoteBuf.charAt(0) == APOSTROPHE &&
1610                        quoteBuf.charAt(1) == APOSTROPHE) {
1611                     rule.append(BACKSLASH).append(APOSTROPHE);
1612                     quoteBuf.delete(0, 2);
1613                 }
1614                 // If the last thing in the quoteBuf is APOSTROPHE
1615                 // (doubled) then remove and count it and add it after.
1616                 int trailingCount = 0;
1617                 while (quoteBuf.length() >= 2 &&
1618                        quoteBuf.charAt(quoteBuf.length()-2) == APOSTROPHE &&
1619                        quoteBuf.charAt(quoteBuf.length()-1) == APOSTROPHE) {
1620                     quoteBuf.setLength(quoteBuf.length()-2);
1621                     ++trailingCount;
1622                 }
1623                 if (quoteBuf.length() > 0) {
1624                     rule.append(APOSTROPHE);
1625                     // jdk 1.3.1 does not have append(StringBuffer) yet
1626                     if(ICUDebug.isJDK14OrHigher){
1627                         rule.append(quoteBuf);
1628                     }else{
1629                         rule.append(quoteBuf.toString());
1630                     }
1631                     rule.append(APOSTROPHE);
1632                     quoteBuf.setLength(0);
1633                 }
1634                 while (trailingCount-- > 0) {
1635                     rule.append(BACKSLASH).append(APOSTROPHE);
1636                 }
1637             }
1638             if (c != -1) {
1639                 /* Since spaces are ignored during parsing, they are
1640                  * emitted only for readability.  We emit one here
1641                  * only if there isn't already one at the end of the
1642                  * rule.
1643                  */
1644                 if (c == ' ') {
1645                     int len = rule.length();
1646                     if (len > 0 && rule.charAt(len-1) != ' ') {
1647                         rule.append(' ');
1648                     }
1649                 } else if (!escapeUnprintable || !Utility.escapeUnprintable(rule, c)) {
1650                     UTF16.append(rule, c);
1651                 }
1652             }
1653         }
1654
1655         // Escape ' and '\' and don't begin a quote just for them
1656         else if (quoteBuf.length() == 0 &&
1657                  (c == APOSTROPHE || c == BACKSLASH)) {
1658             rule.append(BACKSLASH).append((char)c);
1659         }
1660
1661         // Specials (printable ascii that isn't [0-9a-zA-Z]) and
1662         // whitespace need quoting.  Also append stuff to quotes if we are
1663         // building up a quoted substring already.
1664         else if (quoteBuf.length() > 0 ||
1665                  (c >= 0x0021 && c <= 0x007E &&
1666                   !((c >= 0x0030/*'0'*/ && c <= 0x0039/*'9'*/) ||
1667                     (c >= 0x0041/*'A'*/ && c <= 0x005A/*'Z'*/) ||
1668                     (c >= 0x0061/*'a'*/ && c <= 0x007A/*'z'*/))) ||
1669                  UCharacterProperty.isRuleWhiteSpace(c)) {
1670             UTF16.append(quoteBuf, c);
1671             // Double ' within a quote
1672             if (c == APOSTROPHE) {
1673                 quoteBuf.append((char)c);
1674             }
1675         }
1676
1677         // Otherwise just append
1678         else {
1679             UTF16.append(rule, c);
1680         }
1681     }
1682
1683     /**
1684      * Append the given string to the rule.  Calls the single-character
1685      * version of appendToRule for each character.
1686      */
1687     public static void appendToRule(StringBuffer rule,
1688                                     String text,
1689                                     boolean isLiteral,
1690                                     boolean escapeUnprintable,
1691                                     StringBuffer quoteBuf) {
1692         for (int i=0; i<text.length(); ++i) {
1693             // Okay to process in 16-bit code units here
1694             appendToRule(rule, text.charAt(i), isLiteral, escapeUnprintable, quoteBuf);
1695         }
1696     }
1697
1698     /**
1699      * Given a matcher reference, which may be null, append its
1700      * pattern as a literal to the given rule.
1701      */
1702     public static void appendToRule(StringBuffer rule,
1703                                     UnicodeMatcher matcher,
1704                                     boolean escapeUnprintable,
1705                                     StringBuffer quoteBuf) {
1706         if (matcher != null) {
1707             appendToRule(rule, matcher.toPattern(escapeUnprintable),
1708                          true, escapeUnprintable, quoteBuf);
1709         }
1710     }
1711
1712     /**
1713      * Compares 2 unsigned integers
1714      * @param source 32 bit unsigned integer
1715      * @param target 32 bit unsigned integer
1716      * @return 0 if equals, 1 if source is greater than target and -1
1717      *         otherwise
1718      */
1719     public static final int compareUnsigned(int source, int target)
1720     {
1721         source += MAGIC_UNSIGNED;
1722         target += MAGIC_UNSIGNED;
1723         if (source < target) {
1724             return -1;
1725         }
1726         else if (source > target) {
1727             return 1;
1728         }
1729         return 0;
1730     }
1731
1732     /**
1733      * Find the highest bit in a positive integer. This is done
1734      * by doing a binary search through the bits.
1735      *
1736      * @param n is the integer
1737      *
1738      * @return the bit number of the highest bit, with 0 being
1739      * the low order bit, or -1 if <code>n</code> is not positive
1740      */
1741     public static final byte highBit(int n)
1742     {
1743         if (n <= 0) {
1744             return -1;
1745         }
1746
1747         byte bit = 0;
1748
1749         if (n >= 1 << 16) {
1750             n >>= 16;
1751             bit += 16;
1752         }
1753
1754         if (n >= 1 << 8) {
1755             n >>= 8;
1756             bit += 8;
1757         }
1758
1759         if (n >= 1 << 4) {
1760             n >>= 4;
1761             bit += 4;
1762         }
1763
1764         if (n >= 1 << 2) {
1765             n >>= 2;
1766             bit += 2;
1767         }
1768
1769         if (n >= 1 << 1) {
1770             n >>= 1;
1771             bit += 1;
1772         }
1773
1774         return bit;
1775     }
1776     /**
1777      * Utility method to take a int[] containing codepoints and return
1778      * a string representation with code units.
1779      */
1780     public static String valueOf(int[]source){
1781     // TODO: Investigate why this method is not on UTF16 class
1782         StringBuffer result = new StringBuffer(source.length);
1783         for(int i=0; i<source.length; i++){
1784             UTF16.append(result,source[i]);
1785         }
1786         return result.toString();
1787     }
1788
1789
1790     /**
1791      * Utility to duplicate a string count times
1792      * @param s
1793      * @param count
1794      */
1795     public static String repeat(String s, int count) {
1796         if (count <= 0) return "";
1797         if (count == 1) return s;
1798         StringBuffer result = new StringBuffer();
1799         for (int i = 0; i < count; ++i) {
1800             result.append(s);
1801         }
1802         return result.toString();
1803     }
1804
1805
1806     // !!! 1.3 compatibility
1807     public static int indexOf(StringBuffer buf, String s) {
1808 //#if defined(FOUNDATION10) || defined(J2SE13)
1809 //##        return buf.toString().indexOf(s);
1810 //#else
1811         return buf.indexOf(s);
1812 //#endif
1813     }
1814
1815     // !!! 1.3 compatibility
1816     public static int lastIndexOf(StringBuffer buf, String s) {
1817 //#if defined(FOUNDATION10) || defined(J2SE13)
1818 //##        return buf.toString().lastIndexOf(s);
1819 //#else
1820         return buf.lastIndexOf(s);
1821 //#endif
1822     }
1823
1824     // !!! 1.3 compatibility
1825     public static int indexOf(StringBuffer buf, String s, int i) {
1826 //#if defined(FOUNDATION10) || defined(J2SE13)
1827 //##        return buf.toString().indexOf(s, i);
1828 //#else
1829         return buf.indexOf(s, i);
1830 //#endif
1831     }
1832
1833     // !!! 1.3 compatibility
1834    public static int lastIndexOf(StringBuffer buf, String s, int i) {
1835 //#if defined(FOUNDATION10) || defined(J2SE13)
1836 //##        return buf.toString().lastIndexOf(s, i);
1837 //#else
1838         return buf.lastIndexOf(s, i);
1839 //#endif
1840     }
1841
1842    // !!! 1.3/1.4 compatibility
1843    public static String replace(String src, String target, String replacement) {
1844 //#if defined(FOUNDATION10) || defined(J2SE13) || defined(J2SE14)
1845 //##       int i = src.indexOf(target);
1846 //##       if (i == -1) {
1847 //##           return src;
1848 //##       }
1849 //##       StringBuffer buf = new StringBuffer();
1850 //##       int n = 0;
1851 //##       do {
1852 //##           buf.append(src.substring(n, i));
1853 //##           buf.append(replacement);
1854 //##           n = i + target.length();
1855 //##           i = src.indexOf(target, n);
1856 //##       } while (i != -1);
1857 //##       if (n < src.length()) {
1858 //##           buf.append(src.substring(n));
1859 //##       }
1860 //##       return buf.toString();
1861 //#else
1862        return src.replace(target, replacement);
1863 //#endif
1864    }
1865
1866    // !!! 1.3 compatibility
1867    public static String replaceAll(String src, String target, String replacement) {
1868 //#if defined(FOUNDATION10) || defined(J2SE13)
1869 //##       return replace(src, target, replacement);
1870 //#else
1871        return src.replaceAll(target, replacement);
1872 //#endif
1873    }
1874
1875    //private static final String REGEX_SPECIALS = ".^$[]*+?|()";
1876
1877    // !!! 1.3 compatibility
1878    // Note: target is not a string literal, not a regular expression.
1879    public static String[] splitString(String src, String target) {
1880 //#if defined(FOUNDATION10) || defined(J2SE13)
1881 //##       int i = src.indexOf(target);
1882 //##       if (i == -1) {
1883 //##           return new String[] { src };
1884 //##       }
1885 //##       ArrayList output = new ArrayList();
1886 //##       int n = 0;
1887 //##       do {
1888 //##           output.add(src.substring(n, i));
1889 //##           n = i + target.length();
1890 //##           i = src.indexOf(target, n);
1891 //##       } while (i != -1);
1892 //##       if (n < src.length()) {
1893 //##           output.add(src.substring(n));
1894 //##       }
1895 //##       return (String[]) output.toArray(new String[output.size()]);
1896 //#else
1897        return src.split("\\Q" + target + "\\E");
1898 //#endif
1899    }
1900
1901    // !!! 1.3 compatibility
1902   /**
1903    * Split the string at runs of ascii whitespace characters.
1904    */
1905    public static String[] splitWhitespace(String src) {
1906 //#if defined(FOUNDATION10) || defined(J2SE13)
1907 //##        char ws[] = "\u0020\u0009\n\u000b\u000c\r".toCharArray();
1908 //##        ArrayList output = new ArrayList();
1909 //##        boolean inWhitespace = true;
1910 //##        int n = 0;
1911 //##  loop:
1912 //##        for (int i = 0; i < src.length(); ++i) {
1913 //##          char c = src.charAt(i);
1914 //##          for (int j = 0; j < ws.length; ++j) {
1915 //##            if (ws[j] == c) {
1916 //##              if (!inWhitespace) {
1917 //##                output.add(src.substring(n, i));
1918 //##                inWhitespace = true;
1919 //##              }
1920 //##              continue loop;
1921 //##            }
1922 //##          }
1923 //##          if (inWhitespace) {
1924 //##            n = i;
1925 //##            inWhitespace = false;
1926 //##          }
1927 //##        }
1928 //##        if (n < src.length()) {
1929 //##          output.add(src.substring(n));
1930 //##        }
1931 //##        return (String[]) output.toArray(new String[output.size()]);
1932 //#else
1933        return src.split("\\s+");
1934 //#endif
1935    }
1936
1937    // !!! 1.3/1.4 compatibility
1938    // Integer constants - Integer.valueOf(int) is not supported in JDK 1.3/1.4
1939    private static final int MAX_INT_CONST = 64;
1940    private static final Integer[] INT_CONST = new Integer[MAX_INT_CONST];
1941
1942    static {
1943        for (int i = 0; i < MAX_INT_CONST; i++) {
1944            INT_CONST[i] = new Integer(i);
1945        }
1946    }
1947
1948    public static Integer integerValueOf(int val) {
1949        if (0 <= val && val < MAX_INT_CONST) {
1950            return INT_CONST[val];
1951        }
1952        return new Integer(val);
1953    }
1954
1955    // !!! 1.3/1.4 compatibility
1956    // Arrays.toString(Object[])
1957    public static String arrayToString(Object[] a) {
1958        StringBuffer buf = new StringBuffer("[");
1959        for (int i = 0; i < a.length; i++) {
1960            if (i != 0) {
1961                buf.append(", ");
1962            }
1963            if (a[i] == null) {
1964                buf.append("null");
1965            } else {
1966                buf.append(a[i].toString());
1967            }
1968        }
1969        buf.append("]");
1970        return buf.toString();
1971    }
1972 }