Assigned | Wednesday, Sept 6, 2006 |
Due | 11:59pm on Tuesday, Sept 19, 2006 |
Updates |
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.
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
Here are your tasks:
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.
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.
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.
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:
You must provide an overloaded non-member function
operator<<
that outputs the key and value of the element.
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.
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:
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.
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.
Submit the files using the procedure given to you for your section of
the course.
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
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
Additionally, there are two programs for use only by CMSC-341 students
(not part of the UCS submit program). They are in the directory
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 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).
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.
to your own directory and modify it as needed. It can be used
without modification if you follow the file names in the makefile.
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.
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 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 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 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.
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.
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.
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
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:
Please do not submit any of the files provided to you such as Proj1.cpp.
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.
submittals. Make sure they work. Do this before the due date.
submitls. It lists the names of the files you have submitted.
/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.
executable in place.
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.