1 /*********************** 2 * Source: $(PHOBOSSRC std/_bitarray.d) 3 * Macros: 4 * WIKI = StdBitarray 5 */ 6 7 module undead.bitarray; 8 9 //debug = bitarray; // uncomment to turn on debugging printf's 10 11 private import core.bitop; 12 13 /** 14 * An array of bits. 15 */ 16 17 struct BitArray 18 { 19 size_t len; 20 size_t* ptr; 21 22 size_t dim() 23 { 24 return (len + 31) / 32; 25 } 26 27 size_t length() const pure nothrow 28 { 29 return len; 30 } 31 32 void length(size_t newlen) 33 { 34 if (newlen != len) 35 { 36 size_t olddim = dim(); 37 size_t newdim = (newlen + 31) / 32; 38 39 if (newdim != olddim) 40 { 41 // Create a fake array so we can use D's realloc machinery 42 auto b = ptr[0 .. olddim]; 43 b.length = newdim; // realloc 44 ptr = b.ptr; 45 if (newdim & 31) 46 { // Set any pad bits to 0 47 ptr[newdim - 1] &= ~(~0 << (newdim & 31)); 48 } 49 } 50 51 len = newlen; 52 } 53 } 54 55 /********************************************** 56 * Support for [$(I index)] operation for BitArray. 57 */ 58 bool opIndex(size_t i) 59 in 60 { 61 assert(i < len); 62 } 63 do 64 { 65 return cast(bool)bt(ptr, i); 66 } 67 68 /** ditto */ 69 bool opIndexAssign(bool b, size_t i) 70 in 71 { 72 assert(i < len); 73 } 74 do 75 { 76 if (b) 77 bts(ptr, i); 78 else 79 btr(ptr, i); 80 return b; 81 } 82 83 /********************************************** 84 * Support for array.dup property for BitArray. 85 */ 86 BitArray dup() 87 { 88 BitArray ba; 89 90 auto b = ptr[0 .. dim].dup; 91 ba.len = len; 92 ba.ptr = b.ptr; 93 return ba; 94 } 95 96 unittest 97 { 98 BitArray a; 99 BitArray b; 100 101 debug(bitarray) printf("BitArray.dup.unittest\n"); 102 103 a.length = 3; 104 a[0] = 1; a[1] = 0; a[2] = 1; 105 b = a.dup; 106 assert(b.length == 3); 107 for (int i = 0; i < 3; i++) 108 { debug(bitarray) printf("b[%d] = %d\n", i, b[i]); 109 assert(b[i] == (((i ^ 1) & 1) ? true : false)); 110 } 111 } 112 113 /********************************************** 114 * Support for foreach loops for BitArray. 115 */ 116 int opApply(int delegate(ref bool) dg) 117 { 118 int result; 119 120 for (size_t i = 0; i < len; i++) 121 { bool b = opIndex(i); 122 result = dg(b); 123 (this)[i] = b; 124 if (result) 125 break; 126 } 127 return result; 128 } 129 130 /** ditto */ 131 int opApply(int delegate(ref size_t, ref bool) dg) 132 { 133 int result; 134 135 for (size_t i = 0; i < len; i++) 136 { bool b = opIndex(i); 137 result = dg(i, b); 138 (this)[i] = b; 139 if (result) 140 break; 141 } 142 return result; 143 } 144 145 unittest 146 { 147 debug(bitarray) printf("BitArray.opApply unittest\n"); 148 149 static bool[] ba = [1,0,1]; 150 151 BitArray a; a.init(ba); 152 153 int i; 154 foreach (b;a) 155 { 156 switch (i) 157 { case 0: assert(b == true); break; 158 case 1: assert(b == false); break; 159 case 2: assert(b == true); break; 160 default: assert(0); 161 } 162 i++; 163 } 164 165 foreach (j,b;a) 166 { 167 switch (j) 168 { case 0: assert(b == true); break; 169 case 1: assert(b == false); break; 170 case 2: assert(b == true); break; 171 default: assert(0); 172 } 173 } 174 } 175 176 177 /********************************************** 178 * Support for array.reverse property for BitArray. 179 */ 180 181 BitArray reverse() 182 out (result) 183 { 184 assert(result == this); 185 } 186 do 187 { 188 if (len >= 2) 189 { 190 bool t; 191 size_t lo, hi; 192 193 lo = 0; 194 hi = len - 1; 195 for (; lo < hi; lo++, hi--) 196 { 197 t = (this)[lo]; 198 (this)[lo] = (this)[hi]; 199 (this)[hi] = t; 200 } 201 } 202 return this; 203 } 204 205 unittest 206 { 207 debug(bitarray) printf("BitArray.reverse.unittest\n"); 208 209 BitArray b; 210 static bool[5] data = [1,0,1,1,0]; 211 int i; 212 213 b.init(data); 214 b.reverse; 215 for (i = 0; i < data.length; i++) 216 { 217 assert(b[i] == data[4 - i]); 218 } 219 } 220 221 222 /********************************************** 223 * Support for array.sort property for BitArray. 224 */ 225 226 BitArray sort() 227 out (result) 228 { 229 assert(result == this); 230 } 231 do 232 { 233 if (len >= 2) 234 { 235 size_t lo, hi; 236 237 lo = 0; 238 hi = len - 1; 239 while (1) 240 { 241 while (1) 242 { 243 if (lo >= hi) 244 goto Ldone; 245 if ((this)[lo] == true) 246 break; 247 lo++; 248 } 249 250 while (1) 251 { 252 if (lo >= hi) 253 goto Ldone; 254 if ((this)[hi] == false) 255 break; 256 hi--; 257 } 258 259 (this)[lo] = false; 260 (this)[hi] = true; 261 262 lo++; 263 hi--; 264 } 265 Ldone: 266 ; 267 } 268 return this; 269 } 270 271 unittest 272 { 273 debug(bitarray) printf("BitArray.sort.unittest\n"); 274 275 __gshared size_t x = 0b1100011000; 276 __gshared BitArray ba = { 10, &x }; 277 ba.sort; 278 for (size_t i = 0; i < 6; i++) 279 assert(ba[i] == false); 280 for (size_t i = 6; i < 10; i++) 281 assert(ba[i] == true); 282 } 283 284 285 /*************************************** 286 * Support for operators == and != for bit arrays. 287 */ 288 289 bool opEquals(const ref BitArray a2) const pure nothrow 290 { size_t i; 291 292 if (this.length != a2.length) 293 return false; // not equal 294 byte *p1 = cast(byte*)this.ptr; 295 byte *p2 = cast(byte*)a2.ptr; 296 auto n = this.length / 8; 297 for (i = 0; i < n; i++) 298 { 299 if (p1[i] != p2[i]) 300 return false; // not equal 301 } 302 303 n = this.length & 7; 304 auto mask = cast(ubyte)((1 << n) - 1); 305 //printf("i = %d, n = %d, mask = %x, %x, %x\n", i, n, mask, p1[i], p2[i]); 306 return (mask == 0) || (p1[i] & mask) == (p2[i] & mask); 307 } 308 309 unittest 310 { 311 debug(bitarray) printf("BitArray.opEquals unittest\n"); 312 313 static bool[] ba = [1,0,1,0,1]; 314 static bool[] bb = [1,0,1]; 315 static bool[] bc = [1,0,1,0,1,0,1]; 316 static bool[] bd = [1,0,1,1,1]; 317 static bool[] be = [1,0,1,0,1]; 318 319 BitArray a; a.init(ba); 320 BitArray b; b.init(bb); 321 BitArray c; c.init(bc); 322 BitArray d; d.init(bd); 323 BitArray e; e.init(be); 324 325 assert(a != b); 326 assert(a != c); 327 assert(a != d); 328 assert(a == e); 329 } 330 331 /*************************************** 332 * Implement comparison operators. 333 */ 334 335 int opCmp(const ref BitArray a2) const pure nothrow 336 { 337 size_t i; 338 339 auto len = this.length; 340 if (a2.length < len) 341 len = a2.length; 342 auto p1 = cast(ubyte*)this.ptr; 343 auto p2 = cast(ubyte*)a2.ptr; 344 auto n = len / 8; 345 for (i = 0; i < n; i++) 346 { 347 if (p1[i] != p2[i]) 348 break; // not equal 349 } 350 for (auto j = i * 8; j < len; j++) 351 { auto mask = cast(ubyte)(1 << j); 352 353 auto c = cast(int)(p1[i] & mask) - cast(int)(p2[i] & mask); 354 if (c) 355 return c; 356 } 357 version (D_LP64) 358 { 359 long c = this.len - a2.length; 360 if (c < 0) 361 return -1; 362 else 363 return c != 0; 364 } 365 else 366 return cast(int)this.len - cast(int)a2.length; 367 } 368 369 unittest 370 { 371 debug(bitarray) printf("BitArray.opCmp unittest\n"); 372 373 static bool[] ba = [1,0,1,0,1]; 374 static bool[] bb = [1,0,1]; 375 static bool[] bc = [1,0,1,0,1,0,1]; 376 static bool[] bd = [1,0,1,1,1]; 377 static bool[] be = [1,0,1,0,1]; 378 379 BitArray a; a.init(ba); 380 BitArray b; b.init(bb); 381 BitArray c; c.init(bc); 382 BitArray d; d.init(bd); 383 BitArray e; e.init(be); 384 385 assert(a > b); 386 assert(a >= b); 387 assert(a < c); 388 assert(a <= c); 389 assert(a < d); 390 assert(a <= d); 391 assert(a == e); 392 assert(a <= e); 393 assert(a >= e); 394 } 395 396 /*************************************** 397 * Set BitArray to contents of ba[] 398 */ 399 400 void init(bool[] ba) 401 { 402 length = ba.length; 403 foreach (i, b; ba) 404 { 405 (this)[i] = b; 406 } 407 } 408 409 410 /*************************************** 411 * Map BitArray onto v[], with numbits being the number of bits 412 * in the array. Does not copy the data. 413 * 414 * This is the inverse of opCast. 415 */ 416 void init(void[] v, size_t numbits) 417 in 418 { 419 assert(numbits <= v.length * 8); 420 assert((v.length & 3) == 0); 421 } 422 do 423 { 424 ptr = cast(typeof(ptr))v.ptr; 425 len = numbits; 426 } 427 428 unittest 429 { 430 debug(bitarray) printf("BitArray.init unittest\n"); 431 432 static bool[] ba = [1,0,1,0,1]; 433 434 BitArray a; a.init(ba); 435 BitArray b; 436 void[] v; 437 438 v = cast(void[])a; 439 b.init(v, a.length); 440 441 assert(b[0] == 1); 442 assert(b[1] == 0); 443 assert(b[2] == 1); 444 assert(b[3] == 0); 445 assert(b[4] == 1); 446 447 a[0] = 0; 448 assert(b[0] == 0); 449 450 assert(a == b); 451 } 452 453 /*************************************** 454 * Convert to void[]. 455 */ 456 void[] opCast() 457 { 458 return cast(void[])ptr[0 .. dim]; 459 } 460 461 unittest 462 { 463 debug(bitarray) printf("BitArray.opCast unittest\n"); 464 465 static bool[] ba = [1,0,1,0,1]; 466 467 BitArray a; a.init(ba); 468 void[] v = cast(void[])a; 469 470 assert(v.length == a.dim * size_t.sizeof); 471 } 472 473 /*************************************** 474 * Support for unary operator ~ for bit arrays. 475 */ 476 BitArray opUnary(string op : "~")() 477 { 478 auto dim = this.dim(); 479 480 BitArray result; 481 482 result.length = len; 483 for (size_t i = 0; i < dim; i++) 484 result.ptr[i] = ~this.ptr[i]; 485 if (len & 31) 486 result.ptr[dim - 1] &= ~(~0 << (len & 31)); 487 return result; 488 } 489 490 unittest 491 { 492 debug(bitarray) printf("BitArray.opUnary unittest\n"); 493 494 static bool[] ba = [1,0,1,0,1]; 495 496 BitArray a; a.init(ba); 497 BitArray b = ~a; 498 499 assert(b[0] == 0); 500 assert(b[1] == 1); 501 assert(b[2] == 0); 502 assert(b[3] == 1); 503 assert(b[4] == 0); 504 } 505 506 507 /*************************************** 508 * Support for binary operator & for bit arrays. 509 */ 510 BitArray opBinary(string op : "&")(BitArray e2) 511 in 512 { 513 assert(len == e2.length); 514 } 515 do 516 { 517 auto dim = this.dim(); 518 519 BitArray result; 520 521 result.length = len; 522 for (size_t i = 0; i < dim; i++) 523 result.ptr[i] = this.ptr[i] & e2.ptr[i]; 524 return result; 525 } 526 527 unittest 528 { 529 debug(bitarray) printf("BitArray.opBinary unittest\n"); 530 531 static bool[] ba = [1,0,1,0,1]; 532 static bool[] bb = [1,0,1,1,0]; 533 534 BitArray a; a.init(ba); 535 BitArray b; b.init(bb); 536 537 BitArray c = a & b; 538 539 assert(c[0] == 1); 540 assert(c[1] == 0); 541 assert(c[2] == 1); 542 assert(c[3] == 0); 543 assert(c[4] == 0); 544 } 545 546 547 /*************************************** 548 * Support for binary operator | for bit arrays. 549 */ 550 BitArray opBinary(string op : "|")(BitArray e2) 551 in 552 { 553 assert(len == e2.length); 554 } 555 do 556 { 557 auto dim = this.dim(); 558 559 BitArray result; 560 561 result.length = len; 562 for (size_t i = 0; i < dim; i++) 563 result.ptr[i] = this.ptr[i] | e2.ptr[i]; 564 return result; 565 } 566 567 unittest 568 { 569 debug(bitarray) printf("BitArray.opBinary unittest\n"); 570 571 static bool[] ba = [1,0,1,0,1]; 572 static bool[] bb = [1,0,1,1,0]; 573 574 BitArray a; a.init(ba); 575 BitArray b; b.init(bb); 576 577 BitArray c = a | b; 578 579 assert(c[0] == 1); 580 assert(c[1] == 0); 581 assert(c[2] == 1); 582 assert(c[3] == 1); 583 assert(c[4] == 1); 584 } 585 586 587 /*************************************** 588 * Support for binary operator ^ for bit arrays. 589 */ 590 BitArray opBinary(string op : "^")(BitArray e2) 591 in 592 { 593 assert(len == e2.length); 594 } 595 do 596 { 597 auto dim = this.dim(); 598 599 BitArray result; 600 601 result.length = len; 602 for (size_t i = 0; i < dim; i++) 603 result.ptr[i] = this.ptr[i] ^ e2.ptr[i]; 604 return result; 605 } 606 607 unittest 608 { 609 debug(bitarray) printf("BitArray.opBinary unittest\n"); 610 611 static bool[] ba = [1,0,1,0,1]; 612 static bool[] bb = [1,0,1,1,0]; 613 614 BitArray a; a.init(ba); 615 BitArray b; b.init(bb); 616 617 BitArray c = a ^ b; 618 619 assert(c[0] == 0); 620 assert(c[1] == 0); 621 assert(c[2] == 0); 622 assert(c[3] == 1); 623 assert(c[4] == 1); 624 } 625 626 627 /*************************************** 628 * Support for binary operator - for bit arrays. 629 * 630 * $(I a - b) for BitArrays means the same thing as $(I a & ~b). 631 */ 632 BitArray opBinary(string op : "-")(BitArray e2) 633 in 634 { 635 assert(len == e2.length); 636 } 637 do 638 { 639 auto dim = this.dim(); 640 641 BitArray result; 642 643 result.length = len; 644 for (size_t i = 0; i < dim; i++) 645 result.ptr[i] = this.ptr[i] & ~e2.ptr[i]; 646 return result; 647 } 648 649 unittest 650 { 651 debug(bitarray) printf("BitArray.opBinary unittest\n"); 652 653 static bool[] ba = [1,0,1,0,1]; 654 static bool[] bb = [1,0,1,1,0]; 655 656 BitArray a; a.init(ba); 657 BitArray b; b.init(bb); 658 659 BitArray c = a - b; 660 661 assert(c[0] == 0); 662 assert(c[1] == 0); 663 assert(c[2] == 0); 664 assert(c[3] == 0); 665 assert(c[4] == 1); 666 } 667 668 669 /*************************************** 670 * Support for operator &= bit arrays. 671 */ 672 BitArray opOpAssign(string op : "&")(BitArray e2) 673 in 674 { 675 assert(len == e2.length); 676 } 677 do 678 { 679 auto dim = this.dim(); 680 681 for (size_t i = 0; i < dim; i++) 682 ptr[i] &= e2.ptr[i]; 683 return this; 684 } 685 686 unittest 687 { 688 debug(bitarray) printf("BitArray.opOpAssign unittest\n"); 689 690 static bool[] ba = [1,0,1,0,1]; 691 static bool[] bb = [1,0,1,1,0]; 692 693 BitArray a; a.init(ba); 694 BitArray b; b.init(bb); 695 696 a &= b; 697 assert(a[0] == 1); 698 assert(a[1] == 0); 699 assert(a[2] == 1); 700 assert(a[3] == 0); 701 assert(a[4] == 0); 702 } 703 704 705 /*************************************** 706 * Support for operator |= for bit arrays. 707 */ 708 BitArray opOpAssign(string op : "|")(BitArray e2) 709 in 710 { 711 assert(len == e2.length); 712 } 713 do 714 { 715 auto dim = this.dim(); 716 717 for (size_t i = 0; i < dim; i++) 718 ptr[i] |= e2.ptr[i]; 719 return this; 720 } 721 722 unittest 723 { 724 debug(bitarray) printf("BitArray.opOpAssign unittest\n"); 725 726 static bool[] ba = [1,0,1,0,1]; 727 static bool[] bb = [1,0,1,1,0]; 728 729 BitArray a; a.init(ba); 730 BitArray b; b.init(bb); 731 732 a |= b; 733 assert(a[0] == 1); 734 assert(a[1] == 0); 735 assert(a[2] == 1); 736 assert(a[3] == 1); 737 assert(a[4] == 1); 738 } 739 740 /*************************************** 741 * Support for operator ^= for bit arrays. 742 */ 743 BitArray opOpAssign(string op : "^")(BitArray e2) 744 in 745 { 746 assert(len == e2.length); 747 } 748 do 749 { 750 auto dim = this.dim(); 751 752 for (size_t i = 0; i < dim; i++) 753 ptr[i] ^= e2.ptr[i]; 754 return this; 755 } 756 757 unittest 758 { 759 debug(bitarray) printf("BitArray.opOpAssign unittest\n"); 760 761 static bool[] ba = [1,0,1,0,1]; 762 static bool[] bb = [1,0,1,1,0]; 763 764 BitArray a; a.init(ba); 765 BitArray b; b.init(bb); 766 767 a ^= b; 768 assert(a[0] == 0); 769 assert(a[1] == 0); 770 assert(a[2] == 0); 771 assert(a[3] == 1); 772 assert(a[4] == 1); 773 } 774 775 /*************************************** 776 * Support for operator -= for bit arrays. 777 * 778 * $(I a -= b) for BitArrays means the same thing as $(I a &= ~b). 779 */ 780 BitArray opOpAssign(string op : "-")(BitArray e2) 781 in 782 { 783 assert(len == e2.length); 784 } 785 do 786 { 787 auto dim = this.dim(); 788 789 for (size_t i = 0; i < dim; i++) 790 ptr[i] &= ~e2.ptr[i]; 791 return this; 792 } 793 794 unittest 795 { 796 debug(bitarray) printf("BitArray.opOpAssign unittest\n"); 797 798 static bool[] ba = [1,0,1,0,1]; 799 static bool[] bb = [1,0,1,1,0]; 800 801 BitArray a; a.init(ba); 802 BitArray b; b.init(bb); 803 804 a -= b; 805 assert(a[0] == 0); 806 assert(a[1] == 0); 807 assert(a[2] == 0); 808 assert(a[3] == 0); 809 assert(a[4] == 1); 810 } 811 812 /*************************************** 813 * Support for operator ~= for bit arrays. 814 */ 815 816 BitArray opOpAssign(string op : "~")(bool b) 817 { 818 length = len + 1; 819 (this)[len - 1] = b; 820 return this; 821 } 822 823 unittest 824 { 825 debug(bitarray) printf("BitArray.opOpAssign unittest\n"); 826 827 static bool[] ba = [1,0,1,0,1]; 828 829 BitArray a; a.init(ba); 830 BitArray b; 831 832 b = (a ~= true); 833 assert(a[0] == 1); 834 assert(a[1] == 0); 835 assert(a[2] == 1); 836 assert(a[3] == 0); 837 assert(a[4] == 1); 838 assert(a[5] == 1); 839 840 assert(b == a); 841 } 842 843 /*************************************** 844 * ditto 845 */ 846 847 BitArray opOpAssign(string op : "~")(BitArray b) 848 { 849 auto istart = len; 850 length = len + b.length; 851 for (auto i = istart; i < len; i++) 852 (this)[i] = b[i - istart]; 853 return this; 854 } 855 856 unittest 857 { 858 debug(bitarray) printf("BitArray.opOpAssign unittest\n"); 859 860 static bool[] ba = [1,0]; 861 static bool[] bb = [0,1,0]; 862 863 BitArray a; a.init(ba); 864 BitArray b; b.init(bb); 865 BitArray c; 866 867 c = (a ~= b); 868 assert(a.length == 5); 869 assert(a[0] == 1); 870 assert(a[1] == 0); 871 assert(a[2] == 0); 872 assert(a[3] == 1); 873 assert(a[4] == 0); 874 875 assert(c == a); 876 } 877 878 /*************************************** 879 * Support for binary operator ~ for bit arrays. 880 */ 881 BitArray opBinary(string op : "~")(bool b) 882 { 883 auto r = this.dup; 884 r.length = len + 1; 885 r[len] = b; 886 return r; 887 } 888 889 /** ditto */ 890 BitArray opBinaryRight(string op : "~")(bool b) 891 { 892 BitArray r; 893 894 r.length = len + 1; 895 r[0] = b; 896 for (size_t i = 0; i < len; i++) 897 r[1 + i] = (this)[i]; 898 return r; 899 } 900 901 /** ditto */ 902 BitArray opBinary(string op : "~")(BitArray b) 903 { 904 BitArray r; 905 906 r = this.dup(); 907 r ~= b; 908 return r; 909 } 910 911 unittest 912 { 913 debug(bitarray) printf("BitArray.opBinary unittest\n"); 914 915 static bool[] ba = [1,0]; 916 static bool[] bb = [0,1,0]; 917 918 BitArray a; a.init(ba); 919 BitArray b; b.init(bb); 920 BitArray c; 921 922 c = (a ~ b); 923 assert(c.length == 5); 924 assert(c[0] == 1); 925 assert(c[1] == 0); 926 assert(c[2] == 0); 927 assert(c[3] == 1); 928 assert(c[4] == 0); 929 930 c = (a ~ true); 931 assert(c.length == 3); 932 assert(c[0] == 1); 933 assert(c[1] == 0); 934 assert(c[2] == 1); 935 936 c = (false ~ a); 937 assert(c.length == 3); 938 assert(c[0] == 0); 939 assert(c[1] == 1); 940 assert(c[2] == 0); 941 } 942 }