Purposes:

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

General Idea:

Implement general trees. Use Eclipse. Provide good Javadoc documentation for all public or package fields, constructors, and methods.

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 is 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, 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 classes and methods.

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.).

Your Tree class should have the following field:

public V value

Note that this field is public. Although a class is responsible for ensuring the validity of its members, it doesn't matter to us what the user does with this field, because it's just "data"--it doesn't affect the structure or validity of the tree.

Your Tree class should have the following constructor:

public Tree(V value, Tree... children)

Creates a Tree node with the given value and zero or more children.

Your Tree class should have the following methods:

public Tree firstChild()

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


public Tree 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 Tree child(int index) throws NoSuchElementException

Returns the index-th child of this tree (counting from zero, as with arrays). Throws an IllegalArgumentException NoSuchElementException if index is less than zero or greater than or equal to the number of children.


public Iterator<Tree> children()

Returns an iterator for the children of this tree. The iterator should have the usual hasNext(), next(), and remove() methods, all of which should be implemented.


public void addChild(Tree newChild) throws IllegalArgumentException

Adds newChild as the new last child of this tree, provided that the resultant tree is valid (see below). If the operation would result in an invalid tree, the tree is unchanged and the method throws an IllegalArgumentException.


public void addChild(int index, Tree 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 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.)


public boolean hasChildren()

Returns true if this node has children. This is a convenience routine: The user could just test node.numberOfChildren() > 0 instead.


@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 objects 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 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. For example:

	Prints as: one two five three four six seven
The result of calling toString() should be: "one\n two\n five\n three\n four\n six\n seven\n"

Notes:

• There are no getter or setter methods for value. They are unnecessary because this is a public field and we don't care how it is used.
• Trees are strictly "one way": You can get from a node to its children, but you can't get from a node to its parent.
• Because trees are one way, there is no way to tell if a given node is a root (has no parent).

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 child occurs in the tree whose root is parent, and test if node parent occurs in the tree whose root is child. If either of these conditions occurs, do not perform the operation, but instead throw an IllegalArgumentException instead. Note that (1) the tests must search for identical (==) nodes, not just equal ones, and (2) the search is inherently recursive.

You will need a private search method to implement the tests. Since this search method will be private, you cannot test it explicitly--rather, you test it implicitly, by making sure that your addChild methods will throw an exception when asked to construct an invalid tree.

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() has the correct spaces and newlines.

Implementation:

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

Your equals(Object) and toString() methods, and the search method you use to look for potential loops, must be recursive. You may not use a Stack, Vector, additional ArrayList, or similar data structure, to implement these methods.

Please use TDD (Test-Driven Development). This means:

Doing things a little at a time this way is almost sure to reduce the amount of time you spend debugging.

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 Tuesday, January 24.