/*

***************************************************************************

* Copyright (C) 1999-2005, International Business Machines Corporation

* and others. All Rights Reserved.

***************************************************************************

*   Date        Name        Description

*   10/20/99    alan        Creation.

***************************************************************************

*/

#ifndef UNICODESET_H

#define UNICODESET_H

#include "unicode/unifilt.h"

#include "unicode/unistr.h"

#include "unicode/uset.h"

/**

 * \file 

 * \brief C++ API: Unicode Set

 */

U_NAMESPACE_BEGIN

class ParsePosition;

class SymbolTable;

class UVector;

class RuleCharacterIterator;

/**

 * 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:

 *

 * \htmlonly<blockquote>\endhtmlonly

 *   <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 &quot;ab&quot; and

 *       &quot;ac&quot;</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>

 * \htmlonly</blockquote>\endhtmlonly

 *

 * Any character may be preceded by a backslash in order to remove any special

 * meaning.  White space characters, as defined by UCharacter.isWhitespace(), 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://icu.sourceforge.net/userguide/unicodeSet.html">

 * http://icu.sourceforge.net/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>

 *

 * \htmlonly<blockquote>\endhtmlonly

 *   <table>

 *     <tr align="top">

 *       <td nowrap valign="top" align="right"><code>pattern :=&nbsp; </code></td>

 *       <td valign="top"><code>('[' '^'? item* ']') |

 *       property</code></td>

 *     </tr>

 *     <tr align="top">

 *       <td nowrap valign="top" align="right"><code>item :=&nbsp; </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 :=&nbsp; </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 :=&nbsp; </code></td>

 *       <td valign="top"><code>'&amp;' | '-'<br>

 *       </code></td>

 *     </tr>

 *     <tr align="top">

 *       <td nowrap valign="top" align="right"><code>special :=&nbsp; </code></td>

 *       <td valign="top"><code>'[' | ']' | '-'<br>

 *       </code></td>

 *     </tr>

 *     <tr align="top">

 *       <td nowrap valign="top" align="right"><code>char :=&nbsp; </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 :=&nbsp; </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 :=&nbsp; </code></td>

 *       <td valign="top"><em>a Unicode property set pattern</em></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">&nbsp; </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>

 * \htmlonly</blockquote>\endhtmlonly

 *

 * @author Alan Liu

 * @stable ICU 2.0

 */

class U_COMMON_API UnicodeSet : public UnicodeFilter {

    int32_t len; // length of list used; 0 <= len <= capacity

    int32_t capacity; // capacity of list

    int32_t bufferCapacity; // capacity of buffer

    UChar32* list; // MUST be terminated with HIGH

    UChar32* buffer; // internal buffer, may be NULL

    UVector* strings; // maintained in sorted order

    /**

     * 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 empty,

     * indicating that toPattern() must generate a pattern

     * representation from the inversion list.

     */

    UnicodeString pat;

public:

    enum {

        /**

         * Minimum value that can be stored in a UnicodeSet.

         * @stable ICU 2.4

         */

        MIN_VALUE = 0,

        /**

         * Maximum value that can be stored in a UnicodeSet.

         * @stable ICU 2.4

         */

        MAX_VALUE = 0x10ffff

    };

    //----------------------------------------------------------------

    // Constructors &c

    //----------------------------------------------------------------

public:

    /**

     * Constructs an empty set.

     * @stable ICU 2.0

     */

    UnicodeSet();

    /**

     * 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.4

     */

    UnicodeSet(UChar32 start, UChar32 end);

    /**

     * Constructs a set from the given pattern.  See the class

     * description for the syntax of the pattern language.

     * @param pattern a string specifying what characters are in the set

     * @param status returns <code>U_ILLEGAL_ARGUMENT_ERROR</code> if the pattern

     * contains a syntax error.

     * @stable ICU 2.0

     */

    UnicodeSet(const UnicodeString& pattern,

               UErrorCode& status);

    /**

     * Constructs a set from the given pattern.  See the class

     * description for the syntax of the pattern language.

     * @param pattern a string specifying what characters are in the set

     * @param options bitmask for options to apply to the pattern.

     * Valid options are USET_IGNORE_SPACE and USET_CASE_INSENSITIVE.

     * @param symbols a symbol table mapping variable names to values

     * and stand-in characters to UnicodeSets; may be NULL

     * @param status returns <code>U_ILLEGAL_ARGUMENT_ERROR</code> if the pattern

     * contains a syntax error.

     * @internal

     */

    UnicodeSet(const UnicodeString& pattern,

               uint32_t options,

               const SymbolTable* symbols,

               UErrorCode& status);

    /**

     * Constructs a set from the given pattern.  See the class description

     * for the syntax of the pattern language.

     * @param pattern a string specifying what characters are in the set

     * @param pos on input, the position in pattern at which to start parsing.

     * On output, the position after the last character parsed.

     * @param options bitmask for options to apply to the pattern.

     * Valid options are USET_IGNORE_SPACE and USET_CASE_INSENSITIVE.

     * @param symbols a symbol table mapping variable names to values

     * and stand-in characters to UnicodeSets; may be NULL

     * @param status input-output error code

     * @stable ICU 2.8

     */

    UnicodeSet(const UnicodeString& pattern, ParsePosition& pos,

               uint32_t options,

               const SymbolTable* symbols,

               UErrorCode& status);

#ifdef U_USE_UNICODESET_DEPRECATES

    /**

     * Obsolete: Constructs a set from the given Unicode character category.

     * @param category an integer indicating the character category as

     * defined in uchar.h.

     * @obsolete ICU 2.6. Use a pattern with the category instead since this API will be removed in that release.

     */

    UnicodeSet(int8_t category, UErrorCode& status);

#endif

    /**

     * Constructs a set that is identical to the given UnicodeSet.

     * @stable ICU 2.0

     */

    UnicodeSet(const UnicodeSet& o);

    /**

     * Destructs the set.

     * @stable ICU 2.0

     */

    virtual ~UnicodeSet();

    /**

     * Assigns this object to be a copy of another.

     * @stable ICU 2.0

     */

    UnicodeSet& operator=(const UnicodeSet& o);

    /**

     * Compares the specified object with this set for equality.  Returns

     * <tt>true</tt> if the two sets

     * have the same size, and every member of the specified set is

     * contained in this set (or equivalently, every member of this set is

     * contained in the specified set).

     *

     * @param o set to be compared for equality with this set.

     * @return <tt>true</tt> if the specified set is equal to this set.

     * @stable ICU 2.0

     */

    virtual UBool operator==(const UnicodeSet& o) const;

    /**

     * Compares the specified object with this set for equality.  Returns

     * <tt>true</tt> if the specified set is not equal to this set.

     * @stable ICU 2.0

     */

    UBool operator!=(const UnicodeSet& o) const;

    /**

     * Returns a copy of this object.  All UnicodeFunctor objects have

     * to support cloning in order to allow classes using

     * UnicodeFunctors, such as Transliterator, to implement cloning.

     * @stable ICU 2.0

     */

    virtual UnicodeFunctor* clone() const;

    /**

     * Returns the hash code value for this set.

     *

     * @return the hash code value for this set.

     * @see Object#hashCode()

     * @stable ICU 2.0

     */

    virtual int32_t hashCode(void) const;

    //----------------------------------------------------------------

    // Public API

    //----------------------------------------------------------------

    /**

     * Make this object represent the range <code>start - end</code>.

     * If <code>end > start</code> then this object is set to an

     * an empty range.

     *

     * @param start first character in the set, inclusive

     * @param end last character in the set, inclusive

     * @stable ICU 2.4

     */

    UnicodeSet& set(UChar32 start, UChar32 end);

    /**

     * Return true if the given position, in the given pattern, appears

     * to be the start of a UnicodeSet pattern.

     * @stable ICU 2.4

     */

    static UBool resemblesPattern(const UnicodeString& pattern,

                                  int32_t pos);

    /**

     * Modifies this set to represent the set specified by the given

     * pattern, optionally ignoring white space.  See the class

     * description for the syntax of the pattern language.

     * @param pattern a string specifying what characters are in the set

     * @param status returns <code>U_ILLEGAL_ARGUMENT_ERROR</code> if the pattern

     * contains a syntax error.

     * <em> Empties the set passed before applying the pattern.</em>

     * @return a reference to this

     * @stable ICU 2.0

     */

    UnicodeSet& applyPattern(const UnicodeString& pattern,

                             UErrorCode& status);

    /**

     * Modifies this set to represent the set specified by the given

     * pattern, optionally ignoring white space.  See the class

     * description for the syntax of the pattern language.

     * @param pattern a string specifying what characters are in the set

     * @param options bitmask for options to apply to the pattern.

     * Valid options are USET_IGNORE_SPACE and USET_CASE_INSENSITIVE.

     * @param symbols a symbol table mapping variable names to

     * values and stand-ins to UnicodeSets; may be NULL

     * @param status returns <code>U_ILLEGAL_ARGUMENT_ERROR</code> if the pattern

     * contains a syntax error.

     *<em> Empties the set passed before applying the pattern.</em>

     * @return a reference to this

     * @internal

     */

    UnicodeSet& applyPattern(const UnicodeString& pattern,

                             uint32_t options,

                             const SymbolTable* symbols,

                             UErrorCode& status);

    /**

     * 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 a StringBuffer containing a

     * pairs list for the parsed pattern is returned.  This method calls

     * itself recursively to parse embedded subpatterns.

     *<em> Empties the set passed before applying the pattern.</em>

     *

     * @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.

     * @param options bitmask for options to apply to the pattern.

     * Valid options are USET_IGNORE_SPACE and USET_CASE_INSENSITIVE.

     * @param symbols a symbol table mapping variable names to

     * values and stand-ins to UnicodeSets; may be NULL

     * @param status returns <code>U_ILLEGAL_ARGUMENT_ERROR</code> if the pattern

     * contains a syntax error.

     * @return a reference to this

     * @stable ICU 2.8

     */

    UnicodeSet& applyPattern(const UnicodeString& pattern,

                             ParsePosition& pos,

                             uint32_t options,

                             const SymbolTable* symbols,

                             UErrorCode& status);

    /**

     * Returns a string representation of this set.  If the result of

     * calling this function is passed to a UnicodeSet constructor, it

     * will produce another set that is equal to this one.

     * @param result the string to receive the rules.  Previous