COP 4020- Spring 2002
Assignment 3
Due Date: Mar 18 until midnight

Create a class called "Set" in C++ using object-oriented techniques.

The maximum number of elements in a Set is 100. Create the array to store 
the elements of the Set by using the "new" operator.
The only type of elements that can be stored in a Set is an integer.

Programmers may define objects of Set class in the ways shown in the
following examples:

int a[11]={10,0,1,2,3,4,5,6,7,8,9};
int b[6]={5,1,3,5,7,9};
int c[6]={5,0,2,4,6,8};
int d[3]={2,0,1};
int e[1]={0};

Set Nnatural ; 		//creates an empty set
Set one_digit=a;    //creates a set using an array s.t. the first element
                    //of the array shows the size of the array
Set odd=b;
Set even=c;
Set zero=0;         //creates a set with single element 0 (i.e. {0})
Set zero_one=d;     
Set x=one_digit;    //creates a set by usin an existing set 
					//makes an exact copy of the existing set
Set empty_set2=e;

1. Write necessary constructors (and a destructor) for above operations.

2. Write following functions:

   Insert: inserts an element into a set
  	   eg: odd.Insert(6) modifies odd as {1,3,5,6,7,9}

   Remove: removes an element from a set
  	   eg: odd.Remove(5) modifies odd as {1,3,7,9}

   Is_empty: tests whether the set is empty or not
	   eg: odd.Is_empty() returns 0

   Card: Finds the cardinality of a set
	   eg: zero_one.Card()  returns 2

3. Overload following operators:

   =   :  Assignment operation (between 2 sets)
	  eg:  odd=even;	results in odd={0,2,4,6,8}

   +   :  Union of two sets
	  eg:  odd + even  results in a set {0,1,2,3,4,5,6,7,8,9}

   *   :  Intersection of two sets
	  eg:  odd * even  results in an empty set 

   -   :  Difference of two sets
	  eg:  one_digit - even  results in a set {1,3,5,7,9}

   ==  :  Equality of two sets, if all members are same return 1, else 0
	  eg:  one_digit == even  returns 0
	       one_digit == x	  returns 1

   []  : Membership of an element to a set
	  eg:  odd[3] returns 1
	       odd[2] returns 0		

    <  : Subset operator
	  eg:  odd < one_digit returns 1
	      
    >  : Superset operator
	  eg: one_digit > one returns 1

   <<  : Output a set. Elements will be separated by a blank and an end of line 
	 at the end.

   >>  : Input a set. Read the number of elements that will be input
   first.  Then, read the elements, which are separated by a blank.

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

Create a class called "Bag" in C++ using object-oriented techniques.
The Bag class will be a subclass of the class Set.
In a Bag the same element can be repeated any number of times.
Accordingly some existing Set functions should be redefined in a Bag class.
Also some new functions will be defined.

The maximum number of elements in a Bag is 1000. Create the array to store 
the elements of the Bag by using the "new" operator.
The only type of elements that can be stored in a Bag is an integer.

Bag objects can be constructed in different ways:

int a[4]={1,2,3,4};
int b[10]={0,0,0,1,1,2,3,8,9,9};
int c[]={0,1,1,8,9};
int d[]={0,0,8};

Bag empty_bag; 		//creates an empty bag
Bag bag1(b,10);     //creates a bag by initializing it with an array
                    //second parameter shows the size of the array
Bag bag2=bag1;      //creates a bag from an existing bag
Bag bag3=set1;      //creates a bag from an existing set
Bag bag4(c,5);
Bag bag5(d,3);

1. Write necessary constructors to handle the above declarations.

2. The following functions/operator will be inherited from the Set class:

   Insert: inserts an element into a bag
           unlike a set, an existing element can also be instered

   Remove: removes an element from a bag
           since each element can have several copies remove may remove
           only one copy

   Is_empty: tests whether the bag is empty or not

   Card: Finds the cardinality of a bag
            each occurence of an element contributes to the cardinality

   =   :  Assignment operation (between 2 bags)
          Also overlaod another version; assign a set into a bag  

   +   :  Union of two bags
          Allows repetitions.

   *   :  Intersection of two bags
          Allows repetitions.

   -   :  Difference of two bags
	      eg:  bag4 - bag5 results in a bag {1,1,9}

   ==  :  Equality of two bags, if all members are same return 1, else 0

   []  : Count of an element in a bag
	     eg:  bag5[0] returns 2; bag5[1] returns 0		

    <  : Subbag operator
	     eg:  bag5 < bag1 returns 1
	      
    >  : Superbag operator
	     eg: bag4 > bag5 returns 0

   <<  : Output a bag. 
         Each element will be printed with its count as follows:
		 eg: cout<<bag5; will print 0:2 8:1

   >>  : Input a bag. Read the size of the bag first, and then read that
         many integers separated by a blank (or any delimeter).

3. Add the following functions.

   sum  : find the sum of the integers in a bag, and return it

   product : find the product of the integers in a bag, and return it

4. Define the following function:

   void test(Set & ps1, Set & ps2)
   {
	 Bag tb(ps1);
	 int i;

	 cout<<ps1<<ps2<<tb;
	 ps1=ps2+ps2;
	 cout<<ps1;
	 cin>>ps2;
	 tb=ps2;
	 cout<<tb;
	 cin>>i;
	 cout<<tb[i];
   }

   Test this function (by calling it from your main function) with
   different type paramaters (like 2 sets, 2 bags, a bag and a set, etc.)
   and make sure it works correctly allways. If necessary convert some
   of the functions inherited from class Set to virtual. Note that we
   can change this test funtion also (prototype of the function will
   not be changed), so you should better try other functions.


SUBMISSION PROCEDURE: You have to submit your programs by e-mail to
the TA. Just send ASCII format single file. It should include the
whole class and required function definitions. Do not use any
non-standard functions. It is better to test on Unix/Linux
before the submission. Do not include the main function either.
We will write our main function in order to test your programs.