BitArray/BitFields - Resumed and polishing

[Era Scarecrow]

On Thursday, 3 January 2013 at 21:15:19 UTC, Dmitry Olshansky 
wrote:
> 04-Jan-2013 00:11, Era Scarecrow wrote:

> 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*.

  So the slice is a non-allocating view of data some data. I can 
see adding more limitations for that then.

>> 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.

  Only on the first iteration, unless you do a LOT of slicing & 
appending on non-compact blocks, but if you're appending to a 
slice in normal arrays it will dup it anyways (if it doesn't own 
the following memory) so the behavior doesn't really change.

>> 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.

  K, I'll likely re-work my multi-level huffman algorithmn and a 
LZW compression, although the LZW wouldn't make use of the more 
exotic features. Got half the LZW written, but I likely won't get 
this done for a few days.

>>> 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).

  Got a copy, in fact this is one of the first prints. I've likely 
read this book a half dozen times to get a full feel of the 
language (other than templates which I've learned elsewhere)

>> 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.

  That was the idea. A true value type with no hidden allocation. 
There are many cases for it, but I think having the BitArray 
which can allocate has a larger audience than a fixed size. Won't 
know for sure though, maybe it's the other way around.