CS 3500 Assignment #7: Parameterized Types and Visitors
Due: Sunday, November 10, 2013

!!! See the amendment at the bottom. !!! -- amended on November 8, 10:07 am

The purposes of this assignment are:
  * to review parametric polymorphism in Java
  * To implement the Visitor pattern.

Collaboration between students is forbidden on this assignment. You are responsible for keeping your code hidden from all other students. You will submit this assignment within Web-CAT.

Your files of Java code should begin with a block comment that lists:
    1.  Your name, as you want the instructor to write it.
    2.  Your email address.
    3.  Any remarks that you wish to make to the instructor.

Part of your grade will depend on the quality and correctness of your code, part will assess the tests you design - especially the test coverage, part will depend on the readability of your code (comments and indentation), and part will depend on how well you follow the procedure above for submitting your work.  Assignments submitted between 12:00 am and 11:59 pm the day after the due date will receive a 20 percentage point penalty on the assignment. 

You will need to make sure that you have tested BTree, RBTree, and visitors completely. You will submit your test programs, which will be graded for test coverage. Your test programs should be written using JUnit testing or the Tester library. (Your test programs should be named accordingly---ending with Test or beginning with Examples.) Web-CAT will check that you have tested each method and decision within your implementation. Make sure that you include both black and white box tests.

This assignment contains two parts: (1) parameterized types and (2) visitors. 

Part 1:
----------

Convert your representation of the BTree and red-black trees (from Assignment 6) into a version parametrized by the type of elements that the tree will contain---BTree<T> and RBTree<T>. Add tests to your test program that use at least one data type other than Strings.

You should keep the default and rbtree packages that were required for Assignment 6. While the name of your red-black tree implementation was not specified in Assignment 6, for this assignment, the implementation must be named RBTree.

Part 2:
----------

We can define a visitor interface for the RBTree based on how we defined Binary Search Trees earlier this semester and the added notion of color. 
      Binary Search Tree (BST)
        - t is empty
        - t is a node
            - a label
            - the left subtree of t is a BST,
            - the right subtree of t is a BST,
            - every label within the left subtree of t is less than the label of t (based on Comparator),
            - every label within the right subtree of t is greater than the label of t (based on Comparator)

For the assignment, you will use the following interface:

/**
 * A visitor for RBTree
 * @author CS3500f13
 * @version 2013.11.01
 *
 * @param <T> the type of data stored in the RBTree
 * @param <R> the type of data produced by the visitor methods
 */
public interface RBTreeVisitor<T, R> {
    /**
     * The method for the empty tree
     * @param comp the Comparator for the whole tree
     * @param color the color of the node, which should be "RED"
     *        or "BLACK"
     * @return some value of the type R
     */
    public R visitEmpty(Comparator<T> comp, String color);
    
    /**
     * The method for the node of the tree
     * @param comp the Comparator for the whole tree
     * @param color the color of the node, which should be "RED"
     *        or "BLACK"
     * @param data the label/value for the node
     * @param left the left subtree of the node
     * @param right the right subtree of the node
     * @return some value of the type R
     */
    public R visitNode(Comparator<T> comp, String color, T data, 
                     RBTree<T> left, RBTree<T> right);
}

The interface is located in the course directory:
    /course/cs3500f13/Assignments/A7

You will need to add the appropriate accept methods to your RBTree class and subclasses.

If you implemented RBTree with the structure we discussed in class (abstract RBTree with concrete subclasses for Empty and Node), then your accept methods in each subclass will call the corresponding visit method. If you did not implement RBTree in this way, you will have to decide when each visit method is appropriate for your implementation.

You will design the following classes that implement this visitor interface:

 - visitor PathLengths that produces an ArrayList of the lengths of the paths from the root to each empty---the length should not include the empty.
 - visitor Height that computes the length of the longest path in the tree.
 - visitor BlackHeight that returns the black height of the tree---number of non-empty black node from the root to any empty node.
 - visitor CountNodes that returns an ArrayList with three elements---index 0: number of non-empty nodes, index 1: number of non-empty black nodes, index 2: number of non-empty red nodes.

The visitor classes will be defined by the client within the default package. Each visitor should work on RBTrees of any type.

Make sure the visitor classes are named as given above.

-------------------------------------------------------

Additionally: (amended on November 8th 10:07 am)


Within your BTree implementation, you must add the following method:

    /**
     * Method that accepts a visitor that produces a value of the type R
     * *param v the given visitor
     * *param <R> the type of elements this tree holds
     * *return the result of the visitor method
     */
    public <R> R accept(RBTreeVisitor<T, R> v){
        //NOTE: tree is the name of my RBTree field. You would replace tree 
        // with the name of your RBTree field.
        return tree.accept(v); 
    }