OVERVIEW
- For this project, you will calculate the different statistics about the items to be delivered through courier company. First you will start with raw data and use combine knowledge of Hash Table and Tree structure to arrange large chunk of data in Hash Table array. Each array element holds the pointer to the root element of the Tree structure.
OBJECTIVES
- Create and use Hash tables.
- Create and use Tree Data Structures.
- Use the search and traversal mechanism in Tree data structure.
- Use common algorithms to enhance software development.
- Use best practices to effectively produce quality software.
EVALUATION
- The evaluation of this assignment will be done as detailed in the Marking lecture in Week 2 of the C course.
PREPARATION
- Understand how to implement hash tables.
- Understand how to implement tree structure.
BACKGROUND
Consider you work for a large courier company, and they wanted to develop inventory management system. Every item that arrived to the courier company for distribution are entered into their system and it generates huge text file. We will review what data are stored and how data are stored in text files. You must read items data from file and offer user to display various output based on their search.
REQUIREMENTS
- Your data should contain many things but for simplicity you will have destination, weight and valuation ($$) for the parcels to be dispatched. So, each parcel can have three pieces of information linked to it, destination, weight, valuation. Destination is name of the country where parcel will be dispatched.
- As a starting point for this application, you will load large amount of data in application memory to perform further action.
- You will read the couriers.txt file and load the three pieces of information from the file.
- txt would have destination, weight and valuation. The format of data stored in file would be destination, weight, value. Destination would be country name max 20 character and weight is the gross weight of parcel in numbers and valuation in float.
Gross weight is typically in the range of 100 gms to 50000 gms. All weights are in grams. And valuation should be in the range of $10 to $2000.
- You can create a file (couriers.txt) with destination, weight, value min 2000 records are OK.
- You can assume that for given destination there shouldn’t be other parcels with same weight. In real world those parcels can be combined to make one larger parcel, but we will not do that. e. Canada, 500 and Japan, 500 is correct but there is no duplicate weight for same destination.
- Allocate memory for destination dynamically.
- After reading data from files, you will load them in HashTable.
- You will create a Hash table of size 127. This will make sure that good distributions will happened across buckets. Few buckets will be empty, for now that is fine.
- Each index of the HashTable will hold the root node of the Tree structure.
- You will use the Country name as a key to generate the Hash Value to store the data to specific Hash Index. I have also provided the list of the Country, please use countries from them only, these countries name generate the unique Hash Value so that you can avoid more than one country data to be part of same bucket. Please select at least 50 or more countries.
- You must use the “djb2 function” to generate the unique Hash Value of each record using the associated country name and then store those data into Balance AVL tree at specific bucket index.
- Each node in AVL tree represents a parcel.
- Each node in the AVL tree is placed using parcel’s weight.
- It’s OK to use more than 2000 names but don’t have more than 5000.
- After loading the data into application’s memory, you will present the following user menu to the user.
- Please see the below user menu:
- Enter country name and display all the parcels details: when user enters 1, application allow user to enter County name. Then display each parcel’s details.
- Enter country and weight pair: This menu offers user to display all the parcel for given country whose weight is higher/lower than weight entered.
- Display the total parcel load and valuation for the country: When user enters country name, display the cumulative parcel load and total valuation of all the parcels. o 4. Enter the country name and display cheapest and most expensive parcel’s details. o 5. Enter the country name and display lightest and heaviest parcel for the country.
- Exit the application.
- Make the hash table 127 buckets in size.
- Design your code so that you do not have to duplicate code unnecessarily.
This is very important.
- Clean up all allocated memory before exiting.
OTHER REQUIREMENTS
- The field containing the names must be dynamically allocated to an appropriate size.
- Do not get any other user input except as indicated in these requirements.
- Do not display output except as indicated in these requirements.
- Do not clear the screen at any time in this program.
- You must do error checking where necessary.
- If you detect an error, you should display an appropriate error message and take appropriate action.
- You can assume that all statements above that have the phrase “will be” in them will be true when testing is done.
- It must not use global variables.
- It must not use goto.
- Be aware that you still cannot use C++ strings in this assignment because malloc() does not support them.
- You can assume that the country names will not be longer than 20 characters in length.
- If you are working in group or solo, you must be able to explain the code. Also, code should work on your machine and your partner’s machine as well. This may require demoing your code in group.
- The SET Coding Standards must be adhered to.
GIT REQUIREMENTS
- For the group project, you can create your own repository and work in group with other members. So that both members should have access to repository and you can manage issues locally.
- It is expected that both members would have a reasonable number of commits with meaningfully descriptive commit comments.
CHECKLIST REQUIREMENTS
- Create a requirements checklist. This should contain the specific requirements from this assignment as well as any relevant requirements that have been covered in lecture or that are found in the SET Coding Standards or SET Submission Standards. Do it in whatever form you wish. Hand in your completed checklist in PDF form as checklist.pdf. Not having this checklist will result in a cap of 80 on your mark.
FILE NAMING REQUIREMENTS
- You must call your source file project.cpp.
- You must call your checklist checklist.pdf.
- Sample data file name should be couries.txt file
SUBMISSION REQUIREMENTS
- Submit the files mentioned in the File Naming Requirements. Do not hand in any other files. Yes, please submit the sample data that you have used for this project.
- Submit your files to the Project Submission Folder. Only one member needs to submit the file.
- Once you have submitted your file, make sure that you’ve received the eConestoga email confirming your submission. Do not submit that e-mail (simply keep it for your own records until you get your mark).
