Circular Data and Binary Search Trees

This lab will give you practice with circular data definitions and binary search trees. We will use an extension of last weeks test harness.

Part I: Testing

To start download we will download a skeleton project for the lab.
TODO: Import the file lab8.zip and import the project lab8 into your workspace.
We will first look at the new (slightly) different test harness, and the only difference between this harness and last weeks is that this one provides the following method: 
TestHarness.runTests(Object o)
where o should contain methods that start with test and take no arguments. So, to create a test case, say ExampleTest, add methods starting with test, and add a call to TestHarness.runTests in the main method. For example: 
class ExampleTest {
  //
  // The test methods
  //
  void testOne() { ... }
  void testTwo() { ... }
  void testSomething() { ... }
  ...
  void testNth() { ... }

  public static void main(String[] args) {
    //
    // Will run methods testOne, testTwo, ...
    //
    new TestHarness().runTests(new ExampleTest());
  }
}
Refer to the previous lab for information what to put in these methods. For example of using this new class download the following files as in last week and inspect the main method: The idea is is that tests are so important and we want it to be as easy as possible to test your programs.

Part II: Circular Data

In this part we'll visit a familiar concept where circular data exists -- namely, buddy lists. These buddy lists could be IM buddy lists, ICQ ubuddy lists, or lists of friends on social networks. Inuitively a buddy list is just a username and a list of other buddies; the latter part is where we get circularity. So, start by working with the following files:
Buddy.java  -  simple representation of a buddy
ALoBuddy.java  -  abstract list of buddies
MTLoBuddy.java  -  empty list of buddies
ConsLoBuddy.java  -  cons list of buddies
BuddyTest.java  -  tests for buddies
We'll start by implementing some intial methods:
TODO: So start by implementing the same(Object) method in Buddy and each list of Buddy and writing some test cases in the appropriate methods in BuddyTest. Also implment contains in the lists. Note the same in a list of buddies should only check that the two list contain the same values; not necessarily in the same order.
No, we would like to ask some pretty common questions, e.g These three methods will have the form a So, start by implementing hasDirectBuddy using the design recipe and fully test it.
TODO: Implement hasDirectBuddy using the design recipe and fully test it.
Now implement countCommonBuddies using the design recipe and fully test it.
TODO: Implement countCommonBuddies using the design recipe and fully test it.
BONUS

This was easy! The next one is little tougher... you know you'll have to traverse along the buddy lists with an accumulator, unlike the examples you've seen where you can simply say give me the next node (or buddy) to search buddies may have multiple buddies so deciding the next buddy to search will take a little thought... so think!!! sooo....

TODO: Implement hasDistantBuddy using the design recipe and fully test it.

Part III: Binary Search Trees

We will build two versions of binary search trees (BSTs) in this lab. The first is one as we've seen before. The second is mutable so that, as you've seen in class, when insert or remove data in the tree we won't necessarily be creating a new node; instead will be changing members of that node.

BTSs

So to begin, work with the following files:
ABST.java  -  abstract node class
BSTNode.java  -  concrete inner node class
BSTLeaf.java  -  concrete leaf node class
ABSTTest.java  -  test class
We first need to make these classes testable, so add the appropriate same methods.
TODO: add the method same(Object) to the concrete classes BSTNode and BSTLeaf.
Now that we've added this method we need to test it, so...
TODO: add some examples of BSTNodes and BSTLeafs and test the same method in the method testSame of class ABSTTest.
Now, using the design recipe, we will implement insert and test it.
TODO: add the method insert to the concrete classes BSTNode and BSTLeaf.
Now, using the design recipe, we will implement remove and test it.
TODO: add the method remove to the concrete classes BSTNode and BSTLeaf.

Mutable BTSs

We will now create some mutable BTS classes and test them. We will work with the following files:
ABST.java  -  abstract node class
MutatingBSTNode.java  -  concrete inner node class
MutatingBSTLeaf.java  -  concrete leaf node class
Tree.java  -  wrapper class for a mutable tree
MutatingABSTTest.java  -  test class
To begin we need to add setter methods so we can change the members of these classes. So, for every data member
Type name;
we add the settter
void setName(Type name) {
    this.name = name;
}
So, for every data member in the concrete class MutatingBSTNode (not MutatingBSTLeaf, because it has no members), add setters for the following members:
TODO: add setters for all data members in MutatingBSTNode
Now we need to make these classes testable, so add the appropriate same methods.
TODO: add the method same(Object) to the concrete classes MutatingBSTNode and MutatingBSTLeaf.
Now that we've added this method we need to test it, so...
TODO: add some examples of MutatingBSTNodes and MutatingBSTLeafs and test the same method in the method testSame of class MutatingABSTTest.
Testing a mutable method is slightly different than a normal method, because you can't just test the result, you need to observe the change. For example, you need to run test(s) before the mutation and after the mutation.

So, now, using the design recipe, we will implement insert and test it.

TODO: add the method insert to the concrete classes BSTNode and BSTLeaf.
Now, using the design recipe, we will implement remove and test it.
TODO: add the method remove to the concrete classes BSTNode and BSTLeaf.
Now, we want a wrapper class that represents a mutable tree, called Tree, that actually contains an ABST. This class has the same methods as ABST except for two new ones: So,
TODO: add the method add and isLeaf to Tree and fully test it.