/*
 * Created on Jan 31, 2005
 * @author James Wirth
 * Internal documentation by Karl Abrahamson
 */

import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;

public class Scanner extends Reader {

  //===========================================================
  //                    Constructors
  //===========================================================
  // Three constructors are provided.
  //
  // 1. Create a scanner that reads from a given reader.
  // 2. Create a scanner that reads from a given input stream.
  // 3. Create a scanner that reads from the standard input.
  //============================================================

  Scanner(Reader rdr) 
  {
    reader = rdr;
    text = new char[bufferSize];
    text[0] = 0;  // nonexistent backup character
    pos = max = 0;
    workBuffer = new StringBuffer();
  }

  Scanner(InputStream is) 
  {
    this(new InputStreamReader(is));
  }

  Scanner() 
  {
    this(System.in);
  }

  //=========================================================
  //                  Variables and constants
  //=========================================================
  // Characters are read from the reader in blocks for
  // efficiency, and are stored into the buffer, text.
  //
  // When we need a character, we get it from the buffer.
  // Variable pos tells the index of the next character to get.
  // Variable max tells the number of characters that are in
  // the text buffer.
  //
  // If the buffer gets empty, we fill it again.
  //
  // Variable workBuffer is used internally to methods to
  // build up strings as characters are read from the buffer.
  // It is made an instance variable so that it does not need
  // to be created over and over.
  //=========================================================

  Reader reader;
  static final int bufferSize = 512;
  char[] text;
  int pos, max;
  StringBuffer workBuffer;
  
  //=========================================================
  //                Support functions for characters
  //                (These are private to this package)
  //=========================================================
  // These functions classify characters.
  //   isDigit      - true on a digit
  //   isAlpha      - true on a letter
  //   isAlnum      - true on a letter or a digit
  //   isWhiteSpace - true on any white-space character
  //
  // These functions only work for the ASCII subset of Unicode.
  //=========================================================
  
  static boolean isDigit(int ch) 
  {
    return ch>='0' && ch<='9';
  }

  static boolean isAlpha(int ch) 
  {
    if(ch<'A') return false;
    if(ch<='Z') return true;
    if(ch<'a') return false;
    return ch<='z';
  }

  static boolean isAlnum(int ch) 
  {
    return isAlpha(ch) || isDigit(ch);
  }

  static boolean isWhiteSpace(int ch) 
  {
    return ch==' ' || ch=='\t' || ch=='\n' || ch=='\r';
  }

  //=========================================================
  //                          close
  //=========================================================
  // close() closes the reader.  Call it when done.
  //=========================================================

  public void close() throws IOException 
  { 
    reader.close(); 
  }

  //=========================================================
  //                     eof
  //=========================================================
  // eof() returns true if the scanner is at the end of
  // the input.
  //=========================================================

  public boolean eof()
  {
    try
    {
      int c = read();
      if(c < 0) return true;
      backup();
      return false;
    }
    catch(IOException ex)
    {
      throw new Error("ConsoleInput" + ex.getMessage());
    }
  }

  //=========================================================
  //                read(char[], int, int)
  //=========================================================
  // read(buf, frm, len) reads up to len characters from the
  // reader and stores them into array buf, starting at index frm.
  // 
  // There might not be len characters available.  The return
  // value is the actual number of characters that were read.
  //=========================================================
  
  public int read(char[] buf, int frm, int len) throws IOException 
  {
    return reader.read(buf,frm,len);
  }

  //=========================================================
  //                      read()
  //=========================================================
  // read() reads a single character from the buffer, 
  // refilling the buffer if necessary.
  //
  // It returns the code of the character, as an integer,
  // or -1 if there are no more characters available.
  //
  // NOTE: read() skips over \r characters, and does not 
  // return them.
  //=========================================================

  public int read() throws IOException 
  {
    if(pos<max) 
    {
      char ch = text[pos++];
      if(ch=='\r') return read();
      return ch;
    }

    // Putting the previously read character into text[0] allows
    // the backup method to back up one character.

    if(max>1) text[0] = text[max-1];

    pos = 1;
    int nrd = reader.read(text,1,bufferSize-1);
    max = pos+nrd;
    if(nrd<=0)  // EOF
    {
      return -1;
    }
    char ch = text[pos++];
    if(ch=='\r') return read(); 
    return ch;
  }

  //=========================================================
  //                      backup
  //=========================================================
  // backup() puts a character back into the input so that
  // it will be read again.  This is only guaranteed to work
  // once.  That is, after you have backed up a character,
  // you cannot back up again until you read a character.
  //=========================================================

  public void backup() throws IOException 
  {
    if(--pos<0) throw new IOException("ConsoleInput: backed up too far");
  }

  //=========================================================
  //                          skipBlanks
  //=========================================================
  // skipBlanks() reads white space characters until it hits
  // a non-white-space character or the end of the file.
  //
  // The return value is the first non-white-space character
  // encountered (as an integer code) or -1 if the end of
  // input was reached.
  //=========================================================

  int skipBlanks() throws IOException 
  {
    int ch;
    while(true) 
    {
      ch = read();
      if(ch<0) return ch;
      if(!isWhiteSpace(ch)) return ch;
    }    
  }

  //=========================================================
  //                      nextChar()
  //=========================================================
  // nextChar() reads a single character, except that it
  // skips over \r.  It throws an error if there is no 
  // character available.
  //=========================================================

  public char nextChar() 
  {
    try 
    {
      int ch = read();
      if(ch<0) 
      {
       throw new IOException("ConsoleInput: reading character past end of file");
      }
      return (char) ch;
    } 
    catch(IOException ex) 
    { 
      throw new Error("ConsoleInput: "+ex.getMessage());
    }
  }

  //=========================================================
  //                        nextInt
  //=========================================================
  // nextInt() reads an integer.  It throws an error if
  // there is no integer present next.
  //=========================================================

  public int nextInt() {
    try {
      int v = 0;
      boolean sign = false;
      int ch = skipBlanks();
      if(ch<0) 
      {
        throw new Error("ConsoleInput: reading number past end of file");
      }
      if(ch=='-') 
      { 
        sign=true; 
        ch = read(); 
      }
      if(!isDigit(ch)) 
      {
        throw new Error("ConsoleInput: cannot start reading number");    
      }
      do 
      { 
        v = 10*v + (ch-'0');
        ch = read();
      } while(isDigit(ch));

      backup();
      return (sign) ? -v : v; 
    } 
    catch(IOException ex) 
    { 
      throw new Error("ConsoleInput: "+ex.getMessage());
    }
  }

  //=========================================================
  //                        nextDouble
  //=========================================================
  // nextDouble() reads a real number.  It throws an error if
  // if is not possible to read a real number.
  //=========================================================

  public double nextDouble() 
  {
    try 
    {
      workBuffer.setLength(0);
      int ch = skipBlanks();
      if(ch=='-') 
      { 
        workBuffer.append((char)ch); 
        ch = read(); 
      }

      //-------------------------------------------
      // Read the part before the decimal point.
      //-------------------------------------------

      while(isDigit(ch)) 
      { 
        workBuffer.append((char)ch); 
        ch = read(); 
      }

      //-------------------------------------------
      // Read the part after the decimal point.
      //-------------------------------------------

      if(ch=='.') {
        workBuffer.append((char)ch); 
        ch = read();
        while(isDigit(ch)) 
        { 
          workBuffer.append((char)ch); 
          ch = read(); 
        }      
      }

      //-------------------------------------------
      // Read the part before the exponent part.
      //-------------------------------------------


      if(ch=='e' || ch=='E') 
      {
        workBuffer.append((char)ch); 
        ch = read();
        if(ch=='-') 
        { 
          workBuffer.append((char)ch); 
          ch = read(); 
        }
        while(isDigit(ch)) 
        { 
          workBuffer.append((char)ch); 
          ch = read(); 
        }      
      }

      //----------------------------------------------------------
      // Now convert the string in the working buffer to double.
      //----------------------------------------------------------

      try 
      {
         return Double.parseDouble(workBuffer.toString());
      } 
      catch(Exception ex) 
      {
        throw new Error("ConsoleInput: Cannot read real number");
      }
    } 
    catch(IOException ex) 
    { 
      throw new Error("ConsoleInput: "+ex.getMessage());
    }
  }

  //=========================================================
  //                        nextLine
  //=========================================================
  // nextLine() reads one line and returns it.  The newline
  // character is not part of the string.
  // 
  // nextLine throws an error if it is not possible to read
  // a line.
  //=========================================================

  public String nextLine() 
  {
    try 
    {
      workBuffer.setLength(0);
      int ch;
      while(true) 
      {
        ch = read();
        if(ch<0 || ch=='\n') break;
        workBuffer.append((char)ch);
      }
      if(ch<0) backup();
      return new String(workBuffer);
    } 
    catch(IOException ex) 
    { 
      throw new Error("ConsoleInput: "+ex.getMessage());
    }
  }

  
  //=========================================================
  //                      charRepres
  //               (private to this package)
  //=========================================================
  // charRepres(ch) returns a string that describes what 
  // the character with code ch represents.
  //=========================================================

  String charRepres(int ch) {
    if(ch<0) return "EOF";
    if(ch>' ') return ""+(char)ch;
    return "\\x"+Integer.toHexString(ch);
  }

  //=========================================================
  //                      trimEnd
  //=========================================================
  // trimEnd(s) returns the string that results by removing
  // all spaces from the end of s.
  //=========================================================

  public static String trimEnd(String s) 
  {
    int k; 
    for(k=s.length()-1; k>=0; --k)
    {
      if(s.charAt(k) != ' ') break;
    }
    return s.substring(0, k+1);
  }

  //=========================================================
  //                   nextWord
  //=========================================================
  // nextWord() reads a word and returns it.  A word is
  // defined to be a sequence of letters and digits that
  // starts with a letter.
  //
  // This function first skips white space, then reads
  // as many characters as possible to make the word.
  //
  // If it is not possible to read a word, then nextWord
  // throws an errorr.
  //=========================================================

  public String nextWord() 
  {
    try 
    {
      workBuffer.setLength(0);
      int ch = skipBlanks();
      if(!isAlpha(ch)) throw new Error("Console Input: Cannot read word");
      do {
        workBuffer.append((char)ch);
        ch = read();
      } while(isAlnum(ch));
      backup();  // the word delimiter
      return workBuffer.toString();
    } 
    catch(IOException ex) 
    { 
      throw new Error("ConsoleInput: "+ex.getMessage());
    }
  }

  //=========================================================
  //                      next
  //=========================================================
  // next() reads a string up to a white space character.
  //
  // Initial white space is not skipped.  If the input
  // begins with a white space character, then next() will
  // return a string holding just that white space character.
  //=========================================================

  public String next() 
  {
    try 
    {
      workBuffer.setLength(0);
      int ch = read();
      if(ch<0) throw new Error("Console Input: Cannot read next");
      if(isWhiteSpace(ch)) 
      {
	return "" + (char) ch;
      }
      else 
      {
        do 
        {
          workBuffer.append((char)ch);
          ch = read();
        } while(!isWhiteSpace(ch));
        backup();  // the word delimiter
        return workBuffer.toString();
      }
    } 
    catch(IOException ex) 
    { 
      throw new Error("ConsoleInput: "+ex.getMessage());
    }
  }

}