Need Help finding different values in 2 arrays

[jpauly1]

I need to find the difference between 2 arrays and store them in a 3rd array. I am having trouble account for repeat values in each of the first 2 arrays:
i.e.
array1 = 1 1 1 2 2
array2 = 2 1 2 1 2
differenceArray should be: 1 2

I have written the code below but when using the values above, I am getting the differenceArray holding 0 values. I know this is wrong, but everything I have tried hasn't worked either. I also had to find the intersection of these 2 arrays but simply doing the opposite didn't give me the right answers either.

Any help is much appreciated!

  #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;
	
	int freq;
	int freq2;
	int minFreq;
	
	for(int i = 0; i < getCurrentSize(); i++)
	{
		if(otherBag.contains(items[i]))	
		{
			if(!intersectBag.contains(items[i]))
			{
				freq = getFrequencyOf(items[i]);	
				freq2 = getFrequencyOf(otherBag.items[i]);	
				if(freq < freq2)
				{
					minFreq = freq;
				}
				else
				{
					minFreq = freq2;
				}
				for(int j = 0; j < minFreq; j++)
				{
					intersectBag.add(items[i]);
				}
			}
		}
	}
	return intersectBag;
	
}	// end bagIntersection



template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagDifference(const ArrayBag<ItemType> &otherBag) const
{
	ArrayBag<ItemType> differenceBag;
	for(int i = 0; i < getCurrentSize(); i++)
	{
		if(!otherBag.contains(items[i]))
		{
			differenceBag.add(items[i]);
		}
		
	}
	
	
	return differenceBag;
}//end of bagDifference 

Also if anyone wants to verify my bagIntersection method too that would be great.

Thanks!

[lastchance]

Sorry, but your code is too complicated for me to follow. However, to find intersection and difference of two vectors you can use the following - method will probably apply to your code ... if I could follow that.

Fundamentally, just keep parallel bool arrays to indicate which elements have been included in the intersection.

To get the difference you effectively have to find the intersection ... so you might as well do both together anyway.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

//======================================================================

template <class T> void myCompare( vector<T> A, vector<T> B, vector<T> &intersection, vector<T> &difference )
{
   intersection.clear();
   difference.clear();

   vector<bool> usedA( A.size(), false );        // keep tabs on which elements of A and B have been used in intersection
   vector<bool> usedB( B.size(), false );

   for ( int i = 0; i < A.size(); i++ )
   {
      for ( int j = 0; j < B.size(); j++ )
      {
         if ( !usedB[j] && B[j] == A[i] )        // found a match: stick it in intersection, and mark both A and B elements
         {
            intersection.push_back( A[i] );
            usedA[i] = true;
            usedB[j] = true;
            break;                               // breaks out of the search in B
         }
      }
   }

   for ( int i = 0; i < A.size(); i++ ) if ( !usedA[i] ) difference.push_back( A[i] );
   for ( int j = 0; j < B.size(); j++ ) if ( !usedB[j] ) difference.push_back( B[j] );
}

//======================================================================

template <class T> void write( string s, vector<T> A )
{
   cout << s;
   for ( T x : A ) cout << x << " ";
   cout << '\n';

}

//======================================================================

int main()
{
   vector<int> A = { 1, 1, 1, 2, 2 };
   vector<int> B = { 2, 1, 2, 1, 2 };
   vector<int> intersection, difference;

   myCompare( A, B, intersection, difference );
   write( "Intersection: ", intersection );
   write( "Difference:   ", difference   );
}

Intersection: 1 1 2 2 
Difference:   1 2 

[jpauly1]

Sorry, forgot to mention.... cannot use Vectors in this exercise.

[lastchance]

Indeed. Well, you are using them on line 126 of your program.

Anyway, you can use whatever type of container or array you like: ArrayBags or whatever. The sample program uses vectors for convenience: the method would work with other types of storage.