• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
TestVector()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 
TestIntVector()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 
TestBitVector(marisa::UInt32 size)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 
TestBitVector()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 
main()291 int main() {
292   std::srand((unsigned int)time(NULL));
293 
294   TestVector();
295   TestIntVector();
296   TestBitVector();
297 
298   return 0;
299 }
300