View source for User:Jason.wilkins/Laboratory for Sets

{{Underconstruction}}

{{Lab Instructions}}

=Introduction=

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

<blockquote><i>Topics Covered in this Lab:</i>
   <ul>
   <li>Sets
   <li>Set operations
   </ul><i>Questions Answered in this Lab:</i>
   <ul><li>What is a set?
   <li>How might a set class be designed for C++?
   <li>What operations can be performed with sets?
   <li>How might set operations be implemented as part of a class?
   </ul><i>Demonstrable Skills Acquired in this Lab:</i>
   <ul><li>An understanding of sets and set operations
   <li>How one might implement a class given less specific instructions
   </ul></blockquote>

{{Create Project|Create a project <i>oop14iL</i>}}

=Sets=

A <i>set</i> is a collection of <i>mathematical objects</i> (As used in mathematics, <i>object</i> 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 <i>member</i> 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 <i>elements</i> 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 <math>\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}</math>.  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 <i>set builder notation</i>.  An example would be all even integers which can be written as <math>\{x|\text{where }k \in \mathbb{I}, x = 2k\}</math>, 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 <math>\{ \dots , -2, -1, 0, 1, 2, \dots \}</math> and even integers as <math>\{ \dots , -4, -2, 0, 2, 4, \dots \}</math>.


The "<math>\in</math>" operator, pronounced "element of," used in the previous example is a relational operator that is not built into C++.  It returns <tt>true</tt> 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 "<math>\mathbb{I}</math>."


The set containing all the mathematical objects under consideration is called the <i>universe</i>.  For example, if the real numbers are being considered then the <i>universe</i> is the infinite set <math>\mathbb{R}</math> 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 "<math>\in</math>" and "<math>\notin</math>" 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 [http://en.wikipedia.org/wiki/Set_(mathematics)]
* Wolfram MathWorld [http://mathworld.wolfram.com/Set.html]


=Implementing a <tt>Set</tt> Class=

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


<blockquote>
Create the files <b>Set.h</b> and <b>Set.cpp</b> now.  Implement a constructor for <tt>Set</tt> takes no arguments and creates a set with no members (the empty set).
</blockquote>


It is bad programming style to use the literal number <tt>7</tt> in all the places in the code that will access the boolean values of the <tt>Set</tt> 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 <i>magic numbers</i>.  It is better to make the number of elements into a constant static variable that is given a good descriptive name such as <tt>element_count</tt>.


==Adding Elements==

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


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


<blockquote>
Now, implement a member function <tt>add</tt> for <tt>Set</tt> that takes a <tt>char</tt> and sets the corresponding boolean in <tt>Set</tt> 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.  
</blockquote>


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


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


==Implementing the "element of" operator <math>\in</math>==

The "element of" operation is a relational operator like <tt>&gt;</tt>, <tt>&lt;</tt>, and <tt>==</tt>.  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 <tt>bool Set::functionName(char element)</tt>.  A good name for this function might be <tt>hasElement</tt> because then when it is used it would be written something like:

<source lang="cpp">
if (mySet.hasElement('B')) { 
    //... 
}
</source>


The name <tt>hasElement</tt> 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 <tt>char</tt> type so that <tt>'A'.ElementOf(set)</tt> can be written.  Fortunately, later we will write a binary operator that implements something better.


<blockquote>
Now, implement the method <tt>hasElement</tt>
</blockquote>


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


<blockquote>
Now, create a <b>main.cpp</b> and <b>master.h</b> and write code to test the <tt>Set</tt> class.


* Declare a <tt>Set</tt>.
* 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 <tt>remove</tt> method that does the opposite of <tt>add</tt> and implement code in <tt>main</tt> that will test <tt>remove</tt>.

</blockquote>


{{Lab Checkpoint|Demonstrate the test code for the lab instructor}}


==Implementing <tt>write</tt>==

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

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 <tt>write</tt>:


* Make sure to use <tt>hasElement</tt> 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 ("<tt>{}</tt>") or one ("<tt>{ }</tt>"), but two ("<tt>{  }</tt>") is not as nice.
* The mathematical objects <math>A</math> thru <math>G</math> are not character constants so do not print out single quotes.
* Final output should look something like <tt>{ A B C D }</tt> or <tt>{A B C D}</tt>.


The first example, <tt>{ A B C D }</tt> is easier to produce.  If one wishes to produce the second example, <tt>{A B C D}</tt>, then the code is actually similar to that needed to produce the output with commas, <tt>{A, B, C, D}</tt> 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 <b>before</b> 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).


<blockquote>
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 <tt>main</tt> that tests <tt>write</tt> by adding and removing elements and printing all the intermediate results.
</blockquote>


To print the empty set as a special case requires that the <tt>Set</tt> 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
<tt>isEmpty</tt> that can be used by other functions or the user.

Again, when implementing <tt>isEmpty</tt>, use <tt>hasElement</tt> 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 <tt>hasElement</tt> while every function that uses <tt>hasElement</tt> 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 <tt>add</tt>, <tt>remove</tt>, and <tt>hasElement</tt>.  These three functions can be used to implement all the other methods.


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


Make sure to add code to <tt>main</tt> to test these modifications.
</blockquote>


==Implementing <tt>read</tt>==

Reading input from the user should be the inverse of writing.  That means that the <tt>Set</tt> class should read exactly what it writes.  This means that one character should be read at a time.  If the first character is a <tt>0</tt> then the set is empty, if it is a <tt>{</tt> then the characters should be added to the set until a <tt>}</tt> is read.  If you chose to implement commas as delimiters than make sure to skip over them.

<blockquote>
Now, implement a <tt>read</tt> method that accepts for input exactly the same format that was implemented for output.

Also, add another constructor to the class that takes an <tt>ifstream</tt> as an argument and initializes the object from a file.  The constructor can merely call the <tt>read</tt> function to do most of the work.

Make sure to add code to main to test these new functions.
</blockquote>


{{Lab Checkpoint|Demonstrate the <tt>write</tt> and <tt>read</tt> functions to the lab instructor}}


=Set Operations=

...

{{Lab Submit Zipped Files|zip=oop14iL.zip|Makefile Set.h Set.cpp master.h main.cpp}}