CIT 594 Assignment 1: Tree API
Spring 2009, David Matuszek

Purposes of this assignment:

• Refresh your familiarity with Java.
• Introduce the Tree data structure.
• Give you practice with recursion.

General idea of the assignment:

A tree is a data structure composed of nodes, where each node contains a value of some arbitrary type, and a list of zero or more children, each of which is also a node. In this data structure, essentially each node is a tree.

In this assignment you are to build a simple Tree API. This API will enable you to create trees, read and write trees, and do basic navigation.

Details:

This will be a genericized class--that is, when you construct a tree, you specify the type of values it can hold.

public class Tree<V> {...}

public Tree<V>(V value) (Eliminate the <V> here)

Creates a tree consisting of a single node, having the given value. It should also create an empty ArrayList to hold its (future) children.

public Tree<V> addChild(Tree<V> child) throws IllegalArgumentException

Adds the given Tree child as the new last child of this Tree.

You need to write this method very early, because without it you will only be able to create single-node trees. However, you can't really test it until you have the next method (equals) also written.

Don't worry about throwing an IllegalArgumentException until after you have written and tested the contains method. Once that is done, come back and modify this method to throw the exception when tree1.addChild(tree2) is called, and tree2.contains(tree1). This would create a loop, or cycle, in the Tree, which is illegal.

public Tree<V> addChild(V value) throws IllegalArgumentException

A simple convenience method for addChild(new Tree(value)).

@Override
public boolean equals(Object obj)

Tests whether this Tree is equal to the given Object; returns false if the Object is not a Tree.

This is a highly recursive method. Two trees are equal if their values are equal (according to their equals method), and they have the same number of children and all their children are equal and in the same order.

It is important to write this method early, and test it thoroughly, so that you can use it in JUnit tests of the other methods.

@Override
public String toString()

Returns a String representation of this Tree, with the format
     value(child_1 child_2 ... child_N)

Sometimes people try to JUnit test whether Trees (or other data structures) are as expected by comparing their String representations. Don't do this! (1) It ties you to a very specific String representation, and (2) it's wrong anyway, since different values (such as 2 and '2') can have the same String representation.

public List<Tree<V>> children()

Returns the ordered list of the children of this Tree. (This is a one-line method.)

public Iterator<Tree<V>> iterator()

Returns the iterator for the list of children of this Tree. (One line.)

public void setValue(V value)

Sets the value field in this Tree, that is, the value in the root). (One line.)

public V getValue()

Returns the value in this Tree, that is, the value in the root. (One line.)

public static Tree<V><String> parse(String s)

Returns a Tree corresponding to the given String. All values in the resultant Tree will be of type String.

This is the most difficult method. Here's my suggested approach: Use a StringTokenizer to get "tokens" from the input string. Use the settings
        new StringTokenizer(s, " ()", true)
this will return parentheses, spaces, and "words" (not containing spaces or parentheses) as "tokens". Discard the spaces and put the remaining tokens into an ArrayList. Pass this list to a second (private) parse method. This method should do something approximately as follows:

Get a value for the root (or return null)
If there is an open parenthesis,
    Parse each tree inside the parentheses and add it to the root
    Get the close parenthesis
Return the tree

public void print()

Prints the tree, in indented, multi-line format. Since this is an output method, it does not require JUnit testing. This method should also be recursive.

public boolean contains(Tree<V> tree)

Tells whether this Tree contains the identical (in the == sense) node as the given tree. This method should also be recursive.

Examples:

Given this Tree:	toString() should return: one(two three(four five(six seven eight)))
	print() should print: one | two | three | | four | | five | | | six | | | seven | | | eight

Structure of the assignment:

• Project name: DS01 (dee-ess-zero-one)
• Package name: support
• Class names and method signatures:
  • class Tree
    • public Tree<V>(V value) // constructor
    • @Override public boolean equals(Object obj)
    • @Override public String toString()
    • public Tree addChild(Tree child) throws IllegalArgumentException
    • public Tree addChild(V value) throws IllegalArgumentException
    • public List children()
    • Iterator<Tree<V>> iterator()
    • public void setValue(V value)
    • public V getValue()
    • public Tree<V> parse(String)
    • public void print()
    • public boolean contains(Tree<V> tree)
• Provide JUnit tests for: All assigned constructors and methods, unless noted otherwise.
• Provide Javadoc documentation for: All classes and methods, except JUnit tests
  • Document JUnit tests if they are complex or do something non-obvious
• Name to use for Blackboard: DS01_yourName

The above are requirements. You may have additional classes and methods as needed, and they should be documented and unit tested as appropriate.

Grading:

Due date:

Thursday, January 22, before midnight. Zip the complete Eclipse project and submit via Blackboard.