Binary Search Trees

Overview

The first part of your project consists of implementing 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 these classes can be found at javadoc documentation.

The second part of your project consists of developing a simple news manager. Similar to an RSS reader, this manager will allow you to see news, and select which news to see from different sources.

Objectives

The objective of this project is to implement a polymorphic binary search tree. This project is designed to help you develop your skills at recursion, polymorphism and testing.

Grading

(55%) Tests
- (5%) Public JUnit tests
- (25%) Release JUnit tests
- (25%) Secret JUnit tests
(15%) Student Tests
(30%) News Manager Application

Clarifications

Any clarifications or corrections associated with this project will be available at Clarifications

Code Distribution

The project's code distribution is available by checking out the project named Bst. The code distribution provides you with the following:

A package named applet - Includes a demo applet that makes use of the search tree map. You can ignore this applet if you wish.
A package named searchTree - Includes the tree classes/interfaces.
A package named tests - Includes the public tests (PublicTests.java) and a shell for a class (StudentTests.java) that you must complete with your own tests.
A package named newsManager - In this package you will implement the news manager application.
PublicTests.java - This class represents the set of JUnit public tests.
StudentTests.java - This class represents the tests you must provide for your code.

Binary Search Tree Specifications

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 two test cases 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.

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.

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:

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

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.
You may not check whether a tree is empty by using comparisons similar to the following:
- left==EmptyTree.getInstance()
- tree.size()==0
- Other comparisons similar to the above
You are expected to use polymorphism (and exception handling, where appropriate) to handle the differences between empty and nonempty trees. Failure to do so will result in a large negative adjustment to your project grade.
You may not use Collections.sort for this project.
You may not use instanceof.
You may not use getClass().
The delete method must use the approach described in the lecture slides. You may not implement delete by creating a new tree and inserting all the keys from the source tree except the one you want to delete.
For the Subtree method you may not create an empty tree and traverse the whole tree inserting only those entries within the specified range. If a simple check will tell you that an entire subtree can be excluded, your implementation should not traverse that subtree.
You can ignore the TreeSpeed class that is part of the code distribution. This class is used to compare the efficiency of the SearchTreeMap and the TreeMap class. Feel free to run it if you want to see some performance results.

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

News Manager Application

You will use the SearchTreeMap map to develop an application that allow us to examine news items present in text files. The project code distribution has a folder named "News" that provides sample files that can be used by the application you will write. The application will allow you to see news that have taken place in a particular period of time. You can see news from one source/feed or from several sources simultaneously. Notice that the application assumes the files reside in the local system. The format of each file entry is time, followed by the news item (e.g., 10:00am Free music concerts in Italy).

The following Video illustrates the functionality expected for this application.

Specifications

You can assume that not two entries in a file occur at the same time.
You can assume the user will provide correct data.
Add News Source Functionality - Adds a new source to the database. A news source consists of a name and the file with the news.
Get News - Allows you to retrieve news from one or more news sources. News that are within the specified time range will be returned. If no times are provided all news associated with the source(s) will be returned.
Get News Sources - Returns the names of news sources.
Update News - Reloads data from the file associated with a news source.
Your GUI does not need to exactly match the GUI you see in the video.
The format of the news items displayed does not need to exactly match what you see in the video.
You must use a SearchTreeMap to map a time instance to a news (String) instance.
Feel free to use HashMap, HashSet, ArrayList, etc. in your implementation. However, do not use TreeMap (use SearchTreeMap instead).

Requirements

Make sure you define a class named NewsManagerGUI.java which we can use to run the news manager application (it must have a main method we can run). Define this class in the newsManager package. Feel free to define any classes you need to develop the news manager, but make sure you define the NewsManagerGUI class.
Verify that your project passes the submit server tests (https://submit.cs.umd.edu/)
You must attempt to submit your project immediately after checking out the project (even if you have not implemented any methods). This will allow you to verify that the submission process is working as expected.
You should submit your project often. This will keep versions of your project in the submit server that are easy to retrieve (you can also get previous versions from your CVS repository). If your computer crashes or you experience any other problem you will have a permanent backup in the submit server.
You have three tokens for this project in the submit server.
IMPORTANT → If you have a problem with your code and need assistance during office hours, you need to have a student test(s) that illustrates the problem you are experiencing.
See Student Tests for information regarding the implementation of student tests for this project.
See Style Guidelines for information regarding style.

Additional Requirements for Students in CMSC 132H (Honors)

Students in the honors section may need to complete this part. Talk to your instructor to verify if this is the case.

In addition to the above requirements, you must 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.

Suggestions on How to Start/Implement This Programming Assignment

Understand how a traditional (non-polymorphic) tree works.
Check the polymorphic list implementation we discussed in lecture.