Objective

The objective of this project to implement a polymorphic binary search tree.  This project is designed to help you develop your skills at recursion, polymorphism and testing.  This homework is considered a closed homework.  Make sure you read the open/closed policy before continuing working on this project. 

Project Clarifications

Any clarifications or corrections associated with this project will be available at: clarifications.html

Overview

For this project you must implement the methods of the EmptyTree and NonEmptyTree classes.  We have provided a Tree interface and a partial implementation of the SearchTreeMap class (you must implement the keyList and subMap methods).  Complete documentation for this project can be found at javadoc documentation.

Your project will be graded as follows:

• Tests (75 %)

  • Public JUnit tests  (3 %)

  • Release JUnit tests (30 %)

  • Secret JUnit tests ( 42 %)

• Student Tests (20 %)

• Style (5 %)

Testing

It is a required and graded part of your project that you develop and submit test cases that test your code. You only get the one test case in the class PublicTests, and the release tests all have unhelpful names such as testOne and testTwo. The TA's have been instructed that they should not help you debug your code unless you have written a test case on which your code misbehaves.

Using a code coverage tool, such as Clover, is one helpful tool to access whether your tests test all parts of your implementation.

In addition to the release tests, there are additional secret test cases. Don't assume that just because your implementation passes the release tests, it is correct.

Remember you must provide your own tests.

The WordCountApplet uses a SearchTreeMap to count the number of times each word appears in the file specified by a URL. You may use the applet to gauge how well your SearchTreeMap implemention works, simply select "Run As"->"Java Applet", then type in the URL of a file you wish to analyze. 

Here are some fun text files:

• http://www.cs.umd.edu/class/spring2008/cmsc132/projects/p3/data/beatles.txt
• http://www.cs.umd.edu/class/spring2008/cmsc132/projects/p3/data/lincoln.txt
• http://www.cs.umd.edu/class/spring2008/cmsc132/projects/p3/data/shakespeare.txt

Design

The SearchTreeMap class implements some of the functionality of the Map interface (although not all). A SearchTreeMap object is just a wrapper around a Tree, which is actually used to implement binary search trees.

Note that the insert and delete methods on Tree objects return references to Tree objects. In many cases, these functions may return a reference to the this object. However, in some cases they can't. For example. EmptyTree.getInstance.insert("a", "1") has to return an instance of an NonEmptyTree object.

Design and Implementation Restrictions

There are a number of design restrictions you must obey in your implementation of EmptyTree and NonEmptyTree classes:

• You may not use any form of looping construct.
• You may not use any arrays.
• You may not explicitly check a Tree to see whether it is an EmptyTree or NonEmptyTree.
• Your EmptyTree and NonEmptyTree implementations may not have any comparisons against the null value.
• You should not need to do any casting for this project. If you are casting then you are probably not using generic programming correctly.
• If you insert multiple values with the same key, only the value associated with the most recent put( ) will be saved in the map.
• You may not use any classes from java.util except ArrayList and only to implement the keyList( ) method.
• You may not add any methods.

The above restrictions do not apply to your test cases; you may write them however you wish.

Honors Section

Students in the honors section must in addition compare the efficiency of SearchTreeMap and java.util.TreeMap classes for both sorted and unsorted inputs.

• Build two tree-based maps with Integer keys. Let the position of each key be its value.
  • Sorted list of Integers. Example: (1,1), (2,2)...
  • Unsorted list of Integers. You can generate a randomized list of integers using Random r = new Random(100L); r.nextInt(500000); Example: (3915,1), (176250,2), (207874,3)...
• Compare the running time of SearchTreeMap and TreeMap when building maps with 5000 and 500,000 sorted/unsorted Integers.  You may choose smaller lists of Integers if your computer runs out of memory for large trees. 
• TreeSpeed.java provides some useful examples: generating unsorted lists of Integers & Java timing routines.
• Write a short 1-2 page report describing your results, and your guesses as to why the behavior differs. 
• Submit your report as a PDF file using the submit server, along with your project code.

Submission

Submit your project using the submit project option associated with Eclipse. 

Academic Integrity

Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects.  We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the University's Office of Judicial Program