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;
}
|