UMBC CS 202, Spring 00

UMBC CMSC 202 Spring '00

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: 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: submit cs202 proj2 Makefile More complete documentation for submit and related commands can be found here.

Last modified: 21 February 2000