C++ A bag can contain more than one copy of an item. This bag behavior is differ

Question

C++ A bag can contain more than one copy of an item. This bag behavior is different from a set, which can contain only a single copy of any given item. Write (specify, design, and implement) a new container class set, which is similar to a bag, except that a set can contain only one copy of any given item. You will need to change the interface (specifications) a bit. For example, instead of the bag’s count function, you will need a constant member function such as this: bool set::contains(const value_type& item) const; // Postcondition: TRUE if item is in the set. FALSE // otherwise. Similarly, you only need one remove function since there can be only one instance of an element in the set. Analyze the running time of each of the implemented member functions (constructor, insert, remove, contains, size, +=, +, -=, and -).

Explanation / Answer

Solution:

//Bag.h
#ifndef _BAG_
#define _BAG_
typedef int bag_type;
class Bag
{
   private:
       int       Bgcount;       // Bag members
       bag_type Bgdata[20];    // to 20 members data

   public:
               Bag();             // Constructor
       bool    insert(bag_type); // To put a members in bag
       bool    remove(bag_type); // remove a member
       int     size();            // members count in bag
       void    clearbg();           // remove all members
       bool    inbag(bag_type);   // check membership of a bag
       int     bghowmany(bag_type); // count member in bag.
};
#endif

//Bag.cpp
#include "bag.h"
#include <iostream>
// Constructor
Bag::Bag()  
{
   Bgcount=0;
}
// method remove all members from bag
void Bag::clearbg()
{
   Bgcount=0;
}
// method to place a value in Bag
bool Bag::insert(bag_type bgvalue)
{
   bool bgreply;
   if(Bgcount <20 ) {
      Bgdata[Bgcount]=bgvalue;
      bgreply=true;
      Bgcount++;
   } else {
      bgreply=false;
   }
   return bgreply;
}
// method to check the value is in bag
bool Bag::inbag(bag_type bgvalue)
{
   bool bgreply=false;
   int bgindex;
   for(bgindex=0;bgindex<Bgcount&& !bgreply;bgindex++)
      if(Bgdata[bgindex] == bgTvalue) bgreply=true;
   return bgreply;
}
// method to count the bag element
int Bag::bghowmany(bag_type bgTvalue)
{
   int thismany=0;
   int bgindex;
   for(bgindex=0;bgindex<Bgcount;bgindex++)
      if(Bgdata[bgindex]==bgTvalue) thismany++;
   return thismany;
}

// method to remove the value
bool Bag::remove(bag_type bgTvalue)
{
   bool bgreply=false;
   int bgindex;
   if(bghowmany(bgTvalue) == 0) return bgreply;
   bgreply=true;
   bgindex=0;
   while(Bgdata[bgindex] != bgTvalue) bgindex++;
   for(;bgindex<Bgcount;bgindex++)
      Bgdata[bgindex]=Bgdata[bgindex+1];
   Bgcount--;
}

// method to get the bag size
int Bag::size()  
{
   return Bgcount;
}

//test.cpp
#include <iostream>
#include <cstdlib>
#include "bag.h"

using namespace std;

int main(int argc, char *argv[])
{
  
   Bag bgB;
   bag_type bgTvalue;

   cout << "Bag" << endl;
   bgB.insert(5);
   do
   {
       bgTvalue=rand()%6 +1;
   } while(bgB.insert(bgTvalue));
   cout << bgB.size()<< " elements in the bag" << endl;
   cout << bgB.bghowmany(5) << " fours " << endl;
   bgB.remove(5);
   cout << bgB.size()<< " elements in the bag" << endl;
   cout << bgB.bghowmany(5) << " fours " << endl;
   cout << bgB.bghowmany(6) << " fives " << endl;
   while(bgB.inbag(6)) bgB.remove(6);
   cout << bgB.bghowmany(6) << " fives " << endl;

   system("Pause");
   return 0;
}

//main_sav.cpp
#include <algorithm>
#include <cassert>
#include "bag1.h"
using namespace std;

namespace main_sav
{
    /* method to erase the item from bag  
   this method executes the instructions until bgindex equals to
   m_used so its running time is O(n)*/
    bag::size_type bag::erase(const value_type& bgtarget)
    {
        size_type bgindex = 0;
        size_type bgmany_removed = 0;

        while (bgindex < m_used)
        {
            if (m_data[bgindex] == bgtarget)
            {
                --m_used;
                m_data[bgindex] = m_data[m_used];
                ++bgmany_removed;
            }
            else
                ++bgindex;
        }

        return bgmany_removed;
    }

   /* method to remove one item from bag
   this method executes the instructions until bgindex equals to
   m_used so its running time is O(n)*/
    bool bag::erase_one(const value_type& bgtarget)
    {
        size_type bgindex;
        bgindex = 0;
        while ((bgindex < m_used) && (m_data[bgindex] != bgtarget))
            ++bgindex;

        if (bgindex == m_used)
            return false;
        --m_used;
        m_data[bgindex] = m_data[m_used];  
        return true;
    }

   /* method to insert
   this method executes the instructions until size lesser than
   to capacity so its running time is O(n)*/
    void bag::insert(const value_type& bgentry)
    {
        assert(size() < bgCAPACITY);
                m_data[m_used] = bgentry;
        ++m_used;
    }

   //operator overloading
   /* this method executes the instruction upto size() plus
   bgaddend.size() lesser than bgCAPACITY, so its running time is O(n)*/
    void bag::operator +=(const bag& bgaddend)
    {
        assert(size( ) + bgaddend.size( ) <= bgCAPACITY);
      
        copy(bgaddend.m_data, bgaddend.m_data + bgaddend.m_used, m_data + m_used);
        m_used += bgaddend.m_used;
    }

   // method to count element
   /* this method executes the instruction upto m_used,
   so its running time is O(n)*/
    bag::size_type bag::Bgcount(const value_type& bgtarget) const
    {
        size_type bganswer;
        size_type i;

        bganswer = 0;
        for (i = 0; i < m_used; ++i)
            if (bgtarget == m_data[i])
                ++bganswer;
        return bganswer;
    }

    // operator overloading
   /* this method executes the instruction upto bag1 size() plus
   bag2 size() lesser than bgCAPACITY, so its running time is O(n)*/
   bag operator +(const bag& bgb1, const bag& bgb2)
    {
        bag bganswer;
        assert(bgb1.size() + bgb2.size() <= bag::bgCAPACITY);
        bganswer += bgb1;
        bganswer += bgb2;
        return bganswer;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.