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:
- Implement the BigInt class.
- Implement the Rational class.
- Implement the Number class.
- 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.
- 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.
-
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.
-
Answer the questions posed in 341-Fall03-proj1_questions.txt. Copy the
file
/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.
- BigInt(int value = 0) - Constructor with a default initial
value of zero
You are allowed to create another constructor that takes a string (or
char *) as an argument and initializes the BigInt,
e.g. BigInt("-67342").
- ~BigInt() - Destructor
- bool operator==(const BigInt &) const - Equality operator
- BigInt & operator=(const BigInt &) - Assignment operator
- BigInt operator+(const BigInt &) const - Addition operator
This operator adds the values of two BigInts and returns the result,
which is a BigInt as well. You do not need to check whether the result
will be too large to store in a BigInt and no test cases used to grade your
project will yield such a result. Test cases will involve operands that
are both positive and negative, so be sure your addition operator handles
such cases correctly.
- BigInt operator*(const BigInt &) const - Multiplication
operator
This operator multiplies the values of two BigInts and returns the
result, which is a BigInt as well. You do not need to check whether the
result will be too large to store in a BigInt and no test cases used to
grade your project will yield such a result. Test cases will involve
operands that are both positive and negative, so be sure your
multiplication operator handles such cases correctly.
- void print(ostream &) const - Print the value of a BigInt to
an ostream
See page 35 in the Weiss text for an example of how to implement a
print method. You will use the print method inside your
implementation of the operator<< method. If the BigInt is
positive, just print its value. If the BigInt is negative, be sure to
precede the value with a negative sign.
- void read(istream &) - Read the value of a BigInt from an
istream
Calling the read method for a BigInt causes the value of the
object to be set to the value found in the istream passed to the method.
This method should skip characters in the istream until it finds a sign
(+/-) or a digit. It should then read all digits until it finds a
non-digit, and initialize the BigInt to the value just read. You may
assume that values read from files will never overflow a BigInt, and that
whenever a sign occurs it will be followed immediately by one more more
digits.
- int getSign(void) const - Return the sign of a BigInt
Note:This method is optional. If you don't need it, you don't
have to implement it.
- void setSign(const int) - Set the sign of a BigInt
Note:This method is optional. If you don't need it, you don't
have to implement it.
- ostream & operator<<(ostream &, const BigInt &) - Output
operator
This method should simply call the print method as in the code
on page 35 of the Weiss text.
- istream & operator>>(istream &, BigInt &) - Input operator
This method should simply call the read method in a manner
that is analogous to the use of print by operator<<
.
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:
- Constructor - You may want to, and are allowed to, create additional
constructors for rationals. For example, you may want a constructor that
takes two BigInts as arguments, one for the numerator and one for the
denominator.
- Equality operator - Two rationals are equal if their numerators are
equal and their denominators are equal. Therefore, the rationals 4/2 and
10/5 are not equal, despite the fact that 4/2 = 10/5 = 2. This is done so
that you don't have to do things like computing lowest common
denominators.
- Addition operator - When adding A/B to X/Y, the result should be
computed as (AY + XB) / BY.
- Multiplication operator - When multiplying A/B and X/Y, the result
should be computed as AX/BY.
- Print method - You should print the numerator and the denominator on
the same line separated by a "/".
- Read method - The numerator and denominator, which are BigInts, will be
separated by a "/", perhaps with white space between the "/" and the
numbers on either side. Also, either the numerator or the denominator can
be signed.
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:
- ADD n1 n2 -- Add n1 to n2 and print the result.
- MULT n1 n2 -- Multiply n1 and n2 and print the result.
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:
- Files for implementing the BigInt class
- Files for implementing the Rational class
- Files for implementing the Number class
- Auxiliary files which contain the prototypes and defintions of
auxiliary functions such as getCmdLine()
- Your makefile
-
341-Fall03-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-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.