bitset

bitSet.h

#ifndef BITSET_H
#define BITSET_H

#include<assert.h>
#include<iostream>
using namespace std;

const int DefaultSize=50;
/*
  16位无符号短整数实现位映射
  */
template<typename T>
class bitSet{
public:
    bitSet(int sz=DefaultSize);
    bitSet(const bitSet<T>& 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<T>& operator=(const bitSet<T>& R);
    bitSet<T>& operator+(const bitSet<T>& R);
    bitSet<T>& operator*(const bitSet<T>& R);
    bitSet<T>& operator-(const bitSet<T>& R);
    bool Contains(const T x);
    bool subSet(bitSet<T>& R);
    bool operator==(bitSet<T>& R);
    friend istream& operator>>(istream& in,bitSet<T>& R);
    friend ostream& operator<<(ostream& out,bitSet<T>& R){
        for(int i=0;i<R.setSize;i++){
            out << R.bitVector[i] << ",";
        }
        out << endl;
        return out;
    }

private:
    int setSize;
    int vectorSize;
    unsigned short *bitVector;
};

#endif // BITSET_H

bitSet.cpp

#include"bitSet.h"
#include<iostream>
using namespace std;

template<typename T>
bitSet<T>::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<typename T>
bitSet<T>::bitSet(const bitSet<T> &R)
{
    setSize=R.setSize;
    vectorSize=R.vectorSize;
    bitVector = new unsigned short[vectorSize];
    for(int i=0;i<R.vecterSize;++i){
        bitVector[i]=R.bitVector[i];
    }
    assert(bitVector!=NULL);
}

/*
  获得集合元素x在bitVector中相应位置的值
  */
template<typename T>
unsigned short bitSet<T>::getMember(const T x)
{
    int ad=x/16,id=x%16;
    unsigned short elem=bitVector[ad];
    return ((elem>>(15-id))%2);
}

template<typename T>
void bitSet<T>::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+=1;
    else if(temp%2==1&&v==0)
        temp-=1;
    bitVector[ad]=(temp<<(15-id))|(elem>>(id+1));
}

template<typename T>
bool bitSet<T>::addMember(const T x)
{
    assert(x>=0&&x<setSize);
    if(getMember(x)==0){
        putMember(x,0);
        return true;
    }
    return false;
}

template<typename T>
bitSet<T>& bitSet<T>::operator+(const bitSet<T>& R)
{
    assert(vectorSize==R.vecterSize);
    bitSet temp(vectorSize);
    for(int i=0;i<vectorSize;++i){
        temp.bitVector[i]=bitVector[i]|R.bitVector[i];
    }
    return temp;
}

template<typename T>
bitSet<T>& bitSet<T>::operator*(const bitSet<T>& R)
{
    assert(vectorSize==R.vecterSize);
    bitSet temp(vectorSize);
    for(int i=0;i<vectorSize;++i){
        temp.bitVector[i]=bitVector[i]&R.bitVector[i];
    }
    return temp;
}

template<typename T>
bitSet<T>& bitSet<T>::operator-(const bitSet<T>& R)
{
    assert(vectorSize==R.vecterSize);
    bitSet temp(vectorSize);
    for(int i=0;i<vectorSize;++i){
        temp.bitVector[i]=bitVector[i]&!R.bitVector[i];
    }
    return temp;
}

template<typename T>
bool bitSet<T>::Contains(const T x)
{
    assert(x>=0&&x<=setSize);
    return getMemeber(x)==1?true:false;
}

template<typename T>
bool bitSet<T>::subSet(bitSet<T> &R)
{
    assert(setSize==R.setSize);
    for(int i=0;i<vectorSize;++i){
        if(bitVector[i]&!R.bitVector[i])
            return false;
    }
    return true;
}

template<typename T>
bool bitSet<T>::operator==(bitSet<T>& R)
{
    assert(setSize==R.setSize);
    for(int i=0;i<setSize;++i){
        if(bitVector[i]!=R.bitVector[i])
            return false;
    }
    return true;
}