1 #ifndef MARISA_GRIMOIRE_VECTOR_BIT_VECTOR_H_ 2 #define MARISA_GRIMOIRE_VECTOR_BIT_VECTOR_H_ 3 4 #include "marisa/grimoire/vector/rank-index.h" 5 #include "marisa/grimoire/vector/vector.h" 6 7 namespace marisa { 8 namespace grimoire { 9 namespace vector { 10 11 class BitVector { 12 public: 13 #if MARISA_WORD_SIZE == 64 14 typedef UInt64 Unit; 15 #else // MARISA_WORD_SIZE == 64 16 typedef UInt32 Unit; 17 #endif // MARISA_WORD_SIZE == 64 18 BitVector()19 BitVector() 20 : units_(), size_(0), num_1s_(0), ranks_(), select0s_(), select1s_() {} 21 build(bool enables_select0,bool enables_select1)22 void build(bool enables_select0, bool enables_select1) { 23 BitVector temp; 24 temp.build_index(*this, enables_select0, enables_select1); 25 units_.shrink(); 26 temp.units_.swap(units_); 27 swap(temp); 28 } 29 map(Mapper & mapper)30 void map(Mapper &mapper) { 31 BitVector temp; 32 temp.map_(mapper); 33 swap(temp); 34 } read(Reader & reader)35 void read(Reader &reader) { 36 BitVector temp; 37 temp.read_(reader); 38 swap(temp); 39 } write(Writer & writer)40 void write(Writer &writer) const { 41 write_(writer); 42 } 43 disable_select0()44 void disable_select0() { 45 select0s_.clear(); 46 } disable_select1()47 void disable_select1() { 48 select1s_.clear(); 49 } 50 push_back(bool bit)51 void push_back(bool bit) { 52 MARISA_THROW_IF(size_ == MARISA_UINT32_MAX, MARISA_SIZE_ERROR); 53 if (size_ == (MARISA_WORD_SIZE * units_.size())) { 54 units_.resize(units_.size() + (64 / MARISA_WORD_SIZE), 0); 55 } 56 if (bit) { 57 units_[size_ / MARISA_WORD_SIZE] |= 58 (Unit)1 << (size_ % MARISA_WORD_SIZE); 59 ++num_1s_; 60 } 61 ++size_; 62 } 63 64 bool operator[](std::size_t i) const { 65 MARISA_DEBUG_IF(i >= size_, MARISA_BOUND_ERROR); 66 return (units_[i / MARISA_WORD_SIZE] 67 & ((Unit)1 << (i % MARISA_WORD_SIZE))) != 0; 68 } 69 rank0(std::size_t i)70 std::size_t rank0(std::size_t i) const { 71 MARISA_DEBUG_IF(ranks_.empty(), MARISA_STATE_ERROR); 72 MARISA_DEBUG_IF(i > size_, MARISA_BOUND_ERROR); 73 return i - rank1(i); 74 } 75 std::size_t rank1(std::size_t i) const; 76 77 std::size_t select0(std::size_t i) const; 78 std::size_t select1(std::size_t i) const; 79 num_0s()80 std::size_t num_0s() const { 81 return size_ - num_1s_; 82 } num_1s()83 std::size_t num_1s() const { 84 return num_1s_; 85 } 86 empty()87 bool empty() const { 88 return size_ == 0; 89 } size()90 std::size_t size() const { 91 return size_; 92 } total_size()93 std::size_t total_size() const { 94 return units_.total_size() + ranks_.total_size() 95 + select0s_.total_size() + select1s_.total_size(); 96 } io_size()97 std::size_t io_size() const { 98 return units_.io_size() + (sizeof(UInt32) * 2) + ranks_.io_size() 99 + select0s_.io_size() + select1s_.io_size(); 100 } 101 clear()102 void clear() { 103 BitVector().swap(*this); 104 } swap(BitVector & rhs)105 void swap(BitVector &rhs) { 106 units_.swap(rhs.units_); 107 marisa::swap(size_, rhs.size_); 108 marisa::swap(num_1s_, rhs.num_1s_); 109 ranks_.swap(rhs.ranks_); 110 select0s_.swap(rhs.select0s_); 111 select1s_.swap(rhs.select1s_); 112 } 113 114 private: 115 Vector<Unit> units_; 116 std::size_t size_; 117 std::size_t num_1s_; 118 Vector<RankIndex> ranks_; 119 Vector<UInt32> select0s_; 120 Vector<UInt32> select1s_; 121 122 void build_index(const BitVector &bv, 123 bool enables_select0, bool enables_select1); 124 map_(Mapper & mapper)125 void map_(Mapper &mapper) { 126 units_.map(mapper); 127 { 128 UInt32 temp_size; 129 mapper.map(&temp_size); 130 size_ = temp_size; 131 } 132 { 133 UInt32 temp_num_1s; 134 mapper.map(&temp_num_1s); 135 MARISA_THROW_IF(temp_num_1s > size_, MARISA_FORMAT_ERROR); 136 num_1s_ = temp_num_1s; 137 } 138 ranks_.map(mapper); 139 select0s_.map(mapper); 140 select1s_.map(mapper); 141 } 142 read_(Reader & reader)143 void read_(Reader &reader) { 144 units_.read(reader); 145 { 146 UInt32 temp_size; 147 reader.read(&temp_size); 148 size_ = temp_size; 149 } 150 { 151 UInt32 temp_num_1s; 152 reader.read(&temp_num_1s); 153 MARISA_THROW_IF(temp_num_1s > size_, MARISA_FORMAT_ERROR); 154 num_1s_ = temp_num_1s; 155 } 156 ranks_.read(reader); 157 select0s_.read(reader); 158 select1s_.read(reader); 159 } 160 write_(Writer & writer)161 void write_(Writer &writer) const { 162 units_.write(writer); 163 writer.write((UInt32)size_); 164 writer.write((UInt32)num_1s_); 165 ranks_.write(writer); 166 select0s_.write(writer); 167 select1s_.write(writer); 168 } 169 170 // Disallows copy and assignment. 171 BitVector(const BitVector &); 172 BitVector &operator=(const BitVector &); 173 }; 174 175 } // namespace vector 176 } // namespace grimoire 177 } // namespace marisa 178 179 #endif // MARISA_GRIMOIRE_VECTOR_BIT_VECTOR_H_ 180