ArrayBag bagIntersection & bagDifference

[jpauly1]

Working on a problem and I'm currently stuck on the bagIntersection method.

Here is essentially what I need to do:
Create a 3rd ArrayBag object to contain the intersection of bags 1 and 2.

WHERE I'M HAVING TROUBLE:

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.

Cannot use vectors to complete this as well.

Here is what I have so far for bagIntersection: Just need to find a way to get it to read and compare duplicates.

  template<class ItemType>
ArrayBag<ItemType> ArrayBag<ItemType>::bagIntersection(const ArrayBag<ItemType> &otherBag) const
{
    ArrayBag<ItemType> intersectBag;
	
    for(int i = 0; i < getCurrentSize(); i++)
    {
	if(otherBag.contains(items[i]))
        {
            //thinking my issue is here:

	    if(getFrequencyOf(items[i]) < otherBag.getFrequencyOf(items[i]))
	    {
		intersectBag.add(items[i]);
	    }
	    else
	    {
		intersectBag.add(otherBag.items[i]);
	    }
			
	}
		
    }
	
    return intersectBag;
	
}// end bagIntersection 

Also having issues with even getting bagDifference to not crash but I thought figuring this out first may help with solving that one.

[Duthomhas]

The duplicates issue makes your life harder than it could have been. From the structure of your code I presume that a bag does not maintain any specific order. This suggests using a variation of a merge sort to select non-duplicate items from the two source bags to put into the destination bag:

Given: this_bag, that_bag
Create: intersect_bag
Algorithm:

sort this_bag
sort that_bag

this_i = 0
that_i = 0
while (this_i < this_bag_size) and (that_i < that_bag_size):

  if (this_bag[this_i] == that_bag[that_i]):
    /* skip identical items */
    this_i = this_i + 1
    that_i = that_i + 1
  else:

    /* add the lexicographically smaller item to intersect_bag */
    if (this_bag[this_i] < that_bag[that_i]):
      intersect_bag.add( this_bag[this_i] )
      this_i = this_i + 1
    else:
      intersect_bag.add( that_bag[that_i] )
      that_i = that_i + 1

/* one of the bags may still have leftovers */
while (this_i < this_bag_size):
  intersect_bag.add( this_bag[this_i] )
  this_i = this_i + 1

while (that_i < that_bag_size):
  intersect_bag.add( that_bag[that_i] )
  that_i = that_i + 1

Let's visualize that:

this:  A  A  A  B  B  C  D  D  D  E  F
that:  A  A  C  C  D  E
intersection: 

this: [A] A  A  B  B  C  D  D  D  E  F
that: [A] A  C  C  D  E
intersection: 

this:  A [A] A  B  B  C  D  D  D  E  F
that:  A [A] C  C  D  E
intersection: 

this:  A  A [A] B  B  C  D  D  D  E  F
that:  A  A [C] C  D  E
intersection: 

this:  A  A  A [B] B  C  D  D  D  E  F
that:  A  A [C] C  D  E
intersection: A

this:  A  A  A  B [B] C  D  D  D  E  F
that:  A  A [C] C  D  E
intersection: A B

this:  A  A  A  B  B [C] D  D  D  E  F
that:  A  A [C] C  D  E
intersection: A B B

this:  A  A  A  B  B  C [D] D  D  E  F
that:  A  A  C [C] D  E
intersection: A B B

this:  A  A  A  B  B  C [D] D  D  E  F
that:  A  A  C  C [D] E
intersection: A B B C

this:  A  A  A  B  B  C  D [D] D  E  F
that:  A  A  C  C  D [E]
intersection: A B B C

this:  A  A  A  B  B  C  D  D [D] E  F
that:  A  A  C  C  D [E]
intersection: A B B C D

this:  A  A  A  B  B  C  D  D  D [E] F
that:  A  A  C  C  D [E]
intersection: A B B C D D

this:  A  A  A  B  B  C  D  D  D  E [F]
that:  A  A  C  C  D  E []
intersection: A B B C D D

this:  A  A  A  B  B  C  D  D  D  E  F []
that:  A  A  C  C  D  E []
intersection: A B B C D D F

If you cannot work on sorted data, your options are either time or space:

If you wish to expend extra space, create a copy of each source bag, sort the copies, and then use the merge sort strategy.

If you wish to expend extra time, then simply looping over both sources would work. The trick is to not add things that already exist in the result.

Given: this_bag, that_bag
Create: intersect_bag
Algorithm:

for each item in this_bag:
  if (item not in intersect_bag):
    n = abs( frequency of item in this_bag - frequency of item in that_bag )
    add item to intersect_bag n times
for each item in that_bag:
  if (item not in this_bag):
    add item to intersect_bag

Hope this helps.

[jpauly1]

Sorry, maybe I didn't explain what I needed the correct way. Let me try with an example:

array1 = 1 1 2 2 3
array2 = 1 1 1 2 5

IntersectionArray - needs to be: 1 1 2


After trying several things I can get the intersect bag to be: intersectBag = 1 2

Or

intersectBag = 1 1 2 2

So I'm not quite sure what I am doing wrong.


For my difference bag, given the example above, I would need differenceBag to be: 1 2 3 5

[Duthomhas]

I'm so sorry, my sugar has been off and my brain isn't functioning all that great ATM.
The code for intersection is very similar to the difference code. You only need to add stuff to the intersect_bag when you find identical items (line 8 of my pseudocode above), and don't add anything otherwise (delete lines 16 and 19 of my pseudocode above).

sort this_bag
sort that_bag

this_i = 0
that_i = 0
while (this_i < this_bag_size) and (that_i < that_bag_size):

  if (this_bag[this_i] == that_bag[that_i]):
    intersect_bag.add(this_bag[this_i])
    this_i = this_i + 1
    that_i = that_i + 1
  else:

    /* skip the lexicographically smaller item */
    if (this_bag[this_i] < that_bag[that_i]):
      this_i = this_i + 1
    else:
      that_i = that_i + 1

Try to think through how this works.