I need to write a C++ program that does the following:


   In the mathematical theory of sets, a set is defined as a
collection of distinct (no two alike) items of the same type.  In some
programming languages, sets are a built-in data type.  C++ does not
have a built-in set type, though the Standard Template Library does
provide a set type as an add-on to the language.  We can simulate a
set in any language using a one-dimensional array.

                                                                                

There are several operations that can be performed on sets.  We will
consider only three of them:  union, intersection, and difference. 
These are binary operations requiring two sets as operands.

The union of two sets A and B (A + B), is a set that contains elements
that are in A or in B or in both.
The intersection of two sets A and B (A * B) is a set that contains
elements common to both A and B.
The difference of two sets A and B (A - B) is a set that contains only
the elements which are in A but not in B.
                                                                                

For example, if A and B are two sets of integers defined as 

A = { 5, 7, 8, 10 } and B = { 3, 9, 10 }, 

then their union (A + B) is the set { 3, 5, 7, 8, 9, 10 }  

their intersection (A * B) is the set { 10 } 

the difference of A and B (A - B) is the set { 5, 7, 8 }

the difference of B and A (B - A) is the set { 3, 9 }.

 

Input File
File  setdata.txt  contains an even number of lines of data.  Each
line represents the values to be assigned to a set.  Each line
contains up to 25 random positive integers with a space between
consecutive integers.  The integers are in no particular order, and a
particular integer may appear more than once.

Example:

4 8 10 2 14 7 10 8

 

Processing
Write a program that repeats the following until end of file:   

                      

1)  Read a line of data and store the input integers in set (array) A.
 Read another line of

     data and store the integers in set (array) B.  Echo print both input sets.

 

2)  Make sure that both arrays contain proper sets by eliminating
duplicate values in each.

     Place set values in ascending order (while the order of set
values is immaterial, the set

     is easier to read and more efficient to check if its values are
in order, and it gives me an

     excuse to ask you to use a sort).  You will probably find it
easier to eliminate duplicates

     if you do the sort first.                      

 

3)  Compute and print the union of A and B (A + B), the intersection
of A and B (A * B),

     the difference of A and B (A - B), and the difference of B and A
(B - A).

 

     Example of the output format required:

     A = { 3 1 2 4} 

     B = { 8 4 6 5 3 6 4 }

     { 1 2 3 4 } + { 3 4 5 6 8 } = { 1 2 3 4 5 6 8 }                          

     { 1 2 3 4 } * { 3 4 5 6 8 } = { 3 4 }                          

     { 1 2 3 4 } - { 3 4 5 6 8 } =  { 1 2 }                          

     { 3 4 5 6 8 } - { 1 2 3 4 }  =  { 5 6 8 }                          



 
Program Requirements:

1)  Since the purpose of this assignment is to give you practice in
array manipulations and  in sorting and searching, YOU MAY NOT USE the
Standard Template set type or other predefined set functions.

2)  You must call a sort function to sort each set.  You may use
either the bubble sort or the selection sort from the book to
implement sorting.  You could also use your bucket sort you developed
for Assignment #2 as your sorting method.

3)  You may assume that the data will be valid positive integers.

4)  The set unions which you calculate should not contain any
duplicate values.  You might find it useful to have a function which
eliminates duplicates.  You could call it for your input sets as well
as for the set union calculated.

5)  The union, intersection, and difference operations should be
implemented as functions to make it easier to use them in other
applications where a set might be useful.

6)  All union, intersection, and difference sets should be shown with
values in ascending order (call your sort function again).

7)  Sets should be output as shown in the examples (values printed
with a space or a comma between consecutive values and enclosed in
curly braces).



SAMPLE DATA FILE:

15 13 7 5 2 15
6 6 12 13 12 8 8 9 11 11 1 8 9 4 15 2 3 11
9 12 9 4 6 11 10 13 12 8 9 8 15 4 15 8 15 5 13 2 6 13 12
7 7 12 1 14 9 11 4 6 3 5 4 6 10 4 15 2 7 5 10 1
8
9 3 2 2 4
10 1 6 8 9 8 5 5 1 6 8 12 9 5 14
13 7 10 4 15 5 4 4 3 2 4 1 15 8 2 4 15 14 15 9 7 10 15 1 12
3 9 12
12 2 7 9 7 5 14 13 1 1 11 12 6 15 5 4 8 14 13 7


EXAMPLE RESULTS ON SAMPLE DATA FILE:

A = { 15 13  7  5  2 15 }
A = {  2  5  7 13 15 }
B = {  6  6 12 13 12  8  8  9 11 11  1  8  9  4 15  2  3 11 }
B = {  1  2  3  4  6  8  9 11 12 13 15 }

{  2  5  7 13 15 } + {  1  2  3  4  6  8  9 11 12 13 15 } = {  1  2  3
 4  5  6  7  8  9 11 12 13 15 }

{  2  5  7 13 15 } * {  1  2  3  4  6  8  9 11 12 13 15 } = {  2 13 15 }

{  2  5  7 13 15 } - {  1  2  3  4  6  8  9 11 12 13 15 } = {  5  7 }

{  1  2  3  4  6  8  9 11 12 13 15 } - {  2  5  7 13 15 } = {  1  3  4
 6  8  9 11 12 }



A = {  9 12  9  4  6 11 10 13 12  8  9  8 15  4 15  8 15  5 13  2  6 13 12 }
A = {  2  4  5  6  8  9 10 11 12 13 15 }
B = {  7  7 12  1 14  9 11  4  6  3  5  4  6 10  4 15  2  7  5 10  1 }
B = {  1  2  3  4  5  6  7  9 10 11 12 14 15 }

{  2  4  5  6  8  9 10 11 12 13 15 } + {  1  2  3  4  5  6  7  9 10 11
12 14 15 } = {  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 }

{  2  4  5  6  8  9 10 11 12 13 15 } * {  1  2  3  4  5  6  7  9 10 11
12 14 15 } = {  2  4  5  6  9 10 11 12 15 }

{  2  4  5  6  8  9 10 11 12 13 15 } - {  1  2  3  4  5  6  7  9 10 11
12 14 15 } = {  8 13 }

{  1  2  3  4  5  6  7  9 10 11 12 14 15 } - {  2  4  5  6  8  9 10 11
12 13 15 } = {  1  3  7 14 }



A = {  8 }
A = {  8 }
B = {  9  3  2  2  4 }
B = {  2  3  4  9 }

{  8 } + {  2  3  4  9 } = {  2  3  4  8  9 }

{  8 } * {  2  3  4  9 } = { }

{  8 } - {  2  3  4  9 } = {  8 }

{  2  3  4  9 } - {  8 } = {  2  3  4  9 }



A = { 10  1  6  8  9  8  5  5  1  6  8 12  9  5 14 }
A = {  1  5  6  8  9 10 12 14 }
B = { 13  7 10  4 15  5  4  4  3  2  4  1 15  8  2  4 15 14 15  9  7 10 15  1 12 }
B = {  1  2  3  4  5  7  8  9 10 12 13 14 15 }

{  1  5  6  8  9 10 12 14 } + {  1  2  3  4  5  7  8  9 10 12 13 14 15
} = {  1  2  3  4  5  6  7  8  9 10 12 13 14 15 }

{  1  5  6  8  9 10 12 14 } * {  1  2  3  4  5  7  8  9 10 12 13 14 15
} = {  1  5  8  9 10 12 14 }

{  1  5  6  8  9 10 12 14 } - {  1  2  3  4  5  7  8  9 10 12 13 14 15 } = {  6 }

{  1  2  3  4  5  7  8  9 10 12 13 14 15 } - {  1  5  6  8  9 10 12 14
} = {  2  3  4  7 13 15 }



A = {  3  9 12 }
A = {  3  9 12 }
B = { 12  2  7  9  7  5 14 13  1  1 11 12  6 15  5  4  8 14 13  7 }
B = {  1  2  4  5  6  7  8  9 11 12 13 14 15 }

{  3  9 12 } + {  1  2  4  5  6  7  8  9 11 12 13 14 15 } = {  1  2  3
 4  5  6  7  8  9 11 12 13 14 15 }

{  3  9 12 } * {  1  2  4  5  6  7  8  9 11 12 13 14 15 } = {  9 12 }

{  3  9 12 } - {  1  2  4  5  6  7  8  9 11 12 13 14 15 } = {  3 }

{  1  2  4  5  6  7  8  9 11 12 13 14 15 } - {  3  9 12 } = {  1  2  4
 5  6  7  8 11 13 14 15 }

I hope this is enough info. I need this by SAT. night 3-19-05.  If
anyone can help I would appreciate it.

---

Request for Question Clarification by studboy-ga on 17 Mar 2005 13:05 PST

Hi fert-ga

May I know the compiler you'll be using? gcc/g++?

Thanks!

---

Clarification of Question by fert-ga on 17 Mar 2005 13:28 PST

I am using DEV C++ ver. 4.9.9.0

---

Request for Question Clarification by studboy-ga on 17 Mar 2005 18:56 PST

The assignment mentioned you have done the array sort from assignment #2--
can you do that part?  If you can, I can post the rest in about 5
minutes for you to try.  Please let me know.  Thanks.

Hi,

OK, I assume selectionsort and give you that for free.  Enclosed are 3 files--
put them in the same directory:

set.cpp - main program
utils.hh - helper functions to parse input file and do sorting
input.txt - input file

Compile just set.cpp.  Run set.exe and the output is as shown (see below).
Compile.log from Dev C++ is also enclosed.

================================================================================
set.cpp:
================================================================================

#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include "utils.hh"

using namespace std;

int main() {

ifstream in("input.txt");
if (!in) return EXIT_FAILURE;

int t[25];
int a[25];
int b[25];
int u[50]; //union
int x[25]; //intersection
int d[25]; //difference

string line;
StringArray &tokens = * new StringArray("");

while (getline(in,line)) {
   size_t sz_t=0, sz_a=0, sz_b=0, sz_u=0, sz_x=0, sz_d=0;

   cout << "from file: " << line << endl;
   tokens = * new StringArray(line);
   for (int i=0; i<tokens.size(); ++i) {
      t[i] = atoi(tokens.at(i).c_str());
      ++sz_t;
   }
   //sort t[sz_t]
   selectsort(t, sz_t);
   //make unique
   for (int i=0; i<sz_t; ++i) {
      bool found=false;
      for(int j=0; j<sz_a; ++j) {
         if (t[i] == a[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         a[sz_a] = t[i];
         ++sz_a;
      }
   }
   cout << "A = { ";
   for(int i=0; i<sz_a; ++i) {
      cout << a[i] << " ";
   }
   cout << "}" << endl;

   sz_t=0;
   getline(in,line);
   cout << "from file: " << line << endl;
   tokens = * new StringArray(line);
   for (int i=0; i<tokens.size(); ++i) {
      t[i] = atoi(tokens.at(i).c_str());
      ++sz_t;
   }
   //sort t[sz_t]
   selectsort(t, sz_t);
   //make unique
   for (int i=0; i<sz_t; ++i) {
      bool found=false;
      for(int j=0; j<sz_b; ++j) {
         if (t[i] == b[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         b[sz_b] = t[i];
         ++sz_b;
      }
   }
   cout << "B = { ";
   for(int i=0; i<sz_b; ++i) {
      cout << b[i] << " ";
   }
   cout << "}" << endl;

   //compute union
   for(int i=0; i<sz_a; ++i) {
      u[i] = a[i];
      ++sz_u;
   }
   int sz_u_old = sz_u;
   for(int i=0; i<sz_b; ++i) {
      bool found=false;
      for(int j=0; j<sz_u_old; ++j) {
         if (b[i] == u[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         u[sz_u] = b[i];
         ++sz_u;
      }
   }
   //sort u[sz_u]
   selectsort(u, sz_u);
   cout << "A + B = { ";
   for(int i=0; i<sz_u; ++i) {
      cout << u[i] << " ";
   }
   cout << "}" << endl;

   //compute intersection
   for(int i=0; i<sz_a; ++i) {
      for(int j=0; j<sz_b; ++j) {
         if (a[i] == b[j]) {
            x[sz_x] = a[i];
            ++sz_x;
         }
      }
   }
   //sort x[sz_x]
   selectsort(x, sz_x);
   cout << "A * B = { ";
   for(int i=0; i<sz_x; ++i) {
      cout << x[i] << " ";
   }
   cout << "}" << endl;

   //compute differences
   //A - B
   for(int i=0; i<sz_a; ++i) {
      bool found=false;
      for(int j=0; j<sz_b; ++j) {
         if (a[i] == b[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         d[sz_d] = a[i];
         ++sz_d;
      }
   }
   //sort d[sz_d]
   selectsort(d, sz_d);
   cout << "A - B = { ";
   for(int i=0; i<sz_d; ++i) {
      cout << d[i] << " ";
   }
   cout << "}" << endl;
   sz_d = 0;
   //B - A
   for(int i=0; i<sz_b; ++i) {
      bool found=false;
      for(int j=0; j<sz_a; ++j) {
         if (b[i] == a[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         d[sz_d] = b[i];
         ++sz_d;
      }
   }
   //sort d[sz_d]
   selectsort(d, sz_d);
   cout << "B - A = { ";
   for(int i=0; i<sz_d; ++i) {
      cout << d[i] << " ";
   }
   cout << "}" << endl;

   //final
   cout << endl;
}

return 0;
}

================================================================================
utils.hh:
================================================================================

#include <vector>
#include <string>
using namespace std;

using namespace std;

class StringArray
{
public:
protected:
    vector<string> rep;
public:
    StringArray(void);
    StringArray(const string & s);
    virtual ~StringArray(void);
    int size(void);
    void add(const string & s);
    const string & at(int index);
    void tokenize(const string & t);
};

StringArray::StringArray(void) { }

StringArray::~StringArray() { }

int StringArray::size(void)
{
    return (int)rep.size();
}

void StringArray::add(const string & s)
{
    rep.push_back(s);
}

const string & StringArray::at(int index)
{
    return rep.at(index);
}

StringArray::StringArray(const string & s)
{
    tokenize(s);
}

void StringArray::tokenize(const string & t) {
    string s = t + " ";
    int i = 0;
    char ch = s.at(i++);
    while (true) {
        while (isspace(ch)) {
            if (i == s.length())
                return;
            ch = s.at(i++);
        }
        int start = i-1;
        if (ch == '"') {
            if (i == s.length())
                return;
            ch = s.at(i++);
            while (ch != '"') {
                if (i == s.length()) {
                    return;
                }
                ch = s.at(i++);
            }
            add(s.substr(start+1, i - start - 2));
        }
        else {
            while (!isspace(ch)) {
                if (i == s.length()) {
                    break;
                }
                ch = s.at(i++);
            }
            add(s.substr(start,i-start-1));
        }
        if (i == s.length())
            return;
    }
}

void selectsort (int arr[], int size) //selection sort
{
   int i_of_min;
   int pass;
   int j;

   for (pass=0; pass<size-1; pass++)
   {
           i_of_min = pass;

           for (j=pass+1; j<size; j++)
               if (arr[j]<arr[pass])
                   i_of_min = j;

           swap (arr[pass], arr[i_of_min]);
   }
}

// swap function for integers
void swap (int &x, int &y)
{
   int temp;
   temp = x;
   x = y;
   y = temp;
}


================================================================================
input.txt:
================================================================================

2 1 2 3
4 5 4
6 6 6 8 7 7
8 9

================================================================================
output:
================================================================================

from file: 2 1 2 3
A = { 1 2 3 }
from file: 4 5 4
B = { 4 5 }
A + B = { 1 2 3 4 5 }
A * B = { }
A - B = { 1 2 3 }
B - A = { 4 5 }

from file: 6 6 6 8 7 7
A = { 6 7 8 }
from file: 8 9
B = { 8 9 }
A + B = { 6 7 8 9 }
A * B = { 8 }
A - B = { 6 7 }
B - A = { 9 }

================================================================================
compile.log:
================================================================================

Compiler: Default compiler
Executing  g++.exe...
g++.exe "P:\.mill\set.cpp" -o "P:\.mill\set.exe"   
-I"E:\Dev-Cpp\lib\gcc\mingw32\3.4.2\include" 
-I"E:\Dev-Cpp\include\c++\3.4.2\backward" 
-I"E:\Dev-Cpp\include\c++\3.4.2\mingw32" 
-I"E:\Dev-Cpp\include\c++\3.4.2"  -I"E:\Dev-Cpp\include"  
-L"E:\Dev-Cpp\lib"
Execution terminated
Compilation successful

---

Clarification of Answer by studboy-ga on 17 Mar 2005 22:00 PST

I've also break it into functions:

void compute_union (int a[], int b[], int sz_a, int sz_b)
{
   int u[50], x[25], d[25];
   int sz_u=0, sz_x=0, sz_d=0;
   //compute union
   for(int i=0; i<sz_a; ++i) {
      u[i] = a[i];
      ++sz_u;
   }
   int sz_u_old = sz_u;
   for(int i=0; i<sz_b; ++i) {
      bool found=false;
      for(int j=0; j<sz_u_old; ++j) {
         if (b[i] == u[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         u[sz_u] = b[i];
         ++sz_u;
      }
   }
   //sort u[sz_u]
   selectsort(u, sz_u);
   cout << "A + B = { ";
   for(int i=0; i<sz_u; ++i) {
      cout << u[i] << " ";
   }
   cout << "}" << endl;
}

void compute_intersection(int a[], int b[], int sz_a, int sz_b)
{
   int u[50], x[25], d[25];
   int sz_u=0, sz_x=0, sz_d=0;
   //compute intersection
   for(int i=0; i<sz_a; ++i) {
      for(int j=0; j<sz_b; ++j) {
         if (a[i] == b[j]) {
            x[sz_x] = a[i];
            ++sz_x;
         }
      }
   }
   //sort x[sz_x]
   selectsort(x, sz_x);
   cout << "A * B = { ";
   for(int i=0; i<sz_x; ++i) {
      cout << x[i] << " ";
   }
   cout << "}" << endl;
}

void compute_differences(int a[], int b[], int sz_a, int sz_b)
{
   int u[50], x[25], d[25];
   int sz_u=0, sz_x=0, sz_d=0;
   //compute differences
   //A - B
   for(int i=0; i<sz_a; ++i) {
      bool found=false;
      for(int j=0; j<sz_b; ++j) {
         if (a[i] == b[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         d[sz_d] = a[i];
         ++sz_d;
      }
   }
   //sort d[sz_d]
   selectsort(d, sz_d);
   cout << "A - B = { ";
   for(int i=0; i<sz_d; ++i) {
      cout << d[i] << " ";
   }
   cout << "}" << endl;
   sz_d = 0;
   //B - A
   for(int i=0; i<sz_b; ++i) {
      bool found=false;
      for(int j=0; j<sz_a; ++j) {
         if (b[i] == a[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         d[sz_d] = b[i];
         ++sz_d;
      }
   }
   //sort d[sz_d]
   selectsort(d, sz_d);
   cout << "B - A = { ";
   for(int i=0; i<sz_d; ++i) {
      cout << d[i] << " ";
   }
   cout << "}" << endl;
}

---

Clarification of Answer by studboy-ga on 17 Mar 2005 23:23 PST

#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include "utils.hh"

using namespace std;

int main() {

ifstream in("input.txt");
if (!in) return EXIT_FAILURE;

int t[25];
int a[25];
int b[25];
int u[50]; //union
int x[25]; //intersection
int d[25]; //difference

string line;
StringArray &tokens = * new StringArray("");

while (getline(in,line)) {
   size_t sz_t=0, sz_a=0, sz_b=0, sz_u=0, sz_x=0, sz_d=0;

   cout << "from file: " << line << endl;
   tokens = * new StringArray(line);
   for (int i=0; i<tokens.size(); ++i) {
      t[i] = atoi(tokens.at(i).c_str());
      ++sz_t;
   }
   //sort t[sz_t]
   selectsort(t, sz_t);
   //make unique
   for (int i=0; i<sz_t; ++i) {
      bool found=false;
      for(int j=0; j<sz_a; ++j) {
         if (t[i] == a[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         a[sz_a] = t[i];
         ++sz_a;
      }
   }
   cout << "A = { ";
   for(int i=0; i<sz_a; ++i) {
      cout << a[i] << " ";
   }
   cout << "}" << endl;

   sz_t=0;
   getline(in,line);
   cout << "from file: " << line << endl;
   tokens = * new StringArray(line);
   for (int i=0; i<tokens.size(); ++i) {
      t[i] = atoi(tokens.at(i).c_str());
      ++sz_t;
   }
   //sort t[sz_t]
   selectsort(t, sz_t);
   //make unique
   for (int i=0; i<sz_t; ++i) {
      bool found=false;
      for(int j=0; j<sz_b; ++j) {
         if (t[i] == b[j]) {
            found = true;
            break;
         }
      }
      if (!found) {
         b[sz_b] = t[i];
         ++sz_b;
      }
   }
   cout << "B = { ";
   for(int i=0; i<sz_b; ++i) {
      cout << b[i] << " ";
   }
   cout << "}" << endl;

   compute_union(a, b, sz_a, sz_b);
   compute_intersection(a, b, sz_a, sz_b);
   compute_differences(a, b, sz_a, sz_b);
   
   //final
   cout << endl;
}

return 0;
}