UMBC CMSC202, Computer Science II, Fall 1998, Sections 0101, 0102, 0103, 0104

Project 2: Sets of Strings

Due: Monday October 12, 1998

Objective

The objectives of this project are 1) to practice designing a C++ class, 2) to have more practice with the new and delete operators in C++.

Background

For this project, you will design and implement a class for sets of strings. The client for this class will use it in the implementation of a web browser. Think of these sets as sets of URLs. The client has to write code that keeps track of many sets of URLs. For example, the web browser must keep track of the set of URLs on a particular web page and the set of URLs that the user has visited in the past 10 days. Several operations might be performed on these sets as well. For example, the set of URLs on a page that has been visited must be colored differently from those that have not been visited. So, it would be nice if the class supported the intersection of two sets of URLs.

The instructions for this project are deliberately vague. This is to give you as much freedom as possible in the design the class. The details about the data members and member functions are all up to you. We won't even tell you what to name them. The basic constraints are that there should not be limitations placed upon the length of the strings or the number of elements in a set. The data structure that you use to maintain a set should not store duplicates. Other than those restrictions, you are free to design and implement the class as you wish. The minimal functionality of the class is described below. Finally, your assignment for this project includes providing sufficient documentation for your class so the client can use your class properly. As usual, your grade in the project also depends on demonstrating that you have thoroughly tested your implementation of the class.

Assignment

Your class should allow the client to do the following with sets of strings.

create and delete sets: include a good number of constructors, including a copy constructor. Overload the assignment operator. The destructor should deallocate memory properly.
append a new string: there should be a way for the client to add a string to an existing set. This should be reasonably efficient (i.e., don't just use the union operation).
membership test: allow the client to test if a string is a member of an existing set.
subset test: check if a set A is a proper subset of a set B.
equality test: check if two sets have the same elements.
union: create a new set that is the union of two existing sets.
intersection: create a new set that is the intersection of two existing sets.
difference: create a new set is the difference between two existing sets. Note that the set A - B consists of all strings in A that are not in B.
iteration: the client should have some way to access individual strings in an existing set. For example, the client should be able to print out each string in a set. Your class does not provide the printing function, but the client should be able to do this. It would be useful if the size of the set is readily available to the client.

For the set union, intersection and difference operations, your implementation should not modify or delete the original sets. When you are done with your design, write up the documentation for this class. You must do so in the style of a UNIX man page. The documentation should include sections for name, synopsis, description and caveats.

Implementation Issues

Most of the implementation decisions are up to you. It is suggested that you use dynamically allocated arrays of pointers to char to represent a set. However, you may choose any reasonable alternative (e.g., singly-linked lists). As stated above, you may not place a bound on the number of elements in a set or the number of characters in a string. You are not allowed to import large portions of code from other than the class notes. Your design should follow the object-oriented philosophy.

Turning in your program

Submit all the files needed to compile and run your program. You should include test programs that demonstrate the use of your class as well as test programs that show that you have tested your implementation for errors. Your submission should also include the following two files:

"ReadMe": This file should contain instructions to the grader describing how to compile and test your programs.
"Docs": This file should contain the "man page" for your class as described above.

Extra Credit

For 10% extra credit, add to your class the ability to complement a set. Note that the set of all strings is an infinite set, so the complement of a set might be infinite. You can "store" the complement of a finite set (called a cofinite set) by storing the finite set and "remembering" in the object that you really want the complement. Convince yourself that even after you take many intersections and unions of finite and cofinite sets that you won't end up with an infinite set whose complement is also infinite.

Iteration does not have to work for cofinite sets.

Extra credit is all or nothing --- you either get the full 10% for implementing the complementation feature correctly or you get 0%.

Last Modified: 22 Jul 2024 11:28:51 EDT by Richard Chang

Back up to Fall 1998 CMSC 202 Section Homepage