bit-vector.hpp

Go to the documentation of this file.

#if !defined(HSDS_BIT_VECTOR_H_)
#define HSDS_BIT_VECTOR_H_

#include <vector>
#include <iostream>
#include <algorithm>
#include <stdint.h>
#include "hsds/vector.hpp"
#include "hsds/rank-index.hpp"

#if defined(_MSC_VER)

#define FORCE_INLINE    __forceinline

#else

#define FORCE_INLINE    inline __attribute__((always_inline))

#endif

namespace hsds {

namespace {
const uint32_t S_BLOCK_SIZE = 64;
const uint32_t L_BLOCK_SIZE = 512;
const uint32_t BLOCK_RATE = 8;

const char* const E_OUT_OF_RANGE = "Out of range access";
const char* const E_SAVE_FILE = "Failed to save the bit vector.";
const char* const E_LOAD_FILE = "Failed to read file. File format is invalid.";
}

const uint64_t NOT_FOUND = 0xFFFFFFFFFFFFFFFF;

// forward declaration
class Exception;
class PopCount;
class RankIndex;

class BitVector {
public:

    BitVector();

    BitVector(uint64_t size);

    virtual ~BitVector();

    void clear() {
        BitVector().swap(*this);
    }

    bool operator[](uint64_t i) const;

    void set(uint64_t i, bool b = true);

    void push_back(bool b);

    void push_back_bits(uint64_t x, uint64_t len);

    uint64_t get_bits(uint64_t pos, uint64_t len) const;

    void build(bool enable_faster_select1 = false, bool enable_faster_select0 = false);

    FORCE_INLINE uint64_t size() const {
        return size_;
    }

    FORCE_INLINE uint64_t size(bool b) const {
        return b ? (num_of_1s_) : (size_ - num_of_1s_);
    }

    FORCE_INLINE bool empty() const {
        return size_ == 0;
    }

    FORCE_INLINE  uint64_t rank(uint64_t i, bool b = true) const {
        return b ? rank1(i) : rank0(i);
    }

    uint64_t rank0(uint64_t i) const;

    uint64_t rank1(uint64_t i) const;

    FORCE_INLINE  uint64_t select(uint64_t x, bool b = true) const {
        return b ? select1(x) : select0(x);
    }

    uint64_t select0(uint64_t x) const;

    uint64_t select1(uint64_t x) const;

    void save(std::ostream &os) const throw (hsds::Exception);

    void load(std::istream &is) throw (hsds::Exception);

    uint64_t map(void* ptr, uint64_t size) throw (hsds::Exception);
    
    void swap(BitVector &x);

private:
    typedef uint64_t block_type;
    typedef hsds::Vector<block_type> blocks_type;
    typedef hsds::Vector<RankIndex> rank_dict_type;
    typedef hsds::Vector<uint32_t> select_dict_type;

    blocks_type blocks_;                
    rank_dict_type rank_table_;         
    select_dict_type select0_table_;    
    select_dict_type select1_table_;    
    uint64_t size_;                     
    uint64_t num_of_1s_;                

    // Disable assingment operator
    BitVector &operator=(const BitVector &);
};

}

#endif /* !defined(HSDS_BIT_VECTOR_H_) */