Project 2: Sets in C++
Note: There was a mistake in the >= operator definition that
several students caught. It now says that for A >= B, all elements of B
must be contained in A.
Due Date:
Project 2 is due at midnight Sunday, March 5, 2000.
Note that this means before 23:59:59 on Sunday evening.
Objectives
The objectives of project 2 are:
- Gain experience writing classes in C++
- Practice operator overloading
- Learn to separate the class' interface
from its definition
- Gain more familiarity with the SGI C++ compiler at UMBC.
Background
A set is an unordered, homogeneous collection of unique elements.
Sets are very important to computer science as well as mathematics and have
applications all throughout these fields. For project 2 you will be
implementing a Set data type as a class in C++.
The definition of set that we have implies several things:
- A set is a collection of elements. This means that a
set may hold an arbitrarily high number of elements.
The number of elements in a set is called the arity of
the set.
- The elements of a set are homogeneous. This means
that the elements of the set are all of the same type.
- The elements of a set are unique. This means that each
element may appear at most once in the set. If an element
is present in the set, it is said to be a member of the
set.
- The elements of a set are unordered. This means that
in your implementation you do not need to worry about
maintaining a sorted list of elements.
Tasks
You should write a Set class that handles sets of
ints. You must provide an implementation for
the following methods:
Set() (Default constructor)
- This should create a new Set and initialize it to the the empty set. That is, a newly created Set should return true when newSet.isEmpty() is called.
operator ||() (Set union)
- The union operator for sets (||) should take two sets, A and B, and return a new set that contains all of the elements of both A and B.
operator &&() (Set intersection)
- The intersection operator (&&) should take two sets, A and B, and return a new Set that contains all of the elements that were in BOTH A and B.
operator -() (Set difference)
- The set difference operator (-) should take two sets, A and B, and return a new Set that contains all of the elements that are in A but are NOT in B.
isMember() (Set membership test)
- A.isMember(element) takes a single element and returns true is element is in A and false otherwise.
isEmpty() (Test for the empty set)
- A.isEmpty() should return true if A has no elements and false otherwise.
arity() (Set arity)
- A.arity() should return the number of elements currently in the Set.
add() (add an element to a Set)
- A.add(element) should make element a member of A. If element is already a member of A, add() should print a warning to standard error (cerr) and not insert element.
remove() (remove an element from a Set)
- A.remove(element) should remove element from A. If element is not a member of A, remove() should print a suitable warning message to standard error (cerr).
operator <() (Proper subset)
- A is a proper subset of B (A < B) if and only if all of the elements of
A are contained in B and A and B are not equal.
operator <=() (Subset)
- A is a subset of B (A <= B) if and only if all of the elements of
A are contained in B. A and B may be equal.
operator >() (Proper superset)
- A is a proper superset of B (A > B) if and only if all of the elements of
B are contained in A and A and B are not equal.
operator >=() (Superset)
- A is a superset of B (A >= B) if and only if all of the elements of
B are contained in A. A and B may be equal.
operator ==() (Set equality)
- A is equal to B if and only if every element in A is also in B and every element in B is also in A.
operator =() (Set assignment)
- A = B means that A should be a copy of B. Any linked or dynamically
allocated data structures should be copied piece by piece. A more detailed
discussion of why this operator was added at the last minute can be found
here.
print() (Print a Set)
- The elements of A should be written to standard out (cout) as a comma separated list surrounded by braces. For example, the Set containing 1 and 3 would print as: {1, 3} or {3, 1}. Remember: The elements of a Set are unordered, so the order doesn't matter when printing.
Your class should have a public interface declared in Set.H that
matches the following:
<![CDATA[
class Set {
public:
Set();
Set operator ||(Set &);
Set operator &&(Set &);
Set operator -(Set &);
int isMember(int);
int isEmpty();
int arity();
void add(int);
void remove(int);
int operator <(Set &);
int operator <=(Set &);
int operator >(Set &);
int operator >=(Set &);
int operator ==(Set &);
Set operator =(const Set &);
void print();
private:
...
};
]]>
Your program must implement all of the methods listed above
without changing their signatures. This is the public
interface of class Set and other developers are
counting on the fact that has the interface that you see above.
Your implementations of the above methods must satisfy the
requirements listed.
Note that the private section has been intentionally left
blank. You make the choices on how the implementation of this
class works. You may include any members you like as long as your
implementation satisfies the requirements listed and doesn't break any
rules regarding academic dishonesty, etc. Note that you may not
change or add to the public interface above, but
you may add other methods as long as they are private
methods of the class.
Coding Standards
For this project you must follow the class
coding standards.
Using Code You Didn't Write
Claiming authorship of code that you didn't write is plagiarism and will
be dealt with as academic dishonesty. You should not use code that you
didn't write; it defeats the learning experience of the project. If you do
use outside code on your project, you must site the source. If a
significant portion of the project comes from an outside source, your grade
may be reduced.
Testing Your Program
Remember, your program must compile and run using the CC
compiler on the IRIX machines (umbc8/9). If your program does not compile
or does not generate the correct output, you will not receive full credit
for this project.
You should make sure that you have a makefile named either makefile
or Makefile and that when you type make your
program compiles to an executable called proj2. Failure to
follow these simple directions will result in a reduced grade.
The following sample main will help you test your
program. A sample Makefile has also been provided.
What to Turn In
You should submit your Makefile, proj2.C and any
files needed to build the Set class.
The contents of proj2.C will not be graded.
This is a placeholder for the "real" test routines that the graders will use.
The graders' proj2.C will expect the public interface defined
above and will expect to find it in Set.H.
Submitting Your Project
When you have finished and tested your project you can submit it electronically
using submit. The project name for this assignment is
proj2. As an example, to submit your Makefile, you
would type:
<![CDATA[
submit cs202 proj2 Makefile
]]>
More complete documentation for submit and related commands
can be found here.
Last modified: 21 February 2000