Background

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.

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.

Description

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, not just integers. For example, you could associate the integer value 1 with the key "one", or in a different alist you could associate the string value "two" with the 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. In general, no other classes from the STL can be used in any 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:

1. Read the brief introduction to the STL at the following URL:

   http://www.msoe.edu/eecs/cese/resources/stl/index.htm

2. Read and understand the description of the STL version of the vector ADT at the following URL:

   http://www.msoe.edu/eecs/cese/resources/stl/vector.htm

3. Read and understand the description of the ANSI/ISO C++ standard library version of the string ADT at the following URL:

   http://www.msoe.edu/eecs/cese/resources/stl/string.htm

4. 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.

5. Implement the AList class as a C++ template class. Your class must use a vector of AListElements to store the current contents of the alist.
6. Use the main function provided in the file:

/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj1/Proj1.C

Use Proj1.C without making any changes to it. Note: There is no need to copy Proj1.C to your own directory. Your makefile must access the file from the directory in which it is provided. Do not submit Proj1.C.

7. Write the set of auxiliary functions as required by Proj1.C -- getCmdLine( ), processIntStringCommands( ), etc. and put them in the file Proj1_aux.C. Their protoypes belong in Proj1_aux.H.

8. Copy the makefile from

   /afs/umbc.edu/users/o/a/oates/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.

9. Answer the questions posed in 341-Fall02-proj1_questions.txt. Copy the file

/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj1/341-Fall02-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

AListElement

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 copy all of the AListElements after the element to be removed down one position, which can be expensive. 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 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, remembering to set the deleted flag to false).

The operations allowed on an AListElement are:

• Default construction of an empty AListElement.
• Construction of an AListElement that specifies values for the key and value members.
• Construction of an AListElement as a copy of another AListElement (copy constructor).
• Destruction of an AListElement (destructor).
• Assignment operator (operator =)
• Accessors for the key, value, and deleted members and a mutator for the deleted member.
• An overloaded non-member function operator <<

This operator outputs the key and value of the element.
Note: Your implementation must use the print idiom described in the Weiss text on page 35 (in the Employee class). This means you must write both the print method of the AListElement class and a non-class, non-friend function.

AList:

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:

• 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(Key key, 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(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(Key key) that removes, lazily, 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+(AList<Key, Value> rhs) 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-(AList<Key, Value> rhs) 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*(AList<Key, Value> rhs) 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 <<

This operator outputs all of the key/value pairs stored in the AList.
Note: Your implementation must use the print idiom described in the Weiss text on page 35 (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 Command Line

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

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 these two routines take 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. 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 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 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 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 of union of the key/value pairs in 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 whatever was 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 whatever was 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 was 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 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/o/a/oates/pub/CMSC341/Proj1/Proj1.C
  

  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

  Sample output is available for your study at

  
  /afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj1/341-Fall02-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
  • Auxiliary files which contain the prototypes and defintions of auxiliary functions such as  getCmdLine( )
  • your makefile
  • 341-Fall02-proj1_questions.txt - containing your answers to the questions.
  Please do not submit any of the files provided to you such as Proj1.C.

  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/o/a/oates/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 and ii_files), but leaves the
  executable in place.

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

  Example:  submitrun cs341Proj1 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-Fall02-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 midnight of the due date will not be accepted. Do not submit any files after that time.
   

  ---