Question

C++

Create a static implementation of a set. Add the efficiency of each function to the documentation in the header file. Use test_set.cpp as your test program.

Header:

/************************************
This class models a mathematical set.
*/

#ifndef _SET_H
#define _SET_H

#include <cstdlib>
#include <iostream>

class set
{
public:
  typedef int value_type;
  typedef std::size_t size_type;
  static const size_type CAPACITY = 30;

  set();
// postcondition: empty set has been created
  
  void insert (const value_type& entry);
  // precondition: if entry is not in the set, set is not full
  // postcondition: entry is in the set

  void remove (const value_type& entry);
// postcondition: entry is not in the set

  size_type size() const;
// returned: number of elements in the set

  bool contains (const value_type& entry) const;
// returned: whether entry is in the set

  friend set set_union (const set& s1, const set& s2);
  //returned: union of s1 & s2

  friend set set_intersection (const set& s1, const set& s2);
  // returned: intersection of s1 & s2

  friend set set_difference (const set& s1, const set& s2);
// returned: difference of s1 - s2 

  friend bool is_subset (const set& s1, const set& s2);
// returned: whether s1 is a subset of s2

  friend bool operator == (const set& s1, const set& s2);
  // returned: whether s1 & s2 are equal

  friend std::ostream& operator << (std::ostream& output, const set& s);
// postcondition: s has been displayed on output

private:
  size_type find (const value_type& entry) const;
  // returned location of entry in the set if entry is in the set - used otherwise
  value_type data[CAPACITY];
  size_type used;
};


#endif

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Test:

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

int main ()
{
  set s;
  assert (!s.contains (7));
  s.insert (7);
  assert (s.contains (7));
  s.remove (7);
  assert (!s.contains (7));
  
  set s1;
  s1.insert (4);
  s1.insert (5);
  s1.insert (-24);
  s1.insert (89);
  s1.insert (34);
  s1.insert (11);
  s1.insert (0);
  s1.insert (3);
  s1.insert (14);
  s1.insert (28);
  std::cout << s1 << std::endl;

  set s2;
  s2.insert (6);
  s2.insert (-5);
  s2.insert (-24);
  s2.insert (-89);
  s2.insert (34);
  s2.insert (-11);
  s2.insert (0);
  s2.insert (3);
  std::cout << s2 << std::endl;

  set s3 = set_union (s1, s2);
  assert (s3.contains (4));
  assert (s3.contains (0));
  assert (s3.contains (-5));
  std::cout << s3 << std::endl;

  set s4 = set_intersection (s1, s2);
  assert (s4.contains (34));
  assert (!s4.contains (4));
  assert (!s4.contains (-5));
  std::cout << s4 << std::endl;

  set s5 = set_difference (s1, s2);
  assert (s5.contains (4));
  assert (!s5.contains (0));
  assert (!s5.contains (-5));
  std::cout << s5 << std::endl;

  assert (is_subset (s5, s1));
  std::cout << "all tests passed" << std::endl;
  return 0;
}

Answer 1

#include "Set.h"
#include <cassert>
#include<iostream>
using namespace std;
set::set(size_type initial_capacity)
{
capacity = initial_capacity;
used = 0;
data = new value_type[capacity];

}

set::set (const set& source)
{
capacity = source.capacity;
used = source.used;
data = new value_type[capacity];
for(int i = 0; i < used; i++)
data[i] = source.data[i];
}

set::~set()
{
capacity = 0;
used = 0;
delete data;
}

void set::insert (const value_type& entry)
{
bool found = false;
for(int i = 0; i < used; i++)
if(data[i] == entry)
{
found = true;
break;
}
if(!found && used < capacity)
{
data[used] = entry;
used++;
}
}

void set::remove (const value_type& entry)
{
int pos = -1;
for(int i = 0; i < used; i++)
if(data[i] == entry)
{
pos = i;
break;
}
for(int i = pos; i < used-1; i++)
data[i] = data[i+1];
used--;   
}

set::size_type set::size() const
{
return used;
}

bool set::contains (const value_type& entry) const
{
for(int i = 0; i < used; i++)
if(data[i] == entry)
return true;
return false;
}

set set_union (const set& s1, const set& s2)
{
set temp;
for(int i = 0; i < s1.size(); i++)
temp.insert(s1.data[i]);
for(int i = 0; i < s2.size(); i++)
temp.insert(s2.data[i]);
return temp;
}
set set_intersection (const set& s1, const set& s2)
{
set temp;
for(int i = 0; i < s1.size(); i++)
if(s2.contains(s1.data[i]))
temp.insert(s1.data[i]);
return temp;
}

set set_difference (const set& s1, const set& s2)
{
set temp;
for(int i = 0; i < s1.size(); i++)
if(!s2.contains(s1.data[i]))
temp.insert(s1.data[i]);
return temp;
}

bool is_subset (const set& s1, const set& s2)
{
for(int i = 0; i < s1.size(); i++)
if(!s2.contains(s1.data[i]))
return false;
return true;
}

bool operator == (const set& s1, const set& s2)
{
if(is_subset(s1, s2) && is_subset(s2, s1))
return true;
return false;
}

std::ostream& operator << (std::ostream& output, const set& s)
{
output << "{ ";
for(int i = 0; i < s.size()-1; i++)
output <<s.data[i]<<", ";
output<<s.data[s.size()-1]<<" }";
return output;
}