jars/icu4j-4_2_1-src/src/com/ibm/icu/text/UnicodeSet.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.text;
   9
  10 import java.text.*;
  11 import com.ibm.icu.lang.*;
  12
  13 import java.io.IOException;
  14
  15 import com.ibm.icu.impl.NormalizerImpl;
  16 import com.ibm.icu.impl.Utility;
  17 import com.ibm.icu.impl.UCharacterProperty;
  18 import com.ibm.icu.impl.UBiDiProps;
  19 import com.ibm.icu.impl.UCaseProps;
  20 import com.ibm.icu.impl.UPropertyAliases;
  21 import com.ibm.icu.impl.SortedSetRelation;
  22 import com.ibm.icu.impl.RuleCharacterIterator;
  23
  24 import com.ibm.icu.util.Freezable;
  25 import com.ibm.icu.util.ULocale;
  26 import com.ibm.icu.util.VersionInfo;
  27
  28 import com.ibm.icu.text.BreakIterator;
  29
  30 import java.util.MissingResourceException;
  31 import java.util.TreeSet;
  32 import java.util.Iterator;
  33 import java.util.Collection;
  34
  35 /**
  36  * A mutable set of Unicode characters and multicharacter strings.  Objects of this class
  37  * represent <em>character classes</em> used in regular expressions.
  38  * A character specifies a subset of Unicode code points.  Legal
  39  * code points are U+0000 to U+10FFFF, inclusive.
  40  *
  41  * <p>The UnicodeSet class is not designed to be subclassed.
  42  *
  43  * <p><code>UnicodeSet</code> supports two APIs. The first is the
  44  * <em>operand</em> API that allows the caller to modify the value of
  45  * a <code>UnicodeSet</code> object. It conforms to Java 2's
  46  * <code>java.util.Set</code> interface, although
  47  * <code>UnicodeSet</code> does not actually implement that
  48  * interface. All methods of <code>Set</code> are supported, with the
  49  * modification that they take a character range or single character
  50  * instead of an <code>Object</code>, and they take a
  51  * <code>UnicodeSet</code> instead of a <code>Collection</code>.  The
  52  * operand API may be thought of in terms of boolean logic: a boolean
  53  * OR is implemented by <code>add</code>, a boolean AND is implemented
  54  * by <code>retain</code>, a boolean XOR is implemented by
  55  * <code>complement</code> taking an argument, and a boolean NOT is
  56  * implemented by <code>complement</code> with no argument.  In terms
  57  * of traditional set theory function names, <code>add</code> is a
  58  * union, <code>retain</code> is an intersection, <code>remove</code>
  59  * is an asymmetric difference, and <code>complement</code> with no
  60  * argument is a set complement with respect to the superset range
  61  * <code>MIN_VALUE-MAX_VALUE</code>
  62  *
  63  * <p>The second API is the
  64  * <code>applyPattern()</code>/<code>toPattern()</code> API from the
  65  * <code>java.text.Format</code>-derived classes.  Unlike the
  66  * methods that add characters, add categories, and control the logic
  67  * of the set, the method <code>applyPattern()</code> sets all
  68  * attributes of a <code>UnicodeSet</code> at once, based on a
  69  * string pattern.
  70  *
  71  * <p><b>Pattern syntax</b></p>
  72  *
  73  * Patterns are accepted by the constructors and the
  74  * <code>applyPattern()</code> methods and returned by the
  75  * <code>toPattern()</code> method.  These patterns follow a syntax
  76  * similar to that employed by version 8 regular expression character
  77  * classes.  Here are some simple examples:
  78  *
  79  * <blockquote>
  80  *   <table>
  81  *     <tr align="top">
  82  *       <td nowrap valign="top" align="left"><code>[]</code></td>
  83  *       <td valign="top">No characters</td>
  84  *     </tr><tr align="top">
  85  *       <td nowrap valign="top" align="left"><code>[a]</code></td>
  86  *       <td valign="top">The character 'a'</td>
  87  *     </tr><tr align="top">
  88  *       <td nowrap valign="top" align="left"><code>[ae]</code></td>
  89  *       <td valign="top">The characters 'a' and 'e'</td>
  90  *     </tr>
  91  *     <tr>
  92  *       <td nowrap valign="top" align="left"><code>[a-e]</code></td>
  93  *       <td valign="top">The characters 'a' through 'e' inclusive, in Unicode code
  94  *       point order</td>
  95  *     </tr>
  96  *     <tr>
  97  *       <td nowrap valign="top" align="left"><code>[\\u4E01]</code></td>
  98  *       <td valign="top">The character U+4E01</td>
  99  *     </tr>
 100  *     <tr>
 101  *       <td nowrap valign="top" align="left"><code>[a{ab}{ac}]</code></td>
 102  *       <td valign="top">The character 'a' and the multicharacter strings &quot;ab&quot; and
 103  *       &quot;ac&quot;</td>
 104  *     </tr>
 105  *     <tr>
 106  *       <td nowrap valign="top" align="left"><code>[\p{Lu}]</code></td>
 107  *       <td valign="top">All characters in the general category Uppercase Letter</td>
 108  *     </tr>
 109  *   </table>
 110  * </blockquote>
 111  *
 112  * Any character may be preceded by a backslash in order to remove any special
 113  * meaning.  White space characters, as defined by UCharacterProperty.isRuleWhiteSpace(), are
 114  * ignored, unless they are escaped.
 115  *
 116  * <p>Property patterns specify a set of characters having a certain
 117  * property as defined by the Unicode standard.  Both the POSIX-like
 118  * "[:Lu:]" and the Perl-like syntax "\p{Lu}" are recognized.  For a
 119  * complete list of supported property patterns, see the User's Guide
 120  * for UnicodeSet at
 121  * <a href="http://www.icu-project.org/userguide/unicodeSet.html">
 122  * http://www.icu-project.org/userguide/unicodeSet.html</a>.
 123  * Actual determination of property data is defined by the underlying
 124  * Unicode database as implemented by UCharacter.
 125  *
 126  * <p>Patterns specify individual characters, ranges of characters, and
 127  * Unicode property sets.  When elements are concatenated, they
 128  * specify their union.  To complement a set, place a '^' immediately
 129  * after the opening '['.  Property patterns are inverted by modifying
 130  * their delimiters; "[:^foo]" and "\P{foo}".  In any other location,
 131  * '^' has no special meaning.
 132  *
 133  * <p>Ranges are indicated by placing two a '-' between two
 134  * characters, as in "a-z".  This specifies the range of all
 135  * characters from the left to the right, in Unicode order.  If the
 136  * left character is greater than or equal to the
 137  * right character it is a syntax error.  If a '-' occurs as the first
 138  * character after the opening '[' or '[^', or if it occurs as the
 139  * last character before the closing ']', then it is taken as a
 140  * literal.  Thus "[a\\-b]", "[-ab]", and "[ab-]" all indicate the same
 141  * set of three characters, 'a', 'b', and '-'.
 142  *
 143  * <p>Sets may be intersected using the '&' operator or the asymmetric
 144  * set difference may be taken using the '-' operator, for example,
 145  * "[[:L:]&[\\u0000-\\u0FFF]]" indicates the set of all Unicode letters
 146  * with values less than 4096.  Operators ('&' and '|') have equal
 147  * precedence and bind left-to-right.  Thus
 148  * "[[:L:]-[a-z]-[\\u0100-\\u01FF]]" is equivalent to
 149  * "[[[:L:]-[a-z]]-[\\u0100-\\u01FF]]".  This only really matters for
 150  * difference; intersection is commutative.
 151  *
 152  * <table>
 153  * <tr valign=top><td nowrap><code>[a]</code><td>The set containing 'a'
 154  * <tr valign=top><td nowrap><code>[a-z]</code><td>The set containing 'a'
 155  * through 'z' and all letters in between, in Unicode order
 156  * <tr valign=top><td nowrap><code>[^a-z]</code><td>The set containing
 157  * all characters but 'a' through 'z',
 158  * that is, U+0000 through 'a'-1 and 'z'+1 through U+10FFFF
 159  * <tr valign=top><td nowrap><code>[[<em>pat1</em>][<em>pat2</em>]]</code>
 160  * <td>The union of sets specified by <em>pat1</em> and <em>pat2</em>
 161  * <tr valign=top><td nowrap><code>[[<em>pat1</em>]&[<em>pat2</em>]]</code>
 162  * <td>The intersection of sets specified by <em>pat1</em> and <em>pat2</em>
 163  * <tr valign=top><td nowrap><code>[[<em>pat1</em>]-[<em>pat2</em>]]</code>
 164  * <td>The asymmetric difference of sets specified by <em>pat1</em> and
 165  * <em>pat2</em>
 166  * <tr valign=top><td nowrap><code>[:Lu:] or \p{Lu}</code>
 167  * <td>The set of characters having the specified
 168  * Unicode property; in
 169  * this case, Unicode uppercase letters
 170  * <tr valign=top><td nowrap><code>[:^Lu:] or \P{Lu}</code>
 171  * <td>The set of characters <em>not</em> having the given
 172  * Unicode property
 173  * </table>
 174  *
 175  * <p><b>Warning</b>: you cannot add an empty string ("") to a UnicodeSet.</p>
 176  *
 177  * <p><b>Formal syntax</b></p>
 178  *
 179  * <blockquote>
 180  *   <table>
 181  *     <tr align="top">
 182  *       <td nowrap valign="top" align="right"><code>pattern :=&nbsp; </code></td>
 183  *       <td valign="top"><code>('[' '^'? item* ']') |
 184  *       property</code></td>
 185  *     </tr>
 186  *     <tr align="top">
 187  *       <td nowrap valign="top" align="right"><code>item :=&nbsp; </code></td>
 188  *       <td valign="top"><code>char | (char '-' char) | pattern-expr<br>
 189  *       </code></td>
 190  *     </tr>
 191  *     <tr align="top">
 192  *       <td nowrap valign="top" align="right"><code>pattern-expr :=&nbsp; </code></td>
 193  *       <td valign="top"><code>pattern | pattern-expr pattern |
 194  *       pattern-expr op pattern<br>
 195  *       </code></td>
 196  *     </tr>
 197  *     <tr align="top">
 198  *       <td nowrap valign="top" align="right"><code>op :=&nbsp; </code></td>
 199  *       <td valign="top"><code>'&amp;' | '-'<br>
 200  *       </code></td>
 201  *     </tr>
 202  *     <tr align="top">
 203  *       <td nowrap valign="top" align="right"><code>special :=&nbsp; </code></td>
 204  *       <td valign="top"><code>'[' | ']' | '-'<br>
 205  *       </code></td>
 206  *     </tr>
 207  *     <tr align="top">
 208  *       <td nowrap valign="top" align="right"><code>char :=&nbsp; </code></td>
 209  *       <td valign="top"><em>any character that is not</em><code> special<br>
 210  *       | ('\\' </code><em>any character</em><code>)<br>
 211  *       | ('&#92;u' hex hex hex hex)<br>
 212  *       </code></td>
 213  *     </tr>
 214  *     <tr align="top">
 215  *       <td nowrap valign="top" align="right"><code>hex :=&nbsp; </code></td>
 216  *       <td valign="top"><em>any character for which
 217  *       </em><code>Character.digit(c, 16)</code><em>
 218  *       returns a non-negative result</em></td>
 219  *     </tr>
 220  *     <tr>
 221  *       <td nowrap valign="top" align="right"><code>property :=&nbsp; </code></td>
 222  *       <td valign="top"><em>a Unicode property set pattern</td>
 223  *     </tr>
 224  *   </table>
 225  *   <br>
 226  *   <table border="1">
 227  *     <tr>
 228  *       <td>Legend: <table>
 229  *         <tr>
 230  *           <td nowrap valign="top"><code>a := b</code></td>
 231  *           <td width="20" valign="top">&nbsp; </td>
 232  *           <td valign="top"><code>a</code> may be replaced by <code>b</code> </td>
 233  *         </tr>
 234  *         <tr>
 235  *           <td nowrap valign="top"><code>a?</code></td>
 236  *           <td valign="top"></td>
 237  *           <td valign="top">zero or one instance of <code>a</code><br>
 238  *           </td>
 239  *         </tr>
 240  *         <tr>
 241  *           <td nowrap valign="top"><code>a*</code></td>
 242  *           <td valign="top"></td>
 243  *           <td valign="top">one or more instances of <code>a</code><br>
 244  *           </td>
 245  *         </tr>
 246  *         <tr>
 247  *           <td nowrap valign="top"><code>a | b</code></td>
 248  *           <td valign="top"></td>
 249  *           <td valign="top">either <code>a</code> or <code>b</code><br>
 250  *           </td>
 251  *         </tr>
 252  *         <tr>
 253  *           <td nowrap valign="top"><code>'a'</code></td>
 254  *           <td valign="top"></td>
 255  *           <td valign="top">the literal string between the quotes </td>
 256  *         </tr>
 257  *       </table>
 258  *       </td>
 259  *     </tr>
 260  *   </table>
 261  * </blockquote>
 262  * <p>To iterate over contents of UnicodeSet, use UnicodeSetIterator class.
 263  *
 264  * @author Alan Liu
 265  * @stable ICU 2.0
 266  * @see UnicodeSetIterator
 267  */
 268 public class UnicodeSet extends UnicodeFilter implements Freezable {
 269
 270     private static final int LOW = 0x000000; // LOW <= all valid values. ZERO for codepoints
 271     private static final int HIGH = 0x110000; // HIGH > all valid values. 10000 for code units.
 272                                              // 110000 for codepoints
 273
 274     /**
 275      * Minimum value that can be stored in a UnicodeSet.
 276      * @stable ICU 2.0
 277      */
 278     public static final int MIN_VALUE = LOW;
 279
 280     /**
 281      * Maximum value that can be stored in a UnicodeSet.
 282      * @stable ICU 2.0
 283      */
 284     public static final int MAX_VALUE = HIGH - 1;
 285
 286     private int len;      // length used; list may be longer to minimize reallocs
 287     private int[] list;   // MUST be terminated with HIGH
 288     private int[] rangeList; // internal buffer
 289     private int[] buffer; // internal buffer
 290
 291     // NOTE: normally the field should be of type SortedSet; but that is missing a public clone!!
 292     // is not private so that UnicodeSetIterator can get access
 293     TreeSet strings = new TreeSet();
 294
 295     /**
 296      * The pattern representation of this set.  This may not be the
 297      * most economical pattern.  It is the pattern supplied to
 298      * applyPattern(), with variables substituted and whitespace
 299      * removed.  For sets constructed without applyPattern(), or
 300      * modified using the non-pattern API, this string will be null,
 301      * indicating that toPattern() must generate a pattern
 302      * representation from the inversion list.
 303      */
 304     private String pat = null;
 305
 306     private static final int START_EXTRA = 16;         // initial storage. Must be >= 0
 307     private static final int GROW_EXTRA = START_EXTRA; // extra amount for growth. Must be >= 0
 308
 309     // Special property set IDs
 310     private static final String ANY_ID   = "ANY";   // [\u0000-\U0010FFFF]
 311     private static final String ASCII_ID = "ASCII"; // [\u0000-\u007F]
 312     private static final String ASSIGNED = "Assigned"; // [:^Cn:]
 313
 314     /**
 315      * A set of all characters _except_ the second through last characters of
 316      * certain ranges.  These ranges are ranges of characters whose
 317      * properties are all exactly alike, e.g. CJK Ideographs from
 318      * U+4E00 to U+9FA5.
 319      */
 320     private static UnicodeSet INCLUSIONS[] = null;
 321
 322     //----------------------------------------------------------------
 323     // Public API
 324     //----------------------------------------------------------------
 325
 326     /**
 327      * Constructs an empty set.
 328      * @stable ICU 2.0
 329      */
 330     public UnicodeSet() {
 331         list = new int[1 + START_EXTRA];
 332         list[len++] = HIGH;
 333     }
 334
 335     /**
 336      * Constructs a copy of an existing set.
 337      * @stable ICU 2.0
 338      */
 339     public UnicodeSet(UnicodeSet other) {
 340         set(other);
 341     }
 342
 343     /**
 344      * Constructs a set containing the given range. If <code>end >
 345      * start</code> then an empty set is created.
 346      *
 347      * @param start first character, inclusive, of range
 348      * @param end last character, inclusive, of range
 349      * @stable ICU 2.0
 350      */
 351     public UnicodeSet(int start, int end) {
 352         this();
 353         complement(start, end);
 354     }
 355
 356     /**
 357      * Constructs a set from the given pattern.  See the class description
 358      * for the syntax of the pattern language.  Whitespace is ignored.
 359      * @param pattern a string specifying what characters are in the set
 360      * @exception java.lang.IllegalArgumentException if the pattern contains
 361      * a syntax error.
 362      * @stable ICU 2.0
 363      */
 364     public UnicodeSet(String pattern) {
 365         this();
 366         applyPattern(pattern, null, null, IGNORE_SPACE);
 367     }
 368
 369     /**
 370      * Constructs a set from the given pattern.  See the class description
 371      * for the syntax of the pattern language.
 372      * @param pattern a string specifying what characters are in the set
 373      * @param ignoreWhitespace if true, ignore characters for which
 374      * UCharacterProperty.isRuleWhiteSpace() returns true
 375      * @exception java.lang.IllegalArgumentException if the pattern contains
 376      * a syntax error.
 377      * @stable ICU 2.0
 378      */
 379     public UnicodeSet(String pattern, boolean ignoreWhitespace) {
 380         this();
 381         applyPattern(pattern, null, null, ignoreWhitespace ? IGNORE_SPACE : 0);
 382     }
 383
 384     /**
 385      * Constructs a set from the given pattern.  See the class description
 386      * for the syntax of the pattern language.
 387      * @param pattern a string specifying what characters are in the set
 388      * @param options a bitmask indicating which options to apply.
 389      * Valid options are IGNORE_SPACE and CASE.
 390      * @exception java.lang.IllegalArgumentException if the pattern contains
 391      * a syntax error.
 392      * @stable ICU 3.8
 393      */
 394     public UnicodeSet(String pattern, int options) {
 395         this();
 396         applyPattern(pattern, null, null, options);
 397     }
 398
 399     /**
 400      * Constructs a set from the given pattern.  See the class description
 401      * for the syntax of the pattern language.
 402      * @param pattern a string specifying what characters are in the set
 403      * @param pos on input, the position in pattern at which to start parsing.
 404      * On output, the position after the last character parsed.
 405      * @param symbols a symbol table mapping variables to char[] arrays
 406      * and chars to UnicodeSets
 407      * @exception java.lang.IllegalArgumentException if the pattern
 408      * contains a syntax error.
 409      * @stable ICU 2.0
 410      */
 411     public UnicodeSet(String pattern, ParsePosition pos, SymbolTable symbols) {
 412         this();
 413         applyPattern(pattern, pos, symbols, IGNORE_SPACE);
 414     }
 415
 416     /**
 417      * Constructs a set from the given pattern.  See the class description
 418      * for the syntax of the pattern language.
 419      * @param pattern a string specifying what characters are in the set
 420      * @param pos on input, the position in pattern at which to start parsing.
 421      * On output, the position after the last character parsed.
 422      * @param symbols a symbol table mapping variables to char[] arrays
 423      * and chars to UnicodeSets
 424      * @param options a bitmask indicating which options to apply.
 425      * Valid options are IGNORE_SPACE and CASE.
 426      * @exception java.lang.IllegalArgumentException if the pattern
 427      * contains a syntax error.
 428      * @stable ICU 3.2
 429      */
 430     public UnicodeSet(String pattern, ParsePosition pos, SymbolTable symbols, int options) {
 431         this();
 432         applyPattern(pattern, pos, symbols, options);
 433     }
 434
 435
 436     /**
 437      * Return a new set that is equivalent to this one.
 438      * @stable ICU 2.0
 439      */
 440     public Object clone() {
 441         UnicodeSet result = new UnicodeSet(this);
 442         result.frozen = this.frozen;
 443         return result;
 444     }
 445
 446     /**
 447      * Make this object represent the range <code>start - end</code>.
 448      * If <code>end > start</code> then this object is set to an
 449      * an empty range.
 450      *
 451      * @param start first character in the set, inclusive
 452      * @param end last character in the set, inclusive
 453      * @stable ICU 2.0
 454      */
 455     public UnicodeSet set(int start, int end) {
 456         checkFrozen();
 457         clear();
 458         complement(start, end);
 459         return this;
 460     }
 461
 462     /**
 463      * Make this object represent the same set as <code>other</code>.
 464      * @param other a <code>UnicodeSet</code> whose value will be
 465      * copied to this object
 466      * @stable ICU 2.0
 467      */
 468     public UnicodeSet set(UnicodeSet other) {
 469         checkFrozen();
 470         list = (int[]) other.list.clone();
 471         len = other.len;
 472         pat = other.pat;
 473         strings = (TreeSet)other.strings.clone();
 474         return this;
 475     }
 476
 477     /**
 478      * Modifies this set to represent the set specified by the given pattern.
 479      * See the class description for the syntax of the pattern language.
 480      * Whitespace is ignored.
 481      * @param pattern a string specifying what characters are in the set
 482      * @exception java.lang.IllegalArgumentException if the pattern
 483      * contains a syntax error.
 484      * @stable ICU 2.0
 485      */
 486     public final UnicodeSet applyPattern(String pattern) {
 487         checkFrozen();
 488         return applyPattern(pattern, null, null, IGNORE_SPACE);
 489     }
 490
 491     /**
 492      * Modifies this set to represent the set specified by the given pattern,
 493      * optionally ignoring whitespace.
 494      * See the class description for the syntax of the pattern language.
 495      * @param pattern a string specifying what characters are in the set
 496      * @param ignoreWhitespace if true then characters for which
 497      * UCharacterProperty.isRuleWhiteSpace() returns true are ignored
 498      * @exception java.lang.IllegalArgumentException if the pattern
 499      * contains a syntax error.
 500      * @stable ICU 2.0
 501      */
 502     public UnicodeSet applyPattern(String pattern, boolean ignoreWhitespace) {
 503         checkFrozen();
 504         return applyPattern(pattern, null, null, ignoreWhitespace ? IGNORE_SPACE : 0);
 505     }
 506
 507     /**
 508      * Modifies this set to represent the set specified by the given pattern,
 509      * optionally ignoring whitespace.
 510      * See the class description for the syntax of the pattern language.
 511      * @param pattern a string specifying what characters are in the set
 512      * @param options a bitmask indicating which options to apply.
 513      * Valid options are IGNORE_SPACE and CASE.
 514      * @exception java.lang.IllegalArgumentException if the pattern
 515      * contains a syntax error.
 516      * @stable ICU 3.8
 517      */
 518     public UnicodeSet applyPattern(String pattern, int options) {
 519         checkFrozen();
 520         return applyPattern(pattern, null, null, options);
 521     }
 522
 523     /**
 524      * Return true if the given position, in the given pattern, appears
 525      * to be the start of a UnicodeSet pattern.
 526      * @stable ICU 2.0
 527      */
 528     public static boolean resemblesPattern(String pattern, int pos) {
 529         return ((pos+1) < pattern.length() &&
 530                 pattern.charAt(pos) == '[') ||
 531             resemblesPropertyPattern(pattern, pos);
 532     }
 533
 534     /**
 535      * Append the <code>toPattern()</code> representation of a
 536      * string to the given <code>StringBuffer</code>.
 537      */
 538     private static void _appendToPat(StringBuffer buf, String s, boolean escapeUnprintable) {
 539         for (int i = 0; i < s.length(); i += UTF16.getCharCount(i)) {
 540             _appendToPat(buf, UTF16.charAt(s, i), escapeUnprintable);
 541         }
 542     }
 543
 544     /**
 545      * Append the <code>toPattern()</code> representation of a
 546      * character to the given <code>StringBuffer</code>.
 547      */
 548     private static void _appendToPat(StringBuffer buf, int c, boolean escapeUnprintable) {
 549         if (escapeUnprintable && Utility.isUnprintable(c)) {
 550             // Use hex escape notation (<backslash>uxxxx or <backslash>Uxxxxxxxx) for anything
 551             // unprintable
 552             if (Utility.escapeUnprintable(buf, c)) {
 553                 return;
 554             }
 555         }
 556         // Okay to let ':' pass through
 557         switch (c) {
 558         case '[': // SET_OPEN:
 559         case ']': // SET_CLOSE:
 560         case '-': // HYPHEN:
 561         case '^': // COMPLEMENT:
 562         case '&': // INTERSECTION:
 563         case '\\': //BACKSLASH:
 564         case '{':
 565         case '}':
 566         case '$':
 567         case ':':
 568             buf.append('\\');
 569             break;
 570         default:
 571             // Escape whitespace
 572             if (UCharacterProperty.isRuleWhiteSpace(c)) {
 573                 buf.append('\\');
 574             }
 575             break;
 576         }
 577         UTF16.append(buf, c);
 578     }
 579
 580     /**
 581      * Returns a string representation of this set.  If the result of
 582      * calling this function is passed to a UnicodeSet constructor, it
 583      * will produce another set that is equal to this one.
 584      * @stable ICU 2.0
 585      */
 586     public String toPattern(boolean escapeUnprintable) {
 587         StringBuffer result = new StringBuffer();
 588         return _toPattern(result, escapeUnprintable).toString();
 589     }
 590
 591     /**
 592      * Append a string representation of this set to result.  This will be
 593      * a cleaned version of the string passed to applyPattern(), if there
 594      * is one.  Otherwise it will be generated.
 595      */
 596     private StringBuffer _toPattern(StringBuffer result,
 597                                     boolean escapeUnprintable) {
 598         if (pat != null) {
 599             int i;
 600             int backslashCount = 0;
 601             for (i=0; i<pat.length(); ) {
 602                 int c = UTF16.charAt(pat, i);
 603                 i += UTF16.getCharCount(c);
 604                 if (escapeUnprintable && Utility.isUnprintable(c)) {
 605                     // If the unprintable character is preceded by an odd
 606                     // number of backslashes, then it has been escaped.
 607                     // Before unescaping it, we delete the final
 608                     // backslash.
 609                     if ((backslashCount % 2) == 1) {
 610                         result.setLength(result.length() - 1);
 611                     }
 612                     Utility.escapeUnprintable(result, c);
 613                     backslashCount = 0;
 614                 } else {
 615                     UTF16.append(result, c);
 616                     if (c == '\\') {
 617                         ++backslashCount;
 618                     } else {
 619                         backslashCount = 0;
 620                     }
 621                 }
 622             }
 623             return result;
 624         }
 625
 626         return _generatePattern(result, escapeUnprintable, true);
 627     }
 628
 629     /**
 630      * Generate and append a string representation of this set to result.
 631      * This does not use this.pat, the cleaned up copy of the string
 632      * passed to applyPattern().
 633      * @param result the buffer into which to generate the pattern
 634      * @param escapeUnprintable escape unprintable characters if true
 635      * @stable ICU 2.0
 636      */
 637     public StringBuffer _generatePattern(StringBuffer result, boolean escapeUnprintable) {
 638         return _generatePattern(result, escapeUnprintable, true);
 639     }
 640
 641     /**
 642      * Generate and append a string representation of this set to result.
 643      * This does not use this.pat, the cleaned up copy of the string
 644      * passed to applyPattern().
 645      * @param includeStrings if false, doesn't include the strings.
 646      * @stable ICU 3.8
 647      */
 648     public StringBuffer _generatePattern(StringBuffer result,
 649                                          boolean escapeUnprintable, boolean includeStrings) {
 650         result.append('[');
 651
 652 //      // Check against the predefined categories.  We implicitly build
 653 //      // up ALL category sets the first time toPattern() is called.
 654 //      for (int cat=0; cat<CATEGORY_COUNT; ++cat) {
 655 //          if (this.equals(getCategorySet(cat))) {
 656 //              result.append(':');
 657 //              result.append(CATEGORY_NAMES.substring(cat*2, cat*2+2));
 658 //              return result.append(":]");
 659 //          }
 660 //      }
 661
 662         int count = getRangeCount();
 663
 664         // If the set contains at least 2 intervals and includes both
 665         // MIN_VALUE and MAX_VALUE, then the inverse representation will
 666         // be more economical.
 667         if (count > 1 &&
 668             getRangeStart(0) == MIN_VALUE &&
 669             getRangeEnd(count-1) == MAX_VALUE) {
 670
 671             // Emit the inverse
 672             result.append('^');
 673
 674             for (int i = 1; i < count; ++i) {
 675                 int start = getRangeEnd(i-1)+1;
 676                 int end = getRangeStart(i)-1;
 677                 _appendToPat(result, start, escapeUnprintable);
 678                 if (start != end) {
 679                     if ((start+1) != end) {
 680                         result.append('-');
 681                     }
 682                     _appendToPat(result, end, escapeUnprintable);
 683                 }
 684             }
 685         }
 686
 687         // Default; emit the ranges as pairs
 688         else {
 689             for (int i = 0; i < count; ++i) {
 690                 int start = getRangeStart(i);
 691                 int end = getRangeEnd(i);
 692                 _appendToPat(result, start, escapeUnprintable);
 693                 if (start != end) {
 694                     if ((start+1) != end) {
 695                         result.append('-');
 696                     }
 697                     _appendToPat(result, end, escapeUnprintable);
 698                 }
 699             }
 700         }
 701
 702         if (includeStrings && strings.size() > 0) {
 703             Iterator it = strings.iterator();
 704             while (it.hasNext()) {
 705                 result.append('{');
 706                 _appendToPat(result, (String) it.next(), escapeUnprintable);
 707                 result.append('}');
 708             }
 709         }
 710         return result.append(']');
 711     }
 712
 713     /**
 714      * Returns the number of elements in this set (its cardinality)
 715      * Note than the elements of a set may include both individual
 716      * codepoints and strings.
 717      *
 718      * @return the number of elements in this set (its cardinality).
 719      * @stable ICU 2.0
 720      */
 721     public int size() {
 722         int n = 0;
 723         int count = getRangeCount();
 724         for (int i = 0; i < count; ++i) {
 725             n += getRangeEnd(i) - getRangeStart(i) + 1;
 726         }
 727         return n + strings.size();
 728     }
 729
 730     /**
 731      * Returns <tt>true</tt> if this set contains no elements.
 732      *
 733      * @return <tt>true</tt> if this set contains no elements.
 734      * @stable ICU 2.0
 735      */
 736     public boolean isEmpty() {
 737         return len == 1 && strings.size() == 0;
 738     }
 739
 740     /**
 741      * Implementation of UnicodeMatcher API.  Returns <tt>true</tt> if
 742      * this set contains any character whose low byte is the given
 743      * value.  This is used by <tt>RuleBasedTransliterator</tt> for
 744      * indexing.
 745      * @stable ICU 2.0
 746      */
 747     public boolean matchesIndexValue(int v) {
 748         /* The index value v, in the range [0,255], is contained in this set if
 749          * it is contained in any pair of this set.  Pairs either have the high
 750          * bytes equal, or unequal.  If the high bytes are equal, then we have
 751          * aaxx..aayy, where aa is the high byte.  Then v is contained if xx <=
 752          * v <= yy.  If the high bytes are unequal we have aaxx..bbyy, bb>aa.
 753          * Then v is contained if xx <= v || v <= yy.  (This is identical to the
 754          * time zone month containment logic.)
 755          */
 756         for (int i=0; i<getRangeCount(); ++i) {
 757             int low = getRangeStart(i);
 758             int high = getRangeEnd(i);
 759             if ((low & ~0xFF) == (high & ~0xFF)) {
 760                 if ((low & 0xFF) <= v && v <= (high & 0xFF)) {
 761                     return true;
 762                 }
 763             } else if ((low & 0xFF) <= v || v <= (high & 0xFF)) {
 764                 return true;
 765             }
 766         }
 767         if (strings.size() != 0) {
 768             Iterator it = strings.iterator();
 769             while (it.hasNext()) {
 770                 String s = (String) it.next();
 771                 //if (s.length() == 0) {
 772                 //    // Empty strings match everything
 773                 //    return true;
 774                 //}
 775                 // assert(s.length() != 0); // We enforce this elsewhere
 776                 int c = UTF16.charAt(s, 0);
 777                 if ((c & 0xFF) == v) {
 778                     return true;
 779                 }
 780             }
 781         }
 782         return false;
 783     }
 784
 785     /**
 786      * Implementation of UnicodeMatcher.matches().  Always matches the
 787      * longest possible multichar string.
 788      * @stable ICU 2.0
 789      */
 790     public int matches(Replaceable text,
 791                        int[] offset,
 792                        int limit,
 793                        boolean incremental) {
 794
 795         if (offset[0] == limit) {
 796             // Strings, if any, have length != 0, so we don't worry
 797             // about them here.  If we ever allow zero-length strings
 798             // we much check for them here.
 799             if (contains(UnicodeMatcher.ETHER)) {
 800                 return incremental ? U_PARTIAL_MATCH : U_MATCH;
 801             } else {
 802                 return U_MISMATCH;
 803             }
 804         } else {
 805             if (strings.size() != 0) { // try strings first
 806
 807                 // might separate forward and backward loops later
 808                 // for now they are combined
 809
 810                 // TODO Improve efficiency of this, at least in the forward
 811                 // direction, if not in both.  In the forward direction we
 812                 // can assume the strings are sorted.
 813
 814                 Iterator it = strings.iterator();
 815                 boolean forward = offset[0] < limit;
 816
 817                 // firstChar is the leftmost char to match in the
 818                 // forward direction or the rightmost char to match in
 819                 // the reverse direction.
 820                 char firstChar = text.charAt(offset[0]);
 821
 822                 // If there are multiple strings that can match we
 823                 // return the longest match.
 824                 int highWaterLength = 0;
 825
 826                 while (it.hasNext()) {
 827                     String trial = (String) it.next();
 828
 829                     //if (trial.length() == 0) {
 830                     //    return U_MATCH; // null-string always matches
 831                     //}
 832                     // assert(trial.length() != 0); // We ensure this elsewhere
 833
 834                     char c = trial.charAt(forward ? 0 : trial.length() - 1);
 835
 836                     // Strings are sorted, so we can optimize in the
 837                     // forward direction.
 838                     if (forward && c > firstChar) break;
 839                     if (c != firstChar) continue;
 840
 841                     int length = matchRest(text, offset[0], limit, trial);
 842
 843                     if (incremental) {
 844                         int maxLen = forward ? limit-offset[0] : offset[0]-limit;
 845                         if (length == maxLen) {
 846                             // We have successfully matched but only up to limit.
 847                             return U_PARTIAL_MATCH;
 848                         }
 849                     }
 850
 851                     if (length == trial.length()) {
 852                         // We have successfully matched the whole string.
 853                         if (length > highWaterLength) {
 854                             highWaterLength = length;
 855                         }
 856                         // In the forward direction we know strings
 857                         // are sorted so we can bail early.
 858                         if (forward && length < highWaterLength) {
 859                             break;
 860                         }
 861                         continue;
 862                     }
 863                 }
 864
 865                 // We've checked all strings without a partial match.
 866                 // If we have full matches, return the longest one.
 867                 if (highWaterLength != 0) {
 868                     offset[0] += forward ? highWaterLength : -highWaterLength;
 869                     return U_MATCH;
 870                 }
 871             }
 872             return super.matches(text, offset, limit, incremental);
 873         }
 874     }
 875
 876     /**
 877      * Returns the longest match for s in text at the given position.
 878      * If limit > start then match forward from start+1 to limit
 879      * matching all characters except s.charAt(0).  If limit < start,
 880      * go backward starting from start-1 matching all characters
 881      * except s.charAt(s.length()-1).  This method assumes that the
 882      * first character, text.charAt(start), matches s, so it does not
 883      * check it.
 884      * @param text the text to match
 885      * @param start the first character to match.  In the forward
 886      * direction, text.charAt(start) is matched against s.charAt(0).
 887      * In the reverse direction, it is matched against
 888      * s.charAt(s.length()-1).
 889      * @param limit the limit offset for matching, either last+1 in
 890      * the forward direction, or last-1 in the reverse direction,
 891      * where last is the index of the last character to match.
 892      * @return If part of s matches up to the limit, return |limit -
 893      * start|.  If all of s matches before reaching the limit, return
 894      * s.length().  If there is a mismatch between s and text, return
 895      * 0
 896      */
 897     private static int matchRest (Replaceable text, int start, int limit, String s) {
 898         int maxLen;
 899         int slen = s.length();
 900         if (start < limit) {
 901             maxLen = limit - start;
 902             if (maxLen > slen) maxLen = slen;
 903             for (int i = 1; i < maxLen; ++i) {
 904                 if (text.charAt(start + i) != s.charAt(i)) return 0;
 905             }
 906         } else {
 907             maxLen = start - limit;
 908             if (maxLen > slen) maxLen = slen;
 909             --slen; // <=> slen = s.length() - 1;
 910             for (int i = 1; i < maxLen; ++i) {
 911                 if (text.charAt(start - i) != s.charAt(slen - i)) return 0;
 912             }
 913         }
 914         return maxLen;
 915     }
 916
 917 //#if defined(FOUNDATION10) || defined(J2SE13)
 918 //#else
 919     /**
 920      * Tests whether the text matches at the offset. If so, returns the end of the longest substring that it matches. If not, returns -1.
 921      * @internal
 922      * @deprecated This API is ICU internal only.
 923      */
 924     public int matchesAt(CharSequence text, int offset) {
 925         int lastLen = -1;
 926         strings:
 927         if (strings.size() != 0) {
 928             char firstChar = text.charAt(offset);
 929             String trial = null;
 930             // find the first string starting with firstChar
 931             Iterator it = strings.iterator();
 932             while (it.hasNext()) {
 933                 trial = (String) it.next();
 934                 char firstStringChar = trial.charAt(0);
 935                 if (firstStringChar < firstChar) continue;
 936                 if (firstStringChar > firstChar) break strings;
 937             }
 938             // now keep checking string until we get the longest one
 939             for (;;) {
 940                 int tempLen = matchesAt(text, offset, trial);
 941                 if (lastLen > tempLen) break strings;
 942                 lastLen = tempLen;
 943                 if (!it.hasNext()) break;
 944                 trial = (String) it.next();
 945             }
 946         }
 947         if (lastLen < 2) {
 948             int cp = UTF16.charAt(text, offset);
 949             if (contains(cp)) {
 950                 lastLen = UTF16.getCharCount(cp);
 951             }
 952         }
 953         return offset+lastLen;
 954     }
 955
 956     /**
 957      * Does one string contain another, starting at a specific offset?
 958      * @param text
 959      * @param offset
 960      * @param other
 961      * @return
 962      */
 963     // Note: This method was moved from CollectionUtilities
 964     private static int matchesAt(CharSequence text, int offset, CharSequence other) {
 965         int len = other.length();
 966         int i = 0;
 967         int j = offset;
 968         for (; i < len; ++i, ++j) {
 969             char pc = other.charAt(i);
 970             char tc = text.charAt(j);
 971             if (pc != tc) return -1;
 972         }
 973         return i;
 974     }
 975 //#endif
 976
 977     /**
 978      * Implementation of UnicodeMatcher API.  Union the set of all
 979      * characters that may be matched by this object into the given
 980      * set.
 981      * @param toUnionTo the set into which to union the source characters
 982      * @stable ICU 2.2
 983      */
 984     public void addMatchSetTo(UnicodeSet toUnionTo) {
 985         toUnionTo.addAll(this);
 986     }
 987
 988     /**
 989      * Returns the index of the given character within this set, where
 990      * the set is ordered by ascending code point.  If the character
 991      * is not in this set, return -1.  The inverse of this method is
 992      * <code>charAt()</code>.
 993      * @return an index from 0..size()-1, or -1
 994      * @stable ICU 2.0
 995      */
 996     public int indexOf(int c) {
 997         if (c < MIN_VALUE || c > MAX_VALUE) {
 998             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(c, 6));
 999         }
1000         int i = 0;
1001         int n = 0;
1002         for (;;) {
1003             int start = list[i++];
1004             if (c < start) {
1005                 return -1;
1006             }
1007             int limit = list[i++];
1008             if (c < limit) {
1009                 return n + c - start;
1010             }
1011             n += limit - start;
1012         }
1013     }
1014
1015     /**
1016      * Returns the character at the given index within this set, where
1017      * the set is ordered by ascending code point.  If the index is
1018      * out of range, return -1.  The inverse of this method is
1019      * <code>indexOf()</code>.
1020      * @param index an index from 0..size()-1
1021      * @return the character at the given index, or -1.
1022      * @stable ICU 2.0
1023      */
1024     public int charAt(int index) {
1025         if (index >= 0) {
1026             // len2 is the largest even integer <= len, that is, it is len
1027             // for even values and len-1 for odd values.  With odd values
1028             // the last entry is UNICODESET_HIGH.
1029             int len2 = len & ~1;
1030             for (int i=0; i < len2;) {
1031                 int start = list[i++];
1032                 int count = list[i++] - start;
1033                 if (index < count) {
1034                     return start + index;
1035                 }
1036                 index -= count;
1037             }
1038         }
1039         return -1;
1040     }
1041
1042     /**
1043      * Adds the specified range to this set if it is not already
1044      * present.  If this set already contains the specified range,
1045      * the call leaves this set unchanged.  If <code>end > start</code>
1046      * then an empty range is added, leaving the set unchanged.
1047      *
1048      * @param start first character, inclusive, of range to be added
1049      * to this set.
1050      * @param end last character, inclusive, of range to be added
1051      * to this set.
1052      * @stable ICU 2.0
1053      */
1054     public UnicodeSet add(int start, int end) {
1055         checkFrozen();
1056         return add_unchecked(start, end);
1057     }
1058
1059     // for internal use, after checkFrozen has been called
1060     private UnicodeSet add_unchecked(int start, int end) {
1061         if (start < MIN_VALUE || start > MAX_VALUE) {
1062             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
1063         }
1064         if (end < MIN_VALUE || end > MAX_VALUE) {
1065             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
1066         }
1067         if (start < end) {
1068             add(range(start, end), 2, 0);
1069         } else if (start == end) {
1070             add(start);
1071         }
1072         return this;
1073     }
1074
1075 //    /**
1076 //     * Format out the inversion list as a string, for debugging.  Uncomment when
1077 //     * needed.
1078 //     */
1079 //    public final String dump() {
1080 //        StringBuffer buf = new StringBuffer("[");
1081 //        for (int i=0; i<len; ++i) {
1082 //            if (i != 0) buf.append(", ");
1083 //            int c = list[i];
1084 //            //if (c <= 0x7F && c != '\n' && c != '\r' && c != '\t' && c != ' ') {
1085 //            //    buf.append((char) c);
1086 //            //} else {
1087 //                buf.append("U+").append(Utility.hex(c, (c<0x10000)?4:6));
1088 //            //}
1089 //        }
1090 //        buf.append("]");
1091 //        return buf.toString();
1092 //    }
1093
1094     /**
1095      * Adds the specified character to this set if it is not already
1096      * present.  If this set already contains the specified character,
1097      * the call leaves this set unchanged.
1098      * @stable ICU 2.0
1099      */
1100     public final UnicodeSet add(int c) {
1101         checkFrozen();
1102         return add_unchecked(c);
1103     }
1104
1105     // for internal use only, after checkFrozen has been called
1106     private final UnicodeSet add_unchecked(int c) {
1107         if (c < MIN_VALUE || c > MAX_VALUE) {
1108             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(c, 6));
1109         }
1110
1111         // find smallest i such that c < list[i]
1112         // if odd, then it is IN the set
1113         // if even, then it is OUT of the set
1114         int i = findCodePoint(c);
1115
1116         // already in set?
1117         if ((i & 1) != 0) return this;
1118
1119         // HIGH is 0x110000
1120         // assert(list[len-1] == HIGH);
1121
1122         // empty = [HIGH]
1123         // [start_0, limit_0, start_1, limit_1, HIGH]
1124
1125         // [..., start_k-1, limit_k-1, start_k, limit_k, ..., HIGH]
1126         //                             ^
1127         //                             list[i]
1128
1129         // i == 0 means c is before the first range
1130
1131         if (c == list[i]-1) {
1132             // c is before start of next range
1133             list[i] = c;
1134             // if we touched the HIGH mark, then add a new one
1135             if (c == MAX_VALUE) {
1136                 ensureCapacity(len+1);
1137                 list[len++] = HIGH;
1138             }
1139             if (i > 0 && c == list[i-1]) {
1140                 // collapse adjacent ranges
1141
1142                 // [..., start_k-1, c, c, limit_k, ..., HIGH]
1143                 //                     ^
1144                 //                     list[i]
1145                 System.arraycopy(list, i+1, list, i-1, len-i-1);
1146                 len -= 2;
1147             }
1148         }
1149
1150         else if (i > 0 && c == list[i-1]) {
1151             // c is after end of prior range
1152             list[i-1]++;
1153             // no need to chcek for collapse here
1154         }
1155
1156         else {
1157             // At this point we know the new char is not adjacent to
1158             // any existing ranges, and it is not 10FFFF.
1159
1160
1161             // [..., start_k-1, limit_k-1, start_k, limit_k, ..., HIGH]
1162             //                             ^
1163             //                             list[i]
1164
1165             // [..., start_k-1, limit_k-1, c, c+1, start_k, limit_k, ..., HIGH]
1166             //                             ^
1167             //                             list[i]
1168
1169             // Don't use ensureCapacity() to save on copying.
1170             // NOTE: This has no measurable impact on performance,
1171             // but it might help in some usage patterns.
1172             if (len+2 > list.length) {
1173                 int[] temp = new int[len + 2 + GROW_EXTRA];
1174                 if (i != 0) System.arraycopy(list, 0, temp, 0, i);
1175                 System.arraycopy(list, i, temp, i+2, len-i);
1176                 list = temp;
1177             } else {
1178                 System.arraycopy(list, i, list, i+2, len-i);
1179             }
1180
1181             list[i] = c;
1182             list[i+1] = c+1;
1183             len += 2;
1184         }
1185
1186         pat = null;
1187         return this;
1188     }
1189
1190     /**
1191      * Adds the specified multicharacter to this set if it is not already
1192      * present.  If this set already contains the multicharacter,
1193      * the call leaves this set unchanged.
1194      * Thus "ch" => {"ch"}
1195      * <br><b>Warning: you cannot add an empty string ("") to a UnicodeSet.</b>
1196      * @param s the source string
1197      * @return this object, for chaining
1198      * @stable ICU 2.0
1199      */
1200     public final UnicodeSet add(String s) {
1201         checkFrozen();
1202         int cp = getSingleCP(s);
1203         if (cp < 0) {
1204             strings.add(s);
1205             pat = null;
1206         } else {
1207             add_unchecked(cp, cp);
1208         }
1209         return this;
1210     }
1211
1212     /**
1213      * @return a code point IF the string consists of a single one.
1214      * otherwise returns -1.
1215      * @param string to test
1216      */
1217     private static int getSingleCP(String s) {
1218         if (s.length() < 1) {
1219             throw new IllegalArgumentException("Can't use zero-length strings in UnicodeSet");
1220         }
1221         if (s.length() > 2) return -1;
1222         if (s.length() == 1) return s.charAt(0);
1223
1224         // at this point, len = 2
1225         int cp = UTF16.charAt(s, 0);
1226         if (cp > 0xFFFF) { // is surrogate pair
1227             return cp;
1228         }
1229         return -1;
1230     }
1231
1232     /**
1233      * Adds each of the characters in this string to the set. Thus "ch" => {"c", "h"}
1234      * If this set already any particular character, it has no effect on that character.
1235      * @param s the source string
1236      * @return this object, for chaining
1237      * @stable ICU 2.0
1238      */
1239     public final UnicodeSet addAll(String s) {
1240         checkFrozen();
1241         int cp;
1242         for (int i = 0; i < s.length(); i += UTF16.getCharCount(cp)) {
1243             cp = UTF16.charAt(s, i);
1244             add_unchecked(cp, cp);
1245         }
1246         return this;
1247     }
1248
1249     /**
1250      * Retains EACH of the characters in this string. Note: "ch" == {"c", "h"}
1251      * If this set already any particular character, it has no effect on that character.
1252      * @param s the source string
1253      * @return this object, for chaining
1254      * @stable ICU 2.0
1255      */
1256     public final UnicodeSet retainAll(String s) {
1257         return retainAll(fromAll(s));
1258     }
1259
1260     /**
1261      * Complement EACH of the characters in this string. Note: "ch" == {"c", "h"}
1262      * If this set already any particular character, it has no effect on that character.
1263      * @param s the source string
1264      * @return this object, for chaining
1265      * @stable ICU 2.0
1266      */
1267     public final UnicodeSet complementAll(String s) {
1268         return complementAll(fromAll(s));
1269     }
1270
1271     /**
1272      * Remove EACH of the characters in this string. Note: "ch" == {"c", "h"}
1273      * If this set already any particular character, it has no effect on that character.
1274      * @param s the source string
1275      * @return this object, for chaining
1276      * @stable ICU 2.0
1277      */
1278     public final UnicodeSet removeAll(String s) {
1279         return removeAll(fromAll(s));
1280     }
1281
1282     /**
1283      * Remove all strings from this UnicodeSet
1284      * @return this object, for chaining
1285      * @draft ICU 4.2
1286      * @provisional This API might change or be removed in a future release.
1287      */
1288     public final UnicodeSet removeAllStrings() {
1289         checkFrozen();
1290         if (strings.size() != 0) {
1291             strings.clear();
1292             pat = null;
1293         }
1294         return this;
1295     }
1296
1297     /**
1298      * Makes a set from a multicharacter string. Thus "ch" => {"ch"}
1299      * <br><b>Warning: you cannot add an empty string ("") to a UnicodeSet.</b>
1300      * @param s the source string
1301      * @return a newly created set containing the given string
1302      * @stable ICU 2.0
1303      */
1304     public static UnicodeSet from(String s) {
1305         return new UnicodeSet().add(s);
1306     }
1307
1308
1309     /**
1310      * Makes a set from each of the characters in the string. Thus "ch" => {"c", "h"}
1311      * @param s the source string
1312      * @return a newly created set containing the given characters
1313      * @stable ICU 2.0
1314      */
1315     public static UnicodeSet fromAll(String s) {
1316         return new UnicodeSet().addAll(s);
1317     }
1318
1319
1320     /**
1321      * Retain only the elements in this set that are contained in the
1322      * specified range.  If <code>end > start</code> then an empty range is
1323      * retained, leaving the set empty.
1324      *
1325      * @param start first character, inclusive, of range to be retained
1326      * to this set.
1327      * @param end last character, inclusive, of range to be retained
1328      * to this set.
1329      * @stable ICU 2.0
1330      */
1331     public UnicodeSet retain(int start, int end) {
1332         checkFrozen();
1333         if (start < MIN_VALUE || start > MAX_VALUE) {
1334             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
1335         }
1336         if (end < MIN_VALUE || end > MAX_VALUE) {
1337             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
1338         }
1339         if (start <= end) {
1340             retain(range(start, end), 2, 0);
1341         } else {
1342             clear();
1343         }
1344         return this;
1345     }
1346
1347     /**
1348      * Retain the specified character from this set if it is present.
1349      * Upon return this set will be empty if it did not contain c, or
1350      * will only contain c if it did contain c.
1351      * @param c the character to be retained
1352      * @return this object, for chaining
1353      * @stable ICU 2.0
1354      */
1355     public final UnicodeSet retain(int c) {
1356         return retain(c, c);
1357     }
1358
1359     /**
1360      * Retain the specified string in this set if it is present.
1361      * Upon return this set will be empty if it did not contain s, or
1362      * will only contain s if it did contain s.
1363      * @param s the string to be retained
1364      * @return this object, for chaining
1365      * @stable ICU 2.0
1366      */
1367     public final UnicodeSet retain(String s) {
1368         int cp = getSingleCP(s);
1369         if (cp < 0) {
1370             boolean isIn = strings.contains(s);
1371             if (isIn && size() == 1) {
1372                 return this;
1373             }
1374             clear();
1375             strings.add(s);
1376             pat = null;
1377         } else {
1378             retain(cp, cp);
1379         }
1380         return this;
1381     }
1382
1383     /**
1384      * Removes the specified range from this set if it is present.
1385      * The set will not contain the specified range once the call
1386      * returns.  If <code>end > start</code> then an empty range is
1387      * removed, leaving the set unchanged.
1388      *
1389      * @param start first character, inclusive, of range to be removed
1390      * from this set.
1391      * @param end last character, inclusive, of range to be removed
1392      * from this set.
1393      * @stable ICU 2.0
1394      */
1395     public UnicodeSet remove(int start, int end) {
1396         checkFrozen();
1397         if (start < MIN_VALUE || start > MAX_VALUE) {
1398             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
1399         }
1400         if (end < MIN_VALUE || end > MAX_VALUE) {
1401             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
1402         }
1403         if (start <= end) {
1404             retain(range(start, end), 2, 2);
1405         }
1406         return this;
1407     }
1408
1409     /**
1410      * Removes the specified character from this set if it is present.
1411      * The set will not contain the specified character once the call
1412      * returns.
1413      * @param c the character to be removed
1414      * @return this object, for chaining
1415      * @stable ICU 2.0
1416      */
1417     public final UnicodeSet remove(int c) {
1418         return remove(c, c);
1419     }
1420
1421     /**
1422      * Removes the specified string from this set if it is present.
1423      * The set will not contain the specified string once the call
1424      * returns.
1425      * @param s the string to be removed
1426      * @return this object, for chaining
1427      * @stable ICU 2.0
1428      */
1429     public final UnicodeSet remove(String s) {
1430         int cp = getSingleCP(s);
1431         if (cp < 0) {
1432             strings.remove(s);
1433             pat = null;
1434         } else {
1435             remove(cp, cp);
1436         }
1437         return this;
1438     }
1439
1440     /**
1441      * Complements the specified range in this set.  Any character in
1442      * the range will be removed if it is in this set, or will be
1443      * added if it is not in this set.  If <code>end > start</code>
1444      * then an empty range is complemented, leaving the set unchanged.
1445      *
1446      * @param start first character, inclusive, of range to be removed
1447      * from this set.
1448      * @param end last character, inclusive, of range to be removed
1449      * from this set.
1450      * @stable ICU 2.0
1451      */
1452     public UnicodeSet complement(int start, int end) {
1453         checkFrozen();
1454         if (start < MIN_VALUE || start > MAX_VALUE) {
1455             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
1456         }
1457         if (end < MIN_VALUE || end > MAX_VALUE) {
1458             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
1459         }
1460         if (start <= end) {
1461             xor(range(start, end), 2, 0);
1462         }
1463         pat = null;
1464         return this;
1465     }
1466
1467     /**
1468      * Complements the specified character in this set.  The character
1469      * will be removed if it is in this set, or will be added if it is
1470      * not in this set.
1471      * @stable ICU 2.0
1472      */
1473     public final UnicodeSet complement(int c) {
1474         return complement(c, c);
1475     }
1476
1477     /**
1478      * This is equivalent to
1479      * <code>complement(MIN_VALUE, MAX_VALUE)</code>.
1480      * @stable ICU 2.0
1481      */
1482     public UnicodeSet complement() {
1483         checkFrozen();
1484         if (list[0] == LOW) {
1485             System.arraycopy(list, 1, list, 0, len-1);
1486             --len;
1487         } else {
1488             ensureCapacity(len+1);
1489             System.arraycopy(list, 0, list, 1, len);
1490             list[0] = LOW;
1491             ++len;
1492         }
1493         pat = null;
1494         return this;
1495     }
1496
1497     /**
1498      * Complement the specified string in this set.
1499      * The set will not contain the specified string once the call
1500      * returns.
1501      * <br><b>Warning: you cannot add an empty string ("") to a UnicodeSet.</b>
1502      * @param s the string to complement
1503      * @return this object, for chaining
1504      * @stable ICU 2.0
1505      */
1506     public final UnicodeSet complement(String s) {
1507         checkFrozen();
1508         int cp = getSingleCP(s);
1509         if (cp < 0) {
1510             if (strings.contains(s)) strings.remove(s);
1511             else strings.add(s);
1512             pat = null;
1513         } else {
1514             complement(cp, cp);
1515         }
1516         return this;
1517     }
1518
1519     /**
1520      * Returns true if this set contains the given character.
1521      * @param c character to be checked for containment
1522      * @return true if the test condition is met
1523      * @stable ICU 2.0
1524      */
1525     public boolean contains(int c) {
1526         if (c < MIN_VALUE || c > MAX_VALUE) {
1527             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(c, 6));
1528         }
1529
1530         /*
1531         // Set i to the index of the start item greater than ch
1532         // We know we will terminate without length test!
1533         int i = -1;
1534         while (true) {
1535             if (c < list[++i]) break;
1536         }
1537         */
1538
1539         int i = findCodePoint(c);
1540
1541         return ((i & 1) != 0); // return true if odd
1542     }
1543
1544     /**
1545      * Returns the smallest value i such that c < list[i].  Caller
1546      * must ensure that c is a legal value or this method will enter
1547      * an infinite loop.  This method performs a binary search.
1548      * @param c a character in the range MIN_VALUE..MAX_VALUE
1549      * inclusive
1550      * @return the smallest integer i in the range 0..len-1,
1551      * inclusive, such that c < list[i]
1552      */
1553     private final int findCodePoint(int c) {
1554         /* Examples:
1555                                            findCodePoint(c)
1556            set              list[]         c=0 1 3 4 7 8
1557            ===              ==============   ===========
1558            []               [110000]         0 0 0 0 0 0
1559            [\u0000-\u0003]  [0, 4, 110000]   1 1 1 2 2 2
1560            [\u0004-\u0007]  [4, 8, 110000]   0 0 0 1 1 2
1561            [:all:]          [0, 110000]      1 1 1 1 1 1
1562          */
1563
1564         // Return the smallest i such that c < list[i].  Assume
1565         // list[len - 1] == HIGH and that c is legal (0..HIGH-1).
1566         if (c < list[0]) return 0;
1567         // High runner test.  c is often after the last range, so an
1568         // initial check for this condition pays off.
1569         if (len >= 2 && c >= list[len-2]) return len-1;
1570         int lo = 0;
1571         int hi = len - 1;
1572         // invariant: c >= list[lo]
1573         // invariant: c < list[hi]
1574         for (;;) {
1575             int i = (lo + hi) >>> 1;
1576             if (i == lo) return hi;
1577             if (c < list[i]) {
1578                 hi = i;
1579             } else {
1580                 lo = i;
1581             }
1582         }
1583     }
1584
1585 //    //----------------------------------------------------------------
1586 //    // Unrolled binary search
1587 //    //----------------------------------------------------------------
1588 //
1589 //    private int validLen = -1; // validated value of len
1590 //    private int topOfLow;
1591 //    private int topOfHigh;
1592 //    private int power;
1593 //    private int deltaStart;
1594 //
1595 //    private void validate() {
1596 //        if (len <= 1) {
1597 //            throw new IllegalArgumentException("list.len==" + len + "; must be >1");
1598 //        }
1599 //
1600 //        // find greatest power of 2 less than or equal to len
1601 //        for (power = exp2.length-1; power > 0 && exp2[power] > len; power--) {}
1602 //
1603 //        // assert(exp2[power] <= len);
1604 //
1605 //        // determine the starting points
1606 //        topOfLow = exp2[power] - 1;
1607 //        topOfHigh = len - 1;
1608 //        deltaStart = exp2[power-1];
1609 //        validLen = len;
1610 //    }
1611 //
1612 //    private static final int exp2[] = {
1613 //        0x1, 0x2, 0x4, 0x8,
1614 //        0x10, 0x20, 0x40, 0x80,
1615 //        0x100, 0x200, 0x400, 0x800,
1616 //        0x1000, 0x2000, 0x4000, 0x8000,
1617 //        0x10000, 0x20000, 0x40000, 0x80000,
1618 //        0x100000, 0x200000, 0x400000, 0x800000,
1619 //        0x1000000, 0x2000000, 0x4000000, 0x8000000,
1620 //        0x10000000, 0x20000000 // , 0x40000000 // no unsigned int in Java
1621 //    };
1622 //
1623 //    /**
1624 //     * Unrolled lowest index GT.
1625 //     */
1626 //    private final int leastIndexGT(int searchValue) {
1627 //
1628 //        if (len != validLen) {
1629 //            if (len == 1) return 0;
1630 //            validate();
1631 //        }
1632 //        int temp;
1633 //
1634 //        // set up initial range to search. Each subrange is a power of two in length
1635 //        int high = searchValue < list[topOfLow] ? topOfLow : topOfHigh;
1636 //
1637 //        // Completely unrolled binary search, folhighing "Programming Pearls"
1638 //        // Each case deliberately falls through to the next
1639 //        // Logically, list[-1] < all_search_values && list[count] > all_search_values
1640 //        // although the values -1 and count are never actually touched.
1641 //
1642 //        // The bounds at each point are low & high,
1643 //        // where low == high - delta*2
1644 //        // so high - delta is the midpoint
1645 //
1646 //        // The invariant AFTER each line is that list[low] < searchValue <= list[high]
1647 //
1648 //        switch (power) {
1649 //        //case 31: if (searchValue < list[temp = high-0x40000000]) high = temp; // no unsigned int in Java
1650 //        case 30: if (searchValue < list[temp = high-0x20000000]) high = temp;
1651 //        case 29: if (searchValue < list[temp = high-0x10000000]) high = temp;
1652 //
1653 //        case 28: if (searchValue < list[temp = high- 0x8000000]) high = temp;
1654 //        case 27: if (searchValue < list[temp = high- 0x4000000]) high = temp;
1655 //        case 26: if (searchValue < list[temp = high- 0x2000000]) high = temp;
1656 //        case 25: if (searchValue < list[temp = high- 0x1000000]) high = temp;
1657 //
1658 //        case 24: if (searchValue < list[temp = high-  0x800000]) high = temp;
1659 //        case 23: if (searchValue < list[temp = high-  0x400000]) high = temp;
1660 //        case 22: if (searchValue < list[temp = high-  0x200000]) high = temp;
1661 //        case 21: if (searchValue < list[temp = high-  0x100000]) high = temp;
1662 //
1663 //        case 20: if (searchValue < list[temp = high-   0x80000]) high = temp;
1664 //        case 19: if (searchValue < list[temp = high-   0x40000]) high = temp;
1665 //        case 18: if (searchValue < list[temp = high-   0x20000]) high = temp;
1666 //        case 17: if (searchValue < list[temp = high-   0x10000]) high = temp;
1667 //
1668 //        case 16: if (searchValue < list[temp = high-    0x8000]) high = temp;
1669 //        case 15: if (searchValue < list[temp = high-    0x4000]) high = temp;
1670 //        case 14: if (searchValue < list[temp = high-    0x2000]) high = temp;
1671 //        case 13: if (searchValue < list[temp = high-    0x1000]) high = temp;
1672 //
1673 //        case 12: if (searchValue < list[temp = high-     0x800]) high = temp;
1674 //        case 11: if (searchValue < list[temp = high-     0x400]) high = temp;
1675 //        case 10: if (searchValue < list[temp = high-     0x200]) high = temp;
1676 //        case  9: if (searchValue < list[temp = high-     0x100]) high = temp;
1677 //
1678 //        case  8: if (searchValue < list[temp = high-      0x80]) high = temp;
1679 //        case  7: if (searchValue < list[temp = high-      0x40]) high = temp;
1680 //        case  6: if (searchValue < list[temp = high-      0x20]) high = temp;
1681 //        case  5: if (searchValue < list[temp = high-      0x10]) high = temp;
1682 //
1683 //        case  4: if (searchValue < list[temp = high-       0x8]) high = temp;
1684 //        case  3: if (searchValue < list[temp = high-       0x4]) high = temp;
1685 //        case  2: if (searchValue < list[temp = high-       0x2]) high = temp;
1686 //        case  1: if (searchValue < list[temp = high-       0x1]) high = temp;
1687 //        }
1688 //
1689 //        return high;
1690 //    }
1691 //
1692 //    // For debugging only
1693 //    public int len() {
1694 //        return len;
1695 //    }
1696 //
1697 //    //----------------------------------------------------------------
1698 //    //----------------------------------------------------------------
1699
1700     /**
1701      * Returns true if this set contains every character
1702      * of the given range.
1703      * @param start first character, inclusive, of the range
1704      * @param end last character, inclusive, of the range
1705      * @return true if the test condition is met
1706      * @stable ICU 2.0
1707      */
1708     public boolean contains(int start, int end) {
1709         if (start < MIN_VALUE || start > MAX_VALUE) {
1710             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
1711         }
1712         if (end < MIN_VALUE || end > MAX_VALUE) {
1713             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
1714         }
1715         //int i = -1;
1716         //while (true) {
1717         //    if (start < list[++i]) break;
1718         //}
1719         int i = findCodePoint(start);
1720         return ((i & 1) != 0 && end < list[i]);
1721     }
1722
1723     /**
1724      * Returns <tt>true</tt> if this set contains the given
1725      * multicharacter string.
1726      * @param s string to be checked for containment
1727      * @return <tt>true</tt> if this set contains the specified string
1728      * @stable ICU 2.0
1729      */
1730     public final boolean contains(String s) {
1731
1732         int cp = getSingleCP(s);
1733         if (cp < 0) {
1734             return strings.contains(s);
1735         } else {
1736             return contains(cp);
1737         }
1738     }
1739
1740     /**
1741      * Returns true if this set contains all the characters and strings
1742      * of the given set.
1743      * @param b set to be checked for containment
1744      * @return true if the test condition is met
1745      * @stable ICU 2.0
1746      */
1747     public boolean containsAll(UnicodeSet b) {
1748       // The specified set is a subset if all of its pairs are contained in
1749       // this set. This implementation accesses the lists directly for speed.
1750       // TODO: this could be faster if size() were cached. But that would affect building speed
1751       // so it needs investigation.
1752       int[] listB = b.list;
1753       boolean needA = true;
1754       boolean needB = true;
1755       int aPtr = 0;
1756       int bPtr = 0;
1757       int aLen = len - 1;
1758       int bLen = b.len - 1;
1759       int startA = 0, startB = 0, limitA = 0, limitB = 0;
1760       while (true) {
1761         // double iterations are such a pain...
1762         if (needA) {
1763           if (aPtr >= aLen) {
1764             // ran out of A. If B is also exhausted, then break;
1765             if (needB && bPtr >= bLen) {
1766               break;
1767             }
1768             return false;
1769           }
1770           startA = list[aPtr++];
1771           limitA = list[aPtr++];
1772         }
1773         if (needB) {
1774           if (bPtr >= bLen) {
1775             // ran out of B. Since we got this far, we have an A and we are ok so far
1776             break;
1777           }
1778           startB = listB[bPtr++];
1779           limitB = listB[bPtr++];
1780         }
1781         // if B doesn't overlap and is greater than A, get new A
1782         if (startB >= limitA) {
1783           needA = true;
1784           needB = false;
1785           continue;
1786         }
1787         // if B is wholy contained in A, then get a new B
1788         if (startB >= startA && limitB <= limitA) {
1789           needA = false;
1790           needB = true;
1791           continue;
1792         }
1793         // all other combinations mean we fail
1794         return false;
1795       }
1796
1797       if (!strings.containsAll(b.strings)) return false;
1798       return true;
1799   }
1800
1801 //    /**
1802 //     * Returns true if this set contains all the characters and strings
1803 //     * of the given set.
1804 //     * @param c set to be checked for containment
1805 //     * @return true if the test condition is met
1806 //     * @stable ICU 2.0
1807 //     */
1808 //    public boolean containsAllOld(UnicodeSet c) {
1809 //        // The specified set is a subset if all of its pairs are contained in
1810 //        // this set.  It's possible to code this more efficiently in terms of
1811 //        // direct manipulation of the inversion lists if the need arises.
1812 //        int n = c.getRangeCount();
1813 //        for (int i=0; i<n; ++i) {
1814 //            if (!contains(c.getRangeStart(i), c.getRangeEnd(i))) {
1815 //                return false;
1816 //            }
1817 //        }
1818 //        if (!strings.containsAll(c.strings)) return false;
1819 //        return true;
1820 //    }
1821
1822     /**
1823      * Returns true if there is a partition of the string such that this set contains each of the partitioned strings.
1824      * For example, for the Unicode set [a{bc}{cd}]<br>
1825      * containsAll is true for each of: "a", "bc", ""cdbca"<br>
1826      * containsAll is false for each of: "acb", "bcda", "bcx"<br>
1827      * @param s string containing characters to be checked for containment
1828      * @return true if the test condition is met
1829      * @stable ICU 2.0
1830      */
1831      public boolean containsAll(String s) {
1832         int cp;
1833         for (int i = 0; i < s.length(); i += UTF16.getCharCount(cp)) {
1834             cp = UTF16.charAt(s, i);
1835             if (!contains(cp))  {
1836                 if (strings.size() == 0) {
1837                     return false;
1838                 }
1839                 return containsAll(s, 0);
1840             }
1841         }
1842         return true;
1843     }
1844
1845     /**
1846      * Recursive routine called if we fail to find a match in containsAll, and there are strings
1847      * @param s source string
1848      * @param i point to match to the end on
1849      * @return true if ok
1850      */
1851     private boolean containsAll(String s, int i) {
1852         if (i >= s.length()) {
1853             return true;
1854         }
1855         int  cp= UTF16.charAt(s, i);
1856         if (contains(cp) && containsAll(s, i+UTF16.getCharCount(cp))) {
1857             return true;
1858         }
1859
1860         Iterator it = strings.iterator();
1861         while (it.hasNext()) {
1862             String setStr = (String)it.next();
1863             if (s.startsWith(setStr, i) &&  containsAll(s, i+setStr.length())) {
1864                 return true;
1865             }
1866         }
1867         return false;
1868
1869     }
1870
1871     /**
1872      * Get the Regex equivalent for this UnicodeSet
1873      * @return regex pattern equivalent to this UnicodeSet
1874      * @internal
1875      * @deprecated This API is ICU internal only.
1876      */
1877     public String getRegexEquivalent() {
1878         if (strings.size() == 0) return toString();
1879         StringBuffer result = new StringBuffer("(?:");
1880         _generatePattern(result, true, false);
1881         Iterator it = strings.iterator();
1882         while (it.hasNext()) {
1883             result.append('|');
1884             _appendToPat(result, (String) it.next(), true);
1885         }
1886         return result.append(")").toString();
1887     }
1888
1889     /**
1890      * Returns true if this set contains none of the characters
1891      * of the given range.
1892      * @param start first character, inclusive, of the range
1893      * @param end last character, inclusive, of the range
1894      * @return true if the test condition is met
1895      * @stable ICU 2.0
1896      */
1897     public boolean containsNone(int start, int end) {
1898         if (start < MIN_VALUE || start > MAX_VALUE) {
1899             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
1900         }
1901         if (end < MIN_VALUE || end > MAX_VALUE) {
1902             throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
1903         }
1904         int i = -1;
1905         while (true) {
1906             if (start < list[++i]) break;
1907         }
1908         return ((i & 1) == 0 && end < list[i]);
1909     }
1910
1911     /**
1912      * Returns true if none of the characters or strings in this UnicodeSet appears in the string.
1913      * For example, for the Unicode set [a{bc}{cd}]<br>
1914      * containsNone is true for: "xy", "cb"<br>
1915      * containsNone is false for: "a", "bc", "bcd"<br>
1916      * @param b set to be checked for containment
1917      * @return true if the test condition is met
1918      * @stable ICU 2.0
1919      */
1920     public boolean containsNone(UnicodeSet b) {
1921       // The specified set is a subset if some of its pairs overlap with some of this set's pairs.
1922       // This implementation accesses the lists directly for speed.
1923       int[] listB = b.list;
1924       boolean needA = true;
1925       boolean needB = true;
1926       int aPtr = 0;
1927       int bPtr = 0;
1928       int aLen = len - 1;
1929       int bLen = b.len - 1;
1930       int startA = 0, startB = 0, limitA = 0, limitB = 0;
1931       while (true) {
1932         // double iterations are such a pain...
1933         if (needA) {
1934           if (aPtr >= aLen) {
1935             // ran out of A: break so we test strings
1936             break;
1937           }
1938           startA = list[aPtr++];
1939           limitA = list[aPtr++];
1940         }
1941         if (needB) {
1942           if (bPtr >= bLen) {
1943             // ran out of B: break so we test strings
1944             break;
1945           }
1946           startB = listB[bPtr++];
1947           limitB = listB[bPtr++];
1948         }
1949         // if B is higher than any part of A, get new A
1950         if (startB >= limitA) {
1951           needA = true;
1952           needB = false;
1953           continue;
1954         }
1955         // if A is higher than any part of B, get new B
1956         if (startA >= limitB) {
1957           needA = false;
1958           needB = true;
1959           continue;
1960         }
1961         // all other combinations mean we fail
1962         return false;
1963       }
1964
1965       if (!SortedSetRelation.hasRelation(strings, SortedSetRelation.DISJOINT, b.strings)) return false;
1966       return true;
1967   }
1968
1969 //    /**
1970 //     * Returns true if none of the characters or strings in this UnicodeSet appears in the string.
1971 //     * For example, for the Unicode set [a{bc}{cd}]<br>
1972 //     * containsNone is true for: "xy", "cb"<br>
1973 //     * containsNone is false for: "a", "bc", "bcd"<br>
1974 //     * @param c set to be checked for containment
1975 //     * @return true if the test condition is met
1976 //     * @stable ICU 2.0
1977 //     */
1978 //    public boolean containsNoneOld(UnicodeSet c) {
1979 //        // The specified set is a subset if all of its pairs are contained in
1980 //        // this set.  It's possible to code this more efficiently in terms of
1981 //        // direct manipulation of the inversion lists if the need arises.
1982 //        int n = c.getRangeCount();
1983 //        for (int i=0; i<n; ++i) {
1984 //            if (!containsNone(c.getRangeStart(i), c.getRangeEnd(i))) {
1985 //                return false;
1986 //            }
1987 //        }
1988 //        if (!SortedSetRelation.hasRelation(strings, SortedSetRelation.DISJOINT, c.strings)) return false;
1989 //        return true;
1990 //    }
1991
1992     /**
1993      * Returns true if this set contains none of the characters
1994      * of the given string.
1995      * @param s string containing characters to be checked for containment
1996      * @return true if the test condition is met
1997      * @stable ICU 2.0
1998      */
1999     public boolean containsNone(String s) {
2000         int cp;
2001         for (int i = 0; i < s.length(); i += UTF16.getCharCount(cp)) {
2002             cp = UTF16.charAt(s, i);
2003             if (contains(cp)) return false;
2004         }
2005         if (strings.size() == 0) return true;
2006         // do a last check to make sure no strings are in.
2007         for (Iterator it = strings.iterator(); it.hasNext();) {
2008             String item = (String)it.next();
2009             if (s.indexOf(item) >= 0) return false;
2010         }
2011         return true;
2012     }
2013
2014     /**
2015      * Returns true if this set contains one or more of the characters
2016      * in the given range.
2017      * @param start first character, inclusive, of the range
2018      * @param end last character, inclusive, of the range
2019      * @return true if the condition is met
2020      * @stable ICU 2.0
2021      */
2022     public final boolean containsSome(int start, int end) {
2023         return !containsNone(start, end);
2024     }
2025
2026     /**
2027      * Returns true if this set contains one or more of the characters
2028      * and strings of the given set.
2029      * @param s set to be checked for containment
2030      * @return true if the condition is met
2031      * @stable ICU 2.0
2032      */
2033     public final boolean containsSome(UnicodeSet s) {
2034         return !containsNone(s);
2035     }
2036
2037     /**
2038      * Returns true if this set contains one or more of the characters
2039      * of the given string.
2040      * @param s string containing characters to be checked for containment
2041      * @return true if the condition is met
2042      * @stable ICU 2.0
2043      */
2044     public final boolean containsSome(String s) {
2045         return !containsNone(s);
2046     }
2047
2048
2049     /**
2050      * Adds all of the elements in the specified set to this set if
2051      * they're not already present.  This operation effectively
2052      * modifies this set so that its value is the <i>union</i> of the two
2053      * sets.  The behavior of this operation is unspecified if the specified
2054      * collection is modified while the operation is in progress.
2055      *
2056      * @param c set whose elements are to be added to this set.
2057      * @stable ICU 2.0
2058      */
2059     public UnicodeSet addAll(UnicodeSet c) {
2060         checkFrozen();
2061         add(c.list, c.len, 0);
2062         strings.addAll(c.strings);
2063         return this;
2064     }
2065
2066     /**
2067      * Retains only the elements in this set that are contained in the
2068      * specified set.  In other words, removes from this set all of
2069      * its elements that are not contained in the specified set.  This
2070      * operation effectively modifies this set so that its value is
2071      * the <i>intersection</i> of the two sets.
2072      *
2073      * @param c set that defines which elements this set will retain.
2074      * @stable ICU 2.0
2075      */
2076     public UnicodeSet retainAll(UnicodeSet c) {
2077         checkFrozen();
2078         retain(c.list, c.len, 0);
2079         strings.retainAll(c.strings);
2080         return this;
2081     }
2082
2083     /**
2084      * Removes from this set all of its elements that are contained in the
2085      * specified set.  This operation effectively modifies this
2086      * set so that its value is the <i>asymmetric set difference</i> of
2087      * the two sets.
2088      *
2089      * @param c set that defines which elements will be removed from
2090      *          this set.
2091      * @stable ICU 2.0
2092      */
2093     public UnicodeSet removeAll(UnicodeSet c) {
2094         checkFrozen();
2095         retain(c.list, c.len, 2);
2096         strings.removeAll(c.strings);
2097         return this;
2098     }
2099
2100     /**
2101      * Complements in this set all elements contained in the specified
2102      * set.  Any character in the other set will be removed if it is
2103      * in this set, or will be added if it is not in this set.
2104      *
2105      * @param c set that defines which elements will be complemented from
2106      *          this set.
2107      * @stable ICU 2.0
2108      */
2109     public UnicodeSet complementAll(UnicodeSet c) {
2110         checkFrozen();
2111         xor(c.list, c.len, 0);
2112         SortedSetRelation.doOperation(strings, SortedSetRelation.COMPLEMENTALL, c.strings);
2113         return this;
2114     }
2115
2116     /**
2117      * Removes all of the elements from this set.  This set will be
2118      * empty after this call returns.
2119      * @stable ICU 2.0
2120      */
2121     public UnicodeSet clear() {
2122         checkFrozen();
2123         list[0] = HIGH;
2124         len = 1;
2125         pat = null;
2126         strings.clear();
2127         return this;
2128     }
2129
2130     /**
2131      * Iteration method that returns the number of ranges contained in
2132      * this set.
2133      * @see #getRangeStart
2134      * @see #getRangeEnd
2135      * @stable ICU 2.0
2136      */
2137     public int getRangeCount() {
2138         return len/2;
2139     }
2140
2141     /**
2142      * Iteration method that returns the first character in the
2143      * specified range of this set.
2144      * @exception ArrayIndexOutOfBoundsException if index is outside
2145      * the range <code>0..getRangeCount()-1</code>
2146      * @see #getRangeCount
2147      * @see #getRangeEnd
2148      * @stable ICU 2.0
2149      */
2150     public int getRangeStart(int index) {
2151         return list[index*2];
2152     }
2153
2154     /**
2155      * Iteration method that returns the last character in the
2156      * specified range of this set.
2157      * @exception ArrayIndexOutOfBoundsException if index is outside
2158      * the range <code>0..getRangeCount()-1</code>
2159      * @see #getRangeStart
2160      * @see #getRangeEnd
2161      * @stable ICU 2.0
2162      */
2163     public int getRangeEnd(int index) {
2164         return (list[index*2 + 1] - 1);
2165     }
2166
2167     /**
2168      * Reallocate this objects internal structures to take up the least
2169      * possible space, without changing this object's value.
2170      * @stable ICU 2.0
2171      */
2172     public UnicodeSet compact() {
2173         checkFrozen();
2174         if (len != list.length) {
2175             int[] temp = new int[len];
2176             System.arraycopy(list, 0, temp, 0, len);
2177             list = temp;
2178         }
2179         rangeList = null;
2180         buffer = null;
2181         return this;
2182     }
2183
2184     /**
2185      * Compares the specified object with this set for equality.  Returns
2186      * <tt>true</tt> if the specified object is also a set, the two sets
2187      * have the same size, and every member of the specified set is
2188      * contained in this set (or equivalently, every member of this set is
2189      * contained in the specified set).
2190      *
2191      * @param o Object to be compared for equality with this set.
2192      * @return <tt>true</tt> if the specified Object is equal to this set.
2193      * @stable ICU 2.0
2194      */
2195     public boolean equals(Object o) {
2196         try {
2197             UnicodeSet that = (UnicodeSet) o;
2198             if (len != that.len) return false;
2199             for (int i = 0; i < len; ++i) {
2200                 if (list[i] != that.list[i]) return false;
2201             }
2202             if (!strings.equals(that.strings)) return false;
2203         } catch (Exception e) {
2204             return false;
2205         }
2206         return true;
2207     }
2208
2209     /**
2210      * Returns the hash code value for this set.
2211      *
2212      * @return the hash code value for this set.
2213      * @see java.lang.Object#hashCode()
2214      * @stable ICU 2.0
2215      */
2216     public int hashCode() {
2217         int result = len;
2218         for (int i = 0; i < len; ++i) {
2219             result *= 1000003;
2220             result += list[i];
2221         }
2222         return result;
2223     }
2224
2225     /**
2226      * Return a programmer-readable string representation of this object.
2227      * @stable ICU 2.0
2228      */
2229     public String toString() {
2230         return toPattern(true);
2231     }
2232
2233     //----------------------------------------------------------------
2234     // Implementation: Pattern parsing
2235     //----------------------------------------------------------------
2236
2237     /**
2238      * Parses the given pattern, starting at the given position.  The character
2239      * at pattern.charAt(pos.getIndex()) must be '[', or the parse fails.
2240      * Parsing continues until the corresponding closing ']'.  If a syntax error
2241      * is encountered between the opening and closing brace, the parse fails.
2242      * Upon return from a successful parse, the ParsePosition is updated to
2243      * point to the character following the closing ']', and an inversion
2244      * list for the parsed pattern is returned.  This method
2245      * calls itself recursively to parse embedded subpatterns.
2246      *
2247      * @param pattern the string containing the pattern to be parsed.  The
2248      * portion of the string from pos.getIndex(), which must be a '[', to the
2249      * corresponding closing ']', is parsed.
2250      * @param pos upon entry, the position at which to being parsing.  The
2251      * character at pattern.charAt(pos.getIndex()) must be a '['.  Upon return
2252      * from a successful parse, pos.getIndex() is either the character after the
2253      * closing ']' of the parsed pattern, or pattern.length() if the closing ']'
2254      * is the last character of the pattern string.
2255      * @return an inversion list for the parsed substring
2256      * of <code>pattern</code>
2257      * @exception java.lang.IllegalArgumentException if the parse fails.
2258      * @internal
2259      * @deprecated - for internal use only
2260      */
2261     public UnicodeSet applyPattern(String pattern,
2262                       ParsePosition pos,
2263                       SymbolTable symbols,
2264                       int options) {
2265
2266         // Need to build the pattern in a temporary string because
2267         // _applyPattern calls add() etc., which set pat to empty.
2268         boolean parsePositionWasNull = pos == null;
2269         if (parsePositionWasNull) {
2270             pos = new ParsePosition(0);
2271         }
2272
2273         StringBuffer rebuiltPat = new StringBuffer();
2274         RuleCharacterIterator chars =
2275             new RuleCharacterIterator(pattern, symbols, pos);
2276         applyPattern(chars, symbols, rebuiltPat, options);
2277         if (chars.inVariable()) {
2278             syntaxError(chars, "Extra chars in variable value");
2279         }
2280         pat = rebuiltPat.toString();
2281         if (parsePositionWasNull) {
2282             int i = pos.getIndex();
2283
2284             // Skip over trailing whitespace
2285             if ((options & IGNORE_SPACE) != 0) {
2286                 i = Utility.skipWhitespace(pattern, i);
2287             }
2288
2289             if (i != pattern.length()) {
2290                 throw new IllegalArgumentException("Parse of \"" + pattern +
2291                                                    "\" failed at " + i);
2292             }
2293         }
2294         return this;
2295     }
2296
2297     /**
2298      * Parse the pattern from the given RuleCharacterIterator.  The
2299      * iterator is advanced over the parsed pattern.
2300      * @param chars iterator over the pattern characters.  Upon return
2301      * it will be advanced to the first character after the parsed
2302      * pattern, or the end of the iteration if all characters are
2303      * parsed.
2304      * @param symbols symbol table to use to parse and dereference
2305      * variables, or null if none.
2306      * @param rebuiltPat the pattern that was parsed, rebuilt or
2307      * copied from the input pattern, as appropriate.
2308      * @param options a bit mask of zero or more of the following:
2309      * IGNORE_SPACE, CASE.
2310      */
2311     void applyPattern(RuleCharacterIterator chars, SymbolTable symbols,
2312                       StringBuffer rebuiltPat, int options) {
2313
2314         // Syntax characters: [ ] ^ - & { }
2315
2316         // Recognized special forms for chars, sets: c-c s-s s&s
2317
2318         int opts = RuleCharacterIterator.PARSE_VARIABLES |
2319                    RuleCharacterIterator.PARSE_ESCAPES;
2320         if ((options & IGNORE_SPACE) != 0) {
2321             opts |= RuleCharacterIterator.SKIP_WHITESPACE;
2322         }
2323
2324         StringBuffer patBuf = new StringBuffer(), buf = null;
2325         boolean usePat = false;
2326         UnicodeSet scratch = null;
2327         Object backup = null;
2328
2329         // mode: 0=before [, 1=between [...], 2=after ]
2330         // lastItem: 0=none, 1=char, 2=set
2331         int lastItem = 0, lastChar = 0, mode = 0;
2332         char op = 0;
2333
2334         boolean invert = false;
2335
2336         clear();
2337
2338         while (mode != 2 && !chars.atEnd()) {
2339             if (false) {
2340                 // Debugging assertion
2341                 if (!((lastItem == 0 && op == 0) ||
2342                       (lastItem == 1 && (op == 0 || op == '-')) ||
2343                       (lastItem == 2 && (op == 0 || op == '-' || op == '&')))) {
2344                     throw new IllegalArgumentException();
2345                 }
2346             }
2347
2348             int c = 0;
2349             boolean literal = false;
2350             UnicodeSet nested = null;
2351
2352             // -------- Check for property pattern
2353
2354             // setMode: 0=none, 1=unicodeset, 2=propertypat, 3=preparsed
2355             int setMode = 0;
2356             if (resemblesPropertyPattern(chars, opts)) {
2357                 setMode = 2;
2358             }
2359
2360             // -------- Parse '[' of opening delimiter OR nested set.
2361             // If there is a nested set, use `setMode' to define how
2362             // the set should be parsed.  If the '[' is part of the
2363             // opening delimiter for this pattern, parse special
2364             // strings "[", "[^", "[-", and "[^-".  Check for stand-in
2365             // characters representing a nested set in the symbol
2366             // table.
2367
2368             else {
2369                 // Prepare to backup if necessary
2370                 backup = chars.getPos(backup);
2371                 c = chars.next(opts);
2372                 literal = chars.isEscaped();
2373
2374                 if (c == '[' && !literal) {
2375                     if (mode == 1) {
2376                         chars.setPos(backup); // backup
2377                         setMode = 1;
2378                     } else {
2379                         // Handle opening '[' delimiter
2380                         mode = 1;
2381                         patBuf.append('[');
2382                         backup = chars.getPos(backup); // prepare to backup
2383                         c = chars.next(opts);
2384                         literal = chars.isEscaped();
2385                         if (c == '^' && !literal) {
2386                             invert = true;
2387                             patBuf.append('^');
2388                             backup = chars.getPos(backup); // prepare to backup
2389                             c = chars.next(opts);
2390                             literal = chars.isEscaped();
2391                         }
2392                         // Fall through to handle special leading '-';
2393                         // otherwise restart loop for nested [], \p{}, etc.
2394                         if (c == '-') {
2395                             literal = true;
2396                             // Fall through to handle literal '-' below
2397                         } else {
2398                             chars.setPos(backup); // backup
2399                             continue;
2400                         }
2401                     }
2402                 } else if (symbols != null) {
2403                      UnicodeMatcher m = symbols.lookupMatcher(c); // may be null
2404                      if (m != null) {
2405                          try {
2406                              nested = (UnicodeSet) m;
2407                              setMode = 3;
2408                          } catch (ClassCastException e) {
2409                              syntaxError(chars, "Syntax error");
2410                          }
2411                      }
2412                 }
2413             }
2414
2415             // -------- Handle a nested set.  This either is inline in
2416             // the pattern or represented by a stand-in that has
2417             // previously been parsed and was looked up in the symbol
2418             // table.
2419
2420             if (setMode != 0) {
2421                 if (lastItem == 1) {
2422                     if (op != 0) {
2423                         syntaxError(chars, "Char expected after operator");
2424                     }
2425                     add_unchecked(lastChar, lastChar);
2426                     _appendToPat(patBuf, lastChar, false);
2427                     lastItem = op = 0;
2428                 }
2429
2430                 if (op == '-' || op == '&') {
2431                     patBuf.append(op);
2432                 }
2433
2434                 if (nested == null) {
2435                     if (scratch == null) scratch = new UnicodeSet();
2436                     nested = scratch;
2437                 }
2438                 switch (setMode) {
2439                 case 1:
2440                     nested.applyPattern(chars, symbols, patBuf, options);
2441                     break;
2442                 case 2:
2443                     chars.skipIgnored(opts);
2444                     nested.applyPropertyPattern(chars, patBuf, symbols);
2445                     break;
2446                 case 3: // `nested' already parsed
2447                     nested._toPattern(patBuf, false);
2448                     break;
2449                 }
2450
2451                 usePat = true;
2452
2453                 if (mode == 0) {
2454                     // Entire pattern is a category; leave parse loop
2455                     set(nested);
2456                     mode = 2;
2457                     break;
2458                 }
2459
2460                 switch (op) {
2461                 case '-':
2462                     removeAll(nested);
2463                     break;
2464                 case '&':
2465                     retainAll(nested);
2466                     break;
2467                 case 0:
2468                     addAll(nested);
2469                     break;
2470                 }
2471
2472                 op = 0;
2473                 lastItem = 2;
2474
2475                 continue;
2476             }
2477
2478             if (mode == 0) {
2479                 syntaxError(chars, "Missing '['");
2480             }
2481
2482             // -------- Parse special (syntax) characters.  If the
2483             // current character is not special, or if it is escaped,
2484             // then fall through and handle it below.
2485
2486             if (!literal) {
2487                 switch (c) {
2488                 case ']':
2489                     if (lastItem == 1) {
2490                         add_unchecked(lastChar, lastChar);
2491                         _appendToPat(patBuf, lastChar, false);
2492                     }
2493                     // Treat final trailing '-' as a literal
2494                     if (op == '-') {
2495                         add_unchecked(op, op);
2496                         patBuf.append(op);
2497                     } else if (op == '&') {
2498                         syntaxError(chars, "Trailing '&'");
2499                     }
2500                     patBuf.append(']');
2501                     mode = 2;
2502                     continue;
2503                 case '-':
2504                     if (op == 0) {
2505                         if (lastItem != 0) {
2506                             op = (char) c;
2507                             continue;
2508                         } else {
2509                             // Treat final trailing '-' as a literal
2510                             add_unchecked(c, c);
2511                             c = chars.next(opts);
2512                             literal = chars.isEscaped();
2513                             if (c == ']' && !literal) {
2514                                 patBuf.append("-]");
2515                                 mode = 2;
2516                                 continue;
2517                             }
2518                         }
2519                     }
2520                     syntaxError(chars, "'-' not after char or set");
2521                 case '&':
2522                     if (lastItem == 2 && op == 0) {
2523                         op = (char) c;
2524                         continue;
2525                     }
2526                     syntaxError(chars, "'&' not after set");
2527                 case '^':
2528                     syntaxError(chars, "'^' not after '['");
2529                 case '{':
2530                     if (op != 0) {
2531                         syntaxError(chars, "Missing operand after operator");
2532                     }
2533                     if (lastItem == 1) {
2534                         add_unchecked(lastChar, lastChar);
2535                         _appendToPat(patBuf, lastChar, false);
2536                     }
2537                     lastItem = 0;
2538                     if (buf == null) {
2539                         buf = new StringBuffer();
2540                     } else {
2541                         buf.setLength(0);
2542                     }
2543                     boolean ok = false;
2544                     while (!chars.atEnd()) {
2545                         c = chars.next(opts);
2546                         literal = chars.isEscaped();
2547                         if (c == '}' && !literal) {
2548                             ok = true;
2549                             break;
2550                         }
2551                         UTF16.append(buf, c);
2552                     }
2553                     if (buf.length() < 1 || !ok) {
2554                         syntaxError(chars, "Invalid multicharacter string");
2555                     }
2556                     // We have new string. Add it to set and continue;
2557                     // we don't need to drop through to the further
2558                     // processing
2559                     add(buf.toString());
2560                     patBuf.append('{');
2561                     _appendToPat(patBuf, buf.toString(), false);
2562                     patBuf.append('}');
2563                     continue;
2564                 case SymbolTable.SYMBOL_REF:
2565                     //         symbols  nosymbols
2566                     // [a-$]   error    error (ambiguous)
2567                     // [a$]    anchor   anchor
2568                     // [a-$x]  var "x"* literal '$'
2569                     // [a-$.]  error    literal '$'
2570                     // *We won't get here in the case of var "x"
2571                     backup = chars.getPos(backup);
2572                     c = chars.next(opts);
2573                     literal = chars.isEscaped();
2574                     boolean anchor = (c == ']' && !literal);
2575                     if (symbols == null && !anchor) {
2576                         c = SymbolTable.SYMBOL_REF;
2577                         chars.setPos(backup);
2578                         break; // literal '$'
2579                     }
2580                     if (anchor && op == 0) {
2581                         if (lastItem == 1) {
2582                             add_unchecked(lastChar, lastChar);
2583                             _appendToPat(patBuf, lastChar, false);
2584                         }
2585                         add_unchecked(UnicodeMatcher.ETHER);
2586                         usePat = true;
2587                         patBuf.append(SymbolTable.SYMBOL_REF).append(']');
2588                         mode = 2;
2589                         continue;
2590                     }
2591                     syntaxError(chars, "Unquoted '$'");
2592                 default:
2593                     break;
2594                 }
2595             }
2596
2597             // -------- Parse literal characters.  This includes both
2598             // escaped chars ("\u4E01") and non-syntax characters
2599             // ("a").
2600
2601             switch (lastItem) {
2602             case 0:
2603                 lastItem = 1;
2604                 lastChar = c;
2605                 break;
2606             case 1:
2607                 if (op == '-') {
2608                     if (lastChar >= c) {
2609                         // Don't allow redundant (a-a) or empty (b-a) ranges;
2610                         // these are most likely typos.
2611                         syntaxError(chars, "Invalid range");
2612                     }
2613                     add_unchecked(lastChar, c);
2614                     _appendToPat(patBuf, lastChar, false);
2615                     patBuf.append(op);
2616                     _appendToPat(patBuf, c, false);
2617                     lastItem = op = 0;
2618                 } else {
2619                     add_unchecked(lastChar, lastChar);
2620                     _appendToPat(patBuf, lastChar, false);
2621                     lastChar = c;
2622                 }
2623                 break;
2624             case 2:
2625                 if (op != 0) {
2626                     syntaxError(chars, "Set expected after operator");
2627                 }
2628                 lastChar = c;
2629                 lastItem = 1;
2630                 break;
2631             }
2632         }
2633
2634         if (mode != 2) {
2635             syntaxError(chars, "Missing ']'");
2636         }
2637
2638         chars.skipIgnored(opts);
2639
2640         /**
2641          * Handle global flags (invert, case insensitivity).  If this
2642          * pattern should be compiled case-insensitive, then we need
2643          * to close over case BEFORE COMPLEMENTING.  This makes
2644          * patterns like /[^abc]/i work.
2645          */
2646         if ((options & CASE) != 0) {
2647             closeOver(CASE);
2648         }
2649         if (invert) {
2650             complement();
2651         }
2652
2653         // Use the rebuilt pattern (pat) only if necessary.  Prefer the
2654         // generated pattern.
2655         if (usePat) {
2656             rebuiltPat.append(patBuf.toString());
2657         } else {
2658             _generatePattern(rebuiltPat, false, true);
2659         }
2660     }
2661
2662     private static void syntaxError(RuleCharacterIterator chars, String msg) {
2663         throw new IllegalArgumentException("Error: " + msg + " at \"" +
2664                                            Utility.escape(chars.toString()) +
2665                                            '"');
2666     }
2667
2668     /**
2669      * Add the contents of the UnicodeSet (as strings) into a collection.
2670      * @param target collection to add into
2671      * @stable ICU 2.8
2672      */
2673     public void addAllTo(Collection target) {
2674         UnicodeSetIterator it = new UnicodeSetIterator(this);
2675         while (it.next()) {
2676             target.add(it.getString());
2677         }
2678     }
2679
2680     /**
2681      * Add the contents of the collection (as strings) into this UnicodeSet.
2682      * @param source the collection to add
2683      * @stable ICU 2.8
2684      */
2685     public void addAll(Collection source) {
2686         checkFrozen();
2687         Iterator it = source.iterator();
2688         while (it.hasNext()) {
2689             add(it.next().toString());
2690         }
2691     }
2692
2693     //----------------------------------------------------------------
2694     // Implementation: Utility methods
2695     //----------------------------------------------------------------
2696
2697     private void ensureCapacity(int newLen) {
2698         if (newLen <= list.length) return;
2699         int[] temp = new int[newLen + GROW_EXTRA];
2700         System.arraycopy(list, 0, temp, 0, len);
2701         list = temp;
2702     }
2703
2704     private void ensureBufferCapacity(int newLen) {
2705         if (buffer != null && newLen <= buffer.length) return;
2706         buffer = new int[newLen + GROW_EXTRA];
2707     }
2708
2709     /**
2710      * Assumes start <= end.
2711      */
2712     private int[] range(int start, int end) {
2713         if (rangeList == null) {
2714             rangeList = new int[] { start, end+1, HIGH };
2715         } else {
2716             rangeList[0] = start;
2717             rangeList[1] = end+1;
2718         }
2719         return rangeList;
2720     }
2721
2722     //----------------------------------------------------------------
2723     // Implementation: Fundamental operations
2724     //----------------------------------------------------------------
2725
2726     // polarity = 0, 3 is normal: x xor y
2727     // polarity = 1, 2: x xor ~y == x === y
2728
2729     private UnicodeSet xor(int[] other, int otherLen, int polarity) {
2730         ensureBufferCapacity(len + otherLen);
2731         int i = 0, j = 0, k = 0;
2732         int a = list[i++];
2733         int b;
2734         if (polarity == 1 || polarity == 2) {
2735             b = LOW;
2736             if (other[j] == LOW) { // skip base if already LOW
2737                 ++j;
2738                 b = other[j];
2739             }
2740         } else {
2741             b = other[j++];
2742         }
2743         // simplest of all the routines
2744         // sort the values, discarding identicals!
2745         while (true) {
2746             if (a < b) {
2747                 buffer[k++] = a;
2748                 a = list[i++];
2749             } else if (b < a) {
2750                 buffer[k++] = b;
2751                 b = other[j++];
2752             } else if (a != HIGH) { // at this point, a == b
2753                 // discard both values!
2754                 a = list[i++];
2755                 b = other[j++];
2756             } else { // DONE!
2757                 buffer[k++] = HIGH;
2758                 len = k;
2759                 break;
2760             }
2761         }
2762         // swap list and buffer
2763         int[] temp = list;
2764         list = buffer;
2765         buffer = temp;
2766         pat = null;
2767         return this;
2768     }
2769
2770     // polarity = 0 is normal: x union y
2771     // polarity = 2: x union ~y
2772     // polarity = 1: ~x union y
2773     // polarity = 3: ~x union ~y
2774
2775     private UnicodeSet add(int[] other, int otherLen, int polarity) {
2776         ensureBufferCapacity(len + otherLen);
2777         int i = 0, j = 0, k = 0;
2778         int a = list[i++];
2779         int b = other[j++];
2780         // change from xor is that we have to check overlapping pairs
2781         // polarity bit 1 means a is second, bit 2 means b is.
2782         main:
2783         while (true) {
2784             switch (polarity) {
2785               case 0: // both first; take lower if unequal
2786                 if (a < b) { // take a
2787                     // Back up over overlapping ranges in buffer[]
2788                     if (k > 0 && a <= buffer[k-1]) {
2789                         // Pick latter end value in buffer[] vs. list[]
2790                         a = max(list[i], buffer[--k]);
2791                     } else {
2792                         // No overlap
2793                         buffer[k++] = a;
2794                         a = list[i];
2795                     }
2796                     i++; // Common if/else code factored out
2797                     polarity ^= 1;
2798                 } else if (b < a) { // take b
2799                     if (k > 0 && b <= buffer[k-1]) {
2800                         b = max(other[j], buffer[--k]);
2801                     } else {
2802                         buffer[k++] = b;
2803                         b = other[j];
2804                     }
2805                     j++;
2806                     polarity ^= 2;
2807                 } else { // a == b, take a, drop b
2808                     if (a == HIGH) break main;
2809                     // This is symmetrical; it doesn't matter if
2810                     // we backtrack with a or b. - liu
2811                     if (k > 0 && a <= buffer[k-1]) {
2812                         a = max(list[i], buffer[--k]);
2813                     } else {
2814                         // No overlap
2815                         buffer[k++] = a;
2816                         a = list[i];
2817                     }
2818                     i++;
2819                     polarity ^= 1;
2820                     b = other[j++]; polarity ^= 2;
2821                 }
2822                 break;
2823               case 3: // both second; take higher if unequal, and drop other
2824                 if (b <= a) { // take a
2825                     if (a == HIGH) break main;
2826                     buffer[k++] = a;
2827                 } else { // take b
2828                     if (b == HIGH) break main;
2829                     buffer[k++] = b;
2830                 }
2831                 a = list[i++]; polarity ^= 1;   // factored common code
2832                 b = other[j++]; polarity ^= 2;
2833                 break;
2834               case 1: // a second, b first; if b < a, overlap
2835                 if (a < b) { // no overlap, take a
2836                     buffer[k++] = a; a = list[i++]; polarity ^= 1;
2837                 } else if (b < a) { // OVERLAP, drop b
2838                     b = other[j++]; polarity ^= 2;
2839                 } else { // a == b, drop both!
2840                     if (a == HIGH) break main;
2841                     a = list[i++]; polarity ^= 1;
2842                     b = other[j++]; polarity ^= 2;
2843                 }
2844                 break;
2845               case 2: // a first, b second; if a < b, overlap
2846                 if (b < a) { // no overlap, take b
2847                     buffer[k++] = b; b = other[j++]; polarity ^= 2;
2848                 } else  if (a < b) { // OVERLAP, drop a
2849                     a = list[i++]; polarity ^= 1;
2850                 } else { // a == b, drop both!
2851                     if (a == HIGH) break main;
2852                     a = list[i++]; polarity ^= 1;
2853                     b = other[j++]; polarity ^= 2;
2854                 }
2855                 break;
2856             }
2857         }
2858         buffer[k++] = HIGH;    // terminate
2859         len = k;
2860         // swap list and buffer
2861         int[] temp = list;
2862         list = buffer;
2863         buffer = temp;
2864         pat = null;
2865         return this;
2866     }
2867
2868     // polarity = 0 is normal: x intersect y
2869     // polarity = 2: x intersect ~y == set-minus
2870     // polarity = 1: ~x intersect y
2871     // polarity = 3: ~x intersect ~y
2872
2873     private UnicodeSet retain(int[] other, int otherLen, int polarity) {
2874         ensureBufferCapacity(len + otherLen);
2875         int i = 0, j = 0, k = 0;
2876         int a = list[i++];
2877         int b = other[j++];
2878         // change from xor is that we have to check overlapping pairs
2879         // polarity bit 1 means a is second, bit 2 means b is.
2880         main:
2881         while (true) {
2882             switch (polarity) {
2883               case 0: // both first; drop the smaller
2884                 if (a < b) { // drop a
2885                     a = list[i++]; polarity ^= 1;
2886                 } else if (b < a) { // drop b
2887                     b = other[j++]; polarity ^= 2;
2888                 } else { // a == b, take one, drop other
2889                     if (a == HIGH) break main;
2890                     buffer[k++] = a; a = list[i++]; polarity ^= 1;
2891                     b = other[j++]; polarity ^= 2;
2892                 }
2893                 break;
2894               case 3: // both second; take lower if unequal
2895                 if (a < b) { // take a
2896                     buffer[k++] = a; a = list[i++]; polarity ^= 1;
2897                 } else if (b < a) { // take b
2898                     buffer[k++] = b; b = other[j++]; polarity ^= 2;
2899                 } else { // a == b, take one, drop other
2900                     if (a == HIGH) break main;
2901                     buffer[k++] = a; a = list[i++]; polarity ^= 1;
2902                     b = other[j++]; polarity ^= 2;
2903                 }
2904                 break;
2905               case 1: // a second, b first;
2906                 if (a < b) { // NO OVERLAP, drop a
2907                     a = list[i++]; polarity ^= 1;
2908                 } else if (b < a) { // OVERLAP, take b
2909                     buffer[k++] = b; b = other[j++]; polarity ^= 2;
2910                 } else { // a == b, drop both!
2911                     if (a == HIGH) break main;
2912                     a = list[i++]; polarity ^= 1;
2913                     b = other[j++]; polarity ^= 2;
2914                 }
2915                 break;
2916               case 2: // a first, b second; if a < b, overlap
2917                 if (b < a) { // no overlap, drop b
2918                     b = other[j++]; polarity ^= 2;
2919                 } else  if (a < b) { // OVERLAP, take a
2920                     buffer[k++] = a; a = list[i++]; polarity ^= 1;
2921                 } else { // a == b, drop both!
2922                     if (a == HIGH) break main;
2923                     a = list[i++]; polarity ^= 1;
2924                     b = other[j++]; polarity ^= 2;
2925                 }
2926                 break;
2927             }
2928         }
2929         buffer[k++] = HIGH;    // terminate
2930         len = k;
2931         // swap list and buffer
2932         int[] temp = list;
2933         list = buffer;
2934         buffer = temp;
2935         pat = null;
2936         return this;
2937     }
2938
2939     private static final int max(int a, int b) {
2940         return (a > b) ? a : b;
2941     }
2942
2943     //----------------------------------------------------------------
2944     // Generic filter-based scanning code
2945     //----------------------------------------------------------------
2946
2947     private static interface Filter {
2948         boolean contains(int codePoint);
2949     }
2950
2951     private static class NumericValueFilter implements Filter {
2952         double value;
2953         NumericValueFilter(double value) { this.value = value; }
2954         public boolean contains(int ch) {
2955             return UCharacter.getUnicodeNumericValue(ch) == value;
2956         }
2957     }
2958
2959     private static class GeneralCategoryMaskFilter implements Filter {
2960         int mask;
2961         GeneralCategoryMaskFilter(int mask) { this.mask = mask; }
2962         public boolean contains(int ch) {
2963             return ((1 << UCharacter.getType(ch)) & mask) != 0;
2964         }
2965     }
2966
2967     private static class IntPropertyFilter implements Filter {
2968         int prop;
2969         int value;
2970         IntPropertyFilter(int prop, int value) {
2971             this.prop = prop;
2972             this.value = value;
2973         }
2974         public boolean contains(int ch) {
2975             return UCharacter.getIntPropertyValue(ch, prop) == value;
2976         }
2977     }
2978
2979     // VersionInfo for unassigned characters
2980     static final VersionInfo NO_VERSION = VersionInfo.getInstance(0, 0, 0, 0);
2981
2982     private static class VersionFilter implements Filter {
2983         VersionInfo version;
2984         VersionFilter(VersionInfo version) { this.version = version; }
2985         public boolean contains(int ch) {
2986             VersionInfo v = UCharacter.getAge(ch);
2987             // Reference comparison ok; VersionInfo caches and reuses
2988             // unique objects.
2989             return v != NO_VERSION &&
2990                    v.compareTo(version) <= 0;
2991         }
2992     }
2993
2994     private static synchronized UnicodeSet getInclusions(int src) {
2995         if (INCLUSIONS == null) {
2996             INCLUSIONS = new UnicodeSet[UCharacterProperty.SRC_COUNT];
2997         }
2998         if(INCLUSIONS[src] == null) {
2999             UnicodeSet incl = new UnicodeSet();
3000             switch(src) {
3001             case UCharacterProperty.SRC_CHAR:
3002                 UCharacterProperty.getInstance().addPropertyStarts(incl);
3003                 break;
3004             case UCharacterProperty.SRC_PROPSVEC:
3005                 UCharacterProperty.getInstance().upropsvec_addPropertyStarts(incl);
3006                 break;
3007             case UCharacterProperty.SRC_CHAR_AND_PROPSVEC:
3008                 UCharacterProperty.getInstance().addPropertyStarts(incl);
3009                 UCharacterProperty.getInstance().upropsvec_addPropertyStarts(incl);
3010                 break;
3011             case UCharacterProperty.SRC_HST:
3012                 UCharacterProperty.getInstance().uhst_addPropertyStarts(incl);
3013                 break;
3014             case UCharacterProperty.SRC_NORM:
3015                 NormalizerImpl.addPropertyStarts(incl);
3016                 break;
3017             case UCharacterProperty.SRC_CASE:
3018                 try {
3019                     UCaseProps.getSingleton().addPropertyStarts(incl);
3020                 } catch(IOException e) {
3021                     throw new MissingResourceException(e.getMessage(),"","");
3022                 }
3023                 break;
3024             case UCharacterProperty.SRC_BIDI:
3025                 try {
3026                     UBiDiProps.getSingleton().addPropertyStarts(incl);
3027                 } catch(IOException e) {
3028                     throw new MissingResourceException(e.getMessage(),"","");
3029                 }
3030                 break;
3031             default:
3032                 throw new IllegalStateException("UnicodeSet.getInclusions(unknown src "+src+")");
3033             }
3034             INCLUSIONS[src] = incl;
3035         }
3036         return INCLUSIONS[src];
3037     }
3038
3039     /**
3040      * Generic filter-based scanning code for UCD property UnicodeSets.
3041      */
3042     private UnicodeSet applyFilter(Filter filter, int src) {
3043         // Walk through all Unicode characters, noting the start
3044         // and end of each range for which filter.contain(c) is
3045         // true.  Add each range to a set.
3046         //
3047         // To improve performance, use the INCLUSIONS set, which
3048         // encodes information about character ranges that are known
3049         // to have identical properties, such as the CJK Ideographs
3050         // from U+4E00 to U+9FA5.  INCLUSIONS contains all characters
3051         // except the first characters of such ranges.
3052         //
3053         // TODO Where possible, instead of scanning over code points,
3054         // use internal property data to initialize UnicodeSets for
3055         // those properties.  Scanning code points is slow.
3056
3057         clear();
3058
3059         int startHasProperty = -1;
3060         UnicodeSet inclusions = getInclusions(src);
3061         int limitRange = inclusions.getRangeCount();
3062
3063         for (int j=0; j<limitRange; ++j) {
3064             // get current range
3065             int start = inclusions.getRangeStart(j);
3066             int end = inclusions.getRangeEnd(j);
3067
3068             // for all the code points in the range, process
3069             for (int ch = start; ch <= end; ++ch) {
3070                 // only add to the unicodeset on inflection points --
3071                 // where the hasProperty value changes to false
3072                 if (filter.contains(ch)) {
3073                     if (startHasProperty < 0) {
3074                         startHasProperty = ch;
3075                     }
3076                 } else if (startHasProperty >= 0) {
3077                     add_unchecked(startHasProperty, ch-1);
3078                     startHasProperty = -1;
3079                 }
3080             }
3081         }
3082         if (startHasProperty >= 0) {
3083             add_unchecked(startHasProperty, 0x10FFFF);
3084         }
3085
3086         return this;
3087     }
3088
3089
3090     /**
3091      * Remove leading and trailing rule white space and compress
3092      * internal rule white space to a single space character.
3093      *
3094      * @see UCharacterProperty#isRuleWhiteSpace
3095      */
3096     private static String mungeCharName(String source) {
3097         StringBuffer buf = new StringBuffer();
3098         for (int i=0; i<source.length(); ) {
3099             int ch = UTF16.charAt(source, i);
3100             i += UTF16.getCharCount(ch);
3101             if (UCharacterProperty.isRuleWhiteSpace(ch)) {
3102                 if (buf.length() == 0 ||
3103                     buf.charAt(buf.length() - 1) == ' ') {
3104                     continue;
3105                 }
3106                 ch = ' '; // convert to ' '
3107             }
3108             UTF16.append(buf, ch);
3109         }
3110         if (buf.length() != 0 &&
3111             buf.charAt(buf.length() - 1) == ' ') {
3112             buf.setLength(buf.length() - 1);
3113         }
3114         return buf.toString();
3115     }
3116
3117     //----------------------------------------------------------------
3118     // Property set API
3119     //----------------------------------------------------------------
3120
3121     /**
3122      * Modifies this set to contain those code points which have the
3123      * given value for the given binary or enumerated property, as
3124      * returned by UCharacter.getIntPropertyValue.  Prior contents of
3125      * this set are lost.
3126      *
3127      * @param prop a property in the range
3128      * UProperty.BIN_START..UProperty.BIN_LIMIT-1 or
3129      * UProperty.INT_START..UProperty.INT_LIMIT-1 or.
3130      * UProperty.MASK_START..UProperty.MASK_LIMIT-1.
3131      *
3132      * @param value a value in the range
3133      * UCharacter.getIntPropertyMinValue(prop)..
3134      * UCharacter.getIntPropertyMaxValue(prop), with one exception.
3135      * If prop is UProperty.GENERAL_CATEGORY_MASK, then value should not be
3136      * a UCharacter.getType() result, but rather a mask value produced
3137      * by logically ORing (1 << UCharacter.getType()) values together.
3138      * This allows grouped categories such as [:L:] to be represented.
3139      *
3140      * @return a reference to this set
3141      *
3142      * @stable ICU 2.4
3143      */
3144     public UnicodeSet applyIntPropertyValue(int prop, int value) {
3145         checkFrozen();
3146         if (prop == UProperty.GENERAL_CATEGORY_MASK) {
3147             applyFilter(new GeneralCategoryMaskFilter(value), UCharacterProperty.SRC_CHAR);
3148         } else {
3149             applyFilter(new IntPropertyFilter(prop, value), UCharacterProperty.getInstance().getSource(prop));
3150         }
3151         return this;
3152     }
3153
3154
3155
3156     /**
3157      * Modifies this set to contain those code points which have the
3158      * given value for the given property.  Prior contents of this
3159      * set are lost.
3160      *
3161      * @param propertyAlias a property alias, either short or long.
3162      * The name is matched loosely.  See PropertyAliases.txt for names
3163      * and a description of loose matching.  If the value string is
3164      * empty, then this string is interpreted as either a
3165      * General_Category value alias, a Script value alias, a binary
3166      * property alias, or a special ID.  Special IDs are matched
3167      * loosely and correspond to the following sets:
3168      *
3169      * "ANY" = [\u0000-\U0010FFFF],
3170      * "ASCII" = [\u0000-\u007F].
3171      *
3172      * @param valueAlias a value alias, either short or long.  The
3173      * name is matched loosely.  See PropertyValueAliases.txt for
3174      * names and a description of loose matching.  In addition to
3175      * aliases listed, numeric values and canonical combining classes
3176      * may be expressed numerically, e.g., ("nv", "0.5") or ("ccc",
3177      * "220").  The value string may also be empty.
3178      *
3179      * @return a reference to this set
3180      *
3181      * @stable ICU 2.4
3182      */
3183     public UnicodeSet applyPropertyAlias(String propertyAlias, String valueAlias) {
3184         return applyPropertyAlias(propertyAlias, valueAlias, null);
3185     }
3186
3187     /**
3188      * Modifies this set to contain those code points which have the
3189      * given value for the given property.  Prior contents of this
3190      * set are lost.
3191      * @param propertyAlias
3192      * @param valueAlias
3193      * @param symbols if not null, then symbols are first called to see if a property
3194      * is available. If true, then everything else is skipped.
3195      * @return this set
3196      * @stable ICU 3.2
3197      */
3198     public UnicodeSet applyPropertyAlias(String propertyAlias,
3199                                          String valueAlias, SymbolTable symbols) {
3200         checkFrozen();
3201         int p;
3202         int v;
3203         boolean mustNotBeEmpty = false, invert = false;
3204
3205         if (symbols != null
3206                 && (symbols instanceof XSymbolTable)
3207                 && ((XSymbolTable)symbols).applyPropertyAlias(propertyAlias, valueAlias, this)) {
3208                 return this;
3209         }
3210
3211         if (valueAlias.length() > 0) {
3212             p = UCharacter.getPropertyEnum(propertyAlias);
3213
3214             // Treat gc as gcm
3215             if (p == UProperty.GENERAL_CATEGORY) {
3216                 p = UProperty.GENERAL_CATEGORY_MASK;
3217             }
3218
3219             if ((p >= UProperty.BINARY_START && p < UProperty.BINARY_LIMIT) ||
3220                 (p >= UProperty.INT_START && p < UProperty.INT_LIMIT) ||
3221                 (p >= UProperty.MASK_START && p < UProperty.MASK_LIMIT)) {
3222                 try {
3223                     v = UCharacter.getPropertyValueEnum(p, valueAlias);
3224                 } catch (IllegalArgumentException e) {
3225                     // Handle numeric CCC
3226                     if (p == UProperty.CANONICAL_COMBINING_CLASS ||
3227                         p == UProperty.LEAD_CANONICAL_COMBINING_CLASS ||
3228                         p == UProperty.TRAIL_CANONICAL_COMBINING_CLASS) {
3229                         v = Integer.parseInt(Utility.deleteRuleWhiteSpace(valueAlias));
3230                         // If the resultant set is empty then the numeric value
3231                         // was invalid.
3232                         //mustNotBeEmpty = true;
3233                         // old code was wrong; anything between 0 and 255 is valid even if unused.
3234                         if (v < 0 || v > 255) throw e;
3235                     } else {
3236                         throw e;
3237                     }
3238                 }
3239             }
3240
3241             else {
3242
3243                 switch (p) {
3244                 case UProperty.NUMERIC_VALUE:
3245                     {
3246                         double value = Double.parseDouble(Utility.deleteRuleWhiteSpace(valueAlias));
3247                         applyFilter(new NumericValueFilter(value), UCharacterProperty.SRC_CHAR);
3248                         return this;
3249                     }
3250                 case UProperty.NAME:
3251                 case UProperty.UNICODE_1_NAME:
3252                     {
3253                         // Must munge name, since
3254                         // UCharacter.charFromName() does not do
3255                         // 'loose' matching.
3256                         String buf = mungeCharName(valueAlias);
3257                         int ch =
3258                             (p == UProperty.NAME) ?
3259                             UCharacter.getCharFromExtendedName(buf) :
3260                             UCharacter.getCharFromName1_0(buf);
3261                         if (ch == -1) {
3262                             throw new IllegalArgumentException("Invalid character name");
3263                         }
3264                         clear();
3265                         add_unchecked(ch);
3266                         return this;
3267                     }
3268                 case UProperty.AGE:
3269                     {
3270                         // Must munge name, since
3271                         // VersionInfo.getInstance() does not do
3272                         // 'loose' matching.
3273                         VersionInfo version = VersionInfo.getInstance(mungeCharName(valueAlias));
3274                         applyFilter(new VersionFilter(version), UCharacterProperty.SRC_PROPSVEC);
3275                         return this;
3276                     }
3277                 }
3278
3279                 // p is a non-binary, non-enumerated property that we
3280                 // don't support (yet).
3281                 throw new IllegalArgumentException("Unsupported property");
3282             }
3283         }
3284
3285         else {
3286             // valueAlias is empty.  Interpret as General Category, Script,
3287             // Binary property, or ANY or ASCII.  Upon success, p and v will
3288             // be set.
3289             try {
3290                 p = UProperty.GENERAL_CATEGORY_MASK;
3291                 v = UCharacter.getPropertyValueEnum(p, propertyAlias);
3292             } catch (IllegalArgumentException e) {
3293                 try {
3294                     p = UProperty.SCRIPT;
3295                     v = UCharacter.getPropertyValueEnum(p, propertyAlias);
3296                 } catch (IllegalArgumentException e2) {
3297                     try {
3298                         p = UCharacter.getPropertyEnum(propertyAlias);
3299                     } catch (IllegalArgumentException e3) {
3300                         p = -1;
3301                     }
3302                     if (p >= UProperty.BINARY_START && p < UProperty.BINARY_LIMIT) {
3303                         v = 1;
3304                     } else if (p == -1) {
3305                         if (0 == UPropertyAliases.compare(ANY_ID, propertyAlias)) {
3306                             set(MIN_VALUE, MAX_VALUE);
3307                             return this;
3308                         } else if (0 == UPropertyAliases.compare(ASCII_ID, propertyAlias)) {
3309                             set(0, 0x7F);
3310                             return this;
3311                         } else if (0 == UPropertyAliases.compare(ASSIGNED, propertyAlias)) {
3312                             // [:Assigned:]=[:^Cn:]
3313                             p = UProperty.GENERAL_CATEGORY_MASK;
3314                             v = (1<<UCharacter.UNASSIGNED);
3315                             invert = true;
3316                         } else {
3317                             // Property name was never matched.
3318                             throw new IllegalArgumentException("Invalid property alias: " + propertyAlias + "=" + valueAlias);
3319                         }
3320                     } else {
3321                         // Valid propery name, but it isn't binary, so the value
3322                         // must be supplied.
3323                         throw new IllegalArgumentException("Missing property value");
3324                     }
3325                 }
3326             }
3327         }
3328
3329         applyIntPropertyValue(p, v);
3330         if(invert) {
3331             complement();
3332         }
3333
3334         if (mustNotBeEmpty && isEmpty()) {
3335             // mustNotBeEmpty is set to true if an empty set indicates
3336             // invalid input.
3337             throw new IllegalArgumentException("Invalid property value");
3338         }
3339
3340         return this;
3341     }
3342
3343     //----------------------------------------------------------------
3344     // Property set patterns
3345     //----------------------------------------------------------------
3346
3347     /**
3348      * Return true if the given position, in the given pattern, appears
3349      * to be the start of a property set pattern.
3350      */
3351     private static boolean resemblesPropertyPattern(String pattern, int pos) {
3352         // Patterns are at least 5 characters long
3353         if ((pos+5) > pattern.length()) {
3354             return false;
3355         }
3356
3357         // Look for an opening [:, [:^, \p, or \P
3358         return pattern.regionMatches(pos, "[:", 0, 2) ||
3359             pattern.regionMatches(true, pos, "\\p", 0, 2) ||
3360             pattern.regionMatches(pos, "\\N", 0, 2);
3361     }
3362
3363     /**
3364      * Return true if the given iterator appears to point at a
3365      * property pattern.  Regardless of the result, return with the
3366      * iterator unchanged.
3367      * @param chars iterator over the pattern characters.  Upon return
3368      * it will be unchanged.
3369      * @param iterOpts RuleCharacterIterator options
3370      */
3371     private static boolean resemblesPropertyPattern(RuleCharacterIterator chars,
3372                                                     int iterOpts) {
3373         boolean result = false;
3374         iterOpts &= ~RuleCharacterIterator.PARSE_ESCAPES;
3375         Object pos = chars.getPos(null);
3376         int c = chars.next(iterOpts);
3377         if (c == '[' || c == '\\') {
3378             int d = chars.next(iterOpts & ~RuleCharacterIterator.SKIP_WHITESPACE);
3379             result = (c == '[') ? (d == ':') :
3380                      (d == 'N' || d == 'p' || d == 'P');
3381         }
3382         chars.setPos(pos);
3383         return result;
3384     }
3385
3386     /**
3387      * Parse the given property pattern at the given parse position.
3388      * @param symbols TODO
3389      */
3390     private UnicodeSet applyPropertyPattern(String pattern, ParsePosition ppos, SymbolTable symbols) {
3391         int pos = ppos.getIndex();
3392
3393         // On entry, ppos should point to one of the following locations:
3394
3395         // Minimum length is 5 characters, e.g. \p{L}
3396         if ((pos+5) > pattern.length()) {
3397             return null;
3398         }
3399
3400         boolean posix = false; // true for [:pat:], false for \p{pat} \P{pat} \N{pat}
3401         boolean isName = false; // true for \N{pat}, o/w false
3402         boolean invert = false;
3403
3404         // Look for an opening [:, [:^, \p, or \P
3405         if (pattern.regionMatches(pos, "[:", 0, 2)) {
3406             posix = true;
3407             pos = Utility.skipWhitespace(pattern, pos+2);
3408             if (pos < pattern.length() && pattern.charAt(pos) == '^') {
3409                 ++pos;
3410                 invert = true;
3411             }
3412         } else if (pattern.regionMatches(true, pos, "\\p", 0, 2) ||
3413                    pattern.regionMatches(pos, "\\N", 0, 2)) {
3414             char c = pattern.charAt(pos+1);
3415             invert = (c == 'P');
3416             isName = (c == 'N');
3417             pos = Utility.skipWhitespace(pattern, pos+2);
3418             if (pos == pattern.length() || pattern.charAt(pos++) != '{') {
3419                 // Syntax error; "\p" or "\P" not followed by "{"
3420                 return null;
3421             }
3422         } else {
3423             // Open delimiter not seen
3424             return null;
3425         }
3426
3427         // Look for the matching close delimiter, either :] or }
3428         int close = pattern.indexOf(posix ? ":]" : "}", pos);
3429         if (close < 0) {
3430             // Syntax error; close delimiter missing
3431             return null;
3432         }
3433
3434         // Look for an '=' sign.  If this is present, we will parse a
3435         // medium \p{gc=Cf} or long \p{GeneralCategory=Format}
3436         // pattern.
3437         int equals = pattern.indexOf('=', pos);
3438         String propName, valueName;
3439         if (equals >= 0 && equals < close && !isName) {
3440             // Equals seen; parse medium/long pattern
3441             propName = pattern.substring(pos, equals);
3442             valueName = pattern.substring(equals+1, close);
3443         }
3444
3445         else {
3446             // Handle case where no '=' is seen, and \N{}
3447             propName = pattern.substring(pos, close);
3448             valueName = "";
3449
3450             // Handle \N{name}
3451             if (isName) {
3452                 // This is a little inefficient since it means we have to
3453                 // parse "na" back to UProperty.NAME even though we already
3454                 // know it's UProperty.NAME.  If we refactor the API to
3455                 // support args of (int, String) then we can remove
3456                 // "na" and make this a little more efficient.
3457                 valueName = propName;
3458                 propName = "na";
3459             }
3460         }
3461
3462         applyPropertyAlias(propName, valueName, symbols);
3463
3464         if (invert) {
3465             complement();
3466         }
3467
3468         // Move to the limit position after the close delimiter
3469         ppos.setIndex(close + (posix ? 2 : 1));
3470
3471         return this;
3472     }
3473
3474     /**
3475      * Parse a property pattern.
3476      * @param chars iterator over the pattern characters.  Upon return
3477      * it will be advanced to the first character after the parsed
3478      * pattern, or the end of the iteration if all characters are
3479      * parsed.
3480      * @param rebuiltPat the pattern that was parsed, rebuilt or
3481      * copied from the input pattern, as appropriate.
3482      * @param symbols TODO
3483      */
3484     private void applyPropertyPattern(RuleCharacterIterator chars,
3485                                       StringBuffer rebuiltPat, SymbolTable symbols) {
3486         String patStr = chars.lookahead();
3487         ParsePosition pos = new ParsePosition(0);
3488         applyPropertyPattern(patStr, pos, symbols);
3489         if (pos.getIndex() == 0) {
3490             syntaxError(chars, "Invalid property pattern");
3491         }
3492         chars.jumpahead(pos.getIndex());
3493         rebuiltPat.append(patStr.substring(0, pos.getIndex()));
3494     }
3495
3496     //----------------------------------------------------------------
3497     // Case folding API
3498     //----------------------------------------------------------------
3499
3500     /**
3501      * Bitmask for constructor and applyPattern() indicating that
3502      * white space should be ignored.  If set, ignore characters for
3503      * which UCharacterProperty.isRuleWhiteSpace() returns true,
3504      * unless they are quoted or escaped.  This may be ORed together
3505      * with other selectors.
3506      * @stable ICU 3.8
3507      */
3508     public static final int IGNORE_SPACE = 1;
3509
3510     /**
3511      * Bitmask for constructor, applyPattern(), and closeOver()
3512      * indicating letter case.  This may be ORed together with other
3513      * selectors.
3514      *
3515      * Enable case insensitive matching.  E.g., "[ab]" with this flag
3516      * will match 'a', 'A', 'b', and 'B'.  "[^ab]" with this flag will
3517      * match all except 'a', 'A', 'b', and 'B'. This performs a full
3518      * closure over case mappings, e.g. U+017F for s.
3519      *
3520      * The resulting set is a superset of the input for the code points but
3521      * not for the strings.
3522      * It performs a case mapping closure of the code points and adds
3523      * full case folding strings for the code points, and reduces strings of
3524      * the original set to their full case folding equivalents.
3525      *
3526      * This is designed for case-insensitive matches, for example
3527      * in regular expressions. The full code point case closure allows checking of
3528      * an input character directly against the closure set.
3529      * Strings are matched by comparing the case-folded form from the closure
3530      * set with an incremental case folding of the string in question.
3531      *
3532      * The closure set will also contain single code points if the original
3533      * set contained case-equivalent strings (like U+00DF for "ss" or "Ss" etc.).
3534      * This is not necessary (that is, redundant) for the above matching method
3535      * but results in the same closure sets regardless of whether the original
3536      * set contained the code point or a string.
3537      * @stable ICU 3.8
3538      */
3539     public static final int CASE = 2;
3540
3541     /**
3542      * Alias for UnicodeSet.CASE, for ease of porting from C++ where ICU4C
3543      * also has both USET_CASE and USET_CASE_INSENSITIVE (see uset.h).
3544      * @see #CASE
3545      * @stable ICU 3.4
3546      */
3547     public static final int CASE_INSENSITIVE = 2;
3548
3549     /**
3550      * Bitmask for constructor, applyPattern(), and closeOver()
3551      * indicating letter case.  This may be ORed together with other
3552      * selectors.
3553      *
3554      * Enable case insensitive matching.  E.g., "[ab]" with this flag
3555      * will match 'a', 'A', 'b', and 'B'.  "[^ab]" with this flag will
3556      * match all except 'a', 'A', 'b', and 'B'. This adds the lower-,
3557      * title-, and uppercase mappings as well as the case folding
3558      * of each existing element in the set.
3559      * @stable ICU 3.4
3560      */
3561     public static final int ADD_CASE_MAPPINGS = 4;
3562
3563     //  add the result of a full case mapping to the set
3564     //  use str as a temporary string to avoid constructing one
3565     private static final void addCaseMapping(UnicodeSet set, int result, StringBuffer full) {
3566         if(result >= 0) {
3567             if(result > UCaseProps.MAX_STRING_LENGTH) {
3568                 // add a single-code point case mapping
3569                 set.add(result);
3570             } else {
3571                 // add a string case mapping from full with length result
3572                 set.add(full.toString());
3573                 full.setLength(0);
3574             }
3575         }
3576         // result < 0: the code point mapped to itself, no need to add it
3577         // see UCaseProps
3578     }
3579
3580     /**
3581      * Close this set over the given attribute.  For the attribute
3582      * CASE, the result is to modify this set so that:
3583      *
3584      * 1. For each character or string 'a' in this set, all strings
3585      * 'b' such that foldCase(a) == foldCase(b) are added to this set.
3586      * (For most 'a' that are single characters, 'b' will have
3587      * b.length() == 1.)
3588      *
3589      * 2. For each string 'e' in the resulting set, if e !=
3590      * foldCase(e), 'e' will be removed.
3591      *
3592      * Example: [aq\u00DF{Bc}{bC}{Fi}] => [aAqQ\u00DF\uFB01{ss}{bc}{fi}]
3593      *
3594      * (Here foldCase(x) refers to the operation
3595      * UCharacter.foldCase(x, true), and a == b actually denotes
3596      * a.equals(b), not pointer comparison.)
3597      *
3598      * @param attribute bitmask for attributes to close over.
3599      * Currently only the CASE bit is supported.  Any undefined bits
3600      * are ignored.
3601      * @return a reference to this set.
3602      * @stable ICU 3.8
3603      */
3604     public UnicodeSet closeOver(int attribute) {
3605         checkFrozen();
3606         if ((attribute & (CASE | ADD_CASE_MAPPINGS)) != 0) {
3607             UCaseProps csp;
3608             try {
3609                 csp = UCaseProps.getSingleton();
3610             } catch(IOException e) {
3611                 return this;
3612             }
3613             UnicodeSet foldSet = new UnicodeSet(this);
3614             ULocale root = ULocale.ROOT;
3615
3616             // start with input set to guarantee inclusion
3617             // CASE: remove strings because the strings will actually be reduced (folded);
3618             //       therefore, start with no strings and add only those needed
3619             if((attribute & CASE) != 0) {
3620                 foldSet.strings.clear();
3621             }
3622
3623             int n = getRangeCount();
3624             int result;
3625             StringBuffer full = new StringBuffer();
3626             int locCache[] = new int[1];
3627
3628             for (int i=0; i<n; ++i) {
3629                 int start = getRangeStart(i);
3630                 int end   = getRangeEnd(i);
3631
3632                 if((attribute & CASE) != 0) {
3633                     // full case closure
3634                     for (int cp=start; cp<=end; ++cp) {
3635                         csp.addCaseClosure(cp, foldSet);
3636                     }
3637                 } else {
3638                     // add case mappings
3639                     // (does not add long s for regular s, or Kelvin for k, for example)
3640                     for (int cp=start; cp<=end; ++cp) {
3641                         result = csp.toFullLower(cp, null, full, root, locCache);
3642                         addCaseMapping(foldSet, result, full);
3643
3644                         result = csp.toFullTitle(cp, null, full, root, locCache);
3645                         addCaseMapping(foldSet, result, full);
3646
3647                         result = csp.toFullUpper(cp, null, full, root, locCache);
3648                         addCaseMapping(foldSet, result, full);
3649
3650                         result = csp.toFullFolding(cp, full, 0);
3651                         addCaseMapping(foldSet, result, full);
3652                     }
3653                 }
3654             }
3655             if (!strings.isEmpty()) {
3656                 String str;
3657                 if ((attribute & CASE) != 0) {
3658                     Iterator it = strings.iterator();
3659                     while (it.hasNext()) {
3660                         str = UCharacter.foldCase((String)it.next(), 0);
3661                         if(!csp.addStringCaseClosure(str, foldSet)) {
3662                             foldSet.add(str); // does not map to code points: add the folded string itself
3663                         }
3664                     }
3665                 } else {
3666                     BreakIterator bi = BreakIterator.getWordInstance(root);
3667                     Iterator it = strings.iterator();
3668                     while (it.hasNext()) {
3669                         str = (String)it.next();
3670                         foldSet.add(UCharacter.toLowerCase(root, str));
3671                         foldSet.add(UCharacter.toTitleCase(root, str, bi));
3672                         foldSet.add(UCharacter.toUpperCase(root, str));
3673                         foldSet.add(UCharacter.foldCase(str, 0));
3674                     }
3675                 }
3676             }
3677             set(foldSet);
3678         }
3679         return this;
3680     }
3681
3682     /**
3683      * Internal class for customizing UnicodeSet parsing of properties.
3684      * TODO: extend to allow customizing of codepoint ranges
3685      * @draft ICU3.8
3686      * @provisional This API might change or be removed in a future release.
3687      * @author medavis
3688      */
3689     abstract public static class XSymbolTable implements SymbolTable {
3690         /**
3691          * Default constructor
3692          * @draft ICU3.8
3693          * @provisional This API might change or be removed in a future release.
3694          */
3695         public XSymbolTable(){}
3696         /**
3697          * Supplies default implementation for SymbolTable (no action).
3698          * @draft ICU3.8
3699          * @provisional This API might change or be removed in a future release.
3700          */
3701         public UnicodeMatcher lookupMatcher(int i) {
3702             return null;
3703         }
3704         /**
3705          * Apply a new property alias. Is called when parsing [:xxx=yyy:]. Results are to put into result.
3706          * @param propertyName the xxx in [:xxx=yyy:]
3707          * @param propertyValue the yyy in [:xxx=yyy:]
3708          * @param result where the result is placed
3709          * @return true if handled
3710          * @draft ICU3.8
3711          * @provisional This API might change or be removed in a future release.
3712          */
3713         public boolean applyPropertyAlias(String propertyName, String propertyValue, UnicodeSet result) {
3714             return false;
3715         }
3716         /**
3717          * Supplies default implementation for SymbolTable (no action).
3718          * @draft ICU3.8
3719          * @provisional This API might change or be removed in a future release.
3720             */
3721         public char[] lookup(String s) {
3722             return null;
3723         }
3724         /**
3725          * Supplies default implementation for SymbolTable (no action).
3726          * @draft ICU3.8
3727          * @provisional This API might change or be removed in a future release.
3728          */
3729         public String parseReference(String text, ParsePosition pos, int limit) {
3730             return null;
3731         }
3732     }
3733
3734     private boolean frozen;
3735
3736     /**
3737      * Is this frozen, according to the Freezable interface?
3738      * @return value
3739      * @stable ICU 3.8
3740      */
3741     public boolean isFrozen() {
3742         return frozen;
3743     }
3744
3745     /**
3746      * Freeze this class, according to the Freezable interface.
3747      * @return this
3748      * @stable ICU 3.8
3749      */
3750     public Object freeze() {
3751         frozen = true;
3752         return this;
3753     }
3754
3755     /**
3756      * Clone a thawed version of this class, according to the Freezable interface.
3757      * @return this
3758      * @stable ICU 3.8
3759      */
3760     public Object cloneAsThawed() {
3761         UnicodeSet result = (UnicodeSet) clone();
3762         result.frozen = false;
3763         return result;
3764     }
3765
3766     // internal function
3767     private void checkFrozen() {
3768         if (frozen) {
3769             throw new UnsupportedOperationException("Attempt to modify frozen object");
3770         }
3771     }
3772 }
3773 //eof