// 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("This is the OpenList main function.");
    System.out.println("You should write your tests in the OpenListTester class and use JUnit for testing.");

  } // end of main

} // end of the OpenList class