Question

Use the provided BingoBall.h and Set.h files to implement the Set.cpp file.

//File: BingoBall.h

#ifndef BINGOBALL_H
#define   BINGOBALL_H

#include <iostream>

class BingoBall {
public:
   BingoBall():letter{'a'}, number{0} {}
   BingoBall(char let, int num) :
       letter{ let }, number{ num } {}
   char getChar() const { return letter; }
   int getNumber() const { return number; }
   //overload == operator
   bool operator==(BingoBall &b) const { return (number == b.getNumber() && letter == b.getChar()); }
private:
   char letter;
   int number;
};

inline std::ostream& operator<<(std::ostream& out, const BingoBall& b) {
   out << b.getChar() << "-" << b.getNumber();
   return out;
}

#endif   /* BINGOBALL_H */

// File: Set.h


#ifndef SET_H
#define SET_H

#include <string>

using namespace std;

template <typename T>
class Set{
public:
   //creates an initially empy set
   Set();

   //destroys the set, deallocating any freed memory space if appropriate
   ~Set();

   //adds the element to the set (if it is not already in there)
   //returns false if element is not in universe, true otherwise
   bool addElement(const T& elem);

   //removes the specified element from set and returns the removed element, returns
   //nullpointer if the element was not in the set  
   T removeElement(const T& elem);

   //removes a random element and returns it, returns nullpointer if the set was empty initially
   T removeRandom();

   //returns true if the given element is in the set, false otherwise
   bool isIn(const T& elem) const;

   //returns true if the set is empty, false otherwise
   bool empty() const;

   //returns number of elements in the set
   int size() const;
  
private:
   //class level variable for holding an array based set implementation
   T* setArray;

    //the number of elements in the set
   int numEntries;
  
   //used for array based implementations to hold the maximum size of  
   //the array (do we need this? why or why not?)
   int arraySize;
};

// displays the entire set, solely for debugging purposes
template <typename T>
std::ostream& operator<<(std::ostream& out, Set<T>& p);

#endif /* SET_H */

Answer 1

Summary :

Provided notes , code and output.

Notes :

Implemented the set assuming that the Template type is a pointer ( since it has to return NULL for remove element ).

Further array size is doubled when new element is inserted while the set size is full .

The "<<" operator is implemented by removing all the elements from the set and copying to temp set and re-adding them .

And last all functions are tested in the main method with examples.

######################## Code ######################

#include <iostream>
#include <stdlib.h>
#include <time.h> 
#include "Set.h"

using namespace std ;

template<typename T>
Set<T>::Set()
{
        // initialize the size to 10 
        arraySize = 10 ;
        numEntries = 0 ;
        setArray = new T[10];
        srand (time(NULL));
}

template<typename T>
Set<T>::~Set()
{
        // delete the allocated array using delete[]
        for( int i=0 ; i < numEntries ; i++ )
                delete setArray[i];
        
        delete[] setArray ;
}


template <typename T>
void Set<T>::_doubleSize()
{
        T* tmpArray = new T[arraySize] ;
        
        for( int i=0 ; i < this->arraySize ; i++ )
                tmpArray[i] = setArray[i];
        
        delete[] setArray;
        
        setArray = new T[2*arraySize] ;
        
        for( int j =0 ; j < arraySize ; j++ )
                setArray[j] = tmpArray[j];
        
        arraySize = 2 * arraySize;
        
}
template <typename T>
bool Set<T>::addElement(const T& elem)
{
        if ( isIn( elem) )
        {
                cout << " Element found hence not inserting \n";
                return false ;
        } else 
        {
                if (!( numEntries < arraySize ) )
                {
                        
                        cout << " Set is full \n";
                        this->_doubleSize() ;
                }
                //setArray[numEntries]  ;
                setArray[numEntries] = (T ) malloc( sizeof( elem ) ) ;
                
                *setArray[numEntries] = *elem;
                numEntries++ ;
                return true ;

        }
        
        return false;
}



template <typename T>
T Set<T>::removeElement(const T& elem)
{
        int i =0;
        bool flag = false ;
        
        T ptr ;
        for( ; i < numEntries ; i++ )
        {
                if ( *elem == *setArray[i] )
                {  
                        flag = true ;
                        ptr = setArray[i];
                        break ;
                }
        }
        
        if ( flag ) 
        {
                for ( int j = i ; j < numEntries -1  ; j++ ) 
                {
                        setArray[j] = setArray[j+1] ;
                }
                numEntries = numEntries - 1;
                return ptr;
        }
        
        return NULL;
        
}


template <typename T>
T Set<T>::removeRandom()
{
        if ( ! this->empty() )
        {
                int rIdx = rand() % numEntries  ;
                //cout << " Random Indx : " << rIdx << "\n";
                T elm = setArray[rIdx];
                for ( int i= rIdx ; i < numEntries - 1 ; i++ )
                        setArray[i] = setArray[i + 1 ] ;
                
                numEntries = numEntries - 1;
                return elm;
                
        } else 
                return NULL;
                
}

template <typename T>
bool Set<T>::isIn(const T& elem) const
{
        
        int i =0;
        
        for( ; i < numEntries ; i++ )
        {
                if ( *elem == *setArray[i] )
                {  
                        return true ;
                        break ;
                }
        }
        
        return false;
}

template <typename T>
bool Set<T>::empty() const
{
        return numEntries == 0 ;
}

template<typename T>
void Set<T>::_print_() const
{
        cout << "\nSetArray : ";
        for ( int i=0 ; i < numEntries ; i++ )
                cout << *setArray[i] << ", " ;
        
        cout <<"\n";
        
}

template <typename T>
int Set<T>::size() const
{
        return numEntries;
}

template <typename T>
std::ostream& operator<<(std::ostream& out, Set<T>& p)
{
        Set<T> tmp ;
        T tmpElem;
        out << "\n Number of Entries : " << p.size() << "\n Entry List : " ;
        
        int sz = p.size();
        for(int i =0 ; i < sz ; i++ )
        {
                tmpElem = p.removeRandom();
                tmp.addElement(tmpElem);
                out << *tmpElem  << ", " ;
                delete tmpElem;
        }
        
        
        sz = tmp.size();
        for(int i =0 ; i < sz ; i++ )
        {
                tmpElem = tmp.removeRandom();
                p.addElement(tmpElem);
        }
        out << " \n";
        
        return out ;
}


int main()
{
        Set<int *> intList ;
        int x , x1 , x2 ;
        
        for( int i=0 ; i < 15 ; i++ ) 
        {
                x = rand() % 1000 + 1;
                cout << " Trying to Insert : " << x << " Successful : " << 
                intList.addElement(&x) << "\n";
                if ( i == 5 )
                        x1 = x ;
        }
        
        cout << intList << "\n";
        
        cout << " Trying to Insert duplicate : " << x1  <<  ", Successful - " << intList.addElement( &x1 ) << "\n";
        
        int* x4 = intList.removeElement(&x1) ;
        cout << " Remove the element  : " << x1 << ", Successful - " <<  *x4  << "\n";
        if ( x4 != NULL )
                delete x4 ;
        
        if ( intList.removeElement(&x1) != NULL )
        {
                cout << " Found " << x1 << "\n";
        }else 
                cout << "Got NULL \n";
        
        
        
        cout << "\n Set Empty : " << intList.empty() << "\n";
        cout << intList;
        
        
        cout << "Removing Random : " << intList.size() << "\n";;
        int j = 0 , sz = intList.size();
        for (  j = 0 ; j < sz  ; j++ )
        {       
                int * x5 = intList.removeRandom() ;
                cout << *x5 << "\n";
                delete x5;
        }

        cout << "\n Set Empty : " << intList.empty() << "\n";
        
}

############### Output ###############