Lines Matching refs:trie
56 marisa_alpha::Trie trie; in TestTrie() local
58 ASSERT(trie.num_tries() == 0); in TestTrie()
59 ASSERT(trie.num_keys() == 0); in TestTrie()
60 ASSERT(trie.num_nodes() == 0); in TestTrie()
61 ASSERT(trie.total_size() == (sizeof(marisa_alpha::UInt32) * 23)); in TestTrie()
64 trie.build(keys); in TestTrie()
65 ASSERT(trie.num_tries() == 1); in TestTrie()
66 ASSERT(trie.num_keys() == 0); in TestTrie()
67 ASSERT(trie.num_nodes() == 1); in TestTrie()
76 trie.build(keys, &key_ids, in TestTrie()
79 ASSERT(trie.num_tries() == 1); in TestTrie()
80 ASSERT(trie.num_keys() == 4); in TestTrie()
81 ASSERT(trie.num_nodes() == 11); in TestTrie()
93 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestTrie()
95 ASSERT(trie[keys[i]] == key_ids[i]); in TestTrie()
96 ASSERT(trie[key_ids[i]] == keys[i]); in TestTrie()
101 trie.clear(); in TestTrie()
103 ASSERT(trie.num_tries() == 0); in TestTrie()
104 ASSERT(trie.num_keys() == 0); in TestTrie()
105 ASSERT(trie.num_nodes() == 0); in TestTrie()
106 ASSERT(trie.total_size() == (sizeof(marisa_alpha::UInt32) * 23)); in TestTrie()
108 trie.build(keys, &key_ids, in TestTrie()
111 ASSERT(trie.num_tries() == 1); in TestTrie()
112 ASSERT(trie.num_keys() == 4); in TestTrie()
113 ASSERT(trie.num_nodes() == 11); in TestTrie()
123 ASSERT(trie[keys[i]] == key_ids[i]); in TestTrie()
124 ASSERT(trie[key_ids[i]] == keys[i]); in TestTrie()
127 ASSERT(trie["appl"] == trie.notfound()); in TestTrie()
128 ASSERT(trie["applex"] == trie.notfound()); in TestTrie()
129 ASSERT(trie.find_first("ap") == trie.notfound()); in TestTrie()
130 ASSERT(trie.find_first("applex") == trie["app"]); in TestTrie()
131 ASSERT(trie.find_last("ap") == trie.notfound()); in TestTrie()
132 ASSERT(trie.find_last("applex") == trie["apple"]); in TestTrie()
135 ASSERT(trie.find("ap", &ids) == 0); in TestTrie()
136 ASSERT(trie.find("applex", &ids) == 2); in TestTrie()
138 ASSERT(ids[0] == trie["app"]); in TestTrie()
139 ASSERT(ids[1] == trie["apple"]); in TestTrie()
142 ASSERT(trie.find("Baddie", &ids, &lengths) == 1); in TestTrie()
144 ASSERT(ids[2] == trie["Bad"]); in TestTrie()
148 ASSERT(trie.find_callback("anderson", FindCallback(&ids, &lengths)) == 1); in TestTrie()
150 ASSERT(ids[3] == trie["and"]); in TestTrie()
154 ASSERT(trie.predict("") == 4); in TestTrie()
155 ASSERT(trie.predict("a") == 3); in TestTrie()
156 ASSERT(trie.predict("ap") == 2); in TestTrie()
157 ASSERT(trie.predict("app") == 2); in TestTrie()
158 ASSERT(trie.predict("appl") == 1); in TestTrie()
159 ASSERT(trie.predict("apple") == 1); in TestTrie()
160 ASSERT(trie.predict("appleX") == 0); in TestTrie()
161 ASSERT(trie.predict("X") == 0); in TestTrie()
164 ASSERT(trie.predict("a", &ids) == 3); in TestTrie()
166 ASSERT(ids[0] == trie["app"]); in TestTrie()
167 ASSERT(ids[1] == trie["and"]); in TestTrie()
168 ASSERT(ids[2] == trie["apple"]); in TestTrie()
171 ASSERT(trie.predict("a", &ids, &strs) == 3); in TestTrie()
173 ASSERT(ids[3] == trie["app"]); in TestTrie()
174 ASSERT(ids[4] == trie["apple"]); in TestTrie()
175 ASSERT(ids[5] == trie["and"]); in TestTrie()
192 marisa_alpha::Trie trie; in TestPrefixTrie() local
194 trie.build(keys, &key_ids, 1 | MARISA_ALPHA_PREFIX_TRIE in TestPrefixTrie()
197 ASSERT(trie.num_tries() == 1); in TestPrefixTrie()
198 ASSERT(trie.num_keys() == 4); in TestPrefixTrie()
199 ASSERT(trie.num_nodes() == 7); in TestPrefixTrie()
204 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPrefixTrie()
206 ASSERT(trie[keys[i]] == key_ids[i]); in TestPrefixTrie()
207 ASSERT(trie[key_ids[i]] == keys[i]); in TestPrefixTrie()
212 key_length = trie.restore(key_ids[0], NULL, 0); in TestPrefixTrie()
215 EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_ALPHA_PARAM_ERROR); in TestPrefixTrie()
217 key_length = trie.restore(key_ids[0], key_buf, 5); in TestPrefixTrie()
221 key_length = trie.restore(key_ids[0], key_buf, 6); in TestPrefixTrie()
225 trie.build(keys, &key_ids, 2 | MARISA_ALPHA_PREFIX_TRIE in TestPrefixTrie()
228 ASSERT(trie.num_tries() == 2); in TestPrefixTrie()
229 ASSERT(trie.num_keys() == 4); in TestPrefixTrie()
230 ASSERT(trie.num_nodes() == 16); in TestPrefixTrie()
233 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPrefixTrie()
235 ASSERT(trie[keys[i]] == key_ids[i]); in TestPrefixTrie()
236 ASSERT(trie[key_ids[i]] == keys[i]); in TestPrefixTrie()
241 key_length = trie.restore(key_ids[0], NULL, 0); in TestPrefixTrie()
244 EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_ALPHA_PARAM_ERROR); in TestPrefixTrie()
246 key_length = trie.restore(key_ids[0], key_buf, 5); in TestPrefixTrie()
250 key_length = trie.restore(key_ids[0], key_buf, 6); in TestPrefixTrie()
254 trie.build(keys, &key_ids, 2 | MARISA_ALPHA_PREFIX_TRIE in TestPrefixTrie()
257 ASSERT(trie.num_tries() == 2); in TestPrefixTrie()
258 ASSERT(trie.num_keys() == 4); in TestPrefixTrie()
259 ASSERT(trie.num_nodes() == 14); in TestPrefixTrie()
262 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPrefixTrie()
264 ASSERT(trie[keys[i]] == key_ids[i]); in TestPrefixTrie()
265 ASSERT(trie[key_ids[i]] == keys[i]); in TestPrefixTrie()
270 trie.save("trie-test.dat"); in TestPrefixTrie()
271 trie.clear(); in TestPrefixTrie()
273 trie.mmap(&mapper, "trie-test.dat"); in TestPrefixTrie()
276 ASSERT(trie.num_tries() == 2); in TestPrefixTrie()
277 ASSERT(trie.num_keys() == 4); in TestPrefixTrie()
278 ASSERT(trie.num_nodes() == 14); in TestPrefixTrie()
281 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPrefixTrie()
283 ASSERT(trie[keys[i]] == key_ids[i]); in TestPrefixTrie()
284 ASSERT(trie[key_ids[i]] == keys[i]); in TestPrefixTrie()
290 trie.write(stream); in TestPrefixTrie()
291 trie.clear(); in TestPrefixTrie()
292 trie.read(stream); in TestPrefixTrie()
294 ASSERT(trie.num_tries() == 2); in TestPrefixTrie()
295 ASSERT(trie.num_keys() == 4); in TestPrefixTrie()
296 ASSERT(trie.num_nodes() == 14); in TestPrefixTrie()
299 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPrefixTrie()
301 ASSERT(trie[keys[i]] == key_ids[i]); in TestPrefixTrie()
302 ASSERT(trie[key_ids[i]] == keys[i]); in TestPrefixTrie()
307 trie.build(keys, &key_ids, 3 | MARISA_ALPHA_PREFIX_TRIE in TestPrefixTrie()
310 ASSERT(trie.num_tries() == 3); in TestPrefixTrie()
311 ASSERT(trie.num_keys() == 4); in TestPrefixTrie()
312 ASSERT(trie.num_nodes() == 19); in TestPrefixTrie()
315 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPrefixTrie()
317 ASSERT(trie[keys[i]] == key_ids[i]); in TestPrefixTrie()
318 ASSERT(trie[key_ids[i]] == keys[i]); in TestPrefixTrie()
323 ASSERT(trie["ca"] == trie.notfound()); in TestPrefixTrie()
324 ASSERT(trie["card"] == trie.notfound()); in TestPrefixTrie()
327 ASSERT(trie.find_first("ca") == trie.notfound()); in TestPrefixTrie()
328 ASSERT(trie.find_first("car") == trie["car"]); in TestPrefixTrie()
329 ASSERT(trie.find_first("card", &length) == trie["car"]); in TestPrefixTrie()
332 ASSERT(trie.find_last("afte") == trie.notfound()); in TestPrefixTrie()
333 ASSERT(trie.find_last("after") == trie["after"]); in TestPrefixTrie()
334 ASSERT(trie.find_last("afternoon", &length) == trie["after"]); in TestPrefixTrie()
340 ASSERT(trie.find("card", &ids, &lengths) == 1); in TestPrefixTrie()
342 ASSERT(ids[0] == trie["car"]); in TestPrefixTrie()
346 ASSERT(trie.predict("ca", &ids) == 2); in TestPrefixTrie()
348 ASSERT(ids[1] == trie["car"]); in TestPrefixTrie()
349 ASSERT(ids[2] == trie["caster"]); in TestPrefixTrie()
351 ASSERT(trie.predict("ca", &ids, NULL, 1) == 1); in TestPrefixTrie()
353 ASSERT(ids[3] == trie["car"]); in TestPrefixTrie()
356 ASSERT(trie.predict("ca", &ids, &strs, 1) == 1); in TestPrefixTrie()
358 ASSERT(ids[4] == trie["car"]); in TestPrefixTrie()
362 ASSERT(trie.predict_callback("", PredictCallback(&ids, &strs)) == 4); in TestPrefixTrie()
364 ASSERT(ids[5] == trie["car"]); in TestPrefixTrie()
365 ASSERT(ids[6] == trie["caster"]); in TestPrefixTrie()
366 ASSERT(ids[7] == trie["after"]); in TestPrefixTrie()
367 ASSERT(ids[8] == trie["bar"]); in TestPrefixTrie()
378 ASSERT(trie.find("card", ids, lengths, 10) == 1); in TestPrefixTrie()
379 ASSERT(ids[0] == trie["car"]); in TestPrefixTrie()
382 ASSERT(trie.predict("ca", ids, NULL, 10) == 2); in TestPrefixTrie()
383 ASSERT(ids[0] == trie["car"]); in TestPrefixTrie()
384 ASSERT(ids[1] == trie["caster"]); in TestPrefixTrie()
386 ASSERT(trie.predict("ca", ids, NULL, 1) == 1); in TestPrefixTrie()
387 ASSERT(ids[0] == trie["car"]); in TestPrefixTrie()
390 ASSERT(trie.predict("ca", ids, strs, 1) == 1); in TestPrefixTrie()
391 ASSERT(ids[0] == trie["car"]); in TestPrefixTrie()
394 ASSERT(trie.predict("", ids, strs, 10) == 4); in TestPrefixTrie()
395 ASSERT(ids[0] == trie["car"]); in TestPrefixTrie()
396 ASSERT(ids[1] == trie["caster"]); in TestPrefixTrie()
397 ASSERT(ids[2] == trie["after"]); in TestPrefixTrie()
398 ASSERT(ids[3] == trie["bar"]); in TestPrefixTrie()
406 trie.map(trie_data.c_str(), trie_data.length()); in TestPrefixTrie()
408 ASSERT(trie.num_tries() == 2); in TestPrefixTrie()
409 ASSERT(trie.num_keys() == 4); in TestPrefixTrie()
410 ASSERT(trie.num_nodes() == 14); in TestPrefixTrie()
413 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPrefixTrie()
415 ASSERT(trie[keys[i]] == key_ids[i]); in TestPrefixTrie()
416 ASSERT(trie[key_ids[i]] == keys[i]); in TestPrefixTrie()
434 marisa_alpha::Trie trie; in TestPatriciaTrie() local
436 trie.build(keys, &key_ids, 1); in TestPatriciaTrie()
438 ASSERT(trie.num_tries() == 1); in TestPatriciaTrie()
439 ASSERT(trie.num_keys() == 4); in TestPatriciaTrie()
440 ASSERT(trie.num_nodes() == 7); in TestPatriciaTrie()
452 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPatriciaTrie()
454 ASSERT(trie[keys[i]] == key_ids[i]); in TestPatriciaTrie()
455 ASSERT(trie[key_ids[i]] == keys[i]); in TestPatriciaTrie()
460 trie.build(keys, &key_ids, 2 | MARISA_ALPHA_WITHOUT_TAIL); in TestPatriciaTrie()
462 ASSERT(trie.num_tries() == 2); in TestPatriciaTrie()
463 ASSERT(trie.num_keys() == 4); in TestPatriciaTrie()
464 ASSERT(trie.num_nodes() == 17); in TestPatriciaTrie()
467 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPatriciaTrie()
469 ASSERT(trie[keys[i]] == key_ids[i]); in TestPatriciaTrie()
470 ASSERT(trie[key_ids[i]] == keys[i]); in TestPatriciaTrie()
475 trie.build(keys, &key_ids, 2); in TestPatriciaTrie()
477 ASSERT(trie.num_tries() == 2); in TestPatriciaTrie()
478 ASSERT(trie.num_keys() == 4); in TestPatriciaTrie()
479 ASSERT(trie.num_nodes() == 14); in TestPatriciaTrie()
482 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPatriciaTrie()
484 ASSERT(trie[keys[i]] == key_ids[i]); in TestPatriciaTrie()
485 ASSERT(trie[key_ids[i]] == keys[i]); in TestPatriciaTrie()
490 trie.build(keys, &key_ids, 3 | MARISA_ALPHA_WITHOUT_TAIL); in TestPatriciaTrie()
492 ASSERT(trie.num_tries() == 3); in TestPatriciaTrie()
493 ASSERT(trie.num_keys() == 4); in TestPatriciaTrie()
494 ASSERT(trie.num_nodes() == 20); in TestPatriciaTrie()
497 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPatriciaTrie()
499 ASSERT(trie[keys[i]] == key_ids[i]); in TestPatriciaTrie()
500 ASSERT(trie[key_ids[i]] == keys[i]); in TestPatriciaTrie()
506 trie.write(stream); in TestPatriciaTrie()
507 trie.clear(); in TestPatriciaTrie()
508 trie.read(stream); in TestPatriciaTrie()
510 ASSERT(trie.num_tries() == 3); in TestPatriciaTrie()
511 ASSERT(trie.num_keys() == 4); in TestPatriciaTrie()
512 ASSERT(trie.num_nodes() == 20); in TestPatriciaTrie()
515 key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); in TestPatriciaTrie()
517 ASSERT(trie[keys[i]] == key_ids[i]); in TestPatriciaTrie()
518 ASSERT(trie[key_ids[i]] == keys[i]); in TestPatriciaTrie()
532 marisa_alpha::Trie trie; in TestEmptyString() local
534 trie.build(keys, &key_ids); in TestEmptyString()
536 ASSERT(trie.num_tries() == 1); in TestEmptyString()
537 ASSERT(trie.num_keys() == 1); in TestEmptyString()
538 ASSERT(trie.num_nodes() == 1); in TestEmptyString()
543 ASSERT(trie[""] == 0); in TestEmptyString()
544 ASSERT(trie[(marisa_alpha::UInt32)0] == ""); in TestEmptyString()
546 ASSERT(trie["x"] == trie.notfound()); in TestEmptyString()
547 ASSERT(trie.find_first("") == 0); in TestEmptyString()
548 ASSERT(trie.find_first("x") == 0); in TestEmptyString()
549 ASSERT(trie.find_last("") == 0); in TestEmptyString()
550 ASSERT(trie.find_last("x") == 0); in TestEmptyString()
553 ASSERT(trie.find("xyz", &ids) == 1); in TestEmptyString()
555 ASSERT(ids[0] == trie[""]); in TestEmptyString()
558 ASSERT(trie.find("xyz", &ids, &lengths) == 1); in TestEmptyString()
560 ASSERT(ids[0] == trie[""]); in TestEmptyString()
561 ASSERT(ids[1] == trie[""]); in TestEmptyString()
565 ASSERT(trie.find_callback("xyz", FindCallback(&ids, &lengths)) == 1); in TestEmptyString()
567 ASSERT(ids[2] == trie[""]); in TestEmptyString()
571 ASSERT(trie.predict("xyz", &ids) == 0); in TestEmptyString()
573 ASSERT(trie.predict("", &ids) == 1); in TestEmptyString()
575 ASSERT(ids[3] == trie[""]); in TestEmptyString()
578 ASSERT(trie.predict("", &ids, &strs) == 1); in TestEmptyString()
580 ASSERT(ids[4] == trie[""]); in TestEmptyString()
596 marisa_alpha::Trie trie; in TestBinaryKey() local
598 trie.build(keys, &key_ids, 1 | MARISA_ALPHA_WITHOUT_TAIL); in TestBinaryKey()
600 ASSERT(trie.num_tries() == 1); in TestBinaryKey()
601 ASSERT(trie.num_keys() == 1); in TestBinaryKey()
602 ASSERT(trie.num_nodes() == 8); in TestBinaryKey()
607 key_length = trie.restore(0, key_buf, sizeof(key_buf)); in TestBinaryKey()
609 ASSERT(trie[keys[0]] == key_ids[0]); in TestBinaryKey()
610 ASSERT(trie[key_ids[0]] == keys[0]); in TestBinaryKey()
613 trie.build(keys, &key_ids, in TestBinaryKey()
616 ASSERT(trie.num_tries() == 1); in TestBinaryKey()
617 ASSERT(trie.num_keys() == 1); in TestBinaryKey()
618 ASSERT(trie.num_nodes() == 2); in TestBinaryKey()
621 key_length = trie.restore(0, key_buf, sizeof(key_buf)); in TestBinaryKey()
623 ASSERT(trie[keys[0]] == key_ids[0]); in TestBinaryKey()
624 ASSERT(trie[key_ids[0]] == keys[0]); in TestBinaryKey()
627 trie.build(keys, &key_ids, in TestBinaryKey()
630 ASSERT(trie.num_tries() == 1); in TestBinaryKey()
631 ASSERT(trie.num_keys() == 1); in TestBinaryKey()
632 ASSERT(trie.num_nodes() == 2); in TestBinaryKey()
635 key_length = trie.restore(0, key_buf, sizeof(key_buf)); in TestBinaryKey()
637 ASSERT(trie[keys[0]] == key_ids[0]); in TestBinaryKey()
638 ASSERT(trie[key_ids[0]] == keys[0]); in TestBinaryKey()
642 ASSERT(trie.predict_breadth_first("", &ids) == 1); in TestBinaryKey()
647 ASSERT(trie.predict_depth_first("NP", &ids, &strs) == 1); in TestBinaryKey()