#include
#include
#include
using namespace std;
const int DefaultSize = 50;
template
class bitSet
{
public:
bitSet(int sz = DefaultSize);
bitSet(const bitSet& R);
~bitSet(){delete []bitVector;}
void makeEmpty()
{ for (int i = 0; i < vectorSize; i++) bitVector[i] = 0;}
unsigned short getMember(const T x);
void putMember(const T x, unsigned short v);
bool addMember(const T x);
bool delMember(const T x);
bitSet& operator + (const bitSet& R);
bitSet& operator * (const bitSet& R);
bitSet& operator - (const bitSet& R);
bool Contains(const T x);
bool subSet(bitSet& R);
private:
int setSize;
int vectorSize;
unsigned short *bitVector;
};
template
bitSet::bitSet(int sz):setSize(sz)
{
assert(setSize > 0);
vectorSize = (setSize+15)>>4;
bitVector = new unsigned short[vectorSize];
assert(bitVector != NULL);
for(int i=0; i<vectorSize; i++)bitVector[i] = 0;
};
template
bitSet::bitSet(const bitSet& R)
{
setSize = R.setSize;
vectorSize = R.vectorSize;
bitVector = new unsigned short[vectorSize];
assert(bitVector != NULL);
for (int i = 0; i < vectorSize; i++)
bitVector[i] = R.bitVector[i];
};
template
unsigned short bitSet::getMember(const T x)
{ int ad = x/16, id = x%16;
unsigned short elem = bitVector[ad];
return ((elem >>(15-id)) %2);
}
template
void bitSet::putMember(const T x, unsigned short v)
{ int ad = x/16, id = x%16;
unsigned short elem = bitVector[ad];
unsigned short temp = elem>>(15-id); elem=elem<<(id+1);
if (temp%2 == 0 && v == 1) temp = temp+1;
else if (temp%2 == 1 && v == 0) temp = temp - 1;
bitVector[ad] = (temp<<(15-id)) | (elem>>(id+1));
};
template
bool bitSet::addMember(const T x)
{ assert(x >= 0 && x < setSize);
if (getMember(x) == 0)
{ putMember(x,1); return true;}
return false;
};
template
bool bitSet::delMember(const T x)
{ assert(x >= 0 && x < setSize);
if (getMember(x) == 1)
{ putMember(x,0); return true;}
return false;
}
template
bitSet& bitSet::operator + (const bitSet& R)
{ assert(vectorSize == R.vectorSize);
bitSet temp;
for (int i = 0; i < vectorSize; i++)
temp.bitVector[i] = bitVector[i] | R.bitVector[i];
return temp;
}
template
bitSet& bitSet::operator * (const bitSet& R)
{ assert(vectorSize == R.vectorSize);
bitSet temp(vectorSize);
for (int i = 0; i < vectorSize; i++)
temp.bitVector[i] = bitVector[i] & R.bitVector[i];
return temp;
}
template
bitSet& bitSet::operator - (const bitSet& R)
{ assert(vectorSize == R.vectorSize);
bitSet temp(vectorSize);
for (int i = 0; i < vectorSize; i++)
temp.bitVector[i] = bitVector[i] & !R.bitVector[i];
return temp;
}
template
bool bitSet::Contains(const T x)
{ assert(x >= 0 && x <= setSize);
return (getMember(x) == 1)? true: false;
}
int main()
{
bitSet a;
bitSet b;
return 0;
}