1 /** 2 * This module contains a packed bit array implementation in the style of D's 3 * built-in dynamic arrays. 4 * 5 * Copyright: 6 * Copyright (C) 2005-2006 Digital Mars, www.digitalmars.com. 7 * Some parts copyright (c) 2009-2016 dunnhumby Germany GmbH. 8 * All rights reserved. 9 * 10 * License: 11 * Tango Dual License: 3-Clause BSD License / Academic Free License v3.0. 12 * See LICENSE_TANGO.txt for details. 13 * 14 * Authors: Walter Bright, Sean Kelly 15 * 16 */ 17 module ocean.core.BitArray; 18 19 import ocean.core.BitManip; 20 import ocean.core.Verify; 21 22 version (unittest) import ocean.core.Test; 23 24 /** 25 * This struct represents an array of boolean values, each of which occupy one 26 * bit of memory for storage. Thus an array of 32 bits would occupy the same 27 * space as one integer value. The typical array operations--such as indexing 28 * and sorting--are supported, as well as bitwise operations such as and, or, 29 * xor, and complement. 30 */ 31 struct BitArray 32 { 33 size_t len; 34 uint* ptr; 35 36 37 /** 38 * This initializes a BitArray of bits.length bits, where each bit value 39 * matches the corresponding boolean value in bits. 40 * 41 * Params: 42 * bits = The initialization value. 43 * 44 * Returns: 45 * A BitArray with the same number and sequence of elements as bits. 46 */ 47 static BitArray opCall( bool[] bits ) 48 { 49 BitArray temp; 50 51 temp.length = bits.length; 52 foreach( pos, val; bits ) 53 temp[pos] = val; 54 return temp; 55 } 56 57 /** 58 * Get the number of bits in this array. 59 * 60 * Returns: 61 * The number of bits in this array. 62 */ 63 size_t length() 64 { 65 return len; 66 } 67 68 69 /** 70 * Resizes this array to newlen bits. If newlen is larger than the current 71 * length, the new bits will be initialized to zero. 72 * 73 * Params: 74 * newlen = The number of bits this array should contain. 75 */ 76 void length( size_t newlen ) 77 { 78 if( newlen != len ) 79 { 80 auto olddim = dim(); 81 auto newdim = (newlen + 31) / 32; 82 83 if( newdim != olddim ) 84 { 85 // Create a fake array so we can use D's realloc machinery 86 uint[] buf = ptr[0 .. olddim]; 87 88 buf.length = newdim; // realloc 89 assumeSafeAppend(buf); 90 91 ptr = buf.ptr; 92 } 93 94 if( auto pad_bits = (newlen & 31) ) 95 { 96 // Set any pad bits to 0 97 ptr[newdim - 1] &= ~(~0 << pad_bits); 98 } 99 100 len = newlen; 101 } 102 } 103 104 105 /** 106 * Gets the length of a uint array large enough to hold all stored bits. 107 * 108 * Returns: 109 * The size a uint array would have to be to store this array. 110 */ 111 size_t dim() 112 { 113 return (len + 31) / 32; 114 } 115 116 117 /** 118 * Duplicates this array, much like the dup property for built-in arrays. 119 * 120 * Returns: 121 * A duplicate of this array. 122 */ 123 BitArray dup() 124 { 125 BitArray ba; 126 127 uint[] buf = ptr[0 .. dim].dup; 128 ba.len = len; 129 ba.ptr = buf.ptr; 130 return ba; 131 } 132 133 134 unittest 135 { 136 BitArray a; 137 BitArray b; 138 139 a.length = 3; 140 a[0] = 1; a[1] = 0; a[2] = 1; 141 b = a.dup; 142 test( b.length == 3 ); 143 for( int i = 0; i < 3; ++i ) 144 { 145 test( b[i] == (((i ^ 1) & 1) ? true : false) ); 146 } 147 } 148 149 /** 150 * Resets the length of this array to bits.length and then initializes this 151 * 152 * Resizes this array to hold bits.length bits and initializes each bit 153 * value to match the corresponding boolean value in bits. 154 * 155 * Params: 156 * bits = The initialization value. 157 */ 158 void opAssign( bool[] bits ) 159 { 160 length = bits.length; 161 foreach( i, b; bits ) 162 { 163 this[i] = b; 164 } 165 } 166 167 /** 168 * Copy the bits from one array into this array. This is not a shallow 169 * copy. 170 * 171 * Params: 172 * rhs = A BitArray with the same number of bits as this bit array. 173 * 174 * Returns: 175 * A shallow copy of this array. 176 * 177 * -------------------- 178 * BitArray ba = [0,1,0,1,0]; 179 * BitArray ba2; 180 * ba2.length = ba.length; 181 * ba2[] = ba; // perform the copy 182 * ba[0] = true; 183 * assert(ba2[0] == false); 184 * ------------------- 185 */ 186 BitArray opSliceAssign(BitArray rhs) 187 { 188 verify(rhs.len == len); 189 190 auto dimension = this.dim(); 191 this.ptr[0..dimension] = rhs.ptr[0..dimension]; 192 return this; 193 } 194 195 /** 196 * Map BitArray onto target, with numbits being the number of bits in the 197 * array. Does not copy the data. This is the inverse of opCast. 198 * 199 * Params: 200 * target = The array to map. 201 * numbits = The number of bits to map in target. 202 */ 203 void initialize( void[] target, size_t numbits ) 204 { 205 verify(numbits <= target.length * 8); 206 verify((target.length & 3) == 0); 207 208 ptr = cast(uint*)target.ptr; 209 len = numbits; 210 } 211 212 213 unittest 214 { 215 BitArray a = [1,0,1,0,1]; 216 BitArray b; 217 void[] buf; 218 219 buf = cast(void[])a; 220 b.initialize( buf, a.length ); 221 222 test( b[0] == 1 ); 223 test( b[1] == 0 ); 224 test( b[2] == 1 ); 225 test( b[3] == 0 ); 226 test( b[4] == 1 ); 227 228 a[0] = 0; 229 test( b[0] == 0 ); 230 231 test( a == b ); 232 233 // test opSliceAssign 234 BitArray c; 235 c.length = a.length; 236 c[] = a; 237 test( c == a ); 238 a[0] = 1; 239 test( c != a ); 240 } 241 242 /** 243 * Reverses the contents of this array in place, much like the reverse 244 * property for built-in arrays. 245 * 246 * Returns: 247 * A shallow copy of this array. 248 */ 249 BitArray reverse() 250 out( result ) 251 { 252 assert(compare(result, this)); 253 } 254 do 255 { 256 if( len >= 2 ) 257 { 258 bool t; 259 size_t lo, hi; 260 261 lo = 0; 262 hi = len - 1; 263 for( ; lo < hi; ++lo, --hi ) 264 { 265 t = this[lo]; 266 this[lo] = (this)[hi]; 267 this[hi] = t; 268 } 269 } 270 return this; 271 } 272 273 274 unittest 275 { 276 static bool[5] data = [1,0,1,1,0]; 277 BitArray b = data; 278 b.reverse; 279 280 for( size_t i = 0; i < data.length; ++i ) 281 { 282 test( b[i] == data[4 - i] ); 283 } 284 } 285 286 /** 287 * Sorts this array in place, with zero entries sorting before one. This 288 * is equivalent to the sort property for built-in arrays. 289 * 290 * Returns: 291 * A shallow copy of this array. 292 */ 293 BitArray sort() 294 out( result ) 295 { 296 assert(compare(result, this)); 297 } 298 do 299 { 300 if( len >= 2 ) 301 { 302 size_t lo, hi; 303 304 lo = 0; 305 hi = len - 1; 306 while( true ) 307 { 308 while( true ) 309 { 310 if( lo >= hi ) 311 goto Ldone; 312 if( this[lo] == true ) 313 break; 314 ++lo; 315 } 316 317 while( true ) 318 { 319 if( lo >= hi ) 320 goto Ldone; 321 if( this[hi] == false ) 322 break; 323 --hi; 324 } 325 326 this[lo] = false; 327 this[hi] = true; 328 329 ++lo; 330 --hi; 331 } 332 Ldone: 333 ; 334 } 335 return this; 336 } 337 338 339 unittest 340 { 341 uint x = 0b1100011000; 342 BitArray ba = { 10, &x }; 343 344 ba.sort; 345 for( size_t i = 0; i < 6; ++i ) 346 test( ba[i] == false ); 347 for( size_t i = 6; i < 10; ++i ) 348 test( ba[i] == true ); 349 } 350 351 /** 352 * Operates on all bits in this array. 353 * 354 * Params: 355 * dg = The supplied code as a delegate. 356 */ 357 int opApply( scope int delegate(ref bool) dg ) 358 { 359 int result; 360 361 for( size_t i = 0; i < len; ++i ) 362 { 363 bool b = opIndex( i ); 364 result = dg( b ); 365 opIndexAssign( b, i ); 366 if( result ) 367 break; 368 } 369 return result; 370 } 371 372 373 /** ditto */ 374 int opApply( scope int delegate(ref size_t, ref bool) dg ) 375 { 376 int result; 377 378 for( size_t i = 0; i < len; ++i ) 379 { 380 bool b = opIndex( i ); 381 result = dg( i, b ); 382 opIndexAssign( b, i ); 383 if( result ) 384 break; 385 } 386 return result; 387 } 388 389 390 unittest 391 { 392 BitArray a = [1,0,1]; 393 394 int i; 395 foreach( b; a ) 396 { 397 switch( i ) 398 { 399 case 0: test( b == true ); break; 400 case 1: test( b == false ); break; 401 case 2: test( b == true ); break; 402 default: test( false ); 403 } 404 i++; 405 } 406 407 foreach( j, b; a ) 408 { 409 switch( j ) 410 { 411 case 0: test( b == true ); break; 412 case 1: test( b == false ); break; 413 case 2: test( b == true ); break; 414 default: test( false ); 415 } 416 } 417 } 418 419 /** 420 * Compares this array to another for equality. Two bit arrays are equal 421 * if they are the same size and contain the same series of bits. 422 * 423 * Params: 424 * rhs = The array to compare against. 425 * 426 * Returns: 427 * Zero if not equal and non-zero otherwise. 428 */ 429 int opEquals( BitArray rhs ) 430 { 431 return compare(this, rhs); 432 } 433 434 // FIXME_IN_D2: allows comparing both mutable 435 // and immutable BitArray without actually defining 436 // bunch of const methods 437 438 static private int compare(in BitArray lhs_, 439 in BitArray rhs_ ) 440 { 441 // requirement for const methods propagates 442 // transitively, avoid it by casting const away 443 auto lhs = cast(BitArray*) &lhs_; 444 auto rhs = cast(BitArray*) &rhs_; 445 446 if( lhs.length != rhs.length ) 447 return 0; // not equal 448 auto p1 = lhs.ptr; 449 auto p2 = rhs.ptr; 450 size_t n = lhs.length / 32; 451 size_t i; 452 for( i = 0; i < n; ++i ) 453 { 454 if( p1[i] != p2[i] ) 455 return 0; // not equal 456 } 457 int rest = cast(int)(lhs.length & cast(size_t)31u); 458 uint mask = ~((~0u)<<rest); 459 return (rest == 0) || (p1[i] & mask) == (p2[i] & mask); 460 } 461 462 unittest 463 { 464 BitArray a = [1,0,1,0,1]; 465 BitArray b = [1,0,1]; 466 BitArray c = [1,0,1,0,1,0,1]; 467 BitArray d = [1,0,1,1,1]; 468 BitArray e = [1,0,1,0,1]; 469 470 test(a != b); 471 test(a != c); 472 test(a != d); 473 test(a == e); 474 } 475 476 /** 477 * Performs a lexicographical comparison of this array to the supplied 478 * array. 479 * 480 * Params: 481 * rhs = The array to compare against. 482 * 483 * Returns: 484 * A value less than zero if this array sorts before the supplied array, 485 * zero if the arrays are equavalent, and a value greater than zero if 486 * this array sorts after the supplied array. 487 */ 488 int opCmp( BitArray rhs ) 489 { 490 auto len = this.length; 491 if( rhs.length < len ) 492 len = rhs.length; 493 uint* p1 = this.ptr; 494 uint* p2 = rhs.ptr; 495 size_t n = len / 32; 496 size_t i; 497 for( i = 0; i < n; ++i ) 498 { 499 if( p1[i] != p2[i] ){ 500 return ((p1[i] < p2[i])?-1:1); 501 } 502 } 503 int rest=cast(int)(len & cast(size_t) 31u); 504 if (rest>0) { 505 uint mask=~((~0u)<<rest); 506 uint v1=p1[i] & mask; 507 uint v2=p2[i] & mask; 508 if (v1 != v2) return ((v1<v2)?-1:1); 509 } 510 return ((this.length<rhs.length)?-1:((this.length==rhs.length)?0:1)); 511 } 512 513 unittest 514 { 515 BitArray a = [1,0,1,0,1]; 516 BitArray b = [1,0,1]; 517 BitArray c = [1,0,1,0,1,0,1]; 518 BitArray d = [1,0,1,1,1]; 519 BitArray e = [1,0,1,0,1]; 520 BitArray f = [1,0,1,0]; 521 522 test( a > b ); 523 test( a >= b ); 524 test( a < c ); 525 test( a <= c ); 526 test( a < d ); 527 test( a <= d ); 528 test( a == e ); 529 test( a <= e ); 530 test( a >= e ); 531 test( f > b ); 532 } 533 534 /** 535 * Convert this array to a void array. 536 * 537 * Returns: 538 * This array represented as a void array. 539 */ 540 void[] opCast() 541 { 542 return cast(void[])ptr[0 .. dim]; 543 } 544 545 546 unittest 547 { 548 BitArray a = [1,0,1,0,1]; 549 void[] v = cast(void[])a; 550 551 test( v.length == a.dim * uint.sizeof ); 552 } 553 554 /** 555 * Support for index operations, much like the behavior of built-in arrays. 556 * 557 * Params: 558 * pos = The desired index position. 559 * 560 * In: 561 * pos must be less than the length of this array. 562 * 563 * Returns: 564 * The value of the bit at pos. 565 */ 566 bool opIndex( size_t pos ) 567 { 568 verify(pos < len); 569 return cast(bool)bt( cast(size_t*)ptr, pos ); 570 } 571 572 573 /** 574 * Generates a copy of this array with the unary complement operation 575 * applied. 576 * 577 * Params: 578 * op = operation to perform 579 * 580 * Returns: 581 * A new array which is the complement of this array. 582 */ 583 BitArray opUnary ( string op : "~" )( ) 584 { 585 auto dim = this.dim(); 586 587 BitArray result; 588 589 result.length = len; 590 for( size_t i = 0; i < dim; ++i ) 591 result.ptr[i] = ~this.ptr[i]; 592 if( len & 31 ) 593 result.ptr[dim - 1] &= ~(~0 << (len & 31)); 594 return result; 595 } 596 597 598 unittest 599 { 600 BitArray a = [1,0,1,0,1]; 601 BitArray b = ~a; 602 603 test(b[0] == 0); 604 test(b[1] == 1); 605 test(b[2] == 0); 606 test(b[3] == 1); 607 test(b[4] == 0); 608 } 609 610 /** 611 * Generates a new array which is the result of bitwise operation `op` 612 * between this array and the supplied array. 613 * 614 * Supported are bitwise binary operation "&", "|", "^". 615 * 616 * Params: 617 * op = operation to perform 618 * rhs = The array with which to perform the bitwise operation. 619 * 620 * In: 621 * rhs.length must equal the length of this array. 622 * 623 * Returns: 624 * A new array which is the result of a bitwise operation between 625 * this array and the supplied array. 626 */ 627 BitArray opBinary ( string op )( BitArray rhs ) 628 if (op == "&" || op == "|" || op == "^") 629 { 630 verify(len == rhs.length); 631 632 auto dim = this.dim(); 633 634 BitArray result; 635 636 result.length = len; 637 for( size_t i = 0; i < dim; ++i ) 638 result.ptr[i] = mixin(`this.ptr[i]` ~ op ~ `rhs.ptr[i]`); 639 return result; 640 } 641 642 unittest 643 { 644 BitArray a = [1,0,1,0,1]; 645 BitArray b = [1,0,1,1,0]; 646 647 BitArray c = a & b; 648 649 test(c[0] == 1); 650 test(c[1] == 0); 651 test(c[2] == 1); 652 test(c[3] == 0); 653 test(c[4] == 0); 654 } 655 656 unittest 657 { 658 BitArray a = [1,0,1,0,1]; 659 BitArray b = [1,0,1,1,0]; 660 661 BitArray c = a | b; 662 663 test(c[0] == 1); 664 test(c[1] == 0); 665 test(c[2] == 1); 666 test(c[3] == 1); 667 test(c[4] == 1); 668 } 669 670 unittest 671 { 672 BitArray a = [1,0,1,0,1]; 673 BitArray b = [1,0,1,1,0]; 674 675 BitArray c = a ^ b; 676 677 test(c[0] == 0); 678 test(c[1] == 0); 679 test(c[2] == 0); 680 test(c[3] == 1); 681 test(c[4] == 1); 682 } 683 684 /** 685 * Generates a new array which is the result of this array minus the 686 * supplied array. 687 * 688 *$(I a - b) for BitArrays means the same thing as $(I a & ~b). 689 * 690 * Params: 691 * op = operation to perform 692 * rhs = The array with which to perform the subtraction operation. 693 * 694 * In: 695 * rhs.length must equal the length of this array. 696 * 697 * Returns: 698 * A new array which is the result of this array minus the supplied array. 699 */ 700 BitArray opBinary ( string op : "-" )( BitArray rhs ) 701 { 702 verify(len == rhs.length); 703 704 auto dim = this.dim(); 705 706 BitArray result; 707 708 result.length = len; 709 for( size_t i = 0; i < dim; ++i ) 710 result.ptr[i] = this.ptr[i] & ~rhs.ptr[i]; 711 return result; 712 } 713 714 unittest 715 { 716 BitArray a = [1,0,1,0,1]; 717 BitArray b = [1,0,1,1,0]; 718 719 BitArray c = a - b; 720 721 test( c[0] == 0 ); 722 test( c[1] == 0 ); 723 test( c[2] == 0 ); 724 test( c[3] == 0 ); 725 test( c[4] == 1 ); 726 } 727 728 /** 729 * Generates a new array which is the result of this array concatenated 730 * with the supplied array. 731 * 732 * Params: 733 * op = operation to perform 734 * rhs = The array with which to perform the concatenation operation. 735 * 736 * Returns: 737 * A new array which is the result of this array concatenated with the 738 * supplied array. 739 */ 740 BitArray opBinary ( string op : "~" )( bool rhs ) 741 { 742 BitArray result; 743 744 result = this.dup; 745 result.length = len + 1; 746 result[len] = rhs; 747 return result; 748 } 749 750 751 /** ditto */ 752 BitArray opBinaryRight ( string op : "~" )( bool lhs ) 753 { 754 BitArray result; 755 756 result.length = len + 1; 757 result[0] = lhs; 758 for( size_t i = 0; i < len; ++i ) 759 result[1 + i] = this[i]; 760 return result; 761 } 762 763 764 /** ditto */ 765 BitArray opBinary ( string op : "~" )( BitArray rhs ) 766 { 767 BitArray result; 768 769 result = this.dup(); 770 result ~= rhs; 771 return result; 772 } 773 774 unittest 775 { 776 BitArray a = [1,0]; 777 BitArray b = [0,1,0]; 778 BitArray c; 779 780 c = (a ~ b); 781 test( c.length == 5 ); 782 test( c[0] == 1 ); 783 test( c[1] == 0 ); 784 test( c[2] == 0 ); 785 test( c[3] == 1 ); 786 test( c[4] == 0 ); 787 788 c = (a ~ true); 789 test( c.length == 3 ); 790 test( c[0] == 1 ); 791 test( c[1] == 0 ); 792 test( c[2] == 1 ); 793 794 c = (false ~ a); 795 test( c.length == 3 ); 796 test( c[0] == 0 ); 797 test( c[1] == 1 ); 798 test( c[2] == 0 ); 799 } 800 801 /** 802 * Support for index operations, much like the behavior of built-in arrays. 803 * 804 * Params: 805 * b = The new bit value to set. 806 * pos = The desired index position. 807 * 808 * In: 809 * pos must be less than the length of this array. 810 * 811 * Returns: 812 * The new value of the bit at pos. 813 */ 814 bool opIndexAssign( bool b, size_t pos ) 815 { 816 verify(pos < len); 817 818 if( b ) 819 bts( cast(size_t*)ptr, pos ); 820 else 821 btr( cast(size_t*)ptr, pos ); 822 return b; 823 } 824 825 826 /** 827 * Updates the contents of this array with the result of a bitwise `op` 828 * operation between this array and the supplied array. 829 * 830 * Supported are bitwise assignment "&", "|", "^" 831 * 832 * Params: 833 * op = operation to perform 834 * rhs = The array with which to perform the bitwise `op`d operation. 835 * 836 * In: 837 * rhs.length must equal the length of this array. 838 * 839 * Returns: 840 * A shallow copy of this array. 841 */ 842 BitArray opOpAssign ( string op )( BitArray rhs ) 843 if (op == "&" || op == "|" || op == "^") 844 { 845 verify(len == rhs.length); 846 847 auto dim = this.dim(); 848 849 for( size_t i = 0; i < dim; ++i ) 850 mixin(`ptr[i]` ~ op ~ `= rhs.ptr[i];`); 851 return this; 852 } 853 854 unittest 855 { 856 BitArray a = [1,0,1,0,1]; 857 BitArray b = [1,0,1,1,0]; 858 859 a &= b; 860 test( a[0] == 1 ); 861 test( a[1] == 0 ); 862 test( a[2] == 1 ); 863 test( a[3] == 0 ); 864 test( a[4] == 0 ); 865 } 866 867 unittest 868 { 869 BitArray a = [1,0,1,0,1]; 870 BitArray b = [1,0,1,1,0]; 871 872 a |= b; 873 test( a[0] == 1 ); 874 test( a[1] == 0 ); 875 test( a[2] == 1 ); 876 test( a[3] == 1 ); 877 test( a[4] == 1 ); 878 } 879 880 unittest 881 { 882 BitArray a = [1,0,1,0,1]; 883 BitArray b = [1,0,1,1,0]; 884 885 a ^= b; 886 test( a[0] == 0 ); 887 test( a[1] == 0 ); 888 test( a[2] == 0 ); 889 test( a[3] == 1 ); 890 test( a[4] == 1 ); 891 } 892 893 /** 894 * Updates the contents of this array with the result of this array minus 895 * the supplied array. 896 * 897 * $(I a - b) for BitArrays means the same thing as $(I a & ~b). 898 * 899 * Params: 900 * op = operation to perform 901 * rhs = The array with which to perform the subtraction operation. 902 * 903 * In: 904 * rhs.length must equal the length of this array. 905 * 906 * Returns: 907 * A shallow copy of this array. 908 */ 909 BitArray opOpAssign ( string op )( BitArray rhs ) if (op == "-") 910 { 911 verify(len == rhs.length); 912 913 auto dim = this.dim(); 914 915 for( size_t i = 0; i < dim; ++i ) 916 ptr[i] &= ~rhs.ptr[i]; 917 return this; 918 } 919 920 unittest 921 { 922 BitArray a = [1,0,1,0,1]; 923 BitArray b = [1,0,1,1,0]; 924 925 a -= b; 926 test( a[0] == 0 ); 927 test( a[1] == 0 ); 928 test( a[2] == 0 ); 929 test( a[3] == 0 ); 930 test( a[4] == 1 ); 931 } 932 933 /** 934 * Updates the contents of this array with the result of this array 935 * concatenated with the supplied array. 936 * 937 * Params: 938 * op = operation to perform 939 * rhs = The array with which to perform the concatenation operation. 940 * 941 * Returns: 942 * A shallow copy of this array. 943 */ 944 BitArray opOpAssign ( string op : "~" )( bool b ) 945 { 946 length = len + 1; 947 this[len - 1] = b; 948 return this; 949 } 950 951 unittest 952 { 953 BitArray a = [1,0,1,0,1]; 954 BitArray b; 955 956 b = (a ~= true); 957 test( a[0] == 1 ); 958 test( a[1] == 0 ); 959 test( a[2] == 1 ); 960 test( a[3] == 0 ); 961 test( a[4] == 1 ); 962 test( a[5] == 1 ); 963 964 test( b == a ); 965 } 966 967 /** ditto */ 968 BitArray opOpAssign ( string op : "~" )( BitArray rhs ) 969 { 970 auto istart = len; 971 length = len + rhs.length; 972 for( auto i = istart; i < len; ++i ) 973 this[i] = rhs[i - istart]; 974 return this; 975 } 976 977 unittest 978 { 979 BitArray a = [1,0]; 980 BitArray b = [0,1,0]; 981 BitArray c; 982 983 c = (a ~= b); 984 test( a.length == 5 ); 985 test( a[0] == 1 ); 986 test( a[1] == 0 ); 987 test( a[2] == 0 ); 988 test( a[3] == 1 ); 989 test( a[4] == 0 ); 990 991 test( c == a ); 992 } 993 } 994 995 version (unittest) 996 { 997 import ocean.core.Test : NamedTest; 998 } 999 1000 unittest 1001 { 1002 auto t = new NamedTest("Test increase and decrease length of the BitArray"); 1003 1004 static immutable size_of_uint = uint.sizeof * 8; 1005 static immutable num_bits = (size_of_uint * 5) + 15; 1006 1007 // Creates a BitArray and sets all the bits. 1008 scope bool_array = new bool[num_bits]; 1009 bool_array[] = true; 1010 1011 BitArray bit_array; 1012 bit_array = bool_array; 1013 1014 // Self-verification of the BitArray. 1015 test(bit_array.length == bool_array.length); 1016 foreach (bit; bit_array) 1017 t.test!("==")(bit, true); 1018 1019 // Increases the length of the BitArray and checks the former bits remain 1020 // set and the new ones are not. 1021 static immutable greater_length = size_of_uint * 7; 1022 static assert(greater_length > num_bits); 1023 bit_array.length = greater_length; 1024 foreach (pos, bit; bit_array) 1025 { 1026 if (pos < num_bits) 1027 t.test!("==")(bit, true); 1028 else 1029 t.test!("==")(bit, false); 1030 } 1031 1032 // Decreases the length of the BitArray to a shorter length than the 1033 // initial one and checks all bits remain set. 1034 static immutable lower_length = size_of_uint * 5; 1035 static assert(lower_length < num_bits); 1036 bit_array.length = lower_length; 1037 foreach (bit; bit_array) 1038 t.test!("==")(bit, true); 1039 1040 // Resizes back to the initial length of the BitArray to check the bits 1041 // reassigned after decreasing the length of the BitArray are not set. 1042 bit_array.length = num_bits; 1043 foreach (pos, bit; bit_array) 1044 { 1045 if (pos < lower_length) 1046 t.test!("==")(bit, true); 1047 else 1048 t.test!("==")(bit, false); 1049 } 1050 1051 // Checks the bits are reset to zero resizing the BitArray without changing 1052 // its dimension (the BitArray is large enough to hold the new length). 1053 bit_array = [true, true, true, true]; 1054 1055 bit_array.length = 2; 1056 t.test!("==")(bit_array[0], true); 1057 t.test!("==")(bit_array[1], true); 1058 1059 bit_array.length = 4; 1060 t.test!("==")(bit_array[0], true); 1061 t.test!("==")(bit_array[1], true); 1062 t.test!("==")(bit_array[2], false); 1063 t.test!("==")(bit_array[3], false); 1064 }