import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
import org.junit.Before;
import org.junit.Test;


public class BinaryTreeTestOfAdditionalMethods {
    private BinaryTree<String> bt;
    private BinaryTree<String> leaf;
    private BinaryTree<String> bNull;
    private Object[] t;
    private BinaryTree<Object> objectTree;
    private BinaryTree<String> aTree, b, c, d, e;

    
    @Before
    public void setUp() throws Exception {
        //      bt = a             bNull = x            aTree = a
        //          / \                   / \                  / \
        //         b   f                 y   null             /   \
        //        / \   \                                    b     c
        //       c   d   g       objectTree = 0               \   /
        //          /   / \                  / \               d e
        //         e   h   k                1   0
        //            / \                      / \       leaf = LEAF
        //           i   j                    1   0
        //
        bt = parse("a(b(c,d(e,-)),f(-,g(h(i,j),k)))");
        
        leaf = new BinaryTree<String>("LEAF");
        
        bNull = new BinaryTree<String>("x", new BinaryTree<String>("y"), new BinaryTree<String>(null));
        
        t = new Object[5];
        for (int i = 0; i < t.length; i++) t[i] = new Thing((i % 2) + "");
        objectTree = bt(t[0], bt(t[1]), bt(t[2], bt(t[3]), bt(t[4])));

        d = new BinaryTree<String>("d");
        e = new BinaryTree<String>("e");
        b = new BinaryTree<String>("b", null, d);
        c = new BinaryTree<String>("c", e, null);
        aTree = new BinaryTree<String>("a", b, c);
    }
    
    private BinaryTree<Object> bt(Object root) {
        return new BinaryTree<Object>(root);
    }
    
    private BinaryTree<Object> bt(Object root, BinaryTree left, BinaryTree right) {
        return new BinaryTree<Object>(root, left, right);
    }

    @Test
    public void testLeftmostDescendant() {
        assertEquals("c", bt.leftmostDescendant().getValue());
        assertEquals("LEAF", leaf.leftmostDescendant().getValue());
    }

    @Test
    public void testRightmostDescendant() {
        assertEquals("k", bt.rightmostDescendant().getValue());
        assertEquals("LEAF", leaf.rightmostDescendant().getValue());
        assertEquals(null, bNull.rightmostDescendant().getValue());
    }

    @Test
    public void testNumberOfNodes() {
        assertEquals(11, bt.numberOfNodes());
        assertEquals(1, leaf.numberOfNodes());
    }

    @Test
    public void testDepth() {
        assertEquals(4, bt.depth());
        assertEquals(0, leaf.depth());
    }

    @Test
    public void testContainsEqualValue() {
        assertTrue(bt.containsEqualValue("a"));
        assertTrue(bt.containsEqualValue("h"));
        assertFalse(bt.containsEqualValue("w"));
        assertTrue(leaf.containsEqualValue("LEAF"));
    }

    @Test
    public void testContainsSameValue() {
        assertTrue(objectTree.containsSameValue(t[3]));
        assertTrue(objectTree.containsSameValue(t[4]));
        assertFalse(objectTree.containsSameValue(new Thing("0")));
        assertFalse(objectTree.containsSameValue(new Thing("1")));
        assertTrue(bt.containsEqualValue("h"));
        assertFalse(bt.containsSameValue("h"));
        assertTrue(leaf.containsSameValue("LEAF"));
        assertFalse(leaf.containsSameValue(new byte[] { 'L', 'E', 'A', 'F' }.toString()));
    }

    @Test
    public void testLeaves() {        
        Set<BinaryTree<String>> expected = new HashSet<BinaryTree<String>>();
        expected.add(d);
        expected.add(e);
        assertEquals(expected, aTree.leaves());
        
        leaf = new BinaryTree<String>("LEAF");
        expected = new HashSet<BinaryTree<String>>();
        expected.add(leaf);
        assertEquals(expected, leaf.leaves());
    }

    @Test
    public void testValuesOf() {
        Set<String> expected = new HashSet<String>();
        expected.add("a");
        expected.add("b");
        expected.add("c");
        expected.add("d");
        expected.add("e");
        
        assertEquals(expected, aTree.valuesOf());
    }

    @Test
    public void testFringe() {
        List<String> expected = new ArrayList<String>();
        expected.add("d");
        expected.add("e");
        assertEquals(expected, aTree.fringe());
        
        expected = new ArrayList<String>();
        expected.add("c");
        expected.add("e");
        expected.add("i");
        expected.add("j");
        expected.add("k");
        assertEquals(expected, bt.fringe());
    }

    @Test
    public void testCopy() {
        BinaryTree<String> bt1 = parse("a(b(c,d(e,-)),f(-,g(h(i,j),k)))");
        BinaryTree<String> bt2 = parse("a(b(c,d(e,-)),f(-,g(h(i,j),k)))");
        BinaryTree<String> bt3 = bt1.copy();
        assertEquals(bt1, bt3);
        assertEquals(bt2, bt3);
    }

    @Test
    public void testReverse() {
        BinaryTree<String> bt1 = parse("a(b(c,d(e,-)),f(-,g(h(i,j),k)))");
        BinaryTree<String> bt2 = parse("a(f(g(k,h(j,i)),-),b(d(-,e),c))");
        assertEquals(bt2, bt1.reverse());
        assertNotSame(bt1, bt2);
        assertNotSame(bt1.getLeftChild().getRightChild(),
                      bt2.getRightChild().getLeftChild());
    }

    @Test
    public void testReverseInPlace() {
        BinaryTree<String> bt1 = parse("a(b(c,d(e,-)),f(-,g(h(i,j),k)))");
        BinaryTree<String> bt2 = parse("a(f(g(k,h(j,i)),-),b(d(-,e),c))");
        BinaryTree<String> h = bt1.getRightChild().getRightChild().getLeftChild();
        bt1.reverseInPlace();
        assertEquals(bt2, bt1);
        assertSame(h, bt1.getLeftChild().getLeftChild().getRightChild());
    }

    /**
     * Accepts a string with syntax "root(leftChild, rightChild)". If either
     * child is omitted, indicate this with a dash, "-". If both children
     * are omitted, so that the root is also a leaf, omit the entire
     * parenthesized group. Whitespace is allowed and ignored.
     * 
     * @param s The string to be parsed.
     * @return The binary tree described by the input string.
     */
    public BinaryTree<String> parse(String s) {
        PushbackTokenizer tokenizer = new PushbackTokenizer(s);
        return parse(tokenizer);
    }

    /**
     * Returns the binary tree parsed by this tokenizer.
     * 
     * @param tokenizer A tokenizer primed with the string to be parsed.
     * @return The binary tree resulting from the parse.
     */
    private BinaryTree<String> parse(PushbackTokenizer tokenizer) {
        String root, token;
        BinaryTree<String> leftChild, rightChild;

        root = tokenizer.nextToken();
        if (root.equals("-")) return null;

        if (tokenizer.hasMoreTokens()) {
            token = tokenizer.nextToken();
            if (token.equals(",") || token.equals(")")) { // not for me!
                tokenizer.pushBack(token);
                return new BinaryTree(root);
            }
            else if (token.equals("(")) {
                leftChild = parse(tokenizer);
                get(tokenizer, ",");
                rightChild = parse(tokenizer);
                get(tokenizer, ")");
                return new BinaryTree(root, leftChild, rightChild);
            }
        }
        else {
            return new BinaryTree(root);
        }
        return null;
    }
    
    /**
     * Gets the next token from the tokenizer and verifies that it
     * is the required token. If not, a RuntimeException is thrown.
     * 
     * @param tokenizer The source of the next token.
     * @param requiredString The value that the next token must have.
     * @throws RuntimeException If the wrong token is returned.
     */
    public void get(PushbackTokenizer tokenizer, String requiredString) {
        String token = tokenizer.nextToken();
        if (!token.equals(requiredString)) {
            throw new RuntimeException("Parser required " + requiredString + " but got " + token);
        }
    }

    /**
     * Used to test whether the parse(String) method is working;
     * produces printout which must be manually verified, and is
     * <b>not</b> part of JUnit testing.
     * 
     * @param args Unused.
     */
    public static void main(String[] args) {
        new BinaryTreeTestOfAdditionalMethods().run();
    }
    
    /**
     * Does the work described by the <code>main</code> method.
     */
    private void run() {
        BinaryTree<String> bt;
        bt = parse("x");
        bt.print();
        bt = parse("p(q, r)");
        bt.print();
        bt = parse("1(2, -)");
        bt.print();
        bt = parse("one(-, three)");
        bt.print();
        bt = parse("A(B, C(D, E))");
        bt.print();
        bt = parse("V (W (X, Y), Z)");
        bt.print();
        bt = parse("1(2(2.5, 2.8), 3)");
        bt.print();
        bt = parse("a(b,  c(-, d(e(-, g), f(h, i))))");
        bt.print();
        System.out.println(bt);
        bt = parse("a(b(c, d(e, -)), f(-, g(h(i, j), k)))");
        bt.print();
        System.out.println(bt);
        
    }

    // --------------------- Inner class Thing --------------------- 
    
    /**
     * A simple wrapper class for Strings. Due to "interning,"
     * equal Strings defined in different places may be represented
     * in one unique location, hence == as well as "equals."
     * Different Thing objects are guaranteed to not be ==, though
     * they may satisfy "equals."
     * 
     * @author Dave Matuszek
     * @version Feb 1, 2008
     */
    class Thing {
        String value;
        
        public Thing(String s) { value = s; }
        
        @Override
        public String toString() { return "Thing(" + value + ")"; }
        
        @Override
        public boolean equals(Object obj) {
            if (obj == null) return false;
            return value.equals(((Thing)obj).value);
        }
    }

    // --------------- Inner class PushbackTokenizer --------------- 
    
    /**
     * A wrapper class for StringTokenizer, adding the capability to
     * push back one token.
     * 
     * @author David Matuszek
     * @version Feb 1, 2008
     */
    class PushbackTokenizer {
        StringTokenizer tokenizer;
        String token = null;
        
        /**
         * Creates a PushbackTokenizer for the given string.
         * 
         * @param s The string to be tokenized.
         */
        public PushbackTokenizer(String s) {
            tokenizer = new StringTokenizer(s, ",()", true);
            token = null;
        }
        
        /**
         * Equivalent of StringTokenizer.hasMoreTokens().
         * 
         * @return The next token.
         */
        public boolean hasMoreTokens() {
            return token != null || tokenizer.hasMoreTokens();
        }
        
        /**
         * Equivalent of StringTokenizer.nextToken().
         * 
         * @return The next token (with leading and trailing
         *         whitespace trimmed).
         */
        public String nextToken() {
            if (token != null) {
                String temp = token;
                token = null;
                return temp;
            }
            else {
                return tokenizer.nextToken().trim();
            }
        }
        
        /**
         * Returns a single token to this PushbackTokenizer, so that
         * hasNextToken() will return <code>true</code> and the next
         * call to nextToken() will return this same token again.
         * Only one token (the most recently pushed back) is remembered.
         * 
         * @param token The token to be returned by the next call to
         *              nextToken().
         */
        public void pushBack(String token) {
            this.token = token;
        }
    }
}