/*

  * Copyright (c) 1994, 2010, 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.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</code> class represents character strings. All

  * string literals in Java programs, such as <code>"abc"</code>, 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</code> 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</code>(or <code>StringBuffer</code>)

  * class and its <code>append</code> method.

  * String conversions are implemented through the method

  * <code>toString</code>, defined by <code>Object</code> 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</code> 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</code> class for

  * more information).

  * Index values refer to <code>char</code> code units, so a supplementary

  * character uses two positions in a <code>String</code>.

  * <p>The <code>String</code> 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</code> 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[];

     /** The offset is the first index of the storage that is used. */

     private final int offset;

     /** The count is the number of characters in the String. */

     private final int count;

     /** 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</code> (utf String)

      * </pre>

      * The String is written by method <code>DataOutput.writeUTF</code>.

      * 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.offset = 0;

         this.count = 0;

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

         int size = original.count;

         char[] originalValue = original.value;

         char[] v;

         if (originalValue.length > size) {

             // The array representing the String is bigger than the new

             // String itself.  Perhaps this constructor is being called

             // in order to trim the baggage, so make a copy of the array.

             int off = original.offset;

             v = Arrays.copyOfRange(originalValue, off, off+size);

         } else {

             // The array representing the String is the same

             // size as the String, so no point in making a copy.

             v = originalValue;

         }

         this.offset = 0;

         this.count = size;

         this.value = v;

     }

     /**

      * 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[]) {

         int size = value.length;

         this.offset = 0;

         this.count = size;

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

     }

     /**

      * 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.offset = 0;

         this.count = 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;

         this.count  = n;

         this.offset = 0;

     }

     /**

      * 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.offset = 0;

         this.count = count;

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

         char[] v = StringCoding.decode(charsetName, bytes, offset, length);

         this.offset = 0;

         this.count = v.length;

         this.value = v;

     }

     /**

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

         char[] v = StringCoding.decode(charset, bytes, offset, length);

         this.offset = 0;

         this.count = v.length;

         this.value = v;

     }

     /**

      * 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

      *

      * @param  offset

      *         The index of the first byte to decode

      *

      * @param  length

      *         The number of bytes to decode

      *

      * @throws  IndexOutOfBoundsException

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

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

      *

      * @since  JDK1.1

      */

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

         checkBounds(bytes, offset, length);

         char[] v  = StringCoding.decode(bytes, offset, length);

         this.offset = 0;

         this.count = v.length;

         this.value = v;

     }

     /**

      * Constructs a new {@code String} by decoding the specified array 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 byte array.

      *

      * <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

      *

      * @since  JDK1.1

      */

     public String(byte bytes[]) {

         this(bytes, 0, bytes.length);

     }

     /**

      * Allocates a new string that contains the sequence of characters

      * currently contained in the string buffer argument. The contents of the

      * string buffer are copied; subsequent modification of the string buffer

      * does not affect the newly created string.

      *

      * @param  buffer

      *         A {@code StringBuffer}

      */

     public String(StringBuffer buffer) {

         String result = buffer.toString();

         this.value = result.value;

         this.count = result.count;

         this.offset = result.offset;

     }

     /**

      * Allocates a new string that contains the sequence of characters

      * currently contained in the string builder argument. The contents of the

      * string builder are copied; subsequent modification of the string builder

      * does not affect the newly created string.

      *

      * <p> This constructor is provided to ease migration to {@code

      * StringBuilder}. Obtaining a string from a string builder via the {@code

      * toString} method is likely to run faster and is generally preferred.

      *

      * @param   builder

      *          A {@code StringBuilder}

      *

      * @since  1.5

      */

     public String(StringBuilder builder) {

         String result = builder.toString();

         this.value = result.value;

         this.count = result.count;

         this.offset = result.offset;

     }

     // Package private constructor which shares value array for speed.

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

         this.value = value;

         this.offset = offset;

         this.count = count;

     }

     /**

      * Returns the length of this string.

      * The length is equal to the number of <a href="Character.html#unicode">Unicode

      * code units</a> in the string.

      *

      * @return  the length of the sequence of characters represented by this

      *          object.

      */

     public int length() {

         return count;

     }

     /**

      * Returns <tt>true</tt> if, and only if, {@link #length()} is <tt>0</tt>.

      *

      * @return <tt>true</tt> if {@link #length()} is <tt>0</tt>, otherwise

      * <tt>false</tt>

      *

      * @since 1.6

      */

     public boolean isEmpty() {

         return count == 0;

     }

     /**

      * Returns the <code>char</code> value at the

      * specified index. An index ranges from <code>0</code> to

      * <code>length() - 1</code>. The first <code>char</code> value of the sequence

      * is at index <code>0</code>, the next at index <code>1</code>,

      * and so on, as for array indexing.

      *

      * <p>If the <code>char</code> value specified by the index is a

      * <a href="Character.html#unicode">surrogate</a>, the surrogate

      * value is returned.

      *

      * @param      index   the index of the <code>char</code> value.

      * @return     the <code>char</code> value at the specified index of this string.

      *             The first <code>char</code> value is at index <code>0</code>.

      * @exception  IndexOutOfBoundsException  if the <code>index</code>

      *             argument is negative or not less than the length of this

      *             string.

      */

     public char charAt(int index) {

         if ((index < 0) || (index >= count)) {

             throw new StringIndexOutOfBoundsException(index);

         }

         return value[index + offset];

     }

     /**

      * Returns the character (Unicode code point) at the specified

      * index. The index refers to <code>char</code> values

      * (Unicode code units) and ranges from <code>0</code> to

      * {@link #length()}<code> - 1</code>.

      *

      * <p> If the <code>char</code> value specified at the given index

      * is in the high-surrogate range, the following index is less

      * than the length of this <code>String</code>, and the

      * <code>char</code> value at the following index is in the

      * low-surrogate range, then the supplementary code point

      * corresponding to this surrogate pair is returned. Otherwise,

      * the <code>char</code> value at the given index is returned.

      *

      * @param      index the index to the <code>char</code> values

      * @return     the code point value of the character at the

      *             <code>index</code>

      * @exception  IndexOutOfBoundsException  if the <code>index</code>

      *             argument is negative or not less than the length of this

      *             string.

      * @since      1.5

      */

     public int codePointAt(int index) {

         if ((index < 0) || (index >= count)) {

             throw new StringIndexOutOfBoundsException(index);

         }

         return Character.codePointAtImpl(value, offset + index, offset + count);

     }

     /**

      * Returns the character (Unicode code point) before the specified

      * index. The index refers to <code>char</code> values

      * (Unicode code units) and ranges from <code>1</code> to {@link

      * CharSequence#length() length}.

      *

      * <p> If the <code>char</code> value at <code>(index - 1)</code>

      * is in the low-surrogate range, <code>(index - 2)</code> is not

      * negative, and the <code>char</code> value at <code>(index -

      * 2)</code> is in the high-surrogate range, then the

      * supplementary code point value of the surrogate pair is

      * returned. If the <code>char</code> value at <code>index -

      * 1</code> is an unpaired low-surrogate or a high-surrogate, the

      * surrogate value is returned.

      *

      * @param     index the index following the code point that should be returned

      * @return    the Unicode code point value before the given index.

      * @exception IndexOutOfBoundsException if the <code>index</code>

      *            argument is less than 1 or greater than the length

      *            of this string.

      * @since     1.5

      */

     public int codePointBefore(int index) {

         int i = index - 1;

         if ((i < 0) || (i >= count)) {

             throw new StringIndexOutOfBoundsException(index);

         }

         return Character.codePointBeforeImpl(value, offset + index, offset);

     }

     /**

      * Returns the number of Unicode code points in the specified text

      * range of this <code>String</code>. The text range begins at the

      * specified <code>beginIndex</code> and extends to the

      * <code>char</code> at index <code>endIndex - 1</code>. Thus the

      * length (in <code>char</code>s) of the text range is

      * <code>endIndex-beginIndex</code>. Unpaired surrogates within

      * the text range count as one code point each.

      *

      * @param beginIndex the index to the first <code>char</code> of

      * the text range.

      * @param endIndex the index after the last <code>char</code> of

      * the text range.

      * @return the number of Unicode code points in the specified text

      * range

      * @exception IndexOutOfBoundsException if the

      * <code>beginIndex</code> is negative, or <code>endIndex</code>

      * is larger than the length of this <code>String</code>, or

      * <code>beginIndex</code> is larger than <code>endIndex</code>.

      * @since  1.5

      */

     public int codePointCount(int beginIndex, int endIndex) {

         if (beginIndex < 0 || endIndex > count || beginIndex > endIndex) {

             throw new IndexOutOfBoundsException();

         }

         return Character.codePointCountImpl(value, offset+beginIndex, endIndex-beginIndex);

     }

     /**

      * Returns the index within this <code>String</code> that is

      * offset from the given <code>index</code> by

      * <code>codePointOffset</code> code points. Unpaired surrogates

      * within the text range given by <code>index</code> and

      * <code>codePointOffset</code> count as one code point each.

      *

      * @param index the index to be offset

      * @param codePointOffset the offset in code points

      * @return the index within this <code>String</code>

      * @exception IndexOutOfBoundsException if <code>index</code>

      *   is negative or larger then the length of this

      *   <code>String</code>, or if <code>codePointOffset</code> is positive

      *   and the substring starting with <code>index</code> has fewer

      *   than <code>codePointOffset</code> code points,

      *   or if <code>codePointOffset</code> is negative and the substring

      *   before <code>index</code> has fewer than the absolute value

      *   of <code>codePointOffset</code> code points.

      * @since 1.5

      */

     public int offsetByCodePoints(int index, int codePointOffset) {

         if (index < 0 || index > count) {

             throw new IndexOutOfBoundsException();

         }

         return Character.offsetByCodePointsImpl(value, offset, count,

                                                 offset+index, codePointOffset) - offset;

     }

     /**

      * Copy characters from this string into dst starting at dstBegin.

      * This method doesn't perform any range checking.

      */

     void getChars(char dst[], int dstBegin) {

         System.arraycopy(value, offset, dst, dstBegin, count);

     }

     /**

      * Copies characters from this string into the destination character

      * array.

      * <p>

      * The first character to be copied is at index <code>srcBegin</code>;

      * the last character to be copied is at index <code>srcEnd-1</code>

      * (thus the total number of characters to be copied is

      * <code>srcEnd-srcBegin</code>). The characters are copied into the

      * subarray of <code>dst</code> starting at index <code>dstBegin</code>

      * and ending at index:

      * <p><blockquote><pre>

      *     dstbegin + (srcEnd-srcBegin) - 1

      * </pre></blockquote>

      *

      * @param      srcBegin   index of the first character in the string

      *                        to copy.

      * @param      srcEnd     index after the last character in the string

      *                        to copy.

      * @param      dst        the destination array.

      * @param      dstBegin   the start offset in the destination array.

      * @exception IndexOutOfBoundsException If any of the following

      *            is true:

      *            <ul><li><code>srcBegin</code> is negative.

      *            <li><code>srcBegin</code> is greater than <code>srcEnd</code>

      *            <li><code>srcEnd</code> is greater than the length of this

      *                string

      *            <li><code>dstBegin</code> is negative

      *            <li><code>dstBegin+(srcEnd-srcBegin)</code> is larger than

      *                <code>dst.length</code></ul>

      */

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

         if (srcBegin < 0) {

             throw new StringIndexOutOfBoundsException(srcBegin);

         }

         if (srcEnd > count) {

             throw new StringIndexOutOfBoundsException(srcEnd);

         }

         if (srcBegin > srcEnd) {

             throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);

         }

         System.arraycopy(value, offset + srcBegin, dst, dstBegin,

              srcEnd - srcBegin);

     }

     /**

      * Copies characters from this string into the destination byte array. Each

      * byte receives the 8 low-order bits of the corresponding character. The

      * eight high-order bits of each character are not copied and do not

      * participate in the transfer in any way.

      *

      * <p> The first character to be copied is at index {@code srcBegin}; the

      * last character to be copied is at index {@code srcEnd-1}.  The total

      * number of characters to be copied is {@code srcEnd-srcBegin}. The

      * characters, converted to bytes, are copied into the subarray of {@code

      * dst} starting at index {@code dstBegin} and ending at index:

      *

      * <blockquote><pre>

      *     dstbegin + (srcEnd-srcBegin) - 1

      * </pre></blockquote>

      *

      * @deprecated  This method does not properly convert characters into

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

      * {@link #getBytes()} method, which uses the platform's default charset.

      *

      * @param  srcBegin

      *         Index of the first character in the string to copy

      *

      * @param  srcEnd

      *         Index after the last character in the string to copy

      *

      * @param  dst

      *         The destination array

      *

      * @param  dstBegin

      *         The start offset in the destination array

      *

      * @throws  IndexOutOfBoundsException

      *          If any of the following is true:

      *          <ul>

      *            <li> {@code srcBegin} is negative

      *            <li> {@code srcBegin} is greater than {@code srcEnd}

      *            <li> {@code srcEnd} is greater than the length of this String

      *            <li> {@code dstBegin} is negative

      *            <li> {@code dstBegin+(srcEnd-srcBegin)} is larger than {@code

      *                 dst.length}

      *          </ul>

      */

     @Deprecated

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

         if (srcBegin < 0) {

             throw new StringIndexOutOfBoundsException(srcBegin);

         }

         if (srcEnd > count) {

             throw new StringIndexOutOfBoundsException(srcEnd);

         }

         if (srcBegin > srcEnd) {

             throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);

         }

         int j = dstBegin;

         int n = offset + srcEnd;

         int i = offset + srcBegin;

         char[] val = value;   /* avoid getfield opcode */

         while (i < n) {

             dst[j++] = (byte)val[i++];

         }

     }

     /**

      * Encodes this {@code String} into a sequence of bytes using the named

      * charset, storing the result into a new byte array.

      *

      * <p> The behavior of this method when this string cannot be encoded in

      * the given charset is unspecified.  The {@link

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

      * over the encoding process is required.

      *

      * @param  charsetName

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

      *         charset}

      *

      * @return  The resultant byte array

      *

      * @throws  UnsupportedEncodingException

      *          If the named charset is not supported

      *

      * @since  JDK1.1

      */

     public byte[] getBytes(String charsetName)

         throws UnsupportedEncodingException

     {

         if (charsetName == null) throw new NullPointerException();

         return StringCoding.encode(charsetName, value, offset, count);

     }

     /**

      * Encodes this {@code String} into a sequence of bytes using the given

      * {@linkplain java.nio.charset.Charset charset}, storing the result into a

      * new byte array.

      *

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

      * sequences with this charset's default replacement byte array.  The

      * {@link java.nio.charset.CharsetEncoder} class should be used when more

      * control over the encoding process is required.

      *

      * @param  charset

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

      *         the {@code String}

      *

      * @return  The resultant byte array

      *

      * @since  1.6

      */

     public byte[] getBytes(Charset charset) {

         if (charset == null) throw new NullPointerException();

         return StringCoding.encode(charset, value, offset, count);

     }

     /**

      * Encodes this {@code String} into a sequence of bytes using the

      * platform's default charset, storing the result into a new byte array.

      *

      * <p> The behavior of this method when this string cannot be encoded in

      * the default charset is unspecified.  The {@link

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

      * over the encoding process is required.

      *

      * @return  The resultant byte array

      *

      * @since      JDK1.1

      */

     public byte[] getBytes() {

         return StringCoding.encode(value, offset, count);

     }

     /**

      * Compares this string to the specified object.  The result is {@code

      * true} if and only if the argument is not {@code null} and is a {@code

      * String} object that represents the same sequence of characters as this

      * object.

      *

      * @param  anObject

      *         The object to compare this {@code String} against

      *

      * @return  {@code true} if the given object represents a {@code String}

      *          equivalent to this string, {@code false} otherwise

      *

      * @see  #compareTo(String)

      * @see  #equalsIgnoreCase(String)

      */

     public boolean equals(Object anObject) {

         if (this == anObject) {

             return true;

         }

         if (anObject instanceof String) {

             String anotherString = (String)anObject;

             int n = count;

             if (n == anotherString.count) {

                 char v1[] = value;

                 char v2[] = anotherString.value;

                 int i = offset;

                 int j = anotherString.offset;

                 while (n-- != 0) {

                     if (v1[i++] != v2[j++])

                         return false;

                 }

                 return true;

             }

         }

         return false;

     }

     /**

      * Compares this string to the specified {@code StringBuffer}.  The result

      * is {@code true} if and only if this {@code String} represents the same

      * sequence of characters as the specified {@code StringBuffer}.

      *

      * @param  sb

      *         The {@code StringBuffer} to compare this {@code String} against

      *

      * @return  {@code true} if this {@code String} represents the same

      *          sequence of characters as the specified {@code StringBuffer},

      *          {@code false} otherwise

      *

      * @since  1.4

      */

     public boolean contentEquals(StringBuffer sb) {

         synchronized(sb) {

             return contentEquals((CharSequence)sb);

         }

     }

     /**

      * Compares this string to the specified {@code CharSequence}.  The result

      * is {@code true} if and only if this {@code String} represents the same

      * sequence of char values as the specified sequence.

      *

      * @param  cs

      *         The sequence to compare this {@code String} against

      *

      * @return  {@code true} if this {@code String} represents the same

      *          sequence of char values as the specified sequence, {@code

      *          false} otherwise

      *

      * @since  1.5

      */

     public boolean contentEquals(CharSequence cs) {

         if (count != cs.length())

             return false;

         // Argument is a StringBuffer, StringBuilder

         if (cs instanceof AbstractStringBuilder) {

             char v1[] = value;

             char v2[] = ((AbstractStringBuilder)cs).getValue();

             int i = offset;

             int j = 0;

             int n = count;

             while (n-- != 0) {

                 if (v1[i++] != v2[j++])

                     return false;

             }

             return true;

         }

         // Argument is a String

         if (cs.equals(this))

             return true;

         // Argument is a generic CharSequence

         char v1[] = value;

         int i = offset;

         int j = 0;

         int n = count;

         while (n-- != 0) {

             if (v1[i++] != cs.charAt(j++))

                 return false;

         }

         return true;

     }

     /**

      * Compares this {@code String} to another {@code String}, ignoring case

      * considerations.  Two strings are considered equal ignoring case if they

      * are of the same length and corresponding characters in the two strings

      * are equal ignoring case.

      *

      * <p> Two characters {@code c1} and {@code c2} are considered the same

      * ignoring case if at least one of the following is true:

      * <ul>

      *   <li> The two characters are the same (as compared by the

      *        {@code ==} operator)

      *   <li> Applying the method {@link

      *        java.lang.Character#toUpperCase(char)} to each character

      *        produces the same result

      *   <li> Applying the method {@link

      *        java.lang.Character#toLowerCase(char)} to each character

      *        produces the same result

      * </ul>

      *

      * @param  anotherString

      *         The {@code String} to compare this {@code String} against

      *

      * @return  {@code true} if the argument is not {@code null} and it

      *          represents an equivalent {@code String} ignoring case; {@code

      *          false} otherwise

      *

      * @see  #equals(Object)

      */

     public boolean equalsIgnoreCase(String anotherString) {

         return (this == anotherString) ? true :

                (anotherString != null) && (anotherString.count == count) &&

                regionMatches(true, 0, anotherString, 0, count);

     }

     /**

      * Compares two strings lexicographically.

      * The comparison is based on the Unicode value of each character in

      * the strings. The character sequence represented by this

      * <code>String</code> object is compared lexicographically to the

      * character sequence represented by the argument string. The result is

      * a negative integer if this <code>String</code> object

      * lexicographically precedes the argument string. The result is a

      * positive integer if this <code>String</code> object lexicographically

      * follows the argument string. The result is zero if the strings

      * are equal; <code>compareTo</code> returns <code>0</code> exactly when

      * the {@link #equals(Object)} method would return <code>true</code>.

      * <p>

      * This is the definition of lexicographic ordering. If two strings are

      * different, then either they have different characters at some index

      * that is a valid index for both strings, or their lengths are different,

      * or both. If they have different characters at one or more index

      * positions, let <i>k</i> be the smallest such index; then the string

      * whose character at position <i>k</i> has the smaller value, as

      * determined by using the < operator, lexicographically precedes the

      * other string. In this case, <code>compareTo</code> returns the

      * difference of the two character values at position <code>k</code> in

      * the two string -- that is, the value:

      * <blockquote><pre>

      * this.charAt(k)-anotherString.charAt(k)

      * </pre></blockquote>

      * If there is no index position at which they differ, then the shorter

      * string lexicographically precedes the longer string. In this case,

      * <code>compareTo</code> returns the difference of the lengths of the

      * strings -- that is, the value:

      * <blockquote><pre>

      * this.length()-anotherString.length()

      * </pre></blockquote>

      *

      * @param   anotherString   the <code>String</code> to be compared.

      * @return  the value <code>0</code> if the argument string is equal to

      *          this string; a value less than <code>0</code> if this string

      *          is lexicographically less than the string argument; and a

      *          value greater than <code>0</code> if this string is

      *          lexicographically greater than the string argument.

      */

     public int compareTo(String anotherString) {

         int len1 = count;

         int len2 = anotherString.count;

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

         char v1[] = value;

         char v2[] = anotherString.value;

         int i = offset;

         int j = anotherString.offset;

         if (i == j) {

             int k = i;

             int lim = n + i;

             while (k < lim) {

                 char c1 = v1[k];

                 char c2 = v2[k];

                 if (c1 != c2) {

                     return c1 - c2;

                 }

                 k++;

             }

         } else {

             while (n-- != 0) {

                 char c1 = v1[i++];

                 char c2 = v2[j++];

                 if (c1 != c2) {

                     return c1 - c2;

                 }

             }

         }

         return len1 - len2;

     }

     /**

      * A Comparator that orders <code>String</code> objects as by

      * <code>compareToIgnoreCase</code>. This comparator is serializable.

      * <p>

      * Note that this Comparator does <em>not</em> take locale into account,

      * and will result in an unsatisfactory ordering for certain locales.

      * The java.text package provides <em>Collators</em> to allow

      * locale-sensitive ordering.

      *

      * @see     java.text.Collator#compare(String, String)

      * @since   1.2

      */

     public static final Comparator<String> CASE_INSENSITIVE_ORDER

                                          = new CaseInsensitiveComparator();

     private static class CaseInsensitiveComparator

                          implements Comparator<String>, java.io.Serializable {

         // use serialVersionUID from JDK 1.2.2 for interoperability

         private static final long serialVersionUID = 8575799808933029326L;

         public int compare(String s1, String s2) {

             int n1 = s1.length();

             int n2 = s2.length();

             int min = Math.min(n1, n2);

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

                 char c1 = s1.charAt(i);

                 char c2 = s2.charAt(i);

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

                             // No overflow because of numeric promotion

                             return c1 - c2;

                         }

                     }

                 }

             }

             return n1 - n2;

         }

     }

     /**

      * Compares two strings lexicographically, ignoring case

      * differences. This method returns an integer whose sign is that of

      * calling <code>compareTo</code> with normalized versions of the strings

      * where case differences have been eliminated by calling

      * <code>Character.toLowerCase(Character.toUpperCase(character))</code> on

      * each character.

      * <p>

      * Note that this method does <em>not</em> take locale into account,

      * and will result in an unsatisfactory ordering for certain locales.

      * The java.text package provides <em>collators</em> to allow

      * locale-sensitive ordering.

      *

      * @param   str   the <code>String</code> to be compared.

      * @return  a negative integer, zero, or a positive integer as the

      *          specified String is greater than, equal to, or less

      *          than this String, ignoring case considerations.

      * @see     java.text.Collator#compare(String, String)

      * @since   1.2

      */

     public int compareToIgnoreCase(String str) {

         return CASE_INSENSITIVE_ORDER.compare(this, str);

     }

     /**

      * Tests if two string regions are equal.

      * <p>

      * A substring of this <tt>String</tt> object is compared to a substring

      * of the argument other. The result is true if these substrings

      * represent identical character sequences. The substring of this

      * <tt>String</tt> object to be compared begins at index <tt>toffset</tt>

      * and has length <tt>len</tt>. The substring of other to be compared

      * begins at index <tt>ooffset</tt> and has length <tt>len</tt>. The

      * result is <tt>false</tt> if and only if at least one of the following

      * is true:

      * <ul><li><tt>toffset</tt> is negative.

      * <li><tt>ooffset</tt> is negative.

      * <li><tt>toffset+len</tt> is greater than the length of this

      * <tt>String</tt> object.

      * <li><tt>ooffset+len</tt> is greater than the length of the other

      * argument.

      * <li>There is some nonnegative integer <i>k</i> less than <tt>len</tt>

      * such that:

      * <tt>this.charAt(toffset+<i>k</i>)&nbsp;!=&nbsp;other.charAt(ooffset+<i>k</i>)</tt>

      * </ul>

      *

      * @param   toffset   the starting offset of the subregion in this string.

      * @param   other     the string argument.

      * @param   ooffset   the starting offset of the subregion in the string

      *                    argument.

      * @param   len       the number of characters to compare.

      * @return  <code>true</code> if the specified subregion of this string

      *          exactly matches the specified subregion of the string argument;

      *          <code>false</code> otherwise.

      */

     public boolean regionMatches(int toffset, String other, int ooffset,

                                  int len) {

         char ta[] = value;

         int to = offset + toffset;

         char pa[] = other.value;

         int po = other.offset + ooffset;

         // Note: toffset, ooffset, or len might be near -1>>>1.

         if ((ooffset < 0) || (toffset < 0) || (toffset > (long)count - len)

             || (ooffset > (long)other.count - len)) {

             return false;

         }

         while (len-- > 0) {

             if (ta[to++] != pa[po++]) {

                 return false;

             }

         }

         return true;

     }

     /**

      * Tests if two string regions are equal.

      * <p>

      * A substring of this <tt>String</tt> object is compared to a substring

      * of the argument <tt>other</tt>. The result is <tt>true</tt> if these

      * substrings represent character sequences that are the same, ignoring

      * case if and only if <tt>ignoreCase</tt> is true. The substring of

      * this <tt>String</tt> object to be compared begins at index

      * <tt>toffset</tt> and has length <tt>len</tt>. The substring of

      * <tt>other</tt> to be compared begins at index <tt>ooffset</tt> and

      * has length <tt>len</tt>. The result is <tt>false</tt> if and only if

      * at least one of the following is true:

      * <ul><li><tt>toffset</tt> is negative.

      * <li><tt>ooffset</tt> is negative.

      * <li><tt>toffset+len</tt> is greater than the length of this

      * <tt>String</tt> object.

      * <li><tt>ooffset+len</tt> is greater than the length of the other

      * argument.

      * <li><tt>ignoreCase</tt> is <tt>false</tt> and there is some nonnegative

      * integer <i>k</i> less than <tt>len</tt> such that:

      * <blockquote><pre>

      * this.charAt(toffset+k) != other.charAt(ooffset+k)

      * </pre></blockquote>

      * <li><tt>ignoreCase</tt> is <tt>true</tt> and there is some nonnegative

      * integer <i>k</i> less than <tt>len</tt> such that:

      * <blockquote><pre>

      * Character.toLowerCase(this.charAt(toffset+k)) !=

                Character.toLowerCase(other.charAt(ooffset+k))

      * </pre></blockquote>

      * and:

      * <blockquote><pre>

      * Character.toUpperCase(this.charAt(toffset+k)) !=

      *         Character.toUpperCase(other.charAt(ooffset+k))

      * </pre></blockquote>

      * </ul>

      *

      * @param   ignoreCase   if <code>true</code>, ignore case when comparing

      *                       characters.

      * @param   toffset      the starting offset of the subregion in this

      *                       string.

      * @param   other        the string argument.

      * @param   ooffset      the starting offset of the subregion in the string

      *                       argument.

      * @param   len          the number of characters to compare.

      * @return  <code>true</code> if the specified subregion of this string

      *          matches the specified subregion of the string argument;

      *          <code>false</code> otherwise. Whether the matching is exact

      *          or case insensitive depends on the <code>ignoreCase</code>

      *          argument.

      */

     public boolean regionMatches(boolean ignoreCase, int toffset,

                            String other, int ooffset, int len) {

         char ta[] = value;

         int to = offset + toffset;

         char pa[] = other.value;

         int po = other.offset + ooffset;

         // Note: toffset, ooffset, or len might be near -1>>>1.

         if ((ooffset < 0) || (toffset < 0) || (toffset > (long)count - len) ||

                 (ooffset > (long)other.count - len)) {

             return false;

         }

         while (len-- > 0) {

             char c1 = ta[to++];

             char c2 = pa[po++];

             if (c1 == c2) {

                 continue;

             }

             if (ignoreCase) {

                 // If characters don't match but case may be ignored,

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

                     continue;

                 }

                 // Unfortunately, conversion to uppercase does not work properly

                 // for the Georgian alphabet, which has strange rules about case

                 // conversion.  So we need to make one last check before

                 // exiting.

                 if (Character.toLowerCase(u1) == Character.toLowerCase(u2)) {

                     continue;

                 }

             }

             return false;

         }

         return true;

     }

     /**

      * Tests if the substring of this string beginning at the

      * specified index starts with the specified prefix.

      *

      * @param   prefix    the prefix.

      * @param   toffset   where to begin looking in this string.

      * @return  <code>true</code> if the character sequence represented by the

      *          argument is a prefix of the substring of this object starting

      *          at index <code>toffset</code>; <code>false</code> otherwise.

      *          The result is <code>false</code> if <code>toffset</code> is

      *          negative or greater than the length of this

      *          <code>String</code> object; otherwise the result is the same

      *          as the result of the expression

      *          <pre>

      *          this.substring(toffset).startsWith(prefix)

      *          </pre>

      */

     public boolean startsWith(String prefix, int toffset) {

         char ta[] = value;

         int to = offset + toffset;

         char pa[] = prefix.value;

         int po = prefix.offset;

         int pc = prefix.count;

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

         if ((toffset < 0) || (toffset > count - pc)) {

             return false;

         }

         while (--pc >= 0) {

             if (ta[to++] != pa[po++]) {

                 return false;

             }

         }

         return true;

     }

     /**

      * Tests if this string starts with the specified prefix.

      *

      * @param   prefix   the prefix.

      * @return  <code>true</code> if the character sequence represented by the

      *          argument is a prefix of the character sequence represented by

      *          this string; <code>false</code> otherwise.

      *          Note also that <code>true</code> will be returned if the

      *          argument is an empty string or is equal to this

      *          <code>String</code> object as determined by the

      *          {@link #equals(Object)} method.

      * @since   1. 0

      */

     public boolean startsWith(String prefix) {

         return startsWith(prefix, 0);

     }

     /**

      * Tests if this string ends with the specified suffix.

      *

      * @param   suffix   the suffix.

      * @return  <code>true</code> if the character sequence represented by the

      *          argument is a suffix of the character sequence represented by

      *          this object; <code>false</code> otherwise. Note that the

      *          result will be <code>true</code> if the argument is the

      *          empty string or is equal to this <code>String</code> object

      *          as determined by the {@link #equals(Object)} method.

      */

     public boolean endsWith(String suffix) {

         return startsWith(suffix, count - suffix.count);

     }

     /**

      * Returns a hash code for this string. The hash code for a

      * <code>String</code> object is computed as

      * <blockquote><pre>

      * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

      * </pre></blockquote>

      * using <code>int</code> arithmetic, where <code>s[i]</code> is the

      * <i>i</i>th character of the string, <code>n</code> is the length of

      * the string, and <code>^</code> indicates exponentiation.

      * (The hash value of the empty string is zero.)

      *

      * @return  a hash code value for this object.

      */

     public int hashCode() {

         int h = hash;

         if (h == 0 && count > 0) {

             int off = offset;

             char val[] = value;

             int len = count;

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

                 h = 31*h + val[off++];

             }

             hash = h;

         }

         return h;

     }

     /**

      * Returns the index within this string of the first occurrence of

      * the specified character. If a character with value

      * <code>ch</code> occurs in the character sequence represented by

      * this <code>String</code> object, then the index (in Unicode

      * code units) of the first such occurrence is returned. For

      * values of <code>ch</code> in the range from 0 to 0xFFFF

      * (inclusive), this is the smallest value <i>k</i> such that:

      * <blockquote><pre>

      * this.charAt(<i>k</i>) == ch

      * </pre></blockquote>

      * is true. For other values of <code>ch</code>, it is the

      * smallest value <i>k</i> such that:

      * <blockquote><pre>

      * this.codePointAt(<i>k</i>) == ch

      * </pre></blockquote>

      * is true. In either case, if no such character occurs in this

      * string, then <code>-1</code> is returned.

      *

      * @param   ch   a character (Unicode code point).

      * @return  the index of the first occurrence of the character in the

      *          character sequence represented by this object, or

      *          <code>-1</code> if the character does not occur.

      */

     public int indexOf(int ch) {

         return indexOf(ch, 0);

     }

     /**

      * Returns the index within this string of the first occurrence of the

      * specified character, starting the search at the specified index.

      * <p>

      * If a character with value <code>ch</code> occurs in the

      * character sequence represented by this <code>String</code>

      * object at an index no smaller than <code>fromIndex</code>, then

      * the index of the first such occurrence is returned. For values

      * of <code>ch</code> in the range from 0 to 0xFFFF (inclusive),

      * this is the smallest value <i>k</i> such that:

      * <blockquote><pre>

      * (this.charAt(<i>k</i>) == ch) && (<i>k</i> &gt;= fromIndex)

      * </pre></blockquote>

      * is true. For other values of <code>ch</code>, it is the

      * smallest value <i>k</i> such that:

      * <blockquote><pre>

      * (this.codePointAt(<i>k</i>) == ch) && (<i>k</i> &gt;= fromIndex)

      * </pre></blockquote>

      * is true. In either case, if no such character occurs in this

      * string at or after position <code>fromIndex</code>, then

      * <code>-1</code> is returned.

      *

      * <p>

      * There is no restriction on the value of <code>fromIndex</code>. If it

      * is negative, it has the same effect as if it were zero: this entire

      * string may be searched. If it is greater than the length of this

      * string, it has the same effect as if it were equal to the length of

      * this string: <code>-1</code> is returned.

      *

      * <p>All indices are specified in <code>char</code> values

      * (Unicode code units).

      *

      * @param   ch          a character (Unicode code point).

      * @param   fromIndex   the index to start the search from.

      * @return  the index of the first occurrence of the character in the

      *          character sequence represented by this object that is greater

      *          than or equal to <code>fromIndex</code>, or <code>-1</code>

      *          if the character does not occur.

      */

     public int indexOf(int ch, int fromIndex) {

         if (fromIndex < 0) {

             fromIndex = 0;

         } else if (fromIndex >= count) {

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

             final char[] value = this.value;

             final int offset = this.offset;

             final int max = offset + count;

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

                 if (value[i] == ch) {

                     return i - offset;

                 }

             }

             return -1;

         } else {

             return indexOfSupplementary(ch, fromIndex);

         }

     }

     /**

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

      */

     private int indexOfSupplementary(int ch, int fromIndex) {

         if (Character.isValidCodePoint(ch)) {

             final char[] value = this.value;

             final int offset = this.offset;

             final char hi = Character.highSurrogate(ch);

             final char lo = Character.lowSurrogate(ch);

             final int max = offset + count - 1;

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

                 if (value[i] == hi && value[i+1] == lo) {

                     return i - offset;

                 }

             }

         }

         return -1;

     }

     /**

      * Returns the index within this string of the last occurrence of

      * the specified character. For values of <code>ch</code> in the

      * range from 0 to 0xFFFF (inclusive), the index (in Unicode code

      * units) returned is the largest value <i>k</i> such that:

      * <blockquote><pre>

      * this.charAt(<i>k</i>) == ch

      * </pre></blockquote>

      * is true. For other values of <code>ch</code>, it is the

      * largest value <i>k</i> such that:

      * <blockquote><pre>

      * this.codePointAt(<i>k</i>) == ch

      * </pre></blockquote>

      * is true.  In either case, if no such character occurs in this

      * string, then <code>-1</code> is returned.  The

      * <code>String</code> is searched backwards starting at the last

      * character.

      *

      * @param   ch   a character (Unicode code point).

      * @return  the index of the last occurrence of the character in the

      *          character sequence represented by this object, or

      *          <code>-1</code> if the character does not occur.

      */

     public int lastIndexOf(int ch) {

         return lastIndexOf(ch, count - 1);

     }

     /**

      * Returns the index within this string of the last occurrence of

      * the specified character, searching backward starting at the

      * specified index. For values of <code>ch</code> in the range

      * from 0 to 0xFFFF (inclusive), the index returned is the largest

      * value <i>k</i> such that:

      * <blockquote><pre>

      * (this.charAt(<i>k</i>) == ch) && (<i>k</i> &lt;= fromIndex)

      * </pre></blockquote>

      * is true. For other values of <code>ch</code>, it is the

      * largest value <i>k</i> such that:

      * <blockquote><pre>

      * (this.codePointAt(<i>k</i>) == ch) && (<i>k</i> &lt;= fromIndex)

      * </pre></blockquote>

      * is true. In either case, if no such character occurs in this

      * string at or before position <code>fromIndex</code>, then

      * <code>-1</code> is returned.

      *

      * <p>All indices are specified in <code>char</code> values

      * (Unicode code units).

      *

      * @param   ch          a character (Unicode code point).

      * @param   fromIndex   the index to start the search from. There is no

      *          restriction on the value of <code>fromIndex</code>. If it is

      *          greater than or equal to the length of this string, it has

      *          the same effect as if it were equal to one less than the

      *          length of this string: this entire string may be searched.

      *          If it is negative, it has the same effect as if it were -1:

      *          -1 is returned.

      * @return  the index of the last occurrence of the character in the

      *          character sequence represented by this object that is less

      *          than or equal to <code>fromIndex</code>, or <code>-1</code>

      *          if the character does not occur before that point.

      */

     public int lastIndexOf(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))

             final char[] value = this.value;

             final int offset = this.offset;

             int i = offset + Math.min(fromIndex, count - 1);

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

                 if (value[i] == ch) {

                     return i - offset;

                 }

             }

             return -1;

         } else {

             return lastIndexOfSupplementary(ch, fromIndex);

         }

     }

     /**

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

      */

     private int lastIndexOfSupplementary(int ch, int fromIndex) {

         if (Character.isValidCodePoint(ch)) {

             final char[] value = this.value;

             final int offset = this.offset;

             char hi = Character.highSurrogate(ch);

             char lo = Character.lowSurrogate(ch);

             int i = offset + Math.min(fromIndex, count - 2);

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

                 if (value[i] == hi && value[i+1] == lo) {

                     return i - offset;

                 }

             }

         }

         return -1;

     }

     /**

      * Returns the index within this string of the first occurrence of the

      * specified substring.

      *

      * <p>The returned index is the smallest value <i>k</i> for which:

      * <blockquote><pre>

      * this.startsWith(str, <i>k</i>)

      * </pre></blockquote>

      * If no such value of <i>k</i> exists, then {@code -1} is returned.

      *

      * @param   str   the substring to search for.

      * @return  the index of the first occurrence of the specified substring,

      *          or {@code -1} if there is no such occurrence.

      */

     public int indexOf(String str) {

         return indexOf(str, 0);

     }

     /**

      * Returns the index within this string of the first occurrence of the

      * specified substring, starting at the specified index.

      *

      * <p>The returned index is the smallest value <i>k</i> for which:

      * <blockquote><pre>

      * <i>k</i> &gt;= fromIndex && this.startsWith(str, <i>k</i>)

      * </pre></blockquote>

      * If no such value of <i>k</i> exists, then {@code -1} is returned.

      *

      * @param   str         the substring to search for.

      * @param   fromIndex   the index from which to start the search.

      * @return  the index of the first occurrence of the specified substring,

      *          starting at the specified index,

      *          or {@code -1} if there is no such occurrence.

      */

     public int indexOf(String str, int fromIndex) {

         return indexOf(value, offset, count,

                        str.value, str.offset, str.count, fromIndex);

     }

     /**

      * Code shared by String and StringBuffer to do searches. The

      * source is the character array being searched, and the target

      * is the string being searched for.

      *

      * @param   source       the characters being searched.

      * @param   sourceOffset offset of the source string.

      * @param   sourceCount  count of the source string.

      * @param   target       the characters being searched for.

      * @param   targetOffset offset of the target string.

      * @param   targetCount  count of the target string.

      * @param   fromIndex    the index to begin searching from.

      */

     static int indexOf(char[] source, int sourceOffset, int sourceCount,

                        char[] target, int targetOffset, int targetCount,

                        int fromIndex) {

         if (fromIndex >= sourceCount) {

             return (targetCount == 0 ? sourceCount : -1);

         }

         if (fromIndex < 0) {

             fromIndex = 0;

         }

         if (targetCount == 0) {

             return fromIndex;

         }

         char first  = target[targetOffset];

         int max = sourceOffset + (sourceCount - targetCount);

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

             /* Look for first character. */

             if (source[i] != first) {

                 while (++i <= max && source[i] != first);

             }

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

             if (i <= max) {

                 int j = i + 1;

                 int end = j + targetCount - 1;

                 for (int k = targetOffset + 1; j < end && source[j] ==

                          target[k]; j++, k++);

                 if (j == end) {

                     /* Found whole string. */

                     return i - sourceOffset;

                 }

             }

         }

         return -1;

     }

     /**

      * Returns the index within this string of the last occurrence of the

      * specified substring.  The last occurrence of the empty string ""

      * is considered to occur at the index value {@code this.length()}.

      *

      * <p>The returned index is the largest value <i>k</i> for which:

      * <blockquote><pre>

      * this.startsWith(str, <i>k</i>)

      * </pre></blockquote>

      * If no such value of <i>k</i> exists, then {@code -1} is returned.

      *

      * @param   str   the substring to search for.

      * @return  the index of the last occurrence of the specified substring,

      *          or {@code -1} if there is no such occurrence.

      */

     public int lastIndexOf(String str) {

         return lastIndexOf(str, count);

     }

     /**

      * Returns the index within this string of the last occurrence of the

      * specified substring, searching backward starting at the specified index.

      *

      * <p>The returned index is the largest value <i>k</i> for which:

      * <blockquote><pre>

      * <i>k</i> &lt;= fromIndex && this.startsWith(str, <i>k</i>)

      * </pre></blockquote>

      * If no such value of <i>k</i> exists, then {@code -1} is returned.

      *

      * @param   str         the substring to search for.

      * @param   fromIndex   the index to start the search from.

      * @return  the index of the last occurrence of the specified substring,

      *          searching backward from the specified index,

      *          or {@code -1} if there is no such occurrence.

      */

     public int lastIndexOf(String str, int fromIndex) {

         return lastIndexOf(value, offset, count,

                            str.value, str.offset, str.count, fromIndex);

     }

     /**

      * Code shared by String and StringBuffer to do searches. The

      * source is the character array being searched, and the target

      * is the string being searched for.

      *

      * @param   source       the characters being searched.

      * @param   sourceOffset offset of the source string.

      * @param   sourceCount  count of the source string.

      * @param   target       the characters being searched for.

      * @param   targetOffset offset of the target string.

      * @param   targetCount  count of the target string.

      * @param   fromIndex    the index to begin searching from.

      */

     static int lastIndexOf(char[] source, int sourceOffset, int sourceCount,

                            char[] target, int targetOffset, int targetCount,

                            int fromIndex) {

         /*

          * Check arguments; return immediately where possible. For

          * consistency, don't check for null str.

          */

         int rightIndex = sourceCount - targetCount;

         if (fromIndex < 0) {

             return -1;

         }

         if (fromIndex > rightIndex) {

             fromIndex = rightIndex;

         }

         /* Empty string always matches. */

         if (targetCount == 0) {

             return fromIndex;

         }

         int strLastIndex = targetOffset + targetCount - 1;

         char strLastChar = target[strLastIndex];

         int min = sourceOffset + targetCount - 1;

         int i = min + fromIndex;

     startSearchForLastChar:

         while (true) {

             while (i >= min && source[i] != strLastChar) {

                 i--;

             }

             if (i < min) {

                 return -1;

             }

             int j = i - 1;

             int start = j - (targetCount - 1);

             int k = strLastIndex - 1;

             while (j > start) {

                 if (source[j--] != target[k--]) {

                     i--;

                     continue startSearchForLastChar;

                 }

             }

             return start - sourceOffset + 1;

         }

     }

     /**

      * Returns a new string that is a substring of this string. The

      * substring begins with the character at the specified index and

      * extends to the end of this string. <p>

      * Examples:

      * <blockquote><pre>

      * "unhappy".substring(2) returns "happy"

      * "Harbison".substring(3) returns "bison"

      * "emptiness".substring(9) returns "" (an empty string)

      * </pre></blockquote>

      *

      * @param      beginIndex   the beginning index, inclusive.

      * @return     the specified substring.

      * @exception  IndexOutOfBoundsException  if

      *             <code>beginIndex</code> is negative or larger than the

      *             length of this <code>String</code> object.

      */

     public String substring(int beginIndex) {

         return substring(beginIndex, count);

     }

     /**

      * Returns a new string that is a substring of this string. The

      * substring begins at the specified <code>beginIndex</code> and

      * extends to the character at index <code>endIndex - 1</code>.

      * Thus the length of the substring is <code>endIndex-beginIndex</code>.

      * <p>

      * Examples:

      * <blockquote><pre>

      * "hamburger".substring(4, 8) returns "urge"

      * "smiles".substring(1, 5) returns "mile"

      * </pre></blockquote>

      *

      * @param      beginIndex   the beginning index, inclusive.

      * @param      endIndex     the ending index, exclusive.

      * @return     the specified substring.

      * @exception  IndexOutOfBoundsException  if the

      *             <code>beginIndex</code> is negative, or

      *             <code>endIndex</code> is larger than the length of

      *             this <code>String</code> object, or

      *             <code>beginIndex</code> is larger than

      *             <code>endIndex</code>.

      */

     public String substring(int beginIndex, int endIndex) {

         if (beginIndex < 0) {

             throw new StringIndexOutOfBoundsException(beginIndex);

         }

         if (endIndex > count) {

             throw new StringIndexOutOfBoundsException(endIndex);

         }

         if (beginIndex > endIndex) {

             throw new StringIndexOutOfBoundsException(endIndex - beginIndex);

         }

         return ((beginIndex == 0) && (endIndex == count)) ? this :

             new String(offset + beginIndex, endIndex - beginIndex, value);

     }

     /**

      * Returns a new character sequence that is a subsequence of this sequence.

      *

      * <p> An invocation of this method of the form

      *

      * <blockquote><pre>

      * str.subSequence(begin,&nbsp;end)</pre></blockquote>

      *

      * behaves in exactly the same way as the invocation

      *

      * <blockquote><pre>

      * str.substring(begin,&nbsp;end)</pre></blockquote>

      *

      * This method is defined so that the <tt>String</tt> class can implement

      * the {@link CharSequence} interface. </p>

      *

      * @param      beginIndex   the begin index, inclusive.

      * @param      endIndex     the end index, exclusive.

      * @return     the specified subsequence.

      *

      * @throws  IndexOutOfBoundsException

      *          if <tt>beginIndex</tt> or <tt>endIndex</tt> are negative,

      *          if <tt>endIndex</tt> is greater than <tt>length()</tt>,

      *          or if <tt>beginIndex</tt> is greater than <tt>startIndex</tt>

      *

      * @since 1.4

      * @spec JSR-51

      */

     public CharSequence subSequence(int beginIndex, int endIndex) {

         return this.substring(beginIndex, endIndex);

     }

     /**

      * Concatenates the specified string to the end of this string.

      * <p>

      * If the length of the argument string is <code>0</code>, then this

      * <code>String</code> object is returned. Otherwise, a new

      * <code>String</code> object is created, representing a character

      * sequence that is the concatenation of the character sequence

      * represented by this <code>String</code> object and the character

      * sequence represented by the argument string.<p>

      * Examples:

      * <blockquote><pre>

      * "cares".concat("s") returns "caress"

      * "to".concat("get").concat("her") returns "together"

      * </pre></blockquote>

      *

      * @param   str   the <code>String</code> that is concatenated to the end

      *                of this <code>String</code>.

      * @return  a string that represents the concatenation of this object's

      *          characters followed by the string argument's characters.

      */

     public String concat(String str) {

         int otherLen = str.length();

         if (otherLen == 0) {

             return this;

         }

         char buf[] = new char[count + otherLen];

         getChars(0, count, buf, 0);

         str.getChars(0, otherLen, buf, count);

         return new String(0, count + otherLen, buf);

     }

     /**

      * Returns a new string resulting from replacing all occurrences of

      * <code>oldChar</code> in this string with <code>newChar</code>.

      * <p>

      * If the character <code>oldChar</code> does not occur in the

      * character sequence represented by this <code>String</code> object,

      * then a reference to this <code>String</code> object is returned.

      * Otherwise, a new <code>String</code> object is created that

      * represents a character sequence identical to the character sequence

      * represented by this <code>String</code> object, except that every

      * occurrence of <code>oldChar</code> is replaced by an occurrence

      * of <code>newChar</code>.

      * <p>

      * Examples:

      * <blockquote><pre>

      * "mesquite in your cellar".replace('e', 'o')

      *         returns "mosquito in your collar"

      * "the war of baronets".replace('r', 'y')

      *         returns "the way of bayonets"

      * "sparring with a purple porpoise".replace('p', 't')

      *         returns "starring with a turtle tortoise"

      * "JonL".replace('q', 'x') returns "JonL" (no change)

      * </pre></blockquote>

      *

      * @param   oldChar   the old character.

      * @param   newChar   the new character.

      * @return  a string derived from this string by replacing every

      *          occurrence of <code>oldChar</code> with <code>newChar</code>.

      */

     public String replace(char oldChar, char newChar) {

         if (oldChar != newChar) {

             int len = count;

             int i = -1;

             char[] val = value; /* avoid getfield opcode */

             int off = offset;   /* avoid getfield opcode */

             while (++i < len) {

                 if (val[off + i] == oldChar) {

                     break;

                 }

             }

             if (i < len) {

                 char buf[] = new char[len];

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

                     buf[j] = val[off+j];

                 }

                 while (i < len) {

                     char c = val[off + i];

                     buf[i] = (c == oldChar) ? newChar : c;

                     i++;

                 }

                 return new String(0, len, buf);

             }

         }

         return this;

     }

     /**

      * Tells whether or not this string matches the given <a

      * href="../util/regex/Pattern.html#sum">regular expression</a>.

      *

      * <p> An invocation of this method of the form

      * <i>str</i><tt>.matches(</tt><i>regex</i><tt>)</tt> yields exactly the

      * same result as the expression

      *

      * <blockquote><tt> {@link java.util.regex.Pattern}.{@link

      * java.util.regex.Pattern#matches(String,CharSequence)

      * matches}(</tt><i>regex</i><tt>,</tt> <i>str</i><tt>)</tt></blockquote>

      *

      * @param   regex

      *          the regular expression to which this string is to be matched

      *

      * @return  <tt>true</tt> if, and only if, this string matches the

      *          given regular expression

      *

      * @throws  PatternSyntaxException

      *          if the regular expression's syntax is invalid

      *

      * @see java.util.regex.Pattern

      *

      * @since 1.4

      * @spec JSR-51

      */

     public boolean matches(String regex) {

         return Pattern.matches(regex, this);

     }

     /**

      * Returns true if and only if this string contains the specified

      * sequence of char values.

      *

      * @param s the sequence to search for

      * @return true if this string contains <code>s</code>, false otherwise

      * @throws NullPointerException if <code>s</code> is <code>null</code>

      * @since 1.5

      */

     public boolean contains(CharSequence s) {

         return indexOf(s.toString()) > -1;

     }

     /**

      * Replaces the first substring of this string that matches the given <a

      * href="../util/regex/Pattern.html#sum">regular expression</a> with the

      * given replacement.

      *

      * <p> An invocation of this method of the form

      * <i>str</i><tt>.replaceFirst(</tt><i>regex</i><tt>,</tt> <i>repl</i><tt>)</tt>

      * yields exactly the same result as the expression

      *

      * <blockquote><tt>

      * {@link java.util.regex.Pattern}.{@link java.util.regex.Pattern#compile

      * compile}(</tt><i>regex</i><tt>).{@link

      * java.util.regex.Pattern#matcher(java.lang.CharSequence)

      * matcher}(</tt><i>str</i><tt>).{@link java.util.regex.Matcher#replaceFirst

      * replaceFirst}(</tt><i>repl</i><tt>)</tt></blockquote>

      *

      *<p>

      * Note that backslashes (<tt>\</tt>) and dollar signs (<tt>$</tt>) in the

      * replacement string may cause the results to be different than if it were

      * being treated as a literal replacement string; see

      * {@link java.util.regex.Matcher#replaceFirst}.

      * Use {@link java.util.regex.Matcher#quoteReplacement} to suppress the special

      * meaning of these characters, if desired.

      *

      * @param   regex

      *          the regular expression to which this string is to be matched

      * @param   replacement

      *          the string to be substituted for the first match

      *

      * @return  The resulting <tt>String</tt>

      *

      * @throws  PatternSyntaxException

      *          if the regular expression's syntax is invalid

      *

      * @see java.util.regex.Pattern

      *

      * @since 1.4

      * @spec JSR-51

      */

     public String replaceFirst(String regex, String replacement) {

         return Pattern.compile(regex).matcher(this).replaceFirst(replacement);

     }

     /**

      * Replaces each substring of this string that matches the given <a

      * href="../util/regex/Pattern.html#sum">regular expression</a> with the

      * given replacement.

      *

      * <p> An invocation of this method of the form

      * <i>str</i><tt>.replaceAll(</tt><i>regex</i><tt>,</tt> <i>repl</i><tt>)</tt>

      * yields exactly the same result as the expression

      *

      * <blockquote><tt>

      * {@link java.util.regex.Pattern}.{@link java.util.regex.Pattern#compile

      * compile}(</tt><i>regex</i><tt>).{@link

      * java.util.regex.Pattern#matcher(java.lang.CharSequence)

      * matcher}(</tt><i>str</i><tt>).{@link java.util.regex.Matcher#replaceAll

      * replaceAll}(</tt><i>repl</i><tt>)</tt></blockquote>

      *

      *<p>

      * Note that backslashes (<tt>\</tt>) and dollar signs (<tt>$</tt>) in the

      * replacement string may cause the results to be different than if it were

      * being treated as a literal replacement string; see

      * {@link java.util.regex.Matcher#replaceAll Matcher.replaceAll}.

      * Use {@link java.util.regex.Matcher#quoteReplacement} to suppress the special

      * meaning of these characters, if desired.

      *

      * @param   regex

      *          the regular expression to which this string is to be matched

      * @param   replacement

      *          the string to be substituted for each match

      *

      * @return  The resulting <tt>String</tt>

      *

      * @throws  PatternSyntaxException

      *          if the regular expression's syntax is invalid

      *

      * @see java.util.regex.Pattern

      *

      * @since 1.4

      * @spec JSR-51

      */

     public String replaceAll(String regex, String replacement) {

         return Pattern.compile(regex).matcher(this).replaceAll(replacement);

     }

     /**

      * Replaces each substring of this string that matches the literal target

      * sequence with the specified literal replacement sequence. The

      * replacement proceeds from the beginning of the string to the end, for

      * example, replacing "aa" with "b" in the string "aaa" will result in

      * "ba" rather than "ab".

      *

      * @param  target The sequence of char values to be replaced

      * @param  replacement The replacement sequence of char values

      * @return  The resulting string

      * @throws NullPointerException if <code>target</code> or

      *         <code>replacement</code> is <code>null</code>.

      * @since 1.5

      */

     public String replace(CharSequence target, CharSequence replacement) {

         return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(

             this).replaceAll(Matcher.quoteReplacement(replacement.toString()));

     }

     /**

      * Splits this string around matches of the given

      * <a href="../util/regex/Pattern.html#sum">regular expression</a>.

      *

      * <p> The array returned by this method contains each substring of this

      * string that is terminated by another substring that matches the given

      * expression or is terminated by the end of the string.  The substrings in

      * the array are in the order in which they occur in this string.  If the

      * expression does not match any part of the input then the resulting array

      * has just one element, namely this string.

      *

      * <p> The <tt>limit</tt> parameter controls the number of times the

      * pattern is applied and therefore affects the length of the resulting

      * array.  If the limit <i>n</i> is greater than zero then the pattern

      * will be applied at most <i>n</i>&nbsp;-&nbsp;1 times, the array's

      * length will be no greater than <i>n</i>, and the array's last entry

      * will contain all input beyond the last matched delimiter.  If <i>n</i>

      * is non-positive then the pattern will be applied as many times as

      * possible and the array can have any length.  If <i>n</i> is zero then

      * the pattern will be applied as many times as possible, the array can

      * have any length, and trailing empty strings will be discarded.

      *

      * <p> The string <tt>"boo:and:foo"</tt>, for example, yields the

      * following results with these parameters:

      *

      * <blockquote><table cellpadding=1 cellspacing=0 summary="Split example showing regex, limit, and result">

      * <tr>

      *     <th>Regex</th>

      *     <th>Limit</th>

      *     <th>Result</th>

      * </tr>

      * <tr><td align=center>:</td>

      *     <td align=center>2</td>

      *     <td><tt>{ "boo", "and:foo" }</tt></td></tr>

      * <tr><td align=center>:</td>

      *     <td align=center>5</td>

      *     <td><tt>{ "boo", "and", "foo" }</tt></td></tr>

      * <tr><td align=center>:</td>

      *     <td align=center>-2</td>

      *     <td><tt>{ "boo", "and", "foo" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td align=center>5</td>

      *     <td><tt>{ "b", "", ":and:f", "", "" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td align=center>-2</td>

      *     <td><tt>{ "b", "", ":and:f", "", "" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td align=center>0</td>

      *     <td><tt>{ "b", "", ":and:f" }</tt></td></tr>

      * </table></blockquote>

      *

      * <p> An invocation of this method of the form

      * <i>str.</i><tt>split(</tt><i>regex</i><tt>,</tt>&nbsp;<i>n</i><tt>)</tt>

      * yields the same result as the expression

      *

      * <blockquote>

      * {@link java.util.regex.Pattern}.{@link java.util.regex.Pattern#compile

      * compile}<tt>(</tt><i>regex</i><tt>)</tt>.{@link

      * java.util.regex.Pattern#split(java.lang.CharSequence,int)

      * split}<tt>(</tt><i>str</i><tt>,</tt>&nbsp;<i>n</i><tt>)</tt>

      * </blockquote>

      *

      *

      * @param  regex

      *         the delimiting regular expression

      *

      * @param  limit

      *         the result threshold, as described above

      *

      * @return  the array of strings computed by splitting this string

      *          around matches of the given regular expression

      *

      * @throws  PatternSyntaxException

      *          if the regular expression's syntax is invalid

      *

      * @see java.util.regex.Pattern

      *

      * @since 1.4

      * @spec JSR-51

      */

     public String[] split(String regex, int limit) {

         /* fastpath if the regex is a

            (1)one-char String and this character is not one of the

               RegEx's meta characters ".$|()[{^?*+\\", or

            (2)two-char String and the first char is the backslash and

               the second is not the ascii digit or ascii letter.

         */

         char ch = 0;

         if (((regex.count == 1 &&

              ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||

              (regex.length() == 2 &&

               regex.charAt(0) == '\\' &&

               (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&

               ((ch-'a')|('z'-ch)) < 0 &&

               ((ch-'A')|('Z'-ch)) < 0)) &&

             (ch < Character.MIN_HIGH_SURROGATE ||

              ch > Character.MAX_LOW_SURROGATE))

         {

             int off = 0;

             int next = 0;

             boolean limited = limit > 0;

             ArrayList<String> list = new ArrayList<String>();

             while ((next = indexOf(ch, off)) != -1) {

                 if (!limited || list.size() < limit - 1) {

                     list.add(substring(off, next));

                     off = next + 1;

                 } else {    // last one

                     //assert (list.size() == limit - 1);

                     list.add(substring(off, count));

                     off = count;

                     break;

                 }

             }

             // If no match was found, return this

             if (off == 0)

                 return new String[] { this };

             // Add remaining segment

             if (!limited || list.size() < limit)

                 list.add(substring(off, count));

             // Construct result

             int resultSize = list.size();

             if (limit == 0)

                 while (resultSize > 0 && list.get(resultSize-1).length() == 0)

                     resultSize--;

             String[] result = new String[resultSize];

             return list.subList(0, resultSize).toArray(result);

         }

         return Pattern.compile(regex).split(this, limit);

     }

     /**

      * Splits this string around matches of the given <a

      * href="../util/regex/Pattern.html#sum">regular expression</a>.

      *

      * <p> This method works as if by invoking the two-argument {@link

      * #split(String, int) split} method with the given expression and a limit

      * argument of zero.  Trailing empty strings are therefore not included in

      * the resulting array.

      *

      * <p> The string <tt>"boo:and:foo"</tt>, for example, yields the following

      * results with these expressions:

      *

      * <blockquote><table cellpadding=1 cellspacing=0 summary="Split examples showing regex and result">

      * <tr>

      *  <th>Regex</th>

      *  <th>Result</th>

      * </tr>

      * <tr><td align=center>:</td>

      *     <td><tt>{ "boo", "and", "foo" }</tt></td></tr>

      * <tr><td align=center>o</td>

      *     <td><tt>{ "b", "", ":and:f" }</tt></td></tr>

      * </table></blockquote>

      *

      *

      * @param  regex

      *         the delimiting regular expression

      *

      * @return  the array of strings computed by splitting this string

      *          around matches of the given regular expression

      *

      * @throws  PatternSyntaxException

      *          if the regular expression's syntax is invalid

      *

      * @see java.util.regex.Pattern

      *

      * @since 1.4

      * @spec JSR-51

      */

     public String[] split(String regex) {

         return split(regex, 0);

     }

     /**

      * Converts all of the characters in this <code>String</code> to lower

      * case using the rules of the given <code>Locale</code>.  Case mapping is based

      * on the Unicode Standard version specified by the {@link java.lang.Character Character}

      * class. Since case mappings are not always 1:1 char mappings, the resulting

      * <code>String</code> may be a different length than the original <code>String</code>.

      * <p>

      * Examples of lowercase  mappings are in the following table:

      * <table border="1" summary="Lowercase mapping examples showing language code of locale, upper case, lower case, and description">

      * <tr>

      *   <th>Language Code of Locale</th>

      *   <th>Upper Case</th>

      *   <th>Lower Case</th>

      *   <th>Description</th>

      * </tr>

      * <tr>

      *   <td>tr (Turkish)</td>

      *   <td>&#92;u0130</td>

      *   <td>&#92;u0069</td>

      *   <td>capital letter I with dot above -&gt; small letter i</td>

      * </tr>

      * <tr>

      *   <td>tr (Turkish)</td>

      *   <td>&#92;u0049</td>

      *   <td>&#92;u0131</td>

      *   <td>capital letter I -&gt; small letter dotless i </td>

      * </tr>

      * <tr>

      *   <td>(all)</td>

      *   <td>French Fries</td>

      *   <td>french fries</td>

      *   <td>lowercased all chars in String</td>

      * </tr>

      * <tr>

      *   <td>(all)</td>

      *   <td><img src="doc-files/capiota.gif" alt="capiota"><img src="doc-files/capchi.gif" alt="capchi">

      *       <img src="doc-files/captheta.gif" alt="captheta"><img src="doc-files/capupsil.gif" alt="capupsil">

      *       <img src="doc-files/capsigma.gif" alt="capsigma"></td>

      *   <td><img src="doc-files/iota.gif" alt="iota"><img src="doc-files/chi.gif" alt="chi">

      *       <img src="doc-files/theta.gif" alt="theta"><img src="doc-files/upsilon.gif" alt="upsilon">

      *       <img src="doc-files/sigma1.gif" alt="sigma"></td>

      *   <td>lowercased all chars in String</td>

      * </tr>

      * </table>

      *

      * @param locale use the case transformation rules for this locale

      * @return the <code>String</code>, converted to lowercase.

      * @see     java.lang.String#toLowerCase()

      * @see     java.lang.String#toUpperCase()

      * @see     java.lang.String#toUpperCase(Locale)

      * @since   1.1

      */

     public String toLowerCase(Locale locale) {

         if (locale == null) {

             throw new NullPointerException();

         }

         int     firstUpper;

         /* Now check if there are any characters that need to be changed. */

         scan: {

             for (firstUpper = 0 ; firstUpper < count; ) {

                 char c = value[offset+firstUpper];

                 if ((c >= Character.MIN_HIGH_SURROGATE) &&

                     (c <= Character.MAX_HIGH_SURROGATE)) {

                     int supplChar = codePointAt(firstUpper);

                     if (supplChar != Character.toLowerCase(supplChar)) {

                         break scan;

                     }

                     firstUpper += Character.charCount(supplChar);

                 } else {

                     if (c != Character.toLowerCase(c)) {

                         break scan;

                     }

                     firstUpper++;

                 }

             }

             return this;

         }

         char[]  result = new char[count];

         int     resultOffset = 0;  /* result may grow, so i+resultOffset

                                     * is the write location in result */

         /* Just copy the first few lowerCase characters. */

         System.arraycopy(value, offset, result, 0, firstUpper);

         String lang = locale.getLanguage();

         boolean localeDependent =

             (lang == "tr" || lang == "az" || lang == "lt");

         char[] lowerCharArray;

         int lowerChar;

         int srcChar;

         int srcCount;

         for (int i = firstUpper; i < count; i += srcCount) {

             srcChar = (int)value[offset+i];

             if ((char)srcChar >= Character.MIN_HIGH_SURROGATE &&

                 (char)srcChar <= Character.MAX_HIGH_SURROGATE) {

                 srcChar = codePointAt(i);

                 srcCount = Character.charCount(srcChar);

             } else {

                 srcCount = 1;

             }

             if (localeDependent || srcChar == '\u03A3') { // GREEK CAPITAL LETTER SIGMA

                 lowerChar = ConditionalSpecialCasing.toLowerCaseEx(this, i, locale);

             } else if (srcChar == '\u0130') { // LATIN CAPITAL LETTER I DOT

                 lowerChar = Character.ERROR;

             } else {

                 lowerChar = Character.toLowerCase(srcChar);

             }

             if ((lowerChar == Character.ERROR) ||

                 (lowerChar >= Character.MIN_SUPPLEMENTARY_CODE_POINT)) {

                 if (lowerChar == Character.ERROR) {

                      if (!localeDependent && srcChar == '\u0130') {

                          lowerCharArray =

                              ConditionalSpecialCasing.toLowerCaseCharArray(this, i, Locale.ENGLISH);

                      } else {

                         lowerCharArray =

                             ConditionalSpecialCasing.toLowerCaseCharArray(this, i, locale);

                      }

                 } else if (srcCount == 2) {

                     resultOffset += Character.toChars(lowerChar, result, i + resultOffset) - srcCount;

                     continue;

                 } else {

                     lowerCharArray = Character.toChars(lowerChar);

                 }

                 /* Grow result if needed */

                 int mapLen = lowerCharArray.length;

                 if (mapLen > srcCount) {

                     char[] result2 = new char[result.length + mapLen - srcCount];

                     System.arraycopy(result, 0, result2, 0,

                         i + resultOffset);

                     result = result2;

                 }

                 for (int x=0; x<mapLen; ++x) {

                     result[i+resultOffset+x] = lowerCharArray[x];

                 }

                 resultOffset += (mapLen - srcCount);

             } else {

                 result[i+resultOffset] = (char)lowerChar;

             }

         }

         return new String(0, count+resultOffset, result);

     }

     /**

      * Converts all of the characters in this <code>String</code> to lower

      * case using the rules of the default locale. This is equivalent to calling

      * <code>toLowerCase(Locale.getDefault())</code>.

      * <p>

      * <b>Note:</b> This method is locale sensitive, and may produce unexpected

      * results if used for strings that are intended to be interpreted locale

      * independently.

      * Examples are programming language identifiers, protocol keys, and HTML

      * tags.

      * For instance, <code>"TITLE".toLowerCase()</code> in a Turkish locale

      * returns <code>"t\u005Cu0131tle"</code>, where '\u005Cu0131' is the

      * LATIN SMALL LETTER DOTLESS I character.

      * To obtain correct results for locale insensitive strings, use

      * <code>toLowerCase(Locale.ENGLISH)</code>.

      * <p>

      * @return  the <code>String</code>, converted to lowercase.

      * @see     java.lang.String#toLowerCase(Locale)

      */

     public String toLowerCase() {

         return toLowerCase(Locale.getDefault());

     }

     /**

      * Converts all of the characters in this <code>String</code> to upper

      * case using the rules of the given <code>Locale</code>. Case mapping is based

      * on the Unicode Standard version specified by the {@link java.lang.Character Character}

      * class. Since case mappings are not always 1:1 char mappings, the resulting

      * <code>String</code> may be a different length than the original <code>String</code>.

      * <p>

      * Examples of locale-sensitive and 1:M case mappings are in the following table.

      * <p>

      * <table border="1" summary="Examples of locale-sensitive and 1:M case mappings. Shows Language code of locale, lower case, upper case, and description.">

      * <tr>

      *   <th>Language Code of Locale</th>

      *   <th>Lower Case</th>

      *   <th>Upper Case</th>

      *   <th>Description</th>

      * </tr>

      * <tr>

      *   <td>tr (Turkish)</td>

      *   <td>&#92;u0069</td>

      *   <td>&#92;u0130</td>

      *   <td>small letter i -&gt; capital letter I with dot above</td>

      * </tr>

      * <tr>

      *   <td>tr (Turkish)</td>

      *   <td>&#92;u0131</td>

      *   <td>&#92;u0049</td>

      *   <td>small letter dotless i -&gt; capital letter I</td>

      * </tr>

      * <tr>

      *   <td>(all)</td>

      *   <td>&#92;u00df</td>

      *   <td>&#92;u0053 &#92;u0053</td>

      *   <td>small letter sharp s -&gt; two letters: SS</td>

      * </tr>

      * <tr>

      *   <td>(all)</td>

      *   <td>Fahrvergn&uuml;gen</td>

      *   <td>FAHRVERGN&Uuml;GEN</td>

      *   <td></td>

      * </tr>

      * </table>

      * @param locale use the case transformation rules for this locale

      * @return the <code>String</code>, converted to uppercase.

      * @see     java.lang.String#toUpperCase()

      * @see     java.lang.String#toLowerCase()

      * @see     java.lang.String#toLowerCase(Locale)

      * @since   1.1

      */

     public String toUpperCase(Locale locale) {

         if (locale == null) {

             throw new NullPointerException();

         }

         int     firstLower;

         /* Now check if there are any characters that need to be changed. */

         scan: {

             for (firstLower = 0 ; firstLower < count; ) {

                 int c = (int)value[offset+firstLower];

                 int srcCount;

                 if ((c >= Character.MIN_HIGH_SURROGATE) &&

                     (c <= Character.MAX_HIGH_SURROGATE)) {

                     c = codePointAt(firstLower);

                     srcCount = Character.charCount(c);

                 } else {

                     srcCount = 1;

                 }

                 int upperCaseChar = Character.toUpperCaseEx(c);

                 if ((upperCaseChar == Character.ERROR) ||

                     (c != upperCaseChar)) {

                     break scan;

                 }

                 firstLower += srcCount;

             }

             return this;

         }