1 /** Statically sized variant of `std.bitmanip.BitArray. 2 * 3 * Copyright: Per Nordlöw 2018-. 4 * License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 5 * Authors: $(WEB Per Nordlöw) 6 */ 7 module nxt.static_bitarray; 8 9 @safe: 10 11 alias DefaultBlock = size_t; ///< Default block type. 12 13 import std.traits : isUnsigned; 14 15 /** A statically sized `std.bitmanip.BitArray`. 16 * 17 * TODO Infer `Block` from `len` as is done for `Bound` and `Mod`. 18 * 19 * TODO Optimize `allOne`, `allZero` using intrinsic? 20 */ 21 struct StaticBitArray(uint capacity, Block = DefaultBlock) 22 if (isUnsigned!DefaultBlock) 23 { 24 @safe: 25 import std.format : FormatSpec, format; 26 import nxt.modulo : Mod; 27 28 /** Number of bits. 29 * 30 * Length equals capacity. 31 */ 32 enum length = capacity; 33 34 static if (capacity >= 1) 35 { 36 alias Index = Mod!capacity; 37 } 38 39 static if (Block.sizeof == 8) 40 { 41 import core.bitop : bt, bts, btr; 42 } 43 else 44 { 45 import nxt.bitop_ex : bt, bts, btr; 46 } 47 48 /** Number of bits per `Block`. */ 49 enum bitsPerBlock = 8*Block.sizeof; 50 /** Number of `Block`s. */ 51 enum blockCount = (capacity + bitsPerBlock-1) / bitsPerBlock; 52 53 /** Data stored as `Block`s. */ 54 private Block[blockCount] _blocks; 55 56 /** Data as an array of unsigned bytes. */ 57 inout(ubyte)[] ubytes()() inout @trusted 58 { 59 pragma(inline, true); 60 return (cast(ubyte*)&_blocks)[0 .. _blocks.sizeof]; 61 } 62 63 /** Get pointer to data blocks. */ 64 @property inout(Block*) ptr() inout @system 65 66 { 67 pragma(inline, true); 68 return _blocks.ptr; 69 } 70 71 /** Reset all bits (to zero). */ 72 void reset()() 73 { 74 pragma(inline, true); 75 _blocks[] = 0; // TODO is this fastest way? 76 } 77 alias clear = reset; 78 79 /** Gets the amount of native words backing `this`. */ 80 @property static uint dim() 81 { 82 pragma(inline, true); 83 return blockCount; 84 } 85 86 /** Bidirectional range into `BitArray`. 87 * 88 * TODO Provide opSliceAssign for interopability with range algorithms via 89 * private static struct member `Range`. 90 * 91 * TODO Look at how std.container.array implements this. 92 * 93 * See_Also: https://dlang.org/phobos/std_bitmanip.html#bitsSet 94 */ 95 struct Range() // template-lazy 96 { 97 @safe pure nothrow @nogc: 98 99 /// Returns: `true` iff `this` is empty. 100 bool empty() const 101 { 102 pragma(inline, true); 103 return _i == _j; 104 } 105 /// Returns: `this` length. 106 size_t length() const 107 { 108 pragma(inline, true); 109 return _j - _i; 110 } 111 112 import std.traits : isMutable; 113 static if (isMutable!(typeof(_store))) 114 { 115 @disable this(this); // Rust-style mutable reference semantics 116 } 117 118 /// Get front. 119 bool front() const 120 { 121 pragma(inline, true); 122 assert(!empty); // only in debug mode since _store is range-checked 123 return (*_store)[_i]; 124 } 125 126 /// Get back. 127 bool back() const 128 { 129 pragma(inline, true); 130 assert(!empty); // only in debug mode since _store is range-checked 131 return (*_store)[_j - 1]; 132 } 133 134 /// Pop front. 135 void popFront() 136 { 137 pragma(inline, true); 138 assert(!empty); 139 ++_i; 140 } 141 142 /// Pop back. 143 void popBack() 144 { 145 pragma(inline, true); 146 assert(!empty); 147 ++_i; 148 } 149 150 private: 151 StaticBitArray* _store; 152 size_t _i = 0; // front iterator into _store 153 size_t _j = _store.length; // back iterator into _store 154 } 155 156 scope inout(Range!()) opSlice()() inout return @trusted 157 { 158 pragma(inline, true); 159 return typeof(return)(&this); 160 } 161 162 scope inout(Range!()) opSlice()(size_t i, size_t j) inout return @trusted 163 { 164 pragma(inline, true); 165 return typeof(return)(&this, i, j); 166 } 167 168 /** Set all bits to `value` via slice assignment syntax. */ 169 ref typeof(this) opSliceAssign(bool value) 170 { 171 if (value) 172 { 173 one(); 174 } 175 else 176 { 177 zero(); 178 } 179 return this; 180 } 181 182 /** Set all bits (to zero). */ 183 private void zero() 184 { 185 foreach (ref block; _blocks) 186 { 187 block = Block.min; 188 } 189 } 190 191 /** Set all bits (to one). */ 192 private void one() 193 { 194 foreach (ref block; _blocks) 195 { 196 block = Block.max; 197 } 198 } 199 200 /** Gets the $(D i)'th bit. */ 201 bool opIndex(size_t i) const @trusted 202 in 203 { 204 assert(i < capacity); // TODO nothrow or not? 205 } 206 do 207 { 208 pragma(inline, true); 209 // Andrei: review for @@@64-bit@@@ 210 static if (Block.sizeof == 8) 211 { 212 return cast(bool)bt(ptr, i); 213 } 214 else 215 { 216 return bt(_blocks[i/bitsPerBlock], i%bitsPerBlock); 217 } 218 } 219 220 /** Gets the $(D i)'th bit. No range checking needed. */ 221 static if (capacity >= 1) 222 { 223 /** Get the $(D i)'th bit. 224 * 225 * Avoids range-checking because `i` of type is bound to (0 .. capacity-1). 226 */ 227 bool opIndex(ModUInt)(Mod!(capacity, ModUInt) i) const @trusted 228 if (isUnsigned!ModUInt) 229 { 230 pragma(inline, true); 231 static if (Block.sizeof == 8) 232 { 233 return cast(bool)bt(ptr, cast(size_t)i); 234 } 235 else 236 { 237 return bt(_blocks[i/bitsPerBlock], i%bitsPerBlock); 238 } 239 } 240 241 /** Get the $(D i)'th bit. 242 * 243 * Statically verifies that i is < StaticBitArray length. 244 */ 245 bool at(size_t i)() const @trusted 246 if (i < capacity) 247 { 248 pragma(inline, true); 249 return this[i]; 250 } 251 } 252 253 /** Puts the $(D i)'th bit to $(D b). */ 254 typeof(this) put()(size_t i, bool b) @trusted 255 { 256 version(LDC) pragma(inline, true); 257 this[i] = b; 258 return this; 259 } 260 261 /** Sets the $(D i)'th bit. */ 262 import std.traits : isIntegral; 263 bool opIndexAssign(Index2)(bool b, Index2 i) @trusted 264 if (isIntegral!Index2) 265 in 266 { 267 // import std.traits: isMutable; 268 // See_Also: http://stackoverflow.com/questions/19906516/static-parameter-function-specialization-in-d 269 /* static if (!isMutable!Index2) { */ 270 /* import std.conv: to; */ 271 /* static assert(i < capacity, */ 272 /* "Index2 " ~ to!string(i) ~ " must be smaller than StaticBitArray length " ~ to!string(capacity)); */ 273 /* } */ 274 assert(i < capacity); 275 } 276 do 277 { 278 pragma(inline, true); 279 if (b) 280 { 281 bts(ptr, cast(size_t)i); 282 } 283 else 284 { 285 btr(ptr, cast(size_t)i); 286 } 287 return b; 288 } 289 290 static if (capacity >= 1) 291 { 292 /** Sets the $(D i)'th bit. No range checking needed. */ 293 pragma(inline, true) 294 bool opIndexAssign(ModUInt)(bool b, Mod!(capacity, ModUInt) i) @trusted 295 if (isUnsigned!ModUInt) 296 { 297 if (b) 298 { 299 bts(ptr, cast(size_t)i); 300 } 301 else 302 { 303 btr(ptr, cast(size_t)i); 304 } 305 return b; 306 } 307 } 308 309 /// 310 @safe pure nothrow @nogc unittest 311 { 312 StaticBitArray!2 bs; 313 bs[0] = true; 314 assert(bs[0]); 315 assert(!bs[1]); 316 bs[1] = true; 317 assert(bs[1]); 318 } 319 320 /** Duplicate. */ 321 @property typeof(this) dup() const // TODO is this needed for value types? 322 { 323 return this; 324 } 325 326 /** Support for $(D foreach) loops for $(D StaticBitArray). */ 327 int opApply(scope int delegate(ref bool) dg) @trusted 328 { 329 int result; 330 foreach (const size_t i; 0 .. capacity) 331 { 332 bool b = opIndex(i); 333 result = dg(b); 334 this[i] = b; 335 if (result) { break; } 336 } 337 return result; 338 } 339 340 /** ditto */ 341 int opApply(scope int delegate(bool) dg) const @trusted 342 { 343 int result; 344 foreach (const size_t i; 0 .. capacity) 345 { 346 bool b = opIndex(i); 347 result = dg(b); 348 if (result) { break; } 349 } 350 return result; 351 } 352 353 /** ditto */ 354 int opApply(scope int delegate(const ref size_t, ref bool) dg) @trusted 355 { 356 int result; 357 foreach (const size_t i; 0 .. capacity) 358 { 359 bool b = opIndex(i); 360 result = dg(i, b); 361 this[i] = b; 362 if (result) { break; } 363 } 364 return result; 365 } 366 367 /** ditto */ 368 int opApply(scope int delegate(size_t, bool) dg) const @trusted 369 { 370 int result; 371 foreach (const size_t i; 0 .. capacity) 372 { 373 bool b = opIndex(i); 374 result = dg(i, b); 375 if (result) { break; } 376 } 377 return result; 378 } 379 380 /// 381 unittest 382 { 383 static bool[] ba = [1,0,1]; 384 auto a = StaticBitArray!3(ba); 385 size_t i; 386 foreach (immutable b; a[]) // TODO is `opSlice` the right thing? 387 { 388 switch (i) 389 { 390 case 0: assert(b == true); break; 391 case 1: assert(b == false); break; 392 case 2: assert(b == true); break; 393 default: assert(0); 394 } 395 i++; 396 } 397 foreach (j, b; a) // TODO is `opSlice` the right thing? 398 { 399 switch (j) 400 { 401 case 0: assert(b == true); break; 402 case 1: assert(b == false); break; 403 case 2: assert(b == true); break; 404 default: assert(0); 405 } 406 } 407 } 408 409 /** Reverse block `Block`. */ 410 static @property Block reverseBlock()(in Block block) 411 { 412 import core.bitop : bitswap; 413 pragma(inline, true); 414 static if (Block.sizeof == 4) 415 { 416 return cast(uint)block.bitswap; 417 } 418 else static if (Block.sizeof == 8) 419 { 420 return (((cast(Block)((cast(uint)(block)).bitswap)) << 32) | 421 (cast(Block)((cast(uint)(block >> 32)).bitswap))); 422 } 423 else 424 { 425 return block; 426 } 427 } 428 429 /** Reverses the bits of the $(D StaticBitArray) in place. */ 430 @property typeof(this) reverse()() 431 out (result) 432 { 433 assert(result == this); 434 } 435 do 436 { 437 static if (length == blockCount * bitsPerBlock) 438 { 439 static if (blockCount == 1) 440 { 441 _blocks[0] = reverseBlock(_blocks[0]); 442 } 443 else static if (blockCount == 2) 444 { 445 const tmp = _blocks[1]; 446 _blocks[1] = reverseBlock(_blocks[0]); 447 _blocks[0] = reverseBlock(tmp); 448 } 449 else static if (blockCount == 3) 450 { 451 const tmp = _blocks[2]; 452 _blocks[2] = reverseBlock(_blocks[0]); 453 _blocks[1] = reverseBlock(_blocks[1]); 454 _blocks[0] = reverseBlock(tmp); 455 } 456 else 457 { 458 size_t lo = 0; 459 size_t hi = _blocks.length - 1; 460 for (; lo < hi; ++lo, --hi) 461 { 462 immutable t = reverseBlock(_blocks[lo]); 463 _blocks[lo] = reverseBlock(_blocks[hi]); 464 _blocks[hi] = t; 465 } 466 if (lo == hi) 467 { 468 _blocks[lo] = reverseBlock(_blocks[lo]); 469 } 470 } 471 } 472 else 473 { 474 static if (length >= 2) 475 { 476 size_t lo = 0; 477 size_t hi = capacity - 1; 478 for (; lo < hi; ++lo, --hi) 479 { 480 immutable t = this[lo]; 481 this[lo] = this[hi]; 482 this[hi] = t; 483 } 484 } 485 } 486 return this; 487 } 488 489 /// 490 pure unittest 491 { 492 enum capacity = 64; 493 static immutable bool[capacity] data = [0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 494 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0]; 495 auto b = StaticBitArray!capacity(data); 496 b.reverse(); 497 for (size_t i = 0; i < data.length; ++i) 498 { 499 assert(b[i] == data[capacity - 1 - i]); 500 } 501 } 502 503 /// 504 pure unittest 505 { 506 enum capacity = 64*2; 507 static immutable bool[capacity] data = [0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 508 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 509 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 510 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0]; 511 auto b = StaticBitArray!capacity(data); 512 b.reverse(); 513 for (size_t i = 0; i < data.length; ++i) 514 { 515 assert(b[i] == data[capacity - 1 - i]); 516 } 517 } 518 519 /// 520 pure unittest 521 { 522 enum capacity = 64*3; 523 static immutable bool[capacity] data = [0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 524 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 525 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 526 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 527 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 528 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0, 0,1,1,0,1,0,1,0]; 529 auto b = StaticBitArray!capacity(data); 530 b.reverse(); 531 for (size_t i = 0; i < data.length; ++i) 532 { 533 assert(b[i] == data[capacity - 1 - i]); 534 } 535 } 536 537 /** Sorts the $(D StaticBitArray)'s elements. */ 538 @property typeof(this) sort()() 539 out (result) 540 { 541 assert(result == this); 542 } 543 do 544 { 545 if (capacity >= 2) 546 { 547 size_t lo, hi; 548 lo = 0; 549 hi = capacity - 1; 550 while (1) 551 { 552 while (1) 553 { 554 if (lo >= hi) 555 goto Ldone; 556 if (this[lo] == true) 557 break; 558 lo++; 559 } 560 while (1) 561 { 562 if (lo >= hi) 563 goto Ldone; 564 if (this[hi] == false) 565 break; 566 hi--; 567 } 568 this[lo] = false; 569 this[hi] = true; 570 lo++; 571 hi--; 572 } 573 } 574 Ldone: 575 return this; 576 } 577 578 /* unittest */ 579 /* { */ 580 /* __gshared size_t x = 0b1100011000; */ 581 /* __gshared StaticBitArray ba = { 10, &x }; */ 582 /* ba.sort(); */ 583 /* for (size_t i = 0; i < 6; ++i) */ 584 /* assert(ba[i] == false); */ 585 /* for (size_t i = 6; i < 10; ++i) */ 586 /* assert(ba[i] == true); */ 587 /* } */ 588 589 590 /** Support for operators == and != for $(D StaticBitArray). */ 591 bool opEquals(Block2)(in StaticBitArray!(capacity, Block2) a2) const @trusted 592 if (isUnsigned!Block2) 593 { 594 size_t i; 595 596 if (this.length != a2.length) { return 0; } // not equal 597 auto p1 = this.ptr; 598 auto p2 = a2.ptr; 599 auto n = this.length / bitsPerBlock; 600 for (i = 0; i < n; ++i) 601 { 602 if (p1[i] != p2[i]) { return 0; } // not equal 603 } 604 605 n = this.length & (bitsPerBlock-1); 606 size_t mask = (1 << n) - 1; 607 //printf("i = %d, n = %d, mask = %x, %x, %x\n", i, n, mask, p1[i], p2[i]); 608 return (mask == 0) || (p1[i] & mask) == (p2[i] & mask); 609 } 610 /// 611 nothrow unittest 612 { 613 auto a = StaticBitArray!(5, ubyte)([1,0,1,0,1]); 614 auto b = StaticBitArray!(5, ushort)([1,0,1,1,1]); 615 auto c = StaticBitArray!(5, uint)([1,0,1,0,1]); 616 auto d = StaticBitArray!(5, ulong)([1,1,1,1,1]); 617 assert(a != b); 618 assert(a == c); 619 assert(a != d); 620 } 621 622 /** Supports comparison operators for $(D StaticBitArray). */ 623 int opCmp(Block2)(in StaticBitArray!(capacity, Block2) a2) const @trusted 624 if (isUnsigned!Block2) 625 { 626 uint i; 627 628 auto capacity = this.length; 629 if (a2.length < capacity) { capacity = a2.length; } 630 auto p1 = this.ptr; 631 auto p2 = a2.ptr; 632 auto n = capacity / bitsPerBlock; 633 for (i = 0; i < n; ++i) 634 { 635 if (p1[i] != p2[i]) { break; } // not equal 636 } 637 for (size_t j = 0; j < capacity-i * bitsPerBlock; j++) 638 { 639 size_t mask = cast(size_t)(1 << j); 640 auto c = (cast(long)(p1[i] & mask) - cast(long)(p2[i] & mask)); 641 if (c) { return c > 0 ? 1 : -1; } 642 } 643 return cast(int)this.length - cast(int)a2.length; 644 } 645 646 /// 647 nothrow unittest 648 { 649 auto a = StaticBitArray!(5, ubyte)([1,0,1,0,1]); 650 auto b = StaticBitArray!(5, ushort)([1,0,1,1,1]); 651 auto c = StaticBitArray!(5, uint)([1,0,1,0,1]); 652 auto d = StaticBitArray!(5, ulong)([1,1,1,1,1]); 653 assert(a < b); 654 assert(a <= b); 655 assert(a == c); 656 assert(a <= c); 657 assert(a >= c); 658 assert(c < d); 659 } 660 661 /** Support for hashing for $(D StaticBitArray). */ 662 extern(D) hash_t toHash() const @trusted pure nothrow 663 { 664 typeof(return) hash = 3557; 665 auto n = capacity / 8; 666 for (size_t i = 0; i < n; ++i) 667 { 668 hash *= 3559; 669 hash += (cast(byte*)this.ptr)[i]; 670 } 671 for (size_t i = 8*n; i < capacity; ++i) 672 { 673 hash *= 3571; 674 hash += this[i]; 675 } 676 return hash; 677 } 678 679 /** Set `this` to the contents of $(D ba). */ 680 this()(bool[] ba) 681 in 682 { 683 assert(length == ba.length); 684 } 685 do 686 { 687 foreach (immutable i, const b; ba) 688 { 689 this[i] = b; 690 } 691 } 692 693 /** Set `this` to the contents of $(D ba). */ 694 this()(const ref bool[capacity] ba) 695 { 696 foreach (immutable i, const b; ba) 697 { 698 this[i] = b; 699 } 700 } 701 702 bool opCast(T : bool)() const 703 { 704 return !this.allZero; 705 } 706 707 /// construct from dynamic array 708 @safe nothrow @nogc unittest 709 { 710 static bool[] ba = [1,0,1,0,1]; 711 auto a = StaticBitArray!5(ba); 712 assert(a); 713 assert(!a.allZero); 714 } 715 /// ditto 716 @safe nothrow @nogc unittest 717 { 718 static bool[] ba = [0,0,0]; 719 auto a = StaticBitArray!3(ba); 720 assert(!a); 721 assert(a.allZero); 722 } 723 /// construct from static array 724 @safe nothrow @nogc unittest 725 { 726 static bool[3] ba = [0,0,0]; 727 auto a = StaticBitArray!3(ba); 728 assert(!a); 729 assert(a.allZero); 730 } 731 732 static if (capacity >= 1) 733 { 734 import std.traits: isInstanceOf; 735 736 /** Lazy range of the indices of set bits. 737 738 Similar to: `std.bitmanip.bitsSet` 739 740 See_Also: https://dlang.org/phobos/std_bitmanip.html#bitsSet 741 */ 742 struct OneIndexes(Store) 743 // TODO if (isInstanceOf!(StaticBitArray, Store)) 744 { 745 @safe pure nothrow @nogc: 746 747 this(Store* store) 748 { 749 this._store = store; 750 751 // pre-adjust front index. TODO make lazy and move to front 752 while (_i < length && !(*_store)[_i]) 753 { 754 ++_i; 755 } 756 757 // pre-adjust back index. TODO make lazy and move to front 758 while (_j > 1 && !(*_store)[_j]) 759 { 760 --_j; 761 } 762 } 763 764 import std.traits : isMutable; 765 static if (isMutable!(typeof(_store))) 766 { 767 @disable this(this); // Rust-style mutable reference semantics 768 } 769 770 bool empty() const 771 { 772 pragma(inline, true); 773 return _i > _j; 774 } 775 776 /// Get front. 777 Mod!capacity front() const 778 { 779 pragma(inline, true); 780 assert(!empty); // TODO use enforce when it's @nogc 781 return typeof(return)(_i); 782 } 783 784 /// Get back. 785 Mod!capacity back() const 786 { 787 pragma(inline, true); 788 assert(!empty); // TODO use enforce when it's @nogc 789 return typeof(return)(_j); 790 } 791 792 /// Pop front. 793 void popFront() 794 { 795 assert(!empty); 796 while (++_i <= _j) 797 { 798 if ((*_store)[_i]) { break; } 799 } 800 } 801 802 /// Pop back. 803 void popBack() 804 { 805 assert(!empty); 806 while (_i <= --_j) 807 { 808 if ((*_store)[_j]) { break; } 809 } 810 } 811 812 private: 813 Store* _store; // copy of store 814 int _i = 0; // front index into `_store` 815 int _j = (*_store).length - 1; // back index into `_store` 816 } 817 818 /** Returns: a lazy range of the indices of set bits. 819 */ 820 auto oneIndexes()() const 821 { 822 return OneIndexes!(typeof(this))(&this); 823 } 824 /// ditto 825 alias bitsSet = oneIndexes; 826 827 /** Find index of first cleared (zero) bit or `typeof(return).max` if no bit set. 828 * 829 * Optimized for zeros-sparsity. 830 */ 831 size_t indexOfFirstZero()() const 832 { 833 import nxt.bitarray_algorithm; 834 enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0; 835 return indexOfFirstZero!(const(Block)[blockCount], 836 blockAlignedLength)(_blocks, length); 837 } 838 839 /** Find index of first set (one) bit or `typeof(return).max` if no bit set. 840 * 841 * Optimized for ones-sparsity. 842 */ 843 size_t indexOfFirstOne()() const 844 { 845 import nxt.bitarray_algorithm : indexOfFirstOne; 846 enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0; 847 return indexOfFirstOne!(const(Block)[blockCount], 848 blockAlignedLength)(_blocks, length); 849 } 850 851 /** Get number of bits set. */ 852 Mod!(capacity + 1) countOnes()() const // template-lazy. TODO unite with other definitions 853 { 854 import nxt.bitarray_algorithm; 855 enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0; 856 return typeof(return)(nxt.bitarray_algorithm.countOnes!(const(Block)[blockCount], 857 blockAlignedLength)(_blocks, length)); 858 } 859 860 /** Get number of (zero) bits unset. */ 861 size_t countZeros()() const // template-lazy 862 { 863 return length - countOnes; 864 } 865 866 /** Get number of bits set divided by length. */ 867 version(none) 868 auto denseness()(int depth = -1) const // template-lazy 869 { 870 import nxt.rational : Rational; 871 alias Q = Rational!ulong; 872 return Q(countOnes, length); 873 } 874 875 /** Get number of bits unset divided by length. */ 876 version(none) 877 auto sparseness()(int depth = -1) const // template-lazy 878 { 879 import nxt.rational : Rational; 880 alias Q = Rational!ulong; 881 return 1 - denseness(depth); 882 } 883 884 /** Check if `this` has only zeros (is empty). */ 885 bool allZero()() const @safe pure nothrow @nogc 886 { 887 foreach (const block; _fullBlocks) 888 { 889 if (block != Block.min) 890 { 891 return false; 892 } 893 } 894 static if (blockCount) 895 { 896 if (_restBlock != Block.min) 897 { 898 return false; 899 } 900 } 901 return true; 902 } 903 904 /** Check if `this` has only ones. */ 905 bool allOne()() const 906 { 907 const restBitCount = capacity % bitsPerBlock; 908 const hasRest = restBitCount != 0; 909 if (_blocks.length >= 1) 910 { 911 foreach (const block; _blocks[0 .. $ - hasRest]) 912 { 913 if (block != Block.max) { return false; } 914 } 915 } 916 if (restBitCount) 917 { 918 return _blocks[$ - 1] == 2^^restBitCount - 1; 919 } 920 else 921 { 922 return true; 923 } 924 } 925 926 /** Find index (starting at `currIx`) of first bit that equals `value`. 927 * 928 * Returns: `true` if index was found (hit index is put into `nextIx`), `false` otherwise. 929 * 930 * TODO block-optimize for large BitSets 931 */ 932 bool canFindIndexOf(ModUInt)(bool value, 933 Mod!(capacity, ModUInt) currIx, 934 out Mod!(capacity, ModUInt) nextIx) const 935 if (isUnsigned!ModUInt) 936 { 937 if (currIx >= length) { return false; } 938 bool hit = false; 939 foreach (immutable ix_; cast(uint)currIx .. cast(uint)length) 940 { 941 const bool bit = this[ix_]; 942 if (bit == value) 943 { 944 nextIx = typeof(nextIx)(ix_); 945 hit = true; 946 break; 947 } 948 } 949 return hit; 950 } 951 952 bool canFindIndexOf(UInt)(bool value, 953 UInt currIx, 954 out UInt nextIx) const 955 if (isUnsigned!UInt) 956 { 957 if (currIx >= length) { return false; } 958 bool hit = false; 959 foreach (immutable ix_; cast(uint)currIx .. cast(uint)length) 960 { 961 const bool bit = this[ix_]; 962 if (bit == value) 963 { 964 nextIx = typeof(nextIx)(ix_); 965 hit = true; 966 break; 967 } 968 } 969 return hit; 970 } 971 972 } 973 974 /** 975 * Map the $(D StaticBitArray) onto $(D v), with $(D numbits) being the number of bits 976 * in the array. Does not copy the data. 977 * 978 * This is the inverse of $(D opCast). 979 */ 980 /* void init(void[] v, size_t numbits) in { */ 981 /* assert(numbits <= v.length * 8); */ 982 /* assert((v.length & 3) == 0); // must be whole bytes */ 983 /* } do { */ 984 /* _blocks[] = cast(size_t*)v.ptr[0..v.length]; */ 985 /* } */ 986 987 /** Convert to $(D void[]). */ 988 void[] opCast(T : void[])() @trusted 989 { 990 return cast(void[])ptr[0 .. dim]; 991 } 992 993 /** Convert to $(D size_t[]). */ 994 size_t[] opCast(T : size_t[])() 995 { 996 return ptr[0 .. dim]; 997 } 998 /// 999 nothrow unittest 1000 { 1001 static bool[] ba = [1,0,1,0,1]; 1002 auto a = StaticBitArray!5(ba); 1003 void[] v = cast(void[])a; 1004 assert(v.length == a.dim * size_t.sizeof); 1005 } 1006 1007 /** Complement operator. */ 1008 typeof(this) opCom() const @trusted 1009 { 1010 StaticBitArray result; 1011 for (size_t i = 0; i < dim; ++i) 1012 { 1013 result.ptr[i] = cast(Block)~cast(ulong)this.ptr[i]; 1014 } 1015 immutable rem = capacity & (bitsPerBlock-1); // number of rest bits in last block 1016 if (rem < bitsPerBlock) // rest bits in last block 1017 { 1018 // make remaining bits zero in last block 1019 result.ptr[dim - 1] &= ~(~(cast(Block)0) << rem); 1020 } 1021 return result; 1022 } 1023 1024 /** Support for binary operator & for $(D StaticBitArray). */ 1025 typeof(this) opBinary(string op)(in typeof(this) e2) const 1026 if (op == "&") 1027 { 1028 StaticBitArray result; 1029 result._blocks[] = this._blocks[] & e2._blocks[]; 1030 return result; 1031 } 1032 /// 1033 nothrow unittest 1034 { 1035 const a = StaticBitArray!5([1,0,1,0,1]); 1036 auto b = StaticBitArray!5([1,0,1,1,0]); 1037 const c = a & b; 1038 auto d = StaticBitArray!5([1,0,1,0,0]); 1039 assert(c == d); 1040 } 1041 1042 /** Support for binary operator | for $(D StaticBitArray). */ 1043 typeof(this) opBinary(string op)(in typeof(this) e2) const 1044 if (op == "|") 1045 { 1046 StaticBitArray result; 1047 result._blocks[] = this._blocks[] | e2._blocks[]; 1048 return result; 1049 } 1050 /// 1051 nothrow unittest 1052 { 1053 const a = StaticBitArray!5([1,0,1,0,1]); 1054 auto b = StaticBitArray!5([1,0,1,1,0]); 1055 const c = a | b; 1056 auto d = StaticBitArray!5([1,0,1,1,1]); 1057 assert(c == d); 1058 } 1059 1060 /** Support for binary operator ^ for $(D StaticBitArray). */ 1061 typeof(this) opBinary(string op)(in typeof(this) e2) const 1062 if (op == "^") 1063 { 1064 StaticBitArray result; 1065 result._blocks[] = this._blocks[] ^ e2._blocks[]; 1066 return result; 1067 } 1068 /// 1069 nothrow unittest 1070 { 1071 const a = StaticBitArray!5([1,0,1,0,1]); 1072 auto b = StaticBitArray!5([1,0,1,1,0]); 1073 const c = a ^ b; 1074 auto d = StaticBitArray!5([0,0,0,1,1]); 1075 assert(c == d); 1076 } 1077 1078 /** Support for binary operator - for $(D StaticBitArray). 1079 * 1080 * $(D a - b) for $(D StaticBitArray) means the same thing as $(D a & ~b). 1081 */ 1082 typeof(this) opBinary(string op)(in typeof(this) e2) const 1083 if (op == "-") 1084 { 1085 StaticBitArray result; 1086 result._blocks[] = this._blocks[] & ~e2._blocks[]; 1087 return result; 1088 } 1089 /// 1090 nothrow unittest 1091 { 1092 const a = StaticBitArray!5([1,0,1,0,1]); 1093 auto b = StaticBitArray!5([1,0,1,1,0]); 1094 const c = a - b; 1095 auto d = StaticBitArray!5([0,0,0,0,1]); 1096 assert(c == d); 1097 } 1098 1099 /** Support for operator &= for $(D StaticBitArray). 1100 */ 1101 typeof(this) opOpAssign(string op)(in typeof(this) e2) 1102 if (op == "&") 1103 { 1104 _blocks[] &= e2._blocks[]; 1105 return this; 1106 } 1107 /// 1108 nothrow unittest 1109 { 1110 auto a = StaticBitArray!5([1,0,1,0,1]); 1111 const b = StaticBitArray!5([1,0,1,1,0]); 1112 a &= b; 1113 const c = StaticBitArray!5([1,0,1,0,0]); 1114 assert(a == c); 1115 } 1116 1117 /** Support for operator |= for $(D StaticBitArray). 1118 */ 1119 typeof(this) opOpAssign(string op)(in typeof(this) e2) 1120 if (op == "|") 1121 { 1122 _blocks[] |= e2._blocks[]; 1123 return this; 1124 } 1125 /// 1126 nothrow unittest 1127 { 1128 auto a = StaticBitArray!5([1,0,1,0,1]); 1129 const b = StaticBitArray!5([1,0,1,1,0]); 1130 a |= b; 1131 const c = StaticBitArray!5([1,0,1,1,1]); 1132 assert(a == c); 1133 } 1134 1135 /** Support for operator ^= for $(D StaticBitArray). 1136 */ 1137 typeof(this) opOpAssign(string op)(in typeof(this) e2) 1138 if (op == "^") 1139 { 1140 _blocks[] ^= e2._blocks[]; 1141 return this; 1142 } 1143 /// 1144 nothrow unittest 1145 { 1146 auto a = StaticBitArray!5([1,0,1,0,1]); 1147 const b = StaticBitArray!5([1,0,1,1,0]); 1148 a ^= b; 1149 const c = StaticBitArray!5([0,0,0,1,1]); 1150 assert(a == c); 1151 } 1152 1153 /** Support for operator -= for $(D StaticBitArray). 1154 * 1155 * $(D a -= b) for $(D StaticBitArray) means the same thing as $(D a &= ~b). 1156 */ 1157 typeof(this) opOpAssign(string op)(in typeof(this) e2) 1158 if (op == "-") 1159 { 1160 _blocks[] &= ~e2._blocks[]; 1161 return this; 1162 } 1163 /// 1164 nothrow unittest 1165 { 1166 auto a = StaticBitArray!5([1,0,1,0,1]); 1167 const b = StaticBitArray!5([1,0,1,1,0]); 1168 a -= b; 1169 const c = StaticBitArray!5([0,0,0,0,1]); 1170 assert(a == c); 1171 } 1172 1173 /** Return a string representation of this StaticBitArray. 1174 * 1175 * Two format specifiers are supported: 1176 * $(LI $(B %s) which prints the bits as an array, and) 1177 * $(LI $(B %b) which prints the bits as 8-bit byte packets) 1178 * separated with an underscore. 1179 */ 1180 void toString(scope void delegate(scope const(char)[]) sink, 1181 FormatSpec!char fmt) const @trusted 1182 { 1183 switch(fmt.spec) 1184 { 1185 case 'b': 1186 return formatBitString(sink); 1187 case 's': 1188 return formatBitSet(sink); 1189 default: 1190 throw new Exception("Unknown format specifier: %" ~ fmt.spec); 1191 } 1192 } 1193 /// 1194 unittest 1195 { 1196 const b = StaticBitArray!16(([0, 0, 0, 0, 1, 1, 1, 1, 1197 0, 0, 0, 0, 1, 1, 1, 1])); 1198 const s1 = format("%s", b); 1199 assert(s1 == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); 1200 1201 const s2 = format("%b", b); 1202 assert(s2 == "00001111_00001111"); 1203 } 1204 1205 private void formatBitString()(scope void delegate(scope const(char)[]) sink) const @trusted 1206 { 1207 import std.range.primitives : put; 1208 1209 static if (length) 1210 { 1211 const leftover = capacity % 8; 1212 foreach (immutable ix; 0 .. leftover) 1213 { 1214 const bit = this[ix]; 1215 const char[1] res = cast(char)(bit + '0'); 1216 sink.put(res[]); 1217 } 1218 1219 if (leftover && capacity > 8) { sink.put("_"); } // separator 1220 1221 size_t cnt; 1222 foreach (immutable ix; leftover .. capacity) 1223 { 1224 const bit = this[ix]; 1225 const char[1] res = cast(char)(bit + '0'); 1226 sink.put(res[]); 1227 if (++cnt == 8 && ix != capacity - 1) 1228 { 1229 sink.put("_"); // separator 1230 cnt = 0; 1231 } 1232 } 1233 } 1234 } 1235 1236 private void formatBitSet()(scope void delegate(scope const(char)[]) sink) const @trusted 1237 { 1238 sink("["); 1239 foreach (immutable ix; 0 .. capacity) 1240 { 1241 const bit = this[ix]; 1242 const char[1] res = cast(char)(bit + '0'); 1243 sink(res[]); 1244 if (ix+1 < capacity) { sink(", "); } // separator 1245 } 1246 sink("]"); 1247 } 1248 1249 private: 1250 1251 inout(Block)[] _fullBlocks() inout @trusted 1252 { 1253 pragma(inline, true); 1254 const fullBlockCount = length / bitsPerBlock; 1255 return _blocks.ptr[0 .. fullBlockCount]; 1256 } 1257 1258 static if (blockCount) 1259 { 1260 Block _restBlock() const @trusted 1261 { 1262 const restBitCount = length % bitsPerBlock; 1263 return _blocks[blockCount-1] & ((1UL << restBitCount) - 1); 1264 } 1265 } 1266 } 1267 1268 /// run-time 1269 @safe pure nothrow @nogc unittest 1270 { 1271 import std.algorithm : equal; 1272 import nxt.rational : Rational; 1273 1274 alias Q = Rational!ulong; 1275 enum m = 256; 1276 1277 StaticBitArray!m b0; 1278 1279 import nxt.modulo : Mod; 1280 static assert(is(typeof(b0.oneIndexes.front()) == Mod!m)); 1281 1282 b0[1] = 1; 1283 b0[2] = 1; 1284 1285 b0[m/2 - 11] = 1; 1286 b0[m/2 - 1] = 1; 1287 b0[m/2] = 1; 1288 b0[m/2 + 1] = 1; 1289 b0[m/2 + 11] = 1; 1290 1291 b0[m - 3] = 1; 1292 b0[m - 2] = 1; 1293 1294 assert(b0.oneIndexes.equal([1, 2, 1295 m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11, 1296 m - 3, 1297 m - 2].s[])); 1298 assert(b0.countOnes == 9); 1299 } 1300 1301 /// run-time 1302 @safe pure nothrow @nogc unittest 1303 { 1304 import std.algorithm : equal; 1305 import nxt.rational : Rational; 1306 1307 alias Q = Rational!ulong; 1308 enum m = 256; 1309 1310 StaticBitArray!m b0; 1311 1312 import nxt.modulo : Mod; 1313 static assert(is(typeof(b0.oneIndexes.front()) == Mod!m)); 1314 1315 b0[0] = 1; 1316 b0[1] = 1; 1317 b0[m/2 - 11] = 1; 1318 b0[m/2 - 1] = 1; 1319 b0[m/2] = 1; 1320 b0[m/2 + 1] = 1; 1321 b0[m/2 + 11] = 1; 1322 b0[m - 2] = 1; 1323 b0[m - 1] = 1; 1324 1325 assert(b0.oneIndexes.equal([0, 1, 1326 m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11, 1327 m - 2, 1328 m - 1].s[])); 1329 assert(b0.countOnes == 9); 1330 } 1331 1332 /// ditto 1333 @safe pure nothrow @nogc unittest 1334 { 1335 import std.traits : isIterable; 1336 static assert(isIterable!(StaticBitArray!256)); 1337 } 1338 1339 /// test ubyte access 1340 @safe pure nothrow @nogc unittest 1341 { 1342 auto b8 = StaticBitArray!(8, ubyte)(); 1343 b8[0] = 1; 1344 b8[1] = 1; 1345 b8[3] = 1; 1346 b8[6] = 1; 1347 1348 assert(b8.ubytes == [64 + 8 + 2 + 1].s[]); 1349 1350 alias Ix = b8.Index; 1351 Ix nextIx; 1352 1353 assert(b8.canFindIndexOf(true, Ix(0), nextIx)); 1354 assert(nextIx == 0); 1355 1356 assert(b8.canFindIndexOf(true, Ix(1), nextIx)); 1357 assert(nextIx == 1); 1358 1359 assert(b8.canFindIndexOf(true, Ix(2), nextIx)); 1360 assert(nextIx == 3); 1361 1362 assert(b8.canFindIndexOf(true, Ix(3), nextIx)); 1363 assert(nextIx == 3); 1364 1365 assert(b8.canFindIndexOf(true, Ix(4), nextIx)); 1366 assert(nextIx == 6); 1367 1368 assert(!b8.canFindIndexOf(true, Ix(7), nextIx)); 1369 } 1370 1371 /// test all zero and all one predicates 1372 @safe pure nothrow @nogc unittest 1373 { 1374 static void test(size_t restBitCount)() 1375 { 1376 enum n = 8*size_t.sizeof + restBitCount; 1377 1378 auto bs = StaticBitArray!(n, size_t)(); 1379 1380 assert(bs.allZero); 1381 assert(!bs.allOne); 1382 1383 foreach (immutable i; 0 .. n - 1) 1384 { 1385 bs[i] = true; 1386 assert(!bs.allZero); 1387 assert(!bs.allOne); 1388 } 1389 bs[n - 1] = true; 1390 1391 assert(bs.allOne); 1392 } 1393 test!0; 1394 test!1; 1395 test!2; 1396 test!37; 1397 test!62; 1398 test!63; 1399 } 1400 1401 /// ditto 1402 @safe unittest 1403 { 1404 import std.format : format; 1405 1406 const b0_ = StaticBitArray!0([]); 1407 const b0 = b0_; 1408 assert(format("%s", b0) == "[]"); 1409 assert(format("%b", b0) is null); 1410 1411 const b1_ = StaticBitArray!1([1]); 1412 const b1 = b1_; 1413 assert(format("%s", b1) == "[1]"); 1414 assert(format("%b", b1) == "1"); 1415 1416 const b4 = StaticBitArray!4([0, 0, 0, 0]); 1417 assert(format("%b", b4) == "0000"); 1418 1419 const b8 = StaticBitArray!8([0, 0, 0, 0, 1, 1, 1, 1]); 1420 assert(format("%s", b8) == "[0, 0, 0, 0, 1, 1, 1, 1]"); 1421 assert(format("%b", b8) == "00001111"); 1422 1423 const b16 = StaticBitArray!16([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 1424 assert(format("%s", b16) == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); 1425 assert(format("%b", b16) == "00001111_00001111"); 1426 1427 const b9 = StaticBitArray!9([1, 0, 0, 0, 0, 1, 1, 1, 1]); 1428 assert(format("%b", b9) == "1_00001111"); 1429 1430 const b17 = StaticBitArray!17([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 1431 assert(format("%b", b17) == "1_00001111_00001111"); 1432 } 1433 1434 /// test range 1435 @safe pure nothrow unittest 1436 { 1437 static testRange(Block)() 1438 { 1439 StaticBitArray!(6, Block) bs = [false, 1, 0, 0, true, 0]; 1440 bs.put(3, true); 1441 1442 import std.algorithm : equal; 1443 1444 assert(bs[0] == false); 1445 assert(bs[1] == true); 1446 assert(bs[2] == false); 1447 assert(bs[3] == true); 1448 assert(bs[4] == true); 1449 assert(bs[5] == false); 1450 1451 assert(bs.at!0 == false); 1452 assert(bs.at!1 == true); 1453 assert(bs.at!2 == false); 1454 assert(bs.at!3 == true); 1455 assert(bs.at!4 == true); 1456 assert(bs.at!5 == false); 1457 1458 // test slicing 1459 assert(bs[].equal([0, 1, 0, 1, 1, 0].s[])); 1460 assert(bs[1 .. 4].equal([1, 0, 1].s[])); 1461 1462 auto rs = bs[1 .. 6 - 1]; // TODO Use opDollar 1463 assert(rs.length == 4); 1464 assert(rs.front == 1); 1465 assert(rs.back == 1); 1466 1467 rs.popFront(); 1468 assert(rs.front == 0); 1469 assert(rs.back == 1); 1470 1471 rs.popBack(); 1472 assert(rs.front == 1); 1473 assert(rs.back == 1); 1474 1475 rs.popFront(); 1476 rs.popBack(); 1477 1478 assert(rs.length == 0); 1479 assert(rs.empty); 1480 } 1481 1482 import std.meta : AliasSeq; 1483 foreach (Block; AliasSeq!(ubyte, ushort, uint, ulong, size_t)) 1484 { 1485 testRange!Block; 1486 } 1487 } 1488 1489 /// 1490 @safe pure nothrow @nogc unittest 1491 { 1492 alias Block = size_t; 1493 enum blockCount = 2; 1494 enum n = blockCount * 8*Block.sizeof - 1; 1495 StaticBitArray!(n) x; 1496 static assert(x.blockCount == blockCount); 1497 1498 assert(x.indexOfFirstOne == n); 1499 x[n - 1] = true; 1500 assert(x.indexOfFirstOne == x.length - 1); 1501 x[n - 2] = true; 1502 assert(x.indexOfFirstOne == x.length - 2); 1503 1504 x[n/2 + 1] = true; 1505 assert(x.indexOfFirstOne == x.length/2 + 1); 1506 x[n/2] = true; 1507 assert(x.indexOfFirstOne == x.length/2); 1508 x[n/2 - 1] = true; 1509 assert(x.indexOfFirstOne == x.length/2 - 1); 1510 1511 x[0] = true; 1512 assert(x.indexOfFirstOne == 0); 1513 assert(x[0]); 1514 assert(!x[1]); 1515 1516 x[1] = true; 1517 assert(x[1]); 1518 1519 x[1] = false; 1520 assert(!x[1]); 1521 } 1522 1523 /// Test opSliceAssign. 1524 @safe pure nothrow @nogc unittest 1525 { 1526 alias Block = size_t; 1527 enum blockCount = 2; 1528 enum n = blockCount * 8*Block.sizeof - 1; 1529 1530 StaticBitArray!(n) x; 1531 assert(x.countOnes == 0); 1532 1533 x[] = true; 1534 assert(x.countOnes == n); 1535 1536 x[] = false; 1537 assert(x.countOnes == 0); 1538 } 1539 1540 version(unittest) 1541 { 1542 import nxt.array_help : s; 1543 }