/*

 * Copyright (c) 2003, 2013, 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 Taligent, Inc. 1996, 1997 - All Rights Reserved

 * (C) Copyright IBM Corp. 1996 - 2002 - All Rights Reserved

 *

 * The original version of this source code and documentation

 * is copyrighted and owned by Taligent, Inc., a wholly-owned

 * subsidiary of IBM. These materials are provided under terms

 * of a License Agreement between Taligent and Sun. This technology

 * is protected by multiple US and International patents.

 *

 * This notice and attribution to Taligent may not be removed.

 * Taligent is a registered trademark of Taligent, Inc.

 */

package build.tools.generatebreakiteratordata;

import java.util.Arrays;

import java.util.Hashtable;

/**

 * An object representing a set of characters.  (This is a "set" in the

 * mathematical sense: an unduplicated list of characters on which set

 * operations such as union and intersection can be performed.)  The

 * set information is stored in compressed, optimized form: The object

 * contains an integer array with an even number of characters.  Each

 * pair of characters represents a range of characters contained in the set

 * (a pair of the same character represents a single character).  The

 * characters are sorted in increasing order.

 */

class CharSet {

    /**

     * The structure containing the set information.  The characters

     * in this array are organized into pairs, each pair representing

     * a range of characters contained in the set

     */

    private int[] chars;

    //==========================================================================

    // parseString() and associated routines

    //==========================================================================

    /**

     * A cache which is used to speed up parseString() whenever it is

     * used to parse a description that has been parsed before

     */

    private static Hashtable<String, CharSet> expressionCache = null;

    /**

     * Builds a CharSet based on a textual description.  For the syntax of

     * the description, see the documentation of RuleBasedBreakIterator.

     * @see java.text.RuleBasedBreakIterator

     */

    public static CharSet parseString(String s) {

        CharSet result = null;

        // if "s" is in the expression cache, pull the result out

        // of the expresison cache

        if (expressionCache != null) {

            result = expressionCache.get(s);

        }

        // otherwise, use doParseString() to actually parse the string,

        // and then add a corresponding entry to the expression cache

        if (result == null) {

            result = doParseString(s);

            if (expressionCache == null) {

                expressionCache = new Hashtable<>();

            }

            expressionCache.put(s, result);

        }

        result = (CharSet)(result.clone());

        return result;

    }

    /**

     * This function is used by parseString() to actually parse the string

     */

    private static CharSet doParseString(String s) {

        CharSet result = new CharSet();

        int p = 0;

        boolean haveDash = false;

        boolean haveTilde = false;

        boolean wIsReal = false;

        int w = 0x0000;

        // for each character in the description...

        while (p < s.length()) {

            int c = s.codePointAt(p);

            // if it's an opening bracket...

            if (c == '[') {

                // flush the single-character cache

                if (wIsReal) {

                    result.internalUnion(new CharSet(w));

                }

                // locate the matching closing bracket

                int bracketLevel = 1;

                int q = p + 1;

                while (bracketLevel != 0) {

                    // if no matching bracket by end of string then...

                    if (q >= s.length()) {

                        throw new IllegalArgumentException("Parse error at position " + p + " in " + s);

                    }

                    int ch = s.codePointAt(q);

                    switch (ch) {

                    case '\\': // need to step over next character

                        ch = s.codePointAt(++q);

                        break;

                    case '[':

                        ++bracketLevel;

                        break;

                    case ']':

                        --bracketLevel;

                        break;

                    }

                    q += Character.charCount(ch);

                }

                --q;

                // call parseString() recursively to parse the text inside

                // the brackets, then either add or subtract the result from

                // our running result depending on whether or not the []

                // expresison was preceded by a ^

                if (!haveTilde) {

                    result.internalUnion(CharSet.parseString(s.substring(p + 1, q)));

                }

                else {

                    result.internalDifference(CharSet.parseString(s.substring(p + 1, q)));

                }

                haveTilde = false;

                haveDash = false;

                wIsReal = false;

                p = q + 1;

            }

            // if the character is a colon...

            else if (c == ':') {

                // flush the single-character cache

                if (wIsReal) {

                    result.internalUnion(new CharSet(w));

                }

                // locate the matching colon (and throw an error if there

                // isn't one)

                int q = s.indexOf(':', p + 1);

                if (q == -1) {

                    throw new IllegalArgumentException("Parse error at position " + p + " in " + s);

                }

                // use charSetForCategory() to parse the text in the colons,

                // and either add or substract the result from our running

                // result depending on whether the :: expression was

                // preceded by a ^

                if (!haveTilde) {

                    result.internalUnion(charSetForCategory(s.substring(p + 1, q)));

                }

                else {

                    result.internalDifference(charSetForCategory(s.substring(p + 1, q)));

                }

                // reset everything and advance to the next character

                haveTilde = false;

                haveDash = false;

                wIsReal = false;

                p = q + 1;

            }

            // if the character is a dash, set an appropriate flag

            else if (c == '-') {

                if (wIsReal) {

                    haveDash = true;

                }

                ++p;

            }

            // if the character is a caret, flush the single-character

            // cache and set an appropriate flag.  If the set is empty

            // (i.e., if the expression begins with ^), invert the set

            // (i.e., set it to include everything).  The idea here is

            // that a set that includes nothing but ^ expressions

            // means "everything but these things".

            else if (c == '^') {

                if (wIsReal) {

                    result.internalUnion(new CharSet(w));

                    wIsReal = false;

                }

                haveTilde = true;

                ++p;

                if (result.empty()) {

                    result.internalComplement();

                }

            }

            // throw an exception on an illegal character

            else if (c >= ' ' && c < '\u007f' && !Character.isLetter((char)c)

                     && !Character.isDigit((char)c) && c != '\\') {

                throw new IllegalArgumentException("Parse error at position " + p + " in " + s);

            }

            // otherwise, we end up here...

            else {

                // on a backslash, advance to the next character

                if (c == '\\') {

                    ++p;

                }

                // if the preceding character was a dash, this character

                // defines the end of a range.  Add or subtract that range

                // from the running result depending on whether or not it

                // was preceded by a ^

                if (haveDash) {

                    if (s.codePointAt(p) < w) {

                        throw new IllegalArgumentException("U+" +

                            Integer.toHexString(s.codePointAt(p))

                            + " is less than U+" + Integer.toHexString(w) + ".  Dash expressions "

                            + "can't have their endpoints in reverse order.");

                    }

                    int ch = s.codePointAt(p);

                    if (!haveTilde) {

                        result.internalUnion(new CharSet(w, ch));

                    }

                    else {

                        result.internalDifference(new CharSet(w, ch));

                    }

                    p += Character.charCount(ch);

                    haveDash = false;

                    haveTilde = false;

                    wIsReal = false;

                }

                // if the preceding character was a caret, remove this character

                // from the running result

                else if (haveTilde) {

                    w = s.codePointAt(p);

                    result.internalDifference(new CharSet(w));

                    p += Character.charCount(w);

                    haveTilde = false;

                    wIsReal = false;

                }

                // otherwise, flush the single-character cache and then

                // put this character into the cache

                else if (wIsReal) {

                    result.internalUnion(new CharSet(w));

                    w = s.codePointAt(p);

                    p += Character.charCount(w);

                    wIsReal = true;

                } else {

                    w = s.codePointAt(p);

                    p += Character.charCount(w);

                    wIsReal = true;

                }

            }

        }

        // finally, flush the single-character cache one last time

        if (wIsReal) {

            result.internalUnion(new CharSet(w));

        }

        return result;

    }

    /**

     * Creates a CharSet containing all the characters in a particular

     * Unicode category.  The text is either a two-character code from

     * the Unicode database or a single character that begins one or more

     * two-character codes.

     */

    private static CharSet charSetForCategory(String category) {

        // throw an exception if we have anything other than one or two

        // characters inside the colons

        if (category.length() == 0 || category.length() >= 3) {

            throw new IllegalArgumentException("Invalid character category: " + category);

        }

        // if we have two characters, search the category map for that code

        // and either construct and return a CharSet from the data in the

        // category map or throw an exception

        if (category.length() == 2) {

            for (int i = 0; i < CharacterCategory.categoryNames.length; i++) {

                if (CharacterCategory.categoryNames[i].equals(category)) {

                    return new CharSet(CharacterCategory.getCategoryMap(i));

                }

            }

            throw new IllegalArgumentException("Invalid character category: " + category);

        }

        // if we have one character, search the category map for codes beginning

        // with that letter, and union together all of the matching sets that

        // we find (or throw an exception if there are no matches)

        else if (category.length() == 1) {

            CharSet result = new CharSet();

            for (int i = 0; i < CharacterCategory.categoryNames.length; i++) {

                if (CharacterCategory.categoryNames[i].startsWith(category)) {

                    result = result.union(new CharSet(CharacterCategory.getCategoryMap(i)));

                }

            }

            if (result.empty()) {

                throw new IllegalArgumentException("Invalid character category: " + category);

            }

            else {

                return result;

            }

        }

        return new CharSet(); // should never get here, but to make the compiler happy...

    }

    /**

     * Returns a copy of CharSet's expression cache and sets CharSet's

     * expression cache to empty.

     */

    public static Hashtable<String, CharSet> releaseExpressionCache() {

        Hashtable<String, CharSet> result = expressionCache;

        expressionCache = null;

        return result;

    }

    //==========================================================================

    // CharSet manipulation

    //==========================================================================

    /**

     * Creates an empty CharSet.

     */

    public CharSet() {

        chars = new int[0];

    }

    /**

     * Creates a CharSet containing a single character.

     * @param c The character to put into the CharSet

     */

    public CharSet(int c) {

        chars = new int[2];

        chars[0] = c;

        chars[1] = c;

    }

    /**

     * Creates a CharSet containing a range of characters.

     * @param lo The lowest-numbered character to include in the range

     * @param hi The highest-numbered character to include in the range

     */

    public CharSet(int lo, int hi) {

        chars = new int[2];

        if (lo <= hi) {

            chars[0] = lo;

            chars[1] = hi;

        }

        else {

            chars[0] = hi;

            chars[1] = lo;

        }

    }

    /**

     * Creates a CharSet, initializing it from the internal storage

     * of another CharSet (this function performs no error checking

     * on "chars", so if it's malformed, undefined behavior will result)

     */

    private CharSet(int[] chars) {

        this.chars = chars;

    }

    /**

     * Returns a CharSet representing the union of two CharSets.

     */

    public CharSet union(CharSet that) {

        return new CharSet(doUnion(that.chars));

    }

    /**

     * Adds the characters in "that" to this CharSet

     */

    private void internalUnion(CharSet that) {

        chars = doUnion(that.chars);

    }

    /**

     * The actual implementation of the union functions

     */

    private int[] doUnion(int[] c2) {

        int[] result = new int[chars.length+c2.length];

        int i = 0;

        int j = 0;

        int index = 0;

        // consider all the characters in both strings

        while (i < chars.length && j < c2.length) {

            int ub;

            // the first character in the result is the lower of the

            // starting characters of the two strings, and "ub" gets

            // set to the upper bound of that range

            if (chars[i] < c2[j]) {

                result[index++] = chars[i];

                ub = chars[++i];

            }

            else {

                result[index++] = c2[j];

                ub = c2[++j];

            }

            // for as long as one of our two pointers is pointing to a range's

            // end point, or i is pointing to a character that is less than

            // "ub" plus one (the "plus one" stitches touching ranges together)...

            while (i % 2 == 1 ||

                   j % 2 == 1 ||

                   (i < chars.length && chars[i] <= ub + 1)) {

                // advance i to the first character that is greater than

                // "ub" plus one

                while (i < chars.length && chars[i] <= ub + 1) {

                    ++i;

                }

                // if i points to the endpoint of a range, update "ub"

                // to that character, or if i points to the start of

                // a range and the endpoint of the preceding range is

                // greater than "ub", update "up" to _that_ character

                if (i % 2 == 1) {

                    ub = chars[i];

                }

                else if (i > 0 && chars[i - 1] > ub) {

                    ub = chars[i - 1];

                }

                // now advance j to the first character that is greater

                // that "ub" plus one

                while (j < c2.length && c2[j] <= ub + 1) {

                    ++j;

                }

                // if j points to the endpoint of a range, update "ub"

                // to that character, or if j points to the start of

                // a range and the endpoint of the preceding range is

                // greater than "ub", update "up" to _that_ character

                if (j % 2 == 1) {

                    ub = c2[j];

                }

                else if (j > 0 && c2[j - 1] > ub) {

                    ub = c2[j - 1];

                }

            }

            // when we finally fall out of this loop, we will have stitched

            // together a series of ranges that overlap or touch, i and j

            // will both point to starting points of ranges, and "ub" will

            // be the endpoint of the range we're working on.  Write "ub"

            // to the result

            result[index++] = ub;

        // loop back around to create the next range in the result

        }

        // we fall out to here when we've exhausted all the characters in

        // one of the operands.  We can append all of the remaining characters

        // in the other operand without doing any extra work.

        if (i < chars.length) {

            for (int k = i; k < chars.length; k++) {

                result[index++] = chars[k];

            }

        }

        if (j < c2.length) {

            for (int k = j; k < c2.length; k++) {

                result[index++] = c2[k];

            }

        }

        if (result.length > index) {

            int[] tmpbuf = new int[index];

            System.arraycopy(result, 0, tmpbuf, 0, index);

            return tmpbuf;

        }

        return result;

    }

    /**

     * Returns the intersection of two CharSets.

     */

    public CharSet intersection(CharSet that) {

        return new CharSet(doIntersection(that.chars));

    }

    /**

     * Removes from this CharSet any characters that aren't also in "that"

     */

    private void internalIntersection(CharSet that) {

        chars = doIntersection(that.chars);

    }

    /**

     * The internal implementation of the two intersection functions

     */

    private int[] doIntersection(int[] c2) {

        int[] result = new int[chars.length+c2.length];

        int i = 0;

        int j = 0;