1#include <cstdlib>
2#include <ctime>
3
4#include <marisa_alpha/base.h>
5#include <marisa_alpha/popcount.h>
6#include <marisa_alpha/rank.h>
7#include <marisa_alpha/string.h>
8#include <marisa_alpha/key.h>
9#include <marisa_alpha/progress.h>
10#include <marisa_alpha/range.h>
11#include <marisa_alpha/query.h>
12#include <marisa_alpha/container.h>
13#include <marisa_alpha/cell.h>
14
15#include "assert.h"
16
17namespace {
18
19void TestBase() {
20  TEST_START();
21
22  ASSERT(sizeof(marisa_alpha_uint8) == 1);
23  ASSERT(sizeof(marisa_alpha_uint16) == 2);
24  ASSERT(sizeof(marisa_alpha_uint32) == 4);
25  ASSERT(sizeof(marisa_alpha_uint64) == 8);
26
27  ASSERT(MARISA_ALPHA_UINT8_MAX == 0xFFU);
28  ASSERT(MARISA_ALPHA_UINT16_MAX == 0xFFFFU);
29  ASSERT(MARISA_ALPHA_UINT32_MAX == 0xFFFFFFFFU);
30  ASSERT(MARISA_ALPHA_UINT64_MAX == 0xFFFFFFFFFFFFFFFFULL);
31
32  ASSERT(sizeof(marisa_alpha::UInt8) == 1);
33  ASSERT(sizeof(marisa_alpha::UInt16) == 2);
34  ASSERT(sizeof(marisa_alpha::UInt32) == 4);
35  ASSERT(sizeof(marisa_alpha::UInt64) == 8);
36
37  int x = 100, y = 200;
38  marisa_alpha::Swap(&x, &y);
39  ASSERT(x == 200);
40  ASSERT(y == 100);
41
42  EXCEPT(marisa_alpha::Swap(static_cast<int *>(NULL), &y),
43      MARISA_ALPHA_PARAM_ERROR);
44  EXCEPT(marisa_alpha::Swap(&x, static_cast<int *>(NULL)),
45      MARISA_ALPHA_PARAM_ERROR);
46
47  TEST_END();
48}
49
50marisa_alpha::UInt32 NaivePopCount(marisa_alpha::UInt32 x) {
51  marisa_alpha::UInt32 count = 0;
52  while (x) {
53    count += x & 1;
54    x >>= 1;
55  }
56  return count;
57}
58
59void TestPopCount() {
60  TEST_START();
61
62  ASSERT(marisa_alpha::PopCount(0).lo8() == 0);
63  ASSERT(marisa_alpha::PopCount(0).lo16() == 0);
64  ASSERT(marisa_alpha::PopCount(0).lo24() == 0);
65  ASSERT(marisa_alpha::PopCount(0).lo32() == 0);
66
67  ASSERT(marisa_alpha::PopCount(0xFFFFFFFFU).lo8() == 8);
68  ASSERT(marisa_alpha::PopCount(0xFFFFFFFFU).lo16() == 16);
69  ASSERT(marisa_alpha::PopCount(0xFFFFFFFFU).lo24() == 24);
70  ASSERT(marisa_alpha::PopCount(0xFFFFFFFFU).lo32() == 32);
71
72  for (std::size_t i = 0; i < 1024; ++i) {
73    marisa_alpha::UInt32 value = std::rand();
74    marisa_alpha::PopCount popcount(value);
75    ASSERT(popcount.lo8() == NaivePopCount(value & 0xFFU));
76    ASSERT(popcount.lo16() == NaivePopCount(value & 0xFFFFU));
77    ASSERT(popcount.lo24() == NaivePopCount(value & 0xFFFFFFU));
78    ASSERT(popcount.lo32() == NaivePopCount(value));
79  }
80
81  TEST_END();
82}
83
84void TestRank() {
85  TEST_START();
86
87  marisa_alpha::Rank rank;
88
89  ASSERT(rank.abs() == 0);
90  ASSERT(rank.rel1() == 0);
91  ASSERT(rank.rel2() == 0);
92  ASSERT(rank.rel3() == 0);
93  ASSERT(rank.rel4() == 0);
94  ASSERT(rank.rel5() == 0);
95  ASSERT(rank.rel6() == 0);
96  ASSERT(rank.rel7() == 0);
97
98  rank.set_abs(0xFFFFFFFFU);
99  rank.set_rel1(64);
100  rank.set_rel2(128);
101  rank.set_rel3(192);
102  rank.set_rel4(256);
103  rank.set_rel5(320);
104  rank.set_rel6(384);
105  rank.set_rel7(448);
106
107  ASSERT(rank.abs() == 0xFFFFFFFFU);
108  ASSERT(rank.rel1() == 64);
109  ASSERT(rank.rel2() == 128);
110  ASSERT(rank.rel3() == 192);
111  ASSERT(rank.rel4() == 256);
112  ASSERT(rank.rel5() == 320);
113  ASSERT(rank.rel6() == 384);
114  ASSERT(rank.rel7() == 448);
115
116  TEST_END();
117}
118
119void TestString() {
120  TEST_START();
121
122  marisa_alpha::String str;
123
124  ASSERT(str.ptr() == NULL);
125  ASSERT(str.length() == 0);
126
127  marisa_alpha::RString rstr;
128
129  ASSERT(rstr.ptr() == NULL);
130  ASSERT(rstr.length() == 0);
131
132  const char *s = "ab";
133  str = marisa_alpha::String(s);
134
135  ASSERT(str.ptr() == s);
136  ASSERT(str.length() == 2);
137  ASSERT(str[0] == s[0]);
138  ASSERT(str[1] == s[1]);
139
140  rstr = marisa_alpha::RString(str);
141  ASSERT(rstr.ptr() == s);
142  ASSERT(rstr.length() == 2);
143  ASSERT(rstr[0] == s[1]);
144  ASSERT(rstr[1] == s[0]);
145
146  std::string s2 = "xyz";
147  str = marisa_alpha::String(s2.c_str(), s2.length());
148
149  ASSERT(str.ptr() == s2.c_str());
150  ASSERT(str.length() == 3);
151  ASSERT(str[0] == s2[0]);
152  ASSERT(str[1] == s2[1]);
153  ASSERT(str[2] == s2[2]);
154
155  ASSERT(str.substr(0, 2).length() == 2);
156  ASSERT(str.substr(0, 2)[0] == 'x');
157  ASSERT(str.substr(0, 2)[1] == 'y');
158
159  rstr = marisa_alpha::RString(str);
160
161  ASSERT(rstr.ptr() == s2.c_str());
162  ASSERT(rstr.length() == 3);
163  ASSERT(rstr[0] == s2[2]);
164  ASSERT(rstr[1] == s2[1]);
165  ASSERT(rstr[2] == s2[0]);
166
167  ASSERT(rstr.substr(1, 2).length() == 2);
168  ASSERT(rstr.substr(1, 2)[0] == 'y');
169  ASSERT(rstr.substr(1, 2)[1] == 'x');
170
171  ASSERT(marisa_alpha::String("abc") == marisa_alpha::String("abc"));
172  ASSERT(marisa_alpha::String("abc") != marisa_alpha::String("bcd"));
173  ASSERT(marisa_alpha::String("abc") < marisa_alpha::String("bcd"));
174  ASSERT(marisa_alpha::String("ab") < marisa_alpha::String("abc"));
175  ASSERT(marisa_alpha::String("bcd") > marisa_alpha::String("abc"));
176  ASSERT(marisa_alpha::String("abc") > marisa_alpha::String("ab"));
177
178  ASSERT(marisa_alpha::String("abcde").substr(1, 2) ==
179      marisa_alpha::String("bc"));
180
181  TEST_END();
182}
183
184void TestKey() {
185  TEST_START();
186
187  marisa_alpha::Key<marisa_alpha::String> key;
188
189  ASSERT(key.str().length() == 0);
190  ASSERT(key.weight() == 0.0);
191  ASSERT(key.id() == 0);
192  ASSERT(key.terminal() == 0);
193
194  key.set_str(marisa_alpha::String("abc"));
195  key.set_weight(1.0);
196  key.set_id(2);
197  key.set_terminal(3);
198
199  ASSERT(key.str() == marisa_alpha::String("abc"));
200  ASSERT(key.weight() == 1.0);
201  ASSERT(key.id() == 2);
202  ASSERT(key.terminal() == 3);
203
204  marisa_alpha::String str("string");
205  marisa_alpha::Key<marisa_alpha::RString> rkey;
206
207  ASSERT(rkey.str().length() == 0);
208  ASSERT(rkey.weight() == 0.0);
209  ASSERT(rkey.id() == 0);
210  ASSERT(rkey.terminal() == 0);
211
212  rkey.set_str(marisa_alpha::RString(str));
213  rkey.set_weight(4.0);
214  rkey.set_id(5);
215  rkey.set_terminal(6);
216
217  ASSERT(rkey.str() == marisa_alpha::RString(str));
218  ASSERT(rkey.weight() == 4.0);
219  ASSERT(rkey.id() == 5);
220  ASSERT(rkey.terminal() == 6);
221
222  TEST_END();
223}
224void TestProgress() {
225  TEST_START();
226
227  {
228    marisa_alpha::Progress progress(0);
229
230    ASSERT(progress.is_valid());
231    while (!progress.is_last()) {
232      ++progress;
233    }
234    ASSERT(progress.is_last());
235    ASSERT(progress.flags() == MARISA_ALPHA_DEFAULT_FLAGS);
236    ASSERT(progress.trie_id() == progress.num_tries() - 1);
237    ASSERT(progress.total_size() == 0);
238
239    progress.test_total_size(0);
240    progress.test_total_size(1);
241    EXCEPT(progress.test_total_size(MARISA_ALPHA_UINT32_MAX),
242        MARISA_ALPHA_SIZE_ERROR);
243    progress.test_total_size(MARISA_ALPHA_UINT32_MAX - 1);
244    progress.test_total_size(0);
245    EXCEPT(progress.test_total_size(1), MARISA_ALPHA_SIZE_ERROR);
246
247    ASSERT(progress.num_tries() == MARISA_ALPHA_DEFAULT_NUM_TRIES);
248    ASSERT(progress.trie() == MARISA_ALPHA_DEFAULT_TRIE);
249    ASSERT(progress.tail() == MARISA_ALPHA_DEFAULT_TAIL);
250    ASSERT(progress.order() == MARISA_ALPHA_DEFAULT_ORDER);
251  }
252
253  {
254    marisa_alpha::Progress progress(MARISA_ALPHA_DEFAULT_FLAGS);
255
256    ASSERT(progress.is_valid());
257    ASSERT(!progress.is_last());
258    ASSERT(progress.num_tries() == MARISA_ALPHA_DEFAULT_NUM_TRIES);
259    ASSERT(progress.trie() == MARISA_ALPHA_DEFAULT_TRIE);
260    ASSERT(progress.tail() == MARISA_ALPHA_DEFAULT_TAIL);
261    ASSERT(progress.order() == MARISA_ALPHA_DEFAULT_ORDER);
262  }
263
264  {
265    marisa_alpha::Progress progress(255 | MARISA_ALPHA_PREFIX_TRIE
266        | MARISA_ALPHA_BINARY_TAIL | MARISA_ALPHA_LABEL_ORDER);
267
268    ASSERT(progress.is_valid());
269    ASSERT(!progress.is_last());
270    ASSERT(progress.num_tries() == 255);
271    ASSERT(progress.trie() == MARISA_ALPHA_PREFIX_TRIE);
272    ASSERT(progress.tail() == MARISA_ALPHA_BINARY_TAIL);
273    ASSERT(progress.order() == MARISA_ALPHA_LABEL_ORDER);
274  }
275
276  {
277    marisa_alpha::Progress progress(~MARISA_ALPHA_FLAGS_MASK);
278
279    ASSERT(!progress.is_valid());
280  }
281
282  TEST_END();
283}
284
285void TestRange() {
286  TEST_START();
287
288  marisa_alpha::Range range;
289
290  ASSERT(range.begin() == 0);
291  ASSERT(range.end() == 0);
292  ASSERT(range.pos() == 0);
293
294  range.set_begin(1);
295  range.set_end(2);
296  range.set_pos(3);
297
298  ASSERT(range.begin() == 1);
299  ASSERT(range.end() == 2);
300  ASSERT(range.pos() == 3);
301
302  marisa_alpha::WRange wrange;
303
304  ASSERT(wrange.range().begin() == 0);
305  ASSERT(wrange.range().end() == 0);
306  ASSERT(wrange.range().pos() == 0);
307
308  ASSERT(wrange.begin() == 0);
309  ASSERT(wrange.end() == 0);
310  ASSERT(wrange.pos() == 0);
311  ASSERT(wrange.weight() == 0.0);
312
313  wrange = marisa_alpha::WRange(range, 4.0);
314
315  ASSERT(wrange.range().begin() == 1);
316  ASSERT(wrange.range().end() == 2);
317  ASSERT(wrange.range().pos() == 3);
318
319  ASSERT(wrange.begin() == 1);
320  ASSERT(wrange.end() == 2);
321  ASSERT(wrange.pos() == 3);
322  ASSERT(wrange.weight() == 4.0);
323
324  wrange.set_begin(5);
325  wrange.set_end(6);
326  wrange.set_pos(7);
327  wrange.set_weight(8.0);
328
329  ASSERT(wrange.begin() == 5);
330  ASSERT(wrange.end() == 6);
331  ASSERT(wrange.pos() == 7);
332  ASSERT(wrange.weight() == 8.0);
333
334  TEST_END();
335}
336
337void TestQuery() {
338  TEST_START();
339
340  marisa_alpha::Query query("abc", 3);
341
342  ASSERT(query[0] == 'a');
343  ASSERT(!query.ends_at(0));
344
345  ASSERT(query[1] == 'b');
346  ASSERT(!query.ends_at(1));
347
348  ASSERT(query[2] == 'c');
349  ASSERT(!query.ends_at(2));
350
351  ASSERT(query.ends_at(3));
352
353  std::string str("str");
354
355  query.insert(&str);
356  ASSERT(str == "abcstr");
357
358  marisa_alpha::CQuery cquery("xyz");
359
360  ASSERT(cquery[0] == 'x');
361  ASSERT(!cquery.ends_at(0));
362
363  ASSERT(cquery[1] == 'y');
364  ASSERT(!cquery.ends_at(1));
365
366  ASSERT(cquery[2] == 'z');
367  ASSERT(!cquery.ends_at(2));
368
369  ASSERT(cquery.ends_at(3));
370
371  cquery.insert(&str);
372  ASSERT(str == "xyzabcstr");
373
374  TEST_END();
375}
376
377void TestContainer() {
378  TEST_START();
379
380  int array[1024];
381  marisa_alpha::Container<int *> array_container(array);
382
383  ASSERT(array_container.is_valid());
384  for (int i = 0; i < 1024; ++i) {
385    int value = std::rand();
386    array_container.insert(i, value);
387    ASSERT(array[i] == value);
388  }
389
390  marisa_alpha::Container<int *> array_container2(NULL);
391
392  ASSERT(!array_container2.is_valid());
393
394  std::vector<int> vec;
395  marisa_alpha::Container<std::vector<int> *> vec_container(&vec);
396
397  ASSERT(vec_container.is_valid());
398  for (int i = 0; i < 1024; ++i) {
399    int value = std::rand();
400    vec_container.insert(i, value);
401    ASSERT(vec.back() == value);
402    ASSERT(vec[i] == value);
403  }
404  ASSERT(vec.size() == 1024);
405
406  marisa_alpha::Container<std::vector<int> *> vec_container2(&vec);
407
408  ASSERT(vec_container2.is_valid());
409  for (int i = 0; i < 1024; ++i) {
410    int value = std::rand();
411    vec_container2.insert(i, value);
412    ASSERT(vec.back() == value);
413    ASSERT(vec[i + 1024] == value);
414  }
415  ASSERT(vec.size() == 2048);
416
417  marisa_alpha::Container<std::vector<int> *> vec_container3(NULL);
418  ASSERT(!vec_container3.is_valid());
419
420  TEST_END();
421}
422
423void TestCell() {
424  TEST_START();
425
426  marisa_alpha::Cell cell;
427
428  ASSERT(cell.louds_pos() == 0);
429  ASSERT(cell.node() == 0);
430  ASSERT(cell.key_id() == 0);
431  ASSERT(cell.length() == 0);
432
433  cell.set_louds_pos(1);
434  cell.set_node(2);
435  cell.set_key_id(3);
436  cell.set_length(4);
437
438  ASSERT(cell.louds_pos() == 1);
439  ASSERT(cell.node() == 2);
440  ASSERT(cell.key_id() == 3);
441  ASSERT(cell.length() == 4);
442
443  TEST_END();
444}
445
446}  // namespace
447
448int main() {
449  std::srand((unsigned int)time(NULL));
450
451  TestBase();
452  TestPopCount();
453  TestRank();
454  TestString();
455  TestKey();
456  TestProgress();
457  TestRange();
458  TestQuery();
459  TestContainer();
460  TestCell();
461
462  return 0;
463}
464