Purposes:

• To reinforce the idea of ADTs (Abstract Data Types)
• To get you started with linked data structures
• To get you started using generics
• To give you more practice with recursion

General Idea:

Implement binary trees, and use binary trees to represent and evaluate arithmetic expressions. Use Eclipse. Provide good Javadoc documentation for all public fields, constructors, and methods.

Details:

An abstract data type (ADT) has a contract with its users, which is specified by its public members and described via Javadoc. It provides certain operations, and restricts access to only those operations. Your BinaryTree class will be such an ADT.

A binary tree is composed of nodes. Each node has a value, a left child, and a right child. The left child may be null, or may be (a reference to) some other node, and similarly for the right node. For consistency with Java 5.0 collection classes, the binary tree class will be "genericized"--that is, when we create the binary tree, we specify the type of value it may hold

In addition, any class is responsible for ensuring the validity of its data. In this assignment, you are to take that responsibility very, very seriously. Make all fields private, use getters and setters only as necessary, and JUnit test everything.

Your assignment is to define the following classes and methods.

public class BinaryTree<T>

This is your ADT class. Each BinaryTree object represents a single node; however, nodes are linked together, so that any node may be considered as the "root" of a complete binary tree. As far as the implementation is concerned, there is no difference between a "node" and a "binary tree." When we talk about it, however, we usually say "node" to refer to a single object, and "binary tree" to refer to that object along with its children, its children's children, etc.

Your BinaryTree<T> class should have the following fields:

private T value

The value in this node.

private BinaryTree<T> leftChild

This is a reference to another binary tree of the same type. It will be null if this BinaryTree node has no left child.

private BinaryTree<T> rightChild

This is a reference to another binary tree of the same type. It will be null if this BinaryTree node has no right child.

Your BinaryTree class should have the following constructors:

public BinaryTree(T value)

Simply calls the other constructor, with null for each child.

public BinaryTree <T> (T value, BinaryTree<T> leftChild, BinaryTree<T> rightChild)

Puts the value in the node, and uses setLeftChild and setRightChild to add the children.

Your BinaryTree class should have the following methods:

public T getValue()

Returns the value in this node.

public void setValue(T value)

Sets the value in this node.

public BinaryTree<T> getLeftChild()

Returns the left child of this binary tree (which may be null).


public BinaryTree<T> getRightChild()

Returns the right child of this binary tree (which may be null).


public void setLeftChild(BinaryTree<T> newLeftChild)
           throws IllegalArgumentException

Replaces the current left child of this binary tree with the newLeftChild, provided that the resultant binary tree is valid (see below). If the operation would result in an invalid binary tree, the binary tree is unchanged and the method throws an IllegalArgumentException.


public void setRightChild(BinaryTree<T> newRightChild)
           throws IllegalArgumentException

Replaces the current right child of this binary tree with the newRightChild, provided that the resultant binary tree is valid (see below). If the operation would result in an invalid binary tree, the binary tree is unchanged and the method throws an IllegalArgumentException.


public boolean isLeaf()

Returns true if both children of this binary tree are null. This is a convenience routine: The user could do without it.


public boolean equals(Object object)

Compares two binary trees for equality. Returns true if (1) the given object is a binary tree, and (2) the value fields of the two trees are equal, and (3) the left subtrees are equal, and (4) the right subtrees are equal.

Notes:

1. You have to be very careful of nulls; they have to be compared using ==, while non-null objects must be compared using equals(Object).
2. This method is recursive.
3. You will need this method in order to do unit testing on your BinaryTree class.

A binary tree will be considered valid if there are no loops in it. If, starting from some node in the tree and following child links you can get back to the same node, then there is a loop and the tree is invalid. You need to test for validity in the setLeftChild and setRightChild methods. We will, however, allow subtrees to be shared, provided there are no loops.

Use the following algorithm: Before you add a child c to a node n, search c (which is itself a binary tree) to see if node n already occurs in it. If it does, we refuse to set the child, as that would create an illegal loop. If it does not, we can go ahead with the operation. Note that (1) we are searching for the identical (==) node, not an equal one, and (2) the search is inherently recursive.

You will need a (recursive) private search method to implement the test. Since the search method will be private, you cannot test it explicitly with JUnit--rather, you test it implicitly, by making sure that your setLeftChild and setRightChild methods will throw an exception when asked to construct an invalid binary tree.

By the way, there are two reasons for allowing shared subtrees: First, this extension is (usually) harmless, and occasionally useful. Second, the test to prevent this from occurring can be very expensive.

interface Operation {
     int evaluate(ArithmeticExpression x,
                  ArithmeticExpression y);
}

Implement this interface with the following classes:

• public class Add -- the evaluate method evaluates its arguments and returns their sum
• public class Subtract -- the evaluate method evaluates its arguments and returns their difference (first - second)
• public class Multiply -- the evaluate method evaluates its arguments and returns their product
• public class Divide -- the evaluate method evaluates its arguments and returns their quotient (first / second)
• public class IntegerConstant -- the evaluate method ignores its arguments and returns the int that was given to it in its constructor.

Of these classes, only the IntegerConstant class requires an explicit constructor; it takes an int argument and saves it for use by evaluate.

class ArithmeticExpression extends BinaryTree<Operation>

An ArithmeticExpression class could be an ADT, but in this assignment it will just be a user of the BinaryTree class, and imperfectly implemented. You should do full JUnit testing and Javadoc documentation, but you don't need to be overly concerned about the possibility of creating invalid arithmetic expressions.

The ArithmeticExpression class has the following constructors:

public ArithmeticExpression( Operation  IntegerConstant op) throws IllegalArgumentException

Creates an arithmetic expression with op as its value and no children. The exception is thrown if the argument is null.




public ArithmeticExpression(int number)

Creates an arithmetic expression with the given int (converted to a Operation) and no children. (Hint: The body should be just super(new IntegerConstant(number));)

public ArithmeticExpression(Operation op,
                            ArithmeticExpression leftChild,
                            ArithmeticExpression rightChild)
          throws IllegalArgumentException

Constructs an arithmetic expression with the given value and children. The exception is thrown if any argument is null.

The class also has the following methods:

public int evaluate()

Computes and returns the value of the arithmetic expression. It does this by getting the Operation in this node, and sending this Operation the message evaluate, with the left child and right child of this node as the two arguments.

public void print()

Prints out the arithmetic expression, putting parentheses around every operand that isn't an IntegerConstant. Thus, for example, it might print something like ((1 + 2) + (3 + 4)). For a little extra challenge, figure out how to omit unnecessary parentheses (but this is not required).


public void setLeftChild(ArithmeticExpression x)
           throws IllegalArgumentException
public void setRightChild(ArithmeticExpression x)
           throws IllegalArgumentException

Override the inherited version of these methods and always throw the exception.

Explanation: A node in a BinaryTree may have zero, one, or two children. However, a node in an ArithmeticExpression should have either zero or two children, never just one (because we haven't defined any unary operators). These methods can create a node with a single child; we have to prevent this.

Note that, within our ArithmeticExpression class, we can still use the inherited methods by saying super.setLeftChild(...) and super.setRightChild(...).

You do not need to unit test the methods inherited from BinaryTree--if the methods worked for other binary trees, they will work for this one. You do need to unit test the above three methods, however.

public class BinaryTreeTest

This is a JUnit test class for the BinaryTree class. Be thorough, and don't forget to test that exceptions are thrown when they should be.

public class ArithmeticExpressionTest

This is a JUnit test class for the ArithmeticExpression class. Be thorough, and don't forget to test that exceptions are thrown when they should be.

public class OperationTest

It seems a bit silly to write a separate JUnit test class for each of the (very small) classes that implement Operation. You can combine these few tests into a single class. Be thorough, and don't forget to test that exceptions are thrown when they should be.

public class AllTests

This class will perform all JUnit tests.

How to proceed:

Let Eclipse do a lot of the work for you. Write the classes first as stubs (empty method bodies, or bodies that just return some constant value of the right type). Spend some time getting rid of the syntax errors, then ask Eclipse to generate the test classes for you. Check off the methods you want to test, and Eclipse will generate test classes already containing those methods.

Second, fill in the test methods and try them. They should all fail. Any test that doesn't fail at this point is probably a bad test. Fix it.

Finally, pick some one failed test, and work on the "real" code until you get that test to succeed. (You may also have to correct the unit tests themselves.) Repeat until done.

Macintosh users:

You have a choice of using one of the lab computers to do your work, or doing it in Java 1.4 without generics. If you use Java 1.4, you must make ArithmeticExpression a type-safe class, as described in my Generics Slides.

This basically involves:

• Not extending filling the ArithmeticExpression class, but using it as an instance variable.
• Writing a new version of every method in the ArithmeticExpression class, with the same signatures. Most of these will simply call the corresponding method in the ArithmeticExpression class, and possibly do a bit of casting.

You should also take into account the fact that this class will be used in the next four or five assignments; so whatever you decide, you will be kind of stuck with it. (But not entirely; I just rewrote an old class to be Java 5, and it went very fast.)

Due date:

Please turn in your initial JUnit tests by Tuesday, February 1. Turn in your complete program, including all Java source and class files (and revised JUnit tests) and all Javadoc generated documentation, via Blackboard, before midnight Tuesday, February 8.