/*

 * 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.io.ObjectStreamField;

import java.io.UnsupportedEncodingException;

import java.nio.charset.Charset;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Comparator;

import java.util.Formatter;

import java.util.Locale;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

import java.util.regex.PatternSyntaxException;

/**

 * The {@code String} class represents character strings. All

 * string literals in Java programs, such as {@code "abc"}, are

 * implemented as instances of this class.

 * <p>

 * Strings are constant; their values cannot be changed after they

 * are created. String buffers support mutable strings.

 * Because String objects are immutable they can be shared. For example:

 * <p><blockquote><pre>

 *     String str = "abc";

 * </pre></blockquote><p>

 * is equivalent to:

 * <p><blockquote><pre>

 *     char data[] = {'a', 'b', 'c'};

 *     String str = new String(data);

 * </pre></blockquote><p>

 * Here are some more examples of how strings can be used:

 * <p><blockquote><pre>

 *     System.out.println("abc");

 *     String cde = "cde";

 *     System.out.println("abc" + cde);

 *     String c = "abc".substring(2,3);

 *     String d = cde.substring(1, 2);

 * </pre></blockquote>

 * <p>

 * The class {@code String} includes methods for examining

 * individual characters of the sequence, for comparing strings, for

 * searching strings, for extracting substrings, and for creating a

 * copy of a string with all characters translated to uppercase or to

 * lowercase. Case mapping is based on the Unicode Standard version

 * specified by the {@link java.lang.Character Character} class.

 * <p>

 * The Java language provides special support for the string

 * concatenation operator ( + ), and for conversion of

 * other objects to strings. String concatenation is implemented

 * through the {@code StringBuilder}(or {@code StringBuffer})

 * class and its {@code append} method.

 * String conversions are implemented through the method

 * {@code toString}, defined by {@code Object} and

 * inherited by all classes in Java. For additional information on

 * string concatenation and conversion, see Gosling, Joy, and Steele,

 * <i>The Java Language Specification</i>.

 *

 * <p> Unless otherwise noted, passing a <tt>null</tt> argument to a constructor

 * or method in this class will cause a {@link NullPointerException} to be

 * thrown.

 *

 * <p>A {@code String} represents a string in the UTF-16 format

 * in which <em>supplementary characters</em> are represented by <em>surrogate

 * pairs</em> (see the section <a href="Character.html#unicode">Unicode

 * Character Representations</a> in the {@code Character} class for

 * more information).

 * Index values refer to {@code char} code units, so a supplementary

 * character uses two positions in a {@code String}.

 * <p>The {@code String} class provides methods for dealing with

 * Unicode code points (i.e., characters), in addition to those for

 * dealing with Unicode code units (i.e., {@code char} values).

 *

 * @author  Lee Boynton

 * @author  Arthur van Hoff

 * @author  Martin Buchholz

 * @author  Ulf Zibis

 * @see     java.lang.Object#toString()

 * @see     java.lang.StringBuffer

 * @see     java.lang.StringBuilder

 * @see     java.nio.charset.Charset

 * @since   JDK1.0

 */

public final class String

    implements java.io.Serializable, Comparable<String>, CharSequence {

    /** The value is used for character storage. */

    private final char value[];

    /** Cache the hash code for the string */

    private int hash; // Default to 0

    /** use serialVersionUID from JDK 1.0.2 for interoperability */

    private static final long serialVersionUID = -6849794470754667710L;

    /**

     * Class String is special cased within the Serialization Stream Protocol.

     *

     * A String instance is written initially into an ObjectOutputStream in the

     * following format:

     * <pre>

     *      {@code TC_STRING} (utf String)

     * </pre>

     * The String is written by method {@code DataOutput.writeUTF}.

     * A new handle is generated to  refer to all future references to the

     * string instance within the stream.

     */

    private static final ObjectStreamField[] serialPersistentFields =

            new ObjectStreamField[0];

    /**

     * Initializes a newly created {@code String} object so that it represents

     * an empty character sequence.  Note that use of this constructor is

     * unnecessary since Strings are immutable.

     */

    public String() {

        this.value = new char[0];

    }

    /**

     * Initializes a newly created {@code String} object so that it represents

     * the same sequence of characters as the argument; in other words, the

     * newly created string is a copy of the argument string. Unless an

     * explicit copy of {@code original} is needed, use of this constructor is

     * unnecessary since Strings are immutable.

     *

     * @param  original

     *         A {@code String}

     */

    public String(String original) {

        this.value = original.value;

        this.hash = original.hash;

    }

    /**

     * Allocates a new {@code String} so that it represents the sequence of

     * characters currently contained in the character array argument. The

     * contents of the character array are copied; subsequent modification of

     * the character array does not affect the newly created string.

     *

     * @param  value

     *         The initial value of the string

     */

    public String(char value[]) {

        this.value = Arrays.copyOf(value, value.length);

    }

    /**

     * Allocates a new {@code String} that contains characters from a subarray

     * of the character array argument. The {@code offset} argument is the

     * index of the first character of the subarray and the {@code count}

     * argument specifies the length of the subarray. The contents of the

     * subarray are copied; subsequent modification of the character array does

     * not affect the newly created string.

     *

     * @param  value

     *         Array that is the source of characters

     *

     * @param  offset

     *         The initial offset

     *

     * @param  count

     *         The length

     *

     * @throws  IndexOutOfBoundsException

     *          If the {@code offset} and {@code count} arguments index

     *          characters outside the bounds of the {@code value} array

     */

    public String(char value[], int offset, int count) {

        if (offset < 0) {

            throw new StringIndexOutOfBoundsException(offset);

        }

        if (count < 0) {

            throw new StringIndexOutOfBoundsException(count);

        }

        // Note: offset or count might be near -1>>>1.

        if (offset > value.length - count) {

            throw new StringIndexOutOfBoundsException(offset + count);

        }

        this.value = Arrays.copyOfRange(value, offset, offset+count);

    }

    /**

     * Allocates a new {@code String} that contains characters from a subarray

     * of the <a href="Character.html#unicode">Unicode code point</a> array

     * argument.  The {@code offset} argument is the index of the first code

     * point of the subarray and the {@code count} argument specifies the

     * length of the subarray.  The contents of the subarray are converted to

     * {@code char}s; subsequent modification of the {@code int} array does not

     * affect the newly created string.

     *

     * @param  codePoints

     *         Array that is the source of Unicode code points

     *

     * @param  offset

     *         The initial offset

     *

     * @param  count

     *         The length

     *

     * @throws  IllegalArgumentException

     *          If any invalid Unicode code point is found in {@code

     *          codePoints}

     *

     * @throws  IndexOutOfBoundsException

     *          If the {@code offset} and {@code count} arguments index

     *          characters outside the bounds of the {@code codePoints} array

     *

     * @since  1.5

     */

    public String(int[] codePoints, int offset, int count) {

        if (offset < 0) {

            throw new StringIndexOutOfBoundsException(offset);

        }

        if (count < 0) {

            throw new StringIndexOutOfBoundsException(count);

        }

        // Note: offset or count might be near -1>>>1.

        if (offset > codePoints.length - count) {

            throw new StringIndexOutOfBoundsException(offset + count);

        }

        final int end = offset + count;

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

        int n = count;

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

            int c = codePoints[i];

            if (Character.isBmpCodePoint(c))

                continue;

            else if (Character.isValidCodePoint(c))

                n++;

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

        }

        // Pass 2: Allocate and fill in char[]

        final char[] v = new char[n];

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

            int c = codePoints[i];

            if (Character.isBmpCodePoint(c))

                v[j] = (char)c;

            else

                Character.toSurrogates(c, v, j++);

        }

        this.value = v;

    }

    /**

     * Allocates a new {@code String} constructed from a subarray of an array

     * of 8-bit integer values.

     *

     * <p> The {@code offset} argument is the index of the first byte of the

     * subarray, and the {@code count} argument specifies the length of the

     * subarray.

     *

     * <p> Each {@code byte} in the subarray is converted to a {@code char} as

     * specified in the method above.

     *

     * @deprecated This method does not properly convert bytes into characters.

     * As of JDK 1.1, the preferred way to do this is via the

     * {@code String} constructors that take a {@link

     * java.nio.charset.Charset}, charset name, or that use the platform's

     * default charset.

     *

     * @param  ascii

     *         The bytes to be converted to characters

     *

     * @param  hibyte

     *         The top 8 bits of each 16-bit Unicode code unit

     *

     * @param  offset

     *         The initial offset

     * @param  count

     *         The length

     *

     * @throws  IndexOutOfBoundsException

     *          If the {@code offset} or {@code count} argument is invalid

     *

     * @see  #String(byte[], int)

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

     * @see  #String(byte[], int, int, java.nio.charset.Charset)

     * @see  #String(byte[], int, int)

     * @see  #String(byte[], java.lang.String)

     * @see  #String(byte[], java.nio.charset.Charset)

     * @see  #String(byte[])

     */

    @Deprecated

    public String(byte ascii[], int hibyte, int offset, int count) {

        checkBounds(ascii, offset, count);

        char value[] = new char[count];

        if (hibyte == 0) {

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

                value[i] = (char)(ascii[i + offset] & 0xff);

            }

        } else {

            hibyte <<= 8;

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

                value[i] = (char)(hibyte | (ascii[i + offset] & 0xff));

            }

        }

        this.value = value;

    }

    /**

     * Allocates a new {@code String} containing characters constructed from

     * an array of 8-bit integer values. Each character <i>c</i>in the

     * resulting string is constructed from the corresponding component

     * <i>b</i> in the byte array such that:

     *

     * <blockquote><pre>

     *     <b><i>c</i></b> == (char)(((hibyte &amp; 0xff) &lt;&lt; 8)

     *                         | (<b><i>b</i></b> &amp; 0xff))

     * </pre></blockquote>

     *

     * @deprecated  This method does not properly convert bytes into

     * characters.  As of JDK 1.1, the preferred way to do this is via the

     * {@code String} constructors that take a {@link

     * java.nio.charset.Charset}, charset name, or that use the platform's

     * default charset.

     *

     * @param  ascii

     *         The bytes to be converted to characters

     *

     * @param  hibyte

     *         The top 8 bits of each 16-bit Unicode code unit

     *

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

     * @see  #String(byte[], int, int, java.nio.charset.Charset)

     * @see  #String(byte[], int, int)

     * @see  #String(byte[], java.lang.String)

     * @see  #String(byte[], java.nio.charset.Charset)

     * @see  #String(byte[])

     */

    @Deprecated

    public String(byte ascii[], int hibyte) {

        this(ascii, hibyte, 0, ascii.length);

    }

    /* Common private utility method used to bounds check the byte array

     * and requested offset & length values used by the String(byte[],..)

     * constructors.

     */

    private static void checkBounds(byte[] bytes, int offset, int length) {

        if (length < 0)

            throw new StringIndexOutOfBoundsException(length);

        if (offset < 0)

            throw new StringIndexOutOfBoundsException(offset);

        if (offset > bytes.length - length)

            throw new StringIndexOutOfBoundsException(offset + length);

    }

    /**

     * Constructs a new {@code String} by decoding the specified subarray of

     * bytes using the specified charset.  The length of the new {@code String}

     * is a function of the charset, and hence may not be equal to the length

     * of the subarray.

     *

     * <p> The behavior of this constructor when the given bytes are not valid

     * in the given charset is unspecified.  The {@link

     * java.nio.charset.CharsetDecoder} class should be used when more control

     * over the decoding process is required.

     *

     * @param  bytes

     *         The bytes to be decoded into characters

     *

     * @param  offset

     *         The index of the first byte to decode

     *

     * @param  length

     *         The number of bytes to decode

     * @param  charsetName

     *         The name of a supported {@linkplain java.nio.charset.Charset

     *         charset}

     *

     * @throws  UnsupportedEncodingException

     *          If the named charset is not supported

     *

     * @throws  IndexOutOfBoundsException

     *          If the {@code offset} and {@code length} arguments index

     *          characters outside the bounds of the {@code bytes} array

     *

     * @since  JDK1.1

     */

    public String(byte bytes[], int offset, int length, String charsetName)

            throws UnsupportedEncodingException {

        if (charsetName == null)

            throw new NullPointerException("charsetName");

        checkBounds(bytes, offset, length);

        this.value = StringCoding.decode(charsetName, bytes, offset, length);

    }

    /**

     * Constructs a new {@code String} by decoding the specified subarray of

     * bytes using the specified {@linkplain java.nio.charset.Charset charset}.

     * The length of the new {@code String} is a function of the charset, and

     * hence may not be equal to the length of the subarray.

     *

     * <p> This method always replaces malformed-input and unmappable-character

     * sequences with this charset's default replacement string.  The {@link

     * java.nio.charset.CharsetDecoder} class should be used when more control

     * over the decoding process is required.

     *

     * @param  bytes

     *         The bytes to be decoded into characters

     *

     * @param  offset

     *         The index of the first byte to decode

     *

     * @param  length

     *         The number of bytes to decode

     *

     * @param  charset

     *         The {@linkplain java.nio.charset.Charset charset} to be used to

     *         decode the {@code bytes}

     *

     * @throws  IndexOutOfBoundsException

     *          If the {@code offset} and {@code length} arguments index

     *          characters outside the bounds of the {@code bytes} array

     *

     * @since  1.6

     */

    public String(byte bytes[], int offset, int length, Charset charset) {

        if (charset == null)

            throw new NullPointerException("charset");

        checkBounds(bytes, offset, length);

        this.value =  StringCoding.decode(charset, bytes, offset, length);

    }

    /**

     * Constructs a new {@code String} by decoding the specified array of bytes

     * using the specified {@linkplain java.nio.charset.Charset charset}.  The

     * length of the new {@code String} is a function of the charset, and hence

     * may not be equal to the length of the byte array.

     *

     * <p> The behavior of this constructor when the given bytes are not valid

     * in the given charset is unspecified.  The {@link

     * java.nio.charset.CharsetDecoder} class should be used when more control

     * over the decoding process is required.

     *

     * @param  bytes

     *         The bytes to be decoded into characters

     *

     * @param  charsetName

     *         The name of a supported {@linkplain java.nio.charset.Charset

     *         charset}

     *

     * @throws  UnsupportedEncodingException

     *          If the named charset is not supported

     *

     * @since  JDK1.1

     */

    public String(byte bytes[], String charsetName)

            throws UnsupportedEncodingException {

        this(bytes, 0, bytes.length, charsetName);

    }

    /**

     * Constructs a new {@code String} by decoding the specified array of

     * bytes using the specified {@linkplain java.nio.charset.Charset charset}.

     * The length of the new {@code String} is a function of the charset, and

     * hence may not be equal to the length of the byte array.

     *

     * <p> This method always replaces malformed-input and unmappable-character

     * sequences with this charset's default replacement string.  The {@link

     * java.nio.charset.CharsetDecoder} class should be used when more control

     * over the decoding process is required.

     *

     * @param  bytes

     *         The bytes to be decoded into characters

     *

     * @param  charset

     *         The {@linkplain java.nio.charset.Charset charset} to be used to

     *         decode the {@code bytes}

     *

     * @since  1.6

     */

    public String(byte bytes[], Charset charset) {

        this(bytes, 0, bytes.length, charset);

    }

    /**

     * Constructs a new {@code String} by decoding the specified subarray of

     * bytes using the platform's default charset.  The length of the new

     * {@code String} is a function of the charset, and hence may not be equal

     * to the length of the subarray.

     *

     * <p> The behavior of this constructor when the given bytes are not valid

     * in the default charset is unspecified.  The {@link

     * java.nio.charset.CharsetDecoder} class should be used when more control

     * over the decoding process is required.

     *

     * @param  bytes

     *         The bytes to be decoded into characters