C++ Bag ADT help. I\'m having trouble implementing file methods. The following 3
ID: 3891055 • Letter: C
Question
C++ Bag ADT help. I'm having trouble implementing file methods.
The following 3 methods are to be added to the Array-based implementation of a Bag ADT. Methods must compose a new Bag object by accessing the elements of the underlying array of the Bag objects. You may not convert the Bags to vectors in the completion of these methods. The main() method must also be updated to thoroughly test the newly added methods.
1. bagUnion: The union of two bags is a new bag containing the combined contents of the original two bags. Design and specify a method union for the ArrayBag that returns as a new bag the union of the bag receiving the call to the method and the bag that is the method's parameter. Note that the union of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the union of these bags contains x seven times. The union does not affect the contents of the original bags.
2. bagIntersection: The intersection of two bags is a new bag containing the entries that occur in both of the original bags. Design and specify a method intersection for the ArrayBag 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 parameter. 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. The intersection does not affect the contents of the original bags.
3. bagDifference: 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. Design and specify a method difference for the ArrayBag that returns as a new bag the difference of the bag receiving the call to the method and the bag that is the method's parameter. Note that the difference of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the difference of these bags contains x three times.
My ArrayBag implementation .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;
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;
vector<ItemType> toVector() const;
//My methods
ArrayBag<ItemType> bagUnion(const ArrayBag<ItemType> &otherBag) const;
ArrayBag<ItemType> bagIntersection(const ArrayBag<ItemType> &otherBag) const;
ArrayBag<ItemType> bagDifference(const ArrayBag<ItemType> &otherBag) const;
}; // end ArrayBag
#include "ArrayBag.cpp"
#endif
My 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
/*
// 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
//My methods
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagUnion(const ArrayBag<ItemType> &otherBag) const
{
}
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType::bagIntersection(const ArrayBag<ItemType> &otherBag) const
{
}
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType::bagDifference(const ArrayBag<ItemType> &otherBag) const
{
}
My BagTester.cpp/main file for displaying the results
#include <iostream>
#include <string>
#include "ArrayBag.h"
using namespace std;
/*
Testing the Array-Based Bag:
The initial 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
All done!
*/
void displayBag(ArrayBag<string>& bag);
void bagTester(ArrayBag<string>& bag);
int main()
{
ArrayBag<string> bag;
cout << "Testing the Array-Based Bag:" << endl;
cout << "The initial bag is empty." << endl;
bagTester(bag);
cout << "All done!" << endl;
return 0;
} // end main
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
Explanation / Answer
Driver.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
----------------------------------------------------------------------
#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
-------------------------------------------------------------
#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
--------------------------------------------------
#ifndef BAG_INTERFACE_
#define BAG_INTERFACE_
#include <vector>
template<class ItemType>
class BagInterface
{
public:
virtual int getCurrentSize() const = 0;
virtual bool isEmpty() const = 0;
virtual bool add(const ItemType& newEntry) = 0;
virtual bool remove(const ItemType& anEntry) = 0;
virtual void clear() = 0;
virtual int getFrequencyOf(const ItemType& anEntry) const = 0;
virtual bool contains(const ItemType& anEntry) const = 0;
virtual std::vector<ItemType> toVector() const = 0;
virtual ~BagInterface () { }
}; // end BagInterface
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.