Category : C++ Source Code
Archive   : INTSET.ZIP
Filename : INTSET.CPP

 
Output of file : INTSET.CPP contained in archive : INTSET.ZIP

// Module intset

#include





/* Class IntSet

Datainvariant:

set = pointer to the start of the array of IntSet_Bits in memory
max = maximum value of an element in the set
<= sizeof(IntSet_Bits)*8*maxvalue(IntSet_Lim)
cardinality = |set|
limit = max / Nbits +1
(Ai: 0 <= i <= max: (set.i = 0) V (set.i = 1))
after constructor: (Ai: 0 <= i <= max: !member())

*/


const Nbytes = sizeof(IntSet_Bits);
const Nbits = Nbytes*8;
const Nshifts = 4; // = log2(Nbits), 2**Nshifts = Nbits

#if Nbits != 16
#error Nshifts is wrong
#endif


// Constructor(s):

IntSet::IntSet( IntSet_Elem m )
{
max = m;
limit = (max >> Nshifts) +1; // pre => can't lose significant digits
set = new IntSet_Bits[limit];
SetEmpty();
}


// Destructor:

IntSet::~IntSet()
{
delete set;
}


// Modifiers:

IntSet& IntSet::Insert( IntSet_Elem e )
{
IntSet_Bits* p = set + (e >> Nshifts);
IntSet_Bits bit = 1 << (e & (Nbits-1));
if (*p & bit) return *this;
*p |= bit;
cardinality++;
return *this;
}

IntSet& IntSet::Del( IntSet_Elem e )
{
IntSet_Bits* p = set + (e >> Nshifts);
IntSet_Bits bit = 1 << (e & (Nbits-1));
if (*p & bit) {
*p &= ~bit;
cardinality--;
}
return *this;
}

IntSet& IntSet::Assign( const IntSet& b )
{
IntSet_Bits *pa = set;
IntSet_Bits *pb = b.set;
cardinality = b.cardinality;
for(IntSet_Lim i = limit; i; i--)
*pa++ = *pb++;
return *this;
}

IntSet& IntSet::Complement( const IntSet& b )
{
IntSet_Bits *pa = set;
IntSet_Bits *pb = b.set;
cardinality = max+1 - b.cardinality;
for(IntSet_Lim i = limit; i; i--)
*pa++ = ~*pb++;
return *this;
}


// Selectors:

int IntSet::Member( IntSet_Elem e ) const
{
return (*(set + (e >> Nshifts)) & (1 << (e & (Nbits-1)))) != 0;
/*
IntSet_Bits* p = set + (e >> Nshifts);
IntSet_Bits bit = 1 << (e & (Nbits-1));
return (*p & bit) != 0;
*/
}

int IntSet::eq( const IntSet& b ) const
{
if (Card() != b.Card()) return 0;
IntSet_Bits *pa = set;
IntSet_Bits *pb = b.set;
for(IntSet_Lim i = limit; i; i--)
if (*pa++ != *pb++) return 0;
return 1;
}

int IntSet::Sub( const IntSet& b ) const
{
if (Card() > b.Card()) return 0;
IntSet_Bits* pa = set;
IntSet_Bits* pb = b.set;
for(IntSet_Lim i = limit; i; i--,pa++,pb++)
if ((*pa & *pb) != *pa) return 0;
return 1;
}

int IntSet::eqVneVsubsuper( const IntSet& b ) const
{
int rel = 0;
IntSet_Bits* pa = set;
IntSet_Bits* pb = b.set;
for(IntSet_Lim i = limit; i; i--,pa++,pb++) {
IntSet_Bits intersection = *pa & *pb;
if (intersection != *pa) rel |= 2;
if (intersection != *pb) rel |= 1;
if (rel == 3) return 1;
}
if (rel) return 2; else return 0;
}

int IntSet::ArelB( const IntSet& b ) const
{
int rel = 0;
IntSet_Bits* pa = set;
IntSet_Bits* pb = b.set;
for(IntSet_Lim i = limit; i; i--,pa++,pb++) {
IntSet_Bits intersection = *pa & *pb;
if (intersection) rel |= 4;
if (intersection != *pa) rel |= 2;
if (intersection != *pb) rel |= 1;
if (rel == 7) return 4;
}
if (rel < 4) return rel;
return rel-4;
}


// Utilities:

IntSet& IntSet::SetEmpty()
{
IntSet_Bits *p = set;
cardinality = 0;
for(IntSet_Lim i = limit; i; i--)
*p++ = 0;
return *this;
}


/* (Ai: 0 <= i < 256: nbits.i = (Nj: 0 <= j < 8: i & (1 << j))
= number of bits in the number i) */
static unsigned char nbits[] =
{
/* 0- 15 */ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
/* 16- 31 */ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
/* 32- 47 */ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
/* 48- 63 */ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
/* 64- 79 */ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
/* 80- 95 */ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
/* 96-111 */ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
/* 112-127 */ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
/* 128-143 */ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
/* 144-159 */ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
/* 160-175 */ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
/* 176-191 */ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
/* 192-207 */ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
/* 208-223 */ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
/* 224-239 */ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
/* 240-255 */ 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

IntSet& IntSet::Intersection( const IntSet& a, const IntSet& b )
{
union {
IntSet_Bits tmp;
unsigned char n[Nbytes];
};

IntSet_Bits *pa = a.set;
IntSet_Bits *pb = b.set;
IntSet_Bits *pc = set;
cardinality = 0;
for(IntSet_Lim i = limit; i; i--) {
*pc++ = tmp = *pa++ & *pb++;
int j = Nbytes; while(j) cardinality += nbits[n[--j]];
// for( ; tmp; tmp >>= 1) if (tmp & 1) cardinality++;
}
return *this;
}

IntSet& IntSet::Union( const IntSet& a, const IntSet& b )
{
union {
IntSet_Bits tmp;
unsigned char n[Nbytes];
};

IntSet_Bits *pa = a.set;
IntSet_Bits *pb = b.set;
IntSet_Bits *pc = set;
cardinality = 0;
for(IntSet_Lim i = limit; i; i--) {
*pc++ = tmp = *pa++ | *pb++;
int j = Nbytes; while(j) cardinality += nbits[n[--j]];
// for( ; tmp; tmp >>= 1) if (tmp & 1) cardinality++;
}
return *this;
}

IntSet& IntSet::Eor( const IntSet& a, const IntSet& b )
{
union {
IntSet_Bits tmp;
unsigned char n[Nbytes];
};

IntSet_Bits *pa = a.set;
IntSet_Bits *pb = b.set;
IntSet_Bits *pc = set;
cardinality = 0;
for(IntSet_Lim i = limit; i; i--) {
*pc++ = tmp = *pa++ ^ *pb++;
int j = Nbytes; while(j) cardinality += nbits[n[--j]];
// for( ; tmp; tmp >>= 1) if (tmp & 1) cardinality++;
}
return *this;
}

IntSet& IntSet::Minus( const IntSet& a, const IntSet& b )
{
union {
IntSet_Bits tmp;
unsigned char n[Nbytes];
};

IntSet_Bits *pa = a.set;
IntSet_Bits *pb = b.set;
IntSet_Bits *pc = set;
cardinality = 0;
for(IntSet_Lim i = limit; i; i--) {
*pc++ = tmp = *pa++ & ~*pb++;
int j = Nbytes; while(j) cardinality += nbits[n[--j]];
// for( ; tmp; tmp >>= 1) if (tmp & 1) cardinality++;
}
return *this;
}

IntSet_Elem IntSet::Min() const
{
if (Empty()) return max+1;
IntSet_Bits *p = set;
while (*p == 0) p++;
IntSet_Elem e = (p - set) << Nshifts;
IntSet_Bits tmp = *p;
for( ; tmp; tmp >>= 1, e++)
if (tmp & 1) return e;

return 0; // to remove warning
}

IntSet_Elem IntSet::DeleteMin()
{
if (Empty()) return max+1;
IntSet_Elem e = Min();
Del(e);
return e;
}

IntSet_Elem IntSet::NextMember( IntSet_Elem e ) const
{
if (e > max) return max+1;
IntSet_Bits *p = set + (e >> Nshifts);
int i = e & (Nbits-1);
IntSet_Bits tmp = *p >> i;
for( ; i != Nbits; e++, i++, tmp >>= 1 )
if (tmp & 1) return e;
for( p++; (e <= max) && (*p == 0); e+= Nbits, p++ );
if (e > max) return max+1;
tmp = *p;
for( ; tmp; tmp >>= 1, e++)
if (tmp & 1) return e;

return 0; // to remove warning
}




#ifdef TEST_INTSET

#include
#include


int main()
{
cout << "\nTest of intset module\n" << flush;

const long max = 80000l;
unsigned long i;
IntSet a(max),b(max);
IntSet c(100),d(100),e(100);

cout << "test constructors\n";
assert(a.Constructed());
assert(b.Constructed());

cout << "test if empty\n";
for(i = 0; i != max+1; i++)
assert(!a.Member(i));

cout << "insert every element, empty it and check if empty\n";
for(i = 0; i != max+1; i++) a.Insert(i);
a.SetEmpty();
for(i = 0; i != max+1; i++)
assert(!a.Member(i));

/*
cout << "test SetEmpty 500 times\n";
for(i = 0; i != 500; i++) a.SetEmpty();
cout << "finished setempty 500 times\n";
*/
a.Insert(501); a.Insert(0); a.Insert(max);
cout << "0,501," << max << " shall be members:\n";
for(i = 0; i != max+1; i++)
if (a.Member(i)) cout << i << " member\n";

a.Del(0); a.Del(501);
cout << max << " shall be member:\n";
for(i = 0; i != max+1; i++)
if (a.Member(i)) cout << i << " member\n";
a.SetEmpty();
cout << "Card of set shall be 0 and set shall be empty\n";
cout << "Card: " << a.Card() << endl;
assert(a.Empty());

cout << "test a == b with a = b = {3,5,max}\n";
a.Insert(3); a.Insert(5); a.Insert(max);
b.Insert(3); b.Insert(5); b.Insert(max);
assert(a == b);
cout << "test a == b with a != b\n";
a.Del(max);
assert(a != b);

a.SetEmpty();
cout << "Min shall be " << (max+1) << ", Min: " << a.Min() << endl;
a.Insert(365); a.Insert(366);
cout << "Card shall be 2, Card: " << a.Card() << endl;
assert(a.Card() == 2);
cout << "Min shall be 365, Min: " << a.Min() << endl;
a.Insert(365); a.Insert(366);
cout << "Card shall be 2, Card: " << a.Card() << endl;
assert(a.Card() == 2);
a.Del(365); a.Del(365);
cout << "Card shall be 1, Card: " << a.Card() << endl;
assert(a.Card() == 1);
cout << "366 shall be member, 366 is ";
if (a.Member(366)) cout << "member\n"; else cout << "not member";
assert(a.Member(366));
cout << "Min shall be 366, Min: " << a.Min() << endl;

c.Insert(5); c.Insert(52); c.Insert(53);
d.Insert(51); d.Insert(52); d.Insert(53);
cout << "\nArelB shall be 4, is: " << c.ArelB(d) << endl;
d.Del(51);
cout << "ArelB shall be 2, is: " << c.ArelB(d) << endl;
c.Del(5);
cout << "ArelB shall be 0, is: " << c.ArelB(d) << endl;
d.SetEmpty(); d.Insert(14); d.Insert(15);
cout << "ArelB shall be 3, is: " << c.ArelB(d) << endl;

c.SetEmpty(); d.SetEmpty();
c.Insert(16); c.Insert(19); c.Insert(75);
d.Insert(16); d.Insert(22); d.Insert(75);
cout << "\nIntersection shall be 16,75:\n";
e.Intersection(c,d);
for(i = 0; i != 101; i++)
if (e.Member(i)) cout << i << " member\n";
cout << "Card: " << e.Card() << endl;
cout << "\nUnion shall be 16,19,22,75:\n";
e.Union(c,d);
for(i = 0; i != 101; i++)
if (e.Member(i)) cout << i << " member\n";
cout << "Card: " << e.Card() << endl;
cout << "\nEor shall be 19,22\n";
e.Eor(c,d);
for(i = 0; i != 101; i++)
if (e.Member(i)) cout << i << " member\n";
cout << "Card: " << e.Card() << endl;
cout << "\nMinus shall be 19:\n";
e.Minus(c,d);
for(i = 0; i != 101; i++)
if (e.Member(i)) cout << i << " member\n";
cout << "Card: " << e.Card() << endl;

a.SetEmpty();
a.Insert(67); a.Insert(365);
cout << "\ntesting NextMember\nshall get 67,67,365,";
cout << (max+1) << ',' << (max+1) << endl;
i = a.NextMember(0); cout << i << endl;
i = a.NextMember(i); cout << i << endl;
i = a.NextMember(i+1); cout << i << endl;
i = a.NextMember(i+1); cout << i << endl;
i = a.NextMember(max+5); cout << i << endl;

cout << "\ntesting Complement\n";
c.SetEmpty(); d.SetEmpty();
d.Insert(22); c.Insert(34); c.Insert(100);
d.Complement(c);

int card = 0;
for(i = 0; i != 101; i++) {
if (d.Member(i)) card++;
assert(c.Member(i) != d.Member(i));
}
assert(card == d.Card());
cout << "Complement ok\n";

cout << "\ntesting =\n";
a = b;
assert(a == b);

return 0;
}


#endif