bitset

bitmap O(1)

#ifndef BIT_MAP_H_
#define BIT_MAP_H_
#include <stdlib.h>

template <typename RANK = int>
class BitMap
{
public:
    BitMap(RANK n) :
        capacity_(n),
        top_(0),
        count_(0)
    {
        vector_ = (RANK *)malloc(sizeof(RANK) * n);
        stack_ = (RANK *)malloc(sizeof(RANK) * n);
    }

    ~BitMap()
    {
        free(vector_);   
        free(stack_);
    }

    void set(RANK k)
    {
        if (test(k))    return;

        ++count_;

        if (!erased(k)) 
            vector_[k] = top_++;

        stack_[vector_[k]] = k;
    }

    bool test(RANK k) const 
    {
        return vaild(vector_[k]) && (stack_[vector_[k]] == k); 
    }

    void clear(RANK k)
    {
        if (!test(k))  return;

        --count_;
        stack_[vector_[k]] = -1 - k;
    }

    void clear()
    {
        top_ = 0;
        count_ = 0;
    }

    RANK count() const 
    {
        return count_;
    }

protected:
    // 判断 r 是否是栈中合法位置
    bool vaild(RANK r) const { return 0 <= r && r < top_; }
    // 判断 k 是不是曾经被标记过后来又删除了
    bool erased(RANK k) const { return vaild(vector_[k]) && (stack_[ vector_[k] ] + 1 + k == 0); }   // 约定删除后 栈中存储的k替换为 -1 - k

private:
    RANK *vector_;      // set(k)时，vector_[k]存储 k 在栈中的索引, vector_ 与每个 k 一一对应
    RANK capacity_;      
    RANK *stack_;       // set(k)时，k入栈
    RANK top_;          // 栈顶指针
    RANK count_;        // 记录总共有多少位被标记了.
};



#endif

bitset.h

#ifndef BIT_SET_H_
#define BIT_SET_H_ 
#include <unistd.h>
#include <string.h>

template <typename BLOCK = unsigned long>
class BitSet
{
public:
    typedef BLOCK block_type;
    typedef size_t size_type;

public:
    BitSet(size_type n):
        num_bits_(n),
        num_blocks_(n % BITS_PER_BLOCK_ == 0 ? 
                (n / BITS_PER_BLOCK_) : (n / BITS_PER_BLOCK_ + 1) )
    {
        blocks_ = new block_type[num_blocks_]();    // value initialization
#ifdef BITSET_COUNT_O1_
        num_bits_set_ = 0;
#endif
    }
    
    ~BitSet()
    {
        delete []blocks_;
    }

    size_type size() const {return num_bits_; }

    // 设置某位
    void set(size_type pos)        //TODO assert(pos < n)
    {
#ifdef BITSET_COUNT_O1_
        if (!test(pos)) ++num_bits_set_; 
#endif

        blocks_[block_index(pos)] |= bit_mask(pos);
    }

    // 清零某位
    void reset(size_type pos)
    {
#ifdef BITSET_COUNT_O1_
        if (test(pos)) --num_bits_set_;
#endif
        blocks_[block_index(pos)] &= ~bit_mask(pos);
    }

    // 测试某位是否为1
    bool test(size_type pos) const
    {
        return (blocks_[block_index(pos)] & bit_mask(pos)) != 0; 
    }

    // 所有位清零
    void clear()                
    {
#ifdef BITSET_COUNT_O1_
        num_bits_set_ = 0;
#endif
        memset(blocks_, 0, num_blocks_ * sizeof(block_type));
    }
   
    // 返回有多少位被设置
    size_type count() const
    {
#ifdef BITSET_COUNT_O1_
        return num_bits_set_;
#else
        size_type cnt = 0;

        for (int i = 0; i < num_bits_; ++i)
            if (test(i)) ++cnt;
                
        return cnt;  
#endif
    }
    
    void dump(char *file) {
        FILE *fp = fopen(file, "w");                                                                                                                
        fwrite(blocks_, sizeof(block_type), num_blocks_, fp);
        fclose(fp);
    }
    
    void load(char *file) {
        FILE *fp = fopen(file, "r");
        fread(blocks_, sizeof(block_type), num_blocks_, fp);
        fclose(fp);
    }

private:
    static size_type block_index(size_type pos) {return pos / BITS_PER_BLOCK_; }
    static size_type bit_index(size_type pos) {return pos % BITS_PER_BLOCK_;}
    static block_type bit_mask(size_type pos) { return BLOCK(1) << bit_index(pos); }

private:
    static const size_type BITS_PER_BLOCK_ = sizeof(block_type) * 8;

    const size_type num_bits_;        
    block_type *blocks_;
    const size_type num_blocks_;
#ifdef BITSET_COUNT_O1_
    size_type num_bits_set_;
#endif
};


#endif