Given our standard Bag ADT with the following public methods: ArrayBag ) int get
ID: 3889145 • Letter: G
Question
Given our standard Bag ADT with the following public methods: 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 vectorKItemType> tovector () const virtual ArrayBag Using only the public methods provided by the ADT, write a client function merge that combines the contents of two bags into the first one, and deletes the second bag (which is now empty) (Note: I copied the above code from our dynamically-resizable array bag, but we could be using a linked-list bag, too. It doesn't matter. The point is that you **do not** have to worry about the bag getting full. The first bag will always be able to accommodate the items in the second bag.)Explanation / Answer
#include <iostream>
#include <string>
#include "ArrayBag.h"
// Used in main function to display items in the bag
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
// Tests the member functions of ArrayBag ADT
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 << "replace("two, with six"): returns " << bag.replace("two",
"six")<< "; should be 1 (true)" << 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
// Main function creates new ArrayBag and uses member functions to interact with it
int main()
{
ArrayBag<std::string> bag;
int array[] = {1,2,3};
ArrayBag<int> firstBag(array, 3);
ArrayBag<int> secondBag(array, 3);
std::cout << "Testing the Array-Based Bag:" << std::endl;
std::cout << "The initial bag is empty." << std::endl;
bagTester(bag);
std::cout << "The sum of integer array should be 6, your answer is " <<
firstBag.sum() << std::endl;
std::cout << "Merging firstBag and secondBag" << std::endl;
bool ret = firstBag.merge(secondBag);
std::cout << "The size of new bag should be 6, your output is " <<
firstBag.getCurrentSize() << std::endl;
std::cout << "All done!" << std::endl;
return 0;
} // end main
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 = 4;
ItemType* items; //array must be dynamic; so pointers are very yes
int itemCount;
int myCapacity; //added variable to track capacity
public:
ArrayBag(int capacity = DEFAULT_CAPACITY); // new constructor
ArrayBag(const ArrayBag& anotherBag); // copy constructor
~ArrayBag(); //destructor
int getCurrentSize() const;
int getCapacity() const;
void resize(int newCapacity); // resize
bool isEmpty() const;
bool isFull() 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;
ArrayBag& operator=(const ArrayBag& anotherBag);
};
#include "ArrayBag.cpp"
#endif
ArrayBag.cpp
///////////////////////////////////////////////
#include <cstddef>
#include <typeinfo>
#include "ArrayBag.h"
template<class ItemType>
ArrayBag<ItemType>::ArrayBag(): itemCount(0), maxItems(DEFAULT_CAPACITY)
{
} // end default constructor
// Implement a constructor overload which takes a template array along with
// number of entries
// Template create arrayBag of type ItemType
template<class ItemType>
ArrayBag<ItemType>::ArrayBag(ItemType entries[], int entryCount) :
itemCount(entryCount), maxItems(DEFAULT_CAPACITY)
{
// For each entry in entries, add an entry to items
// The for loop is needed to make a deep copy in the ArrayBag class
for (int i = 0; i < entryCount; i++) {
items[i] = entries[i];
}
// Set the objects itemCount equal to the passed in entryCount
itemCount = entryCount;
} // end paremeter constructor
template<class ItemType>
int ArrayBag<ItemType>::getCurrentSize() const
{
// Public member function to return number of entries in
return itemCount;
} // end getCurrentSize
template<class ItemType>
bool ArrayBag<ItemType>::isEmpty() const
{
//Boolean statment to determine if itemCount is 0
return itemCount == 0;
} // end isEmpty
template<class ItemType>
bool ArrayBag<ItemType>::add(const ItemType& newEntry)
{
//Checks whether the array is long enough to add another item
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)
{
// Gets index of a value
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
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
/** Implement a member function sum which counts integer numbers and returns
* the sum as a double variable
* @pre Check if the template is of integer data type
* @post If the template is of other than integer return -1
* @param void
* @return sum of integers present in the array **/
template<class ItemType>
double ArrayBag<ItemType>::sum() const
{
double sumVal = 0;
// Check that the ItemType is a value of int
if (typeid(ItemType) == typeid(int))
{
// For each item, add the value to the sum
for (int i = 0; i < itemCount; i++)
{
sumVal += items[i];
}
}
else
return -1;
// Return the sum Value
return sumVal;
} // end sum
/** Implement a member function which replaces existing entry with new
* entry.
* @param oldItem from the array and newItem from the array
* @return 1 if the replacement is done successfully or else 0 **/
template<class ItemType>
bool ArrayBag<ItemType>::replace(const ItemType oldEntry, const ItemType newEntry)
{
bool hasReplaced = false;
int nextIndex = 0;
// While the index is a feasible number or the starting 0 and the new entry is not equal to the old entry
while (nextIndex >= 0 && newEntry != oldEntry)
{
// Find the old entry
nextIndex = getIndexOf(oldEntry);
// If the index is a real value
if(nextIndex >= 0)
{
// Replace the value at the index
items[nextIndex] = newEntry;
// Set the flag to true
hasReplaced = true;
}
}
// Return the flag
return hasReplaced;
} // end replace
/** Implement a member function to merge a new array into existing array
* @param New array ADT object
* @return 1(true) if successful, or 0(false) if not **/
template<class ItemType>
bool ArrayBag<ItemType>::merge(const ArrayBag<ItemType>& secondBag)
{
bool returnVal;
// If the max size is not big enough, expand the size to the addtion of the sizes
if(maxItems < getCurrentSize()+secondBag.getCurrentSize())
maxItems = getCurrentSize()+secondBag.getCurrentSize();
// Loop through each item in the second bag and add it to the current set of items
for (int i = 0; i < secondBag.getCurrentSize(); i++)
{
bool thisReturnVal = add(secondBag.items[i]);
if (thisReturnVal)
returnVal = true;;
}
// Return the bool that tracks whether the add was successful
return returnVal;
} // end merge
// 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
BagInterface.h
#ifndef BAG_INTERFACE_
#define BAG_INTERFACE_
#include <vector>
template<class ItemType>
class BagInterface
{
// All of these functions are virtual because they will be redefined in the derived class
// They are basic ADT member functions
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.