Question

The goal of this assignment is to implement a set container using linked lists. Use the authors bag3.h and bag3.cpp as a basis for implementing your set container using linked lists. The authors bag3.h and bag3.cpp can be found here https://www.cs.colorado.edu/~main/chapter5/

Since you are using the authors bag3.h and bag3.cpp for your Set container implementation, make sure that you change the name of the class and constructors to reflect the set class.

Additionally you will need to implement the follow set operations. Union, intersection, relative complement, insertion (if the element is in the set, then nothing happens), deletion (if the element is not in the set nothing happens), query to check whether an element is in a set, query to find the number of elements in a set, display the set, destructor, copy constructor, overloading assignment operator.

The assignment must follow the author's guidelines of preconditions andpostconditions for the functions. In addition, the efficiency of each function must be stated.

Answer 1

Here is the code for set.h and set.cpp created from the bag.*** files from the above link mention in your question. You will need node1.h and node1.cpp files as well from the link to compile the code. Implemented the functionality for union, intersect, complement, deletion , display . I have created a Test.cpp file with the code shown to test out the implementation of set. Attached is the screen shot of running Test.cpp. Please do rate the answer if you are happy with the program. Thanks.

set.h

=========

// FILE: set.h
// CLASS PROVIDED: set (part of the namespace main_savitch_5)
//
// TYPEDEFS for the set class:
// set::value_type
// is the data type of the items in the set. It may be any
// of the C++ built-in types (int, char, etc.), or a class with a default
// constructor, a copy constructor, an assignment
// operator, and a test for equality (x == y).
//
// set::size_type
// is the data type of any variable that keeps track of how many items are
// in a set
//
// CONSTRUCTOR for the set class:
// set( )
// Postcondition: The set is empty.
//
// MODIFICATION MEMBER FUNCTIONS for the set class:
//   
// bool erase(const value_type& target)
// Postcondition: If target was in the set, then one copy of target has
// been removed from the set; otherwise the set is unchanged. A true
// return value indicates that one copy was removed; false indicates that
// nothing was removed.
//
// bool insert(const value_type& entry)
// Postcondition: The entry is inserted if not already present in the set.
//       A true is return if insertion successful otherwise false.
//
// void operator +=(const set& addend)
// Postcondition: Each item in addend , if not already present has been added to this set.
//
// CONSTANT MEMBER FUNCTIONS for the set class:
// size_type size( ) const
// Postcondition: Return value is the total number of items in the set.
//
// size_type count(const value_type& target) const
// Postcondition: Return value is number of times target is in the set.
//
//
// value_type grab( ) const
// Precondition: size( ) > 0.
// Postcondition: The return value is a randomly selected item from the set.
//
// NONMEMBER FUNCTIONS for the set class:
// set operator +(const set& b1, const set& b2)
// Postcondition: The set returned is the union of b1 and b2.
//
//   set operator -(const set& b1, const set& b2)
// Postcondition: The set returned is the complement i.e. b1- b2 (all elements in b1 that are not in b2)
// VALUE SEMANTICS for the set class:
// Assignments and the copy constructor may be used with set objects.
//
// DYNAMIC MEMORY USAGE by the set:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc: The constructors, insert, operator +=, operator +, and the
// assignment operator.

#ifndef MAIN_SAVITCH_set_H
#define MAIN_SAVITCH_set_H
#include <cstdlib> // Provides size_t and NULL
#include "node1.h" // Provides node class
namespace main_savitch_5
{
class set
{
public:
// TYPEDEFS
typedef std::size_t size_type;
typedef node::value_type value_type;
// CONSTRUCTORS and DESTRUCTOR
set( );
set(const set& source);
   ~set( );
// MODIFICATION MEMBER FUNCTIONS
bool erase(const value_type& target);
  
bool insert(const value_type& entry);
set intersect(const set& set2);
void operator +=(const set& addend);
void operator -=(const set& set2);
void operator =(const set& source);
// CONSTANT MEMBER FUNCTIONS
size_type size( ) const { return many_nodes; }
bool isPresent(const value_type& target) const;

value_type grab( ) const;
void display() ;
private:
node *head_ptr; // List head pointer
size_type many_nodes; // Number of nodes on the list
};

// NONMEMBER FUNCTIONS for the set class:
set operator +(const set& b1, const set& b2);
   set operator -(const set& b1, const set& b2);
}
#endif

=============

set.cpp

=======

// FILE: set.cxx
// CLASS implemented: set (see set.h for documentation)
// INVARIANT for the set ADT:
// 1. The items in the set are stored on a linked list;
// 2. The head pointer of the list is stored in the member variable head_ptr;
// 3. The total number of items in the list is stored in the member variable
// many_nodes.
#include <iostream>
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL, rand, size_t
#include "node1.h" // Provides node and the linked list functions
#include "set.h"

using namespace std;

namespace main_savitch_5
{

set::set( )
// Library facilities used: cstdlib
{
   head_ptr = NULL;
   many_nodes = 0;
}

set::set(const set& source)
// Library facilities used: node1.h
{
node *tail_ptr; // Needed for argument of list_copy

list_copy(source.head_ptr, head_ptr, tail_ptr);
many_nodes = source.many_nodes;
}
  
set::~set( )
// Library facilities used: node1.h
{
list_clear(head_ptr);
many_nodes = 0;
}
     
   bool set::isPresent(const value_type &target) const
   {
      node *cursor = list_search(head_ptr, target);
      return cursor!=NULL;
   }
  

  
bool set::erase(const value_type& target)
// Library facilities used: cstdlib, node1.h
{
   node *target_ptr;
  
   target_ptr = list_search(head_ptr, target);
   if (target_ptr == NULL)
   return false; // target isn't in the set, so no work to do
   target_ptr->set_data( head_ptr->data( ) );
   list_head_remove(head_ptr);
   --many_nodes;
   return true;
}

set::value_type set::grab( ) const
// Library facilities used: cassert, cstdlib, node1.h
{
   size_type i;
   const node *cursor; // Use const node* since we don't change the nodes.

   assert(size( ) > 0);
   i = (rand( ) % size( )) + 1;
   cursor = list_locate(head_ptr, i);
   return cursor->data( );
}

set set::intersect(const set& set2)
// Library facilities used: node1.h
{
   set answer;
   node *cursor=head_ptr;
   while(cursor!=NULL)
   {
       //check if the item from current set is in set2, then put it in answer
       if(set2.isPresent(cursor->data()))
           answer.insert(cursor->data());
       cursor=cursor->link();
      
   }
   return answer;
}
   bool set::insert(const value_type& entry)
// Library facilities used: node1.h
{
  
   node *cursor;
  
   cursor = list_search(head_ptr, entry);
   if (cursor == NULL)// entry isn't in the set, so add to set
   {
       list_head_insert(head_ptr, entry);
       ++many_nodes;
   return true;
   }
   else
       return false;
  
}

void set::operator +=(const set& addend)
// Library facilities used: cstdlib, node1.h
{
       node *cursor=addend.head_ptr;
  
  
       if (addend.many_nodes > 0)
       {
          //iterate over each item in the set and use insert function. So that no duplicates are in the set
       while(cursor!=NULL)
       {
          
               insert(cursor->data());
              cursor=cursor->link();
       }
       }
}
void set::operator -=(const set& set2)
// Library facilities used: cstdlib, node1.h
{
       node *cursor=set2.head_ptr;
  
  
       if (set2.many_nodes > 0)
       {
          //iterate over each item in the 2nd set and remove it from current
       while(cursor!=NULL)
       {      
               erase(cursor->data());
              cursor=cursor->link();
       }
       }
}
void set::operator =(const set& source)
// Library facilities used: node1.h
{
   node *tail_ptr; // Needed for argument to list_copy

   if (this == &source)
return;

   list_clear(head_ptr);
   many_nodes = 0;
   list_copy(source.head_ptr, head_ptr, tail_ptr);
   many_nodes = source.many_nodes;
}
  
   void set::display()
   {
       node *p=head_ptr;
       cout<<"\n[";
       while(p!=NULL)
       {
           cout<<p->data()<<",";
           p=p->link();
       }
       cout<<"]";
   }
set operator +(const set& b1, const set& b2)
{
   set answer;

   answer += b1;
   answer += b2;
   return answer;
}
  
   set operator -(const set& b1, const set& b2)
{
       set answer;
       answer+=b1;
       answer-=b2;
      
      
       return answer;
}
}

======

Test.cpp

======

#include "set.h"
#include <iostream>
using namespace std;
int main()
{
   main_savitch_5::set A,B;
   A.insert(1);
   A.insert(2);
   A.insert(3);
   A.insert(4);
  
   cout<<"After inserting 1,2,3,4 Set A has :";
   A.display();
  
   B.insert(1);
   B.insert(2);
   B.insert(5);
   B.insert(6);
  
   cout<<"\nAfter inserting 1,2,5,6 Set B has :";
   B.display();
  
   main_savitch_5::set U=A+B,I=A.intersect(B),C=A-B,D=B-A;
   cout<<"\nUnion : Set A + Set B :";
   U.display();
  
   cout<<"\nIntersection of Set A and Set B :";
   I.display();
  
   cout<<"\nSet A - Set B :";
   C.display();
  
   cout<<"\nSet B - Set A :";
   D.display();
  
   //try inserting a duplicate , should not insert
   return 0;
}