/*

  Csu213, Thursday 3/15/07

  Again I suggest reading these notes in a good syntax-highlighted editor.

  We continue the interfaces (traversals etc.) from last time and keep
    our (new) favorite generic List classes...

  Once we get the definitions out of the way, we can start on some new
    stuff.  First we define our usual interfaces, Lists, and Traversals.

*/

// For Later On...
import java.util.ArrayList;
import java.util.Random;

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


// ISame, incase we need it
interface ISame<T>{ boolean same(T t); }


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

// Generic List Union
interface AList<T> extends Traversal<T>{
    // ** 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> implements AList<T>{
    // Basic Constructor
    public MtList(){}

    // 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(); }

    public String toString(){ return "Mt()"; }
}


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

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

    // 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; }

    public String toString(){ return "Cons( "+first+", "+rest+")"; }
}

// 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"); }
}

// First attempt at a generic filter algorithm
class Alg1{
    // 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);
    }
}

/*

  One thing to notice about the filter function above is that it can only
    produce a List.  We can change/fix this by creating a new interface
    for DataSets which can be added to.

*/

// Interface for a collection of data which can be added to and later  traversed
interface DataSet<T>{
    DataSet<T> add(T t);
    Traversal<T> getTraversal();
}

/*

  The reason we need the getTraversal() method is because once we have
    a DataSet, we don't want to just keep adding things to it, so
    we can get a Traversal and do some interesting stuff.

  Now we have to create some DataSets, and a few functions
    which can use them.  What we can do is Wrap existing data structures
    so the interface can be implemented without changing their earlier code

*/

// Wraps an immutable List as a DataSet
class ListWrapper<T> implements DataSet<T>{
    AList<T> list;

    // Clients can only create an empty ListWrapper
    public ListWrapper(){ this(new MtList<T>()); }

    // Private constructor gets passed a List
    private ListWrapper(AList<T> list){ this.list = list; }

    // DataSet Function... add an element to the internal list
    public ListWrapper<T> add(T t){
        return new ListWrapper<T>(new ConsList<T>(t, list));
    }

    // Return the List as a Traversal
    public Traversal<T> getTraversal(){ return list; }
}

/*

  Now for the (seemingly) impossible dream; BSTs...

  We've been talking about how all this stuff abstracts over the data
    structures used, so before we jump to ArrayLists and lots of
    mutation, I'll show you what we mean by general Traversal/DataSet
    with BSTs.

  But, BSTs need a notion of less-than to order elements so we need a
    little more infrastructure first.

*/

// Interface for less than comparison... kinda like ISame
interface LessThan<T>{
    boolean lessThan(T t);
}

// The straight forward BST interface
interface BST<T extends LessThan<T>>{
    // Insert the given T into this BST
    BST<T> insert(T t);

    // Return the Smallest
    T smallest();

    // Chop off the smallest
    BST<T> withoutSmallest();

    // Is this BST a Leaf
    boolean isLeaf();
}

// Represents a non-empty BST
class Node<T extends LessThan<T>> implements BST<T>{
    T data;
    BST<T> left, right;

    // Simple Constructor
    public Node(T d, BST<T> lft, BST<T> rght){
        data = d;
        left = lft;
        right = rght;
    }

    // The usual Insert method... Note: we can have repeated data, it
    //   will just go to the right
    public BST<T> insert(T t){
        if(t.lessThan(data))
            return new Node<T>(data, left.insert(t), right);
        else
            return new Node<T>(data, left, right.insert(t));
    }

    // Return the smallest element == farthest Left
    public T smallest(){
        if(left.isLeaf()) return data;
        else return left.smallest();
    }

    // Remove the smallest element
    public BST<T> withoutSmallest(){
        if(left.isLeaf())return right;
        else 
            return new Node<T>(data, left.withoutSmallest(), right);
    }

    // Definately not a Leaf!
    public boolean isLeaf(){ return false; }
}

// Represents the empty BST
class Leaf<T extends LessThan<T>> implements BST<T>{
    // The Default Constructor is just fine

    // Insert a T into this Leaf
    public BST<T> insert(T t){ return new Node<T>(t, this, this); }

    // No smallest, so we say Error
    public T smallest(){  throw new NoFirstElementException(); }

    // No without smallest, so we say Error
    public BST<T> withoutSmallest(){ throw new NoRestElementException(); }

    // It's a Leaf!
    public boolean isLeaf(){ return true; }
}

/*

  Ok, there's our blessed Binary Search Tree we've been talking so much
    about.  So now how can we use it in some more general algorithms?
    Well, as you may have guessed... we wrap it!

*/

// Wraps a BST so we can use it as a DataSet and/or a Traversal
class BSTWrapper<T extends LessThan<T>> implements DataSet<T>, Traversal<T>{
    BST<T> bst;

    // Public Default Constructor, starts empty
    public BSTWrapper(){ this(new Leaf<T>()); }

    // Public, Wraps a given BST
    public BSTWrapper(BST<T> b){ bst = b; }

    // Add a given T to this BST, and Wrap the result
    public BSTWrapper<T> add(T t){
        return new BSTWrapper<T>(bst.insert(t));
    }

    // Return 'this' as a Traversal
    public Traversal<T> getTraversal(){ return this; }


    // Translation of the BST functions to our Traversal interface
    public boolean isEmpty(){ return bst.isLeaf(); }
    public T getFirst(){ return bst.smallest(); }

    // Here we need to wrap the result again
    public Traversal<T> getRest(){ 
        return new BSTWrapper<T>(bst.withoutSmallest()); 
    }
}

/*  

  Now we can do stuff like implementing filter without using any constructors

*/

// Use our new DataSets to build a completely general filter function
class Alg2{
    // Filter the Traversal into the DataSet
    static <T> DataSet<T> filterAcc(Traversal<T> tr, ISelect<T> pick, DataSet<T> acc){
        if(tr.isEmpty()) return acc;
        else
            return filterAcc(tr.getRest(), pick, updateAcc(pick, tr.getFirst(), acc));
    }

    // Update the accumulator if the given T is to be selected
    static <T> DataSet<T> updateAcc(ISelect<T> pick, T that, DataSet<T> acc){
        if(pick.select(that)) return acc.add(that);
        else return acc;
    }
}

/*

  So on to ArrayLists. Using our new-found interfaces, we can wrap the AL
    but we have to be careful since it relies on side-effects.  The DataSet
    in turn has to use mutation, since the AL does, but we can do our
    Traversal without it, assuming no one is removing from our list while
    we are traversing.

*/

// Wraps an ArrayList as a DataSet
class ALWrapper<T> implements DataSet<T>{
    ArrayList<T> list;

    // Clients can only create an empty ListWrapper
    public ALWrapper(){ list = new ArrayList<T>(); }

    // DataSet Function... add an element to the internal list
    public ALWrapper<T> add(T t){
        list.add(t);
        return this;
    }

    // Allow access to the internal List
    public ArrayList<T> getList(){ return list; }

    // Return the List as a Wrapped Traversal
    public Traversal<T> getTraversal(){ return new ALTraversal<T>(list); }
}


// Wraps an ArrayList as a Traversal
class ALTraversal<T> implements Traversal<T>{
    ArrayList<T> list;
    int current;

    // Cients can only start at 0
    public ALTraversal(ArrayList<T> lst){ this(lst, 0); }

    // Private, Creates a Traversal starting at a given index
    private ALTraversal(ArrayList<T> lst, int curr){ 
        list = lst;
        current = curr; 
    }

    // Are we at the end of the List?
    public boolean isEmpty(){ return current >= list.size(); }

    // Get the current element; it's an error if we're empty
    public T getFirst(){ 
        if(isEmpty())
            throw new NoFirstElementException();
        return list.get(current); 
    }

    // Create a new traversal for the next element
    public Traversal<T> getRest(){ 
        if(isEmpty())
            throw new NoRestElementException();
        return new ALTraversal<T>(list, current+1);
    }
}

/*

  Because we have all these great general interfaces and implementations
    guess what we can do?  We can write General Tests!!  Really we can 
    write general everything, but I'll show you some interesting
    things we can do with these interfaces.

  First we define a simple IntWrapper which implements LessThan then a
    few simple but interesting ISelects to test.

*/

// Wraps an integer so we can compare it using LessThan
class IntWrap implements LessThan<IntWrap>, ISame<IntWrap>{
    int i;
    IntWrap(int i){ this.i = i; }

    // LessThan Interface
    public boolean lessThan(IntWrap that){ return this.i < that.i; }

    // ISame Interface
    public boolean same(IntWrap that){ return this.i == that.i; }

    // Common toString()
    public String toString(){ return ""+i; }
}

class Greater implements ISelect<IntWrap>{
    int cutoff;

    Greater(int c){ cutoff = c; }
    public boolean select(IntWrap i){ return i.i > cutoff; }
}

class Even implements ISelect<IntWrap>{
    public boolean select(IntWrap i){ return ((i.i % 2) == 0); }
}

/*

  Now here comes the meat of what we can do... these are very general 
    functions which produce DataSets and do some reasonably cool stuff 
    without ever knowing exactly what type of data they are operating
    on.  Notice how easy it is to sort once we have a BST DataSet. Also
    see how we can create some random test data, print it out, and check
    it for equality.

*/


// a few useful functions
class Functions{
    // Accumulate some random numerical data into a DataSet
    static DataSet<IntWrap> fillData(DataSet<IntWrap> acc, int howMany){
        if(howMany <= 0) return acc;
        else
            return fillData(acc.add(randomInt()), howMany-1);
    }
    // Get a Random IntWrap
    static IntWrap randomInt(){
        return new IntWrap(new Random().nextInt(30));
    }

    // Sort a Given Traversal using a BST DataSet
    static <T extends LessThan<T>> DataSet<T> sort(Traversal<T> tr){
        return sortAcc(tr, new BSTWrapper<T>());
    }
    // Use the BST accumulator to collect the stuff the result is then 
    //   a DataSet which can be traversed in the correct order (smallest
    //   to largest)
    static <T extends LessThan<T>> DataSet<T> sortAcc(Traversal<T> tr, BSTWrapper<T> acc){
        if(tr.isEmpty()) return acc;
        else
            return sortAcc(tr.getRest(), acc.add(tr.getFirst()));
    }

    // Print out a list looking representation of a Traversal
    static <T> String toString(Traversal<T> tr){ return "[ "+simpleString(tr)+"]"; }
    private static <T> String simpleString(Traversal<T> tr){
        if(tr.isEmpty()) return "";
        else
            return tr.getFirst()+" "+simpleString(tr.getRest());
    }

    // See if two traversals contain the same oredered elements
    static <T extends ISame<T>> boolean same(Traversal<T> tA, Traversal<T> tB){
        if(tA.isEmpty() && tB.isEmpty()) return true;
        else
            if(tA.isEmpty() || tB.isEmpty()) return false;
            else
                return (tA.getFirst().same(tB.getFirst()) &&
                        same(tA.getRest(), tB.getRest()));
    } 
}

/*

  Finally we show how all this falls togther and how it's all called/constructed.
    I also wrap some of the functions to save typing... that's a recuring theme.

*/

public class notes_3_15_07{
    // We wrap println...
    static void print(String s){ System.out.println(s); }

    // We wrap the Functions.toString so that there's much less typing below
    static String string(DataSet<IntWrap> dat){ 
        return Functions.toString(dat.getTraversal());
    }
    // Same for filter... less typing
    static DataSet<IntWrap> filter(Traversal<IntWrap> tr, ISelect<IntWrap> pick){
        return Alg2.filterAcc(tr, pick, new ListWrapper<IntWrap>());
    }
    // Same for 'same' and 'sort'
    static boolean same(DataSet<IntWrap> dA, DataSet<IntWrap> dB){
        return Functions.same(dA.getTraversal(), dB.getTraversal());
    }
    static DataSet<IntWrap> sort(DataSet<IntWrap> dat){
        return Functions.sort(dat.getTraversal());
    }
    public static void main(String args[]){
        DataSet<IntWrap> list1 = Functions.fillData(new ListWrapper<IntWrap>(), 10);
        DataSet<IntWrap> list2 = Functions.fillData(new ListWrapper<IntWrap>(), 10);
        DataSet<IntWrap> alist1 = Functions.fillData(new ALWrapper<IntWrap>(), 10);
        DataSet<IntWrap> alist2 = Functions.fillData(new ALWrapper<IntWrap>(), 10);

        print("     List Tr : "+string(list1));
        print("   nums > 15 : "+string(filter(list1.getTraversal(), new Greater(15))));
        print("      Sorted : "+string(sort(list1)));

        print("");
        print("     List Tr : "+string(list2));
        print("       Evens : "+string(filter(list2.getTraversal(), new Even())));
        print("      Sorted : "+string(sort(list2)));

        print("");
        print("  ArrList Tr : "+string(alist1));
        print("   nums > 15 : "+string(filter(alist1.getTraversal(), new Greater(15))));
        print("      Sorted : "+string(sort(alist1)));

        print("");
        print("  ArrList Tr : "+string(alist2));
        print("       Evens : "+string(filter(alist2.getTraversal(), new Even())));
        print("      Sorted : "+string(sort(alist2)));

        DataSet<IntWrap> small = Functions.fillData(new ListWrapper<IntWrap>(), 5);
        print("");
        print("                      small : "+string(small));
        print("              sorted(small) : "+string(sort(small)));
        print("         same(small, small) : "+same(small, small));
        print(" same(small, sorted(small)) : "+same(small, sort(small)));
    }
}