/*

  Csu213, Wednesday 3/14/07

  I suggest looking at these notes in a program (editor) with good syntax
    highlighting... makes them *much* easier to read.

  We continue with stuff from last time, and expand on what was
    covered in lab...

  Here are some versions of terms we expect you to know:

    Generics: Abstraction over datatypes
      - Type Parameters: 'arguments' to our abstraction. Eg. for our
          usual list example:

              interface AList<T>{ ... }

          "T" is the type parameter.  When we 'instantiate' the List
          type, say AList<Book> then the T becomes Book (so Book in
          this type expression is in some ways also a type parameter)

    Mutation: Modification of instance fields 'in place' (without
      creating new Objects) [also called 'side-effects']

    Function Objects: Used to 'wrap' functions in Java, since everything
      is an Object (data + code), we create one with a function interface
      and no data.

    Wrapper Classes: There are a few definitions of this phrase... in this
      we will use... Classes which are used to 'wrap' mutation of immutable
      structures. Eg. we will keep our list structures as before... immutable,
      but will wrap them into (say) a Student class which will use its 
      'courseList' field to hold what seems (from the outside) to be a 
      mutable list.


  Now that those definitions are out of the way, we'll pick up where lab
    left off.  Our lovely generic list, and a generic 'filter' function.

  Remember from last lecture the mention of Traversal as well... I'll
    define it when we get there, but the implementation will be here
    in these list classes.
*/

// Your favorite Book class
class Book{
    String author;
    String title;
    int year;

    public Book(String author, String title, int year){
        this.author = author;
        this.title = title;
        this.year = year;
    }

    public String toString(){ return "Book( \""+author+"\", \""+title+"\", "+year+")"; }
}

// Our usual Selector interface
interface ISelect<T>{ boolean select(T t); }

// Generic List Union
abstract class AList<T> implements Traversal<T>{
    // Filter out this List-of T based on a Selector (true means 'keep')
    public abstract AList<T> filter(ISelect<T> pick);

    // Add a T to this List-of T
    public AList<T> add(T t){ return new ConsList<T>(t, this); }    

    // These will make the output look a little better...
    // The first is an override of the builtin toString(), the second
    //   will indent for each Cons, so it indents reasonably
    public String toString(){ return toString("             "); }
    abstract String toString(String acc);

    // ** Note that isEmpty(), getFirst() and getRest() are also added 
    //      (abstractly) to this class by the 'implementation' of Traversal
}

// Represents an Empty List of T
class MtList<T> extends AList<T>{
    // Basic Constructor: Note that if I left this out, the 
    //   default constructor would be created, which takes no
    //   arguments.  In this case it's actually what we want
    public MtList(){}

    // Filter based on the given selector... nothing to filter out
    public AList<T> filter(ISelect<T> pick){ return this; }

    // Traversal functions so that things like 'filter' can be
    //   written without disturbing the list classes
    public boolean isEmpty(){ return true; }
    public T getFirst(){ throw new NoFirstElementException(); }
    public Traversal<T> getRest(){ throw new NoRestElementException(); }

    // Just add the indentation to our simple string
    String toString(String acc){ return acc+"Mt()"; }
}


// Represents a Non-empty List of T
class ConsList<T> extends AList<T>{
    T first;
    AList<T> rest;

    // Basic Constructor
    public ConsList(T first, AList<T> rest){
        this.first = first;
        this.rest = rest;
    }

    // Filter (internal implementation) based on the given selector...
    public AList<T> filter(ISelect<T> pick){ 
        if(pick.select(first))
            return new ConsList<T>(first, rest.filter(pick));
        else
            return rest.filter(pick);
    }

    // Traversal functions so that things like 'filter' can also be
    //   written without disturbing the list classes
    public boolean isEmpty(){ return false; }
    public T getFirst(){ return first; }
    public Traversal<T> getRest(){ return rest; }

    String toString(String acc){ 
        return acc+"Cons( "+first+", \n"+rest.toString(acc+"    ")+")";
    }
}

// An ISelect for 'Old' Books
class OldBook implements ISelect<Book>{
    // Remember here that the default constructor is created with
    //   no arguments
    public boolean select(Book b){ return b.year < 1950; }
}


// Some Uses/Examples/Tests of our new Methods/Classes
class BookExamples{
    Book book1 = new Book("Jim", "The Oldest Book", 1932);
    Book book2 = new Book("John", "Mid 20th Century", 1947);
    Book book3 = new Book("Julie", "Very Late 20th Century", 1998);
    Book book4 = new Book("Jen", "The Newest book", 2007);
}

class ListExamples{
    AList<Book> mt, oneOld, oneNew, three, four;

    ListExamples(BookExamples books){ 
        mt = new MtList<Book>();
        oneOld = mt.add(books.book2);
        oneNew = mt.add(books.book3);
        three = mt.add(books.book2).add(books.book1).add(books.book4);
        four = three.add(books.book3);
    }

    public String toString(){
        return ("\n        mt = \n"+mt+
                "\n    oneOld = \n"+oneOld+
                "\n    oneNew = \n"+oneNew+
                "\n     three = \n"+three+
                "\n      four = \n"+four+"\n");
    }
}


/*
   Now for the Traversals... 

   Lists lend themselves very easily (as you have seen above) to these 
     types of Traversals.  

   We can also have Binary Search trees which satisfy the interface and we
     can write generic code which will then operate on any Traversal.  Try 
     it on your own... if you get stuck see your friendly TAs

   First we define the interface and our own exceptions which were taken
     on faith before...
*/

// Throw when No 'First' Element
class NoFirstElementException extends RuntimeException{
    public NoFirstElementException(){ super("No First Element"); }
}

// Throw when No 'Rest' Element
class NoRestElementException extends RuntimeException{
    public NoRestElementException(){ super("No Rest Element"); }
}

// Represents a generic 'linear' traversal
interface Traversal<T>{
    boolean isEmpty();
    T getFirst();
    Traversal<T> getRest();
}

/*
   Now we can define an Algorithm 'library' class which implements some of the
     things now external to our List classes.

   Note, that we give type parameters on the _methods_ *not* on the _class_. The
     syntax is a little different; the parameter comes after any modifiers
     (public/static/abstract etc...) and the rest follows as usual. The parameter
     is only usable within the method... not the whole class.  I made the parameters
     of all the methods different to illustrate this.

*/

// Wraps our static Traversal based algorithms
class Algorithm{
    // Filter the Traversal based on the given Selector
    static <T> AList<T> filter(Traversal<T> tr, ISelect<T> pick){
        if(tr.isEmpty()) return new MtList<T>();
        else
            if(pick.select(tr.getFirst()))
                return new ConsList<T>(tr.getFirst(), filter(tr.getRest(), pick));
            else
                return filter(tr.getRest(), pick);
    }

    // Reverse a generic Traversal into a List
    static <U> AList<U> reverse(Traversal<U> tr){
        return reverseAcc(tr, new MtList<U>());
    }
    // Update or Return the accumulator to reverse the Traversal
    static <S> AList<S> reverseAcc(Traversal<S> tr, AList<S> acc){
        if(tr.isEmpty()) return acc;
        else 
            return reverseAcc(tr.getRest(), new ConsList<S>(tr.getFirst(), acc));
    }
}


public class notes_3_14_07{
    public static void print(String s){ System.out.println(s); }
    public static void main(String args[]){
        BookExamples books = new BookExamples();
        ListExamples lists = new ListExamples(books);
        OldBook old = new OldBook();

        String head = "\n   lists.";
        print("\n**************\nList Examples:");
        print(lists.toString());

        head = "\n   Alg.reverse(lists.";
        print("\n**************\nExternal (Traversal) Reverse Tests:");
        print(head+"mt, old) = \n"+Algorithm.reverse(lists.mt));
        print(head+"oneOld, old) = \n"+Algorithm.reverse(lists.oneOld));
        print(head+"oneNew, old) = \n"+Algorithm.reverse(lists.oneNew));
        print(head+"three, old) = \n"+Algorithm.reverse(lists.three));
        print(head+"four, old) = \n"+Algorithm.reverse(lists.four));

        print("\n**************\nInternal Filter Tests:");
        print(head+"mt.filter(old) = \n"+lists.mt.filter(old));
        print(head+"oneOld.filter(old) = \n"+lists.oneOld.filter(old));
        print(head+"oneNew.filter(old) = \n"+lists.oneNew.filter(old));
        print(head+"three.filter(old) = \n"+lists.three.filter(old));
        print(head+"four.filter(old) = \n"+lists.four.filter(old));

        head = "\n   Alg.filter(lists.";
        print("\n**************\nExternal (Traversal) Filter Tests:");
        print(head+"mt, old) = \n"+Algorithm.filter(lists.mt, old));
        print(head+"oneOld, old) = \n"+Algorithm.filter(lists.oneOld, old));
        print(head+"oneNew, old) = \n"+Algorithm.filter(lists.oneNew, old));
        print(head+"three, old) = \n"+Algorithm.filter(lists.three, old));
        print(head+"four, old) = \n"+Algorithm.filter(lists.four, old));


        /*
           Finally we give a few examples of Java's Exception mechanism

        */

        print("\n**************\nException Demo:\n");
        Traversal<Book> mtTr = lists.mt;
        Traversal<Book> oneTr = lists.oneOld;

        try{// Throws NoFirstElementException
            mtTr.getFirst();
            print("    1 : will *not* be printed! [ No exception ]");
        }catch(NoFirstElementException ex1){
            print("    2 : *will* be printed! ["+ex1+"]");
        }

        try{// Throws NoRestElementException
            mtTr.getRest();
            print("    3 : will *not* be printed! [ No exception ]");
        }catch(NoFirstElementException ex2){
            print("    4 : will *not* be printed! ["+ex2+"]");
        }catch(NoRestElementException ex3){
            print("    5 : *will* be printed! ["+ex3+"]");
        }

        try{// ** No Exception will be thrown Here!
            oneTr.getRest();
            print("    6 : *will* be printed! [ No exception ]");
        }catch(NoRestElementException ex4){
            print("    7 : will *not* be printed! ["+ex4+"]");
        }

        try{// Throws NoFirstElementException
            oneTr.getRest().getFirst();
            print("    8 : will *not* be printed! [ No exception ]");
        }catch(NoRestElementException ex5){
            print("    9 : will *not* be printed! ["+ex5+"]");
        }catch(RuntimeException ex6){
            print("   10 : *will* be printed! ["+ex6+"]");
        }

        /*
            If we happen to call a method which throws an exception, then Java
              'Jumps' us out to the nearest enclosing 'try' with a 'catch' block
              which can handle the given type of Exception
        */

        try{// Throws NoFirstElementException a little 'deeper'
            badMethod(mtTr);
            print("   11 : will *not* be printed! [ No exception ]");
        }catch(NoFirstElementException ex7){
            print("   12 : *will* be printed! ["+ex7+"]");
        }

        /*
            If a method declares to throw an Exception (not a RuntimeException) then
              Java requires we put it in a 'try' block with a 'catch' that will
              handle the expected (possible) exception.

            Try commenting out the try and catch below to see what Java says...
        */

        try{
            mayThrowException();
        }catch(Exception ex8){ /* Do nothing */  }
    }

    // Calls getFirst() blindly without checking isEmpty() first
    static void badMethod(Traversal<Book> tr){
        tr.getFirst();
    }

    // Declares to throw an Exception, which causes the compiler to give an
    //   error if it is not handled (caught) correctly. sub-Exceptions which
    //   inherit from RuntimeExceptions do not require this.
    static void mayThrowException() throws Exception{
        // This basically does nothing
        if(false)throw new Exception();
    }
}