Fall 2000 PIC 10b HW2 Solutions Page

Return to homework page.

//
// File: pic10bhw2file1.h
//
// Contents: Contains interface for Set class.
//
//


#ifndef SET_H
#define SET_H

#include<iostream.h>


// Class name: Set
//
// Purpose: Serves as a container for an unordered collection of int's
//          int's are stored in a dynamically size array
//          but == compares set only on whether the two sets store
//          the same int's but does not care about number of copies
//
// Remark: Set's internally may store multiple copies of same elt.
//           
//
//
// Known Bugs: none 

class Set
{
    public:
	Set(); // constructor. array set to be a new array of ints of size 10
               // curSize is set to 0; maxSize set to 10

	Set(int s);// constructor. array set to be a new array of 
                   // ints of size 10
                   // curSize is set to 0; maxSize set to 10

	Set(const Set& s); //constructor. copies s into current object

	~Set();	 //destructor should free up memory in *array

	Set& operator=(const Set& v);  //uses this pointer to check if
                                    //v is current object. If it is
                                    //return current object. Otherwise,
                                    //set up current object as in v and
                                    //return current object.
                                    //member function not friend!

	Set& operator+=(int elt); // adds elt to current Set using same
                   // algorithm for resizing array as stated above
                  //returns reference of current set.
                  //Only does copying when need to resize.

	friend bool operator==(const Set& s1, const Set& s2);
              // tests if two Sets are the same.
              // They are the same if have same elements.
              // It doesn't matter if they have same number of
              // copies of a given element. i.e., {1,2} and {1,2,1}
              // are same.



	friend Set& operator+(const Set& s, int m); //returns the Set that 
					//results from adding m to s.

	friend Set& operator+(int m, const Set& s); //does same as previous

	bool element(int i); //checks if the integer i has been stored in the 
                             // Set. returns true if it has; false otherwise.

	friend ostream& operator<<(ostream& out, const Set& s);
                                     //prints each element to ostream&
                                     //separated by a return

	friend istream& operator>>(istream& in, Set& s);
                                     //reads one integer element 
                                     //and stores it into set s using
                                     //+ operator.

    private:

	int *array; // stores user data 
	int curSize; // storage space used
	int maxSize; // current total storage space.

};
#endif

//
// File: pic10bhw2file2.cpp
//
// Contents: Contains implementation for Set class.
//
//

#include<iostream.h>
#include<stddef.h>
#include<stdlib.h>
#include "pic10bhw2file1.h"

//
//Global constants
//

static const int DEFAULT_SIZE = 10; //used in default Set constructor

// Function name: allocate(int , int)
//
// Purpose: allocate an array of size many int's.  
//          if fails outputs error number e.          
//
// Known Bugs: none

int* allocate(int size, int e)
{
	int *tmp = new int[size];

	if(tmp == NULL)
	{
	    cout <<  "memory allocation error Set" <<  e << endl;
	    exit(1);
	}

	return tmp;
}

// Method name: Set()
//
// Purpose: Default constructor. Initializes the internally held array to
//          DEFAULT_SIZE 
// Known Bugs: none

Set::Set()
{
	array = allocate(DEFAULT_SIZE, 0);
	curSize =0;
	maxSize = DEFAULT_SIZE;

}

// Method name: Set(int s)
//
// Purpose: Initializes the internally held array to
//          the size specified in s. 
// Known Bugs: none

Set::Set(int s)
{
	array = allocate(s, 0);
	curSize =0;
	maxSize =s;

}

// Method name: Set(const Set& v)
//
// Purpose: Copy constructor. copies v into current object
// 
// Known Bugs: none

Set::Set(const Set& v)
{
	(*this) = v;	

}

// Method name: ~Set()
//
// Purpose: Destructor. Frees up the memory srote in array.
// 
// Known Bugs: none

Set::~Set()
{
	delete [] array;
}

// Method name: =
//
// Purpose: copies v into current Set object.
// 
// Known Bugs: none

Set& Set::operator=(const Set& v)
{


	if (this == &v)
	 	return *this;
	
	delete [] array;

	array = allocate(v.maxSize,5);
	maxSize = v.maxSize;
	curSize = v.curSize;

	for(int i=0; i< curSize; i++)
		array[i]=v.array[i];
	
	return *this;
}

// Function name: ==
//
// Purpose: checks is s1 and s2 contain the same elements. Doesn't care about
//          if they have the same number of repititions of an element.
// 
// Known Bugs: none

bool operator==(const Set& s1, const Set& s2)
{
	Set tmp1(s1), tmp2(s2); // wasteful but works
                                // cannot use element of s1 and s2
                                // since could potentially go against const
                                // modifier. 
	int i;
   
	//need to check tmp1 subset of tmp2 and tmp2 subset of tmp1.

	for(i=0; i< tmp1.curSize; i++)
		if(!tmp2.element(tmp1.array[i])) return false;

	for(i=0; i< tmp2.curSize; i++)
		if(!tmp1.element(tmp2.array[i])) return false;

	return true;
	
}

// Member name: +=
//
// Purpose: Adds the element m to the current set resizing only when
//          necessary. When resizes though allocates twice as much memory.
// 
// Known Bugs: none

Set& Set::operator+=(int m)
{
	int* tmp;

	if(curSize == maxSize) 
	{
		maxSize*=2; 

		tmp=allocate(maxSize,3);

		for(int i=0; i< curSize;i++)
			tmp[i]=array[i];

		delete [] array;

		array=tmp;

 	}

	array[curSize++]=m;	

	return *this;
}

// Function name: +
//
// Purpose: creates a new Set object which results from copying s into a new
//          Set then adding m to the end of the array of this new Set.
// 
// Known Bugs: none

Set& operator+(const Set& s, int m)
{
	Set *tmp = new Set(s);

	(*tmp) += m;

	return *tmp;
}

// Function name: +
//
// Purpose: same as previous + overload
// 
// Known Bugs: none

Set& operator+(int m, const Set& s)
{

	return s+m;
}

// Method name: element
//
// Purpose: returns true if i is contained in the array of the current Set
//          object 
// Known Bugs: none

bool Set::element(int i)
{
	for(int j=0; j <  curSize; j++)	
		if(array[j]== i) return true;

	return false;		
}

// Function name: <<
//
// Purpose: writes the set out to the current output stream. Each element of
//          the set is written to a different line.
// 
// Known Bugs: none

ostream& operator<< (ostream& out, const Set& s)
{
	for(int i =0; i< s.curSize; i++)
		out <<  s.array[i] << endl;

	return out; 
}

// Function name: >>
//
// Purpose: reads one integer into the current Set object.
// 
// Known Bugs: none

istream& operator>>(istream& in, Set& s)
{
	int input;

	in >> input;

	s += input;

	return in;
}


//
// File: pic10bhw2file3.cpp
//
// Contents: Contains Driver program to test Set class.
//
//

#include "pic10bhw2file1.h"
#include <iostream.h>

// Function name: main()
//
// Purpose: Used to test operations of the set class
// 
// Known Bugs: none

int main()
{
	Set *s1, *s2;

	//some practice at dynamically allocating objects.

	s1 = new Set(); //test default constructor.
	s2 = new Set(1); //test second constructor.

	(*s1) = (*s2) + 1; //test +,= overload, copy constructor

	(*s1) = (*s1); //test equals again

	(*s2) = 2+(*s1); //test other form of +


	if(s1->element(2)) // test element() and how things are stored
		cout << "2 was an element of s1\n";
	else 
		cout << "2 was not an element of s1\n";

	if(s2->element(2)) // test element() and how things are stored again
		cout << "2 was an element of s2\n";
	else 
		cout << "2 was not an element of s2\n";

	//Now test insertion and extraction operators.

	cout << "Please enter a number:";
	cin >> *s2;

	cout << *s2;
	

	//free up memory and we're done.

	delete s1;
	delete s2;

	return 0;
}