home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / i18n / uniset.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-26  |  40.2 KB  |  1,142 lines
  1. /*
  2. **********************************************************************
  3. *   Copyright (C) 1999 Alan Liu and others. All rights reserved.
  4. **********************************************************************
  5. *   Date        Name        Description
  6. *   10/20/99    alan        Creation.
  7. **********************************************************************
  8. */
  9.  
  10. #include "uniset.h"
  11. #include "parsepos.h"
  12.  
  13. // N.B.: This mapping is different in ICU and Java
  14. const UnicodeString UnicodeSet::CATEGORY_NAMES(
  15.     "CnLuLlLtLmLoMnMeMcNdNlNoZsZlZpCcCfCoCsPdPsPePcPoSmScSkSoPiPf");
  16.  
  17. /**
  18.  * A cache mapping character category integers, as returned by
  19.  * Unicode::getType(), to pairs strings.  Entries are initially
  20.  * zero length and are filled in on demand.
  21.  */
  22. UnicodeString* UnicodeSet::CATEGORY_PAIRS_CACHE =
  23.      new UnicodeString[Unicode::GENERAL_TYPES_COUNT];
  24.  
  25. //----------------------------------------------------------------
  26. // Debugging and testing
  27. //----------------------------------------------------------------
  28.  
  29. /**
  30.  * Return the representation of this set as a list of character
  31.  * ranges.  Ranges are listed in ascending Unicode order.  For
  32.  * example, the set [a-zA-M3] is represented as "33AMaz".
  33.  */
  34. const UnicodeString& UnicodeSet::getPairs() const {
  35.     return pairs;
  36. }
  37.  
  38. //----------------------------------------------------------------
  39. // Constructors &c
  40. //----------------------------------------------------------------
  41.  
  42. /**
  43.  * Constructs an empty set.
  44.  */
  45. UnicodeSet::UnicodeSet() : pairs() {}
  46.  
  47. /**
  48.  * Constructs a set from the given pattern, optionally ignoring
  49.  * white space.  See the class description for the syntax of the
  50.  * pattern language.
  51.  * @param pattern a string specifying what characters are in the set
  52.  * @param ignoreSpaces if <code>true</code>, all spaces in the
  53.  * pattern are ignored, except those preceded by '\\'.  Spaces are
  54.  * those characters for which <code>Character.isSpaceChar()</code>
  55.  * is <code>true</code>.
  56.  * @exception <code>IllegalArgumentException</code> if the pattern
  57.  * contains a syntax error.
  58.  */
  59. UnicodeSet::UnicodeSet(const UnicodeString& pattern, bool_t ignoreSpaces,
  60.                        UErrorCode& status) : pairs() {
  61.     applyPattern(pattern, ignoreSpaces, status);
  62. }
  63.  
  64. UnicodeSet::UnicodeSet(const UnicodeString& pattern,
  65.                        UErrorCode& status) : pairs() {
  66.     applyPattern(pattern, status);
  67. }
  68.  
  69. /**
  70.  * Constructs a set from the given Unicode character category.
  71.  * @param category an integer indicating the character category as
  72.  * returned by <code>Character.getType()</code>.
  73.  * @exception <code>IllegalArgumentException</code> if the given
  74.  * category is invalid.
  75.  */
  76. UnicodeSet::UnicodeSet(int8_t category, UErrorCode& status) : pairs() {
  77.     if (U_SUCCESS(status)) {
  78.         if (category < 0 || category >= Unicode::GENERAL_TYPES_COUNT) {
  79.             status = U_ILLEGAL_ARGUMENT_ERROR;
  80.         } else {
  81.             pairs = getCategoryPairs(category);
  82.         }
  83.     }
  84. }
  85.  
  86. /**
  87.  * Constructs a set that is identical to the given UnicodeSet.
  88.  */
  89. UnicodeSet::UnicodeSet(const UnicodeSet& o) : pairs(o.pairs) {}
  90.  
  91. /**
  92.  * Destructs the set.
  93.  */
  94. UnicodeSet::~UnicodeSet() {}
  95.  
  96. /**
  97.  * Assigns this object to be a copy of another.
  98.  */
  99. UnicodeSet& UnicodeSet::operator=(const UnicodeSet& o) {
  100.     pairs = o.pairs;
  101.     return *this;
  102. }
  103.  
  104. /**
  105.  * Compares the specified object with this set for equality.  Returns
  106.  * <tt>true</tt> if the two sets
  107.  * have the same size, and every member of the specified set is
  108.  * contained in this set (or equivalently, every member of this set is
  109.  * contained in the specified set).
  110.  *
  111.  * @param o set to be compared for equality with this set.
  112.  * @return <tt>true</tt> if the specified set is equal to this set.
  113.  */
  114. bool_t UnicodeSet::operator==(const UnicodeSet& o) const {
  115.     return pairs == o.pairs;
  116. }
  117.  
  118. /**
  119.  * Returns the hash code value for this set.
  120.  *
  121.  * @return the hash code value for this set.
  122.  * @see Object#hashCode()
  123.  */
  124. int32_t UnicodeSet::hashCode() const {
  125.     return pairs.hashCode();
  126. }
  127.  
  128. //----------------------------------------------------------------
  129. // Public API
  130. //----------------------------------------------------------------
  131.  
  132. /**
  133.  * Modifies this set to represent the set specified by the given
  134.  * pattern, optionally ignoring white space.  See the class
  135.  * description for the syntax of the pattern language.
  136.  * @param pattern a string specifying what characters are in the set
  137.  * @param ignoreSpaces if <code>true</code>, all spaces in the
  138.  * pattern are ignored.  Spaces are those characters for which
  139.  * <code>Character.isSpaceChar()</code> is <code>true</code>.
  140.  * Characters preceded by '\\' are escaped, losing any special
  141.  * meaning they otherwise have.  Spaces may be included by
  142.  * escaping them.
  143.  * @exception <code>IllegalArgumentException</code> if the pattern
  144.  * contains a syntax error.
  145.  */
  146. void UnicodeSet::applyPattern(const UnicodeString& pattern,
  147.                               bool_t ignoreSpaces,
  148.                               UErrorCode& status) {
  149.     if (U_FAILURE(status)) {
  150.         return;
  151.     }
  152.  
  153.     ParsePosition pos(0);
  154.     UnicodeString* pat = (UnicodeString*) &pattern;
  155.  
  156.     // To ignore spaces, create a new pattern without spaces.  We
  157.     // have to process all '\' escapes.  If '\' is encountered,
  158.     // insert it and the following character (if any -- let parse
  159.     // deal with any syntax errors) in the pattern.  This allows
  160.     // escaped spaces.
  161.     if (ignoreSpaces) {
  162.         pat = new UnicodeString();
  163.         for (int32_t i=0; i<pattern.length(); ++i) {
  164.             UChar c = pattern.charAt(i);
  165.             if (Unicode::isSpaceChar(c)) {
  166.                 continue;
  167.             }
  168.             if (c == '\\' && (i+1) < pattern.length()) {
  169.                 pat->append(c);
  170.                 c = pattern.charAt(++i);
  171.                 // Fall through and append the following char
  172.             }
  173.             pat->append(c);
  174.         }
  175.     }
  176.  
  177.     parse(pairs, *pat, pos, status);
  178.     if (pos.getIndex() != pat->length()) {
  179.         status = U_ILLEGAL_ARGUMENT_ERROR;
  180.     }
  181.     if (pat != &pattern) {
  182.         delete pat;
  183.     }
  184. }
  185.  
  186. /**
  187.  * Returns a string representation of this set.  If the result of
  188.  * calling this function is passed to a UnicodeSet constructor, it
  189.  * will produce another set that is equal to this one.
  190.  */
  191. UnicodeString& UnicodeSet::toPattern(UnicodeString& result) const {
  192.     result.remove().append((UChar)'[');
  193.     
  194.     // iterate through the ranges in the UnicodeSet
  195.     for (int32_t i=0; i<pairs.length(); i+=2) {
  196.         // for a range with the same beginning and ending point,
  197.         // output that character, otherwise, output the start and
  198.         // end points of the range separated by a dash
  199.         result.append(pairs.charAt(i));
  200.         if (pairs.charAt(i) != pairs.charAt(i+1)) {
  201.             result.append((UChar)'-').append(pairs.charAt(i+1));
  202.         }
  203.     }
  204.     
  205.     return result.append((UChar)']');
  206. }
  207.  
  208. /**
  209.  * Returns the number of elements in this set (its cardinality),
  210.  * <em>n</em>, where <code>0 <= </code><em>n</em><code> <= 65536</code>.
  211.  *
  212.  * @return the number of elements in this set (its cardinality).
  213.  */
  214. int32_t UnicodeSet::size() const {
  215.     int32_t n = 0;
  216.     for (int32_t i=0; i<pairs.length(); i+=2) {
  217.         n += pairs.charAt(i+1) - pairs.charAt(i) + 1;
  218.     }
  219.     return n;
  220. }
  221.  
  222. /**
  223.  * Returns <tt>true</tt> if this set contains no elements.
  224.  *
  225.  * @return <tt>true</tt> if this set contains no elements.
  226.  */
  227. bool_t UnicodeSet::isEmpty() const {
  228.     return pairs.length() == 0;
  229. }
  230.  
  231. /**
  232.  * Returns <tt>true</tt> if this set contains the specified range
  233.  * of chars.
  234.  *
  235.  * @return <tt>true</tt> if this set contains the specified range
  236.  * of chars.
  237.  */
  238. bool_t UnicodeSet::contains(UChar first, UChar last) const {
  239.     // Set i to the end of the smallest range such that its end
  240.     // point >= last, or pairs.length() if no such range exists.
  241.     int32_t i = 1;
  242.     while (i<pairs.length() && last>pairs.charAt(i)) i+=2;
  243.     return i<pairs.length() && first>=pairs.charAt(i-1);
  244. }
  245.  
  246. /**
  247.  * Returns <tt>true</tt> if this set contains the specified char.
  248.  *
  249.  * @return <tt>true</tt> if this set contains the specified char.
  250.  */
  251. bool_t UnicodeSet::contains(UChar c) const {
  252.     return contains(c, c);
  253. }
  254.  
  255. /**
  256.  * Adds the specified range to this set if it is not already
  257.  * present.  If this set already contains the specified range,
  258.  * the call leaves this set unchanged.  If <code>last > first</code>
  259.  * then an empty range is added, leaving the set unchanged.
  260.  *
  261.  * @param first first character, inclusive, of range to be added
  262.  * to this set.
  263.  * @param last last character, inclusive, of range to be added
  264.  * to this set.
  265.  */
  266. void UnicodeSet::add(UChar first, UChar last) {
  267.     if (first <= last) {
  268.         addPair(pairs, first, last);
  269.     }
  270. }
  271.  
  272. /**
  273.  * Adds the specified character to this set if it is not already
  274.  * present.  If this set already contains the specified character,
  275.  * the call leaves this set unchanged.
  276.  */
  277. void UnicodeSet::add(UChar c) {
  278.     add(c, c);
  279. }
  280.  
  281. /**
  282.  * Removes the specified range from this set if it is present.
  283.  * The set will not contain the specified range once the call
  284.  * returns.  If <code>last > first</code> then an empty range is
  285.  * removed, leaving the set unchanged.
  286.  * 
  287.  * @param first first character, inclusive, of range to be removed
  288.  * from this set.
  289.  * @param last last character, inclusive, of range to be removed
  290.  * from this set.
  291.  */
  292. void UnicodeSet::remove(UChar first, UChar last) {
  293.     if (first <= last) {
  294.         removePair(pairs, first, last);
  295.     }
  296. }
  297.  
  298. /**
  299.  * Removes the specified character from this set if it is present.
  300.  * The set will not contain the specified range once the call
  301.  * returns.
  302.  */
  303. void UnicodeSet::remove(UChar c) {
  304.     remove(c, c);
  305. }
  306.  
  307. /**
  308.  * Returns <tt>true</tt> if the specified set is a <i>subset</i>
  309.  * of this set.
  310.  *
  311.  * @param c set to be checked for containment in this set.
  312.  * @return <tt>true</tt> if this set contains all of the elements of the
  313.  *            specified set.
  314.  */
  315. bool_t UnicodeSet::containsAll(const UnicodeSet& c) const {
  316.     // The specified set is a subset if all of its pairs are contained
  317.     // in this set.
  318.     int32_t i = 1;
  319.     for (int32_t j=0; j<c.pairs.length(); j+=2) {
  320.         UChar last = c.pairs.charAt(j+1);
  321.         // Set i to the end of the smallest range such that its
  322.         // end point >= last, or pairs.length() if no such range
  323.         // exists.
  324.         while (i<pairs.length() && last>pairs.charAt(i)) i+=2;
  325.         if (i>pairs.length() || c.pairs.charAt(j) < pairs.charAt(i-1)) {
  326.             return FALSE;
  327.         }
  328.     }
  329.     return TRUE;
  330. }
  331.  
  332. /**
  333.  * Adds all of the elements in the specified set to this set if
  334.  * they're not already present.  This operation effectively
  335.  * modifies this set so that its value is the <i>union</i> of the two
  336.  * sets.  The behavior of this operation is unspecified if the specified
  337.  * collection is modified while the operation is in progress.
  338.  *
  339.  * @param c set whose elements are to be added to this set.
  340.  * @see #add(char, char)
  341.  */
  342. void UnicodeSet::addAll(const UnicodeSet& c) {
  343.     doUnion(pairs, c.pairs);
  344. }
  345.  
  346. /**
  347.  * Retains only the elements in this set that are contained in the
  348.  * specified set.  In other words, removes from this set all of
  349.  * its elements that are not contained in the specified set.  This
  350.  * operation effectively modifies this set so that its value is
  351.  * the <i>intersection</i> of the two sets.
  352.  *
  353.  * @param c set that defines which elements this set will retain.
  354.  */
  355. void UnicodeSet::retainAll(const UnicodeSet& c) {
  356.     doIntersection(pairs, c.pairs);
  357. }
  358.  
  359. /**
  360.  * Removes from this set all of its elements that are contained in the
  361.  * specified set.  This operation effectively modifies this
  362.  * set so that its value is the <i>asymmetric set difference</i> of
  363.  * the two sets.
  364.  *
  365.  * @param c set that defines which elements will be removed from
  366.  *          this set.
  367.  */
  368. void UnicodeSet::removeAll(const UnicodeSet& c) {
  369.     doDifference(pairs, c.pairs);
  370. }
  371.  
  372. /**
  373.  * Inverts this set.  This operation modifies this set so that
  374.  * its value is its complement.  This is equivalent to the pseudo code:
  375.  * <code>this = new UnicodeSet("[\u0000-\uFFFF]").removeAll(this)</code>.
  376.  */
  377. void UnicodeSet::complement() {
  378.     doComplement(pairs);
  379. }
  380.  
  381. /**
  382.  * Removes all of the elements from this set.  This set will be
  383.  * empty after this call returns.
  384.  */
  385. void UnicodeSet::clear() {
  386.     pairs.remove();
  387. }
  388.  
  389. //----------------------------------------------------------------
  390. // Implementation: Pattern parsing
  391. //----------------------------------------------------------------
  392.  
  393. /**
  394.  * Parses the given pattern, starting at the given position.  The
  395.  * character at pattern.charAt(pos.getIndex()) must be '[', or the
  396.  * parse fails.  Parsing continues until the corresponding closing
  397.  * ']'.  If a syntax error is encountered between the opening and
  398.  * closing brace, the parse fails.  Upon return from a U_SUCCESSful
  399.  * parse, the ParsePosition is updated to point to the character
  400.  * following the closing ']', and a StringBuffer containing a
  401.  * pairs list for the parsed pattern is returned.  This method calls
  402.  * itself recursively to parse embedded subpatterns.
  403.  *
  404.  * @param pattern the string containing the pattern to be parsed.
  405.  * The portion of the string from pos.getIndex(), which must be a
  406.  * '[', to the corresponding closing ']', is parsed.
  407.  * @param pos upon entry, the position at which to being parsing.
  408.  * The character at pattern.charAt(pos.getIndex()) must be a '['.
  409.  * Upon return from a U_SUCCESSful parse, pos.getIndex() is either
  410.  * the character after the closing ']' of the parsed pattern, or
  411.  * pattern.length() if the closing ']' is the last character of
  412.  * the pattern string.
  413.  * @return a StringBuffer containing a pairs list for the parsed
  414.  * substring of <code>pattern</code>
  415.  * @exception IllegalArgumentException if the parse fails.
  416.  */
  417. UnicodeString& UnicodeSet::parse(UnicodeString& pairsBuf /*result*/,
  418.                                  const UnicodeString& pattern,
  419.                                  ParsePosition& pos,
  420.                                  UErrorCode& status) {
  421.     if (U_FAILURE(status)) {
  422.         return pairsBuf;
  423.     }
  424.  
  425.     bool_t invert = FALSE;
  426.     pairsBuf.remove();
  427.  
  428.     /**
  429.      * Nodes:  0 - idle, waiting for '['
  430.      *        10 - like 11, but immediately after "[" or "[^"
  431.      *        11 - awaiting x, "]", "[...]", or "[:...:]"
  432.      *        21 - after x
  433.      *        23 - after x-
  434.      * 
  435.      * The parsing state machine moves from node 0 through zero or more
  436.      * other nodes back to node 0, in a U_SUCCESSful parse.
  437.      */
  438.     int32_t node = 0;
  439.     UChar first = 0;
  440.     int32_t i;
  441.     /**
  442.      * This loop iterates over the characters in the pattern.  We
  443.      * start at the position specified by pos.  We exit the loop
  444.      * when either a matching closing ']' is seen, or we read all
  445.      * characters of the pattern.
  446.      */
  447.     for (i=pos.getIndex(); i<pattern.length(); ++i) {
  448.         UChar c = pattern.charAt(i);            /**
  449.          * Handle escapes here.  If a character is escaped, then
  450.          * it assumes its literal value.  This is true for all
  451.          * characters, both special characters and characters with
  452.          * no special meaning.  We also interpret '\\uxxxx' Unicode
  453.          * escapes here.
  454.          */
  455.         bool_t isLiteral = FALSE;
  456.         if (c == '\\') {
  457.             ++i;
  458.             if (i < pattern.length()) {
  459.                 c = pattern.charAt(i);
  460.                 isLiteral = TRUE;
  461.                 if (c == 'u') {
  462.                     if ((i+4) >= pattern.length()) {
  463.                         status = U_ILLEGAL_ARGUMENT_ERROR;
  464.                         return pairsBuf;
  465.                     }
  466.                     c = (UChar)0x0000;
  467.                     for (int32_t j=(++i)+4; i<j; ++i) { // [sic]
  468.                         // TO DO: Change this to use Unicode::digit()
  469.                         // when that method exists.
  470.                         int32_t digit = /*Unicode::*/UnicodeSet::digit(pattern.charAt(i), 16);
  471.                         if (digit<0) {
  472.                             status = U_ILLEGAL_ARGUMENT_ERROR;
  473.                             return pairsBuf;
  474.                         }
  475.                         c = (UChar) ((c << 4) | digit);
  476.                     }
  477.                     --i; // Move i back to last parsed character
  478.                 }
  479.             } else {
  480.                 status = U_ILLEGAL_ARGUMENT_ERROR;
  481.                 return pairsBuf;
  482.             }
  483.         }
  484.         /**
  485.          * Within this loop, we handle each of the four
  486.          * conditions: '[', ']', '-', other.  The first three
  487.          * characters must not be escaped.
  488.          */
  489.  
  490.         /**
  491.          * An opening bracket indicates either the first bracket
  492.          * of the entire subpattern we are parsing, in which case
  493.          * we are in node 0 and move into node 10.  We also check
  494.          * for an immediately following '^', indicating the
  495.          * complement of the following pattern.  ('^' is any other
  496.          * position has no special meaning.)  If we are not in
  497.          * node 0, '[' represents a nested subpattern that must be
  498.          * recursively parsed and checked for following operators
  499.          * ('&' or '|').  If two nested subpatterns follow one
  500.          * another with no operator, their union is formed, just
  501.          * as with any other elements that follow one another
  502.          * without intervening operator.  The other thing we
  503.          * handle here is the syntax "[:Xx:]" or "[:X:]" that
  504.          * indicates a Unicode category or supercategory.
  505.          */
  506.         if (!isLiteral && c == '[') {
  507.             bool_t parseOp = FALSE;
  508.             UChar d = charAfter(pattern, i);
  509.             // "[:...:]" represents a character category
  510.             if (d == ':') {
  511.                 if (node == 23) {
  512.                     status = U_ILLEGAL_ARGUMENT_ERROR;
  513.                     return pairsBuf;
  514.                 }
  515.                 if (node == 21) {
  516.                     addPair(pairsBuf, first, first);
  517.                     node = 11;
  518.                 }
  519.                 i += 2;
  520.                 int32_t j = pattern.indexOf(":]", i);
  521.                 if (j < 0) {
  522.                     status = U_ILLEGAL_ARGUMENT_ERROR;
  523.                     return pairsBuf;
  524.                 }
  525.                 UnicodeString categoryName;
  526.                 pattern.extract(i, j-i, categoryName);
  527.                 UnicodeString temp;
  528.                 doUnion(pairsBuf,
  529.                         getCategoryPairs(temp, categoryName, status));
  530.                 if (U_FAILURE(status)) {
  531.                     return pairsBuf;
  532.                 }
  533.                 i = j+1;
  534.                 if (node == 10) {
  535.                     node = 11;
  536.                     parseOp = TRUE;
  537.                 } else if (node == 0) {
  538.                     break;
  539.                 }
  540.             } else {
  541.                 if (node == 0) {
  542.                     node = 10;
  543.                     if (d == '^') {
  544.                         invert = TRUE;
  545.                         ++i;
  546.                     }
  547.                 } else {
  548.                     // Nested '['
  549.                     pos.setIndex(i);
  550.                     UnicodeString subPairs; // Pairs for the nested []
  551.                     doUnion(pairsBuf, parse(subPairs, pattern, pos, status));
  552.                     if (U_FAILURE(status)) {
  553.                         return pairsBuf;
  554.                     }
  555.                     i = pos.getIndex() - 1; // Subtract 1 to point at ']'
  556.                     parseOp = TRUE;
  557.                 }
  558.             }
  559.             /**
  560.              * parseOp is true after "[:...:]" or a nested
  561.              * "[...]".  It is false only after the final closing
  562.              * ']'.  If parseOp is true, we look past the closing
  563.              * ']' to see if we have an operator character.  If
  564.              * so, we parse the subsequent "[...]" recursively,
  565.              * then perform the operation.  We do this in a loop
  566.              * until there are no more operators.  Note that this
  567.              * means the operators have equal precedence and are
  568.              * bound left-to-right.
  569.              */
  570.             if (parseOp) {
  571.                 for (;;) {
  572.                     // Is the next character an operator?
  573.                     UChar op = charAfter(pattern, i);
  574.                     if (op == '-' || op == '&') {
  575.                         pos.setIndex(i+2); // Add 2 to point AFTER op
  576.                         UnicodeString rhs;
  577.                         parse(rhs, pattern, pos, status);
  578.                         if (U_FAILURE(status)) {
  579.                             return pairsBuf;
  580.                         }
  581.                         if (op == '-') {
  582.                             doDifference(pairsBuf, rhs);
  583.                         } else if (op == '&') {
  584.                             doIntersection(pairsBuf, rhs);
  585.                         }
  586.                         i = pos.getIndex() - 1; // - 1 to point at ']'
  587.                     } else {
  588.                         break;
  589.                     }
  590.                 }
  591.             }          
  592.         }
  593.         /**
  594.          * A closing bracket can only be a closing bracket for
  595.          * "[...]", since the closing bracket for "[:...:]" is
  596.          * taken care of when the initial "[:" is seen.  When we
  597.          * see a closing bracket, we then know, if we were in node
  598.          * 21 (after x) or 23 (after x-) that nothing more is
  599.          * coming, and we add the last character(s) we saw to the
  600.          * set.  Note that a trailing '-' assumes its literal
  601.          * meaning, just as a leading '-' after "[" or "[^".
  602.          */
  603.         else if (!isLiteral && c == ']') {
  604.             if (node == 0) {
  605.                 status = U_ILLEGAL_ARGUMENT_ERROR;
  606.                 return pairsBuf;
  607.             }
  608.             if (node == 21 || node == 23) {
  609.                 addPair(pairsBuf, first, first);
  610.                 if (node == 23) {
  611.                     addPair(pairsBuf, '-', '-');
  612.                 }
  613.             }
  614.             node = 0;
  615.             break;
  616.         }
  617.         /**
  618.          * '-' has the following interpretations: 1. Within
  619.          * "[...]", between two letters, it indicates a range.
  620.          * 2. Between two nested bracket patterns, "[[...]-[...]",
  621.          * it indicates asymmetric difference.  3. At the start of
  622.          * a bracket pattern, "[-...]", "[^-...]", it indicates
  623.          * the literal character '-'.  4. At the end of a bracket
  624.          * pattern, "[...-]", it indicates the literal character
  625.          * '-'.
  626.          *
  627.          * We handle cases 1 and 3 here.  Cases 2 and 4 are
  628.          * handled in the ']' parsing code.
  629.          */
  630.         else if (!isLiteral && c == '-') {
  631.             if (node == 10) {
  632.                 addPair(pairsBuf, c, c); // Handle "[-...]", "[^-...]"
  633.             } else if (node == 21) {
  634.                 node = 23;
  635.             } else {
  636.                 status = U_ILLEGAL_ARGUMENT_ERROR;
  637.                 return pairsBuf;
  638.             }
  639.         }
  640.         /**
  641.          * If we fall through to this point, we have a literal
  642.          * character, either one that has been escaped with a
  643.          * backslash, escaped with a backslash u, or that isn't
  644.          * a special '[', ']', or '-'.
  645.          *
  646.          * Literals can either start a range "x-...", end a range,
  647.          * "...-x", or indicate a single character "x".
  648.          */
  649.         else {
  650.             if (node == 10 || node == 11) {
  651.                 first = c;
  652.                 node = 21;
  653.             } else if (node == 21) {
  654.                 addPair(pairsBuf, first, first);
  655.                 first = c;
  656.                 node = 21;
  657.             } else if (node == 23) {
  658.                 if (c < first) {
  659.                     status = U_ILLEGAL_ARGUMENT_ERROR;
  660.                     return pairsBuf;
  661.                 }
  662.                 addPair(pairsBuf, first, c);
  663.                 node = 11;
  664.             } else {
  665.                 status = U_ILLEGAL_ARGUMENT_ERROR;
  666.                 return pairsBuf;
  667.             }
  668.         }
  669.     }
  670.  
  671.     if (node != 0) {
  672.         status = U_ILLEGAL_ARGUMENT_ERROR;
  673.         return pairsBuf;
  674.     }
  675.     /**
  676.      * i indexes the last character we parsed or is
  677.      * pattern.length().  In the latter case, the node will not be
  678.      * zero, since we have run off the end without finding a
  679.      * closing ']'.  Therefore, the above statement will have
  680.      * thrown an exception, and we'll never get here.  If we get
  681.      * here, we know i < pattern.length(), and we set the
  682.      * ParsePosition to the next character to be parsed.
  683.      */
  684.     pos.setIndex(i+1);
  685.     /**
  686.      * If we saw a '^' after the initial '[' of this pattern, then
  687.      * perform the complement.  (Inversion after '[:' is handled
  688.      * elsewhere.)
  689.      */
  690.     if (invert) {
  691.         doComplement(pairsBuf);
  692.     }
  693.  
  694.     return pairsBuf;
  695. }
  696.  
  697. //----------------------------------------------------------------
  698. // Implementation: Efficient in-place union & difference
  699. //----------------------------------------------------------------
  700.  
  701. /**
  702.  * Performs a union operation: adds the range 'c'-'d' to the given
  703.  * pairs list.  The pairs list is modified in place.  The result
  704.  * is normalized (in order and as short as possible).  For
  705.  * example, addPair("am", 'l', 'q') => "aq".  addPair("ampz", 'n',
  706.  * 'o') => "az".
  707.  */
  708. void UnicodeSet::addPair(UnicodeString& pairs, UChar c, UChar d) {
  709.     UChar a = 0;
  710.     UChar b = 0;
  711.     for (int32_t i=0; i<pairs.length(); i+=2) {
  712.         UChar e = pairs.charAt(i);
  713.         UChar f = pairs.charAt(i+1);
  714.         if (e <= (d+1) && c <= (f+1)) {
  715.             // Merge with this range
  716.             f = (UChar) icu_max(d, f);
  717.  
  718.             // Check to see if we need to merge with the
  719.             // subsequent range also.  This happens if we have
  720.             // "abdf" and are merging in "cc".  We only need to
  721.             // check on the right side -- never on the left.
  722.             if ((i+2) < pairs.length() &&
  723.                 pairs.charAt(i+2) == (f+1)) {
  724.                 f = pairs.charAt(i+3);
  725.                 pairs.remove(i+2, 2);
  726.             }
  727.             pairs.setCharAt(i, (UChar) icu_min(c, e));
  728.             pairs.setCharAt(i+1, f);
  729.             return;
  730.         } else if ((b+1) < c && (d+1) < e) {
  731.             // Insert before this range c, then d
  732.             pairs.insert(i, d); // d gets moved to i+1 by next insert
  733.             pairs.insert(i, c);
  734.             return;
  735.         }
  736.         a = e;
  737.         b = f;
  738.     }
  739.     // If nothing else, fall through and append this new range to
  740.     // the end.
  741.     pairs.append(c).append(d);
  742. }
  743.  
  744. /**
  745.  * Performs an asymmetric difference: removes the range 'c'-'d'
  746.  * from the pairs list.  The pairs list is modified in place.  The
  747.  * result is normalized (in order and as short as possible).  For
  748.  * example, removePair("am", 'l', 'q') => "ak".
  749.  * removePair("ampz", 'l', 'q') => "akrz".
  750.  */
  751. void UnicodeSet::removePair(UnicodeString& pairs, UChar c, UChar d) {
  752.     // Iterate over pairs until we find a pair that overlaps
  753.     // with the given range.
  754.     for (int32_t i=0; i<pairs.length(); i+=2) {
  755.         UChar b = pairs.charAt(i+1);
  756.         if (b < c) {
  757.             // Range at i is entirely before the given range,
  758.             // since we have a-b < c-d.  No overlap yet...keep
  759.             // iterating.
  760.             continue;
  761.         }
  762.         UChar a = pairs.charAt(i);
  763.         if (d < a) {
  764.             // Range at i is entirely after the given range; c-d <
  765.             // a-b.  Since ranges are in order, nothing else will
  766.             // overlap.
  767.             break;
  768.         }
  769.         // Once we get here, we know c <= b and d >= a.
  770.         // rangeEdited is set to true if we have modified the
  771.         // range a-b (the range at i) in place.
  772.         bool_t rangeEdited = FALSE;
  773.         if (c > a) {
  774.             // If c is after a and before b, then we have overlap
  775.             // of this sort: a--c==b--d or a--c==d--b, where a-b
  776.             // and c-d are the ranges of interest.  We need to
  777.             // add the range a,c-1.
  778.             pairs.setCharAt(i+1, (UChar)(c-1));
  779.             // i is already a
  780.             rangeEdited = TRUE;
  781.         }
  782.         if (d < b) {
  783.             // If d is after a and before b, we overlap like this:
  784.             // c--a==d--b or a--c==d--b, where a-b is the range at
  785.             // i and c-d is the range being removed.  We need to
  786.             // add the range d+1,b.
  787.             if (rangeEdited) {
  788.                 // Insert {d+1, b}
  789.                 pairs.insert(i+2, b); // b moves to i+3 by next insert:
  790.                 pairs.insert(i+2, (UChar)(d+1));
  791.                 i += 2;
  792.             } else {
  793.                 pairs.setCharAt(i, (UChar)(d+1));
  794.                 // i+1 is already b
  795.                 rangeEdited = TRUE;
  796.             }
  797.         }
  798.         if (!rangeEdited) {
  799.             // If we didn't add any ranges, that means the entire
  800.             // range a-b must be deleted, since we have
  801.             // c--a==b--d.
  802.             pairs.remove(i, 2);
  803.             i -= 2;
  804.         }
  805.     }
  806. }
  807.  
  808. //----------------------------------------------------------------
  809. // Implementation: Fundamental operators
  810. //----------------------------------------------------------------
  811.  
  812. /**
  813.  * Changes the pairs list to represent the complement of the set it
  814.  * currently represents.  The pairs list will be normalized (in
  815.  * order and in shortest possible form) if the original pairs list
  816.  * was normalized.
  817.  */
  818. void UnicodeSet::doComplement(UnicodeString& pairs) {
  819.     if (pairs.length() == 0) {
  820.         pairs.append((UChar)0x0000).append((UChar)0xffff);
  821.         return;
  822.     }
  823.  
  824.     // Change each end to a start and each start to an end of the
  825.     // gaps between the ranges.  That is, 3-7 9-12 becomes x-2 8-8
  826.     // 13-x, where 'x' represents a range that must now be fixed
  827.     // up.
  828.     for (int32_t i=0; i<pairs.length(); i+=2) {
  829.         pairs.setCharAt(i,   (UChar) (pairs.charAt(i)   - 1));
  830.         pairs.setCharAt(i+1, (UChar) (pairs.charAt(i+1) + 1));
  831.     }
  832.  
  833.     // Fix up the initial range, either by adding a start point of
  834.     // U+0000, or by deleting the range altogether, if the
  835.     // original range was U+0000 - x.
  836.     if (pairs.charAt(0) == (UChar)0xFFFF) {
  837.         pairs.remove(0, 1);
  838.     } else {
  839.         pairs.insert(0, (UChar)0x0000);
  840.     }
  841.  
  842.     // Fix up the final range, either by adding an end point of
  843.     // U+FFFF, or by deleting the range altogether, if the
  844.     // original range was x - U+FFFF.
  845.     if (pairs.charAt(pairs.length() - 1) == (UChar)0x0000) {
  846.         pairs.remove(pairs.length() - 1);
  847.     } else {
  848.         pairs.append((UChar)0xFFFF);
  849.     }
  850. }
  851.  
  852. /**
  853.  * Given two pairs lists, changes the first in place to represent
  854.  * the union of the two sets.
  855.  */
  856. void UnicodeSet::doUnion(UnicodeString& c1, const UnicodeString& c2) {
  857.     UnicodeString result;
  858.  
  859.     int32_t i = 0;
  860.     int32_t j = 0;
  861.  
  862.     // consider all the characters in both strings
  863.     while (i < c1.length() && j < c2.length()) {
  864.         UChar ub;
  865.         
  866.         // the first character in the result is the lower of the
  867.         // starting characters of the two strings, and "ub" gets
  868.         // set to the upper bound of that range
  869.         if (c1.charAt(i) < c2.charAt(j)) {
  870.             result.append(c1.charAt(i));
  871.             ub = c1.charAt(++i);
  872.         }
  873.         else {
  874.             result.append(c2.charAt(j));
  875.             ub = c2.charAt(++j);
  876.         }
  877.         
  878.         // for as long as one of our two pointers is pointing to a range's
  879.         // end point, or i is pointing to a character that is less than
  880.         // "ub" plus one (the "plus one" stitches touching ranges together)...
  881.         while (i % 2 == 1 || j % 2 == 1 || (i < c1.length() && c1.charAt(i)
  882.                         <= ub + 1)) {
  883.             // advance i to the first character that is greater than
  884.             // "ub" plus one
  885.             while (i < c1.length() && c1.charAt(i) <= ub + 1)
  886.                 ++i;
  887.                 
  888.             // if i points to the endpoint of a range, update "ub"
  889.             // to that character, or if i points to the start of
  890.             // a range and the endpoint of the preceding range is
  891.             // greater than "ub", update "up" to _that_ character
  892.             if (i % 2 == 1)
  893.                 ub = c1.charAt(i);
  894.             else if (i > 0 && c1.charAt(i - 1) > ub)
  895.                 ub = c1.charAt(i - 1);
  896.  
  897.             // now advance j to the first character that is greater
  898.             // that "ub" plus one
  899.             while (j < c2.length() && c2.charAt(j) <= ub + 1)
  900.                 ++j;
  901.                 
  902.             // if j points to the endpoint of a range, update "ub"
  903.             // to that character, or if j points to the start of
  904.             // a range and the endpoint of the preceding range is
  905.             // greater than "ub", update "up" to _that_ character
  906.             if (j % 2 == 1)
  907.                 ub = c2.charAt(j);
  908.             else if (j > 0 && c2.charAt(j - 1) > ub)
  909.                 ub = c2.charAt(j - 1);
  910.         }
  911.         // when we finally fall out of this loop, we will have stitched
  912.         // together a series of ranges that overlap or touch, i and j
  913.         // will both point to starting points of ranges, and "ub" will
  914.         // be the endpoint of the range we're working on.  Write "ub"
  915.         // to the result
  916.         result.append(ub);
  917.         
  918.     // loop back around to create the next range in the result
  919.     }
  920.     
  921.     // we fall out to here when we've exhausted all the characters in
  922.     // one of the operands.  We can append all of the remaining characters
  923.     // in the other operand without doing any extra work.
  924.     if (i < c1.length())
  925.         result.append(c1, i, LONG_MAX);
  926.     if (j < c2.length())
  927.         result.append(c2, j, LONG_MAX);
  928.  
  929.     c1 = result;
  930. }
  931.  
  932. /**
  933.  * Given two pairs lists, changes the first in place to represent
  934.  * the asymmetric difference of the two sets.
  935.  */
  936. void UnicodeSet::doDifference(UnicodeString& pairs, const UnicodeString& pairs2) {
  937.     UnicodeString p2(pairs2);
  938.     doComplement(p2);
  939.     doIntersection(pairs, p2);
  940. }
  941.  
  942. /**
  943.  * Given two pairs lists, changes the first in place to represent
  944.  * the intersection of the two sets.
  945.  */
  946. void UnicodeSet::doIntersection(UnicodeString& c1, const UnicodeString& c2) {
  947.     UnicodeString result;
  948.  
  949.     int32_t i = 0;
  950.     int32_t j = 0;
  951.     int32_t oldI;
  952.     int32_t oldJ;
  953.  
  954.     // iterate until we've exhausted one of the operands
  955.     while (i < c1.length() && j < c2.length()) {
  956.         
  957.         // advance j until it points to a character that is larger than
  958.         // the one i points to.  If this is the beginning of a one-
  959.         // character range, advance j to point to the end
  960.         if (i < c1.length() && i % 2 == 0) {
  961.             while (j < c2.length() && c2.charAt(j) < c1.charAt(i))
  962.                 ++j;
  963.             if (j < c2.length() && j % 2 == 0 && c2.charAt(j) == c1.charAt(i))
  964.                 ++j;
  965.         }
  966.  
  967.         // if j points to the endpoint of a range, save the current
  968.         // value of i, then advance i until it reaches a character
  969.         // which is larger than the character pointed at
  970.         // by j.  All of the characters we've advanced over (except
  971.         // the one currently pointed to by i) are added to the result
  972.         oldI = i;
  973.         while (j % 2 == 1 && i < c1.length() && c1.charAt(i) <= c2.charAt(j))
  974.             ++i;
  975.         result.append(c1, oldI, i-oldI);
  976.  
  977.         // if i points to the endpoint of a range, save the current
  978.         // value of j, then advance j until it reaches a character
  979.         // which is larger than the character pointed at
  980.         // by i.  All of the characters we've advanced over (except
  981.         // the one currently pointed to by i) are added to the result
  982.         oldJ = j;
  983.         while (i % 2 == 1 && j < c2.length() && c2.charAt(j) <= c1.charAt(i))
  984.             ++j;
  985.         result.append(c2, oldJ, j-oldJ);
  986.  
  987.         // advance i until it points to a character larger than j
  988.         // If it points at the beginning of a one-character range,
  989.         // advance it to the end of that range
  990.         if (j < c2.length() && j % 2 == 0) {
  991.             while (i < c1.length() && c1.charAt(i) < c2.charAt(j))
  992.                 ++i;
  993.             if (i < c1.length() && i % 2 == 0 && c2.charAt(j) == c1.charAt(i))
  994.                 ++i;
  995.         }
  996.     }
  997.  
  998.     c1 = result;
  999. }
  1000.  
  1001. //----------------------------------------------------------------
  1002. // Implementation: Generation of pairs for Unicode categories
  1003. //----------------------------------------------------------------
  1004.  
  1005. /**
  1006.  * Returns a pairs string for the given category, given its name.
  1007.  * The category name must be either a two-letter name, such as
  1008.  * "Lu", or a one letter name, such as "L".  One-letter names
  1009.  * indicate the logical union of all two-letter names that start
  1010.  * with that letter.  Case is significant.  If the name starts
  1011.  * with the character '^' then the complement of the given
  1012.  * character set is returned.
  1013.  *
  1014.  * Although individual categories such as "Lu" are cached, we do
  1015.  * not currently cache single-letter categories such as "L" or
  1016.  * complements such as "^Lu" or "^L".  It would be easy to cache
  1017.  * these as well in a hashtable should the need arise.
  1018.  */
  1019. UnicodeString& UnicodeSet::getCategoryPairs(UnicodeString& result,
  1020.                                             const UnicodeString& catName,
  1021.                                             UErrorCode& status) {
  1022.     if (U_FAILURE(status)) {
  1023.         return result;
  1024.     }
  1025.  
  1026.     // The temporary cat is only really needed if invert is true.
  1027.     // TO DO: Allocate cat on the heap only if needed.
  1028.     UnicodeString cat(catName);
  1029.     bool_t invert = (catName.length() > 1 &&
  1030.                      catName.charAt(0) == '^');
  1031.     if (invert) {
  1032.         cat.remove(0, 1);
  1033.     }
  1034.  
  1035.     result.remove();
  1036.     
  1037.     // if we have two characters, search the category map for that
  1038.     // code and either construct and return a UnicodeSet from the
  1039.     // data in the category map or throw an exception
  1040.     if (cat.length() == 2) {
  1041.         int32_t i = CATEGORY_NAMES.indexOf(cat);
  1042.         if (i>=0 && i%2==0) {
  1043.             i /= 2;
  1044.             result = getCategoryPairs((int8_t)i);
  1045.             if (!invert) {
  1046.                 return result;
  1047.             }
  1048.         }
  1049.     } else if (cat.length() == 1) {
  1050.         // if we have one character, search the category map for
  1051.         // codes beginning with that letter, and union together
  1052.         // all of the matching sets that we find (or throw an
  1053.         // exception if there are no matches)
  1054.         for (int32_t i=0; i<Unicode::GENERAL_TYPES_COUNT; ++i) {
  1055.             if (CATEGORY_NAMES.charAt(2*i) == cat.charAt(0)) {
  1056.                 const UnicodeString& pairs = getCategoryPairs((int8_t)i);
  1057.                 if (result.length() == 0) {
  1058.                     result = pairs;
  1059.                 } else {
  1060.                     doUnion(result, pairs);
  1061.                 }
  1062.             }
  1063.         }
  1064.     }
  1065.  
  1066.     if (result.length() == 0) {
  1067.         status = U_ILLEGAL_ARGUMENT_ERROR;
  1068.         return result;
  1069.     }
  1070.  
  1071.     if (invert) {
  1072.         doComplement(result);
  1073.     }
  1074.     return result;
  1075. }
  1076.  
  1077. /**
  1078.  * Returns a pairs string for the given category.  This string is
  1079.  * cached and returned again if this method is called again with
  1080.  * the same parameter.
  1081.  */
  1082. const UnicodeString& UnicodeSet::getCategoryPairs(int8_t cat) {
  1083.     // In order to tell what cache entries are empty, we assume
  1084.     // every category specifies at least one character.  Thus
  1085.     // pair lists in the cache that are empty are uninitialized.
  1086.     if (CATEGORY_PAIRS_CACHE[cat].length() == 0) {
  1087.         // Walk through all Unicode characters, noting the start
  1088.         // and end of each range for which Character.getType(c)
  1089.         // returns the given category integer.  Since we are
  1090.         // iterating in order, we can simply append the resulting
  1091.         // ranges to the pairs string.
  1092.         UnicodeString& pairs = CATEGORY_PAIRS_CACHE[cat];
  1093.         int32_t first = -1;
  1094.         int32_t last = -2;
  1095.         for (int32_t i=0; i<=0xFFFF; ++i) {
  1096.             if (Unicode::getType((UChar)i) == cat) {
  1097.                 if ((last+1) == i) {
  1098.                     last = i;
  1099.                 } else {
  1100.                     if (first >= 0) {
  1101.                         pairs.append((UChar)first).append((UChar)last);
  1102.                     }
  1103.                     first = last = i;
  1104.                 }
  1105.             }
  1106.         }
  1107.         if (first >= 0) {
  1108.             pairs.append((UChar)first).append((UChar)last);
  1109.         }
  1110.     }
  1111.     return CATEGORY_PAIRS_CACHE[cat];
  1112. }
  1113.  
  1114. //----------------------------------------------------------------
  1115. // Implementation: Utility methods
  1116. //----------------------------------------------------------------
  1117.  
  1118. /**
  1119.  * Returns the character after the given position, or '\uFFFF' if
  1120.  * there is none.
  1121.  */
  1122. UChar UnicodeSet::charAfter(const UnicodeString& str, int32_t i) {
  1123.     return ((++i) < str.length()) ? str.charAt(i) : (UChar)0xFFFF;
  1124. }
  1125.  
  1126. /**
  1127.  * TEMPORARY WORKAROUND UNTIL Unicode::digit() exists.
  1128.  * Return the digit value of the given UChar, or -1.  The radix
  1129.  * value is ignored for now and hardcoded as 16.
  1130.  */
  1131. int8_t UnicodeSet::digit(UChar c, int8_t radix) {
  1132.     int32_t d = Unicode::digitValue(c);
  1133.     if (d < 0) {
  1134.         if (c >= (UChar)'a' && c <= (UChar)'f') {
  1135.             d = c - (UChar)('a' - 10);
  1136.         } else if (c >= (UChar)'A' && c <= (UChar)'F') {
  1137.             d = c - (UChar)('A' - 10);
  1138.         }
  1139.     }
  1140.     return (int8_t)d;
  1141. }
  1142.