User:Jason.wilkins/Laboratory for Sets

From A-State Computer Science Wiki
Revision as of 12:44, 19 April 2010 by Jason.wilkins (Talk | contribs) (Implementing write)

Jump to: navigation, search

A portion of this lab is to be done during the scheduled lab time. The take-home programming assignment is to be turned in before the next lab; see the lab website. The in-lab portion is worth 40% of the lab credit; the programming assignment is worth the other 60%. See the website for details on how the programming assignment will be graded. You are not responsible for user errors in input unless specified in the assignment. Feedback will be provided explaining your grade on each assignment.

It is important that you complete each step before going on to the next, as the exercises build upon one another. You will find it helpful to diagram the action of each method or function as you go along. If you have difficulty in some step, DO NOT proceed before resolving it; seek assistance from your lab proctor. You will not be able to fully appreciate the remaining content of the lab and you are likely to compound the problem.

Introduction

In this lab a Set class is developed using the skills learned in previous labs. The instructions given here are less specific and intended more as general guidance.

Topics Covered in this Lab:
  • Sets
  • Set operations
Questions Answered in this Lab:
  • What is a set?
  • How might a set class be designed for C++?
  • What operations can be performed with sets?
  • How might set operations be implemented as part of a class?
Demonstrable Skills Acquired in this Lab:
  • An understanding of sets and set operations
  • How one might implement a class given less specific instructions
Createproject.pngCreate a project oop14iL

Sets

A set is a collection of mathematical objects (As used in mathematics, object is just a way to say "thing", so a set is a collection of things. This is a distinct idea from C++ objects.). A mathematical object is either a member of a set or not, so it does not make sense for an object to be in a set more than once. However, an object can be a member of multiple sets at once. Sets are themselves consider to be mathematical objects, so it is possible to have sets that contain other sets.


To avoid ambiguity, from this point mathematical objects spoken of in relation to sets will be called elements from this point onward.


Sets are commonly denoted by using curly braces in one of two ways. The first is to exhaustively list every element of a set within the curly braces. For example, the set containing the integers between 1 and 10 could be written as \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}. However most sets are too large to define this way and may even contain an infinite number of elements and are denoted using what is referred to as set builder notation. An example would be all even integers which can be written as \{x|\text{where }k \in \mathbb{I}, x = 2k\}, and which is read as "x such that where k is an integer, x is two times k." Sometimes, infinite sets are more intuitively denoted by using ellipsis, for example, all integers could be written \{ \dots , -2, -1, 0, 1, 2, \dots \} and even integers as \{ \dots , -4, -2, 0, 2, 4, \dots \}.


The "\in" operator, pronounced "element of," used in the previous example is a relational operator that is not built into C++. It returns true if the element given on the left is a member of the set given on the right. Also mentioned in the previous example is the the set of all integers which is so commonly used that it has a shorthand notation "\mathbb{I}."


The set containing all the mathematical objects under consideration is called the universe. For example, if the real numbers are being considered then the universe is the infinite set \mathbb{R} containing all reals.


Summary

  • Sets are collections of elements.
  • Each given element is either is a member or not a member of a given set.
  • The relational operator "\in" and "\notin" are used to test set membership.
  • An element cannot appear in a set twice.
  • An element can be in more than one set at once.
  • A set is denoted by listing all the elements inside of curly braces.
  • Infinite sets are denoted using set builder notation or ellipsis.

More information about sets can be found on the Internet.

  • Wikipedia [1]
  • Wolfram MathWorld [2]


Implementing a Set Class

For simplicity for the rest of this lab we are only going to only consider the letters from A to G to be the universe. This set can be denoted as \{ A, B, C, D, E, F, G \}. A Set implemented for this universe in C++ will have to keep track of whether each letter is a member of the Set or not. This can be done by keeping an array of seven boolean values where if an array element is set to true then the corresponding set element is a member of the set.


Create the files Set.h and Set.cpp now. Implement a constructor for Set takes no arguments and creates a set with no members (the empty set).


It is bad programming style to use the literal number 7 in all the places in the code that will access the boolean values of the Set class. If ever the number of elements is changed then it will need to be changed in many places and this introduces the chance that one of the places will be missed. Values scattered throughout the code like this are called magic numbers. It is better to make the number of elements into a constant static variable that is given a good descriptive name such as element_count.


Adding Elements

It would be nice to be able to use C++ character literals like 'A' and 'E' to stand for the elements A and E. Recall that character literals in C++ are really just a convenient way to write ASCII character codes [www.asciitable.com]. For example, 'A' is equal to to the integer 65. Also, the codes 'A' thru 'G' are sequential. Remember that the character constants 'a' thru 'b' have different values.


However, the boolean variables that are a part of Set have indexes from 0 to 6. Because character literals are really numbers it is easy to map them to indexes by using subtraction. 'A' - 65 is 0 and 'G' - 65 is 6, but even better this can be written as 'A' - 'A' and 'G' - 'A' which eliminates the magic number 65.


Now, implement a member function add for Set that takes a char and sets the corresponding boolean in Set to true. The member function does not need to return a value. The function should check that the calculated index is between zero and six and print out a useful warning message if it is not.


There is a function declared as char toupper(char) declared in the standard header file named cctype that can be used to convert a lower-case letter to an upper-case letter. For example toupper('a') == 'A' is true. If a character is not a lower case letter then toupper just returns the character it was given.


Now, modify add to take both lower and upper case letters by converting all characters passed into add into upper-case letters.


Implementing the "element of" operator \in

The "element of" operation is a relational operator like >, <, and ==. Even though it is an operator, for now, lets think of it as a member function.


Lets consider how to implement it as a member function. Because it is a relational operator it should return a boolean. Because it is a member function it has access to the internal private boolean values that indicate set membership. So, the only remaining information that it needs is which element to test for membership. The element to test for membership can be passed to the function as an argument. To summarize, we need to implement a function that looks like this bool Set::functionName(char element). A good name for this function might be hasElement because then when it is used it would be written something like:

if (mySet.hasElement('B')) { 
    //... 
}


The name hasElement is good because it reads well. In the example above it could be read out loud as "if my set has element 'B' then ...," which is understandable as English. Naming variables and functions this way aids others to understand your code.

Unfortunately, a function named "ElementOf" is not possible since it is not possible to add a method to the char type so that 'A'.ElementOf(set) can be written. Fortunately, later we will write a binary operator that implements something better.


Now, implement the method hasElement


Now that there are both add and hasElement functions it is possible to compile and test the code and see if it works.


Now, create a main.cpp and master.h and write code to test the Set class.


  • Declare a Set.
  • Test for all elements and make sure none of them are in the set.
  • Add an element to the set.
  • Test that the newly added element is now a member.
  • Attempt to add erroneous elements to the set and make sure an error message is printed.


Now that the class is tested, add a remove method that does the opposite of add and implement code in main that will test remove.



Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate the test code for the lab instructor


Implementing write

Non-empty sets are denoted inside curly braces, so any write function should begin by printing a left brace and end by printing a right brace. The empty set is denoted using the symbol \emptyset but the closest thing on the keyboard is the 0.

There are several ways to handle output depending on how fancy one wants to be. Let's start with the easiest, which is to separate elements with spaces, and to just write the empty set as a pair of empty braces. There are several things to pay attention too while implementing this version of write:


  • Make sure to use hasElement instead of checking membership directly.
  • A user may want to write a set as part of a sentence, so do not output a newline character afterwards.
  • Spacing should be even, meaning that if there is a space before the first element there should be one after the last element.
  • The empty set may look good with either no spaces ("{}") or one ("{ }"), but two ("{ }") is not as nice.
  • The mathematical objects A thru G are not character constants so do not print out single quotes.
  • Final output should look something like { A B C D } or {A B C D}.


The first example, { A B C D } is easier to produce. If one wishes to produce the second example, {A B C D}, then the code is actually similar to that needed to produce the output with commas, {A, B, C, D} because the delimiter (the separating character) is between each element but not before the first or after the last. The trick to producing elegant code for printing commas is to realize that the comma is printed out before every element except the first. The reason the code is more elegant is that it is often easier to tell what the first element is rather than determining what the last element is (although this does not apply if one is using arrays).


Now, implement a version of the write function. The priority here is to make it print neatly following the guidelines above. Optionally, add code to print commas as a delimiter.

Make sure to add code to main that tests write by adding and removing elements and printing all the intermediate results.


To print the empty set as a special case requires that the Set be checked for emptiness before even printing the first curly brace. This can be done as a loop that checks for every element in the universe, and if none are found, return true. This code could be added to the write function, however this presents an opportunity to create a new function isEmpty that can be used by other functions or the user.

Again, when implementing isEmpty, use hasElement instead of directly accessing the internal member Booleans. This allows code for accessing the internal data to be reused. If there was ever a time when the internal data needed to be implemented in a different way, the only function that would need changing would be hasElement while every function that uses hasElement will not have to be changed. If a function directly accesses the internal data then it would have to be changed to, so it is better to make sure the only functions that access the internal data directly are add, remove, and hasElement. These three functions can be used to implement all the other methods.


Now, implement a method isEmpty that returns true if a set is empty, and then use isEmpty inside of write to print a 0 if the set is empty.


Make sure to add code to main to test these modifications.



Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate the write function to the lab instructor


Set Operations

Labsubmitsinglefile.png FOR IN-LAB CREDIT: Zip up these files: oop14iL.zip
Name the file {{{zip}}} and upload to CSCADE.