Maps exercises

Com 1201 – Spring 2003 – Jeff Raab

Introduction

In this exercise set you will write code that implements the Map ADT, and write strategies for solving a simple – yet deep – problem by using a map to store information. You must follow the course guidelines for type- or handwritten answers, diagrams, and writing code, as posted on the course website.

Programming exercises

LinearProbingMap

# Item[] items

# IHashFunction h

# Item FREE

+ LinearProbingMap()

+ void insertItem(

Object key, 

Object element)

+ Object lookupElement(

Object key)

+ Object removeElement(

Object key)

+ int size()

+ boolean isEmpty()

# boolean shouldRehash()

# void rehash()

1. Write a class named LinearProbingMap that implements the given IMap interface using a linear probing hash table to store the elements. Use the UML specification at the right as a guide. You must have all of the methods and data listed in the UML diagram, but you may add additional methods and data as you wish.

You must write the Item class, as it is not given. It must associate a key and element to be stored in a map. You do not have to use data hiding since the Item class will only be used within this implementation.

The Item array named items represents the hash table array in which items in the map are stored. The default length for this array must be 5.

The IHashFunction named h represents the function used to hash keys to indices in the array of items. Use the factory method createHashFunction in the MapFactory class to construct a hash function to assign to the data member h.

The Item named FREE is a Singleton that represents a free index in the array of items. In the constructor you must assign each index in the array of items to refer to FREE. No index in the array of items should refer to null except in the process of creating an array of items.

The method named shouldRehash must return true if the load factor for the hash table is greater than ½ and false otherwise.

The method named rehash must reduce the load factor for the hash table by creating a new array of items whose length is twice the old array’s length, plus 1. All of the items in the map must be copied from the old, smaller array to appropriate indices in the new, larger array.

You must use the shouldRehash and rehash methods in the insertItem method.

Add tests to the MapTests class that thoroughly test each of the methods of this class, in all cases you can identify.

2. Modify the createMap method in the MapFactory class so that it produces an empty LinearProbingMap. Run the application and click the RunPostOfficeSimulation button to see your class in action.

3. Write a class named MADMethodHashFunction that implements the given IHashFunction interface using the Multiply-Add-and Divide method. The constructor for this class must take the length N of the hash table array, and int values for a and b, as input. Remember that the MAD method uses the following calculation, for a key k:

h(k) = | a ´ k + b | mod N

Add tests to the MapTests class that thoroughly test each of the methods of this class, in all cases you can identify.

4. Modify the createHashFunction method in the MapFactory class so that it produces a MADMethodHashFunction object for an array of the given length. You may choose whatever values you want for a and b in the call to the constructor. Run the application and click the RunPostOfficeSimulation button to see your class in action.

5. Run the application and click the RunWarehouseSimulation button. Complete at least one simulation run for each of the three given strategies, to see what the simulation is like, and how each of the three strategies select locations to place parcels.

Write a class that extends the abstract ACraneStrategy class and implements a strategy for placing Parcel objects in a Warehouse efficiently. For the purposes of this problem, “efficiently” means using a minimum of crane moves. For strategies that result in about an equal number of crane moves per operation, the tie breaking statistic is the amount of processing time per operation.

A full description of the Warehouse simulation is written in a separate document available on the course website. If you would like a hard copy of the document, you may print it in the computer lab.

Your strategy must be more efficient than all three of the given strategies in order to receive full credit. If your strategy is far more efficient than the given three strategies, you may receive extra credit above and beyond a perfect score for this part of the exercise.

6. Modify the addStrategies method in the MapFactory class so that it not only adds objects of the given three types to the given WarehouseApplication object, but also adds an object of your strategy type. Run the application and click the RunWarehouseSimulation button to see your class in action.

Submission

You must submit the following written and/or printed material:

• Printouts of classes and tests you wrote for programming problems

You must submit the following electronic material:

• A folder containing all of the provided files in the exercise

• Classes and tests you wrote for programming problems

Details for electronic submission are given on the course website.