Union Function C++

Question

I need to create a Union function that will produce the union of two bags. My problem is that when i run the program, the function will add the elements and sometimes it might repeat the same number if it is entered more than once. How can I improve this function so that the number will only appear once?

#pragma once
//  Created by Frank M. Carrano and Tim Henry.
//  Copyright (c) 2013 Pearson Education. All rights reserved.

/** Header file for an array-based implementation of the ADT bag.
@file ArrayBag.h */

#ifndef _ARRAY_BAG
#define _ARRAY_BAG

#include "BagInterface.h"
#include <cstddef>

template<class ItemType>
class ArrayBag : public BagInterface<ItemType>
{
private:
    static const int DEFAULT_CAPACITY = 15; // Small size to test for a full bag
    ItemType items[DEFAULT_CAPACITY];      // Array of bag items
    int itemCount;                         // Current count of bag items 
    int maxItems;                          // Max capacity of the bag

                                           // Returns either the index of the element in the array items that
                                           // contains the given target or -1, if the array does not contain 
                                           // the target.
                                           //int getIndexOf(const ItemType& target) const;

public:
    ArrayBag();
    int getIndexOf(const ItemType& target) const;
    int getCurrentSize() const;
    bool isEmpty() const;
    bool add(const ItemType& newEntry);
    bool remove(const ItemType& anEntry);
    bool remove2(const ItemType& anEntry);
    void clear();
    bool contains(const ItemType& anEntry) const;
    int getFrequencyOf(const ItemType& anEntry) const;
    void  displayBag2()const;
    vector<ItemType> toVector() const;
    ArrayBag<ItemType> Union(const ArrayBag<ItemType> myBag2);
    ArrayBag<ItemType> Intersection(const ArrayBag<ItemType> myBag2);
    ArrayBag<ItemType> Difference(const ArrayBag<ItemType> myBag2);
}; // end ArrayBag

   //  Created by Frank M. Carrano and Tim Henry.
   //  Copyright (c) 2013 Pearson Education. All rights reserved.

   /** Implementation file for the class ArrayBag.
   @file ArrayBag.cpp */

#include "ArrayBag.h"
#include <cstddef>

template<class ItemType>
ArrayBag<ItemType>::ArrayBag() : itemCount(0), maxItems(DEFAULT_CAPACITY)
{
}  // end default constructor

template<class ItemType>
int ArrayBag<ItemType>::getCurrentSize() const
{
    return itemCount;
}  // end getCurrentSize

template<class ItemType>
bool ArrayBag<ItemType>::isEmpty() const
{
    return itemCount == 0;
}  // end isEmpty

template<class ItemType>
bool ArrayBag<ItemType>::add(const ItemType& newEntry)
{
    bool hasRoomToAdd = (itemCount < maxItems);
    if (hasRoomToAdd)
    {
        items[itemCount] = newEntry;
        itemCount++;
    }  // end if

    return hasRoomToAdd;
}  // end add

   /*
   template<class ItemType>
   bool ArrayBag<ItemType>::remove(const ItemType& anEntry)
   {

   return false; // STUB
   }  // end remove
   */

template<class ItemType>
bool ArrayBag<ItemType>::remove(const ItemType& anEntry)
{
    int locatedIndex = getIndexOf(anEntry);
    bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
    if (canRemoveItem)
    {
        itemCount--;
        items[locatedIndex] = items[itemCount];
    }  // end if

    return canRemoveItem;
}  // end remove


template<class ItemType>
bool ArrayBag<ItemType>::remove2(const ItemType& anEntry)
{
    int locatedIndex = getIndexOf(anEntry);
    bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
    if (canRemoveItem)
    {
        for (int i = 0; i < getCurrentSize(); i++)
        {
            if (items[i] == anEntry)
            {
                for (int j = i; j < (getCurrentSize() - 1); j++)
                {
                    items[j] = items[j + 1];
                }
                itemCount--;
            }
        }

        //items[locatedIndex] = items[itemCount];

    }  // end if

    return canRemoveItem;
}  // end remove


   /*
   // STUB
   template<class ItemType>
   void ArrayBag<ItemType>::clear()
   {
   // STUB
   }  // end clear
   */

template<class ItemType>
void ArrayBag<ItemType>::clear()
{
    itemCount = 0;
}  // end clear

template<class ItemType>
int ArrayBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
    int frequency = 0;
    int curIndex = 0;       // Current array index
    while (curIndex < itemCount)
    {
        if (items[curIndex] == anEntry)
        {
            frequency++;
        }  // end if

        curIndex++;          // Increment to next entry
    }  // end while

    return frequency;
}  // end getFrequencyOf


template<class ItemType>
bool ArrayBag<ItemType>::contains(const ItemType& anEntry) const
{
    return getIndexOf(anEntry) > -1;
}  // end contains

   /* ALTERNATE 1: First version
   template<class ItemType>
   bool ArrayBag<ItemType>::contains(const ItemType& target) const
   {
   return getFrequencyOf(target) > 0;
   }  // end contains

   // ALTERNATE 2: Second version
   template<class ItemType>
   bool ArrayBag<ItemType>::contains(const ItemType& anEntry) const
   {
   bool found = false;
   int curIndex = 0;        // Current array index
   while (!found && (curIndex < itemCount))
   {
   if (anEntry == items[curIndex])
   {
   found = true;
   } // end if

   curIndex++;           // Increment to next entry
   }  // end while

   return found;
   }  // end contains
   */

template<class ItemType>
vector<ItemType> ArrayBag<ItemType>::toVector() const
{
    vector<ItemType> bagContents;
    for (int i = 0; i < itemCount; i++)
        bagContents.push_back(items[i]);

    return bagContents;
}  // end toVector

   // private
template<class ItemType>
int ArrayBag<ItemType>::getIndexOf(const ItemType& target) const
{
    bool found = false;
    int result = -1;
    int searchIndex = 0;

    // If the bag is empty, itemCount is zero, so loop is skipped
    while (!found && (searchIndex < itemCount))
    {
        if (items[searchIndex] == target)
        {
            found = true;
            result = searchIndex;
        }
        else
        {
            searchIndex++;
        }  // end if
    }  // end while

    return result;
}  // end getIndexOf

template<class ItemType>
void  ArrayBag<ItemType>::displayBag2()const
{
    cout << "The bag contains: < ";
    for (int i = 0; i < getCurrentSize(); i++)
    {
        cout << items[i] << " ";
    }
    cout << ">";
} // end displayBag 


template <class ItemType>
ArrayBag<ItemType> ArrayBag <ItemType> ::Union(const ArrayBag<ItemType> bag2)
{
    ArrayBag<ItemType> unionBag;

    for (int i = 0; i < getCurrentSize(); i++)
    {
        unionBag.add(items[i]);
    }

    for (int i = 0; i < bag2.getCurrentSize(); i++)
    {
        unionBag.add(bag2.items[i]);
        if (items[i] == bag2.items[i])
            unionBag.remove(bag2.items[i]);
    }   

    return unionBag;
}


template <class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::Intersection(const ArrayBag<ItemType> bag2)
{
    ArrayBag<ItemType> interBag;

    for (int i = 0; i < getCurrentSize(); i++)
    {
        if (bag2.contains(items[i]))
            interBag.add(items[i]);

    }

    return interBag;
}

template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::Difference(const ArrayBag<ItemType> bag2)
{
    ArrayBag<ItemType> diffBag;

    for (int i = 0; i < getCurrentSize(); i++)
    {


        if (!bag2.contains(items[i]))
                diffBag.add(items[i]);
        }



        return diffBag;
    }


    #endif

    #pragma once
    //  Created by Frank M. Carrano and Tim Henry.
    //  Copyright (c) 2013 Pearson Education. All rights reserved.

    /** Listing 1-1.
    @file BagInterface.h */
    #ifndef _BAG_INTERFACE
    #define _BAG_INTERFACE

    #include <vector>
    using namespace std;

    template<class ItemType>
    class BagInterface
    {
    public:
        /** Gets the current number of entries in this bag.
        @return The integer number of entries currently in the bag. */
        virtual int getCurrentSize() const = 0;

        /** Sees whether this bag is empty.
        @return True if the bag is empty, or false if not. */
        virtual bool isEmpty() const = 0;

        /** Adds a new entry to this bag.
        @post  If successful, newEntry is stored in the bag and
        the count of items in the bag has increased by 1.
        @param newEntry  The object to be added as a new entry.
        @return  True if addition was successful, or false if not. */
        virtual bool add(const ItemType& newEntry) = 0;

        /** Removes one occurrence of a given entry from this bag,
        if possible.
        @post  If successful, anEntry has been removed from the bag
        and the count of items in the bag has decreased by 1.
        @param anEntry  The entry to be removed.
        @return  True if removal was successful, or false if not. */
        virtual bool remove(const ItemType& anEntry) = 0;

        /** Removes all entries from this bag.
        @post  Bag contains no items, and the count of items is 0. */
        virtual void clear() = 0;

        /** Counts the number of times a given entry appears in bag.
        @param anEntry  The entry to be counted.
        @return  The number of times anEntry appears in the bag. */
        virtual int getFrequencyOf(const ItemType& anEntry) const = 0;

        /** Tests whether this bag contains a given entry.
        @param anEntry  The entry to locate.
        @return  True if bag contains anEntry, or false otherwise. */
        virtual bool contains(const ItemType& anEntry) const = 0;

        /** Empties and then fills a given vector with all entries that
        are in this bag.
        @return  A vector containing all the entries in the bag. */
        virtual vector<ItemType> toVector() const = 0;

    }; // end BagInterface
    #endif

#include <iostream> 
#include <string> 
#include <algorithm>
#include <vector>
#include "ArrayBag.h" 


using  namespace std;
void  displayBag(ArrayBag<string>& bag)
{
    cout << "The bag contains " << bag.getCurrentSize() << " items:" << endl;
    vector<string> bagItems = bag.toVector();
    int  numberOfEntries = (int)bagItems.size();
    for (int i = 0; i < numberOfEntries; i++) {
        cout << bagItems[i] << " ";
    } // end for     cout << endl << endl; 
} // end displayBag 


void  bagTester(ArrayBag<string>& bag)
{
    cout << "isEmpty: returns " << bag.isEmpty() << "; should be 1 (true)" << endl;
    displayBag(bag);
    string items[] = { "one", "two", "three", "four", "five", "one" };
    cout << "Add 6 items to the bag: " << endl; for (int i = 0; i < 6; i++) { bag.add(items[i]); } // end for 
    displayBag(bag);
    cout << "isEmpty: returns " << bag.isEmpty() << "; should be 0 (false)" << endl;
    cout << "getCurrentSize: returns " << bag.getCurrentSize() << "; should be 6" << endl;
    cout << "Try to add another entry: add(\"extra\") returns " << bag.add("extra") << endl;
}   // end bagTester 

int  main()
{
    ArrayBag<int> bag1, bag2;
    char answer, answer2;
    int n, n2;

    cout << "How many numbers are going to be entered: ";
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int num;
        cout << "Enter a number: ";
        cin >> num;
        bag1.add(num);
    }

    cout << endl;
    bag1.displayBag2();
    cout << endl;
    cout << "The bag contains: " << bag1.getCurrentSize() << " numbers.";
    cout << endl << endl;

    cout << "Now we are going to create another bag for comparison." << endl;

    cout << "How many numbers are going to be entered: ";
    cin >> n2;

    for (int i = 0; i < n2; i++)
    {
        int num;
        cout << "Enter a number: ";
        cin >> num;
        bag2.add(num);
    }

    cout << endl;
    bag2.displayBag2();
    cout << endl;
    cout << "The bag contains: " << bag2.getCurrentSize() << " numbers.";
    cout << endl << endl;

    cout << "The union of both bags is: " << endl;
    ArrayBag<int> bag3 = bag1.Union(bag2);
    bag3.displayBag2();
    cout << endl;

    cout << "The intersection of both bags is: " << endl;
    ArrayBag<int> bag4 = bag1.Intersection(bag2);
    bag4.displayBag2();
    cout << endl;

    cout << "The difference of both bags is: " << endl;
    ArrayBag<int> bag5 = bag1.Difference(bag2);
    bag5.displayBag2();
    cout << endl;


    cout << "The frequency of the number 4 is: " << bag1.getFrequencyOf(4);
    cout << endl;

    cout << "The index of the number 9 is: " << bag1.getIndexOf(9);
    cout << endl << endl;

    cout << "Now we are going to remove 4" << endl << endl;
    for (int a = 0; a < n; a++)
    {
        bag1.remove2(4);
    }
    bag1.displayBag2();

    cout << endl;
    cout << "The bag contains: " << bag1.getCurrentSize() << " numbers.";

    cout << endl << endl;

    cout << "Would you like to remove another number (Y/N)? ";
    cin >> answer;

    if (answer == 'Y' || answer == 'y')
    {
        int remove;
        cout << endl;
        cout << "Which number would you like to remove: ";
        cin >> remove;
        for (int a = 0; a < n; a++)
        {
            bag1.remove2(remove);
        }
        cout << endl;

        bag1.displayBag2();

    }
    else
        bag1.displayBag2();

    cout << endl;
    cout << "Would you like to add more numbers to the bag? (Y/N)";
    cin >> answer2;


    if (answer2 == 'Y' || answer2 == 'y')
    {
        int add, quantity;
        cout << endl;

        cout << "How many numbers would you like to add: ";
        cin >> quantity;
        for (int a = 0; a < quantity; a++)
        {
            cout << endl;
            cout << "Which number would you like to add: ";
            cin >> add;
            bag1.add(add);
        }
        cout << endl;

        bag1.displayBag2();
        cout << endl;
        cout << "The bag contains: " << bag1.getCurrentSize() << " numbers.";
        cout << endl;
    }

    cout << endl;
    cout << endl << "Good bye!" << endl << endl;
    system("pause");
    return  0;
} // end main

Answer 1

if (items[i] == bag2.items[i])

This will only be true if the item you're checking in bag2 exists at the exact same index in the current object.

If you need duplicate removal, you need to check if any item in the union matches the one in the source. You should also probably do this as part of the insertion so as to avoid the insert-then-delete scenario, and you should probably do it to both sources (bag2 and the current object). That would be something like:

template <class ItemType>
ArrayBag<ItemType> ArrayBag <ItemType> ::Union(const ArrayBag<ItemType> bag2) {
    ArrayBag<ItemType> unionBag;

    // Add my items, removing dupes.

    for (int i = 0; i < getCurrentSize(); i++)
        if (! unionBag.contains(bag2.items[i]))
            unionBag.add(items[i]);

    // Add other items, removing dupes.

    for (int i = 0; i < bag2.getCurrentSize(); i++)
        if (! unionBag.contains(bag2.items[i]))
            unionBag.add(bag2.items[i]);

    return unionBag;
}

If you really want true set behaviour (only one of each item), you may want to consider the possibility of using a set rather than a bag, at least while constucting the union, after which you could transfer each set item to a bag. A set only has one of each item no matter how many times you try to add it.

---

Of course, there's the opposite^(a) interpretation of taking the union of two bags, one that doesn't involve removing duplicates. An argument can be made that, while the union of the sets {1,2,3} and {2,3,4} is:

{1,2,3} U {2,3,4} => {1,2,3,4}

the union of those two items as bags should be:

{1,2,3} U {2,3,4} => {1,2,2,3,3,4}

After all, a bag is simply a container of objects, and you're allowed to have more than one of each object in the bag. Tipping a bag of seven apples into another bag of three apples would very much give you a bag of ten apples, not one, three, or four (depending on how duplicates are removed).

---

^(a) Some would say "more sensible" but I don't want to insult my audience :-)