1 module judy.judy1; 2 3 import core.exception; 4 import std.array; 5 import std.range; 6 7 import judy.libjudy; 8 9 /* 10 Provides D like wrapper around the libjudy C library 11 */ 12 struct Judy1Array 13 { 14 private: 15 void* array_; 16 17 public: 18 // Free the array 19 ~this() nothrow @nogc 20 { 21 Judy1FreeArray(&array_, NO_ERROR); 22 } 23 24 @property bool empty() const nothrow @nogc 25 { 26 return count == 0; 27 } 28 29 // Returns number of set bit in the Judy array 30 @property size_t count() const nothrow @nogc 31 { 32 return Judy1Count(array_, 0, -1, NO_ERROR); 33 } 34 35 36 // Get lowest index of set bit 37 @property size_t front() const 38 { 39 size_t index = 0; 40 if (first(index)) 41 { 42 return index; 43 } 44 throw new RangeError(); 45 } 46 47 // Unset lowest set bit 48 void popFront() 49 { 50 size_t index = 0; 51 if (first(index)) 52 { 53 unset(index); 54 } 55 else 56 { 57 throw new RangeError(); 58 } 59 } 60 61 62 // Get highest index of set bit 63 @property size_t back() const 64 { 65 size_t index = -1; 66 if (last(index)) 67 { 68 return index; 69 } 70 throw new RangeError(); 71 } 72 73 // Unset highest set bit 74 void popBack() 75 { 76 size_t index = -1; 77 if (last(index)) 78 { 79 unset(index); 80 } 81 else 82 { 83 throw new RangeError(); 84 } 85 } 86 87 88 // Create a (const) slice of the array 89 auto opSlice() const nothrow @nogc 90 { 91 return Judy1ArrayRange(array_); 92 } 93 94 // Create a (const) slice of the array from start to end 95 auto opSlice(const size_t start, const size_t end) const nothrow @nogc 96 { 97 return Judy1ArrayRange(array_, start, end); 98 } 99 100 // Returns highest set index 101 size_t opDollar() const 102 { 103 if (empty) 104 { 105 throw new RangeError(); 106 } 107 return back; 108 } 109 110 111 // Check if bit set at index 112 bool opIndex(const size_t index) const nothrow @nogc 113 { 114 return Judy1Test(array_, index, NO_ERROR) == 1; 115 } 116 117 118 // Set bit at index to value 119 void opIndexAssign(bool value, const size_t index) nothrow @nogc 120 { 121 if (value) 122 { 123 set(index); 124 } 125 else 126 { 127 unset(index); 128 } 129 } 130 131 // Set bit at index 132 bool set(const size_t index) nothrow @nogc 133 { 134 return Judy1Set(&array_, index, NO_ERROR) == 1; 135 } 136 137 // Unset bit at index 138 bool unset(const size_t index) nothrow @nogc 139 { 140 return Judy1Unset(&array_, index, NO_ERROR) == 1; 141 } 142 143 144 // Find first set bit and place it in index. Return false if not found 145 bool first(ref size_t index) const nothrow @nogc 146 { 147 return Judy1First(array_, &index, NO_ERROR) == 1; 148 } 149 150 // Find index of first, throws RangeError if empty 151 size_t first() const 152 { 153 return front; 154 } 155 156 // Find next set bit from index, and place it in index. Return false if not found 157 bool next(ref size_t index) const nothrow @nogc 158 { 159 return Judy1Next(array_, &index, NO_ERROR) == 1; 160 } 161 162 // Find prev set bit from index, and place it in index. Return false if not found 163 bool prev(ref size_t index) const nothrow @nogc 164 { 165 return Judy1Prev(array_, &index, NO_ERROR) == 1; 166 } 167 168 // Find last set bit and place it in index. Return false if not found 169 bool last(ref size_t index) const nothrow @nogc 170 { 171 return Judy1Last(array_, &index, NO_ERROR) == 1; 172 } 173 174 // Get index of last, throws RangeError if empty 175 size_t last() const 176 { 177 return back; 178 } 179 180 181 // Find first unset bit and place into index. Return false if not found 182 bool firstEmpty(ref size_t index) const nothrow @nogc 183 { 184 return Judy1FirstEmpty(array_, &index, NO_ERROR) == 1; 185 } 186 187 // Find next unset bit from index and place into index. Return false if not found; 188 bool nextEmpty(ref size_t index) const nothrow @nogc 189 { 190 return Judy1NextEmpty(array_, &index, NO_ERROR) == 1; 191 } 192 193 // Find prev unset bit from index and place into index. Return false if not found; 194 bool prevEmpty(ref size_t index) const nothrow @nogc 195 { 196 return Judy1PrevEmpty(array_, &index, NO_ERROR) == 1; 197 } 198 199 // Find last unset bit and place into index. Return false if not found 200 bool lastEmpty(ref size_t index) const nothrow @nogc 201 { 202 return Judy1LastEmpty(array_, &index, NO_ERROR) == 1; 203 } 204 205 206 // Return total amount of memory used by the population and infrastructure 207 @property size_t memUsed() const nothrow @nogc 208 { 209 return Judy1MemUsed(array_); 210 } 211 212 // Return total amount of memory used by the population 213 @property size_t memActive() const nothrow @nogc 214 { 215 return Judy1MemActive(array_); 216 } 217 218 // Iteration struct, allows fast read only iteration of the underlying Judy array 219 struct Judy1ArrayRange 220 { 221 private: 222 size_t leftBound_; 223 size_t rightBound_; 224 size_t firstIndex_; 225 size_t lastIndex_; 226 const void* array_; 227 228 public: 229 // Construct with no bounds specified 230 this(const ref void* array) nothrow @nogc 231 { 232 this(array, 0UL, -1UL); 233 } 234 235 // Construct with specified bounds 236 this(const ref void* array, const size_t firstIndex, const size_t lastIndex) nothrow @nogc 237 { 238 array_ = array; 239 leftBound_ = firstIndex_ = firstIndex; 240 rightBound_ = lastIndex_ = lastIndex; 241 242 // Sets first and last to the indices of the actual first and 243 // last within the bound. If the bound is empty sets first and 244 // last index to the 'empty' values (first > last) 245 if ( 246 Judy1First(array_, &firstIndex_, NO_ERROR) != 1 || 247 Judy1Last(array_, &lastIndex_, NO_ERROR) != 1 248 ) 249 { 250 firstIndex_ = 1; 251 lastIndex_ = 0; 252 } 253 254 } 255 256 // Is the slice empty of set bits? 257 @property bool empty() const nothrow @nogc 258 { 259 return firstIndex_ > lastIndex_; 260 } 261 262 // Get index of first set bit in slice 263 @property size_t front() 264 { 265 if (empty) 266 { 267 throw new RangeError(); 268 } 269 return firstIndex_; 270 } 271 272 // Discard and find next first bit of slice 273 void popFront() nothrow @nogc 274 { 275 // Empty check and update firstIndex_ 276 if (!Judy1Next(array_, &firstIndex_, NO_ERROR)) 277 { 278 firstIndex_ = 1; 279 lastIndex_ = 0; 280 } 281 } 282 283 // Find last set bit of slice 284 @property size_t back() 285 { 286 if (empty) 287 { 288 throw new RangeError(); 289 } 290 return lastIndex_; 291 } 292 293 // Discard and find prev last bit of slice 294 void popBack() nothrow @nogc 295 { 296 // Empty check and update lastIndex_ 297 if (!Judy1Prev(array_, &lastIndex_, NO_ERROR)) 298 { 299 firstIndex_ = 1; 300 lastIndex_ = 0; 301 } 302 } 303 304 // Get bit at index. Throws RangeError if index is outside the slice bounds 305 bool opIndex(const size_t index) const 306 { 307 if (index < leftBound_ || index > rightBound_) 308 { 309 throw new RangeError(); 310 } 311 return Judy1Test(array_, index, NO_ERROR) == 1; 312 } 313 314 // Return highest set index of slice 315 size_t opDollar() 316 { 317 return back; 318 } 319 320 // Save iteration state 321 @property auto save() nothrow @nogc 322 { 323 return this; 324 } 325 326 // Get count of bits set in the range of the slice 327 @property auto count() const nothrow @nogc 328 { 329 return Judy1Count(array_, leftBound_, rightBound_, NO_ERROR); 330 } 331 } 332 333 static assert(isInputRange!Judy1Array); 334 335 static assert(isInputRange!Judy1ArrayRange); 336 static assert(isForwardRange!Judy1ArrayRange); 337 static assert(isBidirectionalRange!Judy1ArrayRange); 338 } 339 340 341 version(unittest) 342 { 343 import std.algorithm; 344 import std.exception; 345 import std.stdio; 346 } 347 348 unittest 349 { 350 writeln("[UnitTest Judy1] - empty"); 351 352 auto array = Judy1Array(); 353 354 assert(array.empty, "Array starts empty"); 355 array[10] = false; 356 assert(array.empty, "Unsetting bit still empty"); 357 array[5] = true; 358 assert(!array.empty, "Setting bit no longer empty"); 359 array[5] = false; 360 assert(array.empty, "Array ends empty"); 361 362 array[size_t.max] = true; 363 assert(!array.empty); 364 } 365 366 unittest 367 { 368 writeln("[UnitTest Judy1] - count"); 369 370 auto array = Judy1Array(); 371 372 assert(array.count == 0, "Array counts starts at 0"); 373 374 array[0] = true; 375 assert(array.count == 1, "Adding bit"); 376 array[1] = false; 377 assert(array.count == 1, "Unset bit not included in count"); 378 array[1] = true; 379 assert(array.count == 2); 380 array[0] = false; 381 array[1] = false; 382 assert(array.count == 0, "Array count ends at 0"); 383 384 array[size_t.max] = true; 385 assert(array.count == 1); 386 } 387 388 unittest 389 { 390 writeln("[UnitTest Judy1] - front and back"); 391 392 auto array = Judy1Array(); 393 394 assertThrown!RangeError(array.front, "Empty array"); 395 assertThrown!RangeError(array.back, "Empty array"); 396 397 array[2] = true; 398 assert(array.front == 2); 399 assert(array.back == 2); 400 401 array[10] = true; 402 assert(array.front == 2); 403 assert(array.back == 10); 404 405 array[5] = true; 406 assert(array.front == 2); 407 assert(array.back == 10); 408 409 array[0] = true; 410 assert(array.front == 0); 411 assert(array.back == 10); 412 413 array[10] = false; 414 assert(array.front == 0); 415 assert(array.back == 5); 416 } 417 418 unittest 419 { 420 writeln("[UnitTest Judy1] - popFront and popBack"); 421 422 auto array = Judy1Array(); 423 424 assertThrown!RangeError(array.popFront, "Empty array"); 425 assertThrown!RangeError(array.popBack, "Empty array"); 426 427 array[0] = true; 428 array[1] = true; 429 array[9] = true; 430 array[10] = true; 431 432 array.popFront(); 433 assert(array.front == 1); 434 assert(array.back == 10); 435 436 array.popBack(); 437 assert(array.front == 1); 438 assert(array.back == 9); 439 440 array.popFront(); 441 assert(array.front == 9); 442 assert(array.back == 9); 443 444 array.popBack(); 445 assert(array.empty); 446 } 447 448 unittest 449 { 450 writeln("[UnitTest Judy1] - opDollar"); 451 452 auto array = Judy1Array(); 453 454 assertThrown!RangeError(array[$]); 455 456 array[0] = true; 457 assert(array[$]); 458 array[10] = true; 459 assert(array[0..$].count == 2); 460 } 461 462 unittest 463 { 464 writeln("[UnitTest Judy1] - opIndex"); 465 466 auto array = Judy1Array(); 467 468 array[0] = true; 469 array[3] = true; 470 array[4] = true; 471 array.set(5); 472 473 assert(array[0]); 474 assert(!array[1]); 475 assert(!array[2]); 476 assert(array[3]); 477 assert(array[4]); 478 assert(array[5]); 479 assert(!array[6]); 480 } 481 482 unittest 483 { 484 writeln("[UnitTest Judy1] - set and unset"); 485 486 auto array = Judy1Array(); 487 488 array.set(0); 489 assert(array[0]); 490 array.unset(0); 491 assert(!array[0]); 492 493 array.set(size_t.max); 494 assert(array[$]); 495 array.unset(size_t.max); 496 assert(!array[size_t.max]); 497 } 498 499 unittest 500 { 501 writeln("[UnitTest Judy1] - find in empty array"); 502 503 auto array = Judy1Array(); 504 505 size_t index = 0; 506 assert(!array.first(index)); 507 assertThrown!RangeError(array.first()); 508 509 index = 0; 510 assert(!array.next(index)); 511 512 index = -1; 513 assert(!array.prev(index)); 514 515 index = -1; 516 assert(!array.last(index)); 517 assertThrown!RangeError(array.last()); 518 } 519 520 unittest 521 { 522 writeln("[UnitTest Judy1] - find in array with single bit at start"); 523 524 auto array = Judy1Array(); 525 array[0] = true; 526 527 size_t index = 0; 528 assert(array.first(index)); 529 assert(index == 0); 530 assert(array.first() == 0); 531 532 index = 0; 533 assert(!array.next(index)); 534 535 index = 0; 536 assert(!array.prev(index)); 537 538 index = 0; 539 assert(array.last(index)); 540 assert(index == 0); 541 542 index = -1; 543 assert(array.prev(index)); 544 assert(index == 0); 545 546 index = -1; 547 assert(array.last(index)); 548 assert(index == 0); 549 assert(array.last() == 0); 550 } 551 552 unittest 553 { 554 writeln("[UnitTest Judy1] - find in array with multiple in middle"); 555 556 auto array = Judy1Array(); 557 array[10] = true; 558 array[11] = true; 559 560 size_t index = 0; 561 assert(array.first(index)); 562 assert(index == 10); 563 assert(array.first() == 10); 564 565 index = 0; 566 assert(array.next(index)); 567 assert(index == 10); 568 569 index = 0; 570 assert(!array.prev(index)); 571 572 index = 0; 573 assert(!array.last(index)); 574 575 576 577 index = 10; 578 assert(array.first(index)); 579 assert(index == 10); 580 581 index = 10; 582 assert(array.next(index)); 583 assert(index == 11); 584 585 index = 10; 586 assert(!array.prev(index)); 587 588 index = 10; 589 assert(array.last(index)); 590 assert(index == 10); 591 592 593 594 index = 11; 595 assert(array.first(index)); 596 assert(index == 11); 597 598 index = 11; 599 assert(!array.next(index)); 600 601 index = 11; 602 assert(array.prev(index)); 603 assert(index == 10); 604 605 index = 11; 606 assert(array.last(index)); 607 assert(index == 11); 608 609 610 611 index = -1; 612 assert(array.prev(index)); 613 assert(index == 11); 614 615 index = -1; 616 assert(array.last(index)); 617 assert(index == 11); 618 assert(array.last() == 11); 619 } 620 621 unittest 622 { 623 writeln("[UnitTest Judy1] - find in array with single bit at end"); 624 625 auto array = Judy1Array(); 626 auto END = size_t.max; 627 array[size_t.max] = true; 628 629 size_t index = 0; 630 assert(array.first(index)); 631 assert(index == END); 632 assert(array.first() == END); 633 634 index = 0; 635 assert(array.next(index)); 636 assert(index == END); 637 638 index = 0; 639 assert(!array.prev(index)); 640 641 index = 0; 642 assert(!array.last(index)); 643 644 index = -1; 645 assert(!array.prev(index)); 646 647 index = -1; 648 assert(array.last(index)); 649 assert(index == END); 650 assert(array.last() == END); 651 } 652 653 unittest 654 { 655 writeln("[UnitTest Judy1] - find empty in empty array"); 656 657 auto array = Judy1Array(); 658 659 size_t index = 0; 660 assert(array.firstEmpty(index)); 661 assert(index == 0); 662 663 assert(array.nextEmpty(index)); 664 assert(index == 1); 665 666 index = 0; 667 assert(!array.prevEmpty(index)); 668 669 index = 0; 670 assert(array.lastEmpty(index)); 671 assert(index == 0); 672 673 index = -1; 674 assert(array.prevEmpty(index)); 675 assert(index == size_t.max - 1); 676 677 index = -1; 678 assert(array.lastEmpty(index)); 679 assert(index == size_t.max); 680 } 681 682 unittest 683 { 684 writeln("[UnitTest Judy1] - find empty with single element at start"); 685 686 auto array = Judy1Array(); 687 array[0] = true; 688 689 size_t index = 0; 690 assert(array.firstEmpty(index)); 691 assert(index == 1); 692 693 index = 0; 694 assert(array.nextEmpty(index)); 695 assert(index == 1); 696 697 index = 0; 698 assert(!array.prevEmpty(index)); 699 700 index = 0; 701 assert(!array.lastEmpty(index)); 702 703 index = -1; 704 assert(array.prevEmpty(index)); 705 assert(index == size_t.max - 1); 706 707 index = -1; 708 assert(array.lastEmpty(index)); 709 assert(index == size_t.max); 710 } 711 712 unittest 713 { 714 writeln("[UnitTest Judy1] - find empty with single element in middle"); 715 716 auto array = Judy1Array(); 717 array[10] = true; 718 719 size_t index = 0; 720 assert(array.firstEmpty(index)); 721 assert(index == 0); 722 723 index = 0; 724 assert(array.nextEmpty(index)); 725 assert(index == 1); 726 727 index = 9; 728 assert(array.firstEmpty(index)); 729 assert(index == 9); 730 731 index = 9; 732 assert(array.nextEmpty(index)); 733 assert(index == 11); 734 735 index = 11; 736 assert(array.prevEmpty(index)); 737 assert(index == 9); 738 739 index = 11; 740 assert(array.lastEmpty(index)); 741 assert(index == 11); 742 } 743 744 unittest 745 { 746 writeln("[UnitTest Judy1] - iteration"); 747 748 auto array = Judy1Array(); 749 auto setrange = iota(100, 1000, 10); 750 751 foreach(ref index; array) 752 { 753 assert(false, "empty"); 754 } 755 756 foreach(index; setrange) 757 { 758 array[index] = true; 759 } 760 761 size_t j = 0; 762 foreach(ref index; array) 763 { 764 assert(index == setrange[j++]); 765 } 766 assert(j > 0); 767 768 j = 0; 769 foreach(ref index; array) 770 { 771 assert(index == setrange[j++]); 772 } 773 assert(j > 0); 774 } 775 776 unittest 777 { 778 writeln("[UnitTest Judy1] - free memory"); 779 780 Judy1Array* ptr; 781 782 { 783 auto array = Judy1Array(); 784 785 assert(array.memUsed == 0, "No memory used on empty array"); 786 assert(array.memActive == 0, "No memory active on empty array"); 787 788 auto testrange = iota(0, 100); 789 790 // Set some bits 791 foreach(index; testrange) 792 { 793 array[index] = true; 794 } 795 796 assert(array.count == 100, "Count updated"); 797 assert(array.memUsed > 0, "Memory used"); 798 assert(array.memActive > 0, "Memory active"); 799 800 ptr = &array; 801 } 802 803 assert(ptr.count == 0, "Count cleared"); 804 assert(ptr.memUsed == 0, "Memory reclaimed"); 805 assert(ptr.memActive == 0, "Memory reclaimed"); 806 } 807 808 unittest 809 { 810 writeln("[UnitTest Judy1] - opSlice"); 811 812 auto array = Judy1Array(); 813 814 auto testrange = iota(0UL, 100UL); 815 816 // Test empty 817 foreach(index; array[]) 818 { 819 assert(false, "Empty array"); 820 } 821 822 // Test one bit 823 array[0] = true; 824 size_t j = 0; 825 foreach(index; array[]) 826 { 827 assert(index == j++); 828 } 829 assert(j == 1); 830 array[0] = false; 831 832 // Set some bits 833 foreach(index; testrange) 834 { 835 array[index] = true; 836 } 837 838 839 assert(array.count == array[].count, "Array and slice length the same"); 840 841 j = 0; 842 foreach(index; array[]) 843 { 844 assert(index == testrange[j++]); 845 } 846 847 // backwards iteration 848 j = testrange.length; 849 foreach(index; retro(array[])) 850 { 851 assert(index == testrange[--j]); 852 } 853 854 auto slice = array[]; 855 array[7] = true; 856 assert(slice[7]); 857 array[7] = false; 858 assert(!slice[7]); 859 } 860 861 unittest 862 { 863 writeln("[UnitTest Judy1] - opSlice[x..y]"); 864 865 auto array = Judy1Array(); 866 867 auto testrange = iota(0, 100); 868 869 // Test empty 870 foreach(index; array[1..2]) 871 { 872 assert(false, "Empty array"); 873 } 874 875 // Test one bit 876 array[2] = true; 877 size_t j = 0; 878 foreach(index; array[0..5]) 879 { 880 assert(index == 2); 881 j++; 882 } 883 assert(j == 1); 884 array[2] = false; 885 886 // Insert some bits 887 foreach(index; testrange) 888 { 889 array[index] = true; 890 } 891 892 j = 20; 893 foreach(index; array[20..30]) 894 { 895 assert(index == testrange[j++], "Indexed slice"); 896 } 897 898 j = 25; 899 foreach(index; array[25..500]) 900 { 901 assert(index == testrange[j++], "Indexed slice beyond population"); 902 } 903 904 j = 90; 905 foreach(index; array[90..$]) 906 { 907 assert(index == testrange[j++], "opDollar slice"); 908 } 909 910 j = 20; 911 foreach(index; retro(array[10..20])) 912 { 913 assert(index == testrange[j--], "Retrograde slice"); 914 } 915 916 assertThrown!RangeError(array[10..20][9], "Out of bounds"); 917 assertThrown!RangeError(array[10..20][21], "Out of bounds"); 918 919 auto slice = array[10..20]; 920 array[12] = true; 921 assert(slice[12]); 922 array[12] = false; 923 assert(!slice[12]); 924 } 925