The Final Project is to develop a simple database system. The database is to handle multiple records, each composed of several fields. The database will store its information to a file, addition and deletion of records, field modifications, and it will allow users to sort records based on the selected keys, and produce reports (output) according to predefined criteria.

Some definitions: A database is a collection of information, or data, that you can organize, update, sort, search through, and print as needed. A database does not just hold information; you use a database to organize and analyze information so that you understand its significance. A database file consists of one or more records. Each record holds all the information about one subject item. In C++, the class data type provides an efficient way to represent and manipulate records. Each piece of information in a record is called a field. Fields store the data that has been entered or calculated. In C++ parlance, fields are nothing more than the member variables defined for a particular class.

Given the requirements as a rough specification, you are to design the class and implement the database. So you can consider the requirements below as an outcome from a meeting with a client. You are in full control of the choice of data structures (except the main data structure of a Binary Search Tree, more detail below), algorithms, internal file format, and detailed user interface scheme.

You're designing and implementing a database for an address book. Users should be able to browse, search their contacts, by any field (last name, first name, zip code etc.) from the database, and organize their chosen contacts to their liking and print out a report.

Each contact information includes followings:

Unique ID number. ID is a 9 digit number (assume person has an ID generated from another system)

First name

Middle name (or initial)

Last name

Company name

Home phone

Office phone

Email

Mobile number

Street address

City

State

Zip code

Country

List of affiliates (such as family members or associates name). Each affiliate has first name, and last name. They may have one individual mobile phone number and one email. This database will not track any other information about affiliates. The total number of affiliates is unknown.

Requirements:

1. Database overall management Use a text based menu for users to choose available features. Program should have a main menu at the beginning and sub menus depending on the task.

2. You should allow users to read and write data to a text-based database file. The format of the text-based database file is following:

All information is stored in ASCII text format.

Records are divided by a | character

Each field is distinguished by a new line.

3. When reading from a data file, your program must test the input file to ensure that data is of valid format (basic error detection).

4. The database is primarily organized with the ID# as a key. You must use the provided Binary Search Tree (from HW8) for the base data structure. You will have to modify this code to ensure that you have a Binary Search Tree of Nodes, that is sorted by ID. You may have additional Binary Search Trees if that fits into your design. While you can modify the HW8 files, do not use some "other" Binary Search trees that you might find in the book or the internet, since we won't be able to help you if things go wrong (and they will!)

5. Each component of the overall program should be fairly modular. Each menu item, for example, should be a separate function. The menu feature should be handled by a separate function and not by main( ).

6. Program should be fairly fault tolerant of user input (both when the user is entering data, and making menu choices). Provide appropriate user prompts and on-screen directions

7. Split the program into multiple files based on the roughly categorized functionality.

Data Retrieval and Modification

1. Users should be able to search records based on the field information in two modes: exact and contains. For example, search contacts by last name "Smith", search contacts with an email domain name that contains "newyorkuniversity", etc. So in the search sub menu, users have to pick the search mode and field. Of course users should type in the search item.

2. Quite often, searches may generate a relatively big output. Users should be able to search again within the search result (secondary search) or start all over again from scratch (new search).

3. Since the entire data is structures in a Binary Search Tree tree with the ID# key, any search (except using ID#) should traverse the entire tree.

4. Users should be able to delete a record. So, in the delete record sub menu, users should be able to search and pick a delete candidate record. After deletion, the Binary Search Tree should follow all Binary Search Tree properties (with regard to sorting order, tree levels etc).

5. Users should be able to modify fields in a record, with the same condition above.

6. Users should be able to insert new records. There should be no restriction to the number of records in the database. So, in other words, you should not consider a fixed array for the record data structure.

7. Users can modify records, so the user should be able to write back to file (overwrite to current file or to a new file name similar to "save as").

Output Generation

1. Output generation is responsible for the re-organizing the final result to a user's liking by displaying appropriate fields and sorted records. The final output is a report in ASCII-text format.

2. After a series of data retrieval and modification, finally there is a list of contacts to be an output. Users should be able to further organize the contact and convey them to the output by choosing only the fields they want to print in desired order. So users should be able to pick fields to be finally shown in the output. And users should be able to sort the final output contacts by selecting a field as a key.

3. Users should be able to perform a secondary sorting with the second sort key (e.g., sort by company name, and then last name).

4. Output file generation in text file format.

Users should be able to generate a report output in ASCII text format. Note that this output file is different from the database file in ASCII text format.

Keep in mind that an output may not include all fields and records.

Submission Guideline

1. You need to submit following items (all zipped together):

Source code with reasonable comments Makefile that works (and is tested) on the grid.

A final report that includes: Summary of provided functions. This should be matched with the requirements

Design document that shows the overall program structures, and the explanation of key algorithms. A description of user interface scheme is required to explain the menu items at top level and items in sub menus and how to navigate through menus. A detailed instruction and sample skeleton is available from Design Document.Preview the documentView in a new window

Accurate status of the program, what's done, and what's not completely implemented.

The final report should be in MS Word, or PDF format.

Note: You may use the following Binary Search Tree code. You may not use every function associated with this code and you may need to change it to fit this assignment. Any and all changes should be fully documented.

Q & A

Q: What's the input file format?

A: Something like this ID# First name Middle name Last name Company name Home phone Office phone Email Mobile number Street address City State Zip code Country Affiliate name 1; (this can be family members, office affiliates, etc.) Affiliate name 2, own phone number, own email; Affiliate name 3; Affiliate name 4, own phone number, own email; (number of affiliates are unknown) (each affiliate is delimited by ;. In case an affiliate has its own phone number and own email, those are delimited by comma , . ) | <- record divider next record starts here. First name Middle name Last name.... For this final project, we can reasonably assume that every record has every field information. But just in case, for instance someone does not have a mobile number, fill up the field with "NULL" string.

Q: Assignment states that "A database file consists of one or more records." Does it mean that database is not allowed to be empty (zero records)?

A: Well, if there's no record, then it's not a database either. Allowing it as a database or not is a matter of a program design decision. You may think that you can create a database file first (building the structures) and add records one by one. But until it gets the first record, it doesn't serve as a database, except it has record structures. So I assume that there should be at least one record to make a database. You can make your program to take a database file with at least a record as an input parameter. Otherwise, it simply stops running.

Q: The following requirement seems backwards: Records are divided by a | characterEach field is distinguished by a new line. Shouldnt it be: FIELDS are divided by a | characterEach RECORD is distinguished by a new line.

A: No. If you put the entire record in one line, it could be very long and the word-wrap in a window would make the document very hard to read on typical text editors. Technically, there's nothing wrong with your scheme, though. But having a special character at the end of contact list (which is the end of the record) may make the programming a little easier. Q: Should the final report be one document or a series of documents? A: One MS word or pdf document.

Q: Do we need to give our users an ability to search on any field of the contacts? Should we also give the ability to search on everything including affiliates?

A: Yes, search (both exact and contain) function should be equally applied to all fields including affiliates. If your search function finds a target in the list of affiliates, assume that all main contact info is shared except for those people who have their own phone numbers and emails. For example, you're searching for a person with last name "Smith". The main database may not include someone with "Smith" but "Smith" could be found from affiliates of one or multiple records.

Q: Do we have to provide an infinite number of sub-searches? The assignment describes a requirement that we need to allow 1 sub-search. Do we have to have allow an infinite number of them?

A: Sub-searches, either it's the first level or further refined, should be same. Once you get the first search done, the current search result becomes another dataset from which you should be able to perform the first sub-search. Then the result of this routine should be in a same format just like the original search. So given the same format of dataset, you should be able to run the exactly same sub-searches, more like a recursion.

Q: The project says: Users should be able to search records based on the field information in two modes: exact and contains. For example, search contacts by last name "Smith", search contacts with an email domain name that contains "cudenver", etc. So in the search sub menu, users have to pick a search mode and field, as well as the search key. What a contact company is "first level technology" and the user typed "first technology" . Does "first level technology" contain "first technology" or not? Or, to be considered contained it has to be ether "first level" or "level technology" or "first level technology"?

A: I consider "first level technology" does not contain "first technology" since we're operating a string matching, not word by word containment relations. Q: When a user modifies a record, can s/he change the number of affiliates on a particular contact? or only existing fields can be modified? Can the user delete a particular affiliate from the contact record? A: Yes to both questions. Normally it's a super-user's job but for this project we consider all users have the privileges. Q: what's the format of the report that to be displayed on the screen? A: Table format with the column/row alignment is fine.

Q: When a user deletes records what happens to the affiliates?

A: Delete a record means delete an entire contact information including all affiliates.