Set Class First, combine the two into one set by overloading the + (union) opera
ID: 3742957 • Letter: S
Question
Set Class
First, combine the two into one set by overloading the + (union) operator, and print out the union set. The + operator must remove all duplicates from the result and store one copy of any item. You also need to implement a subtraction operator (difference) where (A-B means removing all elements that are in B from A) an. If the item is in B but not A, it is not placed in the result) Then remove the duplicates from the result. So the main function takes two sets of integers and print the result of + and - operation.
You can either add the + and - operators to the ArrayBag (suggested for most students), or you can add a Set class as a friend to ArrayBag (friend class Set; Then define a class Set in a .h and associated .cpp)
After validating, instead of putting them into a vector, you will add them to a "Set" (ArrayBag) to meet this homework's requirement.
You should submit a single lastnameHW2.zip containing: ArrayBag.h, ArrayBag.cpp, main.cpp, SetFunctions.h, SetFunctions.cpp, makefile, and Readme.txt and setInput.txt.
Extra Credit (up to 4 pts, must note in your readme.txt): Validate that all inputs are integers in a function inside SetFunctions.h and SetFunctions.cpp. Anything else should be rejected with an error message. See validateInput.cpp for an idea of how to validate input. Include a setInputA.txt demonstrating invalid input.
ArrayBag.h
/** ADT bag: Array-based implementation.
@file ArrayBag.h */
#ifndef BAG_
#define BAG_
#include <vector>
typedef int ItemType;
class ArrayBag
{
private:
static const int DEFAULT_BAG_SIZE = 100;
ItemType items[DEFAULT_BAG_SIZE]; // array of bag items
int itemCount; // current count of bag items
int maxItems; // max capacity of the bag
// Returns either the index of the element in the array items that
// contains the given target or -1, if the array does not contain
// the target.
int getIndexOf(const ItemType& target) const;
public:
ArrayBag();
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
}; // end Bag
#endif
ArrayBag.cpp
/** ADT bag: Array-based implementation.
@file ArrayBag.h */
#ifndef BAG_
#define BAG_
#include <vector>
typedef int ItemType;
class ArrayBag
{
private:
static const int DEFAULT_BAG_SIZE = 100;
ItemType items[DEFAULT_BAG_SIZE]; // array of bag items
int itemCount; // current count of bag items
int maxItems; // max capacity of the bag
// Returns either the index of the element in the array items that
// contains the given target or -1, if the array does not contain
// the target.
int getIndexOf(const ItemType& target) const;
public:
ArrayBag();
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
}; // end Bag
#endif
validateInput.cpp
#include <iostream> //cout, cin
#include <sstream> //stringstream
#include <string>
#include <fstream> //ifstream
#include <vector>
using namespace std;
/*Pre: Input a file stream and a vector of integers that were read in from
the file
Post: True if all input in vector are ints
Desc: validates that all items in vector are ints
*/
bool getIntsFromFile(ifstream &infile, vector<int> &vec )
//istream accepts from cin or file as a parent class
{
stringstream ss;
int tempInt;
string readString;
getline(infile, readString);
ss << readString; //Write readString into ss
while (!ss.eof()) //Until end of stream
{
ss >> tempInt; //Read in an int from ss into tempInt
if (ss.fail()) //If it fails to to read an int data type
{
cout << "Input contains non-integer data ";
ss.clear(); //Clears state of string stream;
return false;
}
vec.push_back(tempInt); //Add to the vector
}
return true;
}
/*Desc: Prints out all values in a vector
Pre: Reads in a vector
Post: void
*/
void printValues(vector<int> set)
{
for (int i = 0; i < set.size(); i++)
{
cout << set[i] << " ";
}
cout << endl;
}
int main()
{
ifstream infile("setInput.txt");
vector<int> vec1, vec2;
if ( getIntsFromFile(infile, vec1) )
printValues(vec1);
cout << endl;
if ( getIntsFromFile(infile, vec2) )
printValues(vec2);
return 0;
}
Chapter 1, Exercise 6
The union of two bags is a new bag containing the combined contents of the original two bags. Design and specify a method union for the ADT bag that returns as a new bag the union of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method.
Note that the union of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the union of these bags contains x seven times. Specifically, suppose that bag1 and bag2 are bags; bag1 contains the strings a, b, c; and bag2 contains the strings b, b, d, and e. The expression bag1.union(bag2) returns a bag containing the strings a, b, b, b, c, d, and e. Note that union does not affect the contents of bag1 and bag2.
Chapter 1, Exercise 8
The difference of two bags is a new bag containing the entries that would be left in one bag after removing those that occur in a second. Design and specify a method difference for the ADT bag that returns as a new bag the difference of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method.
Note that the difference of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the difference of these bags contains x three times. Specifically, suppose that bag1 and bag2 are bags; bag1 contains the strings a, b, and c; and bag2 contains the strings b, b, d, and e. The expression bag1.difference(bag2) returns a bag containing only the strings a and c. Note that difference does not affect the contents of bag1 and bag2.
Explanation / Answer
ArrayBbag.cpp
#include "ArrayBag.h"
ArrayBag::ArrayBag() : itemCount(0), maxItems(DEFAULT_BAG_SIZE) {
} // end default constructor
int ArrayBag::getCurrentSize() const {
return itemCount;
} // end getCurrentSize
bool ArrayBag::isEmpty() const {
return itemCount == 0;
} // end isEmpty
bool ArrayBag::add(const ItemType &newEntry) {
bool hasRoomToAdd = (itemCount < maxItems);
if (hasRoomToAdd) {
items[itemCount] = newEntry;
itemCount++;
} // end if
return hasRoomToAdd;
} // end add
bool ArrayBag::remove(const ItemType &anEntry) {
int locatedIndex = getIndexOf(anEntry);
bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
if (canRemoveItem) {
itemCount--;
items[locatedIndex] = items[itemCount];
} // end if
return canRemoveItem;
} // end remove
void ArrayBag::clear() {
itemCount = 0;
} // end clear
int ArrayBag::getFrequencyOf(const ItemType &anEntry) const {
int frequency = 0;
int searchIndex = 0;
while (searchIndex < itemCount) {
if (items[searchIndex] == anEntry) {
frequency++;
} // end if
searchIndex++;
} // end while
return frequency;
} // end getFrequencyOf
bool ArrayBag::contains(const ItemType &anEntry) const {
return getIndexOf(anEntry) > -1;
} // end contains
// private
int ArrayBag::getIndexOf(const ItemType &target) const {
bool found = false;
int result = -1;
int searchIndex = 0;
// if the ArrayBag is empty, itemCount is zero, so loop is skipped
while (!found && (searchIndex < itemCount)) {
if (items[searchIndex] == target) {
found = true;
result = searchIndex;
} else {
searchIndex++;
} // end if
} // end while
return result;
} // end getIndexOf
ArrayBag.h
#ifndef BAG_
#define BAG_
#include <vector>
typedef int ItemType;
class ArrayBag {
private:
static const int DEFAULT_BAG_SIZE = 100;
ItemType items[DEFAULT_BAG_SIZE]; // array of bag items
int itemCount; // current count of bag items
int maxItems; // max capacity of the bag
// Returns either the index of the element in the array items that
// contains the given target or -1, if the array does not contain
// the target.
int getIndexOf(const ItemType &target) const;
public:
ArrayBag();
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType &newEntry);
bool remove(const ItemType &anEntry);
void clear();
bool contains(const ItemType &anEntry) const;
int getFrequencyOf(const ItemType &anEntry) const;
}; // end Bag
#endif
SetFunctions.cpp
#include "SetFunctions.h"
bool Set::add(const int &newEntry) {
//Return false without inserting element if the element is already in the parent's array bag
if (this->getFrequencyOf(newEntry) > 0) return false;
//Call the superclass to perform the insert
return ArrayBag::add(newEntry);
}
istream& operator>>(istream &in, Set &set) {
//Read one line from the input stream and create an istringstream for it
string line;
getline(in, line);
istringstream is(line);
//Read all whitespace-delimited "word" from the line we read
// try to parse it to an int; if there's an error doing that,
// throw our own error to meet the validation requirement for
// the extra credit on this assignment
string word;
while (is >> word) {
try {
//try to parse the string
// if it fails, the string isn't a valid
// integer, and we need to throw our own error
int i = stoi(word);
set.add(i);
} catch (const invalid_argument& e) {
// fullfill validation requirement by catching the invalid_argument error
// and throwing our own error
throw runtime_error("error parsing set from input stream; malformed/non-int word found in input stream");
}
}
//Return the input stream
return in;
}
ostream& operator<<(ostream &out, Set &set) {
//Keep track of how many elements we printed
unsigned int outputCount = 0;
//Check all positive and nexative numbers from [0-max int]
// If a number is in the set, print it and increment outputCount
// If we manage to guess all the numbers in the set, break the loop so we
// don't have to check the rest of the possible integers.
for (int i = 0; (i < numeric_limits<int>::max() && outputCount < set.getCurrentSize()); i++) {
if (set.contains(i)) {
const unsigned int count = set.getFrequencyOf(i);
for (unsigned int j = 0; j<count; j++) {
out << i << ' ';
outputCount++;
}
}
if (set.contains(-i)) {
const unsigned int count = set.getFrequencyOf(-i);
for (unsigned int j = 0; j<count; j++) {
out << -i << ' ';
outputCount++;
}
}
}
return out;
}
Set operator+(Set &a, Set &b) {
//Instatiate a new set c
Set c;
//Keep track of the total number of elements and the number of elements we have checked
const unsigned int totalElementCount = a.getCurrentSize() + b.getCurrentSize();
unsigned int comparedElementCount = 0;
for (int i = 0; (i < numeric_limits<int>::max())&&(comparedElementCount<totalElementCount); i++) {
unsigned int freq = a.getFrequencyOf(i) + b.getFrequencyOf(i);
comparedElementCount += freq;
if (freq>0) c.add(i);
unsigned int freqNeg = a.getFrequencyOf(-i) + b.getFrequencyOf(-i);
comparedElementCount += freqNeg;
if (freqNeg>0) c.add(-i);
}
//Return set c by value
return c;
}
Set operator-(Set &a, Set &b) {
//Instantiate set c to track the result
Set c;
//Keep track of the total number of elements and the number of elements we have checked
const unsigned int totalElementCount = a.getCurrentSize() + b.getCurrentSize();
unsigned int comparedElementCount = 0;
//Check all positive and negative integers to see if they're in the set
// if we manage to check all of the integers in the set, break the loop
// so that we don't bother with many integers that aren't
// Add any int that is in both a and b to set c
for (int i = 0; (i < numeric_limits<int>::max())&&(comparedElementCount<totalElementCount); i++) {
unsigned int freqA = a.getFrequencyOf(i);
unsigned int freqB = b.getFrequencyOf(i);
comparedElementCount += freqA;
comparedElementCount += freqB;
if (freqA>freqB) c.add(i);
unsigned int freqANeg = a.getFrequencyOf(-i);
unsigned int freqBNeg = b.getFrequencyOf(-i);
comparedElementCount += freqANeg;
comparedElementCount += freqBNeg;
if (freqANeg>freqBNeg) c.add(-i);
}
//Return set c by value
return c;
}
SetFunctions.h
#ifndef EDU_CSCI2421_SET_H
#define EDU_CSCI2421_SET_H
//Include iostream for << and >> implementations
#include <iostream>
//Include string for << and >> operations
#include <string>
//Include sstream for the >> operator to read one line at a time
#include <sstream>
//Include numeric limits for brute-force guessing in operation implementations
#include <limits>
//Incude std except because we need runtime_err
#include <stdexcept>
//Include ArrayBag vecuase we need to extend it
#include "ArrayBag.h"
//Use the standard namespace so we don't have to write std:: all the time
using namespace std;
class Set : public ArrayBag {
friend class ArrayBag;
public:
/**
* add()
*
* overrides ArrayBag::add
*
* This implementation prevents the insertion of a value if it's already contained
* in the set.
*
* @param newEntry new entry to add to the set
* @return true if the insert was sucessful; false if not
*/
bool add(const int &a);
friend istream &operator>>(istream &in, Set &set);
/**
* operator<<
*
* outputs a set to an output stream as a tab-delimeted numbers
*
* ineffcient implementation: since we don't have access to the private underlying items array,
* we must make use of the available ArrayBag functions. This means we essentially have to guess
* what elements are in the set. This is inefficient if there are large numbers in the set.
* However, we assume all numbers are "close" to 0. Using this hueristic, we are able to process the example
* data set from the homework quickly.
*
* @param out the output stream (usually cout)
* @param set the set to print
* @return out
*/
friend ostream &operator<<(ostream &out, Set &set);
/**
* operator+
*
* SET UNION OPERATOR
*
* returns the union of two set objects as a new set object
*
* ineffcient implementation: since we don't have access to the private underlying items array,
* we must make use of the available ArrayBag functions. This means we essentially have to guess
* what elements are in the set. This is inefficient if there are large numbers in the set.
* However, we assume all numbers are "close" to 0. Using this hueristic, we are able to process the example
* data set from the homework quickly.
*
* @param a The left side of the union operator
* @param b The right side of the union operator
* @return c The result of the union operator on a and b
*/
friend Set operator+(Set &a, Set &b);
/**
* operator-
*
* SET DIFFERENCE OPERATOR
*
* removes all elements that are in b from a
*
* ineffcient implementation: since we don't have access to the private underlying items array,
* we must make use of the available ArrayBag functions. This means we essentially have to guess
* what elements are in the set. This is inefficient if there are large numbers in the set.
* However, we assume all numbers are "close" to 0. Using this hueristic, we are able to process the example
* data set from the homework quickly.
*
* @param a The left side of the intersection operator
* @param b The right side of the intersection operator
* @return c The result of the intersection operator on a and b
*/
friend Set operator-(Set &a, Set &b);
};
#endif //EDU_CSCI2421_SET_H
main.cpp
//---------Dependency Imports---------
//Include cout
#include <iostream>
#include <fstream>
//Include the GuessingGame class
#include "SetFunctions.h"
//Use the standard namespace so that we don't have to type "std" all the time
using namespace std;
void describe(const string expectString) {
cout << expectString << "...";
}
/**
* assertInt()
*
* Prints "Passed" or "Failed" with appropriate messages bassed on if expected==got.
*
* @param expected The value we expect got to equal
* @param got The actual function value
* @return int 1 if the test failed; 0 if it didn't
*/
int assertInt(int expected, int got) {
if (expected==got) {
cout << "Passed.";
} else {
cout << "Failed. Expected " << expected << "; Got " << got << ".";
}
cout << endl;
return expected!=got;
}
/**
* int test()
*
* Tests the functionality of the union operators; logs errors to the console if they exist
*/
void test() {
//Print welcome message
cout << "========Unit Tests========" << endl;
//Open an input stream
ifstream input;
input.open("setInput.txt");
//Keep track of how many tests we fail
unsigned int failCount = 0;
//Load Set A
describe("Set A should have 10 elements after loading from setInput.txt");
Set a;
input >> a;
failCount += assertInt(10, a.getCurrentSize());
//Load Set B
describe("Set B should have 10 elements after loading from setInput.txt");
Set b;
input >> b;
failCount += assertInt(10, a.getCurrentSize());
//Test union
describe("Set A+B (A union B) should have 15 elements");
Set aUnionB = a + b;
failCount += assertInt(15, aUnionB.getCurrentSize());
//Test difference
describe("Set A-B (A difference B) should have 1 element");
Set aDifferenceB = a - b;
failCount += assertInt(1, aDifferenceB.getCurrentSize());
//Test set functionality
describe("Max frequency in all sets should be 1");
unsigned int maxFreq = 0;
for (int i = -200; i < 200; i++) {
if (a.getFrequencyOf(i) > maxFreq) maxFreq=a.getFrequencyOf(i);
if (b.getFrequencyOf(i) > maxFreq) maxFreq=a.getFrequencyOf(i);
if (aUnionB.getFrequencyOf(i) > maxFreq) maxFreq=a.getFrequencyOf(i);
if (aDifferenceB.getFrequencyOf(i) > maxFreq) maxFreq=a.getFrequencyOf(i);
}
failCount += assertInt(1, maxFreq);
//Validate error checking by trying to load a file that
// contains invalid values
describe("Operator '>>' should throw runtime_error when reading from file that has invalid values");
ifstream invalidInput;
invalidInput.open("setInputInvalid.txt");
unsigned int exceptionCount = 0;
try {
Set d;
invalidInput >> d;
} catch (const runtime_error& e) {
exceptionCount++;
}
assertInt(1, exceptionCount);
//Completion message
cout << endl << "Completed automated tests. Failed " << failCount << " tests." << endl;
cout << "======End Unit Tests======" << endl;
}
//-----------Main Function------------
/**
* int main()
*
* The main entry point for the application.
*
* Returns 0.
*/
int main() {
//Run Unit tests
test();
//---Demo the application---
//Load inputs
ifstream input;
input.open("setInput.txt");
Set a;
Set b;
input >> a;
input >> b;
//Print sets
cout << "Set A: " << a << endl;
cout << "Set B: " << b << endl;
//Calculate union and difference
Set aUnionB = a + b;
Set aDifferenceB = a - b;
//Print union and difference
cout << "Set A+B: " << aUnionB << endl;
cout << "Set A-B: " << aDifferenceB << endl;
//Exit with a 0 status code
return 0;
}
validateInput.cpp
#include <iostream> //cout, cin
#include <sstream> //stringstream
#include <string>
#include <fstream> //ifstream
#include <vector>
using namespace std;
bool getIntsFromFile(ifstream &infile, vector<int> &vec )
//istream accepts from cin or file as a parent class
{
stringstream ss;
int tempInt;
string readString;
getline(infile, readString);
ss << readString; //Write readString into ss
while (!ss.eof()) //Until end of stream
{
ss >> tempInt; //Read in an int from ss into tempInt
if (ss.fail()) //If it fails to to read an int data type
{
cout << "Input contains non-integer data ";
ss.clear(); //Clears state of string stream;
return false;
}
vec.push_back(tempInt); //Add to the vector
}
return true;
}
/*Desc: Prints out all values in a vector
Pre: Reads in a vector
Post: void
*/
void printValues(vector<int> set)
{
for (int i = 0; i < set.size(); i++)
{
cout << set[i] << " ";
}
cout << endl;
}
int main()
{
ifstream infile("setInput.txt");
vector<int> vec1, vec2;
if ( getIntsFromFile(infile, vec1) )
printValues(vec1);
cout << endl;
if ( getIntsFromFile(infile, vec2) )
printValues(vec2);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.