• 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_alpha/vector.h>
8 #include <marisa_alpha/intvector.h>
9 #include <marisa_alpha/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_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 
TestIntVector()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 
TestBitVector(marisa_alpha::UInt32 size)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 
TestBitVector()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 
main()295 int main() {
296   std::srand((unsigned int)time(NULL));
297 
298   TestVector();
299   TestIntVector();
300   TestBitVector();
301 
302   return 0;
303 }
304