Intermediate Programming 601.220 Final Project - Fall 2020 -------------------------- The final project in the course will try to test everything that we have learned and must be written in C++. The project has two parts. In the first part, you will design and implement a complex data structure as a template. You should test the data structure and benchmark its performance in several different scenarios. In the second part, you will design and implement an application that uses the above data structure, involving some of the concepts we learned in the second part of the course (including overloading, inheritance, and templates). Part 1 ------ Design and develop a template based on the expandable multi-level hash data structure presented in class. The data structure (repository) should support at least the following operations: 1. MLH_insert that receives a key and a pointer to an object and inserts that pointer into the repository if an object with that key does not exist already. 2. MLH_get that receives a key and returns a pointer to the appropriate object if it exists in the repository, and NULL otherwise. 3. MLH_delete that receives a key and removes the corresponding object from the repository if it exists, returning a pointer to the removed object. If the object does not exist, the function returns NULL. 4. << that prints the number of objects in the repository, the current number of levels of the deepest multi-level hash node, and the number of hash nodes in the repository. As an option, this operation will print all the keys in the repository and the object associated with each key. Such an option should be implemented using an MLH_set_print_option operation after which the option is set until further MLH_set_print_option calls. A counter should maintain the number of steps performed on the repository. The counter should be initialized to 0 and should be incremented each time a multi-level hash node is inspected in any level of the data structure. This gives an indication of how much effort was spent so far. A Random_operation class is provided in order to generate the random operations to be invoked on the repository. A ML_hash function is provided for the multi-level hash functions. Develop a benchmark program that instantiates your data structure template for an object that includes a single integer. The integer should contain the index of the current operation performed (the first operation has an index of 1). Perform the following benchmarks: 1.a Execute with keys in the range 1..100, for 1000 operations, printing every 100 operations (print including content). 1.b Execute with keys in the range 1..100, for 1,000,000 operations, printing every 100,000 operations (print including content). 1.c Execute with keys in the range 1..10,000, for 1,000,000 operations, printing every 100,000 operations. 1.d Execute with keys in the range 1..100,000, for 10,000,000 operations, printing every 1,000,000 operations. 2. Re-run 1.c, and 1.d with 10 different seeds 11-20. Include in your document the number of steps in each case and calculate the average number of steps. Your final submission should include a benchmark program that can run all the tests specified above with command-line arguments. This part of the project should be completed by Monday, November 30. It is advisable to come show it to us as soon as it is ready to get some feedback as you move to the second part. Part 2 ------ Design and develop an application program that manages a vehicle service center. The center services different kinds of vehicles, including (regular) cars, hybrids, buses, and motorcycles. All vehicles have the following properties: - Unique id ASSIGNED BY THE USER!!! (range 1..100000) - Model year (range 2001..2020) - Color - Mileage Cars have the following properties: - Engine size (cc) - Gas (premium, plus, regular) - Engine pollution level Hybrids are cars that also have the following properties: - Motor power - Motor overall usage (in hours) - Battery capacity Motorcycles have the following properties: - Engine size (cc) - Front wheel size - Back wheel size Buses have the following properties: - Passenger capacity A vehicle brought in to the center can have multiple tasks (unlimited number) performed on it while it is in for service. Examples for tasks include scheduled maintenance, brakes change, tire rotation, etc. Each task has a name, cost of parts, and cost of labor associated with it. Tasks are assigned to a vehicle when it enters the service center and can be added while it is still in service. Your application program should be able to insert records for vehicles entering the service center, and checkout a vehicle, printing its bill and deleting its information. Each record should store all of a vehicle's relevant information (depending on its type), including the tasks currently being performed on the vehicle. The vehicles should be stored and accessed using the multi-level hash template. Your program should allow the user to view a report of all vehicles currently in service, and to view the status of a single vehicle. Be creative! Think about the types of operations a service center might need and implement a few of them not specified here. Some advice ----------- -Get your data structure working first. Please make sure to have a program file including a main function for the benchmarks in part 1 and make it part of your Makefile (that should also build the program for teh second part of the project). Write your application program only after the data structure is solid! -Compile often. The C++ error messages can be confusing -- tackle them in manageable chunks. -Test as you go. Write small driver programs to help you debug, and keep these programs around to avoid duplicating your own work. -Pay special attention to your destructors. Be sure that deleting a vehicle record frees up ALL associated storage. Run Valgrind to check that. -Design, design, design. This project is complex enough that you will likely not have enough time to start from scratch if you find you've gone down the wrong path three days before submission. Try to get it right the first time! We are here to help -- come and talk with us to bounce around some ideas. ------------------------------- Submission date for both parts of the project is: Friday December 11, 10pm. Submission is accomplished by e-mailing a tar file to amir220@cs.jhu.edu and by presenting your project in a pre-arranged meeting with the Instructor & TA. Submissions will be accepted only up to the deadline. Do not include executable/object files or cores in your tar (include only the files you want to submit, including a detailed design document, your results from Part 1, source code, and a Makefile that builds executables for both part 1 and part 2). The development environment and the place where you have to check your program is *only* on the ugrad1-20 machines. We ask that you demonstrate your programs there during the interactive project grading session.