BitArray/BitFields - Resumed and polishing

[Dmitry Olshansky]

04-Jan-2013 00:11, Era Scarecrow пишет:
> On Thursday, 3 January 2013 at 15:48:50 UTC, Dmitry Olshansky wrote:
>> 1/3/2013 2:20 PM, Era Scarecrow wrote:
>>> Suddenly it won't work and slicing is only a range and can only be
>>> used in foreach.
>>
>> No surprise here. Basically container != range over it. It all flows
>> from there. Range doesn't have append nor it owns any data.
>> About foreach see below. Yes, the BitArray container won't pass
>> hasSlicing trait, but it shouldn't as it's meant for ranges. (so in a
>> sense my comment about trying to mimic built-in array applies)
>>
>> And slice can have opIndex and opSlice being a random access range of
>> bool.
>
>   Hmmm.. shouldn't try to make it as close to an actual array as
> possible. I feel like I'm missing something very very simple to making
> it all correct.
>

[snip]
 >>
 >> Again I don't think there is a need to append to a slice. Create an
 >> array out of slice (or in fact any range of bool) then append.
 >
 >   I want to say you're wrong, I'm thinking heavily in the field where
 > you would be doing compression or encryption where random access and
 > appending could be needed at any step. I can see creating a simple table
 > of the compressed sequences (Say huffman), and then appending the slices
 > which then greatly simplifies the interface.

Appending a slice *to* BitArray is perfectly fine as in fact any range 
of bool (or bit if you like). Any array-like or string-like container 
has to support appending a range of element type (and insertion for that 
matter). The table you mention is then an array of BitArray that is 
sliced (getting a range) and these slices are appended to some other 
BitArray. BitArrays in this table could also be appended to just fine 
(so you construct sequences out of others easily).

The key point is that *appending a range to container* is fine (and 
idiomatic) and *slicing is O(1), fast and non-allocating*.

 >I can also see where if you
 > append to a slice it automatically making a new block of memory would be
 > useful as well, as you know you're going to start fresh.

Maybe but I can see it being a nasty surprise in a tight loop.

 > I can make a
 > short test set of functions and post them if you like, doing ranges &
 > slices otherwise might not allow such diversity (simplicity?) in the 
code.

Would be great to put them together as we have implementation details 
sorted out but have trouble with usage patterns.

>> There is an extra rule however, it is the following. If the object in
>> question is not a range and doesn't have opApply but has opSlice()
>> then it slices it first, then again it checks the 2 ways on this slice
>> - as range or opApply.
>
>   I didn't know that; I know it attempted a slice but not that the slice
> has to be a range. Likely that needs to be emphasized in the documentation.

That's pretty much how std.container tries to work. There is little 
documentation on the subject though, same note IRC is in TDPL book 
(highly recommend that one if you don't have it already).

[snip]

>>> I'm aware of the container version, and overall if it can just
>>> replace BitArray as it is, then we might consider only worrying about
>>> a compact version, at which point it would become a template... Might
>>> start seeing BitArray!1024  in places (or BitString!1024 ?).
>>
>> I'm not sure if it will gain that much to have templated fixed size
>> bit array over one that just has small optimization. Could be a lot
>> but somehow I don't expect much, that needs some measurement.
>
>   I agree, but if it's going to be a value type that's heavy on small
> string optimization with as little referencing as possible, then it has
> to know what size to depend on, since resizing beyond the max may not be
> an option if we take that part out.

I meant it's still resizing up to any point, just that it does dup's 
underlying array on copy (if not small, if small then postblit does 
nothing). It's questionable to dup on copy but the idea is that it won't 
be often.

If you mean to make type that doesn't resize beyond some maximum (so 
it's always "small") then indeed having fixed size as template parameter 
makes more sense.

-- 
Dmitry Olshansky