/* Generic List class
 * The contained things are Object, which could be of any type
 * It is expected that a subclass provides its own accessors that
 * convert "thing" and "rest" to the appropriate type.
 *
 * Author:  Ron Cytron
 * Class:   CS101
 */

import cs101.terminal.*;

public class List {

   protected Object thing;
   protected List   rest;

   /*
    *  A subclass will automatically call this default constructor
    *    if no other super constructor is called by you.
    *  So, this constructor is provided as "protected" -- callable
    *    only from subclasses.
    */

   protected List() {
      this.thing = null;
      this.rest  = null;
   }

   /*
    *  Construct a list element with one object
    */

   public List(Object o) {
      this(o,null);
   }

   /*
    *  Construct a list element with one object that points to
    *     "neighbor" as the rest of its list
    */

   public List(Object o, List neighbor) {
      thing = o;
      rest  = neighbor;
   }

   /*
    *  Find the list element that contains the sought-after object
    *  This class is protected---any subclass can use this method.
    *  It is not public because it returns the generic List type.
    *  If a subclass wants to make this method available, it should
    *     define a more specific method that returns the appropriate type
    *     and then call this method to do the actual work, casting
    *     the result before return.
    */

   protected List find(Object sought) {
      for (List c = this; c != null; c = c.rest) {
         if (c.thing.equals(sought)) return(c);
      }
      return(null);
   }

   /*
    *  Find the nth element off of this list.  The first element in
    *      the list, that is "this" counts as element number 1.
    */

   protected List find(int n) {
      List ans = this;
      for (int i=1; i < n; ++i) {
         if (ans != null) ans = ans.rest;
         else return(null);
      }
      return(ans);
   }

   public int cardinality() {
      if (rest != null) return(1 + rest.cardinality());
      else return(1);
   }

   /*
    * duplicate and reverse are list-copying methods that are protected
    *   because their return type is generic.
    */

   protected List duplicate() {
     List remainder;
     if (rest == null) remainder = null;
     else              remainder = rest.duplicate();
     List ans = new List(this.thing, remainder);
     return(ans);
   }

   protected List reverse() {
     List ans = null;
     for (List c = this; c != null; c = c.rest) {
        ans = new List(c.thing, ans);
     }
     return(ans);
   }
         
   public void exchange(Object target) {
      List f = find(target);
      exchange(f);
   }

   public void exchange(List container) {
      if (container != null) {
         Object temp     = this.thing;
         thing           = container.thing;
         container.thing = temp;
       }
   }

  /*
   * Shuffle the list by taking the ith element and exchanging it
   * with a random element in the middle
   */

   public void shuffle() {
      int num = cardinality();
      for (int i=num-1; i>=1; --i) {
         List l1 = find(i);
         int swap = (int) (i * Math.random());
         List l2 = find(swap);
         l1.exchange(l2);
      }
   }

   public String toString() {
      String ans="[";
      for (List c = this; c != null; c = c.rest) {
           ans += c.thing + " ";
      }
      ans += "]";
      return(ans);
   }

   public static void selfTest() {
      Object one = new String("String 1");
      Object two = new String("String 2");
      Object thr = new String("String 3");
      Object fou = new String("String 4");

      List nums = new List(fou, null);
           nums = new List(thr, nums);
           nums = new List(two, nums);
           nums = new List(one, nums);
      List dup  = nums.duplicate();
      List rev  = nums.reverse();
      Terminal.println("\nBegin self test of List");
      Terminal.println("List created:  " + nums);
      nums.shuffle();
      Terminal.println("Shuffle is:    " + nums);
      Terminal.println("Reverse is:    " + rev);
      Terminal.println("Duplicate is:  " + dup);
      Terminal.println("Cardinality is:" + nums.cardinality());
      Terminal.println("End   self test of List\n");
   }

   public static void main(String args[]) { selfTest(); }
}