simple_static_bitarray source code

1 /**
2  * Static bit array container for internal usage.
3  */
4 module simple_static_bitarray;
5 
6 @safe:
7 
8 alias DefaultBlock = size_t;    ///< Default block type.
9 
10 @safe struct StaticBitArray(uint capacity)
11 {
12     pure nothrow @nogc:
13     import core.bitop : bt, bts, btr;
14 
15     /** Number of bits. */
16     enum length = capacity;
17 
18     alias Block = DefaultBlock; ///< Block type.
19 
20     /** Number of bits per `Block`. */
21     enum bitsPerBlock = 8*Block.sizeof;
22 
23     /** Number of blocks of type `Block`. */
24     enum blockCount = (capacity + (bitsPerBlock-1)) / bitsPerBlock;
25 
26     /** Reset all bits (to zero). */
27     void reset()
28     {
29         version(D_Coverage) {} else pragma(inline, true);
30         _blocks[] = 0;          // TODO: is this the fastest way?
31     }
32 
33     /** Gets the $(D idx)'th bit. */
34     bool opIndex(size_t idx) const @trusted
35     in(idx < length)            // TODO: nothrow or not?
36     {
37         version(D_Coverage) {} else pragma(inline, true);
38         return cast(bool)bt(_blocks.ptr, idx);
39     }
40 
41     /** Sets the $(D idx)'th bit. */
42     bool opIndexAssign(bool b, size_t idx) @trusted
43     in(idx < length)            // TODO: nothrow or not?
44     {
45         version(D_Coverage) {} else pragma(inline, true);
46         if (b)
47             bts(_blocks.ptr, cast(size_t)idx);
48         else
49             btr(_blocks.ptr, cast(size_t)idx);
50         return b;
51     }
52 
53     /** Find index of first cleared (zero) bit or `typeof(return).max` if no bit set.
54      *
55      * Optimized for zeros-sparsity.
56      */
57     size_t indexOfFirstZero()() const
58     {
59         import nxt.bitarray_algorithm;
60         enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0;
61         return nxt.bitarray_algorithm.indexOfFirstZero!(const(Block)[blockCount],
62                                                         blockAlignedLength)(_blocks, length);
63     }
64 
65     /** Find index of first set (one) bit or `typeof(return).max` if no bit set.
66      *
67      * Optimized for ones-sparsity.
68      */
69     size_t indexOfFirstOne()() const
70     {
71         import nxt.bitarray_algorithm;
72         enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0;
73         return nxt.bitarray_algorithm.indexOfFirstOne!(const(Block)[blockCount],
74                                                        blockAlignedLength)(_blocks, length);
75     }
76 
77     private Block[blockCount] _blocks;
78 }
79 
80 ///
81 @trusted pure unittest
82 {
83     enum blockCount = 2;
84     enum length = blockCount * 8*DefaultBlock.sizeof - 1; // 2 blocks minus one
85 
86     StaticBitArray!(length) x;
87     static assert(x.blockCount == blockCount);
88 
89     // import std.exception: assertThrown;
90     // import core.exception : AssertError;
91     // assertThrown!AssertError(x[length] = false);
92 
93     x[length/2 - 1] = true;
94     assert(x[length/2 - 1]);
95 
96     x[length/2 - 1] = false;
97     assert(!x[length/2 - 1]);
98 
99     x[length - 1] = true;
100     assert(x[length - 1]);
101 
102     x[length - 1] = false;
103     assert(!x[length - 1]);
104 }
105 
106 /// Test `indexOfFirstZero` for multi set zeros.
107 @safe pure nothrow @nogc unittest
108 {
109     static void test(bool blockAlignedLength)()
110     {
111         static if (blockAlignedLength)
112             const n = 2 * 8*DefaultBlock.sizeof;
113         else
114             const n = 2 * 8*DefaultBlock.sizeof + 1;
115         alias BA = StaticBitArray!(n);
116 
117         auto a = BA();
118 
119         a[0] = false;
120         a[BA.bitsPerBlock/2] = false;
121         a[BA.bitsPerBlock - 1] = false;
122         assert(a.indexOfFirstZero == 0);
123     }
124     test!(false)();
125     test!(true)();
126 }
127 
128 /// Test `indexOfFirstOne` for multi set ones.
129 @safe pure nothrow @nogc unittest
130 {
131     static void test(bool blockAlignedLength)()
132     {
133         static if (blockAlignedLength)
134             const n = 2 * 8*Block.sizeof;
135         else
136             const n = 2 * 8*DefaultBlock.sizeof + 1;
137         alias BA = StaticBitArray!(n);
138 
139         auto a = BA();
140 
141         a[0] = true;
142         a[BA.bitsPerBlock/2] = true;
143         a[BA.bitsPerBlock - 1] = true;
144         assert(a.indexOfFirstOne == 0);
145     }
146     test!(false)();
147 }