1 #include <cstdlib> 2 #include <ctime> 3 #include <sstream> 4 #include <string> 5 #include <vector> 6 7 #include <marisa/vector.h> 8 #include <marisa/intvector.h> 9 #include <marisa/bitvector.h> 10 11 #include "assert.h" 12 13 namespace { 14 15 void TestVector() { 16 TEST_START(); 17 18 std::vector<int> values; 19 for (std::size_t i = 0; i < 1000; ++i) { 20 values.push_back(std::rand()); 21 } 22 23 marisa::Vector<int> vec; 24 25 ASSERT(vec.max_size() == MARISA_UINT32_MAX); 26 ASSERT(vec.size() == 0); 27 ASSERT(vec.capacity() == 0); 28 ASSERT(!vec.fixed()); 29 ASSERT(vec.empty()); 30 ASSERT(vec.total_size() == sizeof(marisa::UInt32)); 31 32 for (std::size_t i = 0; i < values.size(); ++i) { 33 vec.push_back(values[i]); 34 ASSERT(vec[i] == values[i]); 35 ASSERT(static_cast<const marisa::Vector<int> &>(vec)[i] == values[i]); 36 } 37 38 ASSERT(vec.size() == values.size()); 39 ASSERT(vec.capacity() >= vec.size()); 40 ASSERT(!vec.empty()); 41 ASSERT(vec.total_size() == sizeof(marisa::UInt32) 42 + ((sizeof(int) * values.size()))); 43 44 ASSERT(static_cast<const marisa::Vector<int> &>(vec).front() 45 == values.front()); 46 ASSERT(static_cast<const marisa::Vector<int> &>(vec).back() 47 == values.back()); 48 ASSERT(vec.front() == values.front()); 49 ASSERT(vec.back() == values.back()); 50 51 vec.shrink(); 52 53 ASSERT(vec.size() == values.size()); 54 ASSERT(vec.capacity() == vec.size()); 55 for (std::size_t i = 0; i < values.size(); ++i) { 56 ASSERT(vec[i] == values[i]); 57 ASSERT(static_cast<const marisa::Vector<int> &>(vec)[i] == values[i]); 58 } 59 60 vec.save("vector-test.dat"); 61 vec.clear(); 62 63 ASSERT(vec.empty()); 64 ASSERT(vec.capacity() == 0); 65 66 marisa::Mapper mapper; 67 vec.mmap(&mapper, "vector-test.dat"); 68 69 ASSERT(mapper.is_open()); 70 ASSERT(vec.size() == values.size()); 71 ASSERT(vec.capacity() == 0); 72 ASSERT(vec.fixed()); 73 ASSERT(!vec.empty()); 74 ASSERT(vec.total_size() == sizeof(marisa::UInt32) 75 + ((sizeof(int) * values.size()))); 76 77 for (std::size_t i = 0; i < values.size(); ++i) { 78 ASSERT(static_cast<const marisa::Vector<int> &>(vec)[i] == values[i]); 79 } 80 81 vec.clear(); 82 vec.load("vector-test.dat"); 83 84 ASSERT(vec.size() == values.size()); 85 ASSERT(vec.capacity() == vec.size()); 86 ASSERT(!vec.fixed()); 87 ASSERT(!vec.empty()); 88 ASSERT(vec.total_size() == sizeof(marisa::UInt32) 89 + ((sizeof(int) * values.size()))); 90 91 for (std::size_t i = 0; i < values.size(); ++i) { 92 ASSERT(vec[i] == values[i]); 93 ASSERT(static_cast<const marisa::Vector<int> &>(vec)[i] == values[i]); 94 } 95 96 vec.clear(); 97 98 vec.push_back(0); 99 ASSERT(vec.capacity() == 1); 100 vec.push_back(1); 101 ASSERT(vec.capacity() == 2); 102 vec.push_back(2); 103 ASSERT(vec.capacity() == 4); 104 vec.resize(5); 105 ASSERT(vec.capacity() == 8); 106 vec.resize(100); 107 ASSERT(vec.capacity() == 100); 108 109 vec.fix(); 110 ASSERT(vec.fixed()); 111 EXCEPT(vec.fix(), MARISA_STATE_ERROR); 112 EXCEPT(vec.push_back(0), MARISA_STATE_ERROR); 113 EXCEPT(vec.resize(0), MARISA_STATE_ERROR); 114 EXCEPT(vec.reserve(0), MARISA_STATE_ERROR); 115 116 TEST_END(); 117 } 118 119 void TestIntVector() { 120 TEST_START(); 121 122 marisa::IntVector vec; 123 124 ASSERT(vec.num_bits_per_int() == 0); 125 ASSERT(vec.mask() == 0); 126 ASSERT(vec.size() == 0); 127 ASSERT(vec.empty()); 128 ASSERT(vec.total_size() == sizeof(marisa::UInt32) * 4); 129 130 marisa::Vector<marisa::UInt32> values; 131 vec.build(values); 132 133 ASSERT(vec.num_bits_per_int() == 1); 134 ASSERT(vec.mask() == 1); 135 ASSERT(vec.size() == 0); 136 ASSERT(vec.empty()); 137 ASSERT(vec.total_size() == sizeof(marisa::UInt32) * 4); 138 139 values.push_back(0); 140 vec.build(values); 141 142 ASSERT(vec.num_bits_per_int() == 1); 143 ASSERT(vec.mask() == 1); 144 ASSERT(vec.size() == 1); 145 ASSERT(!vec.empty()); 146 ASSERT(vec.total_size() == sizeof(marisa::UInt32) * 5); 147 ASSERT(vec[0] == 0); 148 149 values.push_back(255); 150 vec.build(values); 151 152 ASSERT(vec.num_bits_per_int() == 8); 153 ASSERT(vec.mask() == 0xFF); 154 ASSERT(vec.size() == 2); 155 ASSERT(vec[0] == 0); 156 ASSERT(vec[1] == 255); 157 158 values.push_back(65536); 159 vec.build(values); 160 161 ASSERT(vec.num_bits_per_int() == 17); 162 ASSERT(vec.mask() == 0x1FFFF); 163 ASSERT(vec.size() == 3); 164 ASSERT(vec[0] == 0); 165 ASSERT(vec[1] == 255); 166 ASSERT(vec[2] == 65536); 167 168 vec.save("vector-test.dat"); 169 vec.clear(); 170 171 ASSERT(vec.num_bits_per_int() == 0); 172 ASSERT(vec.mask() == 0); 173 ASSERT(vec.size() == 0); 174 175 marisa::Mapper mapper; 176 vec.mmap(&mapper, "vector-test.dat"); 177 178 ASSERT(mapper.is_open()); 179 ASSERT(vec.num_bits_per_int() == 17); 180 ASSERT(vec.mask() == 0x1FFFF); 181 ASSERT(vec.size() == 3); 182 ASSERT(vec[0] == 0); 183 ASSERT(vec[1] == 255); 184 ASSERT(vec[2] == 65536); 185 186 vec.clear(); 187 vec.load("vector-test.dat"); 188 189 ASSERT(vec.num_bits_per_int() == 17); 190 ASSERT(vec.mask() == 0x1FFFF); 191 ASSERT(vec.size() == 3); 192 ASSERT(vec[0] == 0); 193 ASSERT(vec[1] == 255); 194 ASSERT(vec[2] == 65536); 195 196 values.clear(); 197 for (std::size_t i = 0; i < 500; ++i) { 198 values.push_back(std::rand()); 199 } 200 vec.build(values); 201 202 ASSERT(vec.size() == values.size()); 203 for (std::size_t i = 0; i < vec.size(); ++i) { 204 ASSERT(vec[i] == values[i]); 205 } 206 207 TEST_END(); 208 } 209 210 void TestBitVector(marisa::UInt32 size) { 211 marisa::BitVector bv; 212 213 ASSERT(bv.size() == 0); 214 ASSERT(bv.empty()); 215 ASSERT(bv.total_size() == sizeof(marisa::UInt32) * 5); 216 217 std::vector<bool> bits(size); 218 std::vector<marisa::UInt32> zeros, ones; 219 for (marisa::UInt32 i = 0; i < size; ++i) { 220 const bool bit = (std::rand() % 2) == 0; 221 bits[i] = bit; 222 bv.push_back(bit); 223 (bit ? ones : zeros).push_back(i); 224 ASSERT(bv[i] == bits[i]); 225 } 226 227 ASSERT(bv.size() == bits.size()); 228 ASSERT((size == 0) || !bv.empty()); 229 230 bv.build(); 231 232 marisa::UInt32 num_zeros = 0, num_ones = 0; 233 for (marisa::UInt32 i = 0; i < bits.size(); ++i) { 234 ASSERT(bv[i] == bits[i]); 235 ASSERT(bv.rank0(i) == num_zeros); 236 ASSERT(bv.rank1(i) == num_ones); 237 ++(bv[i] ? num_ones : num_zeros); 238 } 239 for (marisa::UInt32 i = 0; i < zeros.size(); ++i) { 240 ASSERT(bv.select0(i) == zeros[i]); 241 } 242 for (marisa::UInt32 i = 0; i < ones.size(); ++i) { 243 ASSERT(bv.select1(i) == ones[i]); 244 } 245 246 std::stringstream stream; 247 bv.write(stream); 248 bv.clear(); 249 250 ASSERT(bv.size() == 0); 251 ASSERT(bv.empty()); 252 ASSERT(bv.total_size() == sizeof(marisa::UInt32) * 5); 253 254 bv.read(stream); 255 256 ASSERT(bv.size() == bits.size()); 257 258 num_zeros = 0, num_ones = 0; 259 for (marisa::UInt32 i = 0; i < bits.size(); ++i) { 260 ASSERT(bv[i] == bits[i]); 261 ASSERT(bv.rank0(i) == num_zeros); 262 ASSERT(bv.rank1(i) == num_ones); 263 ++(bv[i] ? num_ones : num_zeros); 264 } 265 for (marisa::UInt32 i = 0; i < zeros.size(); ++i) { 266 ASSERT(bv.select0(i) == zeros[i]); 267 } 268 for (marisa::UInt32 i = 0; i < ones.size(); ++i) { 269 ASSERT(bv.select1(i) == ones[i]); 270 } 271 } 272 273 void TestBitVector() { 274 TEST_START(); 275 276 TestBitVector(0); 277 TestBitVector(1); 278 TestBitVector(511); 279 TestBitVector(512); 280 TestBitVector(513); 281 282 for (marisa::UInt32 i = 0; i < 100; ++i) { 283 TestBitVector(std::rand() % 4096); 284 } 285 286 TEST_END(); 287 } 288 289 } // namespace 290 291 int main() { 292 std::srand((unsigned int)time(NULL)); 293 294 TestVector(); 295 TestIntVector(); 296 TestBitVector(); 297 298 return 0; 299 } 300
