package tests;

import static org.junit.Assert.*;

import java.io.Reader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

import org.junit.Test;
import org.junit.Ignore;

import parser.Parser;
import tokenizer.Token;
import tokenizer.TokenType;
import tokenizer.Tokenizer;
import tree.Tree;

/**
 * Test for CIT594 Parser class, Spring 2010
 * @author David Matuszek
 * @version March 31, 2014
 */
public class DavesParserTest {
    private Parser parser;
    private static String keywordString =
            ("penup pendown color home jump set repeat while if else " +
                    "do forward left right face def red orange yellow green " +
                    "cyan blue purple magenta pink olive black gray white " +
                    "brown tan color getX getY block list header program");
    private Set<String> keywords =
            new HashSet<String>(Arrays.asList(keywordString.split(" ")));
    

    /**
     * Test method for {@link parser.Parser#Parser(java.lang.String)}.
     */
    @Test
    public void testParser() {
        // Not much to test here; mostly that the Parser constructor doesn't crash
        parser = new Parser("");
        parser = new Parser("2 + 2");
    }

    /**
     * Test method for {@link parser.Parser#expression()}.
     */
    @Test
    public void testIsExpression() {
        Tree<Token> expected;
        
        use("250");
        assertTrue(parser.isExpression());
        assertStackTop(tree("250"));
        
        use("hello");
        assertTrue(parser.isExpression());
        assertStackTop(tree("hello"));

        use("(xyz + 3)");
        assertTrue(parser.isExpression());
        assertStackTop(tree("+(xyz 3)"));

        use("a + b + c");
        assertTrue(parser.isExpression());
        assertStackTop(tree("+(+(a b) c)"));

        use("3 * 12 - 7");
        assertTrue(parser.isExpression());
        assertStackTop(tree("-(*(3 12) 7)"));

        use("12 * 5 - 3 * 4 / 6 + 8");
        assertTrue(parser.isExpression());
        expected = tree("+( -(*(12 5) /(*(3 4) 6)) 8)");
        assertStackTop(expected);
                     
        use("12 * ((5 - 3) * 4) / 6 + (8)");
        assertTrue(parser.isExpression());
        expected = tree("+(/(*(12 *(-(5 3) 4)) 6) 8)");
        assertStackTop(expected);
        
        use("");
        assertFalse(parser.isExpression());
        
        use("#");
        assertFalse(parser.isExpression());
    }

    /**
     * Test method for {@link parser.Parser#isExpression()}.
     */
    @Test(expected=RuntimeException.class)
    public void testIsBadExpression1() {
        use("17 +");
        parser.isExpression();
    }

    /**
     * Test method for {@link parser.Parser#isExpression()}.
     */
    @Test(expected=RuntimeException.class)
    public void testIsBadExpression2() {
        use("22 *");
        parser.isExpression();
    }

    /**
     * Test method for {@link parser.Parser#isTerm()}.
     */
    @Test
    public void testUnaryMinusBeforeFactor() {
        use("-a + b");
        assertTrue(parser.isExpression());
        assertStackTop(tree("+(-(a) b)"));
        
        use("-a * b + c");
        assertTrue(parser.isExpression());
        assertStackTop(tree("+(*(-(a) b) c)"));
    }

    /**
     * Test method for {@link parser.Parser#isTerm()}.
     */
    @Test
    public void testUnaryMinusInsideParentheses() {
        use("(-foo + 3) / bar");
        assertTrue(parser.isExpression());
        assertStackTop(tree("/(+(-(foo) 3) bar)"));
    }

    /**
     * Test method for {@link parser.Parser#isUnsignedTerm()}.
     */
    @Test
    public void testIsUnsignedTerm() {        
        use("12");
        assertTrue(parser.isUnsignedTerm());
        assertStackTop(tree("12"));

        use("3*12");
        assertTrue(parser.isUnsignedTerm());
        assertStackTop(tree("*(3 12)"));

        use("u * v * z");
        assertTrue(parser.isUnsignedTerm());
        assertStackTop(tree("*(*(u v) z)"));
        
        use("20 * 3 / 4");
        assertTrue(parser.isUnsignedTerm());
        assertStackTop(tree("/(*(20 3) 4)"));

        use("20 * 3 / 4 + 5");
        assertTrue(parser.isUnsignedTerm());
        assertStackTop(tree("/(*(20 3) 4)"));
        unconsumedTokensShouldBe("+ 5");
        
        use("");
        assertFalse(parser.isUnsignedTerm());
        unconsumedTokensShouldBe("");
        
        use("#");
        assertFalse(parser.isUnsignedTerm());
        unconsumedTokensShouldBe("#");
    }

    /**
     * Test method for {@link parser.Parser#isTerm()}.
     */
    @Test
    public void testIsTerm() {
        use("3*12");
        assertTrue(parser.isTerm());
        assertStackTop(tree("*(3 12)"));

        use("-3*12");
        assertTrue(parser.isTerm());
        assertStackTop(tree("*(-(3) 12)"));
    }

    /**
     * Test method for {@link parser.Parser#isFactor()}.
     */
    @Test
    public void testIsUnsignedFactor() {
        use("12");
        assertTrue(parser.isUnsignedFactor());
        assertStackTop(tree("12"));

        use("hello");
        assertTrue(parser.isUnsignedFactor());
        assertStackTop(tree("hello"));
        
        use("(xyz + 3)");
        assertTrue(parser.isUnsignedFactor());
        assertStackTop(tree("+(xyz 3)"));
        
        use("12 * 5");
        assertTrue(parser.isUnsignedFactor());
        assertStackTop(tree("12"));
        unconsumedTokensShouldBe("* 5");
        
        use("17 +");
        assertTrue(parser.isUnsignedFactor());
        assertStackTop(tree("17"));
        unconsumedTokensShouldBe("+");

        use("");
        assertFalse(parser.isUnsignedFactor());
        unconsumedTokensShouldBe("");
        
        use("getX");
        assertTrue(parser.isUnsignedFactor());
        assertStackTop(tree("getX"));
        
        use("getY");
        assertTrue(parser.isUnsignedFactor());
        assertStackTop(tree("getY"));
        
        use("#");
        assertFalse(parser.isUnsignedFactor());
        unconsumedTokensShouldBe("#");
    }

    /**
     * Test method for {@link parser.Parser#isUnsignedFactor()}.
     */
    @Test
    public void testIsFactor() {
        use("12");
        assertTrue(parser.isFactor());
        assertStackTop(tree("12"));

        use("hello");
        assertTrue(parser.isFactor());
        assertStackTop(tree("hello"));
        
        use("-12");
        assertTrue(parser.isFactor());
        assertStackTop(tree("-(12)"));

        use("-hello");
        assertTrue(parser.isFactor());
        assertStackTop(tree("-(hello)"));
    }

    /**
     * Test method for {@link starterCode.Parser#isAddOperator()}.
     */
    @Test
    public void testIsAddOperator() {
        use("+ - + $");
        assertTrue(parser.isAddOperator());
        assertStackTop(tree("+"));
        assertTrue(parser.isAddOperator());
        assertStackTop(tree("-"));
        assertTrue(parser.isAddOperator());
        assertFalse(parser.isAddOperator());
        unconsumedTokensShouldBe("$");
    }

    /**
     * Test method for {@link parser.Parser#isMultiplyOperator()}.
     */
    @Test
    public void testIsMultiplyOperator() {
        use("* / $");
        assertTrue(parser.isMultiplyOperator());
        assertTrue(parser.isMultiplyOperator());
        assertFalse(parser.isMultiplyOperator());
        unconsumedTokensShouldBe("$");
    }

    /**
     * Test method for {@link parser.Parser#isVariable()}.
     */
    @Test
    final public void testIsVariable() {
        use("hello   list abc123 header _");
        assertTrue(parser.isVariable());
        assertTrue(parser.isVariable());
        assertTrue(parser.isVariable());
        assertTrue(parser.isVariable());
        assertTrue(parser.isVariable());
    }

//    /**
//     * Test method for {@link parser.Parser#isListOfVariables()}.
//     */
//    @Test
//    public void testListOfVariables() {
//        use("abc");
//        assertTrue(parser.isListOfVariables());
//        assertStackTop(tree("list(abc)"));
//        use("u v w");
//        assertTrue(parser.isListOfVariables());
//        assertStackTop(tree("list(u v w)"));        
//    }

    /**
     * Test method for {@link parser.Parser#isProgram()}.
     */
    @Test
    public void testIsProgram() {
        use("red \n" +
            "repeat 4 { \n" +
            "    do drawAndTurn 50 90 \n" +
            "} \n" +
            "def drawAndTurn howFar degrees { \n" +
            "    forward howFar \n" +
            "    left degrees \n" +
            "} \n");
        assertTrue(parser.isProgram());
        Tree<Token> expected =
            tree("program(block(color(255 0 0)" +
                 "    repeat(4 block(do(drawAndTurn list(50 90)))))" +
                 "list(def(header(drawAndTurn list(howFar degrees))" +
                 "    block(forward(howFar) left(degrees)))))");
        Tree<Token> actual = parser.stack.peek();
        assertEquals(expected, actual);

    }

    /**
     * Test method for {@link parser.Parser#command()}.
     */
    @Test
    public void testIsCommand() {
        // Move commands
        testCommand2("forward 5 \n", tree("forward(5)"));
        testCommand2("left 5 \n", tree("left(5)"));
        testCommand2("right 5 \n", tree("right(5)"));
        testCommand2("forward a + b + c \n", tree("forward(+(+(a b) c))"));
        
        // Other simple commands
        testCommand2("penup \n", tree("penup"));
        testCommand2("pendown \n", tree("pendown"));
        testCommand2("color 0 100 250 \n", tree("color(0 100 250)"));
        testCommand2("home \n", tree("home"));
        testCommand2("set n n + 1 \n", tree("set(n +(n 1))"));
        
        // Create block for use in testing nested commands
        String fancyBlock = "{ \n" +
        		                "penup \n" +
        		                "if 2 = 2 { \n" +
        		                    "forward 5 \n" +
        		                    "pendown \n" +
        		                "} \n" +
        		            "} \n";
        use(fancyBlock);
        assertTrue(parser.isBlock());
        String blockTree = "block(penup if(=(2 2) block(forward(5) pendown)))";

        testCommand2("repeat 5 { \n } \n", tree("repeat(5 block)"));
        testCommand2("repeat 5" + fancyBlock,
                     tree("repeat(5 " + blockTree + ")"));

        testCommand2("while 2 < 2 { \n } \n", tree("while(<(2 2) block)"));
        testCommand2("while 2 < 2 " + fancyBlock,
                     tree("while(<(2 2) " + blockTree + ")"));
        

        testCommand2("if 2 = 2 { \n } \n", tree("if(=(2 2) block)"));        
        testCommand2("if 2=2 { \n } \n else { \n } \n",
                     tree("if(=(2 2) block block)"));
        testCommand2("if 2 = 2" + fancyBlock + "else" + fancyBlock,
                     tree("if(=(2 2)" + blockTree + blockTree + ")"));
        
        testCommand2("do foo \n", tree("do(foo list)"));
        testCommand2("do foo a b \n", tree("do(foo list(a b))"));
    }

    private void testCommand2(String string, Tree<Token> tree) {
        use(string);
        assertTrue(string, parser.isCommand());
        assertStackTop(tree);
    }

//    /**
//     * Test method for {@link parser.Parser#listOfCommands()}.
//     */
//    @Test
//    public void testListOfCommands() {
//        use("");
//        assertTrue(parser.isListOfCommands());
//        assertStackTop(tree("block()"));
//
//        use("pendown \n");
//        assertTrue(parser.isListOfCommands());
//        assertStackTop(tree("block(pendown)"));
//
//        use("set n 0 \n while n < 10 { \n set n n + 1 \n } \n penup \n");
//        assertTrue(parser.isListOfCommands());
//        assertStackTop(tree("block(set(n 0) while(<(n 10) block(set(n +(n 1)))) penup)"));
//    }

    /**
     * Test method for {@link parser.Parser#isColor()}.
     */
    @Test
    public void testColors() {
        class MyColor {
            String name;
            int red, green, blue;
            
            MyColor(String n, int r, int g, int b) {
                name = n;
                red = r;
                green = g;
                blue = b;
            }           
        }
        MyColor red = new MyColor("red", 255, 0, 0);
        MyColor orange = new MyColor("orange", 255, 128, 0);
        MyColor yellow = new MyColor("yellow", 255, 255, 0);
        MyColor green = new MyColor("green", 0, 153, 0);
        MyColor cyan = new MyColor("cyan", 0, 255, 255);

        MyColor blue = new MyColor("blue", 0, 64, 255);
        MyColor purple = new MyColor("purple", 128, 0, 255);
        MyColor magenta = new MyColor("magenta", 255, 0, 255);
        MyColor pink = new MyColor("pink", 250, 175, 190);
        MyColor olive = new MyColor("olive", 128, 128, 0);

        MyColor black = new MyColor("black", 0, 0, 0);
        MyColor gray = new MyColor("gray", 128, 128, 128);
        MyColor white = new MyColor("white", 255, 255, 255);
        MyColor brown = new MyColor("brown", 128, 64, 0);
        MyColor tan = new MyColor("tan", 210, 180, 140);
        
        MyColor[] colors = { red, orange, yellow, green, cyan,
                blue, purple, magenta, pink, olive,
                black, gray, white, brown, tan };
        
        for (MyColor color : colors) {
            use(color.name + "\n");
            assertTrue(color.name, parser.isCommand());
            Tree<Token> actualTree = parser.stack.peek();
            Tree<Token> possibleTree1 = new Tree<Token>(new Token(TokenType.KEYWORD, color.name));
            Tree<Token> possibleTree2 = new Tree<Token>(new Token(TokenType.KEYWORD, "color"),
                    new Tree<Token>(new Token(TokenType.NUMBER, color.red + "")),
                    new Tree<Token>(new Token(TokenType.NUMBER, color.green + "")),
                    new Tree<Token>(new Token(TokenType.NUMBER, color.blue + "")));
            Tree<Token> actual = parser.stack.peek();
            if (actual.numberOfChildren() == 0) {
                assertEquals(color.name, possibleTree1, actual);
            } else {
                assertEquals(color.name, possibleTree2, actual);
            }
        }
        
        use("color 12 34 5 \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("color(12 34 5)"));
    }
     
    /**
     * Test method for {@link parser.Parser#isColor()}.
     */
    @Test(expected=RuntimeException.class)
    public void testBadColorCommand() {
        use("color \n");
        assertFalse(parser.isCommand());
    }
     
    /**
     * Test method for {@link parser.Parser#isColor()}.
     */
    @Test(expected=RuntimeException.class)
    public void testBadColorCommand2() {
        use("color 50 \n");
        parser.isCommand();
    }

    /**
     * Test method for {@link parser.Parser#isHomeCommand()}.
     */
    @Test
    public void testIsHome() {
        use("home \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("home"));
    }

    /**
     * Test method for {@link parser.Parser#set()}.
     */
    @Test
    public void testIsSet() {
        use("set a 5 \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("set(a 5)"));
    }

    /**
     * Test method for {@link parser.Parser#isBlock()}.
     */
    @Test
    public void testIsBlock() {
        use("{ \n } \n");
        assertTrue(parser.isBlock());
        assertStackTop(tree("block"));

        use("{ \n penup \n} \n");
        assertTrue(parser.isBlock());
        assertStackTop(tree("block(penup)"));

        use("{ \n penup \n pendown \n } \n");
        assertTrue(parser.isBlock());
        assertStackTop(tree("block(penup pendown)"));

        use("{ \n penup \n red \n set m 23 \n pendown \n } \n");
        assertTrue(parser.isBlock());
        assertStackTop(tree("block(penup color(255 0 0) set(m 23) pendown)"));
    }

    /**
     * Test method for {@link parser.Parser#repeatCommand()}.
     */
    @Test
    public void testIsRepeatCommand() {
        use("repeat 5 { \n } \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("repeat(5 block)"));
        
        use("repeat 5 { \n repeat 10 {\n set n n + 1 \n set n n / 2 \n } \n } \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("repeat(5 block(repeat(10 block(set(n +(n 1)) set(n /(n 2))))))"));
    }

    /**
     * Test method for {@link parser.Parser#whileCommand()}.
     */
    @Test
    public void testIsWhileCommand() {
        use("while 2 + 2 = 5 { \n } \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("while(=(+(2 2) 5) block)"));
        
        use("while n + 2 > 5 { \n while n + 2 < 10 {\n" +
        		"set n n + 1 \n set n n / 2 \n } \n } \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("while(>(+(n 2) 5) block(while(<(+(n 2) 10)" +
        		" block(set(n +(n 1)) set(n /(n 2))))))"));
    }

    /**
     * Test method for {@link parser.Parser#isIfCommand()}.
     */
    @Test
    public void testIfCommand() {
        use("if 2 = 2 { \n } \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("if(=(2 2) block)"));
        
        use("if 2=2 { \n } \n else { \n } \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("if(=(2 2) block block)"));
    }

    /**
     * Test method for {@link parser.Parser#isDoCommand()}.
     */
    @Test
    public void testIsDo() {
        use("do foo \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("do(foo list)"));

        use("do foo a b c\n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("do(foo list(a b c))"));

        use("do foo 2 + 2 4\n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("do(foo list(+(2 2) 4))"));
    }

    /**
     * Test method for {@link parser.Parser#isMove()}.
     */
    @Test
    public void testIsMove() {
        use("forward");
        assertTrue(parser.isMove());
        assertStackTop(tree("forward"));

        use("left");
        assertTrue(parser.isMove());
        assertStackTop(tree("left"));

        use("right");
        assertTrue(parser.isMove());
        assertStackTop(tree("right"));

        use("face");
        assertTrue(parser.isMove());
        assertStackTop(tree("face"));
    }


    /**
     * Test method for {@link parser.Parser#isMoveCommand()}.
     */
    @Test
    public void testIsMoveCommand() {
        use("forward 5 \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("forward(5)"));

        use("left 5 \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("left(5)"));

        use("right 5 \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("right(5)"));

        use("face a + b + c \n");
        assertTrue(parser.isCommand());
        assertStackTop(tree("face(+(+(a b) c))"));
    }

    /**
     * Test method for {@link parser.Parser#isCondition()}.
     */
    @Test
    public void testIsCondition() {
        use("a = b");
        assertTrue(parser.isCondition());
        assertStackTop(tree("=(a b)"));
        
        use("a < b");
        assertTrue(parser.isCondition());
        assertStackTop(tree("<(a b)"));
        
        use("a > b");
        assertTrue(parser.isCondition());
        assertStackTop(tree(">(a b)"));
        
        use("3 * 4 = (2 + 2) * 3");
        assertTrue(parser.isCondition());
        assertStackTop(tree("=(*(3 4) *(+(2 2) 3))"));
    }

    /**
     * Test method for {@link parser.Parser#comparator()}.
     */
    @Test
    public void testIsComparator() {
        use("< = > <=>");
        for (int i = 0; i < 2; i++) {
            assertTrue(parser.isComparator());
            assertStackTop(tree("<"));
            assertTrue(parser.isComparator());
            assertStackTop(tree("="));
            assertTrue(parser.isComparator());
            assertStackTop(tree(">"));
        }
    }

    /**
     * Test method for {@link parser.Parser#isProcedure()}.
     */
    @Test
    public void testIsProcedure() {
        use("def foo { \n } \n");
        assertTrue(parser.isProcedure());
        assertStackTop(tree("def(header(foo list) block)"));

        use("def foo a b { \n } \n");
        assertTrue(parser.isProcedure());
        assertStackTop(tree("def(header(foo list(a b)) block)"));

        use("def foo { \n penup \n pendown \n } \n");
        assertTrue(parser.isProcedure());
        assertStackTop(tree("def(header(foo list) block(penup pendown))"));
        
        use("def foo a b { \n penup \n pendown \n } \n");
        assertTrue(parser.isProcedure());
        assertStackTop(tree("def(header(foo list(a b))" +
        		            "block(penup pendown))"));
        
        use("define foo { \n } \n");
        assertFalse(parser.isProcedure());
    }

//    /**
//     * Test method for {@link parser.Parser#isListOfProcedures()}.
//     */
//    @Test
//    public void testListOfProcedures() {
//        String procedure = "to foo { \n } \n";
//        String procedure2 = "to bar { \n } \n";
//        String procedureCode = "to(header(foo list) block)";
//        String procedureCode2 = "to(header(bar list) block)";
//        
//        use("");
//        assertTrue(parser.isListOfProcedures());
//        assertStackTop(tree("list"));
//        
//        use(procedure);
//        assertTrue(parser.isListOfProcedures());
//        assertStackTop(tree("list(" + procedureCode + ")"));
//        
//        use(procedure + procedure2);
//        assertTrue(parser.isListOfProcedures());
//        assertStackTop(tree("list(" + procedureCode +
//                            procedureCode2 + ")"));
//    }

    /**
     * Test method for {@link parser.Parser#isEol()}.
     */
    @Test
    public void testIsEnd() {
        use("+ \n");
        assertTrue(parser.isAddOperator());
        assertTrue(parser.isEol());
        assertStackTop(tree("+"));

        use("\n \n \n *");
        assertTrue(parser.isEol());
        assertTrue(parser.isMultiplyOperator());
    }


//  ----- "Helper" methods
    
    /**
     * Prints a couple of trees in order to test the tree.print() method.
     */
    @Ignore("Prints the results of a helper method; test has been passed.")
    @Test
    public void testTree() {
        Tree<Token> tree = tree("a(b c)");
        System.out.println(tree);
        tree = tree("+(+(a b) c)");
        System.out.println(tree);
    }

   /**
     * The "isX" Parser methods try to recognize an X at the beginning
     * of the input, but should not consume tokens after the X. For example,
     * a factor may contain multiplications but not additions, so given a
     * string such as "3*x+5*y", the isFactor method should consume and
     * accept the "3*x" but leave the "+5*y" for later.
     * <p>
     * This method tests the input string to see whether the correct tokens
     * are left unconsumed. 
     * 
     * @param recognizer The Recognizer recently used to recognize some X from
     *        an input string.
     * @param expectedTokens The following Tokens that should remain in the input
     *        string after the X has been consumed. 
     */
    private void unconsumedTokensShouldBe(String expectedTokens) {
        Token expectedToken;
        Token actualToken;
        
        Tokenizer unconsumedTokens = parser.getTokenizer();
        Tokenizer expected =
                new Tokenizer(new StringReader(expectedTokens), keywords);

        try {
            while (expected.hasNext()) {
                expectedToken = expected.next();
                assertTrue(unconsumedTokens.hasNext());
                actualToken = unconsumedTokens.next();
                assertEquals(expectedToken, actualToken);
            }
        }
        catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    /**
     * Asserts that the parameter is equal to the top of the stack.
     * 
     * @param t The Tree to compare against the top of the stack.
     */
    private void assertStackTop(Tree<Token> t) {
        assertEquals(t, parser.stack.peek());
    }
    
    /**
     * Creates a Tree of Tokens from a String.
     * 
     * @param description The string representation of the Tree
     * (Note: Cannot include parentheses as values.)
     * 
     * @return A Tree of Tokens.
     */
    private Tree<Token> tree(String description) {
        
        int lpar = 0, rpar = 0;
        for (int i = 0; i < description.length(); i++) {
            char ch = description.charAt(i);
            if (ch == '(') lpar++;
            if (ch == ')') rpar++;
        }
        assertEquals(lpar, rpar);
        
        Tree<String> treeOfStrings = parse(description);
        return convertToTreeOfTokens(treeOfStrings);
    }
//    // This was in starter code? TODO XXX
//    private Tree<Token> tree(String description) {
//        Tree<String> treeOfStrings = Tree.parse(description);
//        return convertToTreeOfTokens(treeOfStrings);
 //   }

    
    /**
     * Creates a Tree of Tokens from a Tree of Strings. The given
     * Tree of Strings is unchanged.
     * 
     * @param tree The tree to be translated.
     * @return The resultant tree of tokens.
     */
    private Tree<Token> convertToTreeOfTokens(Tree<String> tree) {
        Tree<Token> root = new Tree<Token>(makeOneToken(tree.getValue()));

        Iterator<Tree<String>> iter = tree.children();
        while (iter.hasNext()) {
            root.addChildren(convertToTreeOfTokens(iter.next()));
        }
        return root;
    }
    
    /**
     * Returns a single token from the given string.
     * 
     * @param word The thing to be turned into a Token.
     * @return The corresponding Token.
     */
    private Token makeOneToken(String word) {
        Tokenizer tokenizer = new Tokenizer(new StringReader(word), keywords);
        return tokenizer.next();
    }

    /**
     * 
     * @param s The string to be parsed.
     */
    private void use(String s) {
        parser = new Parser(s);
    }
    
    // The following parse methods are copied from Dave's Tree class.
    
    /**
     * Parses a string of the general form
     * <code>value(child, child, ..., child)</code> and returns the
     * corresponding tree. Children may be separated by commas and/or spaces.
     * Node values are all Strings.
     * 
     * @param s The String to be parsed.
     * @return The resultant Tree&lt;String&lt;.
     * @throws IllegalArgumentException
     *             If problems are detected in the input string.
     */
    public static Tree<String> parse(String s) throws IllegalArgumentException {
        StringTokenizer tokenizer = new StringTokenizer(s, " ()", true);
        List<String> tokens = new LinkedList<String>();
        while (tokenizer.hasMoreTokens()) {
            String token = tokenizer.nextToken();
            if (token.trim().length() == 0)
                continue;
            tokens.add(token);
        }
        Tree<String> result = parse(tokens);
        if (tokens.size() > 0) {
            throw new IllegalArgumentException("Leftover tokens: " + tokens);
        }
        return result;
    }
    
    /**
     * Parses and returns one tree, consisting of a value and possible children
     * (enclosed in parentheses), starting at the first element of tokens.
     * Returns null if this token is a close parenthesis, or if there are no
     * more tokens.
     * 
     * @param tokens
     *            The tokens that describe a Tree.
     * @return The Tree described by the tokens.
     * @throws IllegalArgumentException
     *             If problems are detected in the input list.
     */
    private static Tree<String> parse(List<String> tokens)
            throws IllegalArgumentException {
        // No tokens -- return null
        if (tokens.size() == 0) {
            return null;
        }
        // Get the next token and remove it from the list
        String token = tokens.remove(0);
        // If the token is an open parenthesis
        if (token.equals("(")) {
            throw new IllegalArgumentException(
                "Unexpected open parenthesis before " + tokens);
        }
        // If the token is a close parenthesis, we are at the end of a list of
        // children
        if (token.equals(")")) {
            return null;
        }
        // Make a tree with this token as its value
        Tree<String> tree = new Tree<String>(token);
        // Check for children
        if (tokens.size() > 0 && tokens.get(0).equals("(")) {
            tokens.remove(0);
            Tree<String> child;
            while ((child = parse(tokens)) != null) {
                tree.addChildren(child);
            }
        }
        return tree;
    }
}