1 // Copyright (C) 2003 Davis E. King (davis@dlib.net) 2 // License: Boost Software License See LICENSE.txt for the full license. 3 #ifndef DLIB_BINARY_SEARCH_TREE_KERNEl_TEST_H_ 4 #define DLIB_BINARY_SEARCH_TREE_KERNEl_TEST_H_ 5 6 7 #include <sstream> 8 #include <string> 9 #include <cstdlib> 10 #include <ctime> 11 12 #include <dlib/memory_manager_global.h> 13 #include <dlib/memory_manager_stateless.h> 14 #include <dlib/binary_search_tree.h> 15 #include "tester.h" 16 17 namespace 18 { 19 20 using namespace test; 21 using namespace std; 22 using namespace dlib; 23 24 logger dlog("test.binary_search_tree"); 25 26 template < 27 typename bst 28 > binary_search_tree_kernel_test()29 void binary_search_tree_kernel_test ( 30 ) 31 /*! 32 requires 33 - bst is an implementation of 34 binary_search_tree/binary_search_tree_kernel_abstract.h is instantiated 35 to map int to int 36 ensures 37 - runs tests on bst for compliance with the specs 38 !*/ 39 { 40 41 bst test, test2; 42 43 srand(static_cast<unsigned int>(time(0))); 44 45 46 DLIB_TEST(test.count(3) == 0); 47 48 enumerable<map_pair<int,int> >& e = test; 49 DLIB_TEST(e.at_start() == true); 50 51 DLIB_TEST(test.count(3) == 0); 52 53 for (int i = 0; i < 4; ++i) 54 { 55 DLIB_TEST(test.size() == 0); 56 DLIB_TEST(test.count(3) == 0); 57 DLIB_TEST(test.height() == 0); 58 DLIB_TEST(test[5] == 0); 59 DLIB_TEST(test[0] == 0); 60 DLIB_TEST(test.at_start()); 61 DLIB_TEST(test.current_element_valid() == false); 62 DLIB_TEST(test.count(3) == 0); 63 64 DLIB_TEST(test.move_next() == false); 65 DLIB_TEST(test.move_next() == false); 66 DLIB_TEST(test.move_next() == false); 67 DLIB_TEST(test.move_next() == false); 68 DLIB_TEST(test.move_next() == false); 69 DLIB_TEST(test.count(3) == 0); 70 71 DLIB_TEST(test.at_start() == false); 72 DLIB_TEST(test.current_element_valid() == false); 73 74 test.clear(); 75 test.position_enumerator(5); 76 DLIB_TEST(test.current_element_valid() == false); 77 DLIB_TEST(test.at_start() == false); 78 test.position_enumerator(5); 79 DLIB_TEST(test.current_element_valid() == false); 80 DLIB_TEST(test.at_start() == false); 81 test.position_enumerator(9); 82 DLIB_TEST(test.current_element_valid() == false); 83 DLIB_TEST(test.at_start() == false); 84 test.clear(); 85 test.position_enumerator(5); 86 DLIB_TEST(test.current_element_valid() == false); 87 DLIB_TEST(test.at_start() == false); 88 test.position_enumerator(5); 89 DLIB_TEST(test.current_element_valid() == false); 90 DLIB_TEST(test.at_start() == false); 91 test.position_enumerator(9); 92 DLIB_TEST(test.current_element_valid() == false); 93 DLIB_TEST(test.at_start() == false); 94 test.clear(); 95 DLIB_TEST(test.at_start() == true); 96 DLIB_TEST(test.current_element_valid() == false); 97 98 99 DLIB_TEST(test.count(3) == 0); 100 101 DLIB_TEST(test.size() == 0); 102 DLIB_TEST(test.height() == 0); 103 DLIB_TEST(test[5] == 0); 104 DLIB_TEST(test[0] == 0); 105 DLIB_TEST(const_cast<const bst&>(test)[5] == 0); 106 DLIB_TEST(const_cast<const bst&>(test)[0] == 0); 107 DLIB_TEST(test.at_start()); 108 DLIB_TEST(test.current_element_valid() == false); 109 110 DLIB_TEST(test.move_next() == false); 111 DLIB_TEST(test.move_next() == false); 112 DLIB_TEST(test.move_next() == false); 113 DLIB_TEST(test.move_next() == false); 114 DLIB_TEST(test.move_next() == false); 115 116 DLIB_TEST(test.at_start() == false); 117 DLIB_TEST(test.current_element_valid() == false); 118 119 120 DLIB_TEST(test.count(3) == 0); 121 test.reset(); 122 DLIB_TEST(test.count(3) == 0); 123 124 DLIB_TEST(test.at_start()); 125 DLIB_TEST(test.current_element_valid() == false); 126 127 128 129 130 131 132 int a = 0, b = 0; 133 134 for (int i = 0; i < 10000; ++i) 135 { 136 a = ::rand()%1000; 137 int temp = a; 138 unsigned long count = test.count(a); 139 test.add(a,b); 140 DLIB_TEST(test.count(temp) == count+1); 141 } 142 143 144 { 145 unsigned long count = test.count(3); 146 147 a = 3; test.add(a,b); ++count; 148 DLIB_TEST(test.count(3) == count); 149 a = 3; test.add(a,b); ++count; 150 DLIB_TEST(test.count(3) == count); 151 a = 3; test.add(a,b); ++count; 152 DLIB_TEST(test.count(3) == count); 153 a = 3; test.add(a,b); ++count; 154 DLIB_TEST(test.count(3) == count); 155 } 156 157 158 test.clear(); 159 160 161 162 163 164 for (int i = 0; i < 10000; ++i) 165 { 166 a = ::rand()&0x7FFF; 167 b = 0; 168 int temp = a; 169 unsigned long count = test.count(a); 170 test.add(a,b); 171 DLIB_TEST(test.count(temp) == count+1); 172 } 173 174 // serialize the state of test, then clear test, then 175 // load the state back into test. 176 ostringstream sout; 177 serialize(test,sout); 178 istringstream sin(sout.str()); 179 test.clear(); 180 deserialize(test,sin); 181 182 DLIB_TEST(test.size() == 10000); 183 DLIB_TEST(test.at_start() == true); 184 DLIB_TEST(test.current_element_valid() == false); 185 186 187 DLIB_TEST_MSG(test.height() > 13 && test.height() <= 26,"this is somewhat of an implementation dependent " 188 << "but really it should be in this range or the implementation is just crap"); 189 190 a = 0; 191 unsigned long count = 0; 192 while (test.move_next()) 193 { 194 DLIB_TEST_MSG(a <= test.element().key(),"the numers are out of order but they should be in order"); 195 a = test.element().key(); 196 ++count; 197 198 199 DLIB_TEST(test.at_start() == false); 200 DLIB_TEST(test.current_element_valid() == true); 201 } 202 203 DLIB_TEST(test.move_next() == false); 204 DLIB_TEST(test.move_next() == false); 205 DLIB_TEST(test.move_next() == false); 206 207 DLIB_TEST(count == 10000); 208 209 210 211 212 DLIB_TEST_MSG(test.height() > 13 && test.height() <= 26,"this is somewhat of an implementation dependent " 213 << "but really it should be in this range or the implementation is just crap"); 214 215 DLIB_TEST(test.at_start() == false); 216 DLIB_TEST(test.current_element_valid() == false); 217 DLIB_TEST(test.size() == 10000); 218 219 220 swap(test,test2); 221 222 223 test2.reset(); 224 count = 0; 225 a = 0; 226 while (test2.move_next()) 227 { 228 DLIB_TEST_MSG(a <= test2.element().key(),"the numers are out of order but they should be in order"); 229 a = test2.element().key(); 230 ++count; 231 232 233 DLIB_TEST(test2.at_start() == false); 234 DLIB_TEST(test2.current_element_valid() == true); 235 236 if (count == 5000) 237 { 238 break; 239 } 240 } 241 242 DLIB_TEST(test2.move_next() == true); 243 DLIB_TEST(test2.move_next() == true); 244 DLIB_TEST(test2.move_next() == true); 245 246 247 test2.reset(); 248 249 count = 0; 250 a = 0; 251 while (test2.move_next()) 252 { 253 DLIB_TEST_MSG(a <= test2.element().key(),"the numers are out of order but they should be in order"); 254 a = test2.element().key(); 255 ++count; 256 257 258 DLIB_TEST(test2.at_start() == false); 259 DLIB_TEST(test2.current_element_valid() == true); 260 } 261 262 DLIB_TEST(count == 10000); 263 DLIB_TEST(test2.move_next() == false); 264 DLIB_TEST(test2.move_next() == false); 265 DLIB_TEST(test2.move_next() == false); 266 267 268 269 270 271 272 273 274 int last = 0; 275 asc_pair_remover<int,int,typename bst::compare_type>& asdf = test2; 276 DLIB_TEST(asdf.size() > 0); 277 while (asdf.size() > 0) 278 { 279 asdf.remove_any(a,b); 280 DLIB_TEST(last <= a); 281 last = a; 282 --count; 283 DLIB_TEST(asdf.size() == count); 284 } 285 286 287 DLIB_TEST(test2.size() == 0); 288 DLIB_TEST(test2.height() ==0); 289 DLIB_TEST(test2.at_start() == true); 290 DLIB_TEST(test2.current_element_valid() == false); 291 DLIB_TEST(test2.move_next() == false); 292 DLIB_TEST(test2.move_next() == false); 293 DLIB_TEST(test2.move_next() == false); 294 295 296 297 298 for (int i = 0; i < 10000; ++i) 299 { 300 a = i; 301 b = i; 302 test2.add(a,b); 303 DLIB_TEST(test2.size() == (unsigned int)(i +1)); 304 DLIB_TEST(test2.count(i) == 1); 305 } 306 307 a = 0; 308 test2.position_enumerator(a); 309 DLIB_TEST(test2.at_start() == false); 310 DLIB_TEST(test2.element().key() == a); 311 DLIB_TEST(test2.element().value() == a); 312 a = 0; 313 test2.position_enumerator(a); 314 DLIB_TEST(test2.element().key() == a); 315 DLIB_TEST(test2.element().value() == a); 316 a = 8; 317 test2.position_enumerator(a); 318 DLIB_TEST(test2.at_start() == false); 319 DLIB_TEST(test2.element().key() == a); 320 DLIB_TEST(test2.element().value() == a); 321 a = 1; 322 test2.position_enumerator(a); 323 DLIB_TEST(test2.element().key() == a); 324 DLIB_TEST(test2.element().value() == a); 325 a = -29; 326 test2.position_enumerator(a); 327 DLIB_TEST(test2.element().key() == 0); 328 DLIB_TEST(test2.element().value() == 0); 329 a = 10000; 330 test2.position_enumerator(a); 331 DLIB_TEST(test2.at_start() == false); 332 DLIB_TEST(test2.current_element_valid() == false); 333 a = -29; 334 test2.position_enumerator(a); 335 DLIB_TEST(test2.element().key() == 0); 336 DLIB_TEST(test2.element().value() == 0); 337 a = 8; 338 test2.position_enumerator(a); 339 DLIB_TEST(test2.at_start() == false); 340 DLIB_TEST(test2.element().key() == a); 341 DLIB_TEST(test2.element().value() == a); 342 test2.reset(); 343 344 345 DLIB_TEST_MSG(test2.height() > 13 && test2.height() <= 26,"this is somewhat of an implementation dependent " 346 << "but really it should be in this range or the implementation is just crap"); 347 348 DLIB_TEST(test2.at_start() == true); 349 DLIB_TEST(test2.current_element_valid() == false); 350 DLIB_TEST(test2.size() == 10000); 351 352 353 for (int i = 0; i < 10000; ++i) 354 { 355 DLIB_TEST(test2.move_next() == true); 356 DLIB_TEST(test2.element().key() == i); 357 } 358 359 360 361 DLIB_TEST_MSG(test2.height() > 13 && test2.height() <= 26,"this is somewhat of an implementation dependent " 362 << "but really it should be in this range or the implementation is just crap"); 363 364 DLIB_TEST(test2.at_start() == false); 365 DLIB_TEST(test2.current_element_valid() == true); 366 DLIB_TEST(test2.size() == 10000); 367 368 369 DLIB_TEST(test2.move_next() == false); 370 DLIB_TEST(test2.current_element_valid() == false); 371 372 a = 3; 373 test2.add(a,b); 374 DLIB_TEST(test2.count(3) == 2); 375 376 377 for (int i = 0; i < 10000; ++i) 378 { 379 test2.remove(i,a,b); 380 DLIB_TEST(i == a); 381 } 382 test2.remove(3,a,b); 383 384 385 DLIB_TEST(test2.size() == 0); 386 DLIB_TEST(test2.height() == 0); 387 DLIB_TEST(test2.at_start() == true); 388 DLIB_TEST(test2.current_element_valid() == false); 389 DLIB_TEST(test2.move_next() == false); 390 DLIB_TEST(test2.at_start() == false); 391 DLIB_TEST(test2.current_element_valid() == false); 392 393 394 395 test2.clear(); 396 397 398 int m = 0; 399 for (int i = 0; i < 10000; ++i) 400 { 401 a = ::rand()&0x7FFF; 402 m = max(a,m); 403 test2.add(a,b); 404 } 405 406 DLIB_TEST(test2.at_start() == true); 407 DLIB_TEST(test2.move_next() == true); 408 DLIB_TEST(test2.at_start() == false); 409 DLIB_TEST(test2.current_element_valid() == true); 410 DLIB_TEST(test2.move_next() == true); 411 DLIB_TEST(test2.current_element_valid() == true); 412 DLIB_TEST(test2.move_next() == true); 413 DLIB_TEST(test2.current_element_valid() == true); 414 DLIB_TEST(test2.move_next() == true); 415 DLIB_TEST(test2.current_element_valid() == true); 416 DLIB_TEST(test2.at_start() == false); 417 418 for (int i = 0; i < 10000; ++i) 419 { 420 a = ::rand()&0xFFFF; 421 test2.position_enumerator(a); 422 if (test2[a]) 423 { 424 DLIB_TEST(test2.element().key() == a); 425 } 426 else if (a <= m) 427 { 428 DLIB_TEST(test2.element().key() > a); 429 } 430 } 431 432 test2.clear(); 433 434 DLIB_TEST(test2.current_element_valid() == false); 435 DLIB_TEST(test2.at_start() == true); 436 DLIB_TEST(test2.move_next() == false); 437 DLIB_TEST(test2.at_start() == false); 438 DLIB_TEST(test2.current_element_valid() == false); 439 DLIB_TEST(test2.move_next() == false); 440 DLIB_TEST(test2.current_element_valid() == false); 441 DLIB_TEST(test2.move_next() == false); 442 DLIB_TEST(test2.current_element_valid() == false); 443 DLIB_TEST(test2.at_start() == false); 444 445 446 DLIB_TEST(test2.size() == 0); 447 DLIB_TEST(test2.height() == 0); 448 449 450 for (int i = 0; i < 20000; ++i) 451 { 452 a = ::rand()&0x7FFF; 453 b = a; 454 test2.add(a,b); 455 } 456 457 458 DLIB_TEST(test2.size() == 20000); 459 460 461 462 // remove a bunch of elements randomly 463 int c; 464 for (int i = 0; i < 50000; ++i) 465 { 466 a = ::rand()&0x7FFF; 467 if (test2[a] != 0) 468 { 469 test2.remove(a,b,c); 470 DLIB_TEST(a == b); 471 } 472 } 473 474 475 // now add a bunch more 476 for (int i = 0; i < 10000; ++i) 477 { 478 a = ::rand()&0x7FFF; 479 b = a; 480 test2.add(a,b); 481 } 482 483 484 // now iterate over it all and then remove all elements 485 { 486 int* array = new int[test2.size()]; 487 int* tmp = array; 488 DLIB_TEST(test2.at_start() == true); 489 while (test2.move_next()) 490 { 491 *tmp = test2.element().key(); 492 ++tmp; 493 } 494 495 DLIB_TEST(test2.at_start() == false); 496 DLIB_TEST(test2.current_element_valid() == false); 497 DLIB_TEST(test2.move_next() == false); 498 499 tmp = array; 500 for (int i = 0; i < 10000; ++i) 501 { 502 DLIB_TEST(*test2[*tmp] == *tmp); 503 DLIB_TEST(*test2[*tmp] == *tmp); 504 DLIB_TEST(*test2[*tmp] == *tmp); 505 DLIB_TEST(*const_cast<const bst&>(test2)[*tmp] == *tmp); 506 ++tmp; 507 } 508 509 tmp = array; 510 while (test2.size() > 0) 511 { 512 unsigned long count = test2.count(*tmp); 513 test2.destroy(*tmp); 514 DLIB_TEST(test2.count(*tmp)+1 == count); 515 ++tmp; 516 } 517 518 DLIB_TEST(test2.at_start() == true); 519 DLIB_TEST(test2.current_element_valid() == false); 520 DLIB_TEST(test2.move_next() == false); 521 DLIB_TEST(test2.at_start() == false); 522 test.swap(test2); 523 test.reset(); 524 525 delete [] array; 526 } 527 528 529 DLIB_TEST(test.size() == 0); 530 DLIB_TEST(test.height() == 0); 531 532 for (unsigned long i = 1; i < 100; ++i) 533 { 534 a = 1234; 535 test.add(a,b); 536 DLIB_TEST(test.count(1234) == i); 537 } 538 539 test.clear(); 540 541 542 543 544 545 546 for (int m = 0; m < 3; ++m) 547 { 548 549 test2.clear(); 550 551 DLIB_TEST(test2.current_element_valid() == false); 552 DLIB_TEST(test2.at_start() == true); 553 DLIB_TEST(test2.move_next() == false); 554 DLIB_TEST(test2.at_start() == false); 555 DLIB_TEST(test2.current_element_valid() == false); 556 DLIB_TEST(test2.move_next() == false); 557 DLIB_TEST(test2.current_element_valid() == false); 558 DLIB_TEST(test2.move_next() == false); 559 DLIB_TEST(test2.current_element_valid() == false); 560 DLIB_TEST(test2.at_start() == false); 561 562 563 DLIB_TEST(test2.size() == 0); 564 DLIB_TEST(test2.height() == 0); 565 566 567 int counter = 0; 568 while (counter < 10000) 569 { 570 a = ::rand()&0x7FFF; 571 b = ::rand()&0x7FFF; 572 if (test2[a] == 0) 573 { 574 test2.add(a,b); 575 ++counter; 576 } 577 578 } 579 580 581 582 DLIB_TEST(test2.size() == 10000); 583 584 585 586 // remove a bunch of elements randomly 587 for (int i = 0; i < 20000; ++i) 588 { 589 a = ::rand()&0x7FFF; 590 if (test2[a] != 0) 591 { 592 test2.remove(a,b,c); 593 DLIB_TEST(a == b); 594 } 595 } 596 597 598 // now add a bunch more 599 for (int i = 0; i < 20000; ++i) 600 { 601 a = ::rand()&0x7FFF; 602 b = ::rand()&0x7FFF; 603 if (test2[a] == 0) 604 test2.add(a,b); 605 } 606 607 608 // now iterate over it all and then remove all elements 609 { 610 int* array = new int[test2.size()]; 611 int* array_val = new int[test2.size()]; 612 int* tmp = array; 613 int* tmp_val = array_val; 614 DLIB_TEST(test2.at_start() == true); 615 int count = 0; 616 while (test2.move_next()) 617 { 618 *tmp = test2.element().key(); 619 ++tmp; 620 *tmp_val = test2.element().value(); 621 ++tmp_val; 622 623 DLIB_TEST(*test2[*(tmp-1)] == *(tmp_val-1)); 624 ++count; 625 } 626 627 DLIB_TEST(count == (int)test2.size()); 628 DLIB_TEST(test2.at_start() == false); 629 DLIB_TEST(test2.current_element_valid() == false); 630 DLIB_TEST(test2.move_next() == false); 631 632 tmp = array; 633 tmp_val = array_val; 634 for (unsigned long i = 0; i < test2.size(); ++i) 635 { 636 DLIB_TEST_MSG(*test2[*tmp] == *tmp_val,i); 637 DLIB_TEST(*test2[*tmp] == *tmp_val); 638 DLIB_TEST(*test2[*tmp] == *tmp_val); 639 DLIB_TEST(*const_cast<const bst&>(test2)[*tmp] == *tmp_val); 640 ++tmp; 641 ++tmp_val; 642 } 643 644 // out << "\nsize: " << test2.size() << endl; 645 // out << "height: " << test2.height() << endl; 646 647 tmp = array; 648 while (test2.size() > 0) 649 { 650 unsigned long count = test2.count(*tmp); 651 test2.destroy(*tmp); 652 DLIB_TEST(test2.count(*tmp)+1 == count); 653 ++tmp; 654 } 655 656 DLIB_TEST(test2.at_start() == true); 657 DLIB_TEST(test2.current_element_valid() == false); 658 DLIB_TEST(test2.move_next() == false); 659 DLIB_TEST(test2.at_start() == false); 660 test.swap(test2); 661 test.reset(); 662 663 delete [] array; 664 delete [] array_val; 665 } 666 667 668 DLIB_TEST(test.size() == 0); 669 DLIB_TEST(test.height() == 0); 670 671 for (unsigned long i = 1; i < 100; ++i) 672 { 673 a = 1234; 674 test.add(a,b); 675 DLIB_TEST(test.count(1234) == i); 676 } 677 678 test.clear(); 679 680 } 681 682 683 684 a = 1; 685 b = 2; 686 687 test.add(a,b); 688 689 test.position_enumerator(0); 690 a = 0; 691 b = 0; 692 DLIB_TEST(test.height() == 1); 693 test.remove_current_element(a,b); 694 DLIB_TEST(a == 1); 695 DLIB_TEST(b == 2); 696 DLIB_TEST(test.at_start() == false); 697 DLIB_TEST(test.current_element_valid() == false); 698 DLIB_TEST(test.height() == 0); 699 DLIB_TEST(test.size() == 0); 700 701 702 a = 1; 703 b = 2; 704 test.add(a,b); 705 a = 1; 706 b = 2; 707 test.add(a,b); 708 709 test.position_enumerator(0); 710 a = 0; 711 b = 0; 712 DLIB_TEST(test.height() == 2); 713 test.remove_current_element(a,b); 714 DLIB_TEST(a == 1); 715 DLIB_TEST(b == 2); 716 DLIB_TEST(test.at_start() == false); 717 DLIB_TEST(test.current_element_valid() == true); 718 DLIB_TEST(test.height() == 1); 719 DLIB_TEST(test.size() == 1); 720 721 test.remove_current_element(a,b); 722 DLIB_TEST(a == 1); 723 DLIB_TEST(b == 2); 724 DLIB_TEST(test.at_start() == false); 725 DLIB_TEST(test.current_element_valid() == false); 726 DLIB_TEST(test.height() == 0); 727 DLIB_TEST(test.size() == 0); 728 729 for (int i = 0; i < 100; ++i) 730 { 731 a = i; 732 b = i; 733 test.add(a,b); 734 } 735 736 DLIB_TEST(test.size() == 100); 737 test.remove_last_in_order(a,b); 738 DLIB_TEST(a == 99); 739 DLIB_TEST(b == 99); 740 DLIB_TEST(test.size() == 99); 741 test.remove_last_in_order(a,b); 742 DLIB_TEST(a == 98); 743 DLIB_TEST(b == 98); 744 DLIB_TEST(test.size() == 98); 745 746 test.position_enumerator(-10); 747 for (int i = 0; i < 97; ++i) 748 { 749 DLIB_TEST(test.element().key() == i); 750 DLIB_TEST(test.element().value() == i); 751 DLIB_TEST(test.move_next()); 752 } 753 DLIB_TEST(test.move_next() == false); 754 DLIB_TEST(test.current_element_valid() == false); 755 756 757 test.position_enumerator(10); 758 for (int i = 10; i < 97; ++i) 759 { 760 DLIB_TEST(test.element().key() == i); 761 DLIB_TEST(test.element().value() == i); 762 DLIB_TEST(test.move_next()); 763 } 764 DLIB_TEST(test.move_next() == false); 765 DLIB_TEST(test.current_element_valid() == false); 766 767 test.reset(); 768 DLIB_TEST(test.at_start()); 769 DLIB_TEST(test.current_element_valid() == false); 770 for (int i = 0; i < 98; ++i) 771 { 772 DLIB_TEST(test.move_next()); 773 DLIB_TEST(test.element().key() == i); 774 DLIB_TEST(test.element().value() == i); 775 } 776 DLIB_TEST_MSG(test.size() == 98, test.size()); 777 DLIB_TEST(test.move_next() == false); 778 779 test.position_enumerator(98); 780 DLIB_TEST(test.current_element_valid() == false); 781 DLIB_TEST(test.at_start() == false); 782 783 784 test.position_enumerator(50); 785 DLIB_TEST(test.element().key() == 50); 786 DLIB_TEST(test.element().value() == 50); 787 DLIB_TEST(test[50] != 0); 788 test.remove_current_element(a,b); 789 DLIB_TEST(test[50] == 0); 790 DLIB_TEST_MSG(test.size() == 97, test.size()); 791 DLIB_TEST(a == 50); 792 DLIB_TEST(b == 50); 793 DLIB_TEST(test.element().key() == 51); 794 DLIB_TEST(test.element().value() == 51); 795 DLIB_TEST(test.current_element_valid()); 796 test.remove_current_element(a,b); 797 DLIB_TEST_MSG(test.size() == 96, test.size()); 798 DLIB_TEST(a == 51); 799 DLIB_TEST(b == 51); 800 DLIB_TEST_MSG(test.element().key() == 52,test.element().key()); 801 DLIB_TEST_MSG(test.element().value() == 52,test.element().value()); 802 DLIB_TEST(test.current_element_valid()); 803 test.remove_current_element(a,b); 804 DLIB_TEST_MSG(test.size() == 95, test.size()); 805 DLIB_TEST(a == 52); 806 DLIB_TEST(b == 52); 807 DLIB_TEST_MSG(test.element().key() == 53,test.element().key()); 808 DLIB_TEST_MSG(test.element().value() == 53,test.element().value()); 809 DLIB_TEST(test.current_element_valid()); 810 test.position_enumerator(50); 811 DLIB_TEST_MSG(test.element().key() == 53,test.element().key()); 812 DLIB_TEST_MSG(test.element().value() == 53,test.element().value()); 813 DLIB_TEST(test.current_element_valid()); 814 test.position_enumerator(51); 815 DLIB_TEST_MSG(test.element().key() == 53,test.element().key()); 816 DLIB_TEST_MSG(test.element().value() == 53,test.element().value()); 817 DLIB_TEST(test.current_element_valid()); 818 test.position_enumerator(52); 819 DLIB_TEST_MSG(test.element().key() == 53,test.element().key()); 820 DLIB_TEST_MSG(test.element().value() == 53,test.element().value()); 821 DLIB_TEST(test.current_element_valid()); 822 test.position_enumerator(53); 823 DLIB_TEST_MSG(test.element().key() == 53,test.element().key()); 824 DLIB_TEST_MSG(test.element().value() == 53,test.element().value()); 825 DLIB_TEST(test.current_element_valid()); 826 827 test.reset(); 828 test.move_next(); 829 int lasta = -1, lastb = -1; 830 count = 0; 831 while (test.current_element_valid() ) 832 { 833 ++count; 834 int c = test.element().key(); 835 int d = test.element().value(); 836 test.remove_current_element(a,b); 837 DLIB_TEST(c == a); 838 DLIB_TEST(d == a); 839 DLIB_TEST(lasta < a); 840 DLIB_TEST(lastb < b); 841 lasta = a; 842 lastb = b; 843 } 844 DLIB_TEST_MSG(count == 95, count); 845 DLIB_TEST(test.size() == 0); 846 DLIB_TEST(test.height() == 0); 847 848 test.clear(); 849 850 for (int i = 0; i < 1000; ++i) 851 { 852 a = 1; 853 b = 1; 854 test.add(a,b); 855 } 856 857 for (int i = 0; i < 40; ++i) 858 { 859 int num = ::rand()%800 + 1; 860 test.reset(); 861 for (int j = 0; j < num; ++j) 862 { 863 DLIB_TEST(test.move_next()); 864 } 865 DLIB_TEST_MSG(test.current_element_valid(),"size: " << test.size() << " num: " << num); 866 test.remove_current_element(a,b); 867 DLIB_TEST_MSG(test.current_element_valid(),"size: " << test.size() << " num: " << num); 868 test.remove_current_element(a,b); 869 test.position_enumerator(1); 870 if (test.current_element_valid()) 871 test.remove_current_element(a,b); 872 DLIB_TEST(a == 1); 873 DLIB_TEST(b == 1); 874 } 875 876 test.clear(); 877 878 } 879 880 881 test.clear(); 882 test2.clear(); 883 884 } 885 886 } 887 888 #endif // DLIB_BINARY_SEARCH_TREE_KERNEl_TEST_H_ 889 890