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
13namespace {
14
15void 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
119void 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
210void 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
273void 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
291int main() {
292  std::srand((unsigned int)time(NULL));
293
294  TestVector();
295  TestIntVector();
296  TestBitVector();
297
298  return 0;
299}
300