Simple Map

Objectives

• Working with maps.
• Implementing a binary search tree.

Instructions

For this assignment, you will implement a map using an underlying binary search tree. This is an expansion on Learning Activity 8.

You may also find it helpful to create test cases.

Here are three interfaces for the map. They correspond to the three levels for the assignment:

• BasicMap.java
• BetterMap.java
• ImprovedMap.java

For the minimal version of the assignment, create an implementation for the interface, BasicMap. This implementation is quite similar to a solution to Learning Activity 8. There are a few changes, but relatively few. (Planning can help you leverage your work on LA8 for the assignment.)

For the standard version implement the interface, BetterMap, which has two additional methods: containsValue and remove. See the binary search tree notes for hints about remove.

For the challenge version, implement the interface, ImprovedMap, which add a single method to the map, one which returns a set of the keys for the map. To make the set that is returned useful, it should be iterable. A new set interface, BetterSet, is provided which includes an iterator method that returns a simplified iterator, SimpleIterator. Download the associated interfaces and implement them.

• BetterSet.java
• SimpleIterator.java

The implementation class(es) shall be in csc143.data_structures.

Here are a few notes:

put:

The put method shall disallow null arguments for either the key or value parameters. Null arguments shall raise an IllegalArgumentException.

toString

The toString method is similar to the toString method of Lab 8. However, the key-value pair needs to be given for each entry in the map. The toString return value will indicate the structure of the underlying tree. See image.

Nested parenthetical for the map shown above would give:

(5:five (2:two (1:one () ()) (3:three () (4:four () ()))) (6:six () (7:seven () ())))

Report

While this could be thought of as an addendum to the Stack/Queue project, we'll let this one stand on its own. The underlying technology is rather different, a binary tree, rather than a linked list or partially filled array.

In light of what you learned there, write a report in which you describe:

• how did you go about starting this project?
• what works and what doesnt?
• the surprises or problems you encountered while implementing this application
• the most important thing(s) you learned from this portion of the assignment
• what you would do differently next time?

Deliverables

Two files:

• A .jar file with the source code (and bytecode) for your implementation(s) of the map interface(s), and associated classes, as needed. This .jar file can also include the source code (and bytecode) for your test cases, if you created them. However, this jar file should not include Java source code for unrelated homework assignments or learning activities.
• An ASCII text file with the report.