/*

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

 */

package java.lang;

import java.util.Arrays;

import java.util.Locale;

import java.util.Spliterator;

import java.util.function.Consumer;

import java.util.function.IntConsumer;

import java.util.stream.Stream;

import java.util.stream.StreamSupport;

import jdk.internal.HotSpotIntrinsicCandidate;

import jdk.internal.vm.annotation.ForceInline;

import jdk.internal.vm.annotation.DontInline;

import static java.lang.String.UTF16;

import static java.lang.String.LATIN1;

final class StringUTF16 {

    public static byte[] newBytesFor(int len) {

        if (len < 0) {

            throw new NegativeArraySizeException();

        }

        if (len > MAX_LENGTH) {

            throw new OutOfMemoryError("UTF16 String size is " + len +

                                       ", should be less than " + MAX_LENGTH);

        }

        return new byte[len << 1];

    }

    @HotSpotIntrinsicCandidate

    // intrinsic performs no bounds checks

    static void putChar(byte[] val, int index, int c) {

        assert index >= 0 && index < length(val) : "Trusted caller missed bounds check";

        index <<= 1;

        val[index++] = (byte)(c >> HI_BYTE_SHIFT);

        val[index]   = (byte)(c >> LO_BYTE_SHIFT);

    }

    @HotSpotIntrinsicCandidate

    // intrinsic performs no bounds checks

    static char getChar(byte[] val, int index) {

        assert index >= 0 && index < length(val) : "Trusted caller missed bounds check";

        index <<= 1;

        return (char)(((val[index++] & 0xff) << HI_BYTE_SHIFT) |

                      ((val[index]   & 0xff) << LO_BYTE_SHIFT));

    }

    public static int length(byte[] value) {

        return value.length >> 1;

    }

    private static int codePointAt(byte[] value, int index, int end, boolean checked) {

        assert index < end;

        if (checked) {

            checkIndex(index, value);

        }

        char c1 = getChar(value, index);

        if (Character.isHighSurrogate(c1) && ++index < end) {

            if (checked) {

                checkIndex(index, value);

            }

            char c2 = getChar(value, index);

            if (Character.isLowSurrogate(c2)) {

               return Character.toCodePoint(c1, c2);

            }

        }

        return c1;

    }

    public static int codePointAt(byte[] value, int index, int end) {

       return codePointAt(value, index, end, false /* unchecked */);

    }

    private static int codePointBefore(byte[] value, int index, boolean checked) {

        --index;

        if (checked) {

            checkIndex(index, value);

        }

        char c2 = getChar(value, index);

        if (Character.isLowSurrogate(c2) && index > 0) {

            --index;

            if (checked) {

                checkIndex(index, value);

            }

            char c1 = getChar(value, index);

            if (Character.isHighSurrogate(c1)) {

               return Character.toCodePoint(c1, c2);

            }

        }

        return c2;

    }

    public static int codePointBefore(byte[] value, int index) {

        return codePointBefore(value, index, false /* unchecked */);

    }

    private static int codePointCount(byte[] value, int beginIndex, int endIndex, boolean checked) {

        assert beginIndex <= endIndex;

        int count = endIndex - beginIndex;

        int i = beginIndex;

        if (checked && i < endIndex) {

            checkBoundsBeginEnd(i, endIndex, value);

        }

        for (; i < endIndex - 1; ) {

            if (Character.isHighSurrogate(getChar(value, i++)) &&

                Character.isLowSurrogate(getChar(value, i))) {

                count--;

                i++;

            }

        }

        return count;

    }

    public static int codePointCount(byte[] value, int beginIndex, int endIndex) {

        return codePointCount(value, beginIndex, endIndex, false /* unchecked */);

    }

    public static char[] toChars(byte[] value) {

        char[] dst = new char[value.length >> 1];

        getChars(value, 0, dst.length, dst, 0);

        return dst;

    }

    @HotSpotIntrinsicCandidate

    public static byte[] toBytes(char[] value, int off, int len) {

        byte[] val = newBytesFor(len);

        for (int i = 0; i < len; i++) {

            putChar(val, i, value[off]);

            off++;

        }

        return val;

    }

    public static byte[] compress(char[] val, int off, int len) {

        byte[] ret = new byte[len];

        if (compress(val, off, ret, 0, len) == len) {

            return ret;

        }

        return null;

    }

    public static byte[] compress(byte[] val, int off, int len) {

        byte[] ret = new byte[len];

        if (compress(val, off, ret, 0, len) == len) {

            return ret;

        }

        return null;

    }

    // compressedCopy char[] -> byte[]

    @HotSpotIntrinsicCandidate

    public static int compress(char[] src, int srcOff, byte[] dst, int dstOff, int len) {

        for (int i = 0; i < len; i++) {

            char c = src[srcOff];

            if (c > 0xFF) {

                len = 0;

                break;

            }

            dst[dstOff] = (byte)c;

            srcOff++;

            dstOff++;

        }

        return len;

    }

    // compressedCopy byte[] -> byte[]

    @HotSpotIntrinsicCandidate

    public static int compress(byte[] src, int srcOff, byte[] dst, int dstOff, int len) {

        // We need a range check here because 'getChar' has no checks

        checkBoundsOffCount(srcOff, len, src);

        for (int i = 0; i < len; i++) {

            char c = getChar(src, srcOff);

            if (c > 0xFF) {

                len = 0;

                break;

            }

            dst[dstOff] = (byte)c;

            srcOff++;

            dstOff++;

        }

        return len;

    }

    public static byte[] toBytes(int[] val, int index, int len) {

        final int end = index + len;

        // Pass 1: Compute precise size of char[]

        int n = len;

        for (int i = index; i < end; i++) {

            int cp = val[i];

            if (Character.isBmpCodePoint(cp))

                continue;

            else if (Character.isValidCodePoint(cp))

                n++;

            else throw new IllegalArgumentException(Integer.toString(cp));

        }

        // Pass 2: Allocate and fill in <high, low> pair

        byte[] buf = newBytesFor(n);

        for (int i = index, j = 0; i < end; i++, j++) {

            int cp = val[i];

            if (Character.isBmpCodePoint(cp)) {

                putChar(buf, j, cp);

            } else {

                putChar(buf, j++, Character.highSurrogate(cp));

                putChar(buf, j, Character.lowSurrogate(cp));

            }

        }

        return buf;

    }

    public static byte[] toBytes(char c) {

        byte[] result = new byte[2];

        putChar(result, 0, c);

        return result;

    }

    static byte[] toBytesSupplementary(int cp) {

        byte[] result = new byte[4];

        putChar(result, 0, Character.highSurrogate(cp));

        putChar(result, 1, Character.lowSurrogate(cp));

        return result;

    }

    @HotSpotIntrinsicCandidate

    public static void getChars(byte[] value, int srcBegin, int srcEnd, char dst[], int dstBegin) {

        // We need a range check here because 'getChar' has no checks

        if (srcBegin < srcEnd) {

            checkBoundsOffCount(srcBegin, srcEnd - srcBegin, value);

        }

        for (int i = srcBegin; i < srcEnd; i++) {

            dst[dstBegin++] = getChar(value, i);

        }

    }

    /* @see java.lang.String.getBytes(int, int, byte[], int) */

    public static void getBytes(byte[] value, int srcBegin, int srcEnd, byte dst[], int dstBegin) {

        srcBegin <<= 1;

        srcEnd <<= 1;

        for (int i = srcBegin + (1 >> LO_BYTE_SHIFT); i < srcEnd; i += 2) {

            dst[dstBegin++] = value[i];

        }

    }

    @HotSpotIntrinsicCandidate

    public static boolean equals(byte[] value, byte[] other) {

        if (value.length == other.length) {

            int len = value.length >> 1;

            for (int i = 0; i < len; i++) {

                if (getChar(value, i) != getChar(other, i)) {

                    return false;

                }

            }

            return true;

        }

        return false;

    }

    @HotSpotIntrinsicCandidate

    public static int compareTo(byte[] value, byte[] other) {

        int len1 = length(value);

        int len2 = length(other);

        return compareValues(value, other, len1, len2);

    }

    /*

     * Checks the boundary and then compares the byte arrays.

     */

    public static int compareTo(byte[] value, byte[] other, int len1, int len2) {

        checkOffset(len1, value);

        checkOffset(len2, other);

        return compareValues(value, other, len1, len2);

    }

    private static int compareValues(byte[] value, byte[] other, int len1, int len2) {

        int lim = Math.min(len1, len2);

        for (int k = 0; k < lim; k++) {

            char c1 = getChar(value, k);

            char c2 = getChar(other, k);

            if (c1 != c2) {

                return c1 - c2;

            }

        }

        return len1 - len2;

    }

    @HotSpotIntrinsicCandidate

    public static int compareToLatin1(byte[] value, byte[] other) {

        return -StringLatin1.compareToUTF16(other, value);

    }

    public static int compareToLatin1(byte[] value, byte[] other, int len1, int len2) {

        return -StringLatin1.compareToUTF16(other, value, len2, len1);

    }

    public static int compareToCI(byte[] value, byte[] other) {

        int len1 = length(value);

        int len2 = length(other);

        int lim = Math.min(len1, len2);

        for (int k = 0; k < lim; k++) {

            char c1 = getChar(value, k);

            char c2 = getChar(other, k);

            if (c1 != c2) {

                c1 = Character.toUpperCase(c1);

                c2 = Character.toUpperCase(c2);

                if (c1 != c2) {

                    c1 = Character.toLowerCase(c1);

                    c2 = Character.toLowerCase(c2);

                    if (c1 != c2) {

                        return c1 - c2;

                    }

                }

            }

        }

        return len1 - len2;

    }

    public static int compareToCI_Latin1(byte[] value, byte[] other) {

        return -StringLatin1.compareToCI_UTF16(other, value);

    }

    public static int hashCode(byte[] value) {

        int h = 0;

        int length = value.length >> 1;

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

            h = 31 * h + getChar(value, i);

        }

        return h;

    }

    public static int indexOf(byte[] value, int ch, int fromIndex) {

        int max = value.length >> 1;

        if (fromIndex < 0) {

            fromIndex = 0;

        } else if (fromIndex >= max) {

            // Note: fromIndex might be near -1>>>1.

            return -1;

        }

        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {

            // handle most cases here (ch is a BMP code point or a

            // negative value (invalid code point))

            return indexOfChar(value, ch, fromIndex, max);

        } else {

            return indexOfSupplementary(value, ch, fromIndex, max);

        }

    }

    @HotSpotIntrinsicCandidate

    public static int indexOf(byte[] value, byte[] str) {

        if (str.length == 0) {

            return 0;

        }

        if (value.length < str.length) {

            return -1;

        }

        return indexOfUnsafe(value, length(value), str, length(str), 0);

    }

    @HotSpotIntrinsicCandidate

    public static int indexOf(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {

        checkBoundsBeginEnd(fromIndex, valueCount, value);

        checkBoundsBeginEnd(0, strCount, str);

        return indexOfUnsafe(value, valueCount, str, strCount, fromIndex);

    }

    private static int indexOfUnsafe(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {

        assert fromIndex >= 0;

        assert strCount > 0;

        assert strCount <= length(str);

        assert valueCount >= strCount;

        char first = getChar(str, 0);

        int max = (valueCount - strCount);

        for (int i = fromIndex; i <= max; i++) {

            // Look for first character.

            if (getChar(value, i) != first) {

                while (++i <= max && getChar(value, i) != first);

            }

            // Found first character, now look at the rest of value

            if (i <= max) {

                int j = i + 1;

                int end = j + strCount - 1;

                for (int k = 1; j < end && getChar(value, j) == getChar(str, k); j++, k++);

                if (j == end) {

                    // Found whole string.

                    return i;

                }

            }

        }

        return -1;

    }

    /**

     * Handles indexOf Latin1 substring in UTF16 string.

     */

    @HotSpotIntrinsicCandidate

    public static int indexOfLatin1(byte[] value, byte[] str) {

        if (str.length == 0) {

            return 0;

        }

        if (length(value) < str.length) {

            return -1;

        }

        return indexOfLatin1Unsafe(value, length(value), str, str.length, 0);

    }

    @HotSpotIntrinsicCandidate

    public static int indexOfLatin1(byte[] src, int srcCount, byte[] tgt, int tgtCount, int fromIndex) {

        checkBoundsBeginEnd(fromIndex, srcCount, src);

        String.checkBoundsBeginEnd(0, tgtCount, tgt.length);

        return indexOfLatin1Unsafe(src, srcCount, tgt, tgtCount, fromIndex);

    }

    public static int indexOfLatin1Unsafe(byte[] src, int srcCount, byte[] tgt, int tgtCount, int fromIndex) {

        assert fromIndex >= 0;

        assert tgtCount > 0;

        assert tgtCount <= tgt.length;

        assert srcCount >= tgtCount;

        char first = (char)(tgt[0] & 0xff);

        int max = (srcCount - tgtCount);

        for (int i = fromIndex; i <= max; i++) {

            // Look for first character.

            if (getChar(src, i) != first) {

                while (++i <= max && getChar(src, i) != first);

            }

            // Found first character, now look at the rest of v2

            if (i <= max) {

                int j = i + 1;

                int end = j + tgtCount - 1;

                for (int k = 1;

                     j < end && getChar(src, j) == (tgt[k] & 0xff);

                     j++, k++);

                if (j == end) {

                    // Found whole string.

                    return i;

                }

            }

        }

        return -1;

    }

    @HotSpotIntrinsicCandidate

    private static int indexOfChar(byte[] value, int ch, int fromIndex, int max) {

        checkBoundsBeginEnd(fromIndex, max, value);

        return indexOfCharUnsafe(value, ch, fromIndex, max);

    }

    private static int indexOfCharUnsafe(byte[] value, int ch, int fromIndex, int max) {

        for (int i = fromIndex; i < max; i++) {

            if (getChar(value, i) == ch) {

                return i;

            }

        }

        return -1;

    }

    /**

     * Handles (rare) calls of indexOf with a supplementary character.

     */

    private static int indexOfSupplementary(byte[] value, int ch, int fromIndex, int max) {

        if (Character.isValidCodePoint(ch)) {

            final char hi = Character.highSurrogate(ch);

            final char lo = Character.lowSurrogate(ch);

            checkBoundsBeginEnd(fromIndex, max, value);

            for (int i = fromIndex; i < max - 1; i++) {

                if (getChar(value, i) == hi && getChar(value, i + 1 ) == lo) {

                    return i;

                }

            }

        }

        return -1;

    }

    // srcCoder == UTF16 && tgtCoder == UTF16

    public static int lastIndexOf(byte[] src, int srcCount,

                                  byte[] tgt, int tgtCount, int fromIndex) {

        assert fromIndex >= 0;

        assert tgtCount > 0;

        assert tgtCount <= length(tgt);

        int min = tgtCount - 1;

        int i = min + fromIndex;

        int strLastIndex = tgtCount - 1;

        checkIndex(strLastIndex, tgt);

        char strLastChar = getChar(tgt, strLastIndex);

        checkIndex(i, src);