I am trying to find the intersection of 2 arrays and am having trouble with this
ID: 3889958 • Letter: I
Question
I am trying to find the intersection of 2 arrays and am having trouble with this portion of the problem:
**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.**
Here is what I have so far but it is not giving me the correct output. I think I need to use the getFrequencyOf() method in some way but cannot figure out how to send multiples to the 3rd arrayBag. Also, we were told we cannot use Vectors to solve this problem.
CODE:
// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** Implementation file for the class ArrayBag.
* Updated to include new methods: bagUnion, bagInterface, and bagDifference.
* @author YOUR NAME
* @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
/*
// 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
**/
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(const ArrayBag<ItemType> &otherBag) const
{
ArrayBag<ItemType> unionBag;
for(int i = 0; i < getCurrentSize(); i++)
{
unionBag.add(items[i]);
}
for(int j = 0; j < otherBag.getCurrentSize(); j++)
{
unionBag.add(otherBag.items[j]);
}
return unionBag;
} // end bagUnion
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagIntersection(const ArrayBag<ItemType> &otherBag) const
{
ArrayBag<ItemType> intersectBag;
for(int i = 0; i < getCurrentSize(); i++)
{
if(contains(otherBag.items[i]))
{
intersectBag.add(items[i]);
}
}
return intersectBag;
} // end bagIntersection
Explanation / Answer
Given below is the fixed code for bagIntersection(). Hope it helps. If it did, please don't forget to rate the answer. Thank you.
template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagIntersection(const ArrayBag<ItemType> &otherBag) const
{
ArrayBag<ItemType> intersectBag;
int freq1, freq2, min;
for(int i = 0; i < getCurrentSize(); i++)
{
if(!intersectBag.contains(items[i])) //if the item was not already processed earlier
{
freq1 = getFrequencyOf(items[i]); //get the items frequency in htis bag
freq2 = otherBag.getFrequencyOf(items[i]); //get the item's frequency in otherBag
if(freq1 < freq2) //since it is intersection , find the lowest of 2 frequencies
min = freq1;
else
min = freq2;
if(min != 0) //if only there is atleast 1 occurence
{
for(int j = 0; j < min; j++) //add as many occurences as the min
intersectBag.add(items[i]);
}
}
}
return intersectBag;
} // end bagIntersection
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.