/*

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

import jdk.internal.HotSpotIntrinsicCandidate;

import static java.lang.String.UTF16;

import static java.lang.String.LATIN1;

import static java.lang.String.checkIndex;

import static java.lang.String.checkOffset;

import static java.lang.String.checkBoundsOffCount;

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

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

        index <<= 1;

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

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

    }

    @HotSpotIntrinsicCandidate

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

        index <<= 1;

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

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

    }

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

        if (index < 0 || index >= value.length >> 1) {

            throw new StringIndexOutOfBoundsException(index);

        }

        return getChar(value, index);

    }

    public static int length(byte[] value) {

        return value.length >> 1;

    }

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

        char c1 = getChar(value, index);

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

            char c2 = getChar(value, index);

            if (Character.isLowSurrogate(c2)) {

               return Character.toCodePoint(c1, c2);

            }

        }

        return c1;

    }

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

        char c2 = getChar(value, --index);

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

            char c1 = getChar(value, --index);

            if (Character.isHighSurrogate(c1)) {

               return Character.toCodePoint(c1, c2);

            }

        }

        return c2;

    }

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

        int count = endIndex - beginIndex;

        for (int i = beginIndex; i < endIndex; ) {

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

                i < endIndex &&

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

                count--;

                i++;

            }

        }

        return count;

    }

    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 << 1, len << 1, src.length);

        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;

    }

    @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 << 1, (srcEnd - srcBegin) << 1, value.length);

        }

        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);

        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 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 == 0) {

            return -1;

        }

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

    }

    @HotSpotIntrinsicCandidate

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

        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 (value.length == 0) {

            return -1;

        }

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

    }

    @HotSpotIntrinsicCandidate

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

        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) {

        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);

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

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

                    return i;

                }

            }

        }

        return -1;

    }

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

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

        int min = tgtCount - 1;

        int i = min + fromIndex;

        int strLastIndex = tgtCount - 1;

        char strLastChar = getChar(tgt, strLastIndex);

    startSearchForLastChar:

        while (true) {

            while (i >= min && getChar(src, i) != strLastChar) {

                i--;

            }

            if (i < min) {

                return -1;

            }

            int j = i - 1;

            int start = j - strLastIndex;

            int k = strLastIndex - 1;

            while (j > start) {

                if (getChar(src, j--) != getChar(tgt, k--)) {

                    i--;

                    continue startSearchForLastChar;

                }

            }

            return start + 1;

        }

    }

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

        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {

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

            // negative value (invalid code point))

            int i = Math.min(fromIndex, (value.length >> 1) - 1);

            for (; i >= 0; i--) {

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

                    return i;

                }

            }

            return -1;

        } else {

            return lastIndexOfSupplementary(value, ch, fromIndex);

        }

    }

    /**

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

     */

    private static int lastIndexOfSupplementary(final byte[] value, int ch, int fromIndex) {

        if (Character.isValidCodePoint(ch)) {

            char hi = Character.highSurrogate(ch);

            char lo = Character.lowSurrogate(ch);

            int i = Math.min(fromIndex, (value.length >> 1) - 2);

            for (; i >= 0; i--) {

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

                    return i;

                }

            }

        }

        return -1;

    }

    public static String replace(byte[] value, char oldChar, char newChar) {

        int len = value.length >> 1;

        int i = -1;

        while (++i < len) {

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

                break;

            }

        }

        if (i < len) {

            byte buf[] = new byte[value.length];

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

                putChar(buf, j, getChar(value, j)); // TBD:arraycopy?

            }

            while (i < len) {

                char c = getChar(value, i);

                putChar(buf, i, c == oldChar ? newChar : c);

                i++;

           }

           // Check if we should try to compress to latin1

           if (String.COMPACT_STRINGS &&

               !StringLatin1.canEncode(oldChar) &&

               StringLatin1.canEncode(newChar)) {

               byte[] val = compress(buf, 0, len);

               if (val != null) {

                   return new String(val, LATIN1);

               }

           }

           return new String(buf, UTF16);

        }

        return null;

    }

    public static boolean regionMatchesCI(byte[] value, int toffset,

                                          byte[] other, int ooffset, int len) {

        int last = toffset + len;

        while (toffset < last) {

            char c1 = getChar(value, toffset++);

            char c2 = getChar(other, ooffset++);

            if (c1 == c2) {

                continue;

            }

            // try converting both characters to uppercase.

            // If the results match, then the comparison scan should

            // continue.

            char u1 = Character.toUpperCase(c1);

            char u2 = Character.toUpperCase(c2);

            if (u1 == u2) {