Question

PLEASE HURRY. Below is the prompt for this problem. Use the code for bag1.cxx, bag1.h and my code for bag.cpp. Also I have provided errors from linux for bag.cpp. Please use that code and fix my errors please. Thank you

The goal of assignment 3 is to reinforce implementation of container class concepts in C++. Specifically, the assignment is to do problem 3.5 on page 149 of the text. You need to implement the set operations union, intersection, and relative complement. Your code must implement the style guidelines of the author (preconditions, postconditions, class invariant, and function efficiencies). Your test program should use a unit test style – test each implemented function and clearly label your output.

You will be provided with bag1.h and bag1.cpp files as reference. You will need to adapt this class to implement a set.

Here are some typical features of a set:

1. A set can have unique elements only – no duplicates allowed
2. Union of 2 sets s1 È s2 = a new set with all elements from s1 and s2 without any duplicates

If s1{1,2,3}, s2{3,4,5}

then s1Ès2 = {1,2,3,4,5}

3. Intersection of 2 sets s1Çs2 = a new set with elements common to both s1 and s2 => {3}
4. Relative complement of s1 to s2 = a new set with all elements from s1 that are not present in s2 => {1,2}

Here are the changes you should ideally be making to the .h and implementation files:

1. Change the name of the class to set and rename the files to set.h and set.cpp
2. You will need to add new functions Union, Intersection and Relative complement, these will need to be non- member friend functions.
3. You should also add a function called contains that checks to see if an entry is already present in the set. It should return a boolean value. This function should be a private function that can be called anytime, you need to insert an entry into a set (to make sure you don’t add duplicate entries).
4. You do not need the following functions from the bag class:

1. Erase
2. Count
3. += overloaded function
4. + overloaded function

5. Do not add any more functions besides the ones listed under 2. & 3.
6. Test the 3 set operations and clearly label your input and outputs.

bag1.cxx

// FILE: bag1.cxx
// CLASS IMPLEMENTED: bag (see bag1.h for documentation)
// INVARIANT for the bag class:
// 1. The number of items in the bag is in the member variable used;
// 2. For an empty bag, we do not care what is stored in any of data; for a
// non-empty bag the items in the bag are stored in data[0] through
// data[used-1], and we don't care what's in the rest of data.

#include <algorithm> // Provides copy function
#include <cassert> // Provides assert function
#include "bag1.h"
using namespace std;

namespace main_savitch_3
{
const bag::size_type bag::CAPACITY;
  
bag::size_type bag::erase(const value_type& target)
{
   size_type index = 0;
   size_type many_removed = 0;

   while (index < used)
   {
   if (data[index] == target)
   {
       --used;
       data[index] = data[used];
       ++many_removed;
   }
   else
       ++index;
   }

   return many_removed;
}

bool bag::erase_one(const value_type& target)
{
   size_type index; // The location of target in the data array

   // First, set index to the location of target in the data array,
   // which could be as small as 0 or as large as used-1. If target is not
   // in the array, then index will be set equal to used.
   index = 0;
   while ((index < used) && (data[index] != target))
   ++index;

   if (index == used)
   return false; // target is in the bag, so no work to do.

   // When execution reaches here, target is in the bag at data[index].
   // So, reduce used by 1 and copy the last item onto data[index].
   --used;
   data[index] = data[used];
   return true;
}

void bag::insert(const value_type& entry)
// Library facilities used: cassert
{   
assert(size( ) < CAPACITY);

data[used] = entry;
   ++used;
}

void bag::operator +=(const bag& addend)
// Library facilities used: algorithm, cassert
{
   assert(size( ) + addend.size( ) <= CAPACITY);
  
   copy(addend.data, addend.data + addend.used, data + used);
   used += addend.used;
}

bag::size_type bag::count(const value_type& target) const
{
size_type answer;
size_type i;

answer = 0;
for (i = 0; i < used; ++i)
if (target == data[i])
++answer;
return answer;
}

bag operator +(const bag& b1, const bag& b2)
// Library facilities used: cassert
{
bag answer;

assert(b1.size( ) + b2.size( ) <= bag::CAPACITY);

answer += b1;
answer += b2;
return answer;
}
}

bag1.h

// FILE: bag1.h
// CLASS PROVIDED: bag (part of the namespace main_savitch_3)
//
// TYPEDEF and MEMBER CONSTANTS for the bag class:
// typedef ____ value_type
// bag::value_type is the data type of the items in the bag. It may be any of
// the C++ built-in types (int, char, etc.), or a class with a default
// constructor, an assignment operator, and operators to
// test for equality (x == y) and non-equality (x != y).
//
// typedef ____ size_type
// bag::size_type is the data type of any variable that keeps track of how many items
// are in a bag.
//
// static const size_type CAPACITY = _____
// bag::CAPACITY is the maximum number of items that a bag can hold.
//
// CONSTRUCTOR for the bag class:
// bag( )
// Postcondition: The bag has been initialized as an empty bag.
//
// MODIFICATION MEMBER FUNCTIONS for the bag class:
// size_type erase(const value_type& target);
// Postcondition: All copies of target have been removed from the bag.
// The return value is the number of copies removed (which could be zero).
//
// void erase_one(const value_type& target)
// Postcondition: If target was in the bag, then one copy has been removed;
// otherwise the bag is unchanged. A true return value indicates that one
// copy was removed; false indicates that nothing was removed.
//
// void insert(const value_type& entry)
// Precondition: size( ) < CAPACITY.
// Postcondition: A new copy of entry has been added to the bag.
//
// void operator +=(const bag& addend)
// Precondition: size( ) + addend.size( ) <= CAPACITY.
// Postcondition: Each item in addend has been added to this bag.
//
// CONSTANT MEMBER FUNCTIONS for the bag class:
// size_type size( ) const
// Postcondition: The return value is the total number of items in the bag.
//
// size_type count(const value_type& target) const
// Postcondition: The return value is number of times target is in the bag.
//
// NONMEMBER FUNCTIONS for the bag class:
// bag operator +(const bag& b1, const bag& b2)
// Precondition: b1.size( ) + b2.size( ) <= bag::CAPACITY.
// Postcondition: The bag returned is the union of b1 and b2.
//
// VALUE SEMANTICS for the bag class:
// Assignments and the copy constructor may be used with bag objects.

#ifndef MAIN_SAVITCH_BAG1_H
#define MAIN_SAVITCH_BAG1_H
#include <cstdlib> // Provides size_t

namespace main_savitch_3
{
class bag
{
public:
// TYPEDEFS and MEMBER CONSTANTS
typedef int value_type;
typedef std::size_t size_type;
static const size_type CAPACITY = 30;
// CONSTRUCTOR
bag( ) { used = 0; }
// MODIFICATION MEMBER FUNCTIONS
size_type erase(const value_type& target);
bool erase_one(const value_type& target);
void insert(const value_type& entry);
void operator +=(const bag& addend);
// CONSTANT MEMBER FUNCTIONS
size_type size( ) const { return used; }
size_type count(const value_type& target) const;
private:
value_type data[CAPACITY]; // The array to store items
size_type used; // How much of array is used
};

// NONMEMBER FUNCTIONS for the bag class
bag operator +(const bag& b1, const bag& b2);
}

#endif

bag.cpp

#include<iostream>

#include "bag1.h"

using namespace std;

int set_operation::search(int a[],int sz,int n)

{

for(int i=0;i<sz;i++)

{

if(a[i]==n)

return(1);

}

return(0);

}

void set_operation::set_union(int a[],int b[],int acount,int bcount)

{

int i;

cout<<endl<<"S1 U S2:";

for(i=0;i<acount;i++)

{

cout<<a[i]<<" ";

}

for(i=0;i<bcount;i++)

{

if(!search(a,acount,b[i]))

cout<<b[i]<<" ";

}

}

void set_operation::set_intersection(int a[],int b[],int acount,int bcount)

{

int i;

cout<<endl<<"S1 intersection S2:";

for(i=0;i<bcount;i++)

{

if(search(a,acount,b[i]))

cout<<b[i]<<" ";

}

}

void set_operation::set_difference(int a[],int b[],int acount,int bcount)

{

int i;

cout<<endl<<"S1-S2: ";

for(i=0;i<acount;i++)

{

if(!search(b,bcount,a[i]))

cout<<a[i]<<" ";

}

}

int main()

{

set_operation ob;

int a[8],b[8],acount,bcount;

int i;

cout<<"How many elements in A: ";

cin>>acount;

cout<<"Enter "<<acount<<" elements of A:";

for(i=0;i<acount;i++)

{

cin>>a[i];

}

cout<<"How many elements in B: ";

cin>>bcount;

cout<<"Enter "<<bcount<<" elements of B:";

for(i=0;i<bcount;i++)

{

cin>>b[i];

}

ob.set_union(a,b,acount,bcount);

ob.set_intersection(a,b,acount,bcount);

ob.set_difference(a,b,acount,bcount);

Errors (from linux)

bag.cpp:7:5: error: âset_operationâ has not been declared
int set_operation::search(int a[],int sz,int n)
^
bag.cpp:25:6: error: âset_operationâ has not been declared
void set_operation::set_union(int a[],int b[],int acount,int bcount)
^
bag.cpp:53:6: error: âset_operationâ has not been declared
void set_operation::set_intersection(int a[],int b[],int acount,int bcount)
^
bag.cpp:73:6: error: âset_operationâ has not been declared
void set_operation::set_difference(int a[],int b[],int acount,int bcount)
^
bag.cpp: In function âint main()â:
bag.cpp:97:1: error: âset_operationâ was not declared in this scope
set_operation ob;
^
bag.cpp:97:15: error: expected â;â before âobâ
set_operation ob;
^
bag.cpp:131:1: error: âobâ was not declared in this scope
ob.set_union(a,b,acount,bcount);
^
bag.cpp:135:37: error: expected â}â at end of input
ob.set_difference(a,b,acount,bcount);

Answer 1

main.cpp

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

using namespace std;

int main() {

    set s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(5);
    cout << "set s..." << endl;
    s.print_set();

    set t;
    t.insert(4);
    t.insert(5);
    t.insert(88);
    t.insert(88);
    t.insert(6);
    t.insert(7);
    cout << "set t..." << endl;
    t.print_set();

    s.make_union(t);
    cout << "set s made union with t..." << endl;
    s.print_set();

    s.make_intersection(t);
    cout << "set s made intersection with t... " << endl;
    s.print_set();

    cout << "----------------" << endl;
    cout << "More testing...\n";

    set r;
    cout << "set r inserting 1, 2, 3, 3, 2 " << endl;
    r.insert(1);
    r.insert(2);
    r.insert(3);
    r.insert(3);
    r.insert(2);
    cout << "set r...\n";
    r.print_set();

    cout << "set r size: " << r.size() << endl;
    cout << "erase a single 2..." << endl;
    r.erase_one(2);
    r.print_set();
    cout << "erase all 3s (which is only one as it's a set..." << endl;
    r.erase(3);
    cout << "set r..." << endl;
    r.print_set();

    cout << "r size: " << r.size() << endl;

    cout << "r union s..." << endl;
    r.make_union(s);
    r.print_set();

    cout << "----------------" << endl;
    cout << "more testing union..." << endl;
    set p;
    p.insert(2);
    p.insert(4);
    p.insert(6);
    p.insert(8);
    cout << "set p..." << endl;
    p.print_set();

    set q;
    q.insert(6);
    q.insert(8);
    q.insert(10);
    cout << "set q..." << endl;
    q.print_set();

    cout << "set p made union with q" << endl;
    p.make_union(q);
    p.print_set();

    cout << "set s..." << endl;
    s.print_set();

    cout << "set p made union with s" << endl;
    p.make_union(s);
    p.print_set();

    cout << "indexing p at 3..." << endl;   // 8
    cout << p[3] << endl;

    return 0;
}

set.cpp

#include "set.h"
#include <algorithm>
#include <iostream>

set::set(set::size_type initial_capacity) {
    data = new value_type[DEFAULT_CAPACITY];
    capacity = initial_capacity;
    used = 0;
}

set::set(const set &source) {
    data = new value_type[source.capacity];
    std::copy(source.data, source.data + source.used, data);
    capacity = source.capacity;
    used = source.used;
}

set::~set() {
    delete[] data;
}

void set::reserve(set::size_type new_capacity) {
    if (new_capacity == capacity) return;           // the allocated memory is already the right size
    if (new_capacity < used) new_capacity = used;   // can't allocate less than we are using

    value_type *larger_array = new value_type[new_capacity];
    std::copy(data, data + used, larger_array);
    delete[] data;
    data = larger_array;
    capacity = new_capacity;
    // used remains unchanged
}

bool set::erase_one(const set::value_type &target) {
    size_type index = 0;
    while (index < used && data[index] != target) index++;
    if (index == used) return false;    // target not in bag

    // if reach here, target in set at data[index]
    // copy last item into data[index], reduce used by 1

    data[index] = data[used - 1];
    used--;
    return true;
}

typename set::size_type set::erase(const set::value_type &target) {
    size_type index = 0;
    size_type num_removed = 0;

    while (index < used) {
        if (data[index] == target) {
            data[index] = data[used - 1];   // last elem in set
            used--;
            num_removed++;
        }
        else index++;
    }
    return num_removed;
}

void set::insert(const set::value_type &entry, bool message) {
    if (contains(entry)) {
        if (message) std::cout << "contains duplicate, item not inserted.\n";
        return;
    }
    if (used == capacity) reserve(used + 1);
    data[used] = entry;
    used++;
}

bool set::contains(const set::value_type &target) const {
    size_type index = 0;
    while (index < used && data[index] != target) index++;
    return index != used;   // we must be on target if true
}

void set::operator+=(const set &addend) {
    if (used + addend.used > capacity) reserve(used + addend.used);
    size_type index = 0;
    while (++index < addend.used) {     // prefix: use then increment
        insert(addend.data[index], false);
    }
}

void set::operator=(const set &source) {
    if (this == &source) return;
    if (capacity != source.capacity) { // allocate an new array with source's capacity
        value_type *new_array = new value_type[source.capacity];
        capacity = source.capacity;
        delete[] data;
        data = new_array;
    }
    used = source.used;
    std::copy(source.data, source.data + source.used, data);
}

typename set::value_type set::operator[](const set::size_type x) {
    return data[x];
}

void set::make_union(const set &other_set) {
    if (used + other_set.used > capacity) reserve(used + other_set.used);
    size_type index = 0;
    while (index < other_set.used) {
        insert(other_set.data[index], false);
        index++;
    }
}

void set::make_intersection(const set &other_set) {
    value_type *array = new value_type[capacity + other_set.capacity];
    capacity = capacity += other_set.capacity;
    size_type tmp_used = 0;

    // loop through largest set, prevents out of bounds
    if (other_set.used > used) {
        size_type index = 0;
        size_type i = 0;
        while (index < other_set.used) {
            if (this->contains(other_set.data[index])) {
                array[i] = other_set.data[index];
                tmp_used++;
                i++;
            }
            index++;
        }
    }
    else {
        size_type index = 0;
        size_type i = 0;
        while (index < used) {
            if (other_set.contains(data[index])) {
                array[i] = data[index];
                tmp_used++;
                i++;
            }
            index++;
        }
    }
    delete[] data;      // return old memory pointed to by data to heap
    data = array;       // point data to newly allocated array memory
    used = tmp_used;    // update used
}

void set::print_set() const {
    for (size_type i = 0; i < used; i++) {
        std::cout << data[i] << ' ';
    }
    std::cout << '\n';
}

set.h

#ifndef SET_SET_H
#define SET_SET_H

#include <cstdlib>

class set {

    typedef int value_type;
    typedef std::size_t size_type;
    static const size_type DEFAULT_CAPACITY = 50;

public:

    // CONSTRUCTORS, DESTRUCTOR
    set(size_type initial_capacity = DEFAULT_CAPACITY);

    set(const set &source);

    ~set();

    // MEMBER FUNCTIONS
    void reserve(size_type new_capacity);

    bool erase_one(const value_type &target);

    size_type erase(const value_type &target);

    void insert(const value_type &entry, bool message = true);

    void operator+=(const set &addend);

    void operator=(const set &source);

    value_type operator[](const size_type x);

    void make_union(const set &other_set);

    void make_intersection(const set &other_set);

    void print_set() const;

    // CONSTANT MEMBER FUNCTIONS
    size_type size() const { return used; }

    bool contains(const value_type &target) const;

private:

    size_type used;     // number of items in set
    size_type capacity; // current capacity of the set
    value_type *data;   // pointer to partially filled dynamic array

};

// non member functions for set class
set operator+(const set &s1, const set &s2);

#endif //SET_SET_H