/*

 * Copyright (c) 2015, 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.

 */

/*

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

 * Copyright (C) 2009-2014, International Business Machines Corporation and

 * others. All Rights Reserved.

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

 */

package sun.text.normalizer;

import java.io.IOException;

import java.nio.ByteBuffer;

import java.nio.ByteOrder;

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

 * This is the interface and common implementation of a Unicode Trie2.

 * It is a kind of compressed table that maps from Unicode code points (0..0x10ffff)

 * to 16- or 32-bit integer values.  It works best when there are ranges of

 * characters with the same value, which is generally the case with Unicode

 * character properties.

 *

 * This is the second common version of a Unicode trie (hence the name Trie2).

 *

 */

abstract class Trie2 implements Iterable<Trie2.Range> {

    /**

     * Create a Trie2 from its serialized form.  Inverse of utrie2_serialize().

     *

     * Reads from the current position and leaves the buffer after the end of the trie.

     *

     * The serialized format is identical between ICU4C and ICU4J, so this function

     * will work with serialized Trie2s from either.

     *

     * The actual type of the returned Trie2 will be either Trie2_16 or Trie2_32, depending

     * on the width of the data.

     *

     * To obtain the width of the Trie2, check the actual class type of the returned Trie2.

     * Or use the createFromSerialized() function of Trie2_16 or Trie2_32, which will

     * return only Tries of their specific type/size.

     *

     * The serialized Trie2 on the stream may be in either little or big endian byte order.

     * This allows using serialized Tries from ICU4C without needing to consider the

     * byte order of the system that created them.

     *

     * @param bytes a byte buffer to the serialized form of a UTrie2.

     * @return An unserialized Trie2, ready for use.

     * @throws IllegalArgumentException if the stream does not contain a serialized Trie2.

     * @throws IOException if a read error occurs in the buffer.

     *

     */

    public static Trie2 createFromSerialized(ByteBuffer bytes) throws IOException {

         //    From ICU4C utrie2_impl.h

         //    * Trie2 data structure in serialized form:

         //     *

         //     * UTrie2Header header;

         //     * uint16_t index[header.index2Length];

         //     * uint16_t data[header.shiftedDataLength<<2];  -- or uint32_t data[...]

         //     * @internal

         //     */

         //    typedef struct UTrie2Header {

         //        /** "Tri2" in big-endian US-ASCII (0x54726932) */

         //        uint32_t signature;

         //       /**

         //         * options bit field:

         //         * 15.. 4   reserved (0)

         //         *  3.. 0   UTrie2ValueBits valueBits

         //         */

         //        uint16_t options;

         //

         //        /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */

         //        uint16_t indexLength;

         //

         //        /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */

         //        uint16_t shiftedDataLength;

         //

         //        /** Null index and data blocks, not shifted. */

         //        uint16_t index2NullOffset, dataNullOffset;

         //

         //        /**

         //         * First code point of the single-value range ending with U+10ffff,

         //         * rounded up and then shifted right by UTRIE2_SHIFT_1.

         //         */

         //        uint16_t shiftedHighStart;

         //    } UTrie2Header;

        ByteOrder outerByteOrder = bytes.order();

        try {

            UTrie2Header header = new UTrie2Header();

            /* check the signature */

            header.signature = bytes.getInt();

            switch (header.signature) {

            case 0x54726932:

                // The buffer is already set to the trie data byte order.

                break;

            case 0x32697254:

                // Temporarily reverse the byte order.

                boolean isBigEndian = outerByteOrder == ByteOrder.BIG_ENDIAN;

                bytes.order(isBigEndian ? ByteOrder.LITTLE_ENDIAN : ByteOrder.BIG_ENDIAN);

                header.signature = 0x54726932;

                break;

            default:

                throw new IllegalArgumentException("Buffer does not contain a serialized UTrie2");

            }

            header.options = bytes.getChar();

            header.indexLength = bytes.getChar();

            header.shiftedDataLength = bytes.getChar();

            header.index2NullOffset = bytes.getChar();

            header.dataNullOffset   = bytes.getChar();

            header.shiftedHighStart = bytes.getChar();

            if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) != 0) {

                throw new IllegalArgumentException("UTrie2 serialized format error.");

            }

            Trie2 This;

            This = new Trie2_16();

            This.header = header;

            /* get the length values and offsets */

            This.indexLength      = header.indexLength;

            This.dataLength       = header.shiftedDataLength << UTRIE2_INDEX_SHIFT;

            This.index2NullOffset = header.index2NullOffset;

            This.dataNullOffset   = header.dataNullOffset;

            This.highStart        = header.shiftedHighStart << UTRIE2_SHIFT_1;

            This.highValueIndex   = This.dataLength - UTRIE2_DATA_GRANULARITY;

            This.highValueIndex += This.indexLength;

            // Allocate the Trie2 index array. If the data width is 16 bits, the array also

            // includes the space for the data.

            int indexArraySize = This.indexLength;

            indexArraySize += This.dataLength;

            This.index = new char[indexArraySize];

            /* Read in the index */

            int i;

            for (i=0; i<This.indexLength; i++) {

                This.index[i] = bytes.getChar();

            }

            /* Read in the data. 16 bit data goes in the same array as the index.

             * 32 bit data goes in its own separate data array.

             */

            This.data16 = This.indexLength;

            for (i=0; i<This.dataLength; i++) {

                This.index[This.data16 + i] = bytes.getChar();

            }

            This.data32 = null;

            This.initialValue = This.index[This.dataNullOffset];

            This.errorValue   = This.index[This.data16+UTRIE2_BAD_UTF8_DATA_OFFSET];

            return This;

        } finally {

            bytes.order(outerByteOrder);

        }

    }

    /**

     * Get the value for a code point as stored in the Trie2.

     *

     * @param codePoint the code point

     * @return the value

     */

    /**

     * Get the trie value for a UTF-16 code unit.

     *

     * A Trie2 stores two distinct values for input in the lead surrogate

     * range, one for lead surrogates, which is the value that will be

     * returned by this function, and a second value that is returned

     * by Trie2.get().

     *

     * For code units outside of the lead surrogate range, this function

     * returns the same result as Trie2.get().

     *

     * This function, together with the alternate value for lead surrogates,

     * makes possible very efficient processing of UTF-16 strings without

     * first converting surrogate pairs to their corresponding 32 bit code point

     * values.

     *

     * At build-time, enumerate the contents of the Trie2 to see if there

     * is non-trivial (non-initialValue) data for any of the supplementary

     * code points associated with a lead surrogate.

     * If so, then set a special (application-specific) value for the

     * lead surrogate code _unit_, with Trie2Writable.setForLeadSurrogateCodeUnit().

     *

     * At runtime, use Trie2.getFromU16SingleLead(). If there is non-trivial

     * data and the code unit is a lead surrogate, then check if a trail surrogate

     * follows. If so, assemble the supplementary code point and look up its value

     * with Trie2.get(); otherwise reset the lead

     * surrogate's value or do a code point lookup for it.

     *

     * If there is only trivial data for lead and trail surrogates, then processing

     * can often skip them. For example, in normalization or case mapping

     * all characters that do not have any mappings are simply copied as is.

     *

     * @param c the code point or lead surrogate value.

     * @return the value

     */

    /**

     * When iterating over the contents of a Trie2, Elements of this type are produced.

     * The iterator will return one item for each contiguous range of codepoints  having the same value.

     *

     * When iterating, the same Trie2EnumRange object will be reused and returned for each range.

     * If you need to retain complete iteration results, clone each returned Trie2EnumRange,

     * or save the range in some other way, before advancing to the next iteration step.

     */

    public static class Range {

        public int     startCodePoint;

        public int     endCodePoint;     // Inclusive.

        public int     value;

        public boolean leadSurrogate;

        public boolean equals(Object other) {

            if (other == null || !(other.getClass().equals(getClass()))) {

                return false;

            }

            Range tother = (Range)other;

            return this.startCodePoint == tother.startCodePoint &&

                   this.endCodePoint   == tother.endCodePoint   &&

                   this.value          == tother.value          &&

                   this.leadSurrogate  == tother.leadSurrogate;

        }

        public int hashCode() {

            int h = initHash();

            h = hashUChar32(h, startCodePoint);

            h = hashUChar32(h, endCodePoint);

            h = hashInt(h, value);

            h = hashByte(h, leadSurrogate? 1: 0);

            return h;

        }

    }

    /**

     *  Create an iterator over the value ranges in this Trie2.

     *  Values from the Trie2 are not remapped or filtered, but are returned as they

     *  are stored in the Trie2.

     *

     * @return an Iterator

     */

    public Iterator<Range> iterator() {

        return iterator(defaultValueMapper);

    }

    private static ValueMapper defaultValueMapper = new ValueMapper() {

        public int map(int in) {

            return in;

        }

    };

    /**

     * Create an iterator over the value ranges from this Trie2.

     * Values from the Trie2 are passed through a caller-supplied remapping function,

     * and it is the remapped values that determine the ranges that

     * will be produced by the iterator.

     *

     *

     * @param mapper provides a function to remap values obtained from the Trie2.

     * @return an Iterator

     */

    public Iterator<Range> iterator(ValueMapper mapper) {

        return new Trie2Iterator(mapper);

    }

    /**

     * When iterating over the contents of a Trie2, an instance of TrieValueMapper may

     * be used to remap the values from the Trie2.  The remapped values will be used

     * both in determining the ranges of codepoints and as the value to be returned

     * for each range.

     *

     * Example of use, with an anonymous subclass of TrieValueMapper:

     *

     *

     * ValueMapper m = new ValueMapper() {

     *    int map(int in) {return in & 0x1f;};

     * }

     * for (Iterator<Trie2EnumRange> iter = trie.iterator(m); i.hasNext(); ) {

     *     Trie2EnumRange r = i.next();

     *     ...  // Do something with the range r.

     * }

     *

     */

    public interface ValueMapper {

        public int  map(int originalVal);

    }

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

    //

    // Below this point are internal implementation items.  No further public API.

    //

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

     /**

     * Trie2 data structure in serialized form:

     *

     * UTrie2Header header;

     * uint16_t index[header.index2Length];

     * uint16_t data[header.shiftedDataLength<<2];  -- or uint32_t data[...]

     *

     * For Java, this is read from the stream into an instance of UTrie2Header.

     * (The C version just places a struct over the raw serialized data.)

     *

     * @internal

     */

    static class UTrie2Header {

        /** "Tri2" in big-endian US-ASCII (0x54726932) */

        int signature;

        /**

         * options bit field (uint16_t):

         * 15.. 4   reserved (0)

         *  3.. 0   UTrie2ValueBits valueBits

         */

        int  options;

        /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH  (uint16_t) */

        int  indexLength;

        /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT  (uint16_t) */

        int  shiftedDataLength;

        /** Null index and data blocks, not shifted.  (uint16_t) */

        int  index2NullOffset, dataNullOffset;

        /**

         * First code point of the single-value range ending with U+10ffff,

         * rounded up and then shifted right by UTRIE2_SHIFT_1.  (uint16_t)

         */

        int shiftedHighStart;

    }

    //

    //  Data members of UTrie2.

    //

    UTrie2Header  header;

    char          index[];           // Index array.  Includes data for 16 bit Tries.

    int           data16;            // Offset to data portion of the index array, if 16 bit data.

                                     //    zero if 32 bit data.

    int           data32[];          // NULL if 16b data is used via index

    int           indexLength;

    int           dataLength;

    int           index2NullOffset;  // 0xffff if there is no dedicated index-2 null block

    int           initialValue;

    /** Value returned for out-of-range code points and illegal UTF-8. */

    int           errorValue;

    /* Start of the last range which ends at U+10ffff, and its value. */

    int           highStart;

    int           highValueIndex;

    int           dataNullOffset;

    /**

     * Trie2 constants, defining shift widths, index array lengths, etc.

     *

     * These are needed for the runtime macros but users can treat these as

     * implementation details and skip to the actual public API further below.

     */

    static final int UTRIE2_OPTIONS_VALUE_BITS_MASK=0x000f;

    /** Shift size for getting the index-1 table offset. */

    static final int UTRIE2_SHIFT_1=6+5;

    /** Shift size for getting the index-2 table offset. */

    static final int UTRIE2_SHIFT_2=5;

    /**

     * Difference between the two shift sizes,

     * for getting an index-1 offset from an index-2 offset. 6=11-5

     */

    static final int UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2;

    /**

     * Number of index-1 entries for the BMP. 32=0x20

     * This part of the index-1 table is omitted from the serialized form.

     */

    static final int UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1;

    /** Number of entries in an index-2 block. 64=0x40 */

    static final int UTRIE2_INDEX_2_BLOCK_LENGTH=1<<UTRIE2_SHIFT_1_2;

    /** Mask for getting the lower bits for the in-index-2-block offset. */

    static final int UTRIE2_INDEX_2_MASK=UTRIE2_INDEX_2_BLOCK_LENGTH-1;

    /** Number of entries in a data block. 32=0x20 */

    static final int UTRIE2_DATA_BLOCK_LENGTH=1<<UTRIE2_SHIFT_2;

    /** Mask for getting the lower bits for the in-data-block offset. */

    static final int UTRIE2_DATA_MASK=UTRIE2_DATA_BLOCK_LENGTH-1;

    /**

     * Shift size for shifting left the index array values.

     * Increases possible data size with 16-bit index values at the cost

     * of compactability.

     * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY.

     */

    static final int UTRIE2_INDEX_SHIFT=2;

    /** The alignment size of a data block. Also the granularity for compaction. */

    static final int UTRIE2_DATA_GRANULARITY=1<<UTRIE2_INDEX_SHIFT;

    /**

     * The part of the index-2 table for U+D800..U+DBFF stores values for

     * lead surrogate code _units_ not code _points_.

     * Values for lead surrogate code _points_ are indexed with this portion of the table.

     * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.)

     */

    static final int UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2;

    static final int UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2;

    /** Count the lengths of both BMP pieces. 2080=0x820 */

    static final int UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH;

    /**

     * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820.

     * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2.

     */

    static final int UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH;

    static final int UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6;  /* U+0800 is the first code point after 2-byte UTF-8 */

    /**

     * The index-1 table, only used for supplementary code points, at offset 2112=0x840.

     * Variable length, for code points up to highStart, where the last single-value range starts.

     * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1.

     * (For 0x100000 supplementary code points U+10000..U+10ffff.)

     *

     * The part of the index-2 table for supplementary code points starts

     * after this index-1 table.

     *

     * Both the index-1 table and the following part of the index-2 table

     * are omitted completely if there is only BMP data.

     */

    static final int UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH;

    /**

     * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80.

     * Used with linear access for single bytes 0..0xbf for simple error handling.

     * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH.

     */

    static final int UTRIE2_BAD_UTF8_DATA_OFFSET=0x80;

    /**

     * Implementation class for an iterator over a Trie2.

     *

     *   Iteration over a Trie2 first returns all of the ranges that are indexed by code points,

     *   then returns the special alternate values for the lead surrogates

     *

     * @internal

     */

    class Trie2Iterator implements Iterator<Range> {

        // The normal constructor that configures the iterator to cover the complete

        //   contents of the Trie2

        Trie2Iterator(ValueMapper vm) {

            mapper    = vm;

            nextStart = 0;

            limitCP   = 0x110000;

            doLeadSurrogates = true;

        }

        /**

         *  The main next() function for Trie2 iterators

         *

         */

        public Range next() {

            if (!hasNext()) {

                throw new NoSuchElementException();

            }

            if (nextStart >= limitCP) {

                // Switch over from iterating normal code point values to

                //   doing the alternate lead-surrogate values.

                doingCodePoints = false;

                nextStart = 0xd800;

            }

            int   endOfRange = 0;

            int   val = 0;

            int   mappedVal = 0;

            if (doingCodePoints) {

                // Iteration over code point values.

                val = get(nextStart);

                mappedVal = mapper.map(val);

                endOfRange = rangeEnd(nextStart, limitCP, val);

                // Loop once for each range in the Trie2 with the same raw (unmapped) value.

                // Loop continues so long as the mapped values are the same.

                for (;;) {

                    if (endOfRange >= limitCP-1) {

                        break;