CIT 594 Assigment 2: Tree ADT
Spring 2010, David Matuszek

Purposes:

General Idea:

An Abstract Data Type is a data type that you can use without knowing any of the details about how it has been implemented (the implementation has been "abstracted" away). Generally, this means you have no direct access to the data; your only access is via the methods provided.

Your assignment is to:

Use Eclipse.

Details:

An abstract data type 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 Tree class will be such an ADT.

In addition, any class is responsible for ensuring the validity of its data. In this assignment, you are to take that responsibility very seriously for the Tree class.

A tree is composed of nodes. Each node has a value, and may have children. The Tree class will be genericized, so that you can specify the type of values in the nodes; the children will be (references to) nodes.

Your assignment is to define the following class, variables, and methods.

The class

public class Tree<V>
This is your ADT class. Each object in the Tree class represents a single node; however, nodes are linked together, so that any node may be considered as the "root" of a complete tree. In the following, the terms "node" and "Tree" are synonyms, but I tend to use "node" when I'm talking about one specific object of type Tree, and "Tree" when I'm referring to that node and all its descendents (children, children of children, etc.).

Constructor

public Tree(V value, Tree<V>... children)
Creates a Tree node with the given value and zero or more children.

Note: The "..." syntax means that you can call the constructor with new Tree(v), or new Tree(v, c1), or new Tree(v, c1, c2), or new Tree(v, c1, c2, c3), etc., but when you write the code inside the constructor, you write it as if it were defined as Tree(V value, Tree[] children).

Accessors

An accessor is a method that returns some information about the data type.

public V getValue()
Returns the value in this node of the Tree.
public Tree<V> firstChild()
Returns the first child of this tree (which may be null).
public Tree<V> lastChild()
Returns the last child of this tree (which may be null).
public int numberOfChildren()
Returns the number of (immediate) children of this node.
public boolean isLeaf()
Returns true if this node has no children. This is a convenience routine: The user could just test node.numberOfChildren() == 0 instead.
public boolean contains(Tree<V> node)
Returns true if this tree contains the given node (not an equal node; use ==, not equals). The root of this tree is included in the recursive search.
public Tree<V> child(int index) throws NoSuchElementException
Returns the index-th child of this tree (counting from zero, as with arrays). Throws a NoSuchElementException if there is no such child (that is, if index is less than zero or greater than or equal to the number of children).
public Iterator<Tree<V>> children()
Returns an iterator for the children of this node. The iterator should have the usual hasNext(), next(), and remove() methods, all of which should be implemented.
@Override
public boolean equals(Object object)
Returns true if (1) the given object is a Tree, and (2) the value fields of the two trees are equal, and (3) each child of one Tree equals the corresponding child of the other Tree. Notes: (1) You have to be very careful of nulls; they have to be compared using ==, while non-null values must be compared using equals(Object), and (2) this method is recursive. Also note that you will need this method in order to do unit testing on your Tree class.
@Override
public String toString()
Returns a single line representation of this Tree, where each node is represented by the String representation of its value, and the children of each node are separated by spaces and enclosed in parentheses.
public String toLongString()
Returns a multiline representation of this Tree. Each line contains the toString() representation of the value in that node, terminated with a newline (\n). Each child is indented two spaces under its parent.
Examples:
valid and invalid trees
For this Tree, toString() should return:
"one(two(five) three four(six seven))"

and toLongString() should return:
"one\n  two\n    five\n  three\n  four\n    six\n    seven\n"  
This should print as:
one
  two
    five
  three
  four
    six
    seven

Transformers (mutative)

A transformer is one that, applied to a data structure, produces a different data structure. A mutative transformer is one that changes the data structure to which it is applied (for example, the add method of the ArrayList class). An applicative transformer is one that produces a new data structure of the same kind (for example, the toLowerCase method of the String class).

public void setValue(V value)
Sets the value in this node of the Tree.
public void addChildren(Tree<V>... children ) throws IllegalArgumentException
Adds each Tree in children as a new child of this tree node, after any existing children, provided that the resultant tree is valid (see below). If the the addition of any child node would result in an invalid tree, that node is not added, tree modification is halted, and the method throws an IllegalArgumentException.
public void addChild(int index, Tree<V> newChild) throws IllegalArgumentException
Adds newChild as the new index-th child of this tree (counting from zero), provided that the resultant tree is valid (see below). The child previously at this index, and all subsequent children, are "shifted right" (their index is increased) to make room for the new child. If the index is less than zero or greater than (not greater than or equal to) the current number of children, or if the operation would result in an invalid tree, the tree is unchanged and the method throws an IllegalArgumentException.
public Tree<V> removeChild(int index) throws NoSuchElementException
Removes and returns the index-th child of this tree, or throws a NoSuchElementException if the index is illegal. (This method, and the remove() method of the above Iterator, simply remove the child from the list of children of this tree; no major tree surgery is involved. The removed subtree remains intact.)

Notes:

A 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 addChild methods. We will, however, allow subtrees to be shared, provided there are no loops.

Use the following algorithm. Before adding a node child as a new child of node parent (each of which may be inside some tree structure), test if node parent occurs in the tree whose root is child. If it does, do not perform the operation, but instead throw an IllegalArgumentException. Note that (1) the test must search for an identical (==) node, not just an equal one, and (2) the search is inherently recursive.

Why shared subtrees?

Shared subtrees are occasionally useful. For example, if you were to evaluate the tree equivalent of the expression (x - y) * (x - y), you might be able to do so in such a way that you evaluate (x - y) only once.

Usually, however, trees are defined in such a way that shared subtrees are not allowed. Furthermore, I do not expect to make use of shared subtrees in this course. However, while it is fairly simple to do a recursive search to disallow loops in a tree, it is much more difficult to detect (and disallow) shared subtrees. Since shared subtrees are generally harmless, it is easier to allow them than to try to prevent them.

public class TreeTest

As part of the assignment, write, use, and turn in a JUnit test class for the Tree class. Be thorough, and don't forget to test that exceptions are thrown when they should be.

When grading your program, we will use our own JUnit tests, as well as or instead of yours, so be sure to follow the above specifications exactly. Be especially careful that your toString() and toLongString() methods produce exactly the characters specified.

Implementation:

The best way to keep the children of a node is in an ArrayList. If a node has no children, your code will be simpler with an empty ArrayList than with a null value for children.

The equals(Object), contains(Tree<V>), toString(), and toLongString() methods must be recursive. You may not use a Stack, Vector, additional ArrayList, or similar data structure, to implement these methods.

Use TDD (Test-Driven Development). This means:

Write stubs for all the methods. (Methods which return a value should return the value that is most likely to be wrong.)
Use Eclipse to generate stubs for all the JUnit4 test methods.
while (not all methods have been written and tested) {
    while (
some method is incomplete) {
                Write (or add to) a test for that method.
                Run the tests, and make sure the new test fails.
                Add just enough code to the method to pass the test.
    }
}  

To get started, you first need to write the constructor, and you need to write the equals method. After that, it's best to build up the methods and their tests a little at a time; for example, you will probably want to write the addChild method fairly early, but you can't test whether it correctly throws an IllegalArgumentException until you have also written the contains method. Doing things a little at a time this way is almost sure to reduce the amount of time you spend debugging.

To save you a bunch of routine copying and pasting from this page, here's a bare-bones Tree.java file for you to start with. It includes the necessary comments for the assigned methods. Do not change the signature of any assigned method, or it will fail our JUnit tests.

Due date:

Please zip up and turn in your completed program, including all Java source and class files and all Javadoc generated documentation, via Blackboard, before midnight Friday, February 5 .