import java.io.StreamTokenizer;
import java.io.Reader;
import java.io.StringReader;
import java.io.IOException;
import java.math.BigInteger;

/**
 * 文字ストリームからリストを読み取る
 */

public class ListReader {

  /*****************/
  /* PRIVATE FIELD */
  /*****************/
  /**
   *  文字ストリームの文字列の語彙解析用
   */
  private final StreamTokenizer t;

  /***************/
  /* CONSTRUCTOR */
  /***************/
  /**
   *  指定された文字ストリーム用のListReaderを生成する。
   */
  public ListReader(Reader r) {
    t = new StreamTokenizer(r);
    t.resetSyntax();
    t.wordChars('!', '~');	// ワード
    t.whitespaceChars('\0', ' '); // 区切り文字
    t.ordinaryChars('(', ')');	// １文字トークン
    t.commentChar(';');		// コメント
    t.quoteChar('\"');		// 文字列
    t.wordChars('#', '#');		// RADIX付き数値
  }

  /*****************/
  /* PUBLIC METHOD */
  /*****************/
  /**
   * アトムまたはリストを一つ読み取る。
   * <p>リストは「(」「)」で囲まれているとする。
   * 末尾がnilでないリストは、ドット表現になっているとする。
   * ただし、「.」の両側にはスペースが必要である。
   * アトムはlong型として解釈可能ならLongAtomに、double型として解釈可能なら
   * DoubleAtomに、それ以外ならStringAtomになる。
   * 強制的にStringAtomにしたいときや、StringAtomにスペースや「(」「)」を
   * 含めたいときは、文字列を""で囲む。
   * ""内ではエスケープシーケンスが認識される。
   * ストリームの終わりが読み込まれたらnull(nilではない)を返す。
   *
   * @return		 入力されたS式表現
   * @exception IOException	入出力エラー
   */
  public Cell read() throws IOException {
    return readList(0, false);
  }

  /**
   * アトムまたはリストを一つ読み取る。
   * <p>read()と同様の機能を持つが、読み込まれた全てのセルは、検索高速化のためハッシュ・テーブルに登録される。
   *
   * @return		 入力されたS式表現
   * @exception IOException	入出力エラー
   */
  public Cell hashingRead() throws IOException {
    return readList(0, true);
  }

  /**
   * 現在の行番号
   * @return	読み込み済の行番号
   */
  public int lineno() {
    return t.lineno();
  }

  /************************/
  /* PUBLIC STATIC METHOD */
  /************************/
  /**
   * 文字列からリストを読み込む
   * @param s		リストを含む文字列
   * @return		読み込まれたリスト
   */
  public static Cell read(String s) {
    ListReader lr = new ListReader(new StringReader(s));
    try {
      return lr.read();
    } catch(IOException e) {
      Util.abort("ListRead: IOException on String");
    }
    return null; // Dummy
  }

  /**
   * 文字列からリストを読み込む
   * @param s		リストを含む文字列
   * @return		読み込まれたリスト
   */
  public static Cell hashingRead(String s) {
    ListReader lr = new ListReader(new StringReader(s));
    try {
      return lr.hashingRead();
    } catch(IOException e) {
      Util.abort("ListRead: IOException on String");
    }
    return null; // Dummy
  }

  /******************/
  /* PRIVATE METHOD */
  /******************/
  /**
   * アトムまたはリストを一つ読み取る。
   * @param contourLevel	現在の構文レベル
   * @return			読み込まれたリスト
   */
  private Cell readList(int contourLevel, boolean hashing) throws IOException {
    t.nextToken();
    if ( t.ttype==StreamTokenizer.TT_EOF ) return null;
    /*
     * 余分な')'を読み飛ばす
     */
    while ( t.ttype==')' ) {
      errMsg("Extra \")\"");
      t.nextToken();
    }
    /*
     * Listの読み込み
     */
    if( t.ttype=='(' ) {
      t.nextToken();
      // 空リスト
      if ( t.ttype==')' ) {
	return List.nil;
      }
      // carがnilのドット対
      if ( t.ttype==StreamTokenizer.TT_WORD && t.sval.equals(".") ) {
	Cell d = readRest(contourLevel, hashing);
	if ( d==null ) return null;
	if ( hashing )
	  return List.hashingCons(List.nil, d);
	else
	  return List.cons(List.nil, d);
      }
      // car部を読み込む
      t.pushBack();
      Cell c = readList(contourLevel+1, hashing);
      if ( c==null ) return null;
      Cell d = readRest(contourLevel, hashing);
      if ( d==null ) return null;
      if ( hashing )
	return List.hashingCons(c, d);
      else
	return List.cons(c, d);
    }
    /*
     * Atomの読み込み
     */
    t.pushBack();
    Cell a = readAtom(contourLevel, hashing);
    if ( a==null ) return null;
    if ( contourLevel!=1 && ((StringAtom)a).topLevel ) {
      errMsg("Unexpected TOPLEVEL atom");
      return null;
    }
    return a;
  }

  /**
   * アトムを読み込む
   * @return	読み込まれたアトム
   */
  private Cell readAtom(int contourLevel, boolean hashing) throws IOException {
    t.nextToken();
    if ( t.ttype==StreamTokenizer.TT_EOF ) {
      errMsg("Unexpected EOF");
      return null;
    }
    /*
     * ダブルクォート記法のチェック
     *
     */
    Util.assert(t.ttype==StreamTokenizer.TT_WORD || t.ttype=='\"',
		"t.ttype==StreamTokenizer.TT_WORD || t.ttype==\'\"\'",
		t.lineno());
    /*
     * Atomの読み込み
     */
    String s = t.sval;
    if ( s.charAt(0)=='#' ) {	// radix付き整数
      int radix, shft;
      switch ( s.charAt(1) ) {
      case 'b':			// 2進数
      case 'B':
	radix = 2;
	shft = 1;
	break;
      case 'o':
      case 'O':
	radix = 8;
	shft = 3;
	break;
      case 'x':			// 16進数
      case 'X':
	radix = 16;
	shft = 4;
	break;
      default:
	errMsg("Number format error: "+s);
	return readList(contourLevel, hashing);
      }
      // 2001/06/25: 加藤
      //   整数値をLongAtomではなく、BigNumAtomで扱うよう修正した。
      //
      //      try {
      //	return List.atom(Long.parseLong(s.substring(2), radix));
      //      } catch(NumberFormatException e) {
      //	try {
      //	  long l = Long.parseLong(s.substring(s.length()-1), radix);
      //	  long u = Long.parseLong(s.substring(2, s.length()-1), radix);
      //	  return List.atom((u<<shft)|l);
      //	} catch(NumberFormatException e1) {
      //	  errMsg("Number format error: "+s);
      //	  return read();
      //	}
      try {
	return List.atom(new BigInteger(s.substring(2), radix));
      } catch(NumberFormatException e) {
	errMsg("Number format error: "+s);
	return read();
      }
    } else {			// その他数値、記号
      // 2001/06/25: 加藤
      //   整数値をLongAtomではなく、BigNumAtomで扱うよう修正した。
      //
      //      try {
      //	return List.atom(Long.parseLong(s)); // 整数
      //      } catch(NumberFormatException e) {
      //	try {
      //	  return List.atom(new Double(s).doubleValue()); // 浮動小数点
      //	} catch(NumberFormatException e1) {
      //	  if ( s.equals("nil") ) return List.nil;	// nil
      //	  return List.atom(s);	// 記号
      //	}
      //      }
      try {
      	return List.atom(new BigInteger(s)); // 整数
      } catch(NumberFormatException e) {
      	try {
      	  return List.atom(new Double(s).doubleValue()); // 浮動小数点
      	} catch(NumberFormatException e1) {
      	  if ( s.equals("nil") ) return List.nil;	// nil
      	  return List.atom(s);	// 記号
      	}
      }
    }
  }

  /**
   * リストのcdr部を読み込む
   * @return	cdr部のリスト
   */
  private Cell readRest(int contourLevel, boolean hashing) throws IOException {
    t.nextToken();
    if ( t.ttype==StreamTokenizer.TT_EOF ) {
      errMsg("Unexpected EOF");
      return null;
    }
    /*
     * Listの読み込み
     */
    if( t.ttype=='(' ) {
      t.pushBack();
      Cell c = readList(contourLevel+1, hashing);
      if ( c==null ) return null;
      Cell d = readRest(contourLevel, hashing);
      if ( d==null ) return null;
      if ( hashing )
	return List.hashingCons(c, d);
      else
	return List.cons(c, d);
    }
    /*
     * リスト終端
     */
    if ( t.ttype==')' ) return List.nil;
    /*
     * ドット対
     */
    if ( t.ttype==StreamTokenizer.TT_WORD && t.sval.equals(".") ) {
	Cell d = readList(contourLevel+1, hashing);
	if ( d==null ) return null;
	t.nextToken();
	if ( t.ttype!=')' ) return null;
	return d;
      }
    /*
     * <atom>+cdrの読み込み
     */
    t.pushBack();
    Cell c = readAtom(contourLevel, hashing);
    if ( c==null ) return null;
    Cell d = readRest(contourLevel, hashing);
    if ( d==null ) return null;
    if ( hashing )
      return List.hashingCons(c, d);
    else
      return List.cons(c, d);
  }

  /**
   * 記法エラー・メッセージ表示
   * @param s	表示メッセージ
   */
  private void errMsg(String s) {
    System.err.println("ListReader: Line "+t.lineno()+": "+s);
  }

}