Comment #0 by bearophile_hugs — 2014-03-26T05:54:48Z
I suggest to add to Phobos a simple data structure similar to BitArray but implemented with a fixed-size array:
struct StaticBitArray(uint N) {
alias T = size_t;
enum size_t bpc = T.sizeof * 8;
T[(N + bpc - 1) / bpc] data;
static assert(N <= data.sizeof * 8);
alias data this;
alias length = N;
T isSet(in size_t i) const pure nothrow {
// Pre-condition here.
immutable size_t offset = i / bpc;
immutable T mask = (cast(T)1) << (i % bpc);
return data[offset] & mask;
}
void set(in size_t i) pure nothrow {
// Pre-condition here.
immutable size_t offset = i / bpc;
immutable T mask = (cast(T)1) << (i % bpc);
data[offset] |= mask;
}
void reset(in size_t i) pure nothrow {
// Pre-condition here.
immutable size_t offset = i / bpc;
immutable T mask = (cast(T)1) << (i % bpc);
if ((data[offset] & mask) != 0)
data[offset] = data[offset] ^ mask;
}
void setAll() const pure nothrow {
//data[] = T.max; // Currently not efficient if N is small.
foreach (immutable i; 0 .. data.length)
data[i] = T.max;
}
void reseAll() const pure nothrow {
//data[i] = 0; // Currently not efficient if N is small.
foreach (immutable i; 0 .. data.length)
data[i] = 0;
}
// Some more methods here.
}
I have used set/reset methods because they are more efficient than opIndexAssign when the compiler is not inlining much.
The advantages of this data structure are similar to the advantages of fixed-size arrays compared to dynamic arrays (less indirection, less memory, can be stored in-place simply and copied simply, simpler code and smaller resulting binary, etc).
Comment #1 by robert.schadek — 2024-12-01T16:20:43Z