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 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 import std.traits: isInstanceOf; 601 602 /** Lazy range of the indices of set bits. 603 604 Similar to: `std.bitmanip.bitsSet` 605 606 See_Also: https://dlang.org/phobos/std_bitmanip.html#bitsSet 607 */ 608 struct OneIndexes(Store) 609 // TODO: if (isInstanceOf!(StaticBitArray, Store)) 610 { 611 @safe pure nothrow @nogc: 612 613 this(Store* store) 614 { 615 this._store = store; 616 617 // pre-adjust front index. TODO: make lazy and move to front 618 while (_i < length && !(*_store)[_i]) 619 ++_i; 620 621 // pre-adjust back index. TODO: make lazy and move to front 622 while (_j > 1 && !(*_store)[_j]) 623 --_j; 624 } 625 626 import std.traits : isMutable; 627 static if (isMutable!(typeof(_store))) 628 @disable this(this); // Rust-style mutable reference semantics 629 630 pragma(inline, true): 631 632 bool empty() const @property => _i > _j; 633 Mod!capacity front() const @property in(!empty) => typeof(return)(_i); // TODO: use enforce when it's @nogc 634 Mod!capacity back() const @property in(!empty) => typeof(return)(_j); // TODO: use enforce when it's @nogc 635 void popFront() in(!empty) 636 { 637 version(DigitalMars) pragma(inline); 638 while (++_i <= _j) 639 if ((*_store)[_i]) 640 break; 641 } 642 void popBack() in(!empty) 643 { 644 while (_i <= --_j) 645 if ((*_store)[_j]) 646 break; 647 } 648 649 private: 650 Store* _store; // copy of store 651 int _i = 0; // front index into `_store` 652 int _j = (*_store).length - 1; // back index into `_store` 653 } 654 655 /** Returns: a lazy range of the indices of set bits. 656 */ 657 auto oneIndexes()() const => OneIndexes!(typeof(this))(&this); 658 /// ditto 659 alias bitsSet = oneIndexes; 660 661 /** Find index of first cleared (zero) bit or `typeof(return).max` if no bit set. 662 * 663 * Optimized for zeros-sparsity. 664 */ 665 size_t indexOfFirstZero()() const 666 { 667 import nxt.bitarray_algorithm; 668 enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0; 669 return indexOfFirstZero!(const(Block)[blockCount], 670 blockAlignedLength)(_blocks, length); 671 } 672 673 /** Find index of first set (one) bit or `typeof(return).max` if no bit set. 674 * 675 * Optimized for ones-sparsity. 676 */ 677 size_t indexOfFirstOne()() const 678 { 679 import nxt.bitarray_algorithm : indexOfFirstOne; 680 enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0; 681 return indexOfFirstOne!(const(Block)[blockCount], 682 blockAlignedLength)(_blocks, length); 683 } 684 685 /** Get number of bits set. */ 686 Mod!(capacity + 1) countOnes()() const /* template-lazy. TODO: unite with other definitions */ 687 { 688 import nxt.bitarray_algorithm; 689 enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0; 690 return typeof(return)(nxt.bitarray_algorithm.countOnes!(const(Block)[blockCount], 691 blockAlignedLength)(_blocks, length)); 692 } 693 694 /** Get number of (zero) bits unset. */ 695 size_t countZeros()() const /* template-lazy */ 696 { 697 return length - countOnes; 698 } 699 700 /** Get number of bits set divided by length. */ 701 version(none) 702 auto denseness()(int depth = -1) const /* template-lazy */ 703 { 704 import nxt.rational : Rational; 705 alias Q = Rational!ulong; 706 return Q(countOnes, length); 707 } 708 709 /** Get number of bits unset divided by length. */ 710 version(none) 711 auto sparseness()(int depth = -1) const /* template-lazy */ 712 { 713 import nxt.rational : Rational; 714 alias Q = Rational!ulong; 715 return 1 - denseness(depth); 716 } 717 718 /** Check if `this` has only zeros (is empty). */ 719 bool allZero()() const @safe pure nothrow @nogc 720 { 721 foreach (const block; _fullBlocks) 722 if (block != Block.min) 723 return false; 724 static if (blockCount) 725 if (_restBlock != Block.min) 726 return false; 727 return true; 728 } 729 730 /** Check if `this` has only ones. */ 731 bool allOne()() const 732 { 733 const restBitCount = capacity % bitsPerBlock; 734 const hasRest = restBitCount != 0; 735 if (_blocks.length >= 1) 736 foreach (const block; _blocks[0 .. $ - hasRest]) 737 if (block != Block.max) { return false; } 738 if (restBitCount) 739 return _blocks[$ - 1] == 2^^restBitCount - 1; 740 else 741 return true; 742 } 743 744 /** Find index (starting at `currIx`) of first bit that equals `value`. 745 * 746 * Returns: `true` if index was found (hit index is put into `nextIx`), `false` otherwise. 747 * 748 * TODO: block-optimize for large BitSets 749 */ 750 bool canFindIndexOf(ModUInt)(bool value, 751 Mod!(capacity, ModUInt) currIx, 752 out Mod!(capacity, ModUInt) nextIx) const 753 if (isUnsigned!ModUInt) 754 { 755 if (currIx >= length) { return false; } 756 bool hit = false; 757 foreach (immutable ix_; cast(uint)currIx .. cast(uint)length) 758 { 759 const bool bit = this[ix_]; 760 if (bit == value) 761 { 762 nextIx = typeof(nextIx)(ix_); 763 hit = true; 764 break; 765 } 766 } 767 return hit; 768 } 769 770 bool canFindIndexOf(UInt)(bool value, 771 UInt currIx, 772 out UInt nextIx) const 773 if (isUnsigned!UInt) 774 { 775 if (currIx >= length) { return false; } 776 bool hit = false; 777 foreach (immutable ix_; cast(uint)currIx .. cast(uint)length) 778 { 779 const bool bit = this[ix_]; 780 if (bit == value) 781 { 782 nextIx = typeof(nextIx)(ix_); 783 hit = true; 784 break; 785 } 786 } 787 return hit; 788 } 789 790 } 791 792 /** 793 * Map the $(D StaticBitArray) onto $(D v), with $(D numbits) being the number of bits 794 * in the array. Does not copy the data. 795 * 796 * This is the inverse of $(D opCast). 797 */ 798 /* void init(void[] v, size_t numbits) in { */ 799 /* assert(numbits <= v.length * 8); */ 800 /* assert((v.length & 3) == 0); // must be whole bytes */ 801 /* } do { */ 802 /* _blocks[] = cast(in size_t*)v.ptr[0..v.length]; */ 803 /* } */ 804 805 /** Convert to $(D void[]). */ 806 void[] opCast(T : void[])() @trusted => cast(void[])ptr[0 .. dim]; 807 808 /** Convert to $(D size_t[]). */ 809 size_t[] opCast(T : size_t[])() => ptr[0 .. dim]; 810 /// 811 nothrow unittest 812 { 813 static bool[] ba = [1,0,1,0,1]; 814 auto a = StaticBitArray!5(ba); 815 void[] v = cast(void[])a; 816 assert(v.length == a.dim * size_t.sizeof); 817 } 818 819 /** Complement operator. */ 820 typeof(this) opCom() const @trusted 821 { 822 StaticBitArray result; 823 foreach (const i; 0 .. dim) 824 result.ptr[i] = cast(Block)~cast(ulong)this.ptr[i]; 825 immutable rem = capacity & (bitsPerBlock-1); // number of rest bits in last block 826 if (rem < bitsPerBlock) // rest bits in last block 827 // make remaining bits zero in last block 828 result.ptr[dim - 1] &= ~(~(cast(Block)0) << rem); 829 return result; 830 } 831 832 /** Support for binary operator & for $(D StaticBitArray). */ 833 typeof(this) opBinary(string op)(in typeof(this) e2) const 834 if (op == "&") 835 { 836 StaticBitArray result; 837 result._blocks[] = this._blocks[] & e2._blocks[]; 838 return result; 839 } 840 /// 841 nothrow unittest 842 { 843 const a = StaticBitArray!5([1,0,1,0,1]); 844 auto b = StaticBitArray!5([1,0,1,1,0]); 845 const c = a & b; 846 auto d = StaticBitArray!5([1,0,1,0,0]); 847 assert(c == d); 848 } 849 850 /** Support for binary operator | for $(D StaticBitArray). */ 851 typeof(this) opBinary(string op)(in typeof(this) e2) const if (op == "|") 852 { 853 StaticBitArray result; 854 result._blocks[] = this._blocks[] | e2._blocks[]; 855 return result; 856 } 857 /// 858 nothrow unittest 859 { 860 const a = StaticBitArray!5([1,0,1,0,1]); 861 auto b = StaticBitArray!5([1,0,1,1,0]); 862 const c = a | b; 863 auto d = StaticBitArray!5([1,0,1,1,1]); 864 assert(c == d); 865 } 866 867 /** Support for binary operator ^ for $(D StaticBitArray). */ 868 typeof(this) opBinary(string op)(in typeof(this) e2) const if (op == "^") 869 { 870 StaticBitArray result; 871 result._blocks[] = this._blocks[] ^ e2._blocks[]; 872 return result; 873 } 874 /// 875 nothrow unittest 876 { 877 const a = StaticBitArray!5([1,0,1,0,1]); 878 auto b = StaticBitArray!5([1,0,1,1,0]); 879 const c = a ^ b; 880 auto d = StaticBitArray!5([0,0,0,1,1]); 881 assert(c == d); 882 } 883 884 /** Support for binary operator - for $(D StaticBitArray). 885 * 886 * $(D a - b) for $(D StaticBitArray) means the same thing as $(D a & ~b). 887 */ 888 typeof(this) opBinary(string op)(in typeof(this) e2) const if (op == "-") 889 { 890 StaticBitArray result; 891 result._blocks[] = this._blocks[] & ~e2._blocks[]; 892 return result; 893 } 894 /// 895 nothrow unittest 896 { 897 const a = StaticBitArray!5([1,0,1,0,1]); 898 auto b = StaticBitArray!5([1,0,1,1,0]); 899 const c = a - b; 900 auto d = StaticBitArray!5([0,0,0,0,1]); 901 assert(c == d); 902 } 903 904 /** Support for operator &= for $(D StaticBitArray). 905 */ 906 typeof(this) opOpAssign(string op)(in typeof(this) e2) if (op == "&") 907 { 908 _blocks[] &= e2._blocks[]; 909 return this; 910 } 911 /// 912 nothrow unittest 913 { 914 auto a = StaticBitArray!5([1,0,1,0,1]); 915 const b = StaticBitArray!5([1,0,1,1,0]); 916 a &= b; 917 const c = StaticBitArray!5([1,0,1,0,0]); 918 assert(a == c); 919 } 920 921 /** Support for operator |= for $(D StaticBitArray). 922 */ 923 typeof(this) opOpAssign(string op)(in typeof(this) e2) if (op == "|") 924 { 925 _blocks[] |= e2._blocks[]; 926 return this; 927 } 928 /// 929 nothrow unittest 930 { 931 auto a = StaticBitArray!5([1,0,1,0,1]); 932 const b = StaticBitArray!5([1,0,1,1,0]); 933 a |= b; 934 const c = StaticBitArray!5([1,0,1,1,1]); 935 assert(a == c); 936 } 937 938 /** Support for operator ^= for $(D StaticBitArray). 939 */ 940 typeof(this) opOpAssign(string op)(in typeof(this) e2) if (op == "^") 941 { 942 _blocks[] ^= e2._blocks[]; 943 return this; 944 } 945 /// 946 nothrow unittest 947 { 948 auto a = StaticBitArray!5([1,0,1,0,1]); 949 const b = StaticBitArray!5([1,0,1,1,0]); 950 a ^= b; 951 const c = StaticBitArray!5([0,0,0,1,1]); 952 assert(a == c); 953 } 954 955 /** Support for operator -= for $(D StaticBitArray). 956 * 957 * $(D a -= b) for $(D StaticBitArray) means the same thing as $(D a &= ~b). 958 */ 959 typeof(this) opOpAssign(string op)(in typeof(this) e2) if (op == "-") 960 { 961 _blocks[] &= ~e2._blocks[]; 962 return this; 963 } 964 /// 965 nothrow unittest 966 { 967 auto a = StaticBitArray!5([1,0,1,0,1]); 968 const b = StaticBitArray!5([1,0,1,1,0]); 969 a -= b; 970 const c = StaticBitArray!5([0,0,0,0,1]); 971 assert(a == c); 972 } 973 974 /** Return a string representation of this StaticBitArray. 975 * 976 * Two format specifiers are supported: 977 * $(LI $(B %s) which prints the bits as an array, and) 978 * $(LI $(B %b) which prints the bits as 8-bit byte packets) 979 * separated with an underscore. 980 */ 981 void toString(Sink)(ref scope Sink sink, FormatSpec!char fmt) const @trusted 982 { 983 switch(fmt.spec) 984 { 985 case 'b': 986 return formatBitString(sink); 987 case 's': 988 return formatBitSet(sink); 989 default: 990 throw new Exception("Unknown format specifier: %" ~ fmt.spec); 991 } 992 } 993 /// 994 unittest 995 { 996 const b = StaticBitArray!16(([0, 0, 0, 0, 1, 1, 1, 1, 997 0, 0, 0, 0, 1, 1, 1, 1])); 998 const s1 = format("%s", b); 999 assert(s1 == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); 1000 1001 const s2 = format("%b", b); 1002 assert(s2 == "00001111_00001111"); 1003 } 1004 1005 private void formatBitString(Sink)(ref scope Sink sink) const @trusted 1006 { 1007 import std.range.primitives : put; 1008 1009 static if (length) 1010 { 1011 const leftover = capacity % 8; 1012 foreach (immutable ix; 0 .. leftover) 1013 { 1014 const bit = this[ix]; 1015 const char[1] res = cast(char)(bit + '0'); 1016 sink.put(res[]); 1017 } 1018 1019 if (leftover && 1020 capacity > 8) 1021 sink.put("_"); // separator 1022 1023 size_t cnt; 1024 foreach (immutable ix; leftover .. capacity) 1025 { 1026 const bit = this[ix]; 1027 const char[1] res = cast(char)(bit + '0'); 1028 sink.put(res[]); 1029 if (++cnt == 8 && ix != capacity - 1) 1030 { 1031 sink.put("_"); // separator 1032 cnt = 0; 1033 } 1034 } 1035 } 1036 } 1037 1038 private void formatBitSet(Sink)(ref scope Sink sink) const @trusted 1039 { 1040 sink("["); 1041 foreach (immutable ix; 0 .. capacity) 1042 { 1043 const bit = this[ix]; 1044 const char[1] res = cast(char)(bit + '0'); 1045 sink(res[]); 1046 if (ix+1 < capacity) { sink(", "); } // separator 1047 } 1048 sink("]"); 1049 } 1050 1051 private: 1052 pragma(inline, true) 1053 inout(Block)[] _fullBlocks() inout @trusted => _blocks.ptr[0 .. (length / bitsPerBlock)]; 1054 1055 static if (blockCount) 1056 { 1057 Block _restBlock() const @trusted 1058 { 1059 const restBitCount = length % bitsPerBlock; 1060 return _blocks[blockCount-1] & ((1UL << restBitCount) - 1); 1061 } 1062 } 1063 } 1064 1065 /// run-time 1066 @safe pure nothrow @nogc unittest 1067 { 1068 import nxt.array_algorithm : equal; 1069 1070 enum m = 256; 1071 1072 StaticBitArray!m b0; 1073 1074 import nxt.modulo : Mod; 1075 static assert(is(typeof(b0.oneIndexes.front()) == Mod!m)); 1076 1077 b0[1] = 1; 1078 b0[2] = 1; 1079 1080 b0[m/2 - 11] = 1; 1081 b0[m/2 - 1] = 1; 1082 b0[m/2] = 1; 1083 b0[m/2 + 1] = 1; 1084 b0[m/2 + 11] = 1; 1085 1086 b0[m - 3] = 1; 1087 b0[m - 2] = 1; 1088 1089 assert(b0.oneIndexes.equal([1, 2, 1090 m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11, 1091 m - 3, 1092 m - 2].s[])); 1093 assert(b0.countOnes == 9); 1094 } 1095 1096 /// run-time 1097 @safe pure nothrow @nogc unittest 1098 { 1099 import nxt.array_algorithm : equal; 1100 1101 enum m = 256; 1102 1103 StaticBitArray!m b0; 1104 1105 import nxt.modulo : Mod; 1106 static assert(is(typeof(b0.oneIndexes.front()) == Mod!m)); 1107 1108 b0[0] = 1; 1109 b0[1] = 1; 1110 b0[m/2 - 11] = 1; 1111 b0[m/2 - 1] = 1; 1112 b0[m/2] = 1; 1113 b0[m/2 + 1] = 1; 1114 b0[m/2 + 11] = 1; 1115 b0[m - 2] = 1; 1116 b0[m - 1] = 1; 1117 1118 assert(b0.oneIndexes.equal([0, 1, 1119 m/2 - 11, m/2 - 1, m/2, m/2 + 1, m/2 + 11, 1120 m - 2, 1121 m - 1].s[])); 1122 assert(b0.countOnes == 9); 1123 } 1124 1125 /// ditto 1126 @safe pure nothrow @nogc unittest 1127 { 1128 import std.traits : isIterable; 1129 static assert(isIterable!(StaticBitArray!256)); 1130 } 1131 1132 /// test ubyte access 1133 @safe pure nothrow @nogc unittest 1134 { 1135 auto b8 = StaticBitArray!(8, ubyte)(); 1136 b8[0] = 1; 1137 b8[1] = 1; 1138 b8[3] = 1; 1139 b8[6] = 1; 1140 1141 assert(b8.ubytes == [64 + 8 + 2 + 1].s[]); 1142 1143 alias Ix = b8.Index; 1144 Ix nextIx; 1145 1146 assert(b8.canFindIndexOf(true, Ix(0), nextIx)); 1147 assert(nextIx == 0); 1148 1149 assert(b8.canFindIndexOf(true, Ix(1), nextIx)); 1150 assert(nextIx == 1); 1151 1152 assert(b8.canFindIndexOf(true, Ix(2), nextIx)); 1153 assert(nextIx == 3); 1154 1155 assert(b8.canFindIndexOf(true, Ix(3), nextIx)); 1156 assert(nextIx == 3); 1157 1158 assert(b8.canFindIndexOf(true, Ix(4), nextIx)); 1159 assert(nextIx == 6); 1160 1161 assert(!b8.canFindIndexOf(true, Ix(7), nextIx)); 1162 } 1163 1164 /// test all zero and all one predicates 1165 @safe pure nothrow @nogc unittest 1166 { 1167 static void test(size_t restBitCount)() 1168 { 1169 enum n = 8*size_t.sizeof + restBitCount; 1170 1171 auto bs = StaticBitArray!(n, size_t)(); 1172 1173 assert(bs.allZero); 1174 assert(!bs.allOne); 1175 1176 foreach (immutable i; 0 .. n - 1) 1177 { 1178 bs[i] = true; 1179 assert(!bs.allZero); 1180 assert(!bs.allOne); 1181 } 1182 bs[n - 1] = true; 1183 1184 assert(bs.allOne); 1185 } 1186 test!0; 1187 test!1; 1188 test!2; 1189 test!37; 1190 test!62; 1191 test!63; 1192 } 1193 1194 /// ditto 1195 @safe unittest 1196 { 1197 import std.format : format; 1198 1199 const b0_ = StaticBitArray!0([]); 1200 const b0 = b0_; 1201 assert(format("%s", b0) == "[]"); 1202 assert(format("%b", b0) is null); 1203 1204 const b1_ = StaticBitArray!1([1]); 1205 const b1 = b1_; 1206 assert(format("%s", b1) == "[1]"); 1207 assert(format("%b", b1) == "1"); 1208 1209 const b4 = StaticBitArray!4([0, 0, 0, 0]); 1210 assert(format("%b", b4) == "0000"); 1211 1212 const b8 = StaticBitArray!8([0, 0, 0, 0, 1, 1, 1, 1]); 1213 assert(format("%s", b8) == "[0, 0, 0, 0, 1, 1, 1, 1]"); 1214 assert(format("%b", b8) == "00001111"); 1215 1216 const b16 = StaticBitArray!16([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 1217 assert(format("%s", b16) == "[0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]"); 1218 assert(format("%b", b16) == "00001111_00001111"); 1219 1220 const b9 = StaticBitArray!9([1, 0, 0, 0, 0, 1, 1, 1, 1]); 1221 assert(format("%b", b9) == "1_00001111"); 1222 1223 const b17 = StaticBitArray!17([1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]); 1224 assert(format("%b", b17) == "1_00001111_00001111"); 1225 } 1226 1227 /// test range 1228 @safe pure nothrow unittest 1229 { 1230 static testRange(Block)() 1231 { 1232 StaticBitArray!(6, Block) bs = [false, 1, 0, 0, true, 0]; 1233 bs.put(3, true); 1234 1235 import nxt.array_algorithm : equal; 1236 1237 assert(bs[0] == false); 1238 assert(bs[1] == true); 1239 assert(bs[2] == false); 1240 assert(bs[3] == true); 1241 assert(bs[4] == true); 1242 assert(bs[5] == false); 1243 1244 assert(bs.at!0 == false); 1245 assert(bs.at!1 == true); 1246 assert(bs.at!2 == false); 1247 assert(bs.at!3 == true); 1248 assert(bs.at!4 == true); 1249 assert(bs.at!5 == false); 1250 1251 // test slicing 1252 assert(bs[].equal([0, 1, 0, 1, 1, 0].s[])); 1253 assert(bs[1 .. 4].equal([1, 0, 1].s[])); 1254 1255 auto rs = bs[1 .. 6 - 1]; // TODO: Use opDollar 1256 assert(rs.length == 4); 1257 assert(rs.front == true); 1258 assert(rs.back == true); 1259 1260 rs.popFront(); 1261 assert(rs.front == false); 1262 assert(rs.back == true); 1263 1264 rs.popBack(); 1265 assert(rs.front == false); 1266 assert(rs.back == true); 1267 1268 rs.popFront(); 1269 assert(rs.front == true); 1270 assert(rs.back == true); 1271 1272 rs.popBack(); 1273 assert(rs.length == 0); 1274 assert(rs.empty); 1275 } 1276 1277 import std.meta : AliasSeq; 1278 foreach (Block; AliasSeq!(ubyte, ushort, uint, ulong, size_t)) 1279 testRange!Block; 1280 } 1281 1282 /// 1283 @safe pure nothrow @nogc unittest 1284 { 1285 alias Block = size_t; 1286 enum blockCount = 2; 1287 enum n = blockCount * 8*Block.sizeof - 1; 1288 StaticBitArray!(n) x; 1289 static assert(x.blockCount == blockCount); 1290 1291 assert(x.indexOfFirstOne == n); 1292 x[n - 1] = true; 1293 assert(x.indexOfFirstOne == x.length - 1); 1294 x[n - 2] = true; 1295 assert(x.indexOfFirstOne == x.length - 2); 1296 1297 x[n/2 + 1] = true; 1298 assert(x.indexOfFirstOne == x.length/2 + 1); 1299 x[n/2] = true; 1300 assert(x.indexOfFirstOne == x.length/2); 1301 x[n/2 - 1] = true; 1302 assert(x.indexOfFirstOne == x.length/2 - 1); 1303 1304 x[0] = true; 1305 assert(x.indexOfFirstOne == 0); 1306 assert(x[0]); 1307 assert(!x[1]); 1308 1309 x[1] = true; 1310 assert(x[1]); 1311 1312 x[1] = false; 1313 assert(!x[1]); 1314 } 1315 1316 /// Test opSliceAssign. 1317 @safe pure nothrow @nogc unittest 1318 { 1319 alias Block = size_t; 1320 enum blockCount = 2; 1321 enum n = blockCount * 8*Block.sizeof - 1; 1322 1323 StaticBitArray!(n) x; 1324 assert(x.countOnes == 0); 1325 1326 x[] = true; 1327 assert(x.countOnes == n); 1328 1329 x[] = false; 1330 assert(x.countOnes == 0); 1331 } 1332 1333 version(unittest) 1334 { 1335 import nxt.array_help : s; 1336 }