Sign in to follow this  
Vortez

Something odd about set_difference()

Recommended Posts

Hi, i've just refactored a class that originally used a STL set in order to keep track of the possibles values for each cell in my sudoku solver, by using a WORD instead to store values from 1 to 9, since i used the exact same interface(almost), no code changes we're required elsewhere.

 

Everything worked fine the first shoot except for the set difference operation. I got it to work, but something is puzzling me. First, let me show you the old code

/***************************************************************************************************************/
// Perform a difference operation on the set
/***************************************************************************************************************/
Possibles Possibles::operator-=(Possibles &s)
{
	Possibles TmpSet = *this;
	possibles.clear();

	set_difference(TmpSet.GetSet()->begin(), TmpSet.GetSet()->end(), s.GetSet()->begin(), s.GetSet()->end(), inserter(possibles, possibles.begin()));
	return *this;
}

/***************************************************************************************************************/
// Perform an union operation on the set
/***************************************************************************************************************/
Possibles Possibles::operator+=(Possibles &s)
{
	Possibles TmpSet = *this;
	possibles.clear();

	set_union(TmpSet.GetSet()->begin(), TmpSet.GetSet()->end(), s.GetSet()->begin(), s.GetSet()->end(), inserter(possibles, possibles.begin()));
	return *this;
}

/***************************************************************************************************************/
// Perform an intersection operation on the set
/***************************************************************************************************************/
Possibles Possibles::operator|=(Possibles &s)
{
	Possibles TmpSet = *this;
	possibles.clear();

	set_intersection(TmpSet.GetSet()->begin(), TmpSet.GetSet()->end(), s.GetSet()->begin(), s.GetSet()->end(), inserter(possibles, possibles.begin()));
	return *this;
}

(NOTE: not sure i used the right operator sign...)

 

Then, when i emulated this with a WORD, the code looked like this:

/***************************************************************************************************************/
// Perform an union operation on the set
/***************************************************************************************************************/
Possibles Possibles::operator+=(Possibles &s)
{
	p |= s.Get();
	return *this;
}

/***************************************************************************************************************/
// Perform a difference operation on the set
/***************************************************************************************************************/
Possibles Possibles::operator-=(Possibles &s)
{
	p ^= s.Get();
	return *this;
}

/***************************************************************************************************************/
// Perform an intersection operation on the set
/***************************************************************************************************************/
Possibles Possibles::operator|=(Possibles &s)
{
	p &= s.Get();
	return *this;
}

All worked fine except the -= operator.

 

For example, the first code only added the difference IN THE FIRST SET instead of both (wich is the required behavior for my game), but the 2nd example added the difference in BOTH set, wich is normal but not what i wanted. So, to fix it, i had to write some ugly code like this:

/***************************************************************************************************************/
// Perform a difference operation on the set
/***************************************************************************************************************/
Possibles Possibles::operator-=(Possibles &s)
{
	WORD w1 = p;
	WORD w2 = s.Get();
	WORD res = 0;

	for(int i = 0; i < 9; i++){
		if(((w1 & (1<<i)) > 0) && ((w2 & (1<<i)) == 0))
			res |= (1<<i);
	}
	p = res;

	return *this;
}

That way, everything work fine except the code is not like the other 2 functions, and i was simply wondering why is that? To be more clear, why can i use simple bitwise operation for 2 of the 3 operation but not the 3rd???

 

EDIT: I might not be able to respond to this thread for a few days.

Edited by Vortez

Share this post


Link to post
Share on other sites

You can immediately conclude that using XOR is wrong because set_difference(A,B) != set_difference(B,A), but xor(A,B) == xor(B,A).

 

What XOR does is that xor(A,B) toggles the bits in A using the bits in B, or vice versa; in any case, that operation is symmetric whether you use A to toggle B or B to toggle A. The problem is that bits in A will not only reset bits in B, but also set them if they were already reset. From the set's point of view, that adds elements to the set that wasn't there to begin with. The difference can only remove elements but never add.

 

In terms of the XOR operation, you want to only reset bits that are set, but never set bits that are reset. Use the AND operator to clear out bits from the second operand that corresponds to reset bits in the first operand, and then apply the XOR on the remaining bits to ensure that only set bits can be toggled.

Edited by Brother Bob

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this