Assignment 4 template for Set Class Due Friday 13th
Most basic collections represent a group of items. A set represents a collection of unordered items with no duplicates. For example, the following three sets are equivalent:

{1, 3, 2} = {1, 2, 3} = {1, 1, 3, 2, 3, 3}

We have already seen sets in math. We have finite sets such as:

{ 1, 2, a, b, c}

or infinite sets like

{x | x is an integer }

Theoretically, an infinite set on a computer is unbounded; however, since a computer has a limited memory capacity, only finite sets are used in programs. Likewise, all sets in C++ are finite.

Beyond inserting and removing elements, common set operations are:

· membership
true if x is in S, false otherwise

· union
all elements in S1 or S2

· intersection
the elements in both S1 and S2

· complement
the objects not in S

Sets are very useful as abstraction structures. Librarians are concerned with the sets of all encyclopedias on their shelves. Teachers have to keep track of the sets of students in their classes.

To decide whether or not a collection of objects can be represented as a set, the programmer has to make sure that:

• an object cannot appear in the collection more than once.
• the objects in the collection are not ordered in any way.

Common C++ set operations are:

• check size all sets are finite
  int size( )
• check membership
  bool find( Item )
• insertion
  void insert Item )
• removal
  void erase( Item)

Either (concrete) arrays or linked lists can be used to implement sets. Here is a potential header file for a linked list implementation.

#ifndef SET_H

#define SET_H

template <class Item>

class Set

// This class is a container class that can hold as many Items

// as the amount of available memory allows.

// Only one instance of an item is allowed in the a set and the

// items are not stored in any specific order. The class

// provides member functions to insert and remove items as well

// as return the number of items already in the Set.

// Requirement:

// - Item for this container must have

// default constructor

// copy constructor

// assignment operator

// == operator

// Class Invariants:

// - count is the number of items contained in the Set

// - count >= 0

{

public:

Set();

// Default constructor

// PRE: none

// POST: An empty Set is created

Set( const Set& originalSet );

// Copy constructor

// PRE: originalSet is a valid Set object

// POST: A new Set is created containing the same elements as

// originalSet

~Set();

// Destructor

// PRE: none

// POST: The Set object is destroyed

void insert( const Item& entry );

// Modification member function

// PRE: entry is a valid Item

// POST: If entry is not already in the Set, then the entry is

// added; otherwise, nothing happens

void erase( const Item& target );

// Modification member function

// PRE: target is a valid Item

// POST: If target is in the Set, it is removed;

// otherwise nothing happens

int size() const;

// Accessor member function

// PRE: none

// POST: Returns the number of items in the set.

bool find( const Item& target ) const;

// Member function

// PRE: target is a valid Item

// POST: If target is in the Set, it returns true;

// otherwise, it returns false

void print() const;

// Member function

// PRE: none

// POST: The elements in the Set are printed out

const Set& operator=( const Set& otherSet );

// Member operator function

// PRE: otherSet is a valid Set object

// POST: The contents of 'otherSet' are copied into the current Set

Set operator+( const Set& otherSet ) const;

// Member operator function

// PRE: otherSet is a valid Set object

// POST: A new Set is returned that contains the current elements

// of this Set plus the elements of otherSet that are not in

// the current set. (union)

Set operator*( const Set& otherSet ) const;

// Member operator function

// PRE: otherSet is a valid Set object

// POST: A new Set is returned that contains the elements that are

// contained in both the current Set and in otherSet (intersection)

private:

struct SetNode

// This struct defines the Node of the singly linked list.

{

Item item;

SetNode* next;

};

SetNode* list; // pointer to a singly linked list of Set 'elements'

int count; // number of items stored in the list

void copy( const Set& otherSet );

// Private member function

// PRE: otherSet is a valid Set object

// POST: The elements from the other Set are copied into this Set.

};

Assignment

Implement a template for the Set class using the above interface. You may have to include the

definitions of the member functions in the interface file in order to compile correctly!!!!

In your test program create sets of several types including integers and strings.

This is a group project you may work with other students in the class as a team.

Remember the templates are like regular classes, except some types are shown as parameters.

A template class declaration for the Set class looks like the following:

template <class Item>
class Set
{
 ...
} 

The function definition for the constructor of Set looks like the following:

template <class Item>
Set<Item>::Set()
{
...
} 

Set can be used as following:

Set<int> intset;
 
Set<char> charset;
...