import java.util.Hashtable;
import java.util.HashMap;
import java.io.IOException;
import java.math.BigInteger;

/**
 * S式の構築や操作のためのメソッドを集めたクラス
 * <P>Cellのサブクラスのインスタンス生成は、すべてListのメソッドを使う。
 * Consセルのcar部、cdr部の参照や変更は、フィールドを直接操作してもよいが、
 * ListあるいはCellのメソッドを使うと便利な場合もある。
 * cdrをとっていった末尾がnilとなるリストだけでなく一般のS式も扱える。
 * <P>アトムの同一性は、==演算子で判定できる。
 * すなわち、同じ値を持つアトムを表すオブジェクトは、唯一である。
 */

public class List implements java.io.Serializable {

  /****************/
  /* PUBLIC FIELD */
  /****************/
  /**
   * nilを表す唯一のオブジェクト。
   */
  public static NilAtom nil = new NilAtom();

  /*****************/
  /* PRIVATE FIELD */
  /*****************/
  /**
   * アトムの同一性管理用ハッシュ・テーブル。
   */
  private static Hashtable atomTable = new Hashtable();

  /**
   * Consの同一性管理用ハッシュ・マップ
   */
  private static HashMap consMap = new HashMap();

  /* デバッグ */
  private static final int debMode = 0;

  /***************/
  /* INITIALIZER */
  /***************/
  /**
   * 再初期化の準備を行う。
   */
  public static void cleanUp() {
    atomTable = new Hashtable();
    consMap = new HashMap();
  }

  /**
   * 再初期化を行う。
   */
  public static void init() {
  }

  /***************/
  /* CONSTRUCTOR */
  /***************/
  /**
   * インスタンスは生成できない。
   */
  private List() {
  }

  /*****************/
  /* PUBLIC METHOD */
  /*****************/

  /*
   * 各種ユーティリティ・メソッド
   */
  /**
   * リストの同一性を判定する。
   * 相異なるセルであっても、構造が同じならtrueとなる。
   * @param x	リスト
   * @param y	リスト
   * @return	同一構造を持つリストならtrue
   */
  public static boolean equal(Cell x, Cell y) {
    while ( x!=y ) {
      if ( x.isAtom() ) return false;
      if ( y.isAtom() ) return false;
      if ( !equal(((Cons)x).car, ((Cons)y).car) ) return false;
      x = ((Cons)x).cdr; y=((Cons)y).cdr;
    }
    return true;
  }

  /*
   * 各種オブジェクトの生成
   */
  /**
   * Consセルを生成し、ハッシュ・テーブルに登録する。
   * <p>car、cdrを使ってハッシュ検索を行い、car、cdr両方の一致するconsセルを検索する。
   * 一致するconsセルが見つからない場合は新規にセルを作成し、ハッシュ・テーブルに登録する。
   * @param car		consセルのcar部
   * @param cdr		consセルのcdr部
   * @return		生成または検索されたconsセル
   */
  public static Cons hashingCons(Cell car, Cell cdr) {
    /* car部でハッシュ検索 */
    HashMap carMap = (HashMap)consMap.get(car);
    if ( carMap==null ) {
      carMap = new HashMap();
      consMap.put(car, carMap);
    }
    /* cdr部でハッシュ検索 */
    Cons c = (Cons)carMap.get(cdr);
    if ( c==null ) {
      c = new Cons();
      c.car = car;
      c.cdr = cdr;
      carMap.put(cdr, c);
    }
    return c;
  }

  /**
   * Consセルを生成する。
   * <p>car、cdrを使ってハッシュ検索を行い、car、cdr両方の一致するconsセルを検索する。
   * 一致するconsセルが見つからない場合はセルの生成だけを行い。ハッシュ・テーブルへの登録は行わない。
   * @param car		consセルのcar部
   * @param cdr		consセルのcdr部
   * @return		生成または検索されたconsセル
   */
  public static Cons cons(Cell car, Cell cdr) {
    /* car部でハッシュ検索 */
    HashMap carMap = (HashMap)consMap.get(car);
    Cons c;
    if ( carMap==null ) {
      c = new Cons();
      c.car = car;
      c.cdr = cdr;
      /* ハッシュ・テーブルへの登録は行わない */
    } else {
      /* cdr部でハッシュ検索 */
      c = (Cons)carMap.get(cdr);
      if ( c==null ) {
	c = new Cons();
	c.car = car;
	c.cdr = cdr;
	/* ハッシュ・テーブルへの登録は行わない */
      }
    }
    return c;
  }

  /**
   * long型の値を持つアトムを生成する。
   * @param v		アトムの値
   * @return		生成または検索long型アトム
   */
  public static LongAtom atom(long v) {
    Long l = new Long(v);
    LongAtom a = (LongAtom)atomTable.get(l);
    if ( a!=null ) return a;
    if ( debMode>=9 ) System.out.println("List: make new long atom: "+v);
    a = new LongAtom(v);
    atomTable.put(l, a);
    return a;
  }

  /**
   * double型の値を持つアトムを生成する。
   * @param v		アトムの値
   * @return		生成または検索double型アトム
   */
  public static DoubleAtom atom(double v) {
    Double d = new Double(v);
    DoubleAtom a = (DoubleAtom)atomTable.get(d);
    if ( a!=null ) return a;
    if ( debMode>=9 ) System.out.println("List: make new double atom: "+v);
    a = new DoubleAtom(v);
    atomTable.put(d, a);
    return a;
  }

  /**
   * String型の値を持つアトムを生成する。
   * @param v		アトムの値
   * @return		生成または検索String型アトム
   */
  public static StringAtom atom(String v) {
    StringAtom a = (StringAtom)atomTable.get(v);
    if ( a!=null ) return a;
    if ( debMode>=9 ) System.out.println("List: make new string atom: "+v);
    a = new StringAtom(v);
    atomTable.put(v,a);
    return a;
  }

  /**
   * String型の値を持つアトムを生成する。
   * @param v		アトムの値
   * @param t		トップレベルに出現可能か
   * @return		生成または検索String型アトム
   */
  public static StringAtom atom(String v, boolean t) {
    StringAtom a = (StringAtom)atomTable.get(v);
    if ( a!=null ) return a;
    if ( debMode>=9 ) System.out.println("List: make new string atom: "+v);
    a = new StringAtom(v, t);
    atomTable.put(v, a);
    return a;
  }

  /**
   * bignum型の値を持つアトムを生成する。
   * @param v		アトムの値
   * @return		生成または検索long型アトム
   */
  public static BigNumAtom atom(BigInteger v) {
    BigNumAtom a = (BigNumAtom)atomTable.get(v);
    if ( a!=null ) return a;
    if ( debMode>=9 ) System.out.println("List: make new bignum atom: "+v);
    a = new BigNumAtom(v);
    atomTable.put(v, a);
    return a;
  }

  /**
   * 中間形式ファイル(バイナリ形式)読み込み時にハッシュテーブル登録処理を行う。
   * @param c		ハッシュテーブルに登録するCONSセル
   */
  public static void entryCons(Cons c) {
    Cell car = c.car, cdr = c.cdr;
    /* car部でハッシュ検索 */
    HashMap carMap = (HashMap)consMap.get(car);
    if ( carMap==null ) {
      if ( debMode>=9 ) System.out.println("List: entryCons: new carMap: "+c);
      carMap = new HashMap();
      consMap.put(car, carMap);
    }
    /* cdr部でハッシュ検索 */
    if ( !carMap.containsKey(cdr) ) {
      if ( debMode>=9 ) System.out.println("List: entryCons: "+c);
      carMap.put(cdr, c);
    }

  }

  /**
   * 中間形式ファイル(バイナリ形式)読み込み時にハッシュテーブル登録処理を行う。
   * @param a		ハッシュテーブルに登録するアトム
   */
  public static void entryLongAtom(LongAtom a) {
    Long l = new Long(a.value);
    if ( !atomTable.containsKey(l) ) {
      if ( debMode>=9 ) System.out.println("List: entryLongAtom: "+a);
      atomTable.put(l, a);
    }
  }

  /**
   * 中間形式ファイル(バイナリ形式)読み込み時にハッシュテーブル登録処理を行う。
   * @param a		ハッシュテーブルに登録するアトム
   */
  public static void entryDoubleAtom(DoubleAtom a) {
    Double d = new Double(a.value);
    if ( !atomTable.containsKey(d) ) {
      if ( debMode>=9 ) System.out.println("List: entryDoubleAtom: "+a);
      atomTable.put(d, a);
    }
  }

  /**
   * 中間形式ファイル(バイナリ形式)読み込み時にハッシュテーブル登録処理を行う。
   * @param a		ハッシュテーブルに登録するアトム
   */
  public static void entryStringAtom(StringAtom a) {
    if ( !atomTable.containsKey(a.value) ) {
      if ( debMode>=9 ) System.out.println("List: entryStringAtom: "+a);
      atomTable.put(a.value, a);
    }
  }

  /**
   * 中間形式ファイル(バイナリ形式)読み込み時にハッシュテーブル登録処理を行う。
   * @param a		ハッシュテーブルに登録するアトム
   */
  public static void entryBigNumAtom(BigNumAtom a) {
    if ( !atomTable.containsKey(a.value) ) {
      if ( debMode>=9 ) System.out.println("List: entryBigNumAtom: "+a);
      atomTable.put(a.value, a);
    }
  }

}