// OpenList.java
// Name:
// Date:
// Comments


/* OpenList is an open linked list that can hold any Java Objects as data
 */
class OpenList
{
  // the data members are private, only
  // to be accessed by the class itself
  private Object first;
  private OpenList rest;

  /**  this is _the_ empty list
    *  there is only one, because it is static*/
  public static OpenList emptyList = new OpenList(null,null);

  /** method: OpenList constructor
    * It is equivalent to a static call to cons */
  public OpenList(Object first, OpenList rest)
  {
    this.first = first;
    this.rest = rest;
  }

  /** method: isEmpty
   *  inputs: none
   *  outputs: true if the calling list is empty; false otherwise
   */
  public boolean isEmpty()
  {
    return first == null && rest == null;
  }

  /** method: isEmpty, static version
   *  inputs: an OpenList, L
   *  outputs: true if the input list is empty; false otherwise
   */
  public static boolean isEmpty(OpenList L)
  {
    return L.isEmpty(); 
  }

  /** method: printItems()
   *  inputs: none
   *  outputs: a String representing the items of this OpenList
   */
  private String printItems()
  {
    if (this.isEmpty())
    {
      return "";
    }
    else if (this.rest.isEmpty())   // handle the case of 1 element
    {
      return this.first.toString(); // so that there is no extra comma
    }
    else
    {
      return "" + this.first + ", " + this.rest.printItems();
    }
  }

  /** method: toString
   *  inputs: none
   *  outputs: a string representing this OpenList
   */
  public String toString()
  {
    String output = "[" + this.printItems() + "]";
    return output;
  }

  /** method: assoc (static)
   *  inputs: an Object o and an OpenList DB, which must
   *          contain sublists as elements
   *  outputs: the element of DB that contains o as its
   *           first element OR, if no such element exists,
   *           the empty list.
   */
  public static OpenList assoc(Object o, OpenList DB)
  {
    if (DB.isEmpty())
    {
      return OpenList.emptyList;
    }

    /*
       * Warning: this line includes what is known as a "cast"
       *          It is the (OpenList) to the left of (DB.first)
       *
       *          This cast is a mechanism for telling Java that 
       *          _you_ are sure the object DB.first is of type OpenList.
       *
       *          After all, the compiler is only sure that DB.first
       *          is an Object, not necessarily an OpenList.
       */
    OpenList firstOfDB = (OpenList)(DB.first);

    if (o.equals( firstOfDB.first ))
    {
      return firstOfDB;
    }

    return OpenList.assoc(o,DB.rest);
  }

  /** method: assoc (nonstatic)
   *  inputs: an Object o and an OpenList DB, which must
   *          contain sublists as elements
   *  outputs: the element of DB that contains o as its
   *           first element OR, if no such element exists,
   *           the empty list.
   */
  public OpenList assoc(Object o)
  {
    return OpenList.assoc(o,this);
  }



  /** method: main, the starting point for this class's tests
   *  inputs: a String array not being used right now
   *  outputs: none
   */
  public static void main(String[] args)
  {
    System.out.println("Starting main...");

    /* tests for the constructors
    */
    OpenList greet1 = new OpenList( "Hello", OpenList.emptyList );
    OpenList greet2 = new OpenList( "Hey", greet1 );
    System.out.println(greet1); // should be ["Hello"]
    System.out.println(greet2); // should be ["Hey", "Hello"]

    /* more tests for the constructors
    */
    OpenList numericStrings = OpenList.emptyList;
    System.out.println("numericStrings is " + numericStrings); // should be []
    for (int i=0 ; i<5 ; ++i)
    {
      numericStrings = new OpenList( i , numericStrings );
    }
    System.out.println("numericStrings is " + numericStrings); // should be [4, 3, 2, 1, 0]

    /* Be sure to include tests for all of your methods here !!
    */

    /*
     * creation of an association list
     * This would be much easier if we had written cons already...
     */
    OpenList sublist1 = new OpenList( "jan", new OpenList( 31, emptyList ));
    OpenList sublist2 = new OpenList( "feb", new OpenList( 28, emptyList ));
    OpenList sublist3 = new OpenList( "mar", new OpenList( 31, emptyList ));

    OpenList DB = new OpenList( sublist3, emptyList );
    DB = new OpenList( sublist2, DB );
    DB = new OpenList( sublist1, DB );

    System.out.println("DB is\n" + DB);
    System.out.println("assoc(\"feb\",DB) is " + assoc("feb",DB));
    System.out.println("assoc(\"sep\",DB) is " + assoc("sep",DB));

    System.out.println("DB is\n" + DB);
    System.out.println("DB.assoc(\"feb\") is " + DB.assoc("feb"));
    System.out.println("DB.assoc(\"sep\") is " + DB.assoc("sep"));

    System.out.println("Finishing main...");
  } // end of main

} // end of the OpenList class