Need help to implement these function intersection, difference and union to the
ID: 3742288 • Letter: N
Question
Need help to implement these function intersection, difference and union to the ArrayBag class and test in the main. The union of two bags is a new bag containing the combined contents of the original two bags. The intersection of two bags is a new bag containing the entries that occur in both of the original two bags. The difference of two bags is a new bag containing the entries that would be left in one bag after removing those that also occur in the second.
// 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>
#include <stdexcept>
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
/*
// STUB
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
/*
// 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
//Begin Chapter 3 Homework
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::Union(const ArrayBag<ItemType> secondBag)
{
ArrayBag<ItemType> unionBag;
getCurrentSize();
int bigSize = itemCount + secondBag.getCurrentSize();
//Begin C++ Interlude 3 HW
if (bigSize > unionBag.DEFAULT_CAPACITY)
throw std::out_of_range("Union of these Bags exceeds Default Capacity");
for (int i = 0; i<getCurrentSize(); i++)
unionBag.add(items[i]);
for (int i = 0; i<secondBag.getCurrentSize(); i++)
unionBag.add(secondBag.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)
{
for (int i = 0; i<getCurrentSize(); i++)
{
if (bag2.contains(items[i]))
{
remove(items[i]);
}
}
}
// Created by Frank M. Carrano and Tim Henry.
// Copyright (c) 2013 __Pearson Education__. All rights reserved.
/** Listing 4-4. */
#include "ArrayBag.h"
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
void displayBag(ArrayBag<string>&bagPtr)
{
cout << "The bag contains " << bagPtr.getCurrentSize()
<< " items:" << endl;
vector<string> bagItems = bagPtr.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>& bagPtr)
{
cout << "isEmpty: returns " << bagPtr.isEmpty()
<< "; should be 1 (true)" << endl;
string items[] = { "one", "two", "three", "four", "five", "six" };
cout << "Add 6 items to the bag: " << endl;
for (int i = 0; i < 6; i++)
{
bagPtr.add(items[i]);
} // end for
displayBag(bagPtr);
cout << "isEmpty: returns " << bagPtr.isEmpty()
<< "; should be 0 (false)" << endl;
cout << "getCurrentSize returns : " << bagPtr.getCurrentSize()
<< "; should be 6" << endl;
cout << "Try to add another entry: add("extra") returns "
<< bagPtr.add("extra") << endl;
cout << "Methods involving two bags" << endl;
ArrayBag<string> secondBagPtr;
string newItems[] = { "two", "four", "six", "eight", "ten", "twelve" };
cout << "Add 6 items to the bag: " << endl;
for (int i = 0; i < 6; i++)
{
secondBagPtr.add(newItems[i]);
} // end for
displayBag(bagPtr);
displayBag(secondBagPtr);
ArrayBag<string> unionBagPtr = bagPtr.Union(secondBagPtr);
ArrayBag<string> interBagPtr = bagPtr.intersection(secondBagPtr);
ArrayBag<string> diffBagPtr = bagPtr.difference(secondBagPtr);
cout << "Union of bags: " << endl;
displayBag(unionBagPtr);
cout << "Should contain both bags' values" << endl;
cout << "Intersection of bags: " << endl;
displayBag(interBagPtr);
cout << "Should contain two, four, and six" << endl;
cout << "Difference of bags: " << endl;
displayBag(diffBagPtr);
cout << "Should contain one, three, and five" << endl;
//end chapter 4 hw
} // end bagTester
int main()
{
ArrayBag<string> bagPtr;
cout << "Testing the Array-Based Bag:" << endl;
cout << "The initial bag is empty." << endl;
bagTester(bagPtr);
return 0;
} // end main
Explanation / Answer
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::difference(const ArrayBag<ItemType> bag2)
{
ArrayBag<ItemType> ans;
for (int i = 0; i<getCurrentSize(); i++)
{
// if he current item is not present in bag2
if (!bag2.contains(items[i]))
{
// add this term to the ans bag
ans.add(items[i]);
}
}
return ans;
}
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::Union(const ArrayBag<ItemType> bag2)
{
ArrayBag<ItemType> ans;
int i;
// add all the entries of the current bag in ans bag
for (i = 0; i<getCurrentSize(); i++)
{
// add the current term to the ans bag
ans.add(items[i]);
}
// add all the entries of the bag2 bag in ans bag
for (i = 0; i < bag2.getCurrentSize(); i++)
{
// add the current term to the ans bag
ans.add(bag2.items[i]);
}
return ans;
}
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::intersection(const ArrayBag<ItemType> bag2)
{
ArrayBag<ItemType> ans;
for (int i = 0; i<getCurrentSize(); i++)
{
// if he current item is present in bag2
if (bag2.contains(items[i]))
{
// add this term to the ans bag
ans.add(items[i]);
}
}
return ans;
}
=======================================================================
Add the following lines to ArrayBag.h inside the class definition
ArrayBag<ItemType> ArrayBag<ItemType>::difference(const ArrayBag<ItemType> bag2);
ArrayBag<ItemType> ArrayBag<ItemType>::Union(const ArrayBag<ItemType> bag2);
ArrayBag<ItemType> ArrayBag<ItemType>::intersection(const ArrayBag<ItemType> bag2);