Back to index...

	/*
	* Copyright (c) 2005, 2011, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	/*
	*******************************************************************************
	* (C) Copyright IBM Corp. and others, 1996-2009 - All Rights Reserved *
	* *
	* The original version of this source code and documentation is copyrighted *
	* and owned by IBM, These materials are provided under terms of a License *
	* Agreement between IBM and Sun. This technology is protected by multiple *
	* US and International patents. This notice and attribution to IBM may not *
	* to removed. *
	*******************************************************************************
	*/

	package sun.text.normalizer;

	import java.text.ParsePosition;
	import java.util.Iterator;
	import java.util.TreeSet;

	/**
	* A mutable set of Unicode characters and multicharacter strings. Objects of this class
	* represent <em>character classes</em> used in regular expressions.
	* A character specifies a subset of Unicode code points. Legal
	* code points are U+0000 to U+10FFFF, inclusive.
	*
	* <p>The UnicodeSet class is not designed to be subclassed.
	*
	* <p><code>UnicodeSet</code> supports two APIs. The first is the
	* <em>operand</em> API that allows the caller to modify the value of
	* a <code>UnicodeSet</code> object. It conforms to Java 2's
	* <code>java.util.Set</code> interface, although
	* <code>UnicodeSet</code> does not actually implement that
	* interface. All methods of <code>Set</code> are supported, with the
	* modification that they take a character range or single character
	* instead of an <code>Object</code>, and they take a
	* <code>UnicodeSet</code> instead of a <code>Collection</code>. The
	* operand API may be thought of in terms of boolean logic: a boolean
	* OR is implemented by <code>add</code>, a boolean AND is implemented
	* by <code>retain</code>, a boolean XOR is implemented by
	* <code>complement</code> taking an argument, and a boolean NOT is
	* implemented by <code>complement</code> with no argument. In terms
	* of traditional set theory function names, <code>add</code> is a
	* union, <code>retain</code> is an intersection, <code>remove</code>
	* is an asymmetric difference, and <code>complement</code> with no
	* argument is a set complement with respect to the superset range
	* <code>MIN_VALUE-MAX_VALUE</code>
	*
	* <p>The second API is the
	* <code>applyPattern()</code>/<code>toPattern()</code> API from the
	* <code>java.text.Format</code>-derived classes. Unlike the
	* methods that add characters, add categories, and control the logic
	* of the set, the method <code>applyPattern()</code> sets all
	* attributes of a <code>UnicodeSet</code> at once, based on a
	* string pattern.
	*
	* <p><b>Pattern syntax</b></p>
	*
	* Patterns are accepted by the constructors and the
	* <code>applyPattern()</code> methods and returned by the
	* <code>toPattern()</code> method. These patterns follow a syntax
	* similar to that employed by version 8 regular expression character
	* classes. Here are some simple examples:
	*
	* <blockquote>
	* <table>
	* <tr align="top">
	* <td nowrap valign="top" align="left"><code>[]</code></td>
	* <td valign="top">No characters</td>
	* </tr><tr align="top">
	* <td nowrap valign="top" align="left"><code>[a]</code></td>
	* <td valign="top">The character 'a'</td>
	* </tr><tr align="top">
	* <td nowrap valign="top" align="left"><code>[ae]</code></td>
	* <td valign="top">The characters 'a' and 'e'</td>
	* </tr>
	* <tr>
	* <td nowrap valign="top" align="left"><code>[a-e]</code></td>
	* <td valign="top">The characters 'a' through 'e' inclusive, in Unicode code
	* point order</td>
	* </tr>
	* <tr>
	* <td nowrap valign="top" align="left"><code>[\\u4E01]</code></td>
	* <td valign="top">The character U+4E01</td>
	* </tr>
	* <tr>
	* <td nowrap valign="top" align="left"><code>[a{ab}{ac}]</code></td>
	* <td valign="top">The character 'a' and the multicharacter strings "ab" and
	* "ac"</td>
	* </tr>
	* <tr>
	* <td nowrap valign="top" align="left"><code>[\p{Lu}]</code></td>
	* <td valign="top">All characters in the general category Uppercase Letter</td>
	* </tr>
	* </table>
	* </blockquote>
	*
	* Any character may be preceded by a backslash in order to remove any special
	* meaning. White space characters, as defined by UCharacterProperty.isRuleWhiteSpace(), are
	* ignored, unless they are escaped.
	*
	* <p>Property patterns specify a set of characters having a certain
	* property as defined by the Unicode standard. Both the POSIX-like
	* "[:Lu:]" and the Perl-like syntax "\p{Lu}" are recognized. For a
	* complete list of supported property patterns, see the User's Guide
	* for UnicodeSet at
	* <a href="http://www.icu-project.org/userguide/unicodeSet.html">
	* http://www.icu-project.org/userguide/unicodeSet.html</a>.
	* Actual determination of property data is defined by the underlying
	* Unicode database as implemented by UCharacter.
	*
	* <p>Patterns specify individual characters, ranges of characters, and
	* Unicode property sets. When elements are concatenated, they
	* specify their union. To complement a set, place a '^' immediately
	* after the opening '['. Property patterns are inverted by modifying
	* their delimiters; "[:^foo]" and "\P{foo}". In any other location,
	* '^' has no special meaning.
	*
	* <p>Ranges are indicated by placing two a '-' between two
	* characters, as in "a-z". This specifies the range of all
	* characters from the left to the right, in Unicode order. If the
	* left character is greater than or equal to the
	* right character it is a syntax error. If a '-' occurs as the first
	* character after the opening '[' or '[^', or if it occurs as the
	* last character before the closing ']', then it is taken as a
	* literal. Thus "[a\\-b]", "[-ab]", and "[ab-]" all indicate the same
	* set of three characters, 'a', 'b', and '-'.
	*
	* <p>Sets may be intersected using the '&' operator or the asymmetric
	* set difference may be taken using the '-' operator, for example,
	* "[[:L:]&[\\u0000-\\u0FFF]]" indicates the set of all Unicode letters
	* with values less than 4096. Operators ('&' and '\|') have equal
	* precedence and bind left-to-right. Thus
	* "[[:L:]-[a-z]-[\\u0100-\\u01FF]]" is equivalent to
	* "[[[:L:]-[a-z]]-[\\u0100-\\u01FF]]". This only really matters for
	* difference; intersection is commutative.
	*
	* <table>
	* <tr valign=top><td nowrap><code>[a]</code><td>The set containing 'a'
	* <tr valign=top><td nowrap><code>[a-z]</code><td>The set containing 'a'
	* through 'z' and all letters in between, in Unicode order
	* <tr valign=top><td nowrap><code>[^a-z]</code><td>The set containing
	* all characters but 'a' through 'z',
	* that is, U+0000 through 'a'-1 and 'z'+1 through U+10FFFF
	* <tr valign=top><td nowrap><code>[[<em>pat1</em>][<em>pat2</em>]]</code>
	* <td>The union of sets specified by <em>pat1</em> and <em>pat2</em>
	* <tr valign=top><td nowrap><code>[[<em>pat1</em>]&[<em>pat2</em>]]</code>
	* <td>The intersection of sets specified by <em>pat1</em> and <em>pat2</em>
	* <tr valign=top><td nowrap><code>[[<em>pat1</em>]-[<em>pat2</em>]]</code>
	* <td>The asymmetric difference of sets specified by <em>pat1</em> and
	* <em>pat2</em>
	* <tr valign=top><td nowrap><code>[:Lu:] or \p{Lu}</code>
	* <td>The set of characters having the specified
	* Unicode property; in
	* this case, Unicode uppercase letters
	* <tr valign=top><td nowrap><code>[:^Lu:] or \P{Lu}</code>
	* <td>The set of characters <em>not</em> having the given
	* Unicode property
	* </table>
	*
	* <p><b>Warning</b>: you cannot add an empty string ("") to a UnicodeSet.</p>
	*
	* <p><b>Formal syntax</b></p>
	*
	* <blockquote>
	* <table>
	* <tr align="top">
	* <td nowrap valign="top" align="right"><code>pattern :=  </code></td>
	* <td valign="top"><code>('[' '^'? item* ']') \|
	* property</code></td>
	* </tr>
	* <tr align="top">
	* <td nowrap valign="top" align="right"><code>item :=  </code></td>
	* <td valign="top"><code>char \| (char '-' char) \| pattern-expr<br>
	* </code></td>
	* </tr>
	* <tr align="top">
	* <td nowrap valign="top" align="right"><code>pattern-expr :=  </code></td>
	* <td valign="top"><code>pattern \| pattern-expr pattern \|
	* pattern-expr op pattern<br>
	* </code></td>
	* </tr>
	* <tr align="top">
	* <td nowrap valign="top" align="right"><code>op :=  </code></td>
	* <td valign="top"><code>'&' \| '-'<br>
	* </code></td>
	* </tr>
	* <tr align="top">
	* <td nowrap valign="top" align="right"><code>special :=  </code></td>
	* <td valign="top"><code>'[' \| ']' \| '-'<br>
	* </code></td>
	* </tr>
	* <tr align="top">
	* <td nowrap valign="top" align="right"><code>char :=  </code></td>
	* <td valign="top"><em>any character that is not</em><code> special<br>
	* \| ('\\' </code><em>any character</em><code>)<br>
	* \| ('\u' hex hex hex hex)<br>
	* </code></td>
	* </tr>
	* <tr align="top">
	* <td nowrap valign="top" align="right"><code>hex :=  </code></td>
	* <td valign="top"><em>any character for which
	* </em><code>Character.digit(c, 16)</code><em>
	* returns a non-negative result</em></td>
	* </tr>
	* <tr>
	* <td nowrap valign="top" align="right"><code>property :=  </code></td>
	* <td valign="top"><em>a Unicode property set pattern</td>
	* </tr>
	* </table>
	* <br>
	* <table border="1">
	* <tr>
	* <td>Legend: <table>
	* <tr>
	* <td nowrap valign="top"><code>a := b</code></td>
	* <td width="20" valign="top">  </td>
	* <td valign="top"><code>a</code> may be replaced by <code>b</code> </td>
	* </tr>
	* <tr>
	* <td nowrap valign="top"><code>a?</code></td>
	* <td valign="top"></td>
	* <td valign="top">zero or one instance of <code>a</code><br>
	* </td>
	* </tr>
	* <tr>
	* <td nowrap valign="top"><code>a*</code></td>
	* <td valign="top"></td>
	* <td valign="top">one or more instances of <code>a</code><br>
	* </td>
	* </tr>
	* <tr>
	* <td nowrap valign="top"><code>a \| b</code></td>
	* <td valign="top"></td>
	* <td valign="top">either <code>a</code> or <code>b</code><br>
	* </td>
	* </tr>
	* <tr>
	* <td nowrap valign="top"><code>'a'</code></td>
	* <td valign="top"></td>
	* <td valign="top">the literal string between the quotes </td>
	* </tr>
	* </table>
	* </td>
	* </tr>
	* </table>
	* </blockquote>
	* <p>To iterate over contents of UnicodeSet, use UnicodeSetIterator class.
	*
	* @author Alan Liu
	* @stable ICU 2.0
	* @see UnicodeSetIterator
	*/
	public class UnicodeSet implements UnicodeMatcher {

	private static final int LOW = 0x000000; // LOW <= all valid values. ZERO for codepoints
	private static final int HIGH = 0x110000; // HIGH > all valid values. 10000 for code units.
	// 110000 for codepoints

	/**
	* Minimum value that can be stored in a UnicodeSet.
	* @stable ICU 2.0
	*/
	public static final int MIN_VALUE = LOW;

	/**
	* Maximum value that can be stored in a UnicodeSet.
	* @stable ICU 2.0
	*/
	public static final int MAX_VALUE = HIGH - 1;

	private int len; // length used; list may be longer to minimize reallocs
	private int[] list; // MUST be terminated with HIGH
	private int[] rangeList; // internal buffer
	private int[] buffer; // internal buffer

	// NOTE: normally the field should be of type SortedSet; but that is missing a public clone!!
	// is not private so that UnicodeSetIterator can get access
	TreeSet<String> strings = new TreeSet<>();

	/**
	* The pattern representation of this set. This may not be the
	* most economical pattern. It is the pattern supplied to
	* applyPattern(), with variables substituted and whitespace
	* removed. For sets constructed without applyPattern(), or
	* modified using the non-pattern API, this string will be null,
	* indicating that toPattern() must generate a pattern
	* representation from the inversion list.
	*/
	private String pat = null;

	private static final int START_EXTRA = 16; // initial storage. Must be >= 0
	private static final int GROW_EXTRA = START_EXTRA; // extra amount for growth. Must be >= 0

	/**
	* A set of all characters _except_ the second through last characters of
	* certain ranges. These ranges are ranges of characters whose
	* properties are all exactly alike, e.g. CJK Ideographs from
	* U+4E00 to U+9FA5.
	*/
	private static UnicodeSet INCLUSIONS[] = null;

	//----------------------------------------------------------------
	// Public API
	//----------------------------------------------------------------

	/**
	* Constructs an empty set.
	* @stable ICU 2.0
	*/
	public UnicodeSet() {
	list = new int[1 + START_EXTRA];
	list[len++] = HIGH;
	}

	/**
	* Constructs a set containing the given range. If <code>end >
	* start</code> then an empty set is created.
	*
	* @param start first character, inclusive, of range
	* @param end last character, inclusive, of range
	* @stable ICU 2.0
	*/
	public UnicodeSet(int start, int end) {
	this();
	complement(start, end);
	}

	/**
	* Constructs a set from the given pattern. See the class description
	* for the syntax of the pattern language. Whitespace is ignored.
	* @param pattern a string specifying what characters are in the set
	* @exception java.lang.IllegalArgumentException if the pattern contains
	* a syntax error.
	* @stable ICU 2.0
	*/
	public UnicodeSet(String pattern) {
	this();
	applyPattern(pattern, null, null, IGNORE_SPACE);
	}

	/**
	* Make this object represent the same set as <code>other</code>.
	* @param other a <code>UnicodeSet</code> whose value will be
	* copied to this object
	* @stable ICU 2.0
	*/
	public UnicodeSet set(UnicodeSet other) {
	list = other.list.clone();
	len = other.len;
	pat = other.pat;
	strings = (TreeSet)other.strings.clone();
	return this;
	}

	/**
	* Modifies this set to represent the set specified by the given pattern.
	* See the class description for the syntax of the pattern language.
	* Whitespace is ignored.
	* @param pattern a string specifying what characters are in the set
	* @exception java.lang.IllegalArgumentException if the pattern
	* contains a syntax error.
	* @stable ICU 2.0
	*/
	public final UnicodeSet applyPattern(String pattern) {
	return applyPattern(pattern, null, null, IGNORE_SPACE);
	}

	/**
	* Append the <code>toPattern()</code> representation of a
	* string to the given <code>StringBuffer</code>.
	*/
	private static void _appendToPat(StringBuffer buf, String s, boolean escapeUnprintable) {
	for (int i = 0; i < s.length(); i += UTF16.getCharCount(i)) {
	_appendToPat(buf, UTF16.charAt(s, i), escapeUnprintable);
	}
	}

	/**
	* Append the <code>toPattern()</code> representation of a
	* character to the given <code>StringBuffer</code>.
	*/
	private static void _appendToPat(StringBuffer buf, int c, boolean escapeUnprintable) {
	if (escapeUnprintable && Utility.isUnprintable(c)) {
	// Use hex escape notation (<backslash>uxxxx or <backslash>Uxxxxxxxx) for anything
	// unprintable
	if (Utility.escapeUnprintable(buf, c)) {
	return;
	}
	}
	// Okay to let ':' pass through
	switch (c) {
	case '[': // SET_OPEN:
	case ']': // SET_CLOSE:
	case '-': // HYPHEN:
	case '^': // COMPLEMENT:
	case '&': // INTERSECTION:
	case '\\': //BACKSLASH:
	case '{':
	case '}':
	case '$':
	case ':':
	buf.append('\\');
	break;
	default:
	// Escape whitespace
	if (UCharacterProperty.isRuleWhiteSpace(c)) {
	buf.append('\\');
	}
	break;
	}
	UTF16.append(buf, c);
	}

	/**
	* Append a string representation of this set to result. This will be
	* a cleaned version of the string passed to applyPattern(), if there
	* is one. Otherwise it will be generated.
	*/
	private StringBuffer _toPattern(StringBuffer result,
	boolean escapeUnprintable) {
	if (pat != null) {
	int i;
	int backslashCount = 0;
	for (i=0; i<pat.length(); ) {
	int c = UTF16.charAt(pat, i);
	i += UTF16.getCharCount(c);
	if (escapeUnprintable && Utility.isUnprintable(c)) {
	// If the unprintable character is preceded by an odd
	// number of backslashes, then it has been escaped.
	// Before unescaping it, we delete the final
	// backslash.
	if ((backslashCount % 2) == 1) {
	result.setLength(result.length() - 1);
	}
	Utility.escapeUnprintable(result, c);
	backslashCount = 0;
	} else {
	UTF16.append(result, c);
	if (c == '\\') {
	++backslashCount;
	} else {
	backslashCount = 0;
	}
	}
	}
	return result;
	}

	return _generatePattern(result, escapeUnprintable, true);
	}

	/**
	* Generate and append a string representation of this set to result.
	* This does not use this.pat, the cleaned up copy of the string
	* passed to applyPattern().
	* @param includeStrings if false, doesn't include the strings.
	* @stable ICU 3.8
	*/
	public StringBuffer _generatePattern(StringBuffer result,
	boolean escapeUnprintable, boolean includeStrings) {
	result.append('[');

	int count = getRangeCount();

	// If the set contains at least 2 intervals and includes both
	// MIN_VALUE and MAX_VALUE, then the inverse representation will
	// be more economical.
	if (count > 1 &&
	getRangeStart(0) == MIN_VALUE &&
	getRangeEnd(count-1) == MAX_VALUE) {

	// Emit the inverse
	result.append('^');

	for (int i = 1; i < count; ++i) {
	int start = getRangeEnd(i-1)+1;
	int end = getRangeStart(i)-1;
	_appendToPat(result, start, escapeUnprintable);
	if (start != end) {
	if ((start+1) != end) {
	result.append('-');
	}
	_appendToPat(result, end, escapeUnprintable);
	}
	}
	}

	// Default; emit the ranges as pairs
	else {
	for (int i = 0; i < count; ++i) {
	int start = getRangeStart(i);
	int end = getRangeEnd(i);
	_appendToPat(result, start, escapeUnprintable);
	if (start != end) {
	if ((start+1) != end) {
	result.append('-');
	}
	_appendToPat(result, end, escapeUnprintable);
	}
	}
	}

	if (includeStrings && strings.size() > 0) {
	Iterator<String> it = strings.iterator();
	while (it.hasNext()) {
	result.append('{');
	_appendToPat(result, it.next(), escapeUnprintable);
	result.append('}');
	}
	}
	return result.append(']');
	}

	// for internal use, after checkFrozen has been called
	private UnicodeSet add_unchecked(int start, int end) {
	if (start < MIN_VALUE \|\| start > MAX_VALUE) {
	throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
	}
	if (end < MIN_VALUE \|\| end > MAX_VALUE) {
	throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
	}
	if (start < end) {
	add(range(start, end), 2, 0);
	} else if (start == end) {
	add(start);
	}
	return this;
	}

	/**
	* Adds the specified character to this set if it is not already
	* present. If this set already contains the specified character,
	* the call leaves this set unchanged.
	* @stable ICU 2.0
	*/
	public final UnicodeSet add(int c) {
	return add_unchecked(c);
	}

	// for internal use only, after checkFrozen has been called
	private final UnicodeSet add_unchecked(int c) {
	if (c < MIN_VALUE \|\| c > MAX_VALUE) {
	throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(c, 6));
	}

	// find smallest i such that c < list[i]
	// if odd, then it is IN the set
	// if even, then it is OUT of the set
	int i = findCodePoint(c);

	// already in set?
	if ((i & 1) != 0) return this;

	// HIGH is 0x110000
	// assert(list[len-1] == HIGH);

	// empty = [HIGH]
	// [start_0, limit_0, start_1, limit_1, HIGH]

	// [..., start_k-1, limit_k-1, start_k, limit_k, ..., HIGH]
	// ^
	// list[i]

	// i == 0 means c is before the first range

	if (c == list[i]-1) {
	// c is before start of next range
	list[i] = c;
	// if we touched the HIGH mark, then add a new one
	if (c == MAX_VALUE) {
	ensureCapacity(len+1);
	list[len++] = HIGH;
	}
	if (i > 0 && c == list[i-1]) {
	// collapse adjacent ranges

	// [..., start_k-1, c, c, limit_k, ..., HIGH]
	// ^
	// list[i]
	System.arraycopy(list, i+1, list, i-1, len-i-1);
	len -= 2;
	}
	}

	else if (i > 0 && c == list[i-1]) {
	// c is after end of prior range
	list[i-1]++;
	// no need to chcek for collapse here
	}

	else {
	// At this point we know the new char is not adjacent to
	// any existing ranges, and it is not 10FFFF.


	// [..., start_k-1, limit_k-1, start_k, limit_k, ..., HIGH]
	// ^
	// list[i]

	// [..., start_k-1, limit_k-1, c, c+1, start_k, limit_k, ..., HIGH]
	// ^
	// list[i]

	// Don't use ensureCapacity() to save on copying.
	// NOTE: This has no measurable impact on performance,
	// but it might help in some usage patterns.
	if (len+2 > list.length) {
	int[] temp = new int[len + 2 + GROW_EXTRA];
	if (i != 0) System.arraycopy(list, 0, temp, 0, i);
	System.arraycopy(list, i, temp, i+2, len-i);
	list = temp;
	} else {
	System.arraycopy(list, i, list, i+2, len-i);
	}

	list[i] = c;
	list[i+1] = c+1;
	len += 2;
	}

	pat = null;
	return this;
	}

	/**
	* Adds the specified multicharacter to this set if it is not already
	* present. If this set already contains the multicharacter,
	* the call leaves this set unchanged.
	* Thus "ch" => {"ch"}
	* <br><b>Warning: you cannot add an empty string ("") to a UnicodeSet.</b>
	* @param s the source string
	* @return this object, for chaining
	* @stable ICU 2.0
	*/
	public final UnicodeSet add(String s) {
	int cp = getSingleCP(s);
	if (cp < 0) {
	strings.add(s);
	pat = null;
	} else {
	add_unchecked(cp, cp);
	}
	return this;
	}

	/**
	* @return a code point IF the string consists of a single one.
	* otherwise returns -1.
	* @param string to test
	*/
	private static int getSingleCP(String s) {
	if (s.length() < 1) {
	throw new IllegalArgumentException("Can't use zero-length strings in UnicodeSet");
	}
	if (s.length() > 2) return -1;
	if (s.length() == 1) return s.charAt(0);

	// at this point, len = 2
	int cp = UTF16.charAt(s, 0);
	if (cp > 0xFFFF) { // is surrogate pair
	return cp;
	}
	return -1;
	}

	/**
	* Complements the specified range in this set. Any character in
	* the range will be removed if it is in this set, or will be
	* added if it is not in this set. If <code>end > start</code>
	* then an empty range is complemented, leaving the set unchanged.
	*
	* @param start first character, inclusive, of range to be removed
	* from this set.
	* @param end last character, inclusive, of range to be removed
	* from this set.
	* @stable ICU 2.0
	*/
	public UnicodeSet complement(int start, int end) {
	if (start < MIN_VALUE \|\| start > MAX_VALUE) {
	throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(start, 6));
	}
	if (end < MIN_VALUE \|\| end > MAX_VALUE) {
	throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(end, 6));
	}
	if (start <= end) {
	xor(range(start, end), 2, 0);
	}
	pat = null;
	return this;
	}

	/**
	* This is equivalent to
	* <code>complement(MIN_VALUE, MAX_VALUE)</code>.
	* @stable ICU 2.0
	*/
	public UnicodeSet complement() {
	if (list[0] == LOW) {
	System.arraycopy(list, 1, list, 0, len-1);
	--len;
	} else {
	ensureCapacity(len+1);
	System.arraycopy(list, 0, list, 1, len);
	list[0] = LOW;
	++len;
	}
	pat = null;
	return this;
	}

	/**
	* Returns true if this set contains the given character.
	* @param c character to be checked for containment
	* @return true if the test condition is met
	* @stable ICU 2.0
	*/
	public boolean contains(int c) {
	if (c < MIN_VALUE \|\| c > MAX_VALUE) {
	throw new IllegalArgumentException("Invalid code point U+" + Utility.hex(c, 6));
	}

	/*
	// Set i to the index of the start item greater than ch
	// We know we will terminate without length test!
	int i = -1;
	while (true) {
	if (c < list[++i]) break;
	}
	*/

	int i = findCodePoint(c);

	return ((i & 1) != 0); // return true if odd
	}

	/**
	* Returns the smallest value i such that c < list[i]. Caller
	* must ensure that c is a legal value or this method will enter
	* an infinite loop. This method performs a binary search.
	* @param c a character in the range MIN_VALUE..MAX_VALUE
	* inclusive
	* @return the smallest integer i in the range 0..len-1,
	* inclusive, such that c < list[i]
	*/
	private final int findCodePoint(int c) {
	/* Examples:
	findCodePoint(c)
	set list[] c=0 1 3 4 7 8
	=== ============== ===========
	[] [110000] 0 0 0 0 0 0
	[\u0000-\u0003] [0, 4, 110000] 1 1 1 2 2 2
	[\u0004-\u0007] [4, 8, 110000] 0 0 0 1 1 2
	[:all:] [0, 110000] 1 1 1 1 1 1
	*/

	// Return the smallest i such that c < list[i]. Assume
	// list[len - 1] == HIGH and that c is legal (0..HIGH-1).
	if (c < list[0]) return 0;
	// High runner test. c is often after the last range, so an
	// initial check for this condition pays off.
	if (len >= 2 && c >= list[len-2]) return len-1;
	int lo = 0;
	int hi = len - 1;
	// invariant: c >= list[lo]
	// invariant: c < list[hi]
	for (;;) {
	int i = (lo + hi) >>> 1;
	if (i == lo) return hi;
	if (c < list[i]) {
	hi = i;
	} else {
	lo = i;
	}
	}
	}

	/**
	* Adds all of the elements in the specified set to this set if
	* they're not already present. This operation effectively
	* modifies this set so that its value is the <i>union</i> of the two
	* sets. The behavior of this operation is unspecified if the specified
	* collection is modified while the operation is in progress.
	*
	* @param c set whose elements are to be added to this set.
	* @stable ICU 2.0
	*/
	public UnicodeSet addAll(UnicodeSet c) {
	add(c.list, c.len, 0);
	strings.addAll(c.strings);
	return this;
	}

	/**
	* Retains only the elements in this set that are contained in the
	* specified set. In other words, removes from this set all of
	* its elements that are not contained in the specified set. This
	* operation effectively modifies this set so that its value is
	* the <i>intersection</i> of the two sets.
	*
	* @param c set that defines which elements this set will retain.
	* @stable ICU 2.0
	*/
	public UnicodeSet retainAll(UnicodeSet c) {
	retain(c.list, c.len, 0);
	strings.retainAll(c.strings);
	return this;
	}

	/**
	* Removes from this set all of its elements that are contained in the
	* specified set. This operation effectively modifies this
	* set so that its value is the <i>asymmetric set difference</i> of
	* the two sets.
	*
	* @param c set that defines which elements will be removed from
	* this set.
	* @stable ICU 2.0
	*/
	public UnicodeSet removeAll(UnicodeSet c) {
	retain(c.list, c.len, 2);
	strings.removeAll(c.strings);
	return this;
	}

	/**
	* Removes all of the elements from this set. This set will be
	* empty after this call returns.
	* @stable ICU 2.0
	*/
	public UnicodeSet clear() {
	list[0] = HIGH;
	len = 1;
	pat = null;
	strings.clear();
	return this;
	}

	/**
	* Iteration method that returns the number of ranges contained in
	* this set.
	* @see #getRangeStart
	* @see #getRangeEnd
	* @stable ICU 2.0
	*/
	public int getRangeCount() {
	return len/2;
	}

	/**
	* Iteration method that returns the first character in the
	* specified range of this set.
	* @exception ArrayIndexOutOfBoundsException if index is outside
	* the range <code>0..getRangeCount()-1</code>
	* @see #getRangeCount
	* @see #getRangeEnd
	* @stable ICU 2.0
	*/
	public int getRangeStart(int index) {
	return list[index*2];
	}

	/**
	* Iteration method that returns the last character in the
	* specified range of this set.
	* @exception ArrayIndexOutOfBoundsException if index is outside
	* the range <code>0..getRangeCount()-1</code>
	* @see #getRangeStart
	* @see #getRangeEnd
	* @stable ICU 2.0
	*/
	public int getRangeEnd(int index) {
	return (list[index*2 + 1] - 1);
	}

	//----------------------------------------------------------------
	// Implementation: Pattern parsing
	//----------------------------------------------------------------

	/**
	* Parses the given pattern, starting at the given position. The character
	* at pattern.charAt(pos.getIndex()) must be '[', or the parse fails.
	* Parsing continues until the corresponding closing ']'. If a syntax error
	* is encountered between the opening and closing brace, the parse fails.
	* Upon return from a successful parse, the ParsePosition is updated to
	* point to the character following the closing ']', and an inversion
	* list for the parsed pattern is returned. This method
	* calls itself recursively to parse embedded subpatterns.
	*
	* @param pattern the string containing the pattern to be parsed. The
	* portion of the string from pos.getIndex(), which must be a '[', to the
	* corresponding closing ']', is parsed.
	* @param pos upon entry, the position at which to being parsing. The
	* character at pattern.charAt(pos.getIndex()) must be a '['. Upon return
	* from a successful parse, pos.getIndex() is either the character after the
	* closing ']' of the parsed pattern, or pattern.length() if the closing ']'
	* is the last character of the pattern string.
	* @return an inversion list for the parsed substring
	* of <code>pattern</code>
	* @exception java.lang.IllegalArgumentException if the parse fails.
	*/
	UnicodeSet applyPattern(String pattern,
	ParsePosition pos,
	SymbolTable symbols,
	int options) {

	// Need to build the pattern in a temporary string because
	// _applyPattern calls add() etc., which set pat to empty.
	boolean parsePositionWasNull = pos == null;
	if (parsePositionWasNull) {
	pos = new ParsePosition(0);
	}

	StringBuffer rebuiltPat = new StringBuffer();
	RuleCharacterIterator chars =
	new RuleCharacterIterator(pattern, symbols, pos);
	applyPattern(chars, symbols, rebuiltPat, options);
	if (chars.inVariable()) {
	syntaxError(chars, "Extra chars in variable value");
	}
	pat = rebuiltPat.toString();
	if (parsePositionWasNull) {
	int i = pos.getIndex();

	// Skip over trailing whitespace
	if ((options & IGNORE_SPACE) != 0) {
	i = Utility.skipWhitespace(pattern, i);
	}

	if (i != pattern.length()) {
	throw new IllegalArgumentException("Parse of \"" + pattern +
	"\" failed at " + i);
	}
	}
	return this;
	}

	/**
	* Parse the pattern from the given RuleCharacterIterator. The
	* iterator is advanced over the parsed pattern.
	* @param chars iterator over the pattern characters. Upon return
	* it will be advanced to the first character after the parsed
	* pattern, or the end of the iteration if all characters are
	* parsed.
	* @param symbols symbol table to use to parse and dereference
	* variables, or null if none.
	* @param rebuiltPat the pattern that was parsed, rebuilt or
	* copied from the input pattern, as appropriate.
	* @param options a bit mask of zero or more of the following:
	* IGNORE_SPACE, CASE.
	*/
	void applyPattern(RuleCharacterIterator chars, SymbolTable symbols,
	StringBuffer rebuiltPat, int options) {
	// Syntax characters: [ ] ^ - & { }

	// Recognized special forms for chars, sets: c-c s-s s&s

	int opts = RuleCharacterIterator.PARSE_VARIABLES \|
	RuleCharacterIterator.PARSE_ESCAPES;
	if ((options & IGNORE_SPACE) != 0) {
	opts \|= RuleCharacterIterator.SKIP_WHITESPACE;
	}

	StringBuffer patBuf = new StringBuffer(), buf = null;
	boolean usePat = false;
	UnicodeSet scratch = null;
	Object backup = null;

	// mode: 0=before [, 1=between [...], 2=after ]
	// lastItem: 0=none, 1=char, 2=set
	int lastItem = 0, lastChar = 0, mode = 0;
	char op = 0;

	boolean invert = false;

	clear();

	while (mode != 2 && !chars.atEnd()) {
	if (false) {
	// Debugging assertion
	if (!((lastItem == 0 && op == 0) \|\|
	(lastItem == 1 && (op == 0 \|\| op == '-')) \|\|
	(lastItem == 2 && (op == 0 \|\| op == '-' \|\| op == '&')))) {
	throw new IllegalArgumentException();
	}
	}

	int c = 0;
	boolean literal = false;
	UnicodeSet nested = null;

	// -------- Check for property pattern

	// setMode: 0=none, 1=unicodeset, 2=propertypat, 3=preparsed
	int setMode = 0;
	if (resemblesPropertyPattern(chars, opts)) {
	setMode = 2;
	}

	// -------- Parse '[' of opening delimiter OR nested set.
	// If there is a nested set, use `setMode' to define how
	// the set should be parsed. If the '[' is part of the
	// opening delimiter for this pattern, parse special
	// strings "[", "[^", "[-", and "[^-". Check for stand-in
	// characters representing a nested set in the symbol
	// table.

	else {
	// Prepare to backup if necessary
	backup = chars.getPos(backup);
	c = chars.next(opts);
	literal = chars.isEscaped();

	if (c == '[' && !literal) {
	if (mode == 1) {
	chars.setPos(backup); // backup
	setMode = 1;
	} else {
	// Handle opening '[' delimiter
	mode = 1;
	patBuf.append('[');
	backup = chars.getPos(backup); // prepare to backup
	c = chars.next(opts);
	literal = chars.isEscaped();
	if (c == '^' && !literal) {
	invert = true;
	patBuf.append('^');
	backup = chars.getPos(backup); // prepare to backup
	c = chars.next(opts);
	literal = chars.isEscaped();
	}
	// Fall through to handle special leading '-';
	// otherwise restart loop for nested [], \p{}, etc.
	if (c == '-') {
	literal = true;
	// Fall through to handle literal '-' below
	} else {
	chars.setPos(backup); // backup
	continue;
	}
	}
	} else if (symbols != null) {
	UnicodeMatcher m = symbols.lookupMatcher(c); // may be null
	if (m != null) {
	try {
	nested = (UnicodeSet) m;
	setMode = 3;
	} catch (ClassCastException e) {
	syntaxError(chars, "Syntax error");
	}
	}
	}
	}

	// -------- Handle a nested set. This either is inline in
	// the pattern or represented by a stand-in that has
	// previously been parsed and was looked up in the symbol
	// table.

	if (setMode != 0) {
	if (lastItem == 1) {
	if (op != 0) {
	syntaxError(chars, "Char expected after operator");
	}
	add_unchecked(lastChar, lastChar);
	_appendToPat(patBuf, lastChar, false);
	lastItem = op = 0;
	}

	if (op == '-' \|\| op == '&') {
	patBuf.append(op);
	}

	if (nested == null) {
	if (scratch == null) scratch = new UnicodeSet();
	nested = scratch;
	}
	switch (setMode) {
	case 1:
	nested.applyPattern(chars, symbols, patBuf, options);
	break;
	case 2:
	chars.skipIgnored(opts);
	nested.applyPropertyPattern(chars, patBuf, symbols);
	break;
	case 3: // `nested' already parsed
	nested._toPattern(patBuf, false);
	break;
	}

	usePat = true;

	if (mode == 0) {
	// Entire pattern is a category; leave parse loop
	set(nested);
	mode = 2;
	break;
	}

	switch (op) {
	case '-':
	removeAll(nested);
	break;
	case '&':
	retainAll(nested);
	break;
	case 0:
	addAll(nested);
	break;
	}

	op = 0;
	lastItem = 2;

	continue;
	}

	if (mode == 0) {
	syntaxError(chars, "Missing '['");
	}

	// -------- Parse special (syntax) characters. If the
	// current character is not special, or if it is escaped,
	// then fall through and handle it below.

	if (!literal) {
	switch (c) {
	case ']':
	if (lastItem == 1) {
	add_unchecked(lastChar, lastChar);
	_appendToPat(patBuf, lastChar, false);
	}
	// Treat final trailing '-' as a literal
	if (op == '-') {
	add_unchecked(op, op);
	patBuf.append(op);
	} else if (op == '&') {
	syntaxError(chars, "Trailing '&'");
	}
	patBuf.append(']');
	mode = 2;
	continue;
	case '-':
	if (op == 0) {
	if (lastItem != 0) {
	op = (char) c;
	continue;
	} else {
	// Treat final trailing '-' as a literal
	add_unchecked(c, c);
	c = chars.next(opts);
	literal = chars.isEscaped();
	if (c == ']' && !literal) {
	patBuf.append("-]");
	mode = 2;
	continue;
	}
	}
	}
	syntaxError(chars, "'-' not after char or set");
	break;
	case '&':
	if (lastItem == 2 && op == 0) {
	op = (char) c;
	continue;
	}
	syntaxError(chars, "'&' not after set");
	break;
	case '^':
	syntaxError(chars, "'^' not after '['");
	break;
	case '{':
	if (op != 0) {
	syntaxError(chars, "Missing operand after operator");
	}
	if (lastItem == 1) {
	add_unchecked(lastChar, lastChar);
	_appendToPat(patBuf, lastChar, false);
	}
	lastItem = 0;
	if (buf == null) {
	buf = new StringBuffer();
	} else {
	buf.setLength(0);
	}
	boolean ok = false;
	while (!chars.atEnd()) {
	c = chars.next(opts);
	literal = chars.isEscaped();
	if (c == '}' && !literal) {
	ok = true;
	break;
	}
	UTF16.append(buf, c);
	}
	if (buf.length() < 1 \|\| !ok) {
	syntaxError(chars, "Invalid multicharacter string");
	}
	// We have new string. Add it to set and continue;
	// we don't need to drop through to the further
	// processing
	add(buf.toString());
	patBuf.append('{');
	_appendToPat(patBuf, buf.toString(), false);
	patBuf.append('}');
	continue;
	case SymbolTable.SYMBOL_REF:
	// symbols nosymbols
	// [a-$] error error (ambiguous)
	// [a$] anchor anchor
	// [a-$x] var "x"* literal '$'
	// [a-$.] error literal '$'
	// *We won't get here in the case of var "x"
	backup = chars.getPos(backup);
	c = chars.next(opts);
	literal = chars.isEscaped();
	boolean anchor = (c == ']' && !literal);
	if (symbols == null && !anchor) {
	c = SymbolTable.SYMBOL_REF;
	chars.setPos(backup);
	break; // literal '$'
	}
	if (anchor && op == 0) {
	if (lastItem == 1) {
	add_unchecked(lastChar, lastChar);
	_appendToPat(patBuf, lastChar, false);
	}
	add_unchecked(UnicodeMatcher.ETHER);
	usePat = true;
	patBuf.append(SymbolTable.SYMBOL_REF).append(']');
	mode = 2;
	continue;
	}
	syntaxError(chars, "Unquoted '$'");
	break;
	default:
	break;
	}
	}

	// -------- Parse literal characters. This includes both
	// escaped chars ("\u4E01") and non-syntax characters
	// ("a").

	switch (lastItem) {
	case 0:
	lastItem = 1;
	lastChar = c;
	break;
	case 1:
	if (op == '-') {
	if (lastChar >= c) {
	// Don't allow redundant (a-a) or empty (b-a) ranges;
	// these are most likely typos.
	syntaxError(chars, "Invalid range");
	}
	add_unchecked(lastChar, c);
	_appendToPat(patBuf, lastChar, false);
	patBuf.append(op);
	_appendToPat(patBuf, c, false);
	lastItem = op = 0;
	} else {
	add_unchecked(lastChar, lastChar);
	_appendToPat(patBuf, lastChar, false);
	lastChar = c;
	}
	break;
	case 2:
	if (op != 0) {
	syntaxError(chars, "Set expected after operator");
	}
	lastChar = c;
	lastItem = 1;
	break;
	}
	}

	if (mode != 2) {
	syntaxError(chars, "Missing ']'");
	}

	chars.skipIgnored(opts);

	if (invert) {
	complement();
	}

	// Use the rebuilt pattern (pat) only if necessary. Prefer the
	// generated pattern.
	if (usePat) {
	rebuiltPat.append(patBuf.toString());
	} else {
	_generatePattern(rebuiltPat, false, true);
	}
	}

	private static void syntaxError(RuleCharacterIterator chars, String msg) {
	throw new IllegalArgumentException("Error: " + msg + " at \"" +
	Utility.escape(chars.toString()) +
	'"');
	}

	//----------------------------------------------------------------
	// Implementation: Utility methods
	//----------------------------------------------------------------

	private void ensureCapacity(int newLen) {
	if (newLen <= list.length) return;
	int[] temp = new int[newLen + GROW_EXTRA];
	System.arraycopy(list, 0, temp, 0, len);
	list = temp;
	}

	private void ensureBufferCapacity(int newLen) {
	if (buffer != null && newLen <= buffer.length) return;
	buffer = new int[newLen + GROW_EXTRA];
	}

	/**
	* Assumes start <= end.
	*/
	private int[] range(int start, int end) {
	if (rangeList == null) {
	rangeList = new int[] { start, end+1, HIGH };
	} else {
	rangeList[0] = start;
	rangeList[1] = end+1;
	}
	return rangeList;
	}

	//----------------------------------------------------------------
	// Implementation: Fundamental operations
	//----------------------------------------------------------------

	// polarity = 0, 3 is normal: x xor y
	// polarity = 1, 2: x xor ~y == x === y

	private UnicodeSet xor(int[] other, int otherLen, int polarity) {
	ensureBufferCapacity(len + otherLen);
	int i = 0, j = 0, k = 0;
	int a = list[i++];
	int b;
	if (polarity == 1 \|\| polarity == 2) {
	b = LOW;
	if (other[j] == LOW) { // skip base if already LOW
	++j;
	b = other[j];
	}
	} else {
	b = other[j++];
	}
	// simplest of all the routines
	// sort the values, discarding identicals!
	while (true) {
	if (a < b) {
	buffer[k++] = a;
	a = list[i++];
	} else if (b < a) {
	buffer[k++] = b;
	b = other[j++];
	} else if (a != HIGH) { // at this point, a == b
	// discard both values!
	a = list[i++];
	b = other[j++];
	} else { // DONE!
	buffer[k++] = HIGH;
	len = k;
	break;
	}
	}
	// swap list and buffer
	int[] temp = list;
	list = buffer;
	buffer = temp;
	pat = null;
	return this;
	}

	// polarity = 0 is normal: x union y
	// polarity = 2: x union ~y
	// polarity = 1: ~x union y
	// polarity = 3: ~x union ~y

	private UnicodeSet add(int[] other, int otherLen, int polarity) {
	ensureBufferCapacity(len + otherLen);
	int i = 0, j = 0, k = 0;
	int a = list[i++];
	int b = other[j++];
	// change from xor is that we have to check overlapping pairs
	// polarity bit 1 means a is second, bit 2 means b is.
	main:
	while (true) {
	switch (polarity) {
	case 0: // both first; take lower if unequal
	if (a < b) { // take a
	// Back up over overlapping ranges in buffer[]
	if (k > 0 && a <= buffer[k-1]) {
	// Pick latter end value in buffer[] vs. list[]
	a = max(list[i], buffer[--k]);
	} else {
	// No overlap
	buffer[k++] = a;
	a = list[i];
	}
	i++; // Common if/else code factored out
	polarity ^= 1;
	} else if (b < a) { // take b
	if (k > 0 && b <= buffer[k-1]) {
	b = max(other[j], buffer[--k]);
	} else {
	buffer[k++] = b;
	b = other[j];
	}
	j++;
	polarity ^= 2;
	} else { // a == b, take a, drop b
	if (a == HIGH) break main;
	// This is symmetrical; it doesn't matter if
	// we backtrack with a or b. - liu
	if (k > 0 && a <= buffer[k-1]) {
	a = max(list[i], buffer[--k]);
	} else {
	// No overlap
	buffer[k++] = a;
	a = list[i];
	}
	i++;
	polarity ^= 1;
	b = other[j++]; polarity ^= 2;
	}
	break;
	case 3: // both second; take higher if unequal, and drop other
	if (b <= a) { // take a
	if (a == HIGH) break main;
	buffer[k++] = a;
	} else { // take b
	if (b == HIGH) break main;
	buffer[k++] = b;
	}
	a = list[i++]; polarity ^= 1; // factored common code
	b = other[j++]; polarity ^= 2;
	break;
	case 1: // a second, b first; if b < a, overlap
	if (a < b) { // no overlap, take a
	buffer[k++] = a; a = list[i++]; polarity ^= 1;
	} else if (b < a) { // OVERLAP, drop b
	b = other[j++]; polarity ^= 2;
	} else { // a == b, drop both!
	if (a == HIGH) break main;
	a = list[i++]; polarity ^= 1;
	b = other[j++]; polarity ^= 2;
	}
	break;
	case 2: // a first, b second; if a < b, overlap
	if (b < a) { // no overlap, take b
	buffer[k++] = b; b = other[j++]; polarity ^= 2;
	} else if (a < b) { // OVERLAP, drop a
	a = list[i++]; polarity ^= 1;
	} else { // a == b, drop both!
	if (a == HIGH) break main;
	a = list[i++]; polarity ^= 1;
	b = other[j++]; polarity ^= 2;
	}
	break;
	}
	}
	buffer[k++] = HIGH; // terminate
	len = k;
	// swap list and buffer
	int[] temp = list;
	list = buffer;
	buffer = temp;
	pat = null;
	return this;
	}

	// polarity = 0 is normal: x intersect y
	// polarity = 2: x intersect ~y == set-minus
	// polarity = 1: ~x intersect y
	// polarity = 3: ~x intersect ~y

	private UnicodeSet retain(int[] other, int otherLen, int polarity) {
	ensureBufferCapacity(len + otherLen);
	int i = 0, j = 0, k = 0;
	int a = list[i++];
	int b = other[j++];
	// change from xor is that we have to check overlapping pairs
	// polarity bit 1 means a is second, bit 2 means b is.
	main:
	while (true) {
	switch (polarity) {
	case 0: // both first; drop the smaller
	if (a < b) { // drop a
	a = list[i++]; polarity ^= 1;
	} else if (b < a) { // drop b
	b = other[j++]; polarity ^= 2;
	} else { // a == b, take one, drop other
	if (a == HIGH) break main;
	buffer[k++] = a; a = list[i++]; polarity ^= 1;
	b = other[j++]; polarity ^= 2;
	}
	break;
	case 3: // both second; take lower if unequal
	if (a < b) { // take a
	buffer[k++] = a; a = list[i++]; polarity ^= 1;
	} else if (b < a) { // take b
	buffer[k++] = b; b = other[j++]; polarity ^= 2;
	} else { // a == b, take one, drop other
	if (a == HIGH) break main;
	buffer[k++] = a; a = list[i++]; polarity ^= 1;
	b = other[j++]; polarity ^= 2;
	}
	break;
	case 1: // a second, b first;
	if (a < b) { // NO OVERLAP, drop a
	a = list[i++]; polarity ^= 1;
	} else if (b < a) { // OVERLAP, take b
	buffer[k++] = b; b = other[j++]; polarity ^= 2;
	} else { // a == b, drop both!
	if (a == HIGH) break main;
	a = list[i++]; polarity ^= 1;
	b = other[j++]; polarity ^= 2;
	}
	break;
	case 2: // a first, b second; if a < b, overlap
	if (b < a) { // no overlap, drop b
	b = other[j++]; polarity ^= 2;
	} else if (a < b) { // OVERLAP, take a
	buffer[k++] = a; a = list[i++]; polarity ^= 1;
	} else { // a == b, drop both!
	if (a == HIGH) break main;
	a = list[i++]; polarity ^= 1;
	b = other[j++]; polarity ^= 2;
	}
	break;
	}
	}
	buffer[k++] = HIGH; // terminate
	len = k;
	// swap list and buffer
	int[] temp = list;
	list = buffer;
	buffer = temp;
	pat = null;
	return this;
	}

	private static final int max(int a, int b) {
	return (a > b) ? a : b;
	}

	//----------------------------------------------------------------
	// Generic filter-based scanning code
	//----------------------------------------------------------------

	private static interface Filter {
	boolean contains(int codePoint);
	}

	// VersionInfo for unassigned characters
	static final VersionInfo NO_VERSION = VersionInfo.getInstance(0, 0, 0, 0);

	private static class VersionFilter implements Filter {
	VersionInfo version;

	VersionFilter(VersionInfo version) { this.version = version; }

	public boolean contains(int ch) {
	VersionInfo v = UCharacter.getAge(ch);
	// Reference comparison ok; VersionInfo caches and reuses
	// unique objects.
	return v != NO_VERSION &&
	v.compareTo(version) <= 0;
	}
	}

	private static synchronized UnicodeSet getInclusions(int src) {
	if (INCLUSIONS == null) {
	INCLUSIONS = new UnicodeSet[UCharacterProperty.SRC_COUNT];
	}
	if(INCLUSIONS[src] == null) {
	UnicodeSet incl = new UnicodeSet();
	switch(src) {
	case UCharacterProperty.SRC_PROPSVEC:
	UCharacterProperty.getInstance().upropsvec_addPropertyStarts(incl);
	break;
	default:
	throw new IllegalStateException("UnicodeSet.getInclusions(unknown src "+src+")");
	}
	INCLUSIONS[src] = incl;
	}
	return INCLUSIONS[src];
	}

	/**
	* Generic filter-based scanning code for UCD property UnicodeSets.
	*/
	private UnicodeSet applyFilter(Filter filter, int src) {
	// Walk through all Unicode characters, noting the start
	// and end of each range for which filter.contain(c) is
	// true. Add each range to a set.
	//
	// To improve performance, use the INCLUSIONS set, which
	// encodes information about character ranges that are known
	// to have identical properties, such as the CJK Ideographs
	// from U+4E00 to U+9FA5. INCLUSIONS contains all characters
	// except the first characters of such ranges.
	//
	// TODO Where possible, instead of scanning over code points,
	// use internal property data to initialize UnicodeSets for
	// those properties. Scanning code points is slow.

	clear();

	int startHasProperty = -1;
	UnicodeSet inclusions = getInclusions(src);
	int limitRange = inclusions.getRangeCount();

	for (int j=0; j<limitRange; ++j) {
	// get current range
	int start = inclusions.getRangeStart(j);
	int end = inclusions.getRangeEnd(j);

	// for all the code points in the range, process
	for (int ch = start; ch <= end; ++ch) {
	// only add to the unicodeset on inflection points --
	// where the hasProperty value changes to false
	if (filter.contains(ch)) {
	if (startHasProperty < 0) {
	startHasProperty = ch;
	}
	} else if (startHasProperty >= 0) {
	add_unchecked(startHasProperty, ch-1);
	startHasProperty = -1;
	}
	}
	}
	if (startHasProperty >= 0) {
	add_unchecked(startHasProperty, 0x10FFFF);
	}

	return this;
	}

	/**
	* Remove leading and trailing rule white space and compress
	* internal rule white space to a single space character.
	*
	* @see UCharacterProperty#isRuleWhiteSpace
	*/
	private static String mungeCharName(String source) {
	StringBuffer buf = new StringBuffer();
	for (int i=0; i<source.length(); ) {
	int ch = UTF16.charAt(source, i);
	i += UTF16.getCharCount(ch);
	if (UCharacterProperty.isRuleWhiteSpace(ch)) {
	if (buf.length() == 0 \|\|
	buf.charAt(buf.length() - 1) == ' ') {
	continue;
	}
	ch = ' '; // convert to ' '
	}
	UTF16.append(buf, ch);
	}
	if (buf.length() != 0 &&
	buf.charAt(buf.length() - 1) == ' ') {
	buf.setLength(buf.length() - 1);
	}
	return buf.toString();
	}

	/**
	* Modifies this set to contain those code points which have the
	* given value for the given property. Prior contents of this
	* set are lost.
	* @param propertyAlias
	* @param valueAlias
	* @param symbols if not null, then symbols are first called to see if a property
	* is available. If true, then everything else is skipped.
	* @return this set
	* @stable ICU 3.2
	*/
	public UnicodeSet applyPropertyAlias(String propertyAlias,
	String valueAlias, SymbolTable symbols) {
	if (valueAlias.length() > 0) {
	if (propertyAlias.equals("Age")) {
	// Must munge name, since
	// VersionInfo.getInstance() does not do
	// 'loose' matching.
	VersionInfo version = VersionInfo.getInstance(mungeCharName(valueAlias));
	applyFilter(new VersionFilter(version), UCharacterProperty.SRC_PROPSVEC);
	return this;
	}
	}
	throw new IllegalArgumentException("Unsupported property: " + propertyAlias);
	}

	/**
	* Return true if the given iterator appears to point at a
	* property pattern. Regardless of the result, return with the
	* iterator unchanged.
	* @param chars iterator over the pattern characters. Upon return
	* it will be unchanged.
	* @param iterOpts RuleCharacterIterator options
	*/
	private static boolean resemblesPropertyPattern(RuleCharacterIterator chars,
	int iterOpts) {
	boolean result = false;
	iterOpts &= ~RuleCharacterIterator.PARSE_ESCAPES;
	Object pos = chars.getPos(null);
	int c = chars.next(iterOpts);
	if (c == '[' \|\| c == '\\') {
	int d = chars.next(iterOpts & ~RuleCharacterIterator.SKIP_WHITESPACE);
	result = (c == '[') ? (d == ':') :
	(d == 'N' \|\| d == 'p' \|\| d == 'P');
	}
	chars.setPos(pos);
	return result;
	}

	/**
	* Parse the given property pattern at the given parse position.
	* @param symbols TODO
	*/
	private UnicodeSet applyPropertyPattern(String pattern, ParsePosition ppos, SymbolTable symbols) {
	int pos = ppos.getIndex();

	// On entry, ppos should point to one of the following locations:

	// Minimum length is 5 characters, e.g. \p{L}
	if ((pos+5) > pattern.length()) {
	return null;
	}

	boolean posix = false; // true for [:pat:], false for \p{pat} \P{pat} \N{pat}
	boolean isName = false; // true for \N{pat}, o/w false
	boolean invert = false;

	// Look for an opening [:, [:^, \p, or \P
	if (pattern.regionMatches(pos, "[:", 0, 2)) {
	posix = true;
	pos = Utility.skipWhitespace(pattern, pos+2);
	if (pos < pattern.length() && pattern.charAt(pos) == '^') {
	++pos;
	invert = true;
	}
	} else if (pattern.regionMatches(true, pos, "\\p", 0, 2) \|\|
	pattern.regionMatches(pos, "\\N", 0, 2)) {
	char c = pattern.charAt(pos+1);
	invert = (c == 'P');
	isName = (c == 'N');
	pos = Utility.skipWhitespace(pattern, pos+2);
	if (pos == pattern.length() \|\| pattern.charAt(pos++) != '{') {
	// Syntax error; "\p" or "\P" not followed by "{"
	return null;
	}
	} else {
	// Open delimiter not seen
	return null;
	}

	// Look for the matching close delimiter, either :] or }
	int close = pattern.indexOf(posix ? ":]" : "}", pos);
	if (close < 0) {
	// Syntax error; close delimiter missing
	return null;
	}

	// Look for an '=' sign. If this is present, we will parse a
	// medium \p{gc=Cf} or long \p{GeneralCategory=Format}
	// pattern.
	int equals = pattern.indexOf('=', pos);
	String propName, valueName;
	if (equals >= 0 && equals < close && !isName) {
	// Equals seen; parse medium/long pattern
	propName = pattern.substring(pos, equals);
	valueName = pattern.substring(equals+1, close);
	}

	else {
	// Handle case where no '=' is seen, and \N{}
	propName = pattern.substring(pos, close);
	valueName = "";

	// Handle \N{name}
	if (isName) {
	// This is a little inefficient since it means we have to
	// parse "na" back to UProperty.NAME even though we already
	// know it's UProperty.NAME. If we refactor the API to
	// support args of (int, String) then we can remove
	// "na" and make this a little more efficient.
	valueName = propName;
	propName = "na";
	}
	}

	applyPropertyAlias(propName, valueName, symbols);

	if (invert) {
	complement();
	}

	// Move to the limit position after the close delimiter
	ppos.setIndex(close + (posix ? 2 : 1));

	return this;
	}

	/**
	* Parse a property pattern.
	* @param chars iterator over the pattern characters. Upon return
	* it will be advanced to the first character after the parsed
	* pattern, or the end of the iteration if all characters are
	* parsed.
	* @param rebuiltPat the pattern that was parsed, rebuilt or
	* copied from the input pattern, as appropriate.
	* @param symbols TODO
	*/
	private void applyPropertyPattern(RuleCharacterIterator chars,
	StringBuffer rebuiltPat, SymbolTable symbols) {
	String patStr = chars.lookahead();
	ParsePosition pos = new ParsePosition(0);
	applyPropertyPattern(patStr, pos, symbols);
	if (pos.getIndex() == 0) {
	syntaxError(chars, "Invalid property pattern");
	}
	chars.jumpahead(pos.getIndex());
	rebuiltPat.append(patStr.substring(0, pos.getIndex()));
	}

	//----------------------------------------------------------------
	// Case folding API
	//----------------------------------------------------------------

	/**
	* Bitmask for constructor and applyPattern() indicating that
	* white space should be ignored. If set, ignore characters for
	* which UCharacterProperty.isRuleWhiteSpace() returns true,
	* unless they are quoted or escaped. This may be ORed together
	* with other selectors.
	* @stable ICU 3.8
	*/
	public static final int IGNORE_SPACE = 1;

	}

Back to index...