On Friday, 8 August 2014 at 23:57:17 UTC, H. S. Teoh via
Digitalmars-d wrote:
- SmallBitArray: fits inside a ulong, and has value semantics.
Behaves
like a ulong: minimal cost for passing it around, making
multiple
copies of it, etc.. Basically for juggling bits in a ulong.
Easy enough to make a struct that doesn't care, would be able to
foreach over it and do direct access as long as you don't have to
worry about where it starts/ends (the length). Just forcibly
convert a type to a small bitarray and it works... slicing and
other advanced features would be missing...
- StaticBitArray: a value type that fits inside n ulong's.
Appends only
work up to the max capacity of n ulong's. This one is mainly
for
people who need to manipulate bitmasks, perform bit
operations en
masse, etc.. Backed by an embedded static array, so it has
value
semantics, and you can pass it around, copy it, etc., without
worrying
about aliasing.
I remember starting something like this, it started to become a
template hell... And code bloat... I ended up deciding it was
simpler to have one type that allowed slicing as part of it's
design.
- DynamicBitArray: a reference type backed by the GC. This one
is for
people who are after something that behaves like D dynamic
arrays;
slicing is supported (by means of extra info about how many
bits at
the beginning/end of the array is actually part of an array,
so you
can slice it at arbitrary bit positions not aligned with word
boundaries), as is arbitrary appending, etc.. The emphasis
for this
one is memory efficiency (e.g. for people who need to store
massive
numbers of bools without wasting an entire byte per bool), at
the cost
of potentially slower copying / overhead of maintaining
start/end bit
indices, etc..
Obviously, these types are closely related, so they will
probably share quite a good number of common algorithms. So
potentially they can be implemented as a core of common
functions that can work on all 3 BitArray types, with a few
customized methods for each type.
So UFCS rather than be template functions inside of template
structs... that would simplify separating the storage vs shared
algorithm/design. Yeah i think i can do that... And hopefully
satisfy all three basic types.
So to decide how it identifies these, what makes up a BitArray.
For simplicity probably readable fields, being bitslicestart and
bitslicelength. Finally a flag that says if it's dynamic or not.
bitslice_isdynamic... Probably those three things (Unless someone
else has a better idea).
After that what operators do they all support... Definitely
basic opIndex get/set. And being able to foreach over them, or a
wrapper to make it an input/output range.
If anyone wants to help with the exact details for what the
requirements of all the BitArray types are, and a good list of
what kind of unittests we should use to verify it's usage and
correctness then i'm all ears.
