/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.hyracks.data.std.primitive;

import static org.apache.hyracks.util.string.UTF8StringUtil.HIGH_SURROGATE_WITHOUT_LOW_SURROGATE;
import static org.apache.hyracks.util.string.UTF8StringUtil.LOW_SURROGATE_WITHOUT_HIGH_SURROGATE;

import java.io.IOException;
import java.nio.charset.Charset;

import org.apache.hyracks.api.dataflow.value.ITypeTraits;
import org.apache.hyracks.api.exceptions.HyracksDataException;
import org.apache.hyracks.api.io.IJsonSerializable;
import org.apache.hyracks.api.io.IPersistedResourceRegistry;
import org.apache.hyracks.data.std.api.AbstractPointable;
import org.apache.hyracks.data.std.api.IComparable;
import org.apache.hyracks.data.std.api.IHashable;
import org.apache.hyracks.data.std.api.IPointable;
import org.apache.hyracks.data.std.api.IPointableFactory;
import org.apache.hyracks.data.std.util.GrowableArray;
import org.apache.hyracks.data.std.util.UTF8StringBuilder;
import org.apache.hyracks.util.string.UTF8StringUtil;

import com.fasterxml.jackson.databind.JsonNode;

import it.unimi.dsi.fastutil.ints.IntCollection;

public final class UTF8StringPointable extends AbstractPointable implements IHashable, IComparable {

    public static final UTF8StringPointableFactory FACTORY = new UTF8StringPointableFactory();
    public static final ITypeTraits TYPE_TRAITS = VarLengthTypeTrait.INSTANCE;
    // These values are cached to speed up the length data access.
    // Since we are using the variable-length encoding, we can save the repeated decoding efforts.
    // WARNING: must call the resetConstants() method after each reset().
    private int utf8Length;
    private int metaLength;
    private int hashValue;
    private int stringLength;

    public static final UTF8StringPointable SPACE_STRING_POINTABLE = generateUTF8Pointable(" ");
    public static final Charset CESU8_CHARSET = Charset.forName("CESU8");

    /**
     * reset those meta length.
     * Since the {@code utf8Length} and the {@code metaLength} are often used, we compute those two values in advance.
     * As for the {@code stringLength} and the {@code hashValue}, they will be lazily initialized after the first call.
     */
    @Override
    protected void afterReset() {
        utf8Length = UTF8StringUtil.getUTFLength(bytes, start);
        metaLength = UTF8StringUtil.getNumBytesToStoreLength(getUTF8Length());
        hashValue = 0;
        stringLength = -1;
    }

    public static class UTF8StringPointableFactory implements IPointableFactory {
        private static final long serialVersionUID = 1L;

        private UTF8StringPointableFactory() {
        }

        @Override
        public UTF8StringPointable createPointable() {
            return new UTF8StringPointable();
        }

        @Override
        public ITypeTraits getTypeTraits() {
            return TYPE_TRAITS;
        }

        @Override
        public JsonNode toJson(IPersistedResourceRegistry registry) throws HyracksDataException {
            return registry.getClassIdentifier(getClass(), serialVersionUID);
        }

        @SuppressWarnings("squid:S1172") // unused parameter
        public static IJsonSerializable fromJson(IPersistedResourceRegistry registry, JsonNode json) {
            return FACTORY;
        }
    }

    public static UTF8StringPointable generateUTF8Pointable(String string) {
        byte[] bytes;
        bytes = UTF8StringUtil.writeStringToBytes(string);
        UTF8StringPointable ptr = new UTF8StringPointable();
        ptr.set(bytes, 0, bytes.length);
        return ptr;
    }

    /**
     * Returns the character at the given byte offset. The caller is responsible for making sure that
     * the provided offset is within bounds and points to the beginning of a valid UTF8 character.
     *
     * @param offset
     *            - Byte offset
     * @return Character at the given offset.
     */
    public char charAt(int offset) {
        return UTF8StringUtil.charAt(bytes, start + offset);
    }

    public int charSize(int offset) {
        return UTF8StringUtil.charSize(bytes, start + offset);
    }

    public int codePointAt(int offset) {
        return UTF8StringUtil.codePointAt(bytes, start + offset);
    }

    public int codePointSize(int offset) {
        return UTF8StringUtil.codePointSize(bytes, start + offset);
    }

    public void getCodePoints(IntCollection codePointSet) {
        int byteIdx = 0;
        while (byteIdx < utf8Length) {
            codePointSet.add(codePointAt(metaLength + byteIdx));
            byteIdx += codePointSize(metaLength + byteIdx);
        }

        if (byteIdx != utf8Length) {
            throw new IllegalArgumentException("Decoding error: malformed bytes");
        }
    }

    /**
     * Gets the length of the string in characters.
     * The first time call will need to go through the entire string, the following call will just return the pre-caculated result
     *
     * @return length of string in characters
     */
    public int getStringLength() {
        if (stringLength < 0) {
            stringLength = UTF8StringUtil.getStringLength(bytes, start);
        }
        return stringLength;
    }

    /**
     * Gets the length of the UTF-8 encoded string in bytes.
     *
     * @return length of UTF-8 encoded string in bytes
     */
    public int getUTF8Length() {
        return utf8Length;
    }

    public int getMetaDataLength() {
        return metaLength;
    }

    public int getCharStartOffset() {
        return getStartOffset() + getMetaDataLength();
    }

    @Override
    public int compareTo(IPointable pointer) {
        return compareTo(pointer.getByteArray(), pointer.getStartOffset(), pointer.getLength());
    }

    @Override
    public int compareTo(byte[] bytes, int start, int length) {
        return UTF8StringUtil.compareTo(this.bytes, this.start, bytes, start);
    }

    @Override
    public int hash() {
        if (hashValue == 0) {
            hashValue = UTF8StringUtil.hash(this.bytes, this.start);
        }
        return hashValue;
    }

    public void toString(StringBuilder buffer) {
        UTF8StringUtil.toString(buffer, bytes, start);
    }

    @Override
    public String toString() {
        return new String(bytes, getCharStartOffset(), getUTF8Length(), CESU8_CHARSET);
    }

    public int ignoreCaseCompareTo(UTF8StringPointable other) {
        return UTF8StringUtil.lowerCaseCompareTo(this.getByteArray(), this.getStartOffset(), other.getByteArray(),
                other.getStartOffset());
    }

    public int find(UTF8StringPointable pattern, boolean ignoreCase) {
        return find(this, pattern, ignoreCase);
    }

    @SuppressWarnings("squid:S1172") // unused parameter
    public static int compare(byte[] bytes, int start, int length, byte[] thatBytes, int thatStart, int thatLength) {
        return UTF8StringUtil.compareTo(bytes, start, thatBytes, thatStart);
    }

    // takes advantage of cached utf8 length and meta length
    public static int compare(UTF8StringPointable pointable1, UTF8StringPointable pointable2) {
        return UTF8StringUtil.compareTo(pointable1.bytes, pointable1.start + pointable1.metaLength,
                pointable1.utf8Length, pointable2.bytes, pointable2.start + pointable2.metaLength,
                pointable2.utf8Length);
    }

    /**
     * @param src,
     *            the source string.
     * @param pattern,
     *            the pattern string.
     * @param ignoreCase,
     *            to ignore case or not.
     * @return the byte offset of the first character of the matching string. Not including the MetaLength.
     */
    public static int find(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase) {
        return find(src, pattern, ignoreCase, 0);
    }

    /**
     * @param src,
     *            the source string.
     * @param pattern,
     *            the pattern string.
     * @param ignoreCase,
     *            to ignore case or not.
     * @return the offset in the unit of code point of the first character of the matching string. Not including the MetaLength.
     */
    public static int findInCodePoint(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase) {
        return findInByteOrCodePoint(src, pattern, ignoreCase, 0, false);
    }

    /**
     * @param src,
     *            the source string.
     * @param pattern,
     *            the pattern string.
     * @param ignoreCase,
     *            to ignore case or not.
     * @param startMatch,
     *            the start offset.
     * @return the byte offset of the first character of the matching string after <code>startMatchPos}</code>.
     *         Not including the MetaLength.
     */
    public static int find(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase, int startMatch) {
        return findInByteOrCodePoint(src, pattern, ignoreCase, startMatch, true);
    }

    /**
     * @param src,
     *            the source string.
     * @param pattern,
     *            the pattern string.
     * @param ignoreCase,
     *            to ignore case or not.
     * @param startMatch,
     *            the start offset.
     * @return the offset in the unit of code point of the first character of the matching string. Not including the MetaLength.
     */
    public static int findInCodePoint(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase,
            int startMatch) {
        return findInByteOrCodePoint(src, pattern, ignoreCase, startMatch, false);
    }

    // If resultInByte is true, then return the position in bytes, otherwise return the position in code points
    private static int findInByteOrCodePoint(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase,
            int startMatch, boolean resultInByte) {
        int startMatchPos = startMatch;
        final int srcUtfLen = src.getUTF8Length();
        final int pttnUtfLen = pattern.getUTF8Length();
        final int srcStart = src.getMetaDataLength();
        final int pttnStart = pattern.getMetaDataLength();
        int codePointCount = 0;

        int maxStart = srcUtfLen - pttnUtfLen;
        boolean prevHighSurrogate = false;
        while (startMatchPos <= maxStart) {
            int c1 = startMatchPos;
            int c2 = 0;
            while (c1 < srcUtfLen && c2 < pttnUtfLen) {
                char ch1 = src.charAt(srcStart + c1);
                char ch2 = pattern.charAt(pttnStart + c2);

                if (ch1 != ch2) {
                    // Currently, the ignoreCase is only valid for one-surrogate characters
                    // (e.g. characters whose UTF-16 encoding is 2-byte (1 Java char) instead of 4-byte (2 Java chars).
                    // We may need to support the two-surrogate characters in the future
                    //
                    // Another edge case is that one letter may have different forms of lower cases in different languages
                    // For example, the letter I may have "i" as the lower case in English but "ı" in Turkish.
                    // We may need to use methods such as String.toLowerCase(Locale locale) to support other languages in the future
                    // Reference: https://stackoverflow.com/questions/11063102/using-locales-with-javas-tolowercase-and-touppercase
                    if (!ignoreCase || Character.toLowerCase(ch1) != Character.toLowerCase(ch2)) {
                        break;
                    }
                }
                c1 += src.charSize(srcStart + c1);
                c2 += pattern.charSize(pttnStart + c2);
            }

            if (c2 == pttnUtfLen) {
                if (resultInByte) {
                    return startMatchPos;
                } else {
                    if (prevHighSurrogate) {
                        throw new IllegalArgumentException(HIGH_SURROGATE_WITHOUT_LOW_SURROGATE);
                    }
                    return codePointCount;
                }
            }

            // The result is counted in code point instead of bytes
            if (resultInByte == false) {
                char ch = src.charAt(srcStart + startMatchPos);
                if (Character.isHighSurrogate(ch)) {
                    prevHighSurrogate = true;
                } else if (Character.isLowSurrogate(ch)) {
                    if (prevHighSurrogate) {
                        codePointCount++;
                        prevHighSurrogate = false;
                    } else {
                        throw new IllegalArgumentException(LOW_SURROGATE_WITHOUT_HIGH_SURROGATE);
                    }
                } else {
                    codePointCount++;
                }
            }

            startMatchPos += src.charSize(srcStart + startMatchPos);
        }
        return -1;
    }

    public boolean contains(UTF8StringPointable pattern, boolean ignoreCase) {
        return contains(this, pattern, ignoreCase);
    }

    public static boolean contains(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase) {
        return find(src, pattern, ignoreCase) >= 0;
    }

    public boolean startsWith(UTF8StringPointable pattern, boolean ignoreCase) {
        return startsWith(this, pattern, ignoreCase);
    }

    public static boolean startsWith(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase) {
        int utflen1 = src.getUTF8Length();
        int utflen2 = pattern.getUTF8Length();
        if (utflen2 > utflen1) {
            return false;
        }

        int s1Start = src.getMetaDataLength();
        int s2Start = pattern.getMetaDataLength();

        int c1 = 0;
        int c2 = 0;
        while (c1 < utflen1 && c2 < utflen2) {
            char ch1 = src.charAt(s1Start + c1);
            char ch2 = pattern.charAt(s2Start + c2);
            if (ch1 != ch2) {
                if (!ignoreCase || Character.toLowerCase(ch1) != Character.toLowerCase(ch2)) {
                    break;
                }
            }
            c1 += src.charSize(s1Start + c1);
            c2 += pattern.charSize(s2Start + c2);
        }
        return (c2 == utflen2);
    }

    public boolean endsWith(UTF8StringPointable pattern, boolean ignoreCase) {
        return endsWith(this, pattern, ignoreCase);
    }

    public static boolean endsWith(UTF8StringPointable src, UTF8StringPointable pattern, boolean ignoreCase) {
        int len1 = src.getUTF8Length();
        int len2 = pattern.getUTF8Length();
        if (len2 > len1) {
            return false;
        }

        int s1Start = src.getMetaDataLength();
        int s2Start = pattern.getMetaDataLength();

        int c1 = len1 - len2;
        int c2 = 0;
        while (c1 < len1 && c2 < len2) {
            char ch1 = src.charAt(s1Start + c1);
            char ch2 = pattern.charAt(s2Start + c2);

            if (ch1 != ch2) {
                if (!ignoreCase || Character.toLowerCase(ch1) != Character.toLowerCase(ch2)) {
                    break;
                }
            }
            c1 += src.charSize(s1Start + c1);
            c2 += pattern.charSize(s2Start + c2);
        }
        return (c2 == len2);
    }

    public void concat(UTF8StringPointable next, UTF8StringBuilder builder, GrowableArray out) throws IOException {
        concat(this, next, builder, out);
    }

    public static void concat(UTF8StringPointable first, UTF8StringPointable next, UTF8StringBuilder builder,
            GrowableArray out) throws IOException {
        int firstUtfLen = first.getUTF8Length();
        int nextUtfLen = next.getUTF8Length();

        builder.reset(out, firstUtfLen + nextUtfLen);
        builder.appendUtf8StringPointable(first);
        builder.appendUtf8StringPointable(next);
        builder.finish();
    }

    /**
     * Return the substring. Note that the offset and length are in the unit of code point.
     * @return {@code true} if substring was successfully written into given {@code out}, or
     *         {@code false} if substring could not be obtained ({@code codePointOffset} or {@code codePointLength}
     *         are less than 0 or starting position is greater than the input length)
     */
    public boolean substr(int codePointOffset, int codePointLength, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        return substr(this, codePointOffset, codePointLength, builder, out);
    }

    /**
     * Return the substring. Note that the offset and length are in the unit of code point.
     * @return {@code true} if substring was successfully written into given {@code out}, or
     *         {@code false} if substring could not be obtained ({@code codePointOffset} or {@code codePointLength}
     *         are less than 0 or starting position is greater than the input length)
     */
    public static boolean substr(UTF8StringPointable src, int codePointOffset, int codePointLength,
            UTF8StringBuilder builder, GrowableArray out) throws IOException {
        if (codePointOffset < 0 || codePointLength < 0) {
            return false;
        }

        int utfLen = src.getUTF8Length();
        int codePointIdx = 0;
        int byteIdx = 0;
        while (byteIdx < utfLen && codePointIdx < codePointOffset) {
            byteIdx += src.codePointSize(src.getMetaDataLength() + byteIdx);
            codePointIdx++;
        }
        if (byteIdx >= utfLen) {
            return false;
        }

        int estimateOutBytes = byteIdx == 0 ? codePointLength : (int) (codePointLength * 1.0 * byteIdx / codePointIdx);
        builder.reset(out, Math.min(utfLen - byteIdx, estimateOutBytes));
        codePointIdx = 0;
        while (byteIdx < utfLen && codePointIdx < codePointLength) {
            builder.appendCodePoint(src.codePointAt(src.getMetaDataLength() + byteIdx));
            codePointIdx++;
            byteIdx += src.codePointSize(src.getMetaDataLength() + byteIdx);
        }
        builder.finish();
        return true;
    }

    public void substrBefore(UTF8StringPointable match, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        substrBefore(this, match, builder, out);
    }

    /**
     * Write the substring before the given pattern. It will write a empty string if the matching fails.
     *
     * @param src
     * @param match
     * @param builder
     * @param out
     * @throws IOException
     */
    public static void substrBefore(UTF8StringPointable src, UTF8StringPointable match, UTF8StringBuilder builder,
            GrowableArray out) throws IOException {

        int byteOffset = find(src, match, false);
        if (byteOffset < 0) {
            builder.reset(out, 0);
            builder.finish();
            return;
        }

        final int srcMetaLen = src.getMetaDataLength();

        builder.reset(out, byteOffset);
        for (int idx = 0; idx < byteOffset;) {
            builder.appendChar(src.charAt(srcMetaLen + idx));
            idx += src.charSize(srcMetaLen + idx);
        }
        builder.finish();
    }

    public void substrAfter(UTF8StringPointable match, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        substrAfter(this, match, builder, out);
    }

    /**
     * Write the substring after the given pattern. It will write a empty string if the matching fails.
     *
     * @param src
     * @param match
     * @param builder
     * @param out
     */
    public static void substrAfter(UTF8StringPointable src, UTF8StringPointable match, UTF8StringBuilder builder,
            GrowableArray out) throws IOException {

        int byteOffset = find(src, match, false);
        if (byteOffset < 0) {
            builder.reset(out, 0);
            builder.finish();
            return;
        }

        final int srcUtfLen = src.getUTF8Length();
        final int matchUtfLen = match.getUTF8Length();

        final int resultLen = srcUtfLen - byteOffset - matchUtfLen;
        builder.reset(out, resultLen);
        builder.appendUtf8StringPointable(src, src.getCharStartOffset() + byteOffset + matchUtfLen, resultLen);
        builder.finish();
    }

    public void lowercase(UTF8StringBuilder builder, GrowableArray out) throws IOException {
        lowercase(this, builder, out);
    }

    /**
     * Generates a lower case string of an input string.
     *
     * @param src
     *            , the input source string.
     * @param builder
     *            , a builder for the resulting string.
     * @param out
     *            , the storage for a result string.
     * @throws IOException
     */
    public static void lowercase(UTF8StringPointable src, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        final int srcUtfLen = src.getUTF8Length();
        final int srcStart = src.getMetaDataLength();

        builder.reset(out, srcUtfLen);
        int byteIndex = 0;
        while (byteIndex < srcUtfLen) {
            builder.appendChar(Character.toLowerCase(src.charAt(srcStart + byteIndex)));
            byteIndex += src.charSize(srcStart + byteIndex);
        }
        builder.finish();
    }

    public void uppercase(UTF8StringBuilder builder, GrowableArray out) throws IOException {
        uppercase(this, builder, out);
    }

    /**
     * Generates an upper case string of an input string.
     *
     * @param src
     *            , the input source string.
     * @param builder
     *            , a builder for the resulting string.
     * @param out
     *            , the storage for a result string.
     * @throws IOException
     */
    public static void uppercase(UTF8StringPointable src, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        final int srcUtfLen = src.getUTF8Length();
        final int srcStart = src.getMetaDataLength();

        builder.reset(out, srcUtfLen);
        int byteIndex = 0;
        while (byteIndex < srcUtfLen) {
            builder.appendChar(Character.toUpperCase(src.charAt(srcStart + byteIndex)));
            byteIndex += src.charSize(srcStart + byteIndex);
        }
        builder.finish();
    }

    public void initCap(UTF8StringBuilder builder, GrowableArray out) throws IOException {
        initCap(this, builder, out);
    }

    /**
     * Generates a "title" format string from an input source string, i.e., the first letter of each word
     * is in the upper case while the other letter is in the lower case.
     *
     * @param src
     *            , the input source string.
     * @param builder
     *            , a builder for the resulting string.
     * @param out
     *            , the storage for a result string.
     * @throws IOException
     */
    public static void initCap(UTF8StringPointable src, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        final int srcUtfLen = src.getUTF8Length();
        final int srcStart = src.getMetaDataLength();

        builder.reset(out, srcUtfLen);
        boolean toUpperCase = true;
        int byteIndex = 0;
        while (byteIndex < srcUtfLen) {
            char originalChar = src.charAt(srcStart + byteIndex);
            boolean isLetter = Character.isLetter(originalChar);

            // Make the first character into upper case while the later ones into lower case.
            char resultChar = toUpperCase && isLetter ? Character.toUpperCase(originalChar)
                    : (isLetter ? Character.toLowerCase(originalChar) : originalChar);
            builder.appendChar(resultChar);
            byteIndex += src.charSize(srcStart + byteIndex);

            // Whether the next letter needs to switch to the upper case.
            toUpperCase = !isLetter;
        }
        builder.finish();
    }

    /**
     * Generates a trimmed string of an input source string.
     *
     * @param srcPtr
     *            , the input source string
     * @param builder
     *            , the result string builder.
     * @param out
     *            , the storage for the output string.
     * @param left
     *            , whether to trim the left side.
     * @param right
     *            , whether to trim the right side.
     * @param codePointSet
     *            , the set of code points that should be trimmed.
     * @throws IOException
     */
    public static void trim(UTF8StringPointable srcPtr, UTF8StringBuilder builder, GrowableArray out, boolean left,
            boolean right, IntCollection codePointSet) throws IOException {
        final int srcUtfLen = srcPtr.getUTF8Length();
        final int srcStart = srcPtr.getMetaDataLength();
        // Finds the start Index (inclusive).
        int startIndex = 0;
        if (left) {
            while (startIndex < srcUtfLen) {
                int codepoint = srcPtr.codePointAt(srcStart + startIndex);
                if (!codePointSet.contains(codepoint)) {
                    break;
                }
                startIndex += srcPtr.codePointSize(srcStart + startIndex);
            }
        }

        // Finds the end index (exclusive).
        int endIndex = srcUtfLen;
        if (right) {
            endIndex = startIndex;
            int cursorIndex = startIndex;
            while (cursorIndex < srcUtfLen) {
                int codePioint = srcPtr.codePointAt(srcStart + cursorIndex);
                cursorIndex += srcPtr.codePointSize(srcStart + cursorIndex);
                if (!codePointSet.contains(codePioint)) {
                    endIndex = cursorIndex;
                }
            }
        }

        // Outputs the desired substring.
        int len = endIndex - startIndex;
        builder.reset(out, len);
        builder.appendUtf8StringPointable(srcPtr, srcPtr.getStartOffset() + srcStart + startIndex, len);
        builder.finish();
    }

    /**
     * Generates a trimmed string from the original string.
     *
     * @param builder
     *            , the result string builder.
     * @param out
     *            , the storage for the output string.
     * @param left
     *            , whether to trim the left side.
     * @param right
     *            , whether to trim the right side.
     * @param codePointSet
     *            , the set of code points that should be trimmed.
     * @throws IOException
     */
    public void trim(UTF8StringBuilder builder, GrowableArray out, boolean left, boolean right,
            IntCollection codePointSet) throws IOException {
        trim(this, builder, out, left, right, codePointSet);
    }

    /**
     * Generates a reversed string from an input source string
     *
     * @param srcPtr
     *            , the input source string.
     * @param builder
     *            , a builder for the resulting string.
     * @param out
     *            , the storage for a result string.
     * @throws IOException
     */
    public static void reverse(UTF8StringPointable srcPtr, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        builder.reset(out, srcPtr.getUTF8Length());
        int srcStart = srcPtr.getCharStartOffset();
        int srcEnd = srcPtr.getStartOffset() + srcPtr.getLength() - 1;
        for (int cursorIndex = srcEnd; cursorIndex >= srcStart; cursorIndex--) {
            if (UTF8StringUtil.isCharStart(srcPtr.bytes, cursorIndex)) {
                char ch = UTF8StringUtil.charAt(srcPtr.bytes, cursorIndex);
                int charSize = UTF8StringUtil.charSize(srcPtr.bytes, cursorIndex);

                if (Character.isLowSurrogate(ch)) {
                    while (cursorIndex >= srcStart) {
                        cursorIndex--;
                        if (UTF8StringUtil.isCharStart(srcPtr.bytes, cursorIndex)) {
                            ch = UTF8StringUtil.charAt(srcPtr.bytes, cursorIndex);
                            if (Character.isHighSurrogate(ch) == false) {
                                throw new IllegalArgumentException(
                                        "Decoding Error: no corresponding high surrogate found for the following low surrogate");
                            }

                            charSize += UTF8StringUtil.charSize(srcPtr.bytes, cursorIndex);
                            break;
                        }
                    }
                } else if (Character.isHighSurrogate(ch)) {
                    throw new IllegalArgumentException("Decoding Error: get a high surrogate without low surrogate");
                }

                builder.appendUtf8StringPointable(srcPtr, cursorIndex, charSize);
            }
        }
        builder.finish();
    }

    public boolean findAndReplace(UTF8StringPointable searchPtr, UTF8StringPointable replacePtr, int replaceLimit,
            UTF8StringBuilder builder, GrowableArray out) throws IOException {
        return findAndReplace(this, searchPtr, replacePtr, replaceLimit, builder, out);
    }

    public static boolean findAndReplace(UTF8StringPointable srcPtr, UTF8StringPointable searchPtr,
            UTF8StringPointable replacePtr, int replaceLimit, UTF8StringBuilder builder, GrowableArray out)
            throws IOException {
        if (replaceLimit == 0) {
            return false;
        }
        if (replaceLimit < 0) {
            replaceLimit = Integer.MAX_VALUE;
        }
        int curIdx = find(srcPtr, searchPtr, false);
        if (curIdx < 0) {
            return false;
        }
        int searchUtfLen = searchPtr.getUTF8Length();
        int replaceUtfLen = replacePtr.getUTF8Length();
        int estimatedLen = searchUtfLen > 0 && replaceUtfLen > searchUtfLen
                ? (int) (((long) srcPtr.getUTF8Length()) * replaceUtfLen / searchUtfLen) : srcPtr.getUTF8Length();
        builder.reset(out, estimatedLen);
        builder.appendUtf8StringPointable(srcPtr, srcPtr.getCharStartOffset(), curIdx);
        builder.appendUtf8StringPointable(replacePtr);

        curIdx += searchUtfLen;
        int limit = replaceLimit - 1;

        int nextIdx;
        while (limit > 0 && (nextIdx = find(srcPtr, searchPtr, false, curIdx)) > 0) {
            builder.appendUtf8StringPointable(srcPtr, srcPtr.getCharStartOffset() + curIdx, nextIdx - curIdx);
            builder.appendUtf8StringPointable(replacePtr);
            curIdx = nextIdx + searchUtfLen;
            limit--;
        }
        builder.appendUtf8StringPointable(srcPtr, srcPtr.getCharStartOffset() + curIdx,
                srcPtr.getUTF8Length() - curIdx);

        builder.finish();

        return true;
    }
}
