import tester.*;
import java.util.*;

class Algorithms {
   
    /*
     Here is a very complicated way of implementing the map function
     for ArrayLists. It uses all that we have learned in Java so far, 
     but is incredibly hard to understand.
     
     In DrRacket, if map has not been provided, we would implement it as follows:
     
     ;; my-map: [Listof T] (f:T -> R) -> [Listof R]
     (define (my-map tlist, fcn)
       (cond
         [(empty? tlist) empty]
         [(cons? tlist) (cons (fcn (first tlist))
                              (my-map (rest tlist) fcn))]))
                              
     The first cond clause defines the base case, 
     the second part, for every item in the list applies the given function
     to each element of the list and accumulates the result with the result
     already computed. (Well, it does it backwards, but you get the idea.)
     
     So, to design a similar method we need to define the BASE CASE, 
     figure out how to UPDATE the result with every new element 
     we extract from the list -- this is the 'Computation' part.
     
     The other part of the 'loop function' is 'Traversal' - here we need to be
     able to know whether to continue or not 
     (the (empty? tlist) CONTINUAION QUESTION)
     and be able to extract CURRENT element and ADVANCE to the remaining items
     in the list.
      
     */
    
    
    // produce an ArrayList from the given one by applying the given function
    // to every object in the given ArrayList
    <R, T> ArrayList<R> map(ArrayList<T> tlist, T2R<T, R> fcn) {
        ArrayList<R> result = new ArrayList<R>();  // BASE CASE
        return mapNext(tlist, fcn, result, 0);
    }
    
    // produce an ArrayList from the given one by applying the given function
    // to every object in the given ArrayList, starting at the given index,
    // and accumulating the given partial result
    <R, T> ArrayList<R> mapNext(ArrayList<T> tlist, T2R<T, R> fcn,
                                ArrayList<R> result, int index) {
        if (tlist.size() == index) {  // CONTINUATION QUESTION
            return result;
        }
        else {  // UPDATE (the next line)
            result.add(fcn.apply(tlist.get(index)));  // CURRENT (tlist.get(index)
            return mapNext(tlist, fcn, result, index + 1); // ADVANCE (index + 1)
        }
    }
    
    /*
     Java provides for us a language construct (statement) that encapsulates the 
     traversal over a typical data structure of elements of the same type.
     It is commonly known as 'for-each loop' and is defined as follows:
     
     for(T t:tlist) {
     
     }
     
     which means that it will extract elements of the type T from the data 
     collection 'tlist' one at a time, and for each of these it will perform
     the statements enclosed in the curly braces.Within the curly braces 
     we can refer to the current element with the variable name 't'.
     
     Of course, the names 'tlist' and 't' are whatever we choose.
     
     Using the 'for-each' loop our method becomes much simpler and is much
     more readable:
     */
    
    // produce an ArrayList from the given one by applying the given function
    // to every object in the given ArrayList
    <R, T> ArrayList<R> mapForEach(ArrayList<T> tlist, T2R<T, R> fcn) {
        ArrayList<R> result = new ArrayList<R>();  // BASE CASE
        for(T t:tlist) {
            result.add(fcn.apply(t)); // UPDATE using CURRENT
        }
        return result;
    }

    
}

// produce an item of the type R from the given item of the type T
interface T2R<T,R> {
    R apply(T t);
}

// produce the length of the given String
class StringLength implements T2R<String, Integer> {
    public Integer apply(String s) {
        return s.length();
    }
}

class ExamplesAlgorithms {
    
    T2R<String, Integer> slength = new StringLength();
    
    Algorithms algo = new Algorithms();
    
    ArrayList<String> slist = new ArrayList<String>();
    ArrayList<Integer> ilist = new ArrayList<Integer>();
    
    void init() {
        slist.clear();
        slist.add("arrivederci");
        slist.add("bye");
        slist.add("ciao");
        slist.add("hello");
        
        ilist.clear();
        ilist.add(11);
        ilist.add(3);
        ilist.add(4);
        ilist.add(5);       
    }
    
    // test the method map in the class Algorithms
    void testMap(Tester t) {
        this.init();
        t.checkExpect(algo.map(this.slist, slength), this.ilist);
        this.init();
        t.checkExpect(algo.mapForEach(this.slist, slength), this.ilist);
    }
    
    public static void main(String[] argv) {
        ExamplesAlgorithms ea = new ExamplesAlgorithms();
        Tester.run(ea);
    }
}