Programming Forums > Application Development > C++

codylee270 · Oct 27th, 2006, 12:03 PM

Here is the code to my next programming project.

The subset sum problem is stated as follows:  Given a set of positive integers, S, and a 
positive integer, L, find all of the subsets of the set S such that the sum of all of the 
elements in the subset is equal to L. 
 
For example, consider the set S = {11, 5, 9, 14, 6} and L = 11.  The solution to 
the subset sum problem is: S1 = {11}; S2 = {5, 6} since the sum of all of the 
elements of S1 = 11, and the sum of all of the elements of S2 = 5+6 = 11.  Solutions 
to other subset sum problems include: 
 
 
S = {1, 3, 11, 13}; L = 1 
S1 = {1} 
 
S =  {4, 7, 10, 14, 20}; L = 12 
S1 = {} 
 
S = {3, 6, 9, 12, 15}; L = 15 
S1 = {3, 12} 
S2 = {6, 9} 
S2 = {15} 
 
 
The subset sum belongs to a set of algorithms that are NP-complete, meaning that they cannot be solved in polynomial time.  

One method to solve the subset sum problem is through the use of backtracking.  What we will do in this case is examine all of the possible subsets, Si, of a particular set S.  
Note that for a set of length L, there are 2L possible subsets.  For instance if S = {1, 2, 3}, 
the possible subsets are {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 
2, 3} and the empty set {}.   
 
All of the possible subsets of a set can be generated by creating a vector of Boolean values of length L, where position Li is true if the element at position i of the set S is included in the subset, and false otherwise.  For your second programming project, there 
are four main additions: 
 
1) Change your sets to incorporate templates, so you can have sets of different types. 
2) Create a public member function findSubsetSum which reads in an integer L 
and prints out all of the subsets of the current set instance where the sum of the 
subsets is equal to L.  findSubsetSum will create the initial call to the private 
member function recurseSubsetSum. 
3) Create a private member function recurseSubsetSum which will examine all 
of the possible subsets of the current set instance, and if the sum of the elements is 
in the subset, it will print them out. 
4) Create five test cases for the subset sum problem, and code these into file 
newUseSets.cpp, which is given below. 
 
To help you out, the pseudocode for the findSubsetSum and 
recurseSubsetSum functions is given below: 
 
function findSubsetSum (sumToFind) { 
   create a Boolean array of the length of the set 
   initialize all of the values to false 
   call recurseSubsetSum, passing the Boolean array,  
   the sum to find, the current index pointing to the  
   beginning of the set, and the current sum of the subset   
   equal to zero 
   return 
} 
 
 
function recurseSubsetSum(booleanArray, sumToFind, currentPosition, 
currentSum) { 
   if(the currentPosition is at the end of the set) 
       if(currentSum is the sumToFind) 
            print out the subset (which is also a set!!!) 
      else 
           current subset is not a solution (do nothing) 
   else 
      include the next element in the set in the subset 
      add the next element to the current sum 
      recursively call recurseSebsetSum, with the currentPosition  
      incremented 
 
      // NOW BACKTRACK 
      remove next element from the subset 
      subtract next element from the current sum 
      recursively call recurseSubsetSum 
   } 
} 
 
 
The file newUseset.cpp that needs to be modified with your test cases and with the 
addition of templates is: 
#include "MySet.H" 
 
#include <iostream> // used for cin, cout, etc 
#include <cstdlib>  // used for EXIT_SUCCESS 
#include <ctime>    // used to seed the random number generator 
using namespace std; 
 
int main() { 
   srand((unsigned)time(0));    // Seed the random number generator 
 
   MySet OrigSet("Original Set"); 
 
   // RANDOMLY PICK 25 numbers for the set between 0 and 1000 
   for(int i = 0; i < 20; i++) { 
      int randNum = 1 + (int)(20.0 * (rand()/(RAND_MAX + 1.0))); 
      OrigSet += randNum; 
   } 
 
  int subsetSum = 1 + (int)(30.0 * (rand()/(RAND_MAX + 1.0))); 
  cout << "The orginal set is "; 
  cout << OrigSet << endl; 
  cout << "The subset sum to find is: "<< subsetSum << endl; 
  OrigSet.findSubsetSum(subsetSum); 
 
  MySet TestSet("TEST SET"); 
  TestSet += 1; 
  TestSet += 2; 
  TestSet += 3; 
  TestSet += 4; 
  int testSum = 5; 
  cout << "The Test set is " << TestSet << endl; 
  cout << "The subset sum to find is: " << testSum << endl; 
 
  cout << "Expected solution: {1, 4}; {2,3}" << endl; 
  TestSet.findSubsetSum(testSum); 
 
   return EXIT_SUCCESS; 
} 
 
A sample output for this program is: 
 
The orginal set is Original Set = {11, 16, 2, 17, 10, 8, 18, 6, 4, 7, 
15, 19, 20} 
The subset sum to find is: 13 
SUBSETSUM = {11, 2} 
SUBSETSUM = {2, 4, 7} 
SUBSETSUM = {6, 7} 
The Test set is TEST SET = {1, 2, 3, 4} 
The subset sum to find is: 5 
Expected solution: {1, 4}; {2,3} 
SUBSETSUM = {1, 4} 
SUBSETSUM = {2, 3}

The subset sum problem is stated as follows:  Given a set of positive integers, S, and a 
positive integer, L, find all of the subsets of the set S such that the sum of all of the 
elements in the subset is equal to L. 
 
For example, consider the set S = {11, 5, 9, 14, 6} and L = 11.  The solution to 
the subset sum problem is: S1 = {11}; S2 = {5, 6} since the sum of all of the 
elements of S1 = 11, and the sum of all of the elements of S2 = 5+6 = 11.  Solutions 
to other subset sum problems include: 
 
 
S = {1, 3, 11, 13}; L = 1 
S1 = {1} 
 
S =  {4, 7, 10, 14, 20}; L = 12 
S1 = {} 
 
S = {3, 6, 9, 12, 15}; L = 15 
S1 = {3, 12} 
S2 = {6, 9} 
S2 = {15} 
 
 
The subset sum belongs to a set of algorithms that are NP-complete, meaning that they cannot be solved in polynomial time.  

One method to solve the subset sum problem is through the use of backtracking.  What we will do in this case is examine all of the possible subsets, Si, of a particular set S.  
Note that for a set of length L, there are 2L possible subsets.  For instance if S = {1, 2, 3}, 
the possible subsets are {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 
2, 3} and the empty set {}.   
 
All of the possible subsets of a set can be generated by creating a vector of Boolean values of length L, where position Li is true if the element at position i of the set S is included in the subset, and false otherwise.  For your second programming project, there 
are four main additions: 
 
1) Change your sets to incorporate templates, so you can have sets of different types. 
2) Create a public member function findSubsetSum which reads in an integer L 
and prints out all of the subsets of the current set instance where the sum of the 
subsets is equal to L.  findSubsetSum will create the initial call to the private 
member function recurseSubsetSum. 
3) Create a private member function recurseSubsetSum which will examine all 
of the possible subsets of the current set instance, and if the sum of the elements is 
in the subset, it will print them out. 
4) Create five test cases for the subset sum problem, and code these into file 
newUseSets.cpp, which is given below. 
 
To help you out, the pseudocode for the findSubsetSum and 
recurseSubsetSum functions is given below: 
 
function findSubsetSum (sumToFind) { 
   create a Boolean array of the length of the set 
   initialize all of the values to false 
   call recurseSubsetSum, passing the Boolean array,  
   the sum to find, the current index pointing to the  
   beginning of the set, and the current sum of the subset   
   equal to zero 
   return 
} 
 
 
function recurseSubsetSum(booleanArray, sumToFind, currentPosition, 
currentSum) { 
   if(the currentPosition is at the end of the set) 
       if(currentSum is the sumToFind) 
            print out the subset (which is also a set!!!) 
      else 
           current subset is not a solution (do nothing) 
   else 
      include the next element in the set in the subset 
      add the next element to the current sum 
      recursively call recurseSebsetSum, with the currentPosition  
      incremented 
 
      // NOW BACKTRACK 
      remove next element from the subset 
      subtract next element from the current sum 
      recursively call recurseSubsetSum 
   } 
} 
 
 
The file newUseset.cpp that needs to be modified with your test cases and with the 
addition of templates is: 
#include "MySet.H" 
 
#include <iostream> // used for cin, cout, etc 
#include <cstdlib>  // used for EXIT_SUCCESS 
#include <ctime>    // used to seed the random number generator 
using namespace std; 
 
int main() { 
   srand((unsigned)time(0));    // Seed the random number generator 
 
   MySet OrigSet("Original Set"); 
 
   // RANDOMLY PICK 25 numbers for the set between 0 and 1000 
   for(int i = 0; i < 20; i++) { 
      int randNum = 1 + (int)(20.0 * (rand()/(RAND_MAX + 1.0))); 
      OrigSet += randNum; 
   } 
 
  int subsetSum = 1 + (int)(30.0 * (rand()/(RAND_MAX + 1.0))); 
  cout << "The orginal set is "; 
  cout << OrigSet << endl; 
  cout << "The subset sum to find is: "<< subsetSum << endl; 
  OrigSet.findSubsetSum(subsetSum); 
 
  MySet TestSet("TEST SET"); 
  TestSet += 1; 
  TestSet += 2; 
  TestSet += 3; 
  TestSet += 4; 
  int testSum = 5; 
  cout << "The Test set is " << TestSet << endl; 
  cout << "The subset sum to find is: " << testSum << endl; 
 
  cout << "Expected solution: {1, 4}; {2,3}" << endl; 
  TestSet.findSubsetSum(testSum); 
 
   return EXIT_SUCCESS; 
} 
 
A sample output for this program is: 
 
The orginal set is Original Set = {11, 16, 2, 17, 10, 8, 18, 6, 4, 7, 
15, 19, 20} 
The subset sum to find is: 13 
SUBSETSUM = {11, 2} 
SUBSETSUM = {2, 4, 7} 
SUBSETSUM = {6, 7} 
The Test set is TEST SET = {1, 2, 3, 4} 
The subset sum to find is: 5 
Expected solution: {1, 4}; {2,3} 
SUBSETSUM = {1, 4} 
SUBSETSUM = {2, 3}

I can change the actual program that is being added into to use templates just fine, but I am confused with the following:

1) What the vector of boolean values has to do with anything. The pseudocode for the recursive function really doesn't mention the vector, conveniently enough.

2) What's happening with:

// NOW BACKTRACK
remove next element from the subset
subtract next element from the current sum
recursively call recurseSubsetSum

Where would the next element be? From the if/elses before this backtracking part, it looks like it searches the entire set that was originally used to invoke the findSubsetSum member function. Then it starts the backtracking and removing of elements created using the recursice function. Any ideas? I still don't understand the usage of the vector required.

If anyone can help get started on this, I will greatly appreciate it.

Thanks!

The Dark · Oct 27th, 2006, 12:17 PM

1. the subset is stored in the boolean array, so whenever the pseudo code says "subset", it means the boolean array. The array indicates which values of the set are in the subset.
2. The "next element" is the element at currentPosition, so to remove that element from the subset, you just set the boolean array element at currentPosition to false.

codylee270 · Oct 27th, 2006, 2:24 PM

since no actual numeric values are stored in the boolen vector, what exactly does this boolen array do for us in this situation? B/c the in the pseudocode it sometimes says to printout the subset, which of course is going to be a numeric value that adds up to a certain number, not true/false.

When findSubset asks to pass the current index pointing to be beginning of the set, is it asking for the index of the beginning of the MySet object that invoked it or the beginning index of the boolean vector?

And since this boolean array is given a set length at the beginning and all value initialized to false, does it have to be a vector?

Finally ( for this post at least) - this function will be void, correct?

The Dark · Oct 27th, 2006, 7:18 PM

You use the boolean vector to determine which of the values in the set vector are in the subset. When you want to print the subset, loop through the boolean vector and the set vector in step and print out any entry in the set vector that has a corresponding true in the boolean vector.

Both. The currentIndex passed in is an integer, which is the position in both the set vector and the boolean vector.

The only reason the boolean array has to be a vector, is because the assignment specifies that it is. a vector is probably easier to manage anyway, but a array allocated with new wold work just as well.

It doesn't seem to need to return anything, so it might as well be void.

codylee270 · Oct 28th, 2006, 7:14 PM

Well, before I can actually attempt to figure out the recursive function for this assignment, I need to convert one of my old programs into template form. I had assumed all this required was to remove my typedef and put "template <class element_type>" before the class definition and before all the member function implementations, but when trying to compile, I got blue-million errors. Now, I know the errors are template related, but this is technically the first time I've ever used templates, so I'm posting the header file and implementation file of my old program that is reused for this assignment with the template stuff added. What stupid stuff did i do this time to cause the explosion with VS.

Header file:

(Toggle Plain Text)

//FILE: mySet.h
#ifndef MYSET_H
#define MYSET_H

//Cody S. --- CECS 302
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>


#define MAX_SET_SIZE 100 // Default maximum set size


template <class element_type>
class MySet {
public:
// FIRST, CONSTRUCTOR AND DESTRUCTOR PROTOTYPES
MySet(); //Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
MySet(string label);
//Precondition - Accepts value of type string only
//Postcondition - A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
MySet(string label, int maxSize);
//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
MySet(int maxSize);
MySet(MySet &secondSet); // automatic copy constructor
//Precondtion - Accepts object of type Myset
//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
~MySet(); //Postcondition - Reallocates data of container from activating object

// THEN PUBLIC MEMBER FUNCTIONS

int cardinality(); // Postcondition - Returns the set size
bool inSet(element_type element); 
//Precondition - element must be of type element_type
//Postcondition returns true if element is in the set; false otherwise

bool isFull(); // Postcondtion - Returns true if set is full
element_type getElement(int index); 
// Precondition - Accepts integer value only
// Postcondtion - Returns element at position index
void setLabel(string label); 
// Precondtion - Accepts string only
// Postcondition - sets the name of the set


// OVERLOADED OPERATORS AS MEMBER FUNCTIONS -, += (one for
// adding contents of a second set; one for adding single
// element) -=, =
// OVERLOAD FRIEND OPERATORS FOR UNION (+), INTERSECTION (*)
// DIFFERENCE (-) and OUTPUT (<<) AS WELL

void MySet::operator +=(MySet &addedSet);
//Precondtion - Accepts reference to object type MySet
// Post Condition - adds int values of second set into activating set - unique values only - no return - void
void MySet::operator +=(element_type addedElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - adds int value into activating set if max size isn't achieved - unique values only - no return - void
void MySet::operator -=(MySet &subSet);
//Precondtion - reference to object type MySet
//Postcondition - subtracts int values of second set into activating set - unique values only - no return - void
void MySet::operator -=(element_type subElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - subtracts int value into activating set if not empty - unique values only - no return - void
void MySet::operator =(MySet &secondSet);
//Precondtion - Accepts reference to object type MySet
//Postcondition: Sets activating object equal to the right hand operand of type MySet

//friends

friend ostream& operator << (ostream& outs, MySet& source);
//Precondtion - accepts a reference to ostream and a reference to object type MySet
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
friend MySet operator -(MySet &aSet, MySet &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
friend MySet operator +(MySet &aSet, MySet &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
friend MySet operator *(MySet &aSet, MySet &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition - Returns set of type MySet with contents of the intersection between the two passed sets

private:
// PRIVATE DATA MEMBERS AND FUNCTIONS CAN ONLY BE ACCESSED
// WITHIN THE CLASS AND FRIENDS OF THE CLASS


element_type *Container;
int setSize; // number of elements for the set
string setName; // label for the set
int maxSetSize; // maximum number of elements for the set

};
#endif

//FILE: mySet.h
#ifndef MYSET_H
#define MYSET_H

//Cody S. --- CECS 302
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>


#define MAX_SET_SIZE 100 // Default maximum set size


template <class element_type>
class MySet {
public:
// FIRST, CONSTRUCTOR AND DESTRUCTOR PROTOTYPES
MySet(); //Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
MySet(string label);
//Precondition - Accepts value of type string only
//Postcondition - A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
MySet(string label, int maxSize);
//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
MySet(int maxSize);
MySet(MySet &secondSet); // automatic copy constructor
//Precondtion - Accepts object of type Myset
//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
~MySet(); //Postcondition - Reallocates data of container from activating object

// THEN PUBLIC MEMBER FUNCTIONS

int cardinality(); // Postcondition - Returns the set size
bool inSet(element_type element); 
//Precondition - element must be of type element_type
//Postcondition returns true if element is in the set; false otherwise

bool isFull(); // Postcondtion - Returns true if set is full
element_type getElement(int index); 
// Precondition - Accepts integer value only
// Postcondtion - Returns element at position index
void setLabel(string label); 
// Precondtion - Accepts string only
// Postcondition - sets the name of the set


// OVERLOADED OPERATORS AS MEMBER FUNCTIONS -, += (one for
// adding contents of a second set; one for adding single
// element) -=, =
// OVERLOAD FRIEND OPERATORS FOR UNION (+), INTERSECTION (*)
// DIFFERENCE (-) and OUTPUT (<<) AS WELL

void MySet::operator +=(MySet &addedSet);
//Precondtion - Accepts reference to object type MySet
// Post Condition - adds int values of second set into activating set - unique values only - no return - void
void MySet::operator +=(element_type addedElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - adds int value into activating set if max size isn't achieved - unique values only - no return - void
void MySet::operator -=(MySet &subSet);
//Precondtion - reference to object type MySet
//Postcondition - subtracts int values of second set into activating set - unique values only - no return - void
void MySet::operator -=(element_type subElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - subtracts int value into activating set if not empty - unique values only - no return - void
void MySet::operator =(MySet &secondSet);
//Precondtion - Accepts reference to object type MySet
//Postcondition: Sets activating object equal to the right hand operand of type MySet

//friends

friend ostream& operator << (ostream& outs, MySet& source);
//Precondtion - accepts a reference to ostream and a reference to object type MySet
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
friend MySet operator -(MySet &aSet, MySet &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
friend MySet operator +(MySet &aSet, MySet &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
friend MySet operator *(MySet &aSet, MySet &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition - Returns set of type MySet with contents of the intersection between the two passed sets

private:
// PRIVATE DATA MEMBERS AND FUNCTIONS CAN ONLY BE ACCESSED
// WITHIN THE CLASS AND FRIENDS OF THE CLASS


element_type *Container;
int setSize; // number of elements for the set
string setName; // label for the set
int maxSetSize; // maximum number of elements for the set

};
#endif

Implementation

(Toggle Plain Text)

// FILE: Imp.cpp
#include "MySet.H"
#include <iostream> // used for cin, cout, etc
#include <cstdlib> // used for EXIT_SUCCESS
#include <ctime> // used to seed the random number generator
#include <cassert>
#include <string>

using namespace std;

#define MAX_SET_SIZE 100 // Default maximum set size

//Implementations

// Automatic Copy Constructor
template <class element_type>
MySet::MySet(MySet &secondSet) {
	//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
   Container = new element_type[secondSet.maxSetSize];
   maxSetSize = secondSet.maxSetSize;
   setName = secondSet.setName;
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
}
// assignment operator
template <class element_type>
void MySet::operator = (MySet &secondSet) {
	//Postcondition: Sets activating object equal to the right hand operand of type MySet
   if(this == &secondSet)
      return;
   if(maxSetSize != secondSet.maxSetSize) {
      element_type *newContainer;
      newContainer = new element_type[secondSet.maxSetSize];
      delete [] Container;
      Container = newContainer;
      maxSetSize = secondSet.maxSetSize;
   }
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
   setName = secondSet.setName;
}
template <class element_type>
MySet::MySet()
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
              setSize = 0;
              maxSetSize = MAX_SET_SIZE; 
              Container = new element_type[maxSetSize];  //Creates new empty container of default max size
}

template <class element_type>
MySet::MySet(string label)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = MAX_SET_SIZE;
              Container = new element_type[maxSetSize]; //Creates new empty container of default max size
              setLabel(label);
}

template <class element_type>
MySet::MySet(string label, int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
              setLabel(label);
}

template <class element_type>
MySet::MySet(int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
}

template <class element_type>
MySet::~MySet()
{
	//destructor - reallocates memory
               delete Container;
}

template <class element_type>
int MySet::cardinality(){return(setSize);} //Postcondition - return size of activating set

template <class element_type>
bool MySet::inSet(element_type element) // return true/false based on existence of searched element
{
     //int searchElement;
     for( int i = 0; i < cardinality(); ++i) // Checks if element exists
     {
          if (Container[i] == element)
          {
              return(true);
          }
     }
     return(false);
}

template <class element_type>
bool MySet::isFull()
{
	//Postcondition: Returns true if the activating set has reached its max size
     return(cardinality() == maxSetSize); // returns true if the set size is equal to its max size 
}
template <class element_type>
element_type MySet::getElement(int index) {return (Container[index]);} //returns int value of set at given index

template <class element_type>
void MySet::setLabel(string label) {setName = label;} // Post Condition - sets label for set based on user input - no return

template <class element_type>
void MySet::operator +=(MySet &addedSet) // Post Condition - adds int values of seconds set into activating set - unique values only - no return
{
     
     if ( this == &addedSet)
                 return; // Sets are unique - no copies allowed - a+=a takes no action
     for(int i = 0; i < addedSet.cardinality(); i++) // Adds element into activating object if it doesn't already exist
         {
             if(!inSet(addedSet.Container[i]))
               (*this)+=addedSet.Container[i];
                
         }
}

template <class element_type>
void MySet::operator +=(element_type addedElement) //Postcondition - adds int value into activating set if max size isn't achieved - unique values only
												   // Void- no return
{
     assert( (cardinality() + 1) <= maxSetSize);
     if(isFull())
     cout << endl << "Action can't be completed. Set is full." << endl;
     else
     Container[setSize] = addedElement;
     setSize++;
}

template <class element_type>
void MySet::operator -=(MySet &subSet)
{
	//Postcondition: Subtracts int values from activating set based on passed set, if the values exist - uniques values only - void - no return
     
     for(int i = 0; i < subSet.cardinality(); i++) // Subtracts elements from activating object if values of passed set = those in activator
         {
             if(inSet(subSet.Container[i]))
               (*this)-=subSet.Container[i];
         } 
}    
template <class element_type>
void MySet::operator -=(element_type subElement) // erases one element 
{
	//Postcondition: Subtracts int value from activating set based on passed element, if the value exists - uniques values only - void - no return
     assert( (cardinality() - 1) >= 0);
     int index=0;
     for( int i = 0; i < cardinality(); ++i) 
     {
          if (Container[i] == subElement) // gets index of element to be erased
          {
              index = i;
          }
     }
     
     setSize--;
     for(int i = index; i < setSize; i++) // Moves all data forward if values are subtracted to maintain container continuity
     {
             Container[i] = Container[i + 1];
     }
}


     

//----------- Friends ---------------------------------------------------------------------------------------------  
template <class element_type>
ostream& operator << (ostream& outs, MySet& source) 
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
{
         int i=0;
         if( source.cardinality() == 0) // Prints blank brackets if set is Empty
             outs << source.setName << " = " << "{ }";
         else
         {     
         outs << source.setName << " = " << "{";
         while( i < source.cardinality()) // Prints in { 1, 2, 3 } format keeping a stray "," from the end
         {
                    
                for( i = 0; i < source.cardinality(); i++)
                {
                     if( (i != (source.cardinality()-1) ))
                     {
                         outs << source.Container[i] << "," ;
                     }
                     else
                     {
                         outs << source.Container[i];
                     }                    
                }        
         }
         outs << "}" ;
         }
         return outs;
} 

template <class element_type>
MySet operator -(MySet &aSet, MySet &bSet)
{
	//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
     MySet diffSet; //creates new Set using values from activated set
     
     if(aSet.cardinality() == 0) // If first parameter is empty, then the difference is the contents of the second set
     {
        for( int m = 0; m < bSet.cardinality(); m++)
         {
              diffSet += bSet.Container[m];
              
         }
     return diffSet;
	 }
	 else if(bSet.cardinality() == 0) // If second parameter is empty, then the difference is the contents of the first set
	 {
		 for( int m = 0; m < aSet.cardinality(); m++)
         {
              diffSet += aSet.Container[m];
              
         }
	return diffSet;
	 }
     else // Finds and returns via a new object of type MySet the difference of the two passed sets
     {
         diffSet = aSet;
         for(int i = 0; i < bSet.cardinality(); i++)
         {
             if(aSet.inSet(bSet.Container[i]))
               diffSet-=bSet.Container[i];
         }

     }
	 return diffSet;
} 

template <class element_type>
MySet operator +(MySet &aSet, MySet &bSet) 
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
{
     assert( (aSet.cardinality() + bSet.cardinality()) <= aSet.maxSetSize);
     MySet addSet; //creates new Set using values from activated set
             
              if ( &aSet == &bSet)
              {
                   for( int m = 0; m < aSet.cardinality(); m++)
                   {
                        addSet += aSet.Container[m];
                        
                   }  // Sets are unique - no copies allowed - a+=a takes no action
					return addSet;
              }
              else
              {
                  addSet = aSet;
                       for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the union of the two passed sets
                        {
                            if(!aSet.inSet(bSet.Container[i]))
                            addSet+=bSet.Container[i];
                        }
                       
				}
      return addSet;         
}             
template <class element_type>
MySet operator *(MySet &aSet, MySet &bSet)
{
     
     
     MySet interSet; 
	 //Postcondition Returns set of type MySet with contents of the intersection between the two passed sets
     
     if(&aSet == &bSet)
     {
        for( int m = 0; m < aSet.cardinality(); m++) // If both passed sets are the same object - the the intersection is the contents of either set
         {
              interSet += aSet.Container[m];
              
         }
		return interSet;
     }
     else
     {
         for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the intersection of the two passed sets
         {
                 if(aSet.inSet(bSet.Container[i]))
                 interSet+=bSet.Container[i];
         }
     }   
     return interSet;
     
}

// FILE: Imp.cpp
#include "MySet.H"
#include <iostream> // used for cin, cout, etc
#include <cstdlib> // used for EXIT_SUCCESS
#include <ctime> // used to seed the random number generator
#include <cassert>
#include <string>

using namespace std;

#define MAX_SET_SIZE 100 // Default maximum set size

//Implementations

// Automatic Copy Constructor
template <class element_type>
MySet::MySet(MySet &secondSet) {
	//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
   Container = new element_type[secondSet.maxSetSize];
   maxSetSize = secondSet.maxSetSize;
   setName = secondSet.setName;
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
}
// assignment operator
template <class element_type>
void MySet::operator = (MySet &secondSet) {
	//Postcondition: Sets activating object equal to the right hand operand of type MySet
   if(this == &secondSet)
      return;
   if(maxSetSize != secondSet.maxSetSize) {
      element_type *newContainer;
      newContainer = new element_type[secondSet.maxSetSize];
      delete [] Container;
      Container = newContainer;
      maxSetSize = secondSet.maxSetSize;
   }
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
   setName = secondSet.setName;
}
template <class element_type>
MySet::MySet()
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
              setSize = 0;
              maxSetSize = MAX_SET_SIZE; 
              Container = new element_type[maxSetSize];  //Creates new empty container of default max size
}

template <class element_type>
MySet::MySet(string label)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = MAX_SET_SIZE;
              Container = new element_type[maxSetSize]; //Creates new empty container of default max size
              setLabel(label);
}

template <class element_type>
MySet::MySet(string label, int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
              setLabel(label);
}

template <class element_type>
MySet::MySet(int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
}

template <class element_type>
MySet::~MySet()
{
	//destructor - reallocates memory
               delete Container;
}

template <class element_type>
int MySet::cardinality(){return(setSize);} //Postcondition - return size of activating set

template <class element_type>
bool MySet::inSet(element_type element) // return true/false based on existence of searched element
{
     //int searchElement;
     for( int i = 0; i < cardinality(); ++i) // Checks if element exists
     {
          if (Container[i] == element)
          {
              return(true);
          }
     }
     return(false);
}

template <class element_type>
bool MySet::isFull()
{
	//Postcondition: Returns true if the activating set has reached its max size
     return(cardinality() == maxSetSize); // returns true if the set size is equal to its max size 
}
template <class element_type>
element_type MySet::getElement(int index) {return (Container[index]);} //returns int value of set at given index

template <class element_type>
void MySet::setLabel(string label) {setName = label;} // Post Condition - sets label for set based on user input - no return

template <class element_type>
void MySet::operator +=(MySet &addedSet) // Post Condition - adds int values of seconds set into activating set - unique values only - no return
{
     
     if ( this == &addedSet)
                 return; // Sets are unique - no copies allowed - a+=a takes no action
     for(int i = 0; i < addedSet.cardinality(); i++) // Adds element into activating object if it doesn't already exist
         {
             if(!inSet(addedSet.Container[i]))
               (*this)+=addedSet.Container[i];
                
         }
}

template <class element_type>
void MySet::operator +=(element_type addedElement) //Postcondition - adds int value into activating set if max size isn't achieved - unique values only
												   // Void- no return
{
     assert( (cardinality() + 1) <= maxSetSize);
     if(isFull())
     cout << endl << "Action can't be completed. Set is full." << endl;
     else
     Container[setSize] = addedElement;
     setSize++;
}

template <class element_type>
void MySet::operator -=(MySet &subSet)
{
	//Postcondition: Subtracts int values from activating set based on passed set, if the values exist - uniques values only - void - no return
     
     for(int i = 0; i < subSet.cardinality(); i++) // Subtracts elements from activating object if values of passed set = those in activator
         {
             if(inSet(subSet.Container[i]))
               (*this)-=subSet.Container[i];
         } 
}    
template <class element_type>
void MySet::operator -=(element_type subElement) // erases one element 
{
	//Postcondition: Subtracts int value from activating set based on passed element, if the value exists - uniques values only - void - no return
     assert( (cardinality() - 1) >= 0);
     int index=0;
     for( int i = 0; i < cardinality(); ++i) 
     {
          if (Container[i] == subElement) // gets index of element to be erased
          {
              index = i;
          }
     }
     
     setSize--;
     for(int i = index; i < setSize; i++) // Moves all data forward if values are subtracted to maintain container continuity
     {
             Container[i] = Container[i + 1];
     }
}


     

//----------- Friends ---------------------------------------------------------------------------------------------  
template <class element_type>
ostream& operator << (ostream& outs, MySet& source) 
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
{
         int i=0;
         if( source.cardinality() == 0) // Prints blank brackets if set is Empty
             outs << source.setName << " = " << "{ }";
         else
         {     
         outs << source.setName << " = " << "{";
         while( i < source.cardinality()) // Prints in { 1, 2, 3 } format keeping a stray "," from the end
         {
                    
                for( i = 0; i < source.cardinality(); i++)
                {
                     if( (i != (source.cardinality()-1) ))
                     {
                         outs << source.Container[i] << "," ;
                     }
                     else
                     {
                         outs << source.Container[i];
                     }                    
                }        
         }
         outs << "}" ;
         }
         return outs;
} 

template <class element_type>
MySet operator -(MySet &aSet, MySet &bSet)
{
	//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
     MySet diffSet; //creates new Set using values from activated set
     
     if(aSet.cardinality() == 0) // If first parameter is empty, then the difference is the contents of the second set
     {
        for( int m = 0; m < bSet.cardinality(); m++)
         {
              diffSet += bSet.Container[m];
              
         }
     return diffSet;
	 }
	 else if(bSet.cardinality() == 0) // If second parameter is empty, then the difference is the contents of the first set
	 {
		 for( int m = 0; m < aSet.cardinality(); m++)
         {
              diffSet += aSet.Container[m];
              
         }
	return diffSet;
	 }
     else // Finds and returns via a new object of type MySet the difference of the two passed sets
     {
         diffSet = aSet;
         for(int i = 0; i < bSet.cardinality(); i++)
         {
             if(aSet.inSet(bSet.Container[i]))
               diffSet-=bSet.Container[i];
         }

     }
	 return diffSet;
} 

template <class element_type>
MySet operator +(MySet &aSet, MySet &bSet) 
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
{
     assert( (aSet.cardinality() + bSet.cardinality()) <= aSet.maxSetSize);
     MySet addSet; //creates new Set using values from activated set
             
              if ( &aSet == &bSet)
              {
                   for( int m = 0; m < aSet.cardinality(); m++)
                   {
                        addSet += aSet.Container[m];
                        
                   }  // Sets are unique - no copies allowed - a+=a takes no action
					return addSet;
              }
              else
              {
                  addSet = aSet;
                       for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the union of the two passed sets
                        {
                            if(!aSet.inSet(bSet.Container[i]))
                            addSet+=bSet.Container[i];
                        }
                       
				}
      return addSet;         
}             
template <class element_type>
MySet operator *(MySet &aSet, MySet &bSet)
{
     
     
     MySet interSet; 
	 //Postcondition Returns set of type MySet with contents of the intersection between the two passed sets
     
     if(&aSet == &bSet)
     {
        for( int m = 0; m < aSet.cardinality(); m++) // If both passed sets are the same object - the the intersection is the contents of either set
         {
              interSet += aSet.Container[m];
              
         }
		return interSet;
     }
     else
     {
         for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the intersection of the two passed sets
         {
                 if(aSet.inSet(bSet.Container[i]))
                 interSet+=bSet.Container[i];
         }
     }   
     return interSet;
     
}

codylee270 · Oct 29th, 2006, 8:17 AM

Anyone?? These 2 files compiled before adding the template stuff.

grumpy · Oct 29th, 2006, 9:06 AM

You've posted more code than I'm interested in wading through, but there's more to making a class into a template class than (in your words) "remove my typedef and put "template <class element_type>" before the class definition and before all the member function implementations".

For example, the implementation of a copy constructor of your class would be like this;

(Toggle Plain Text)

// Automatic Copy Constructor
template <class element_type>
MySet<element_type>::MySet(MySet<element_type>  &secondSet)
{
// the body
}

The same sort of thing needs to be done for all member functions.

A few other comments on things I picked up on a quick skim;

1) With using types/objects/etc from the standard library, it is usually a good idea to fully prefix them in header files with "std::", rather than relying on a "using namespace std;" to be invoked.

2) It is rarely a good idea for an operator=() to return void. Return a reference to your type, and return *this.

3) It is often a very bad idea to test for self-assignment in an operator=() using a test of the form "if (this == &secondSet)". If such a test is necessary, it is almost a given that your code will misbehave or cause resource leaks if an exception is thrown. And one place where exceptions might be thrown in a Set class is when copying or assigning individual elements.

4) When passing arbitrary types as arguments to functions, it is usually better to pass them by const reference rather than by value.

5) I would suggest adding a const qualifier to the argument of the copy constructor; it is very rare that you would want the original changed when making a copy.

codylee270 · Oct 29th, 2006, 2:10 PM

Thanks for your help Grumpy... I've added the <element_type> to other relevant areas as you have posted, but I'm still getting some errors. Here's what they are ( these all are reported inside the implementation file, which i'm sure are cause by header issues):

error C2039: 'operator`+='' : is not a member of 'MySet<element_type>'
error C2039: 'operator`='' : is not a member of 'MySet<element_type>'
error C2039: 'operator`+='' : is not a member of 'MySet<element_type>'
error C2039: 'operator`-='' : is not a member of 'MySet<element_type>'
error C2039: 'operator`-='' : is not a member of 'MySet<element_type>'

Before I go on to tackle some of your other suggestions, I'd like to at least get this part to compile. I simply cannot move onto the actual assignment of making this recursive/backtracking function to insert until then.

So, here is the implementation file that was altered, along with the new header file.

Implementation File:

(Toggle Plain Text)

// FILE: Imp.cpp
#include "MySet.H"
#include <iostream> // used for cin, cout, etc
#include <cstdlib> // used for EXIT_SUCCESS
#include <ctime> // used to seed the random number generator
#include <cassert>
#include <string>

using namespace std;

#define MAX_SET_SIZE 100 // Default maximum set size
// DEFINE element_type


//Implementations

// Automatic Copy Constructor
template <class element_type>
MySet<element_type>::MySet(MySet<element_type> &secondSet) {
	//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
   Container = new element_type[secondSet.maxSetSize];
   maxSetSize = secondSet.maxSetSize;
   setName = secondSet.setName;
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
}
// assignment operator
template <class element_type>
void MySet<element_type>::operator = (MySet<element_type> &secondSet) {
	//Postcondition: Sets activating object equal to the right hand operand of type MySet
   if(this == &secondSet)
      return;
   if(maxSetSize != secondSet.maxSetSize) {
      element_type *newContainer;
      newContainer = new element_type[secondSet.maxSetSize];
      delete [] Container;
      Container = newContainer;
      maxSetSize = secondSet.maxSetSize;
   }
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
   setName = secondSet.setName;
}
template <class element_type>
MySet<element_type>::MySet()
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
              setSize = 0;
              maxSetSize = MAX_SET_SIZE; 
              Container = new element_type[maxSetSize];  //Creates new empty container of default max size
}

template <class element_type>
MySet<element_type>::MySet(string label)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = MAX_SET_SIZE;
              Container = new element_type[maxSetSize]; //Creates new empty container of default max size
              setLabel(label);
}

template <class element_type>
MySet<element_type>::MySet(string label, int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
              setLabel(label);
}

template <class element_type>
MySet<element_type>::MySet(int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
}

template <class element_type>
MySet<element_type>::~MySet()
{
	//destructor - reallocates memory
               delete Container;
}

template <class element_type>
int MySet<element_type>::cardinality(){return(setSize);} //Postcondition - return size of activating set

template <class element_type>
bool MySet<element_type>::inSet(element_type element) // return true/false based on existence of searched element
{
     //int searchElement;
     for( int i = 0; i < cardinality(); ++i) // Checks if element exists
     {
          if (Container[i] == element)
          {
              return(true);
          }
     }
     return(false);
}

template <class element_type>
bool MySet<element_type>::isFull()
{
	//Postcondition: Returns true if the activating set has reached its max size
     return(cardinality() == maxSetSize); // returns true if the set size is equal to its max size 
}
template <class element_type>
element_type MySet<element_type>::getElement(int index) {return (Container[index]);} //returns int value of set at given index

template <class element_type>
void MySet<element_type>::setLabel(string label) {setName = label;} // Post Condition - sets label for set based on user input - no return

template <class element_type>
void MySet<element_type>::operator +=(MySet<element_type> &addedSet) // Post Condition - adds int values of seconds set into activating set - unique values only - no return
{
     
     if ( this == &addedSet)
                 return; // Sets are unique - no copies allowed - a+=a takes no action
     for(int i = 0; i < addedSet.cardinality(); i++) // Adds element into activating object if it doesn't already exist
         {
             if(!inSet(addedSet.Container[i]))
               (*this)+=addedSet.Container[i];
                
         }
}

template <class element_type>
void MySet<element_type>::operator +=(element_type addedElement) //Postcondition - adds int value into activating set if max size isn't achieved - unique values only
												   // Void- no return
{
     assert( (cardinality() + 1) <= maxSetSize);
     if(isFull())
     cout << endl << "Action can't be completed. Set is full." << endl;
     else
     Container[setSize] = addedElement;
     setSize++;
}

template <class element_type>
void MySet<element_type>::operator -=(MySet<element_type> &subSet)
{
	//Postcondition: Subtracts int values from activating set based on passed set, if the values exist - uniques values only - void - no return
     
     for(int i = 0; i < subSet.cardinality(); i++) // Subtracts elements from activating object if values of passed set = those in activator
         {
             if(inSet(subSet.Container[i]))
               (*this)-=subSet.Container[i];
         } 
}    
template <class element_type>
void MySet<element_type>::operator -=(element_type subElement) // erases one element 
{
	//Postcondition: Subtracts int value from activating set based on passed element, if the value exists - uniques values only - void - no return
     assert( (cardinality() - 1) >= 0);
     int index=0;
     for( int i = 0; i < cardinality(); ++i) 
     {
          if (Container[i] == subElement) // gets index of element to be erased
          {
              index = i;
          }
     }
     
     setSize--;
     for(int i = index; i < setSize; i++) // Moves all data forward if values are subtracted to maintain container continuity
     {
             Container[i] = Container[i + 1];
     }
}


     

//----------- Friends ---------------------------------------------------------------------------------------------  
template <class element_type>
ostream& operator << (ostream& outs, MySet<element_type>& source) 
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
{
         int i=0;
         if( source.cardinality() == 0) // Prints blank brackets if set is Empty
             outs << source.setName << " = " << "{ }";
         else
         {     
         outs << source.setName << " = " << "{";
         while( i < source.cardinality()) // Prints in { 1, 2, 3 } format keeping a stray "," from the end
         {
                    
                for( i = 0; i < source.cardinality(); i++)
                {
                     if( (i != (source.cardinality()-1) ))
                     {
                         outs << source.Container[i] << "," ;
                     }
                     else
                     {
                         outs << source.Container[i];
                     }                    
                }        
         }
         outs << "}" ;
         }
         return outs;
} 

template <class element_type>
MySet<element_type> operator -(MySet<element_type> &aSet, MySet<element_type> &bSet)
{
	//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
     MySet diffSet; //creates new Set using values from activated set
     
     if(aSet.cardinality() == 0) // If first parameter is empty, then the difference is the contents of the second set
     {
        for( int m = 0; m < bSet.cardinality(); m++)
         {
              diffSet += bSet.Container[m];
              
         }
     return diffSet;
	 }
	 else if(bSet.cardinality() == 0) // If second parameter is empty, then the difference is the contents of the first set
	 {
		 for( int m = 0; m < aSet.cardinality(); m++)
         {
              diffSet += aSet.Container[m];
              
         }
	return diffSet;
	 }
     else // Finds and returns via a new object of type MySet the difference of the two passed sets
     {
         diffSet = aSet;
         for(int i = 0; i < bSet.cardinality(); i++)
         {
             if(aSet.inSet(bSet.Container[i]))
               diffSet-=bSet.Container[i];
         }

     }
	 return diffSet;
} 

template <class element_type>
MySet<element_type> operator +(MySet<element_type> &aSet, MySet<element_type> &bSet) 
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
{
     assert( (aSet.cardinality() + bSet.cardinality()) <= aSet.maxSetSize);
     MySet<element_type> addSet; //creates new Set using values from activated set
             
              if ( &aSet == &bSet)
              {
                   for( int m = 0; m < aSet.cardinality(); m++)
                   {
                        addSet += aSet.Container[m];
                        
                   }  // Sets are unique - no copies allowed - a+=a takes no action
					return addSet;
              }
              else
              {
                  addSet = aSet;
                       for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the union of the two passed sets
                        {
                            if(!aSet.inSet(bSet.Container[i]))
                            addSet+=bSet.Container[i];
                        }
                       
				}
      return addSet;         
}             
template <class element_type>
MySet<element_type> operator *(MySet<element_type> &aSet, MySet<element_type> &bSet)
{
     
     
     MySet interSet; 
	 //Postcondition Returns set of type MySet with contents of the intersection between the two passed sets
     
     if(&aSet == &bSet)
     {
        for( int m = 0; m < aSet.cardinality(); m++) // If both passed sets are the same object - the the intersection is the contents of either set
         {
              interSet += aSet.Container[m];
              
         }
		return interSet;
     }
     else
     {
         for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the intersection of the two passed sets
         {
                 if(aSet.inSet(bSet.Container[i]))
                 interSet+=bSet.Container[i];
         }
     }   
     return interSet;
     
}

// FILE: Imp.cpp
#include "MySet.H"
#include <iostream> // used for cin, cout, etc
#include <cstdlib> // used for EXIT_SUCCESS
#include <ctime> // used to seed the random number generator
#include <cassert>
#include <string>

using namespace std;

#define MAX_SET_SIZE 100 // Default maximum set size
// DEFINE element_type


//Implementations

// Automatic Copy Constructor
template <class element_type>
MySet<element_type>::MySet(MySet<element_type> &secondSet) {
	//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
   Container = new element_type[secondSet.maxSetSize];
   maxSetSize = secondSet.maxSetSize;
   setName = secondSet.setName;
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
}
// assignment operator
template <class element_type>
void MySet<element_type>::operator = (MySet<element_type> &secondSet) {
	//Postcondition: Sets activating object equal to the right hand operand of type MySet
   if(this == &secondSet)
      return;
   if(maxSetSize != secondSet.maxSetSize) {
      element_type *newContainer;
      newContainer = new element_type[secondSet.maxSetSize];
      delete [] Container;
      Container = newContainer;
      maxSetSize = secondSet.maxSetSize;
   }
   setSize = secondSet.setSize;
   for(int i = 0; i < setSize; i++) {
      Container[i] = secondSet.Container[i];
   }
   setName = secondSet.setName;
}
template <class element_type>
MySet<element_type>::MySet()
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
              setSize = 0;
              maxSetSize = MAX_SET_SIZE; 
              Container = new element_type[maxSetSize];  //Creates new empty container of default max size
}

template <class element_type>
MySet<element_type>::MySet(string label)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = MAX_SET_SIZE;
              Container = new element_type[maxSetSize]; //Creates new empty container of default max size
              setLabel(label);
}

template <class element_type>
MySet<element_type>::MySet(string label, int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
              setLabel(label);
}

template <class element_type>
MySet<element_type>::MySet(int maxSize)
{
	//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container
              setSize = 0;
              maxSetSize = maxSize;
              Container = new element_type[maxSetSize]; //Creates new empty container of user entered max size
}

template <class element_type>
MySet<element_type>::~MySet()
{
	//destructor - reallocates memory
               delete Container;
}

template <class element_type>
int MySet<element_type>::cardinality(){return(setSize);} //Postcondition - return size of activating set

template <class element_type>
bool MySet<element_type>::inSet(element_type element) // return true/false based on existence of searched element
{
     //int searchElement;
     for( int i = 0; i < cardinality(); ++i) // Checks if element exists
     {
          if (Container[i] == element)
          {
              return(true);
          }
     }
     return(false);
}

template <class element_type>
bool MySet<element_type>::isFull()
{
	//Postcondition: Returns true if the activating set has reached its max size
     return(cardinality() == maxSetSize); // returns true if the set size is equal to its max size 
}
template <class element_type>
element_type MySet<element_type>::getElement(int index) {return (Container[index]);} //returns int value of set at given index

template <class element_type>
void MySet<element_type>::setLabel(string label) {setName = label;} // Post Condition - sets label for set based on user input - no return

template <class element_type>
void MySet<element_type>::operator +=(MySet<element_type> &addedSet) // Post Condition - adds int values of seconds set into activating set - unique values only - no return
{
     
     if ( this == &addedSet)
                 return; // Sets are unique - no copies allowed - a+=a takes no action
     for(int i = 0; i < addedSet.cardinality(); i++) // Adds element into activating object if it doesn't already exist
         {
             if(!inSet(addedSet.Container[i]))
               (*this)+=addedSet.Container[i];
                
         }
}

template <class element_type>
void MySet<element_type>::operator +=(element_type addedElement) //Postcondition - adds int value into activating set if max size isn't achieved - unique values only
												   // Void- no return
{
     assert( (cardinality() + 1) <= maxSetSize);
     if(isFull())
     cout << endl << "Action can't be completed. Set is full." << endl;
     else
     Container[setSize] = addedElement;
     setSize++;
}

template <class element_type>
void MySet<element_type>::operator -=(MySet<element_type> &subSet)
{
	//Postcondition: Subtracts int values from activating set based on passed set, if the values exist - uniques values only - void - no return
     
     for(int i = 0; i < subSet.cardinality(); i++) // Subtracts elements from activating object if values of passed set = those in activator
         {
             if(inSet(subSet.Container[i]))
               (*this)-=subSet.Container[i];
         } 
}    
template <class element_type>
void MySet<element_type>::operator -=(element_type subElement) // erases one element 
{
	//Postcondition: Subtracts int value from activating set based on passed element, if the value exists - uniques values only - void - no return
     assert( (cardinality() - 1) >= 0);
     int index=0;
     for( int i = 0; i < cardinality(); ++i) 
     {
          if (Container[i] == subElement) // gets index of element to be erased
          {
              index = i;
          }
     }
     
     setSize--;
     for(int i = index; i < setSize; i++) // Moves all data forward if values are subtracted to maintain container continuity
     {
             Container[i] = Container[i + 1];
     }
}


     

//----------- Friends ---------------------------------------------------------------------------------------------  
template <class element_type>
ostream& operator << (ostream& outs, MySet<element_type>& source) 
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
{
         int i=0;
         if( source.cardinality() == 0) // Prints blank brackets if set is Empty
             outs << source.setName << " = " << "{ }";
         else
         {     
         outs << source.setName << " = " << "{";
         while( i < source.cardinality()) // Prints in { 1, 2, 3 } format keeping a stray "," from the end
         {
                    
                for( i = 0; i < source.cardinality(); i++)
                {
                     if( (i != (source.cardinality()-1) ))
                     {
                         outs << source.Container[i] << "," ;
                     }
                     else
                     {
                         outs << source.Container[i];
                     }                    
                }        
         }
         outs << "}" ;
         }
         return outs;
} 

template <class element_type>
MySet<element_type> operator -(MySet<element_type> &aSet, MySet<element_type> &bSet)
{
	//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
     MySet diffSet; //creates new Set using values from activated set
     
     if(aSet.cardinality() == 0) // If first parameter is empty, then the difference is the contents of the second set
     {
        for( int m = 0; m < bSet.cardinality(); m++)
         {
              diffSet += bSet.Container[m];
              
         }
     return diffSet;
	 }
	 else if(bSet.cardinality() == 0) // If second parameter is empty, then the difference is the contents of the first set
	 {
		 for( int m = 0; m < aSet.cardinality(); m++)
         {
              diffSet += aSet.Container[m];
              
         }
	return diffSet;
	 }
     else // Finds and returns via a new object of type MySet the difference of the two passed sets
     {
         diffSet = aSet;
         for(int i = 0; i < bSet.cardinality(); i++)
         {
             if(aSet.inSet(bSet.Container[i]))
               diffSet-=bSet.Container[i];
         }

     }
	 return diffSet;
} 

template <class element_type>
MySet<element_type> operator +(MySet<element_type> &aSet, MySet<element_type> &bSet) 
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
{
     assert( (aSet.cardinality() + bSet.cardinality()) <= aSet.maxSetSize);
     MySet<element_type> addSet; //creates new Set using values from activated set
             
              if ( &aSet == &bSet)
              {
                   for( int m = 0; m < aSet.cardinality(); m++)
                   {
                        addSet += aSet.Container[m];
                        
                   }  // Sets are unique - no copies allowed - a+=a takes no action
					return addSet;
              }
              else
              {
                  addSet = aSet;
                       for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the union of the two passed sets
                        {
                            if(!aSet.inSet(bSet.Container[i]))
                            addSet+=bSet.Container[i];
                        }
                       
				}
      return addSet;         
}             
template <class element_type>
MySet<element_type> operator *(MySet<element_type> &aSet, MySet<element_type> &bSet)
{
     
     
     MySet interSet; 
	 //Postcondition Returns set of type MySet with contents of the intersection between the two passed sets
     
     if(&aSet == &bSet)
     {
        for( int m = 0; m < aSet.cardinality(); m++) // If both passed sets are the same object - the the intersection is the contents of either set
         {
              interSet += aSet.Container[m];
              
         }
		return interSet;
     }
     else
     {
         for(int i = 0; i < bSet.cardinality(); i++) // Finds and returns via a new object of type MySet the intersection of the two passed sets
         {
                 if(aSet.inSet(bSet.Container[i]))
                 interSet+=bSet.Container[i];
         }
     }   
     return interSet;
     
}

Header:

(Toggle Plain Text)

//FILE: mySet.h
#ifndef MYSET_H
#define MYSET_H

//Cody S. --- CECS 302
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>
using namespace std;

#define MAX_SET_SIZE 100 // Default maximum set size


template <class element_type>
class MySet {
public:
// FIRST, CONSTRUCTOR AND DESTRUCTOR PROTOTYPES
MySet(); //Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
MySet(string label);
//Precondition - Accepts value of type string only
//Postcondition - A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
MySet(string label, int maxSize);
//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
MySet(int maxSize);
MySet(MySet<element_type> &secondSet); // automatic copy constructor
//Precondtion - Accepts object of type Myset
//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
~MySet(); //Postcondition - Reallocates data of container from activating object

// THEN PUBLIC MEMBER FUNCTIONS

int cardinality(); // Postcondition - Returns the set size
bool inSet(element_type element); 
//Precondition - element must be of type element_type
//Postcondition returns true if element is in the set; false otherwise

bool isFull(); // Postcondtion - Returns true if set is full
element_type getElement(int index); 
// Precondition - Accepts integer value only
// Postcondtion - Returns element at position index
void setLabel(string label); 
// Precondtion - Accepts string only
// Postcondition - sets the name of the set


// OVERLOADED OPERATORS AS MEMBER FUNCTIONS -, += (one for
// adding contents of a second set; one for adding single
// element) -=, =
// OVERLOAD FRIEND OPERATORS FOR UNION (+), INTERSECTION (*)
// DIFFERENCE (-) and OUTPUT (<<) AS WELL

void MySet<element_type>::operator +=(MySet<element_type> &addedSet);
//Precondtion - Accepts reference to object type MySet
// Post Condition - adds int values of second set into activating set - unique values only - no return - void
void MySet<element_type>::operator +=(element_type addedElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - adds int value into activating set if max size isn't achieved - unique values only - no return - void
void MySet<element_type>::operator -=(MySet<element_type> &subSet);
//Precondtion - reference to object type MySet
//Postcondition - subtracts int values of second set into activating set - unique values only - no return - void
void MySet<element_type>::operator -=(element_type subElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - subtracts int value into activating set if not empty - unique values only - no return - void
void MySet<element_type>::operator =(MySet<element_type> &secondSet);
//Precondtion - Accepts reference to object type MySet
//Postcondition: Sets activating object equal to the right hand operand of type MySet

//friends

friend ostream& operator << (ostream& outs, MySet<element_type>& source);
//Precondtion - accepts a reference to ostream and a reference to object type MySet
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
friend MySet<element_type> operator -(MySet<element_type> &aSet, MySet<element_type> &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
friend MySet<element_type> operator +(MySet<element_type> &aSet, MySet<element_type> &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
friend MySet<element_type> operator *(MySet<element_type> &aSet, MySet<element_type> &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition - Returns set of type MySet with contents of the intersection between the two passed sets

private:
// PRIVATE DATA MEMBERS AND FUNCTIONS CAN ONLY BE ACCESSED
// WITHIN THE CLASS AND FRIENDS OF THE CLASS


element_type *Container;
int setSize; // number of elements for the set
string setName; // label for the set
int maxSetSize; // maximum number of elements for the set

};
#endif

//FILE: mySet.h
#ifndef MYSET_H
#define MYSET_H

//Cody S. --- CECS 302
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>
using namespace std;

#define MAX_SET_SIZE 100 // Default maximum set size


template <class element_type>
class MySet {
public:
// FIRST, CONSTRUCTOR AND DESTRUCTOR PROTOTYPES
MySet(); //Postcondition: A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, and an empty value container
MySet(string label);
//Precondition - Accepts value of type string only
//Postcondition - A new object of type MySet is created with a set size of 0, and maxsize of the default MAX_SET_SIZE, an empty value container and a label specified
	// by user
MySet(string label, int maxSize);
//Postcondition: A new object of type MySet is created with a set size of 0, and maxsize set by the user, an empty value container and a label specified
	// by user
MySet(int maxSize);
MySet(MySet<element_type> &secondSet); // automatic copy constructor
//Precondtion - Accepts object of type Myset
//Postcondition: A new object of type MySet is created with a copy of the values from the activating object
~MySet(); //Postcondition - Reallocates data of container from activating object

// THEN PUBLIC MEMBER FUNCTIONS

int cardinality(); // Postcondition - Returns the set size
bool inSet(element_type element); 
//Precondition - element must be of type element_type
//Postcondition returns true if element is in the set; false otherwise

bool isFull(); // Postcondtion - Returns true if set is full
element_type getElement(int index); 
// Precondition - Accepts integer value only
// Postcondtion - Returns element at position index
void setLabel(string label); 
// Precondtion - Accepts string only
// Postcondition - sets the name of the set


// OVERLOADED OPERATORS AS MEMBER FUNCTIONS -, += (one for
// adding contents of a second set; one for adding single
// element) -=, =
// OVERLOAD FRIEND OPERATORS FOR UNION (+), INTERSECTION (*)
// DIFFERENCE (-) and OUTPUT (<<) AS WELL

void MySet<element_type>::operator +=(MySet<element_type> &addedSet);
//Precondtion - Accepts reference to object type MySet
// Post Condition - adds int values of second set into activating set - unique values only - no return - void
void MySet<element_type>::operator +=(element_type addedElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - adds int value into activating set if max size isn't achieved - unique values only - no return - void
void MySet<element_type>::operator -=(MySet<element_type> &subSet);
//Precondtion - reference to object type MySet
//Postcondition - subtracts int values of second set into activating set - unique values only - no return - void
void MySet<element_type>::operator -=(element_type subElement);
//Precondtion - Accepts only value of type element_type
//Postcondition - subtracts int value into activating set if not empty - unique values only - no return - void
void MySet<element_type>::operator =(MySet<element_type> &secondSet);
//Precondtion - Accepts reference to object type MySet
//Postcondition: Sets activating object equal to the right hand operand of type MySet

//friends

friend ostream& operator << (ostream& outs, MySet<element_type>& source);
//Precondtion - accepts a reference to ostream and a reference to object type MySet
// Postcondition - prints all values of activator in {1,2,3} format - prints { } if no values exist in set, void - no return
friend MySet<element_type> operator -(MySet<element_type> &aSet, MySet<element_type> &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the difference between the two passed sets
friend MySet<element_type> operator +(MySet<element_type> &aSet, MySet<element_type> &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition: Returns set of type MySet with contents of the union between the two passed sets
friend MySet<element_type> operator *(MySet<element_type> &aSet, MySet<element_type> &bSet);
//Precondtion - Accepts reference to two objects of type MySet
//Postcondition - Returns set of type MySet with contents of the intersection between the two passed sets

private:
// PRIVATE DATA MEMBERS AND FUNCTIONS CAN ONLY BE ACCESSED
// WITHIN THE CLASS AND FRIENDS OF THE CLASS


element_type *Container;
int setSize; // number of elements for the set
string setName; // label for the set
int maxSetSize; // maximum number of elements for the set

};
#endif

THANK YOU!!!!

grumpy · Oct 30th, 2006, 4:20 AM

Within the class declaration, you do not need to fully qualify names of operators. For example, in this;

(Toggle Plain Text)

template <class element_type>
class MySet
{
     // other stuff
    void MySet<element_type>::operator +=(MySet<element_type> &addedSet);
};

the bits highlighted in red will upset your compiler. In exactly the same way as

(Toggle Plain Text)

class X
{
     void X::operator+=(const X &);
}

would.

Oct 27th, 2006, 12:03 PM	#1
codylee270 Unverified User Join Date: Sep 2005 Posts: 209 Rep Power: 0	Need help starting a recsursive/backtracking function Here is the code to my next programming project. (Toggle Plain Text) The subset sum problem is stated as follows: Given a set of positive integers, S, and a positive integer, L, find all of the subsets of the set S such that the sum of all of the elements in the subset is equal to L. For example, consider the set S = {11, 5, 9, 14, 6} and L = 11. The solution to the subset sum problem is: S1 = {11}; S2 = {5, 6} since the sum of all of the elements of S1 = 11, and the sum of all of the elements of S2 = 5+6 = 11. Solutions to other subset sum problems include: S = {1, 3, 11, 13}; L = 1 S1 = {1} S = {4, 7, 10, 14, 20}; L = 12 S1 = {} S = {3, 6, 9, 12, 15}; L = 15 S1 = {3, 12} S2 = {6, 9} S2 = {15} The subset sum belongs to a set of algorithms that are NP-complete, meaning that they cannot be solved in polynomial time. One method to solve the subset sum problem is through the use of backtracking. What we will do in this case is examine all of the possible subsets, Si, of a particular set S. Note that for a set of length L, there are 2L possible subsets. For instance if S = {1, 2, 3}, the possible subsets are {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} and the empty set {}. All of the possible subsets of a set can be generated by creating a vector of Boolean values of length L, where position Li is true if the element at position i of the set S is included in the subset, and false otherwise. For your second programming project, there are four main additions: 1) Change your sets to incorporate templates, so you can have sets of different types. 2) Create a public member function findSubsetSum which reads in an integer L and prints out all of the subsets of the current set instance where the sum of the subsets is equal to L. findSubsetSum will create the initial call to the private member function recurseSubsetSum. 3) Create a private member function recurseSubsetSum which will examine all of the possible subsets of the current set instance, and if the sum of the elements is in the subset, it will print them out. 4) Create five test cases for the subset sum problem, and code these into file newUseSets.cpp, which is given below. To help you out, the pseudocode for the findSubsetSum and recurseSubsetSum functions is given below: function findSubsetSum (sumToFind) { create a Boolean array of the length of the set initialize all of the values to false call recurseSubsetSum, passing the Boolean array, the sum to find, the current index pointing to the beginning of the set, and the current sum of the subset equal to zero return } function recurseSubsetSum(booleanArray, sumToFind, currentPosition, currentSum) { if(the currentPosition is at the end of the set) if(currentSum is the sumToFind) print out the subset (which is also a set!!!) else current subset is not a solution (do nothing) else include the next element in the set in the subset add the next element to the current sum recursively call recurseSebsetSum, with the currentPosition incremented // NOW BACKTRACK remove next element from the subset subtract next element from the current sum recursively call recurseSubsetSum } } The file newUseset.cpp that needs to be modified with your test cases and with the addition of templates is: #include "MySet.H" #include <iostream> // used for cin, cout, etc #include <cstdlib> // used for EXIT_SUCCESS #include <ctime> // used to seed the random number generator using namespace std; int main() { srand((unsigned)time(0)); // Seed the random number generator MySet OrigSet("Original Set"); // RANDOMLY PICK 25 numbers for the set between 0 and 1000 for(int i = 0; i < 20; i++) { int randNum = 1 + (int)(20.0 * (rand()/(RAND_MAX + 1.0))); OrigSet += randNum; } int subsetSum = 1 + (int)(30.0 * (rand()/(RAND_MAX + 1.0))); cout << "The orginal set is "; cout << OrigSet << endl; cout << "The subset sum to find is: "<< subsetSum << endl; OrigSet.findSubsetSum(subsetSum); MySet TestSet("TEST SET"); TestSet += 1; TestSet += 2; TestSet += 3; TestSet += 4; int testSum = 5; cout << "The Test set is " << TestSet << endl; cout << "The subset sum to find is: " << testSum << endl; cout << "Expected solution: {1, 4}; {2,3}" << endl; TestSet.findSubsetSum(testSum); return EXIT_SUCCESS; } A sample output for this program is: The orginal set is Original Set = {11, 16, 2, 17, 10, 8, 18, 6, 4, 7, 15, 19, 20} The subset sum to find is: 13 SUBSETSUM = {11, 2} SUBSETSUM = {2, 4, 7} SUBSETSUM = {6, 7} The Test set is TEST SET = {1, 2, 3, 4} The subset sum to find is: 5 Expected solution: {1, 4}; {2,3} SUBSETSUM = {1, 4} SUBSETSUM = {2, 3} The subset sum problem is stated as follows: Given a set of positive integers, S, and a positive integer, L, find all of the subsets of the set S such that the sum of all of the elements in the subset is equal to L. For example, consider the set S = {11, 5, 9, 14, 6} and L = 11. The solution to the subset sum problem is: S1 = {11}; S2 = {5, 6} since the sum of all of the elements of S1 = 11, and the sum of all of the elements of S2 = 5+6 = 11. Solutions to other subset sum problems include: S = {1, 3, 11, 13}; L = 1 S1 = {1} S = {4, 7, 10, 14, 20}; L = 12 S1 = {} S = {3, 6, 9, 12, 15}; L = 15 S1 = {3, 12} S2 = {6, 9} S2 = {15} The subset sum belongs to a set of algorithms that are NP-complete, meaning that they cannot be solved in polynomial time. One method to solve the subset sum problem is through the use of backtracking. What we will do in this case is examine all of the possible subsets, Si, of a particular set S. Note that for a set of length L, there are 2L possible subsets. For instance if S = {1, 2, 3}, the possible subsets are {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} and the empty set {}. All of the possible subsets of a set can be generated by creating a vector of Boolean values of length L, where position Li is true if the element at position i of the set S is included in the subset, and false otherwise. For your second programming project, there are four main additions: 1) Change your sets to incorporate templates, so you can have sets of different types. 2) Create a public member function findSubsetSum which reads in an integer L and prints out all of the subsets of the current set instance where the sum of the subsets is equal to L. findSubsetSum will create the initial call to the private member function recurseSubsetSum. 3) Create a private member function recurseSubsetSum which will examine all of the possible subsets of the current set instance, and if the sum of the elements is in the subset, it will print them out. 4) Create five test cases for the subset sum problem, and code these into file newUseSets.cpp, which is given below. To help you out, the pseudocode for the findSubsetSum and recurseSubsetSum functions is given below: function findSubsetSum (sumToFind) { create a Boolean array of the length of the set initialize all of the values to false call recurseSubsetSum, passing the Boolean array, the sum to find, the current index pointing to the beginning of the set, and the current sum of the subset equal to zero return } function recurseSubsetSum(booleanArray, sumToFind, currentPosition, currentSum) { if(the currentPosition is at the end of the set) if(currentSum is the sumToFind) print out the subset (which is also a set!!!) else current subset is not a solution (do nothing) else include the next element in the set in the subset add the next element to the current sum recursively call recurseSebsetSum, with the currentPosition incremented // NOW BACKTRACK remove next element from the subset subtract next element from the current sum recursively call recurseSubsetSum } } The file newUseset.cpp that needs to be modified with your test cases and with the addition of templates is: #include "MySet.H" #include <iostream> // used for cin, cout, etc #include <cstdlib> // used for EXIT_SUCCESS #include <ctime> // used to seed the random number generator using namespace std; int main() { srand((unsigned)time(0)); // Seed the random number generator MySet OrigSet("Original Set"); // RANDOMLY PICK 25 numbers for the set between 0 and 1000 for(int i = 0; i < 20; i++) { int randNum = 1 + (int)(20.0 * (rand()/(RAND_MAX + 1.0))); OrigSet += randNum; } int subsetSum = 1 + (int)(30.0 * (rand()/(RAND_MAX + 1.0))); cout << "The orginal set is "; cout << OrigSet << endl; cout << "The subset sum to find is: "<< subsetSum << endl; OrigSet.findSubsetSum(subsetSum); MySet TestSet("TEST SET"); TestSet += 1; TestSet += 2; TestSet += 3; TestSet += 4; int testSum = 5; cout << "The Test set is " << TestSet << endl; cout << "The subset sum to find is: " << testSum << endl; cout << "Expected solution: {1, 4}; {2,3}" << endl; TestSet.findSubsetSum(testSum); return EXIT_SUCCESS; } A sample output for this program is: The orginal set is Original Set = {11, 16, 2, 17, 10, 8, 18, 6, 4, 7, 15, 19, 20} The subset sum to find is: 13 SUBSETSUM = {11, 2} SUBSETSUM = {2, 4, 7} SUBSETSUM = {6, 7} The Test set is TEST SET = {1, 2, 3, 4} The subset sum to find is: 5 Expected solution: {1, 4}; {2,3} SUBSETSUM = {1, 4} SUBSETSUM = {2, 3} I can change the actual program that is being added into to use templates just fine, but I am confused with the following: 1) What the vector of boolean values has to do with anything. The pseudocode for the recursive function really doesn't mention the vector, conveniently enough. 2) What's happening with: // NOW BACKTRACK remove next element from the subset subtract next element from the current sum recursively call recurseSubsetSum Where would the next element be? From the if/elses before this backtracking part, it looks like it searches the entire set that was originally used to invoke the findSubsetSum member function. Then it starts the backtracking and removing of elements created using the recursice function. Any ideas? I still don't understand the usage of the vector required. If anyone can help get started on this, I will greatly appreciate it. Thanks!

Oct 27th, 2006, 2:24 PM	#3
codylee270 Unverified User Join Date: Sep 2005 Posts: 209 Rep Power: 0	since no actual numeric values are stored in the boolen vector, what exactly does this boolen array do for us in this situation? B/c the in the pseudocode it sometimes says to printout the subset, which of course is going to be a numeric value that adds up to a certain number, not true/false. When findSubset asks to pass the current index pointing to be beginning of the set, is it asking for the index of the beginning of the MySet object that invoked it or the beginning index of the boolean vector? And since this boolean array is given a set length at the beginning and all value initialized to false, does it have to be a vector? Finally ( for this post at least) - this function will be void, correct? Last edited by codylee270; Oct 27th, 2006 at 2:38 PM.

Oct 29th, 2006, 9:06 AM	#7
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,260 Rep Power: 5	You've posted more code than I'm interested in wading through, but there's more to making a class into a template class than (in your words) "remove my typedef and put "template <class element_type>" before the class definition and before all the member function implementations". For example, the implementation of a copy constructor of your class would be like this; (Toggle Plain Text) // Automatic Copy Constructor template <class element_type> MySet<element_type>::MySet(MySet<element_type> &secondSet) { // the body } // Automatic Copy Constructor template <class element_type> MySet<element_type>::MySet(MySet<element_type> &secondSet) { // the body } The same sort of thing needs to be done for all member functions. A few other comments on things I picked up on a quick skim; 1) With using types/objects/etc from the standard library, it is usually a good idea to fully prefix them in header files with "std::", rather than relying on a "using namespace std;" to be invoked. 2) It is rarely a good idea for an operator=() to return void. Return a reference to your type, and return *this. 3) It is often a very bad idea to test for self-assignment in an operator=() using a test of the form "if (this == &secondSet)". If such a test is necessary, it is almost a given that your code will misbehave or cause resource leaks if an exception is thrown. And one place where exceptions might be thrown in a Set class is when copying or assigning individual elements. 4) When passing arbitrary types as arguments to functions, it is usually better to pass them by const reference rather than by value. 5) I would suggest adding a const qualifier to the argument of the copy constructor; it is very rare that you would want the original changed when making a copy.

Oct 30th, 2006, 4:20 AM	#9
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,260 Rep Power: 5	Within the class declaration, you do not need to fully qualify names of operators. For example, in this; (Toggle Plain Text) template <class element_type> class MySet { // other stuff void MySet<element_type>::operator +=(MySet<element_type> &addedSet); }; template <class element_type> class MySet { // other stuff void MySet<element_type>::operator +=(MySet<element_type> &addedSet); }; the bits highlighted in red will upset your compiler. In exactly the same way as (Toggle Plain Text) class X { void X::operator+=(const X &); } class X { void X::operator+=(const X &); } would.

Oct 27th, 2006, 12:17 PM	#2
The Dark Expert Programmer Join Date: Jun 2005 Posts: 894 Rep Power: 4	1. the subset is stored in the boolean array, so whenever the pseudo code says "subset", it means the boolean array. The array indicates which values of the set are in the subset. 2. The "next element" is the element at currentPosition, so to remove that element from the subset, you just set the boolean array element at currentPosition to false.

Oct 27th, 2006, 7:18 PM	#4
The Dark Expert Programmer Join Date: Jun 2005 Posts: 894 Rep Power: 4	You use the boolean vector to determine which of the values in the set vector are in the subset. When you want to print the subset, loop through the boolean vector and the set vector in step and print out any entry in the set vector that has a corresponding true in the boolean vector. Both. The currentIndex passed in is an integer, which is the position in both the set vector and the boolean vector. The only reason the boolean array has to be a vector, is because the assignment specifies that it is. a vector is probably easier to manage anyway, but a array allocated with new wold work just as well. It doesn't seem to need to return anything, so it might as well be void.

Oct 29th, 2006, 8:17 AM	#6
codylee270 Unverified User Join Date: Sep 2005 Posts: 209 Rep Power: 0	Anyone?? These 2 files compiled before adding the template stuff.

Programming Forums > Application Development > C++

Need help starting a recsursive/backtracking function