1#include <sstream>
2
3#include <marisa.h>
4
5#include "assert.h"
6
7namespace {
8
9class FindCallback {
10 public:
11  FindCallback(std::vector<marisa::UInt32> *key_ids,
12      std::vector<std::size_t> *key_lengths)
13      : key_ids_(key_ids), key_lengths_(key_lengths) {}
14  FindCallback(const FindCallback &callback)
15      : key_ids_(callback.key_ids_), key_lengths_(callback.key_lengths_) {}
16
17  bool operator()(marisa::UInt32 key_id, std::size_t key_length) const {
18    key_ids_->push_back(key_id);
19    key_lengths_->push_back(key_length);
20    return true;
21  }
22
23 private:
24  std::vector<marisa::UInt32> *key_ids_;
25  std::vector<std::size_t> *key_lengths_;
26
27  // Disallows assignment.
28  FindCallback &operator=(const FindCallback &);
29};
30
31class PredictCallback {
32 public:
33  PredictCallback(std::vector<marisa::UInt32> *key_ids,
34      std::vector<std::string> *keys)
35      : key_ids_(key_ids), keys_(keys) {}
36  PredictCallback(const PredictCallback &callback)
37      : key_ids_(callback.key_ids_), keys_(callback.keys_) {}
38
39  bool operator()(marisa::UInt32 key_id, const std::string &key) const {
40    key_ids_->push_back(key_id);
41    keys_->push_back(key);
42    return true;
43  }
44
45 private:
46  std::vector<marisa::UInt32> *key_ids_;
47  std::vector<std::string> *keys_;
48
49  // Disallows assignment.
50  PredictCallback &operator=(const PredictCallback &);
51};
52
53void TestTrie() {
54  TEST_START();
55
56  marisa::Trie trie;
57
58  ASSERT(trie.num_tries() == 0);
59  ASSERT(trie.num_keys() == 0);
60  ASSERT(trie.num_nodes() == 0);
61  ASSERT(trie.total_size() == (sizeof(marisa::UInt32) * 23));
62
63  std::vector<std::string> keys;
64  trie.build(keys);
65  ASSERT(trie.num_tries() == 1);
66  ASSERT(trie.num_keys() == 0);
67  ASSERT(trie.num_nodes() == 1);
68
69  keys.push_back("apple");
70  keys.push_back("and");
71  keys.push_back("Bad");
72  keys.push_back("apple");
73  keys.push_back("app");
74
75  std::vector<marisa::UInt32> key_ids;
76  trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL | MARISA_LABEL_ORDER);
77
78  ASSERT(trie.num_tries() == 1);
79  ASSERT(trie.num_keys() == 4);
80  ASSERT(trie.num_nodes() == 11);
81
82  ASSERT(key_ids.size() == 5);
83  ASSERT(key_ids[0] == 3);
84  ASSERT(key_ids[1] == 1);
85  ASSERT(key_ids[2] == 0);
86  ASSERT(key_ids[3] == 3);
87  ASSERT(key_ids[4] == 2);
88
89  char key_buf[256];
90  std::size_t key_length;
91  for (std::size_t i = 0; i < keys.size(); ++i) {
92    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
93
94    ASSERT(trie[keys[i]] == key_ids[i]);
95    ASSERT(trie[key_ids[i]] == keys[i]);
96    ASSERT(key_length == keys[i].length());
97    ASSERT(keys[i] == key_buf);
98  }
99
100  trie.clear();
101
102  ASSERT(trie.num_tries() == 0);
103  ASSERT(trie.num_keys() == 0);
104  ASSERT(trie.num_nodes() == 0);
105  ASSERT(trie.total_size() == (sizeof(marisa::UInt32) * 23));
106
107  trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL | MARISA_WEIGHT_ORDER);
108
109  ASSERT(trie.num_tries() == 1);
110  ASSERT(trie.num_keys() == 4);
111  ASSERT(trie.num_nodes() == 11);
112
113  ASSERT(key_ids.size() == 5);
114  ASSERT(key_ids[0] == 3);
115  ASSERT(key_ids[1] == 1);
116  ASSERT(key_ids[2] == 2);
117  ASSERT(key_ids[3] == 3);
118  ASSERT(key_ids[4] == 0);
119
120  for (std::size_t i = 0; i < keys.size(); ++i) {
121    ASSERT(trie[keys[i]] == key_ids[i]);
122    ASSERT(trie[key_ids[i]] == keys[i]);
123  }
124
125  ASSERT(trie["appl"] == trie.notfound());
126  ASSERT(trie["applex"] == trie.notfound());
127  ASSERT(trie.find_first("ap") == trie.notfound());
128  ASSERT(trie.find_first("applex") == trie["app"]);
129  ASSERT(trie.find_last("ap") == trie.notfound());
130  ASSERT(trie.find_last("applex") == trie["apple"]);
131
132  std::vector<marisa::UInt32> ids;
133  ASSERT(trie.find("ap", &ids) == 0);
134  ASSERT(trie.find("applex", &ids) == 2);
135  ASSERT(ids.size() == 2);
136  ASSERT(ids[0] == trie["app"]);
137  ASSERT(ids[1] == trie["apple"]);
138
139  std::vector<std::size_t> lengths;
140  ASSERT(trie.find("Baddie", &ids, &lengths) == 1);
141  ASSERT(ids.size() == 3);
142  ASSERT(ids[2] == trie["Bad"]);
143  ASSERT(lengths.size() == 1);
144  ASSERT(lengths[0] == 3);
145
146  ASSERT(trie.find_callback("anderson", FindCallback(&ids, &lengths)) == 1);
147  ASSERT(ids.size() == 4);
148  ASSERT(ids[3] == trie["and"]);
149  ASSERT(lengths.size() == 2);
150  ASSERT(lengths[1] == 3);
151
152  ASSERT(trie.predict("") == 4);
153  ASSERT(trie.predict("a") == 3);
154  ASSERT(trie.predict("ap") == 2);
155  ASSERT(trie.predict("app") == 2);
156  ASSERT(trie.predict("appl") == 1);
157  ASSERT(trie.predict("apple") == 1);
158  ASSERT(trie.predict("appleX") == 0);
159  ASSERT(trie.predict("X") == 0);
160
161  ids.clear();
162  ASSERT(trie.predict("a", &ids) == 3);
163  ASSERT(ids.size() == 3);
164  ASSERT(ids[0] == trie["app"]);
165  ASSERT(ids[1] == trie["and"]);
166  ASSERT(ids[2] == trie["apple"]);
167
168  std::vector<std::string> strs;
169  ASSERT(trie.predict("a", &ids, &strs) == 3);
170  ASSERT(ids.size() == 6);
171  ASSERT(ids[3] == trie["app"]);
172  ASSERT(ids[4] == trie["apple"]);
173  ASSERT(ids[5] == trie["and"]);
174  ASSERT(strs[0] == "app");
175  ASSERT(strs[1] == "apple");
176  ASSERT(strs[2] == "and");
177
178  TEST_END();
179}
180
181void TestPrefixTrie() {
182  TEST_START();
183
184  std::vector<std::string> keys;
185  keys.push_back("after");
186  keys.push_back("bar");
187  keys.push_back("car");
188  keys.push_back("caster");
189
190  marisa::Trie trie;
191  std::vector<marisa::UInt32> key_ids;
192  trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE
193      | MARISA_TEXT_TAIL | MARISA_LABEL_ORDER);
194
195  ASSERT(trie.num_tries() == 1);
196  ASSERT(trie.num_keys() == 4);
197  ASSERT(trie.num_nodes() == 7);
198
199  char key_buf[256];
200  std::size_t key_length;
201  for (std::size_t i = 0; i < keys.size(); ++i) {
202    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
203
204    ASSERT(trie[keys[i]] == key_ids[i]);
205    ASSERT(trie[key_ids[i]] == keys[i]);
206    ASSERT(key_length == keys[i].length());
207    ASSERT(keys[i] == key_buf);
208  }
209
210  key_length = trie.restore(key_ids[0], NULL, 0);
211
212  ASSERT(key_length == keys[0].length());
213  EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_PARAM_ERROR);
214
215  key_length = trie.restore(key_ids[0], key_buf, 5);
216
217  ASSERT(key_length == keys[0].length());
218
219  key_length = trie.restore(key_ids[0], key_buf, 6);
220
221  ASSERT(key_length == keys[0].length());
222
223  trie.build(keys, &key_ids, 2 | MARISA_PREFIX_TRIE
224      | MARISA_WITHOUT_TAIL | MARISA_WEIGHT_ORDER);
225
226  ASSERT(trie.num_tries() == 2);
227  ASSERT(trie.num_keys() == 4);
228  ASSERT(trie.num_nodes() == 16);
229
230  for (std::size_t i = 0; i < keys.size(); ++i) {
231    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
232
233    ASSERT(trie[keys[i]] == key_ids[i]);
234    ASSERT(trie[key_ids[i]] == keys[i]);
235    ASSERT(key_length == keys[i].length());
236    ASSERT(keys[i] == key_buf);
237  }
238
239  key_length = trie.restore(key_ids[0], NULL, 0);
240
241  ASSERT(key_length == keys[0].length());
242  EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_PARAM_ERROR);
243
244  key_length = trie.restore(key_ids[0], key_buf, 5);
245
246  ASSERT(key_length == keys[0].length());
247
248  key_length = trie.restore(key_ids[0], key_buf, 6);
249
250  ASSERT(key_length == keys[0].length());
251
252  trie.build(keys, &key_ids, 2 | MARISA_PREFIX_TRIE
253      | MARISA_TEXT_TAIL | MARISA_LABEL_ORDER);
254
255  ASSERT(trie.num_tries() == 2);
256  ASSERT(trie.num_keys() == 4);
257  ASSERT(trie.num_nodes() == 14);
258
259  for (std::size_t i = 0; i < keys.size(); ++i) {
260    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
261
262    ASSERT(trie[keys[i]] == key_ids[i]);
263    ASSERT(trie[key_ids[i]] == keys[i]);
264    ASSERT(key_length == keys[i].length());
265    ASSERT(keys[i] == key_buf);
266  }
267
268  trie.save("trie-test.dat");
269  trie.clear();
270  marisa::Mapper mapper;
271  trie.mmap(&mapper, "trie-test.dat");
272
273  ASSERT(mapper.is_open());
274  ASSERT(trie.num_tries() == 2);
275  ASSERT(trie.num_keys() == 4);
276  ASSERT(trie.num_nodes() == 14);
277
278  for (std::size_t i = 0; i < keys.size(); ++i) {
279    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
280
281    ASSERT(trie[keys[i]] == key_ids[i]);
282    ASSERT(trie[key_ids[i]] == keys[i]);
283    ASSERT(key_length == keys[i].length());
284    ASSERT(keys[i] == key_buf);
285  }
286
287  std::stringstream stream;
288  trie.write(stream);
289  trie.clear();
290  trie.read(stream);
291
292  ASSERT(trie.num_tries() == 2);
293  ASSERT(trie.num_keys() == 4);
294  ASSERT(trie.num_nodes() == 14);
295
296  for (std::size_t i = 0; i < keys.size(); ++i) {
297    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
298
299    ASSERT(trie[keys[i]] == key_ids[i]);
300    ASSERT(trie[key_ids[i]] == keys[i]);
301    ASSERT(key_length == keys[i].length());
302    ASSERT(keys[i] == key_buf);
303  }
304
305  trie.build(keys, &key_ids, 3 | MARISA_PREFIX_TRIE
306      | MARISA_WITHOUT_TAIL | MARISA_WEIGHT_ORDER);
307
308  ASSERT(trie.num_tries() == 3);
309  ASSERT(trie.num_keys() == 4);
310  ASSERT(trie.num_nodes() == 19);
311
312  for (std::size_t i = 0; i < keys.size(); ++i) {
313    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
314
315    ASSERT(trie[keys[i]] == key_ids[i]);
316    ASSERT(trie[key_ids[i]] == keys[i]);
317    ASSERT(key_length == keys[i].length());
318    ASSERT(keys[i] == key_buf);
319  }
320
321  ASSERT(trie["ca"] == trie.notfound());
322  ASSERT(trie["card"] == trie.notfound());
323
324  std::size_t length = 0;
325  ASSERT(trie.find_first("ca") == trie.notfound());
326  ASSERT(trie.find_first("car") == trie["car"]);
327  ASSERT(trie.find_first("card", &length) == trie["car"]);
328  ASSERT(length == 3);
329
330  ASSERT(trie.find_last("afte") == trie.notfound());
331  ASSERT(trie.find_last("after") == trie["after"]);
332  ASSERT(trie.find_last("afternoon", &length) == trie["after"]);
333  ASSERT(length == 5);
334
335  {
336    std::vector<marisa::UInt32> ids;
337    std::vector<std::size_t> lengths;
338    ASSERT(trie.find("card", &ids, &lengths) == 1);
339    ASSERT(ids.size() == 1);
340    ASSERT(ids[0] == trie["car"]);
341    ASSERT(lengths.size() == 1);
342    ASSERT(lengths[0] == 3);
343
344    ASSERT(trie.predict("ca", &ids) == 2);
345    ASSERT(ids.size() == 3);
346    ASSERT(ids[1] == trie["car"]);
347    ASSERT(ids[2] == trie["caster"]);
348
349    ASSERT(trie.predict("ca", &ids, NULL, 1) == 1);
350    ASSERT(ids.size() == 4);
351    ASSERT(ids[3] == trie["car"]);
352
353    std::vector<std::string> strs;
354    ASSERT(trie.predict("ca", &ids, &strs, 1) == 1);
355    ASSERT(ids.size() == 5);
356    ASSERT(ids[4] == trie["car"]);
357    ASSERT(strs.size() == 1);
358    ASSERT(strs[0] == "car");
359
360    ASSERT(trie.predict_callback("", PredictCallback(&ids, &strs)) == 4);
361    ASSERT(ids.size() == 9);
362    ASSERT(ids[5] == trie["car"]);
363    ASSERT(ids[6] == trie["caster"]);
364    ASSERT(ids[7] == trie["after"]);
365    ASSERT(ids[8] == trie["bar"]);
366    ASSERT(strs.size() == 5);
367    ASSERT(strs[1] == "car");
368    ASSERT(strs[2] == "caster");
369    ASSERT(strs[3] == "after");
370    ASSERT(strs[4] == "bar");
371  }
372
373  {
374    marisa::UInt32 ids[10];
375    std::size_t lengths[10];
376    ASSERT(trie.find("card", ids, lengths, 10) == 1);
377    ASSERT(ids[0] == trie["car"]);
378    ASSERT(lengths[0] == 3);
379
380    ASSERT(trie.predict("ca", ids, NULL, 10) == 2);
381    ASSERT(ids[0] == trie["car"]);
382    ASSERT(ids[1] == trie["caster"]);
383
384    ASSERT(trie.predict("ca", ids, NULL, 1) == 1);
385    ASSERT(ids[0] == trie["car"]);
386
387    std::string strs[10];
388    ASSERT(trie.predict("ca", ids, strs, 1) == 1);
389    ASSERT(ids[0] == trie["car"]);
390    ASSERT(strs[0] == "car");
391
392    ASSERT(trie.predict("", ids, strs, 10) == 4);
393    ASSERT(ids[0] == trie["car"]);
394    ASSERT(ids[1] == trie["caster"]);
395    ASSERT(ids[2] == trie["after"]);
396    ASSERT(ids[3] == trie["bar"]);
397    ASSERT(strs[0] == "car");
398    ASSERT(strs[1] == "caster");
399    ASSERT(strs[2] == "after");
400    ASSERT(strs[3] == "bar");
401  }
402
403  TEST_END();
404}
405
406void TestPatriciaTrie() {
407  TEST_START();
408
409  std::vector<std::string> keys;
410  keys.push_back("bach");
411  keys.push_back("bet");
412  keys.push_back("chat");
413  keys.push_back("check");
414  keys.push_back("check");
415
416  marisa::Trie trie;
417  std::vector<marisa::UInt32> key_ids;
418  trie.build(keys, &key_ids, 1);
419
420  ASSERT(trie.num_tries() == 1);
421  ASSERT(trie.num_keys() == 4);
422  ASSERT(trie.num_nodes() == 7);
423
424  ASSERT(key_ids.size() == 5);
425  ASSERT(key_ids[0] == 2);
426  ASSERT(key_ids[1] == 3);
427  ASSERT(key_ids[2] == 1);
428  ASSERT(key_ids[3] == 0);
429  ASSERT(key_ids[4] == 0);
430
431  char key_buf[256];
432  std::size_t key_length;
433  for (std::size_t i = 0; i < keys.size(); ++i) {
434    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
435
436    ASSERT(trie[keys[i]] == key_ids[i]);
437    ASSERT(trie[key_ids[i]] == keys[i]);
438    ASSERT(key_length == keys[i].length());
439    ASSERT(keys[i] == key_buf);
440  }
441
442  trie.build(keys, &key_ids, 2 | MARISA_WITHOUT_TAIL);
443
444  ASSERT(trie.num_tries() == 2);
445  ASSERT(trie.num_keys() == 4);
446  ASSERT(trie.num_nodes() == 17);
447
448  for (std::size_t i = 0; i < keys.size(); ++i) {
449    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
450
451    ASSERT(trie[keys[i]] == key_ids[i]);
452    ASSERT(trie[key_ids[i]] == keys[i]);
453    ASSERT(key_length == keys[i].length());
454    ASSERT(keys[i] == key_buf);
455  }
456
457  trie.build(keys, &key_ids, 2);
458
459  ASSERT(trie.num_tries() == 2);
460  ASSERT(trie.num_keys() == 4);
461  ASSERT(trie.num_nodes() == 14);
462
463  for (std::size_t i = 0; i < keys.size(); ++i) {
464    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
465
466    ASSERT(trie[keys[i]] == key_ids[i]);
467    ASSERT(trie[key_ids[i]] == keys[i]);
468    ASSERT(key_length == keys[i].length());
469    ASSERT(keys[i] == key_buf);
470  }
471
472  trie.build(keys, &key_ids, 3 | MARISA_WITHOUT_TAIL);
473
474  ASSERT(trie.num_tries() == 3);
475  ASSERT(trie.num_keys() == 4);
476  ASSERT(trie.num_nodes() == 20);
477
478  for (std::size_t i = 0; i < keys.size(); ++i) {
479    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
480
481    ASSERT(trie[keys[i]] == key_ids[i]);
482    ASSERT(trie[key_ids[i]] == keys[i]);
483    ASSERT(key_length == keys[i].length());
484    ASSERT(keys[i] == key_buf);
485  }
486
487  std::stringstream stream;
488  trie.write(stream);
489  trie.clear();
490  trie.read(stream);
491
492  ASSERT(trie.num_tries() == 3);
493  ASSERT(trie.num_keys() == 4);
494  ASSERT(trie.num_nodes() == 20);
495
496  for (std::size_t i = 0; i < keys.size(); ++i) {
497    key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
498
499    ASSERT(trie[keys[i]] == key_ids[i]);
500    ASSERT(trie[key_ids[i]] == keys[i]);
501    ASSERT(key_length == keys[i].length());
502    ASSERT(keys[i] == key_buf);
503  }
504
505  TEST_END();
506}
507
508void TestEmptyString() {
509  TEST_START();
510
511  std::vector<std::string> keys;
512  keys.push_back("");
513
514  marisa::Trie trie;
515  std::vector<marisa::UInt32> key_ids;
516  trie.build(keys, &key_ids);
517
518  ASSERT(trie.num_tries() == 1);
519  ASSERT(trie.num_keys() == 1);
520  ASSERT(trie.num_nodes() == 1);
521
522  ASSERT(key_ids.size() == 1);
523  ASSERT(key_ids[0] == 0);
524
525  ASSERT(trie[""] == 0);
526  ASSERT(trie[(marisa::UInt32)0] == "");
527
528  ASSERT(trie["x"] == trie.notfound());
529  ASSERT(trie.find_first("") == 0);
530  ASSERT(trie.find_first("x") == 0);
531  ASSERT(trie.find_last("") == 0);
532  ASSERT(trie.find_last("x") == 0);
533
534  std::vector<marisa::UInt32> ids;
535  ASSERT(trie.find("xyz", &ids) == 1);
536  ASSERT(ids.size() == 1);
537  ASSERT(ids[0] == trie[""]);
538
539  std::vector<std::size_t> lengths;
540  ASSERT(trie.find("xyz", &ids, &lengths) == 1);
541  ASSERT(ids.size() == 2);
542  ASSERT(ids[0] == trie[""]);
543  ASSERT(ids[1] == trie[""]);
544  ASSERT(lengths.size() == 1);
545  ASSERT(lengths[0] == 0);
546
547  ASSERT(trie.find_callback("xyz", FindCallback(&ids, &lengths)) == 1);
548  ASSERT(ids.size() == 3);
549  ASSERT(ids[2] == trie[""]);
550  ASSERT(lengths.size() == 2);
551  ASSERT(lengths[1] == 0);
552
553  ASSERT(trie.predict("xyz", &ids) == 0);
554
555  ASSERT(trie.predict("", &ids) == 1);
556  ASSERT(ids.size() == 4);
557  ASSERT(ids[3] == trie[""]);
558
559  std::vector<std::string> strs;
560  ASSERT(trie.predict("", &ids, &strs) == 1);
561  ASSERT(ids.size() == 5);
562  ASSERT(ids[4] == trie[""]);
563  ASSERT(strs[0] == "");
564
565  TEST_END();
566}
567
568void TestBinaryKey() {
569  TEST_START();
570
571  std::string binary_key = "NP";
572  binary_key += '\0';
573  binary_key += "Trie";
574
575  std::vector<std::string> keys;
576  keys.push_back(binary_key);
577
578  marisa::Trie trie;
579  std::vector<marisa::UInt32> key_ids;
580  trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL);
581
582  ASSERT(trie.num_tries() == 1);
583  ASSERT(trie.num_keys() == 1);
584  ASSERT(trie.num_nodes() == 8);
585  ASSERT(key_ids.size() == 1);
586
587  char key_buf[256];
588  std::size_t key_length;
589  key_length = trie.restore(0, key_buf, sizeof(key_buf));
590
591  ASSERT(trie[keys[0]] == key_ids[0]);
592  ASSERT(trie[key_ids[0]] == keys[0]);
593  ASSERT(std::string(key_buf, key_length) == keys[0]);
594
595  trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE | MARISA_BINARY_TAIL);
596
597  ASSERT(trie.num_tries() == 1);
598  ASSERT(trie.num_keys() == 1);
599  ASSERT(trie.num_nodes() == 2);
600  ASSERT(key_ids.size() == 1);
601
602  key_length = trie.restore(0, key_buf, sizeof(key_buf));
603
604  ASSERT(trie[keys[0]] == key_ids[0]);
605  ASSERT(trie[key_ids[0]] == keys[0]);
606  ASSERT(std::string(key_buf, key_length) == keys[0]);
607
608  trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE | MARISA_TEXT_TAIL);
609
610  ASSERT(trie.num_tries() == 1);
611  ASSERT(trie.num_keys() == 1);
612  ASSERT(trie.num_nodes() == 2);
613  ASSERT(key_ids.size() == 1);
614
615  key_length = trie.restore(0, key_buf, sizeof(key_buf));
616
617  ASSERT(trie[keys[0]] == key_ids[0]);
618  ASSERT(trie[key_ids[0]] == keys[0]);
619  ASSERT(std::string(key_buf, key_length) == keys[0]);
620
621  std::vector<marisa::UInt32> ids;
622  ASSERT(trie.predict_breadth_first("", &ids) == 1);
623  ASSERT(ids.size() == 1);
624  ASSERT(ids[0] == key_ids[0]);
625
626  std::vector<std::string> strs;
627  ASSERT(trie.predict_depth_first("NP", &ids, &strs) == 1);
628  ASSERT(ids.size() == 2);
629  ASSERT(ids[1] == key_ids[0]);
630  ASSERT(strs[0] == keys[0]);
631
632  TEST_END();
633}
634
635}  // namespace
636
637int main() {
638  TestTrie();
639  TestPrefixTrie();
640  TestPatriciaTrie();
641  TestEmptyString();
642  TestBinaryKey();
643
644  return 0;
645}
646