CMSC-341 Spring 2003

Project 1

Assigned	Monday, January 27, 2003
Due	11:59pm Sunday, February 9, 2003
Clarification	*03 Feb 2003* In the Bag definition section, one required operation is "int ItemCount( const ItemType& ) that returns the number of items of the specified type in the Bag. Returns zero if the item is not in the Bag." The word "type" is a little misleading to some students. This method is used to return the number of ints/strings with a particular value. For example, in a Bag of ints we would invoke this method as `int count = ItemCount ( 7 );` and the method would return the number of 7s in the Bag.

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.

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

Here are your tasks:

Read the brief introduction to the STL at the following URL:
http://www.msoe.edu/eecs/cese/resources/stl/index.htm
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
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
Implement the Bag class as described below.
Implement the functions which are required by Proj1.C (GetCmdLine ( ), ProcessStringCommands( ) and ProcessIntCommands( )) in a separate file named Proj1Aux.C. Their prototypes must be found in Proj1Aux.H. The functionality of Process...Commands is described in the command file section
Use the main function provided in the file:

/afs/umbc.edu/users/d/e/dennis/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.

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-Spring03-proj1_questions.txt. Copy the file

/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj1/341-Spring03-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 a Bag

A Bag is a fixed-size collection of possibly duplicate homogeneous objects. The size of the bag is the maximum number of items the Bag can hold. For example, a Bag of crayons of size 10 can contain up to 10 crayons. There could be 10 red crayons in the bag, or 5 blue crayons or 3 purple and 5 green crayons, or 10 crayons that are each a different color. Because the Bag can contain any kind of object, it must be implemented as a template. The type of object in the Bag is the template parameter. The fixed size of the Bag is specified when the Bag is constructed.

The operations allowed on a Bag are

Default construction of an empty Bag with size 10.
Construction of a Bag that specifies the fixed size.
Construction of a Bag as a copy of another Bag (copy constructor).
Destruction of a Bag (destructor).
Assignment operator (operator =)
bool Add( const ItemType& ) that adds an item to the Bag.
bool Remove ( const ItemType& ) that removes an item from the bag. If the Bag contains more than one of the specified ItemType, only one is removed.
int ItemCount( void ) that returns the total number of items in the Bag.
int ItemCount( const ItemType& ) that returns the number of items of the specified type in the Bag. Returns zero if the item is not in the Bag.
int NumDistinctItems( void ) that returns the number of distinct items in the Bag.
const ItemType& MaxItem( void ) that returns the item which occurs the most times in the Bag. If more than one item occurs most, any of the items may be returned.
An overloaded non-member function operator <<
Note: Your implementation of the Bag class must use the print idiom described in the Weiss text on page 35 (in the Employee class). This means you must write both the public print method of the Bag class and a non-class, non-friend function.

Note: Your implementation of the Bag class may include any private methods you deem necessary, but only the methods listed above may be public.

Note 2: The default constructor, copy constructor, assignment operator and destructor must be written by you even if there is no code. You may not use the compiler's default version of these methods even if the compiler's default version would be sufficient.

The Command Line

Project 1 will be invoked with a command line that consists of three arguments. The first argument specifies the type item to be stored in the bag and will be either "int" (without the quotes) in which case the Bag will contain integers, or "string" (without the quotes) in which case the Bag will contain C++ strings (not C-style NULL terminated char arrays). The second argument is the size of the Bag (number of items it can hold). The third argument will be the name of a file that contains a set of operations that must be performed on Bags 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 Bags. Each line in the file represents one command. Blank lines may appear anywhere in the file and should 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.

Note that there are two routines for processing the command file depending on the type of item 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.

The command file format follows:

ADD <item> -- Adds the item to the Bag. If the Bag is full, an error message is printed.
REMOVE <item> -- Removes the item from the Bag. If the specified item is not in the Bag or the Bag is empty, an error message is printed.
OCCURS <item> -- Prints the number of times the specified item is stored in the Bag
COUNT -- Prints the total number of items in the Bag
MAX -- Prints the item which occurs most frequently in the Bag and the number of times it occurs. If the Bag is empty, an error message is printed.
DISTINCT -- Prints the number of distinct items in the Bag
PRINT -- Prints the contents of the Bag
The following information is required for PRINT
- total number of items in the Bag
- number of distinct items in the Bag
- each item in the Bag and the number of times it occurs

Main Function Definition

The file containing the main function at the following location:


/afs/umbc.edu/users/d/e/dennis/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 are permitted. Reference it with your makefile. Instead of copying Proj1.C to your directory, make your makefile work correctly from the start. This will save you much grief and probably a few points on your project score.

Free Advice

You should consider these issues in order to maximize your grade.

Not only does the Bag contain items placed in it, it also keeps track of information about those items. You should consider how best to associate the items and their information.
In some circumstances (e.g. trying to add an item to a bag that's full), your program is required to print an error message. Good design principles dictates that there is a right way and a wrong way to do this.

Sample Output

Sample output is available for your study at


/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj1/341-Spring03-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:

Bag.H -- the definition of the Bag class
Bag.C -- the implementation of the Bag class
Proj1Aux.H -- the prototypes for auxiliary functions you may write such as GetCommandLine()
Proj1Aux.C -- the implemenation of your auxiliary functions
.H and .C files for any other class(es) you have chosen to implement (if any)
your makefile
341-Spring03-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/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 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-Spring03-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.