1 #ifndef MARISA_BITVECTOR_H_ 2 #define MARISA_BITVECTOR_H_ 3 4 #include "rank.h" 5 #include "vector.h" 6 7 namespace marisa { 8 9 class BitVector { 10 public: 11 BitVector(); 12 13 void build(); 14 clear_select0s()15 void clear_select0s() { 16 select0s_.clear(); 17 } clear_select1s()18 void clear_select1s() { 19 select1s_.clear(); 20 } 21 22 void mmap(Mapper *mapper, const char *filename, 23 long offset = 0, int whence = SEEK_SET); 24 void map(const void *ptr, std::size_t size); 25 void map(Mapper &mapper); 26 27 void load(const char *filename, 28 long offset = 0, int whence = SEEK_SET); 29 void fread(std::FILE *file); 30 void read(int fd); 31 void read(std::istream &stream); 32 void read(Reader &reader); 33 34 void save(const char *filename, bool trunc_flag = true, 35 long offset = 0, int whence = SEEK_SET) const; 36 void fwrite(std::FILE *file) const; 37 void write(int fd) const; 38 void write(std::ostream &stream) const; 39 void write(Writer &writer) const; 40 push_back(bool bit)41 void push_back(bool bit) { 42 MARISA_THROW_IF(size_ == max_size(), MARISA_SIZE_ERROR); 43 if ((size_ % 32) == 0) { 44 blocks_.push_back(0); 45 } 46 if (bit) { 47 blocks_.back() |= 1U << (size_ % 32); 48 } 49 ++size_; 50 } 51 52 bool operator[](std::size_t i) const { 53 MARISA_DEBUG_IF(i >= size_, MARISA_PARAM_ERROR); 54 return (blocks_[i / 32] & (1U << (i % 32))) != 0; 55 } 56 rank0(UInt32 i)57 UInt32 rank0(UInt32 i) const { 58 MARISA_DEBUG_IF(i > size_, MARISA_PARAM_ERROR); 59 return i - rank1(i); 60 } 61 UInt32 rank1(UInt32 i) const; 62 63 UInt32 select0(UInt32 i) const; 64 UInt32 select1(UInt32 i) const; 65 size()66 std::size_t size() const { 67 return size_; 68 } empty()69 bool empty() const { 70 return blocks_.empty(); 71 } max_size()72 std::size_t max_size() const { 73 return MARISA_UINT32_MAX; 74 } total_size()75 std::size_t total_size() const { 76 return blocks_.total_size() + sizeof(size_) + ranks_.total_size() 77 + select0s_.total_size() + select1s_.total_size(); 78 } 79 80 void clear(); 81 void swap(BitVector *rhs); 82 83 private: 84 Vector<UInt32> blocks_; 85 UInt32 size_; 86 Vector<Rank> ranks_; 87 Vector<UInt32> select0s_; 88 Vector<UInt32> select1s_; 89 90 // Disallows copy and assignment. 91 BitVector(const BitVector &); 92 BitVector &operator=(const BitVector &); 93 }; 94 95 } // namespace marisa 96 97 #endif // MARISA_BITVECTOR_H_ 98