import java.lang.*;
import java.util.*;



public class ListTester {

    private List l;
    private ArrayList al;
    String expected;
    final String initContents = "ABCDEFGHIJ";
    final String illegalElements = "#$%"; // these should never show up in the list
    
    
    
    public ListTester() 
    {
        expected = "";
        l = null;
    }
    

    private void insert(int index, String s) 
    {
        int n = index;
        
        for (int i = 0; i < s.length(); i++) {
            l.add(n++, s.substring(i,i+1));
        }
        if (index == 0) 
            expected = s + expected;
        else
            expected = expected.substring(0, index) + s + expected.substring(index);
    }
    
            
    void initList() 
    {
        l = newList();
        

        for (int i = 0; i < initContents.length(); i++) {
            l.add(initContents.substring(i,i+1));
        }
        expected = initContents;
        insert(3, "STUV");
    }
    
    private List copyList(int stride) 
    {
        List copy = newList();
        
        Iterator i = l.iterator();
        int cnt = 0;
        
        while (i.hasNext()) {
            Object o = i.next();
            if (cnt++ % stride == 0) 
                copy.add(o);
        }
        return copy;
    }
    


    void printList() 
    {
        Iterator i = l.iterator();
        System.out.println("LIST: (sz=" + l.size() + "):");
        while (i.hasNext()) {
            System.out.print(i.next());
        }
        System.out.println();
    }
    
        
    boolean validatePosition(String s, int i)
    {
        String e = expected.substring(i,i+1);
        //      System.out.println("GOT " + s);
        //      System.out.println("EXPECTED " + e);
        return s.equals(e);
    }
    
        
    
    void validateList(Tester t) throws Exception
    {
        String found = "";
        
        if (expected.length() != l.size()) {
            t.fail("Validation fail. Expected list of size " +
                   expected.length() +
                   " but got one of size " + l.size());
        }
        for (int i = 0; i < l.size(); i++) {
            String f = (String)l.get(i);
            found = found + f;
            if (!validatePosition(f, i)) {
                t.fail("Validation fail, expecting " +
                       expected.substring(i,i+1));
            }
        }
    }
    


    //
    // Tester instances implement a particular test by overriding doTest.
    //

    abstract class Tester 
    {
        protected String name;
        public Tester(String n) 
        {
            name = n;
        }
        void runTest() throws Exception 
        {
            System.out.println(testKind() + "-Test:" + name);
            doTest();
        }

        void fail(String s) throws Exception
        {
            throw new Exception(testKind() + " - FailedTest: " + name + " " + s);
        }
        
        abstract void doTest() throws Exception;
    }
    


    //
    // Automatically initialized array of tests for this testing module.
    //
    private Tester[] tests = {
        new Tester("add") 
        {
            void doTest()  throws Exception
            {
                initList();
                insert(1, "5");
                insert(7, "*");
                insert(3, "@");
                validateList(this);
            }
            
        },


        new Tester("addAll")
        {
            void doTest() throws Exception 
            {
                ArrayList al = new ArrayList();
                al.add("X");
                al.add("Y");
                al.add("Z");
                l.addAll(al);
                expected = expected + "XYZ";
                l.addAll(0, al);        
                expected = "XYZ" + expected;
                validateList(this);
            }
        },


        new Tester("isEmpty") 
        {
            void doTest() throws Exception
            {
                List le = newList();
                if (!le.isEmpty())
                    fail("Empty list appears non empty");
                le.add("2");
                if (le.isEmpty())
                    fail("Non empty list appears empty");
            }
        }


        // MORE TESTS GET DESCRIBED HERE
        
        
    };
    
        
        

    
    public boolean runTests() 
    {
        try {
            for (int i = 0; i < tests.length; i++) {
                tests[i].runTest();
            }
        } catch  (Exception e) {
            System.out.println("runTests fail: " + e);
            return false;
        }
        return true;
    }
    

    static boolean useLinked = false;

    static List newList()
    {
        if (useLinked)
            return new LinkedList();
        else
            return new RecursiveList();
    }

    static String testKind() 
    {
        return useLinked ? "LinkedList" : "RecursiveList";
    }
    
            
    static public void main(String args[]) 
    {

        if (args.length > 0) 
            useLinked = args[0].equals("-linked");
        ListTester ld = new ListTester();
        if (ld.runTests()) 
            System.out.println("PASSED");
        else
            System.out.println("FAILED");
    }
    
            
            

}