You will be provided with a large file containing thousands of records representing a warehouse’s inventory of current stock. The records are not currently in any particular order. Each record is identified by a unique key comprising of the category (table, chair, computer, etc) and a sequence number, eg: Computer:14. Each record contains both the key and information associated with the item (type, price, etc — see section 2.1 for details). Your task is to write a program that can load the records into memory and allow users to look up and display records via the item key (since the user knows the record key and wants to find out the associated information).
Since this is a unit on data structures, you will be required to implement two search methods based on two data structures. Initially, you are to load the records into an array, and the user may then request to search the array using a linear O(N) search. The user must also be able to build a binary search tree from the array and subsequently choose to search using the O(log N) find of a binary search tree. Finally, the user must be able to store the data to a file in key-sorted order.
When the program starts up, it should show the following main menu choices:
The system should loop, requesting the user enter in their choice at which point the system executes the desired option (sometimes involving further user input) and loops back to re- display the main menu. If the user chooses to Quit the program should exit. Detailed specifications for the behaviour of each of the above options follows.
LOAD RECORDS INTO ARRAY. On choosing Option 1, the user must be asked to enter in the path to the data ?le containing the records. Two example data files will be provided to you, a smaller one containing 1,000 records and a larger one containing a million records. However, although these files do not contain errors your code must still handle the possibility that the data gets corrupted and so must check for errors in formatting (see Input Validation below). Data ?les are in CSV format and each record is formatted as follows:
DO NOT SORT THE ARRAY YET. It is important that you leave it in unsorted order for the binary search tree build (option 2). If you sort it, the tree will be degenerate and its search performance will be awful.
BUILD BINARY SEARCH TREE FROM ARRAY On selecting this option, the program must build a binary search tree of the data by inserting the items from the array one at a time into a new binary search tree.
SEARCH ARRAY (LINEAR SEARCH). On selecting this option, the program must ask the user for a key (CategoryName:ID) to search for. The program must then perform a linear search through the array looking for the record containing that key. If found, the Warehouse record should be displayed to the user; if not found an appropriate error message should be displayed to the user. In both cases, the time taken to perform the search (in milliseconds) must be displayed.
Ensure the record is displayed in a neat format with each field name indicated. Weight must have ‘kg’ appended, and price have ‘$’ prefixed. Display each field on its own line, ie:
Ensure the values (XXXX above) line up by padding spaces after the field names. Alternatively, you can use string formatting to do this for you (eg: to print the a string in a field 10 characters wide, use sPaddedStr = String.format(“%25s”, sStr); - extra chars will be spaces - see the JavaDocs on String.format for more information). Search must be case-SENSITIVE. Validation: The array must already be loaded.
SEARCH TREE. On selecting this option, the program must ask the user for a key (CategoryName:|D) to search for. The program must then perform a search through the tree looking for the record containing that key. If found, the Warehouse record should be displayed to the user; if not found an appropriate error message should be displayed to the user. In both cases, the time taken to perform the search (in milliseconds) must be displayed.
Do not forget to display the time taken to do the search. You should find that the search of the tree is much faster than the linear search of the array (especially with the million-item dataset). Validation: The tree must already be built
SAVE DATA TO FILE. When selecting this option, the user is asked for the name of the file to save the data. This must save data to a file in comma-separated format and in key-sorted ascending order. You have two options on how to do this:
Validation: The data must already be loaded
REPORT. You are also required to submit a small ‘report’ (this may be submitted electronically). You must also provide a printed and signed assignment cover sheet (see unit pages for the cover sheet). The report is to have the following parts to it: