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