CMSC-341 Fall 2006

Project 1

Assigned	Wednesday, Sept 6, 2006
Due	11:59pm on Tuesday, Sept 19, 2006
Updates

Background

Abstract Data Types (ADTs) are a central idea of this course and of object-oriented programming in general. Recall that an ADT has two parts: (1) a description of the elements that make up the type, and (2) a description of the operations allowed on instances of the type. The ADT idea is implemented in C++ as a class.

The ADT is one of the most powerful and important ideas in computer science. This project will give you some exercise in using ADTs.

Another important OOP idea, parametric polymorphism, is implemented in C++ by templates. This project will give you some practice with C++ templates in preparation for future projects.

You will be given a makefile, include headers from multiple directories, compile code from multiple directories, and use a set of class libraries. These are commonly used techniques in industry, so they're worth learning for future reference. You will be responsible for creating your own makefiles for all other projects.

This project also requires the use exceptions. You will implement, throw, and catch exceptions as appropriate.

Note that no STL class (other than vector and string) may be used in this project.

Description

In this project you will implement a data structure called an association list, or alist. Alists are used to store unordered collections of values. A unique key is associated with each value in an AList and the key must be used to access the value. The term AList is borrowed from the Lisp language in which ALists are implemented using lists as the underlying data structure. In this project, you will use vectors as the underlying data structure.

One way to understand an AList is to compare it with a simple array. Arrays are used to store values, and the values are accessed by specifying an integer that is the location of the desired value. The array index can be thought of as a key. In contrast, there is no notion of location with ALists, and keys can be any class type, not necessarily integers.

For example, you could associate the integer value 1 with the string key "one", or in a different AList you could associate the string value "two" with the integer key 2. In the latter case, the fact that the key is 2 does not mean that the value "two" is stored at location 2. It just means that there's a value (i.e. the string "two") in the AList that was stored with the key 2 and that this key must be used to retrieve the value.

As part of this project you will use the vector template class in the Standard Template Library (STL) and the ANSI/ISO C++ standard library version of the string class. The STL is a collection of commonly used data structures and algorithms. You may freely use the vector and string classes in any project in this course. No other classes from the STL can be used in this project.

The ADT that you will implement is described fully in the "ADT" section below. Use the description there to design your classes. Please remember that you must provide good documentation as described in the "Project Organization" handout.

Here are your tasks:

Implement the AListElement class as a C++ template class. Instances of this class contain information about a single key/value pair stored in an AList.
Implement the AList class as a C++ template class. Your class must use a vector of AListElement objects to store the current contents of the AList.
Use the main function provided in the file: /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj1/Proj1.cpp
Use Proj1.cpp without making any changes to it. Note: There is no need to copy Proj1.cpp to your own directory. Your makefile must access the file from the directory in which it is provided. Do not submit Proj1.cpp.
Write the set of auxiliary functions as required by Proj1.cpp -- GetCmdLine( ), ProcessIntStringCommands( ), etc. and implement them in the file Proj1_aux.cpp. Their protoypes belong in Proj1_aux.h.
Note that there are two routines for processing the command file depending on the types of the keys and values specified on the command line. These two routines should be very similar. It is probably a good idea to write, test, and debug one of them completely before starting on the other.
Also note that the first parameter for the Process...( )routines is an array of ALists. The main routine declares two arrays, one containing ALists with int keys and string values, and another containing string keys and int values. Depending on the command line arguments to the program, one of these arrays will be passed to a command processing routine. Commands provide an index (or indices) into this array to specify the AList(s) affected by the command.
Copy the makefile from /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj1/Makefile
to your own directory and modify it as needed. It can be used without modification if you follow the file names in the makefile.
Answer the questions posed in 341-Fall06-proj1_questions.txt. Copy the file /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj1/341-Fall06-p1_questions.txt
to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it's 10% of this project's grade.

Definition of the ADT

The AList Class

An AList is simply a vector of AList elements. The tricky thing about defining the AList is that the types of the keys and values must be template parameters, and these parameters must be used when declaring the vector of AListElements. That is, the template parameters used when declaring an AList must be used when declaring the corresponding vector of AListElements inside the AList class.

Note that a couple of the methods described below throw exceptions. You must write the exception classes, throw exceptions when appropriate, and catch exceptions that might be thrown to ensure that your program does not abort.

The operations allowed on an AList are listed below. "Key" and "Value" are the template parameters representing the types of the keys and values, repectively.

Default construction of an empty AList.
Construction of an AList as a copy of another AList (copy constructor).
Destruction of an AList (destructor).
Assignment operator (operator =)
void Insert(const Key& key, const Value& value) that inserts the given value with the given key into the AList. If the key already exists in the AList then this routine must throw an exception of type DuplicateKey.
bool Find(const Key& key, Value & value) that looks for the specified key in the AList. If the key is found the method returns true and retrieves the value via the reference parameter. If the key is not found the method returns false.
bool Remove(const Key& key) that lazily removes the element with the specified key in the AList. If the AList contains the key the method returns true, otherwise it returns false.
AList<Key, Value> operator+(const AList<Key, Value>& rhs) const that returns a new AList containing the union of the key/value pairs in the AList for which the method is called and the AList that is the argument to the method. This is the union operator. Recall that all keys in an AList must be unique. If both operand ALists contain values with the same key, then there are two special cases. If the values are the same, put only one copy in the result AList. If the values are different, throw an exception of type MismatchedKeys.
AList<Key, Value> operator-(const AList<Key, Value>& rhs) const that returns a new AList containing all of the key/value pairs that are in the AList for which the method is called but that are not in the AList that is the argument to the method. This is the difference operator. If both ALists contain any given key for which the values differ, throw an exception of type MismatchedKeys.
AList<Key, Value> operator*(const AList<Key, Value>& rhs) const that returns a new AList containing all of the key/value pairs that are in both the AList for which the method is called and the AList that is the argument to the method. This is the intersection operator. If both ALists contain any given key for which the values differ, throw an exception of type MismatchedKeys.
An overloaded non-member function operator<<

Note

Employee

Print

The AListElement Class

An AList is a vector of AListElements. Each AListElement has a key, a value that is associated with the key, and an indicator of whether the element has been deleted. The type of the key and value must be template parameters for the class so that, for example, you can create an AList<int, string> whose elements have an int key and a string value, or an AList<string, int> whose elements have a string key and an int value, or an AList<int, StudentRecord> whose elements have an integer key and StudentRecord "values".

The purpose of the deleted member requires a little explanation. We will use a technique known as lazy deletion when removing elements from an AList. That is, rather than actually removing the element, we will simply mark it as deleted. There are two reasons for using lazy deletion in this project. First, because vectors are used to store AListElements, without lazy deletion it would be necessary to use vector methods which would copy all of the AListElements after the element to be removed down one position, which can be inefficient. Second, to remove elements from a vector you need to understand iterators, which is something we cover later in the course.

With lazy deletion, removing a key/value pair from an AList simply requires finding the AListElement with the specified key and setting its deleted flag to true. It is important to consider the value of the deleted flag when searching for a value given its key (i.e. you want to be sure to skip elements that have been deleted) and when inserting new key/value pairs (i.e. you want to re-use deleted elements).

The design and implemenation of the AListElement class is left to you, but you should follow this guideline:
The AListElement class should be implemented with a minimal interface. Only those methods necessary to support the AList class should be provided. In particular, use the methods provided by the compiler if they are sufficient and do not provide unncessary accessors and mutators.

You must provide an overloaded non-member function operator<< that outputs the key and value of the element.
Note: Your implementation of this operator must use the print idiom described in the Weiss text on page 33 (in the Employee class). This means you must write both the Print method of the AListElement class and a non-class, non-friend function.

The Exception Classes

The design and implemenation of the exception classes is up to you. The classes should be as simple or as complex as necessary to allow the the command processing routines to output the required error messages.

The Command Line

Project 1 will be invoked with a command line that consists of two arguments. The first argument specifies the types of the keys and values and will be either "int-string" (without the quotes), in which case the keys are ints and the values are strings, or "string-int" (without the quotes), in which case the keys are strings and the values are ints. The second argument will be the name of a file that contains a set of operations that must be performed on ALists of the appropriate type. The format of this file is described in the command file section below.

Note that you must check command line arguments to ensure that they are valid, e.g. that the command file can be opened, and print an appropriate message if an error is found.

The Command File

Commands in the file specify operations to be performed on ALists. Each line in the file represents one command. Blank lines may appear anywhere in the file and should be ignored. Lines whose first character is '#' are comments and should also be ignored. Otherwise, you can assume that any line containing a command is syntactically well-formed. We make this assumption so you don't have to spend lots of time making the command file parser bullet proof.

All commands and their parameters must be echoed as part of your program output.

Recall that the command processing routines deal with an array of ALists which is passed to each routine. The commands described below all have as their first argument a number that is the index in this array of the AList on which the command is to be performed. You can assume that the array index is valid.

The command file format follows:

INSERT <AList-array-index> <key> <value> -- Insert the given value with the given key into the AList whose array index is specified. If the key already exists in the AList print an appropriate error message.
FIND <AList-array-index> <key> -- Retrieve and print the value associated with the given key in the AList whose array index is specified. If the key does not exist in the AList, print an appropriate error message.
REMOVE <AList-array-index> <key> -- Remove the value associated with the given key in the AList whose array index is specified. If the key does not exist in the AList, print an appropriate error message.
UNION <result index> <first operand index> <second operand index> -- Create an AList that contains the union of the key/value pairs of the ALists specified by the two array operand indices. Put the resulting AList in the location specified by the "result index", overwriting any AList that might already be there. Recall that all keys in an AList must be unique. If both operand ALists contain values with the same key, then there are two special cases. If the values are the same, put only one copy in the result AList. If the values are different, print an error message and do not modify the AList in the "result index".
INTERSECTION <result index> <first operand index> <second operand index> -- Create an AList that contains only those key/value pairs that occur in both the AList at the first operand index and the second operand index. Put the resulting AList in the location specified by the "result index", overwriting any AList that might already be there. If both operand ALists contain the same key but the values differ, print an error message and do not modify the AList in the "result index".
DIFFERENCE <result index> <first operand index> <second operand index> -- Create an AList that contains only those key/value pairs that occur in the AList at the first operand index but not the AList at the second operand index. Put the resulting AList in the location specified by the "result index", overwriting whatever AList might already be there. Again, if the operand ALists both contain the same key but the values differ, print an error message and do not modify the AList in the "result index".
PRINT <AList-array-index> -- Print all of the key/value pairs stored in the AList whose array index is specified.

Main Function Definition

The file containing the main function at the following location: /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj1/Proj1.cpp

Remember, there is no need for you to copy this file to your own directory. Use the main function as is; no changes, please. Reference it with your makefile.

Sample Output

A small sample command file and sample output are available for your study at /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj1/341-Fall06-p1-sample_output.txt

Note that this output was NOT created by executing any program, but generated artificially by hand. Note also that it is required that every command that is read from the command file is echoed as part of the output.

Files To Be Submitted

You should submit only the files you have written, a makefile, and the file containing your answers to the questions. The files to be submitted are:

Files for implementing the AListElement class
Files for implementing the AList class

You may choose to use both a .h and .cpp file for AList and AListELement, or to place both the defintiion and implementation for these templates in the .h file. The makefile assumes that the implementation is in the .h file and that there are no corresponding .cpp files.

Files for implementing the exception classes
Auxiliary files which contain the prototypes and defintions of auxiliary functions such as GetCmdLine( )
Your makefile
341-Fall06-proj1_questions.txt - containing your answers to the questions.

Please do not submit any of the files provided to you such as Proj1.cpp.

Submit the files using the procedure given to you for your section of the course.
If your makefile is set up correctly, you should be able to excute the command make submit.

Submit Tools

There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful
compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your
submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/. One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to
make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example: submitmake cs341 Proj1

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o files), but leaves the
executable in place.

submitrun <class> <project> [command-line args]

Example: submitrun cs341 Proj1 checkers checkfile.dat

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Grading and Academic Integrity

Your project will be tested using a variety of command lines, some of which will be invalid.
Your project will also be tested using a variety of command files which will test various conditions which your code should handle.

Project grading is described in the Project Policy handout.

Your answers to 341-Fall06-proj1_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after 11:59pm of the due date will not be accepted. Do not submit any files after that time.