C++ The intersection of two bags is a new bag containing the entries that occur
ID: 3804207 • Letter: C
Question
C++
The intersection of two bags is a new bag containing the entries that occur in both of the original two bags. Design and specify a method intersection for the ADT bag that returns as a new bag the intersection of the bag receiving the call to the method and the bag that is the method's one argument. Include sufficient comments to fully specify the method. Note that the intersection of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the intersection of these bags contains x two times. Specifically, suppose that bag1 and bag2 are bags; bag1 contains the strings a, b, and c; and bag2 contains the strings b, b, d, and e. The expression bag1. intersection (bag2) returns a bag containing only the string b. Note that intersection does not affect the contents of bag1 and bag2.Explanation / Answer
main.cpp
#include <iostream>
#include <string>
#include "ArrayBag.h"
void displayBag(ArrayBag<std::string>& bag)
{
std::cout << "The bag contains " << bag.getCurrentSize()
<< " items:" << std::endl;
std::vector<std::string> bagItems = bag.toVector();
int numberOfEntries = (int) bagItems.size();
for (int i = 0; i < numberOfEntries; i++)
{
std::cout << bagItems[i] << " ";
} // end for
std::cout << std::endl << std::endl;
} // end displayBag
void bagTester(ArrayBag<std::string>& bag)
{
std::cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << std::endl;
displayBag(bag);
std::string items[] = {"one", "two", "three", "four", "five", "one"};
std::cout << "Add 6 items to the bag: " << std::endl;
for (int i = 0; i < 6; i++)
{
bag.add(items[i]);
} // end for
displayBag(bag);
std::cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 0 (false)" << std::endl;
std::cout << "getCurrentSize: returns " << bag.getCurrentSize()
<< "; should be 6" << std::endl;
std::cout << "Try to add another entry: add("extra") returns "
<< bag.add("extra") << std::endl;
std::cout << "contains("three"): returns " << bag.contains("three")
<< "; should be 1 (true)" << std::endl;
std::cout << "contains("ten"): returns " << bag.contains("ten")
<< "; should be 0 (false)" << std::endl;
std::cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 2" << std::endl;
std::cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << std::endl;
std::cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 1" << std::endl;
std::cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << std::endl;
std::cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 0 (false)" << std::endl;
std::cout << std::endl;
displayBag(bag);
std::cout << "After clearing the bag, ";
bag.clear();
std::cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << std::endl;
} // end bagTester
void bagTester2(ArrayBag<std::string>& bag)
{
std::cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << std::endl;
displayBag(bag);
std::string items[] = { "one", "three", "three", "four", "one" };
std::cout << "Add 5 items to the bag: " << std::endl;
for (int i = 0; i < 5; i++)
{
bag.add(items[i]);
} // end for
displayBag(bag);
std::cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 0 (false)" << std::endl;
std::cout << "getCurrentSize: returns " << bag.getCurrentSize()
<< "; should be 5" << std::endl;
std::cout << "Try to add another entry: add("extra") returns "
<< bag.add("extra") << std::endl;
std::cout << "contains("three"): returns " << bag.contains("three")
<< "; should be 1 (true)" << std::endl;
std::cout << "contains("ten"): returns " << bag.contains("ten")
<< "; should be 0 (false)" << std::endl;
std::cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 2" << std::endl;
std::cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << std::endl;
std::cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 1" << std::endl;
std::cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << std::endl;
std::cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 0 (false)" << std::endl;
std::cout << std::endl;
displayBag(bag);
std::cout << "After clearing the bag, ";
bag.clear();
std::cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << std::endl;
} // end bagTester2
void bagUnionTest(ArrayBag<std::string> bag1, ArrayBag<std::string> bag2) {
std::cout << "Populating bags with items..." << std::endl;
std::string items1[] = { "one", "five", "one" };
for (int i = 0; i < 3; i++)
{
bag1.add(items1[i]);
}
std::cout << "Getting current size of first bag: " << bag1.getCurrentSize() << std::endl;
displayBag(bag1);
std::string items2[] = { "three", "six", "one" };
for (int i = 0; i < 3; i++)
{
bag2.add(items2[i]);
}
std::cout << "Getting current size of second bag: " << bag2.getCurrentSize() << std::endl;
displayBag(bag2);
std::cout << "Testing bagUnion... " << std::endl;
bag1 = bag1.bagUnion(bag2);
std::cout << "Showing result bag..." << std::endl;
displayBag(bag1);
std::cout << "Clearing both bags..." << std::endl;
bag1.clear();
bag2.clear();
}
void bagIntersectionTest(ArrayBag<std::string> bag1, ArrayBag<std::string> bag2) {
std::cout << "Populating bags with items..." << std::endl;
std::string items1[] = { "one", "five", "one", "three" };
for (int i = 0; i < 4; i++)
{
bag1.add(items1[i]);
}
std::cout << "Getting current size of first bag: " << bag1.getCurrentSize() << std::endl;
displayBag(bag1);
std::string items2[] = { "three", "six", "one" };
for (int i = 0; i < 3; i++)
{
bag2.add(items2[i]);
}
std::cout << "Getting current size of second bag: " << bag2.getCurrentSize() << std::endl;
displayBag(bag2);
std::cout << "Testing bagIntersection... " << std::endl;
bag1 = bag1.bagIntersection(bag2);
std::cout << "Showing result bag..." << std::endl;
displayBag(bag1);
std::cout << "Clearing both bags..." << std::endl;
bag1.clear();
bag2.clear();
}
void bagDifferenceTest(ArrayBag<std::string> bag1, ArrayBag<std::string> bag2) {
std::cout << "Populating bags with items..." << std::endl;
std::string items1[] = { "one", "five", "one", "three" };
for (int i = 0; i < 4; i++)
{
bag1.add(items1[i]);
}
std::cout << "Getting current size of first bag: " << bag1.getCurrentSize() << std::endl;
displayBag(bag1);
std::string items2[] = { "three", "six", "one" };
for (int i = 0; i < 3; i++)
{
bag2.add(items2[i]);
}
std::cout << "Getting current size of second bag: " << bag2.getCurrentSize() << std::endl;
displayBag(bag2);
std::cout << "Testing bagDifference... " << std::endl;
bag1 = bag1.bagDifference(bag2);
std::cout << "Showing result bag..." << std::endl;
displayBag(bag1);
std::cout << "Clearing both bags..." << std::endl;
bag1.clear();
bag2.clear();
}
void bagDifferenceTest2(ArrayBag<std::string> bag1, ArrayBag<std::string> bag2) {
std::cout << "Populating bags with items..." << std::endl;
std::string items1[] = { "three", "six", "one" };
for (int i = 0; i < 3; i++)
{
bag1.add(items1[i]);
}
std::cout << "Getting current size of first bag: " << bag1.getCurrentSize() << std::endl;
displayBag(bag1);
std::string items2[] = { "one", "five", "one", "three" };
for (int i = 0; i < 4; i++)
{
bag2.add(items2[i]);
}
std::cout << "Getting current size of second bag: " << bag2.getCurrentSize() << std::endl;
displayBag(bag2);
std::cout << "Testing bagDifference... " << std::endl;
bag1 = bag1.bagDifference(bag2);
std::cout << "Showing result bag..." << std::endl;
displayBag(bag1);
std::cout << "Clearing both bags..." << std::endl;
bag1.clear();
bag2.clear();
}
int main()
{
ArrayBag<std::string> bag;
std::cout << " Testing the first Array-Based Bag:" << std::endl << std::endl;
std::cout << "The initial first bag is empty." << std::endl;
bagTester(bag);
ArrayBag<std::string> bag2;
std::cout << std::endl << " Testing the second Array-Based Bag:" << std::endl << std::endl;
std::cout << "The initial second bag is empty." << std::endl;
bagTester2(bag2);
std::cout << std::endl << " Testing the Bag Union function..." << std::endl << std::endl;
bagUnionTest(bag, bag2);
std::cout << std::endl << " Testing the Bag Intersection function..." << std::endl << std::endl;
bagIntersectionTest(bag, bag2);
std::cout << std::endl << " Testing the Bag Difference function..." << std::endl << std::endl;
bagDifferenceTest(bag, bag2);
std::cout << std::endl << " Testing the Bag Difference function with bags swapped..." << std::endl << std::endl;
bagDifferenceTest2(bag, bag2);
std::cout << "All done!" << std::endl;
system("pause");
return 0;
} // end main
ArrayBag.cpp
/** 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)
{
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>
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>
std::vector<ItemType> ArrayBag<ItemType>::toVector() const
{
std::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>
ArrayBag<ItemType> ArrayBag<ItemType>::bagUnion(ArrayBag<ItemType> otherBag)
{
ArrayBag<ItemType> resultBag;
for (int count = 0; count < getCurrentSize(); count++)
{
resultBag.add(items[count]);
}
std::vector<std::string> bagItems = otherBag.toVector();
for (int count = 0; count < otherBag.getCurrentSize(); count++)
{
resultBag.add(bagItems[count]);
}
return resultBag;
}
template<class ItemType>
int ArrayBag<ItemType>::leastFrequency(int freq, int freq2) {
if (freq > freq2)
return freq2;
else
return freq;
}
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagIntersection(ArrayBag<ItemType> otherBag)
{
ArrayBag<ItemType> resultBag;
for (int count = 0; count < getCurrentSize(); count++)
{
int need = leastFrequency(getFrequencyOf(items[count]), otherBag.getFrequencyOf(items[count]));
int have = resultBag.getFrequencyOf(items[count]);
for (int freqCount = have; freqCount < need; freqCount++)
{
resultBag.add(items[count]);
}
}
return resultBag;
}
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagDifference(ArrayBag<ItemType> otherBag)
{
ArrayBag<ItemType> resultBag;
for (int count = 0; count < getCurrentSize(); count++)
{
resultBag.add(items[count]);
}
ArrayBag<ItemType> intersectBag = resultBag.bagIntersection(otherBag);
std::vector<std::string> bagItems = intersectBag.toVector();
for (int count = 0; count < intersectBag.getCurrentSize(); count++)
{
resultBag.remove(bagItems[count]);
}
return resultBag;
}
ArrayBag.h
/** Header file for an array-based implementation of the ADT bag.
@file ArrayBag.h */
#ifndef ARRAY_BAG_
#define ARRAY_BAG_
#include "BagInterface.h"
template<class ItemType>
class ArrayBag : public BagInterface<ItemType>
{
private:
static const int DEFAULT_CAPACITY = 6; // 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;
int leastFrequency(int, int);
public:
ArrayBag();
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
std::vector<ItemType> toVector() const;
ArrayBag<ItemType> bagUnion(ArrayBag<ItemType> bag);
ArrayBag<ItemType> bagIntersection(ArrayBag<ItemType> bag);
ArrayBag<ItemType> bagDifference(ArrayBag<ItemType> bag);
}; // end ArrayBag
#include "ArrayBag.cpp"
#endif
BagInterface.h
/** Listing 1-1.
@file BagInterface.h */
#ifndef BAG_INTERFACE_
#define BAG_INTERFACE_
#include <vector>
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 std::vector<ItemType> toVector() const = 0;
/** Destroys object and frees memory allocated by object.
(See C++ Interlude 2) */
virtual ~BagInterface () { }
}; // end BagInterface
#endif
Sample Output:
Testing the first Array-Based Bag:
The initial first bag is empty.
isEmpty: returns 1; should be 1 (true)
The bag contains 0 items:
Add 6 items to the bag:
The bag contains 6 items:
one two three four five one
isEmpty: returns 0; should be 0 (false)
getCurrentSize: returns 6; should be 6
Try to add another entry: add("extra") returns 0
contains("three"): returns 1; should be 1 (true)
contains("ten"): returns 0; should be 0 (false)
getFrequencyOf("one"): returns 2 should be 2
remove("one"): returns 1; should be 1 (true)
getFrequencyOf("one"): returns 1 should be 1
remove("one"): returns 1; should be 1 (true)
remove("one"): returns 0; should be 0 (false)
The bag contains 4 items:
five two three four
After clearing the bag, isEmpty: returns 1; should be 1 (true)
Testing the second Array-Based Bag:
The initial second bag is empty.
isEmpty: returns 1; should be 1 (true)
The bag contains 0 items:
Add 5 items to the bag:
The bag contains 5 items:
one three three four one
isEmpty: returns 0; should be 0 (false)
getCurrentSize: returns 5; should be 5
Try to add another entry: add("extra") returns 1
contains("three"): returns 1; should be 1 (true)
contains("ten"): returns 0; should be 0 (false)
getFrequencyOf("one"): returns 2 should be 2
remove("one"): returns 1; should be 1 (true)
getFrequencyOf("one"): returns 1 should be 1
remove("one"): returns 1; should be 1 (true)
remove("one"): returns 0; should be 0 (false)
The bag contains 4 items:
extra three three four
After clearing the bag, isEmpty: returns 1; should be 1 (true)
Testing the Bag Union function...
Populating bags with items...
Getting current size of first bag: 3
The bag contains 3 items:
one five one
Getting current size of second bag: 3
The bag contains 3 items:
three six one
Testing bagUnion...
Showing result bag...
The bag contains 6 items:
one five one three six one
Clearing both bags...
Testing the Bag Intersection function...
Populating bags with items...
Getting current size of first bag: 4
The bag contains 4 items:
one five one three
Getting current size of second bag: 3
The bag contains 3 items:
three six one
Testing bagIntersection...
Showing result bag...
The bag contains 2 items:
one three
Clearing both bags...
Testing the Bag Difference function...
Populating bags with items...
Getting current size of first bag: 4
The bag contains 4 items:
one five one three
Getting current size of second bag: 3
The bag contains 3 items:
three six one
Testing bagDifference...
Showing result bag...
The bag contains 2 items:
one five
Clearing both bags...
Testing the Bag Difference function with bags swapped...
Populating bags with items...
Getting current size of first bag: 3
The bag contains 3 items:
three six one
Getting current size of second bag: 4
The bag contains 4 items:
one five one three
Testing bagDifference...
Showing result bag...
The bag contains 1 items:
six
Clearing both bags...
All done!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.