CMSC-341 Fall 2003

Project 1

Assigned 8 Sep 2003
Due 21 Sep 2003


Background

Abstract Data Types (ADTs) are the central focus 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, and compile code from multiple directories. 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

In this project you will implement three classes - BigInt, Rational, and Number - that make it possible to multiply and add numbers that are too large to represent using built-in data types. For example, the largest value that can be represented with an unsigned long integer on linux.gl is 4294967295. Objects of type BigInt can represent integers containing a large, but fixed, number of digits (e.g. hundreds of digits).

Objects of type Rational represent real numbers as the ratio of two BigInts. For example, the real number 2.5 might be represented as the rational number 5/2, or the real number 10.0 might be represented as the rational number 10/1.

Finally, objects of type Number contain a data member that supports the addition and multiplication operators. The actual type of the member is specified via a template parameter, which in this project will be either BigInt or Rational.

The ADTs that you will implement are 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. Implement the BigInt class.
  2. Implement the Rational class.
  3. Implement the Number class.
  4. Use the main function provided in the file:
  5. /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.

  6. Write the set of auxiliary functions as required by Proj1.C -- e.g. getCmdLine( ) -- and put them in the file Proj1_aux.C. Their protoypes belong in Proj1_aux.H.
  7. Copy the makefile from:
  8. /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-Fall03-proj1_questions.txt. Copy the file
  10. /afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj1/341-Fall03-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

BigInt
BigInts store the values of signed integers. Rather than representing these values in binary form, as is done with the built-in type int, BigInts store integers as an array of ints. Each element in the array corresponds to a digit in the BigInt. Clearly, the size of the array limits the number of digits that can be represented in a BigInt. For this project, you will never need to manipulate BigInts that contain more than 200 digits.

You will implement addition and multiplication operators for BigInts. It will be much easier to write the code for these if you store BigInt digits in the array starting with the lowest order digits. That is, rather than representing the value 1024 as [1, 0, 2, 4] you should represent it as [4, 2, 0, 1]. This will greatly simplify your code. Note that these operations must return results with the proper sign. For example, -2 * 4 = -8. You will need a private data member that stores the sign of the value of the BigInt. A simple way to do this is to use an int that takes on the value -1 if the BigInt is negative and 1 if the BigInt is zero or positive.

You must implement the following public methods for BigInt (with the exception of setSign and getSign). You may not create any other pulic methods, unless specifically mentioned in the description below. You can create any private methods or data members you need.

Rational
Rationals store the values of real numbers as the ratio of two BigInts. For example, the number 0.524449 is equal to 4569 / 8712. You must implement all of the methods described above for BigInts for Rationals as well. The prototypes should be the same except you will replace BigInt with Rational. Below are notes on specific points of difference between the BigInt and Rational versions of the methods:
Number
Objects of type Number have a single data member which must be of a type that supports the addition and multiplication operators. The type of the data member should be specified by a template parameter. You must implement all of the methods described above for BigInts for Numbers as well. The prototypes should be the same except you will replace BigInt with Number. Note that each Number method should be a simple call to the same method for the underlying data member.

The Command Line

Project 1 will be invoked with a command line that consists of two arguments. The first argument specifies the type of number that will be manipulated, and should be one of "BigInt" or "Rational". The second argument will be the name of a file that contains a set of operations that must be performed on numbers of the specified 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 numbers. 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.

The command file format follows:


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