The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science

CSci 131 -- Data Structures
Project #5

Due Date: week 13

(A) Modify the private part and body of your generic table handler from projects 3 and 4 so that a table is implemented as a binary search tree.

Re-test using the same instantiations and tests you used in the previous projects. An important goal of this project is to show the advantage of having a general and well-thought-out interface to a package like this, so that it is possible to change implementations without causing any client code to be modified.

In this project, it is OK to use the generic binary search tree package given in Chapter 11, but you will be held responsible for understanding it, so please study it in addition to just using it.

(B) Now you are going to write a different client program that uses the table package. Consider a grocery store inventory system to keep track of products. Each product record will have:

• the last five digits of the universal product code (UPC) as a key, so the key range will be 00001..99999;
• a 25-character string for product description;
• a non-negative float value for the price per item;
• a nonnegative integer value for the number of items on hand in the store;
• a nonnegative integer value for the reorder quantity, i.e., if the quantity on hand dips below this value, the item will be re-ordered.

Your menu-driven program will need to handle these transactions:

• add a new product to the inventory; delete a product from the inventory;
• record a sale (reduce quantity on hand) or return (increase it); note that this is a good use of the retrieve/replace package operations! This operation should report to the screen when a product needs to be reordered.
• change the price of a product
• add to the quantity on hand of the product

Develop this client and test it. Here are a few products you can start with:

65213 Breakfast Krunch, small 2.95 20 5

77777 Ground Round, pound 3.95 5 1

23459 Shine-em-up Toothpaste, large 2.75 10 2

32195 Moo-juice condensed milk 1.09 10 5

52430 Soft-Sneeze Tissues, box .95 20 10

44432 Whiter-than-white detergent 6.50 10 7

(C) Once you have this working, change the way the file is stored. Instead of keeping the entire record in the tree, keep only the key and a value that corresponds to a record number in a direct-access disk file. This will be a good simulation of a real system, in which the number of records is too large to keep in RAM, so the records themselves are stored on disk.

You should use Ada.Direct_IO to store and retrieve records from the disk file. To use it, just WITH Ada.Direct_IO in your package (the client should not know it is being used!).