Spells and Dispells

Instructions

For this project you will be designing and implementing a system, in C++ (98, 11, or 14), to help the local wizard shop catalogue magical spells, items, and customers. Your system should act as a database, and allow the user to load in multiple tables of data, run basic queries on the data, and then store the data off for later use.

Requirements

Report

For the report portion, you must generate documentation, in PDF format, describing your system. The purpose of this is for you to explain not just what your system is doing, and how it is doing it, but why. You will need to justify your design decisions in a concise, informative manner. Justifications such as "I did this because it was easy" are not sufficient, as you should actually explain why a particular data structure or algorithm was more efficient, effective, or optimal. Additionally, commented code, while sometimes helpful in small examples, is not a sufficient explanation in and of itself. Your explanations and justifications are expected to be presented in prose and in paragraph format, i.e. not bulleted lists. Further, part of the evaluation of your report is the apparent amount of thought and effort that went into its creation.

This document should be divided into three main sections

For the Project Description section, in one to two paragraphs you should describe the project in your own words and give a brief overview of the problem. Do not copy and paste this information from this instruction document.

For the Data Structure section, you should describe the data structures you used in your system. What objects or structs did you create to store data? How did you organize and manage them? What types of formal data structures did you make use of (trees, graphs, arrays, hashes, etc)? Be sure to put the majority of the functionality explanation in the System Functionality section. In a few paragraphs, describe in detail how you stored the various data elements in your system, and be sure to provide sufficient justification of your methodology.

For the System Functionality section, you should describe functionality of your system. How is data moved and transformed? How is it read in? How is it output? What are the various major functions you constructed and how do they work? In a few paragraphs, describe in detail how your system works, and be sure to provide sufficient justification of your methodology. You might also consider including diagrams to more easily visualize how all of the pieces fit together.

Implementation

Your program must provide the following functionality and adhere to the following constraints:

• Allow the user to choose the file describing the initial setup of the database
  • Do NOT hardcode the filename into your program
  • The first set of lines in this file will provide a space delimited pair of a file name and a table name that should be used for the data within that file. There will be one pair per line
  • The next line will be an empty line
  • The remaining lines will be basic operations including INSERT, UPDATE, SEARCH, DELETE, DISPLAY and WRITE
• For each table file:
  • The first line will list the table's keys
  • The second line will list the table's scheme
  • All other lines will be | delimited rows of data to be inserted into the table
• While the data may change for different sets of input files, the schemes will always be identical for each table
• Each table should have a primary index implemented as a hash table, and secondary index implemented as a linked list
  • You may either have a generic table class and the database contains a unique instantiation of that class for each table or one unique table class per table
  • A table class must be defined in its own .cpp and header
  • An entry in a table may be defined either as a class or a struct, and may be a private inner class/struct
• For the primary index
  • You must implement your own hash table and hash function
  • You may choose your collision strategy from the strategies we have covered in class
  • You may choose your hashing function from the strategies we have covered in class
  • Each table must have a different hashing function and collision strategy
  • You may not use the map, unordered_map, or any other hash table from any of the C/C++ libraries, STL, or Boost libraries
  • You may not use the hash function or any other hashing function from any of the C/C++ libraries, STL, or Boost libraries
• For the secondary index
  • The secondary index is a linked list of pointers to structs or objects that exist in your primary index
  • No actual entries may be stored in the secondary index, only pointers
• All .cpp files, except your main.cpp, must have associated header files. You may not #include a .cpp file, only header files
• The queries should be implemented as individual functions in the following way:
  • INSERT(string ,string) where the first string is a tuple of values, and second string is the table name
  • INSERT should alert the user and not overwrite the data if there is already an entry with that key value
  • Otherwise INSERT should add the data to the table and report a successful insertion. Be sure to specify the tuple and the table in the reporting.
  • UPDATE(string ,string) where the first string is a tuple of values, and second string is the table name
  • UPDATE should alert the user and not insert the data if there is no entry with that key value
  • Otherwise UPDATE should alter the data that key points to and report a successful update. Be sure to specify the tuple and the table in the reporting.
  • SELECT(string ,string), where the first string is a tuple that can have either a value or * for each component, and second string is the table name
  • SELECT should alert the user if no rows match the query
  • Otherwise SELECT should output all rows that match the query
  • If the key attribute has a *, the secondary index should be used
  • DELETE(string ,string) where the first string is a tuple that can have either a value or * for each component, and second string is the table name
  • DELETE should alert the user if no rows match the query
  • Otherwise DELETE should remove all rows that match the query and report a successful deletion. Be sure to specify the tuple and the table in the reporting.
  • If the key attribute has a *, the secondary index should be used
  • DISPLAY()
  • DISPLAY should output the current state of each table to the user in a tabular format
  • Be sure to include the attribute names for each table
  • WRITE()
  • WRITE should write the data in each of the tables to a separate file in the same format they were read in
  • The first line will list the table's keys
  • The second line will list the table's scheme
  • All other lines will be | delimited rows of data in the table
  • The filename should be the different than the original file name to avoid overwriting
• Your code must be well commented.
• You must provide a short README file which includes your name and explains how to compile and run your program.
• Additionally, you may write a makefile if you want your code to compile with additional flags.

Extra

Your system must include the PROJECT(SELECT(string,string), string) operation. PROJECT should take in the output from a SELECT statement and a list of columns, and only output data for the columns listed in the second string. You may need to modify your SELECT function to return its output, in addition to outputting it to the user.