Lines Matching refs:trie
56 marisa::Trie trie;
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));
64 trie.build(keys);
65 ASSERT(trie.num_tries() == 1);
66 ASSERT(trie.num_keys() == 0);
67 ASSERT(trie.num_nodes() == 1);
76 trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL | MARISA_LABEL_ORDER);
78 ASSERT(trie.num_tries() == 1);
79 ASSERT(trie.num_keys() == 4);
80 ASSERT(trie.num_nodes() == 11);
92 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
94 ASSERT(trie[keys[i]] == key_ids[i]);
95 ASSERT(trie[key_ids[i]] == keys[i]);
100 trie.clear();
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));
107 trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL | MARISA_WEIGHT_ORDER);
109 ASSERT(trie.num_tries() == 1);
110 ASSERT(trie.num_keys() == 4);
111 ASSERT(trie.num_nodes() == 11);
121 ASSERT(trie[keys[i]] == key_ids[i]);
122 ASSERT(trie[key_ids[i]] == keys[i]);
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"]);
133 ASSERT(trie.find("ap", &ids) == 0);
134 ASSERT(trie.find("applex", &ids) == 2);
136 ASSERT(ids[0] == trie["app"]);
137 ASSERT(ids[1] == trie["apple"]);
140 ASSERT(trie.find("Baddie", &ids, &lengths) == 1);
142 ASSERT(ids[2] == trie["Bad"]);
146 ASSERT(trie.find_callback("anderson", FindCallback(&ids, &lengths)) == 1);
148 ASSERT(ids[3] == trie["and"]);
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);
162 ASSERT(trie.predict("a", &ids) == 3);
164 ASSERT(ids[0] == trie["app"]);
165 ASSERT(ids[1] == trie["and"]);
166 ASSERT(ids[2] == trie["apple"]);
169 ASSERT(trie.predict("a", &ids, &strs) == 3);
171 ASSERT(ids[3] == trie["app"]);
172 ASSERT(ids[4] == trie["apple"]);
173 ASSERT(ids[5] == trie["and"]);
190 marisa::Trie trie;
192 trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE
195 ASSERT(trie.num_tries() == 1);
196 ASSERT(trie.num_keys() == 4);
197 ASSERT(trie.num_nodes() == 7);
202 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
204 ASSERT(trie[keys[i]] == key_ids[i]);
205 ASSERT(trie[key_ids[i]] == keys[i]);
210 key_length = trie.restore(key_ids[0], NULL, 0);
213 EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_PARAM_ERROR);
215 key_length = trie.restore(key_ids[0], key_buf, 5);
219 key_length = trie.restore(key_ids[0], key_buf, 6);
223 trie.build(keys, &key_ids, 2 | MARISA_PREFIX_TRIE
226 ASSERT(trie.num_tries() == 2);
227 ASSERT(trie.num_keys() == 4);
228 ASSERT(trie.num_nodes() == 16);
231 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
233 ASSERT(trie[keys[i]] == key_ids[i]);
234 ASSERT(trie[key_ids[i]] == keys[i]);
239 key_length = trie.restore(key_ids[0], NULL, 0);
242 EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_PARAM_ERROR);
244 key_length = trie.restore(key_ids[0], key_buf, 5);
248 key_length = trie.restore(key_ids[0], key_buf, 6);
252 trie.build(keys, &key_ids, 2 | MARISA_PREFIX_TRIE
255 ASSERT(trie.num_tries() == 2);
256 ASSERT(trie.num_keys() == 4);
257 ASSERT(trie.num_nodes() == 14);
260 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
262 ASSERT(trie[keys[i]] == key_ids[i]);
263 ASSERT(trie[key_ids[i]] == keys[i]);
268 trie.save("trie-test.dat");
269 trie.clear();
271 trie.mmap(&mapper, "trie-test.dat");
274 ASSERT(trie.num_tries() == 2);
275 ASSERT(trie.num_keys() == 4);
276 ASSERT(trie.num_nodes() == 14);
279 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
281 ASSERT(trie[keys[i]] == key_ids[i]);
282 ASSERT(trie[key_ids[i]] == keys[i]);
288 trie.write(stream);
289 trie.clear();
290 trie.read(stream);
292 ASSERT(trie.num_tries() == 2);
293 ASSERT(trie.num_keys() == 4);
294 ASSERT(trie.num_nodes() == 14);
297 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
299 ASSERT(trie[keys[i]] == key_ids[i]);
300 ASSERT(trie[key_ids[i]] == keys[i]);
305 trie.build(keys, &key_ids, 3 | MARISA_PREFIX_TRIE
308 ASSERT(trie.num_tries() == 3);
309 ASSERT(trie.num_keys() == 4);
310 ASSERT(trie.num_nodes() == 19);
313 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
315 ASSERT(trie[keys[i]] == key_ids[i]);
316 ASSERT(trie[key_ids[i]] == keys[i]);
321 ASSERT(trie["ca"] == trie.notfound());
322 ASSERT(trie["card"] == trie.notfound());
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"]);
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"]);
338 ASSERT(trie.find("card", &ids, &lengths) == 1);
340 ASSERT(ids[0] == trie["car"]);
344 ASSERT(trie.predict("ca", &ids) == 2);
346 ASSERT(ids[1] == trie["car"]);
347 ASSERT(ids[2] == trie["caster"]);
349 ASSERT(trie.predict("ca", &ids, NULL, 1) == 1);
351 ASSERT(ids[3] == trie["car"]);
354 ASSERT(trie.predict("ca", &ids, &strs, 1) == 1);
356 ASSERT(ids[4] == trie["car"]);
360 ASSERT(trie.predict_callback("", PredictCallback(&ids, &strs)) == 4);
362 ASSERT(ids[5] == trie["car"]);
363 ASSERT(ids[6] == trie["caster"]);
364 ASSERT(ids[7] == trie["after"]);
365 ASSERT(ids[8] == trie["bar"]);
376 ASSERT(trie.find("card", ids, lengths, 10) == 1);
377 ASSERT(ids[0] == trie["car"]);
380 ASSERT(trie.predict("ca", ids, NULL, 10) == 2);
381 ASSERT(ids[0] == trie["car"]);
382 ASSERT(ids[1] == trie["caster"]);
384 ASSERT(trie.predict("ca", ids, NULL, 1) == 1);
385 ASSERT(ids[0] == trie["car"]);
388 ASSERT(trie.predict("ca", ids, strs, 1) == 1);
389 ASSERT(ids[0] == trie["car"]);
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"]);
416 marisa::Trie trie;
418 trie.build(keys, &key_ids, 1);
420 ASSERT(trie.num_tries() == 1);
421 ASSERT(trie.num_keys() == 4);
422 ASSERT(trie.num_nodes() == 7);
434 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
436 ASSERT(trie[keys[i]] == key_ids[i]);
437 ASSERT(trie[key_ids[i]] == keys[i]);
442 trie.build(keys, &key_ids, 2 | MARISA_WITHOUT_TAIL);
444 ASSERT(trie.num_tries() == 2);
445 ASSERT(trie.num_keys() == 4);
446 ASSERT(trie.num_nodes() == 17);
449 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
451 ASSERT(trie[keys[i]] == key_ids[i]);
452 ASSERT(trie[key_ids[i]] == keys[i]);
457 trie.build(keys, &key_ids, 2);
459 ASSERT(trie.num_tries() == 2);
460 ASSERT(trie.num_keys() == 4);
461 ASSERT(trie.num_nodes() == 14);
464 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
466 ASSERT(trie[keys[i]] == key_ids[i]);
467 ASSERT(trie[key_ids[i]] == keys[i]);
472 trie.build(keys, &key_ids, 3 | MARISA_WITHOUT_TAIL);
474 ASSERT(trie.num_tries() == 3);
475 ASSERT(trie.num_keys() == 4);
476 ASSERT(trie.num_nodes() == 20);
479 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
481 ASSERT(trie[keys[i]] == key_ids[i]);
482 ASSERT(trie[key_ids[i]] == keys[i]);
488 trie.write(stream);
489 trie.clear();
490 trie.read(stream);
492 ASSERT(trie.num_tries() == 3);
493 ASSERT(trie.num_keys() == 4);
494 ASSERT(trie.num_nodes() == 20);
497 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf));
499 ASSERT(trie[keys[i]] == key_ids[i]);
500 ASSERT(trie[key_ids[i]] == keys[i]);
514 marisa::Trie trie;
516 trie.build(keys, &key_ids);
518 ASSERT(trie.num_tries() == 1);
519 ASSERT(trie.num_keys() == 1);
520 ASSERT(trie.num_nodes() == 1);
525 ASSERT(trie[""] == 0);
526 ASSERT(trie[(marisa::UInt32)0] == "");
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);
535 ASSERT(trie.find("xyz", &ids) == 1);
537 ASSERT(ids[0] == trie[""]);
540 ASSERT(trie.find("xyz", &ids, &lengths) == 1);
542 ASSERT(ids[0] == trie[""]);
543 ASSERT(ids[1] == trie[""]);
547 ASSERT(trie.find_callback("xyz", FindCallback(&ids, &lengths)) == 1);
549 ASSERT(ids[2] == trie[""]);
553 ASSERT(trie.predict("xyz", &ids) == 0);
555 ASSERT(trie.predict("", &ids) == 1);
557 ASSERT(ids[3] == trie[""]);
560 ASSERT(trie.predict("", &ids, &strs) == 1);
562 ASSERT(ids[4] == trie[""]);
573 binary_key += "Trie";
578 marisa::Trie trie;
580 trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL);
582 ASSERT(trie.num_tries() == 1);
583 ASSERT(trie.num_keys() == 1);
584 ASSERT(trie.num_nodes() == 8);
589 key_length = trie.restore(0, key_buf, sizeof(key_buf));
591 ASSERT(trie[keys[0]] == key_ids[0]);
592 ASSERT(trie[key_ids[0]] == keys[0]);
595 trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE | MARISA_BINARY_TAIL);
597 ASSERT(trie.num_tries() == 1);
598 ASSERT(trie.num_keys() == 1);
599 ASSERT(trie.num_nodes() == 2);
602 trie.restore(0, key_buf, sizeof(key_buf));
604 ASSERT(trie[keys[0]] == key_ids[0]);
605 ASSERT(trie[key_ids[0]] == keys[0]);
608 trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE | MARISA_TEXT_TAIL);
610 ASSERT(trie.num_tries() == 1);
611 ASSERT(trie.num_keys() == 1);
612 ASSERT(trie.num_nodes() == 2);
615 key_length = trie.restore(0, key_buf, sizeof(key_buf));
617 ASSERT(trie[keys[0]] == key_ids[0]);
618 ASSERT(trie[key_ids[0]] == keys[0]);
622 ASSERT(trie.predict_breadth_first("", &ids) == 1);
627 ASSERT(trie.predict_depth_first("NP", &ids, &strs) == 1);
