1 #include <sstream> 2 3 #include <marisa.h> 4 5 #include "assert.h" 6 7 namespace { 8 9 class 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 31 class 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 53 void 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 181 void 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 406 void 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 508 void 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 568 void 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 637 int main() { 638 TestTrie(); 639 TestPrefixTrie(); 640 TestPatriciaTrie(); 641 TestEmptyString(); 642 TestBinaryKey(); 643 644 return 0; 645 } 646
