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