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