/*

 * 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.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

package java.util;

import java.util.regex.*;

import java.io.*;

import java.math.*;

import java.nio.*;

import java.nio.channels.*;

import java.nio.charset.*;

import java.text.*;

import java.util.Locale;

import sun.misc.LRUCache;

/**

 * A simple text scanner which can parse primitive types and strings using

 * regular expressions.

 *

 * <p>A <code>Scanner</code> breaks its input into tokens using a

 * delimiter pattern, which by default matches whitespace. The resulting

 * tokens may then be converted into values of different types using the

 * various <tt>next</tt> methods.

 *

 * <p>For example, this code allows a user to read a number from

 * <tt>System.in</tt>:

 * <blockquote><pre>

 *     Scanner sc = new Scanner(System.in);

 *     int i = sc.nextInt();

 * </pre></blockquote>

 *

 * <p>As another example, this code allows <code>long</code> types to be

 * assigned from entries in a file <code>myNumbers</code>:

 * <blockquote><pre>

 *      Scanner sc = new Scanner(new File("myNumbers"));

 *      while (sc.hasNextLong()) {

 *          long aLong = sc.nextLong();

 *      }</pre></blockquote>

 *

 * <p>The scanner can also use delimiters other than whitespace. This

 * example reads several items in from a string:

 *<blockquote><pre>

 *     String input = "1 fish 2 fish red fish blue fish";

 *     Scanner s = new Scanner(input).useDelimiter("\\s*fish\\s*");

 *     System.out.println(s.nextInt());

 *     System.out.println(s.nextInt());

 *     System.out.println(s.next());

 *     System.out.println(s.next());

 *     s.close(); </pre></blockquote>

 * <p>

 * prints the following output:

 * <blockquote><pre>

 *     1

 *     2

 *     red

 *     blue </pre></blockquote>

 *

 * <p>The same output can be generated with this code, which uses a regular

 * expression to parse all four tokens at once:

 *<blockquote><pre>

 *     String input = "1 fish 2 fish red fish blue fish";

 *     Scanner s = new Scanner(input);

 *     s.findInLine("(\\d+) fish (\\d+) fish (\\w+) fish (\\w+)");

 *     MatchResult result = s.match();

 *     for (int i=1; i<=result.groupCount(); i++)

 *         System.out.println(result.group(i));

 *     s.close(); </pre></blockquote>

 *

 * <p>The <a name="default-delimiter">default whitespace delimiter</a> used

 * by a scanner is as recognized by {@link java.lang.Character}.{@link

 * java.lang.Character#isWhitespace(char) isWhitespace}. The {@link #reset}

 * method will reset the value of the scanner's delimiter to the default

 * whitespace delimiter regardless of whether it was previously changed.

 *

 * <p>A scanning operation may block waiting for input.

 *

 * <p>The {@link #next} and {@link #hasNext} methods and their

 * primitive-type companion methods (such as {@link #nextInt} and

 * {@link #hasNextInt}) first skip any input that matches the delimiter

 * pattern, and then attempt to return the next token. Both <tt>hasNext</tt>

 * and <tt>next</tt> methods may block waiting for further input.  Whether a

 * <tt>hasNext</tt> method blocks has no connection to whether or not its

 * associated <tt>next</tt> method will block.

 *

 * <p> The {@link #findInLine}, {@link #findWithinHorizon}, and {@link #skip}

 * methods operate independently of the delimiter pattern. These methods will

 * attempt to match the specified pattern with no regard to delimiters in the

 * input and thus can be used in special circumstances where delimiters are

 * not relevant. These methods may block waiting for more input.

 *

 * <p>When a scanner throws an {@link InputMismatchException}, the scanner

 * will not pass the token that caused the exception, so that it may be

 * retrieved or skipped via some other method.

 *

 * <p>Depending upon the type of delimiting pattern, empty tokens may be

 * returned. For example, the pattern <tt>"\\s+"</tt> will return no empty

 * tokens since it matches multiple instances of the delimiter. The delimiting

 * pattern <tt>"\\s"</tt> could return empty tokens since it only passes one

 * space at a time.

 *

 * <p> A scanner can read text from any object which implements the {@link

 * java.lang.Readable} interface.  If an invocation of the underlying

 * readable's {@link java.lang.Readable#read} method throws an {@link

 * java.io.IOException} then the scanner assumes that the end of the input

 * has been reached.  The most recent <tt>IOException</tt> thrown by the

 * underlying readable can be retrieved via the {@link #ioException} method.

 *

 * <p>When a <code>Scanner</code> is closed, it will close its input source

 * if the source implements the {@link java.io.Closeable} interface.

 *

 * <p>A <code>Scanner</code> is not safe for multithreaded use without

 * external synchronization.

 *

 * <p>Unless otherwise mentioned, passing a <code>null</code> parameter into

 * any method of a <code>Scanner</code> will cause a

 * <code>NullPointerException</code> to be thrown.

 *

 * <p>A scanner will default to interpreting numbers as decimal unless a

 * different radix has been set by using the {@link #useRadix} method. The

 * {@link #reset} method will reset the value of the scanner's radix to

 * <code>10</code> regardless of whether it was previously changed.

 *

 * <a name="localized-numbers">

 * <h4> Localized numbers </h4>

 *

 * <p> An instance of this class is capable of scanning numbers in the standard

 * formats as well as in the formats of the scanner's locale. A scanner's

 * <a name="initial-locale">initial locale </a>is the value returned by the {@link

 * java.util.Locale#getDefault} method; it may be changed via the {@link

 * #useLocale} method. The {@link #reset} method will reset the value of the

 * scanner's locale to the initial locale regardless of whether it was

 * previously changed.

 *

 * <p>The localized formats are defined in terms of the following parameters,

 * which for a particular locale are taken from that locale's {@link

 * java.text.DecimalFormat DecimalFormat} object, <tt>df</tt>, and its and

 * {@link java.text.DecimalFormatSymbols DecimalFormatSymbols} object,

 * <tt>dfs</tt>.

 *

 * <blockquote><table>

 * <tr><td valign="top"><i>LocalGroupSeparator&nbsp;&nbsp;</i></td>

 *     <td valign="top">The character used to separate thousands groups,

 *                      <i>i.e.,</i>&nbsp;<tt>dfs.</tt>{@link

 *                      java.text.DecimalFormatSymbols#getGroupingSeparator

 *                      getGroupingSeparator()}</td></tr>

 * <tr><td valign="top"><i>LocalDecimalSeparator&nbsp;&nbsp;</i></td>

 *     <td valign="top">The character used for the decimal point,

 *                      <i>i.e.,</i>&nbsp;<tt>dfs.</tt>{@link

 *                      java.text.DecimalFormatSymbols#getDecimalSeparator

 *                      getDecimalSeparator()}</td></tr>

 * <tr><td valign="top"><i>LocalPositivePrefix&nbsp;&nbsp;</i></td>

 *     <td valign="top">The string that appears before a positive number (may

 *                      be empty), <i>i.e.,</i>&nbsp;<tt>df.</tt>{@link

 *                      java.text.DecimalFormat#getPositivePrefix

 *                      getPositivePrefix()}</td></tr>

 * <tr><td valign="top"><i>LocalPositiveSuffix&nbsp;&nbsp;</i></td>

 *     <td valign="top">The string that appears after a positive number (may be

 *                      empty), <i>i.e.,</i>&nbsp;<tt>df.</tt>{@link

 *                      java.text.DecimalFormat#getPositiveSuffix

 *                      getPositiveSuffix()}</td></tr>

 * <tr><td valign="top"><i>LocalNegativePrefix&nbsp;&nbsp;</i></td>

 *     <td valign="top">The string that appears before a negative number (may

 *                      be empty), <i>i.e.,</i>&nbsp;<tt>df.</tt>{@link

 *                      java.text.DecimalFormat#getNegativePrefix

 *                      getNegativePrefix()}</td></tr>

 * <tr><td valign="top"><i>LocalNegativeSuffix&nbsp;&nbsp;</i></td>

 *     <td valign="top">The string that appears after a negative number (may be

 *                      empty), <i>i.e.,</i>&nbsp;<tt>df.</tt>{@link

 *                      java.text.DecimalFormat#getNegativeSuffix

 *                      getNegativeSuffix()}</td></tr>

 * <tr><td valign="top"><i>LocalNaN&nbsp;&nbsp;</i></td>

 *     <td valign="top">The string that represents not-a-number for

 *                      floating-point values,

 *                      <i>i.e.,</i>&nbsp;<tt>dfs.</tt>{@link

 *                      java.text.DecimalFormatSymbols#getNaN

 *                      getNaN()}</td></tr>

 * <tr><td valign="top"><i>LocalInfinity&nbsp;&nbsp;</i></td>

 *     <td valign="top">The string that represents infinity for floating-point

 *                      values, <i>i.e.,</i>&nbsp;<tt>dfs.</tt>{@link

 *                      java.text.DecimalFormatSymbols#getInfinity

 *                      getInfinity()}</td></tr>

 * </table></blockquote>

 *

 * <a name="number-syntax">

 * <h4> Number syntax </h4>

 *

 * <p> The strings that can be parsed as numbers by an instance of this class

 * are specified in terms of the following regular-expression grammar, where

 * Rmax is the highest digit in the radix being used (for example, Rmax is 9

 * in base 10).

 *

 * <p>

 * <table cellspacing=0 cellpadding=0 align=center>

 *

 *   <tr><td valign=top align=right><i>NonASCIIDigit</i>&nbsp;&nbsp;::</td>

 *       <td valign=top>= A non-ASCII character c for which

 *            {@link java.lang.Character#isDigit Character.isDigit}<tt>(c)</tt>

 *                        returns&nbsp;true</td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>Non0Digit</i>&nbsp;&nbsp;::</td>

 *   <td><tt>= [1-</tt><i>Rmax</i><tt>] | </tt><i>NonASCIIDigit</i></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>Digit</i>&nbsp;&nbsp;::</td>

 *   <td><tt>= [0-</tt><i>Rmax</i><tt>] | </tt><i>NonASCIIDigit</i></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td valign=top align=right><i>GroupedNumeral</i>&nbsp;&nbsp;::</td>

 *       <td valign=top>

 *         <table cellpadding=0 cellspacing=0>

 *           <tr><td><tt>= (&nbsp;</tt></td>

 *               <td><i>Non0Digit</i><tt>

 *                   </tt><i>Digit</i><tt>?

 *                   </tt><i>Digit</i><tt>?</tt></td></tr>

 *           <tr><td></td>

 *               <td><tt>(&nbsp;</tt><i>LocalGroupSeparator</i><tt>

 *                         </tt><i>Digit</i><tt>

 *                         </tt><i>Digit</i><tt>

 *                         </tt><i>Digit</i><tt> )+ )</tt></td></tr>

 *         </table></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>Numeral</i>&nbsp;&nbsp;::</td>

 *       <td><tt>= ( ( </tt><i>Digit</i><tt>+ )

 *               | </tt><i>GroupedNumeral</i><tt> )</tt></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td valign=top align=right>

 *         <a name="Integer-regex"><i>Integer</i>&nbsp;&nbsp;::</td>

 *       <td valign=top><tt>= ( [-+]? ( </tt><i>Numeral</i><tt>

 *                               ) )</tt></td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>LocalPositivePrefix</i><tt> </tt><i>Numeral</i><tt>

 *                      </tt><i>LocalPositiveSuffix</i></td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>LocalNegativePrefix</i><tt> </tt><i>Numeral</i><tt>

 *                 </tt><i>LocalNegativeSuffix</i></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>DecimalNumeral</i>&nbsp;&nbsp;::</td>

 *       <td><tt>= </tt><i>Numeral</i></td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>Numeral</i><tt>

 *                 </tt><i>LocalDecimalSeparator</i><tt>

 *                 </tt><i>Digit</i><tt>*</tt></td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>LocalDecimalSeparator</i><tt>

 *                 </tt><i>Digit</i><tt>+</tt></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>Exponent</i>&nbsp;&nbsp;::</td>

 *       <td><tt>= ( [eE] [+-]? </tt><i>Digit</i><tt>+ )</tt></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right>

 *         <a name="Decimal-regex"><i>Decimal</i>&nbsp;&nbsp;::</td>

 *       <td><tt>= ( [-+]? </tt><i>DecimalNumeral</i><tt>

 *                         </tt><i>Exponent</i><tt>? )</tt></td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>LocalPositivePrefix</i><tt>

 *                 </tt><i>DecimalNumeral</i><tt>

 *                 </tt><i>LocalPositiveSuffix</i>

 *                 </tt><i>Exponent</i><tt>?</td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>LocalNegativePrefix</i><tt>

 *                 </tt><i>DecimalNumeral</i><tt>

 *                 </tt><i>LocalNegativeSuffix</i>

 *                 </tt><i>Exponent</i><tt>?</td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>HexFloat</i>&nbsp;&nbsp;::</td>

 *       <td><tt>= [-+]? 0[xX][0-9a-fA-F]*\.[0-9a-fA-F]+

 *                 ([pP][-+]?[0-9]+)?</tt></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>NonNumber</i>&nbsp;&nbsp;::</td>

 *       <td valign=top><tt>= NaN

 *                          | </tt><i>LocalNan</i><tt>

 *                          | Infinity

 *                          | </tt><i>LocalInfinity</i></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td align=right><i>SignedNonNumber</i>&nbsp;&nbsp;::</td>

 *       <td><tt>= ( [-+]? </tt><i>NonNumber</i><tt> )</tt></td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>LocalPositivePrefix</i><tt>

 *                 </tt><i>NonNumber</i><tt>

 *                 </tt><i>LocalPositiveSuffix</i></td></tr>

 *   <tr><td></td>

 *       <td><tt>| </tt><i>LocalNegativePrefix</i><tt>

 *                 </tt><i>NonNumber</i><tt>

 *                 </tt><i>LocalNegativeSuffix</i></td></tr>

 *

 *   <tr><td>&nbsp;</td></tr>

 *

 *   <tr><td valign=top align=right>

 *         <a name="Float-regex"><i>Float</i>&nbsp;&nbsp;::</td>

 *       <td valign=top><tt>= </tt><i>Decimal</i><tt></td></tr>

 *       <tr><td></td>

 *           <td><tt>| </tt><i>HexFloat</i><tt></td></tr>

 *       <tr><td></td>

 *           <td><tt>| </tt><i>SignedNonNumber</i><tt></td></tr>

 *

 * </table>

 * </center>

 *

 * <p> Whitespace is not significant in the above regular expressions.

 *

 * @since   1.5

 */

public final class Scanner implements Iterator<String> {

    // Internal buffer used to hold input

    private CharBuffer buf;

    // Size of internal character buffer

    private static final int BUFFER_SIZE = 1024; // change to 1024;

    // The index into the buffer currently held by the Scanner

    private int position;

    // Internal matcher used for finding delimiters

    private Matcher matcher;

    // Pattern used to delimit tokens

    private Pattern delimPattern;

    // Pattern found in last hasNext operation

    private Pattern hasNextPattern;

    // Position after last hasNext operation

    private int hasNextPosition;

    // Result after last hasNext operation

    private String hasNextResult;

    // The input source

    private Readable source;

    // Boolean is true if source is done

    private boolean sourceClosed = false;

    // Boolean indicating more input is required

    private boolean needInput = false;

    // Boolean indicating if a delim has been skipped this operation

    private boolean skipped = false;

    // A store of a position that the scanner may fall back to

    private int savedScannerPosition = -1;

    // A cache of the last primitive type scanned

    private Object typeCache = null;

    // Boolean indicating if a match result is available

    private boolean matchValid = false;

    // Boolean indicating if this scanner has been closed

    private boolean closed = false;

    // The current radix used by this scanner

    private int radix = 10;

    // The default radix for this scanner

    private int defaultRadix = 10;

    // The locale used by this scanner

    private Locale locale = null;

    // A cache of the last few recently used Patterns

    private LRUCache<String,Pattern> patternCache =

    new LRUCache<String,Pattern>(7) {

        protected Pattern create(String s) {

            return Pattern.compile(s);

        }

        protected boolean hasName(Pattern p, String s) {

            return p.pattern().equals(s);

        }

    };

    // A holder of the last IOException encountered

    private IOException lastException;

    // A pattern for java whitespace

    private static Pattern WHITESPACE_PATTERN = Pattern.compile(

                                                "\\p{javaWhitespace}+");

    // A pattern for any token

    private static Pattern FIND_ANY_PATTERN = Pattern.compile("(?s).*");

    // A pattern for non-ASCII digits

    private static Pattern NON_ASCII_DIGIT = Pattern.compile(

        "[\\p{javaDigit}&&[^0-9]]");

    // Fields and methods to support scanning primitive types

    /**

     * Locale dependent values used to scan numbers

     */

    private String groupSeparator = "\\,";

    private String decimalSeparator = "\\.";

    private String nanString = "NaN";

    private String infinityString = "Infinity";

    private String positivePrefix = "";

    private String negativePrefix = "\\-";

    private String positiveSuffix = "";

    private String negativeSuffix = "";

    /**

     * Fields and an accessor method to match booleans

     */

    private static volatile Pattern boolPattern;

    private static final String BOOLEAN_PATTERN = "true|false";

    private static Pattern boolPattern() {

        Pattern bp = boolPattern;

        if (bp == null)

            boolPattern = bp = Pattern.compile(BOOLEAN_PATTERN,

                                          Pattern.CASE_INSENSITIVE);

        return bp;

    }

    /**

     * Fields and methods to match bytes, shorts, ints, and longs

     */

    private Pattern integerPattern;

    private String digits = "0123456789abcdefghijklmnopqrstuvwxyz";

    private String non0Digit = "[\\p{javaDigit}&&[^0]]";

    private int SIMPLE_GROUP_INDEX = 5;

    private String buildIntegerPatternString() {

        String radixDigits = digits.substring(0, radix);

        // \\p{javaDigit} is not guaranteed to be appropriate

        // here but what can we do? The final authority will be

        // whatever parse method is invoked, so ultimately the

        // Scanner will do the right thing

        String digit = "((?i)["+radixDigits+"]|\\p{javaDigit})";

        String groupedNumeral = "("+non0Digit+digit+"?"+digit+"?("+

                                groupSeparator+digit+digit+digit+")+)";

        // digit++ is the possessive form which is necessary for reducing

        // backtracking that would otherwise cause unacceptable performance

        String numeral = "(("+ digit+"++)|"+groupedNumeral+")";

        String javaStyleInteger = "([-+]?(" + numeral + "))";

        String negativeInteger = negativePrefix + numeral + negativeSuffix;

        String positiveInteger = positivePrefix + numeral + positiveSuffix;

        return "("+ javaStyleInteger + ")|(" +

            positiveInteger + ")|(" +

            negativeInteger + ")";

    }

    private Pattern integerPattern() {

        if (integerPattern == null) {

            integerPattern = patternCache.forName(buildIntegerPatternString());

        }

        return integerPattern;

    }

    /**

     * Fields and an accessor method to match line separators

     */

    private static volatile Pattern separatorPattern;

    private static volatile Pattern linePattern;

    private static final String LINE_SEPARATOR_PATTERN =

                                           "\r\n|[\n\r\u2028\u2029\u0085]";

    private static final String LINE_PATTERN = ".*("+LINE_SEPARATOR_PATTERN+")|.+$";

    private static Pattern separatorPattern() {

        Pattern sp = separatorPattern;

        if (sp == null)

            separatorPattern = sp = Pattern.compile(LINE_SEPARATOR_PATTERN);

        return sp;

    }

    private static Pattern linePattern() {

        Pattern lp = linePattern;

        if (lp == null)

            linePattern = lp = Pattern.compile(LINE_PATTERN);

        return lp;

    }

    /**

     * Fields and methods to match floats and doubles

     */

    private Pattern floatPattern;

    private Pattern decimalPattern;

    private void buildFloatAndDecimalPattern() {

        // \\p{javaDigit} may not be perfect, see above

        String digit = "([0-9]|(\\p{javaDigit}))";

        String exponent = "([eE][+-]?"+digit+"+)?";

        String groupedNumeral = "("+non0Digit+digit+"?"+digit+"?("+

                                groupSeparator+digit+digit+digit+")+)";

        // Once again digit++ is used for performance, as above

        String numeral = "(("+digit+"++)|"+groupedNumeral+")";

        String decimalNumeral = "("+numeral+"|"+numeral +

            decimalSeparator + digit + "*+|"+ decimalSeparator +

            digit + "++)";