1. Review set_iterate2. It shows how to construct the union of two sets.

  2. Discuss how you would construct the intersection of two counters lists. The intersection is comprised of nodes that are present in both lists. If a node is present in both lists, for today (and Lab 6), define the count in the resulting intersection list to be the minimum of the counts of the two nodes. For a counters node with a key that does not exist in both sets, we set its count to 0 in the intersection result.

  3. Copy the starter code intersect to your cs50/ directory after logging to the plank server: 
    $ cp -r $loc/activities/day22/intersect/ .

    Here counters_intersect.c creates two dummy counters lists. Your task is to complete the counters_intersect() function to perform counters intersection.

  4. Once you complete counters_intersect(), you can compile and run the code as below: 
    $ mygcc -o intersect counters_intersect.c libcs50/libcs50-given.a 
$ ./intersect 
{3=2, 4=0, 5=1, 7=3, }

    Hint: Make sure to use the counters_iterate() function. Below is a reminder of how counters_iterate() was implemented:

/**************** counters_iterate() ****************/
void
counters_iterate(counters_t *ctrs, void *arg,
		 void (*itemfunc)(void *arg, const int key, int count))
{
	if (ctrs != NULL && itemfunc != NULL) {
		// scan the counters
		for (countersnode_t *node = ctrs->head; node != NULL; node = node->next) {
			(*itemfunc)(arg, node->key, node->count);
		}
	}
}

You will need this for Lab 6’s AND operator!

Solution

Intersection is tricky (and inefficient!) with the functions available in the counters module. To accomplish an intersection of two counters, we need pseudocode like this:

   result = counters_new()
   for each (key,item) in c1
     if key found in c2
        add (key,item) to result
     else
        add (key, 0) to result

That second line is like calling counters_iterate(c1, ...), but then how does its helper function accomplish the contents of that loop? It needs access to both c2 and result. Remember how a previous lecture passed two sets into an iterator and hence into the helper function? We can do the same here; declare a small struct to hold pointers to both result and another.

 struct twocts { counters_t *result, *another } ; //store result in first counter
 struct twocts args = { c1, c2 };
 counters_iterate(c1, &args, intersect_helper);

The pointer to args will pass through counters_iterate and be available to intersect_helper and thus that function can implement remainder of our pseudocode above.

Solution

counters_intersect-solution.c