View mode: basic / threaded / horizontal-split · Log in · Help
June 08, 2012
const version for foreach/opApply
Hi,

trying to traverse the entries of a std.bitmanip.BitArray I stumbled
upon the following problem:

The original code is as follows:

int opApply(scope int delegate(ref bool) dg)
{
 int result;
 for (size_t i = 0; i < len; i++)
 {
   bool b = opIndex(i);
   result = dg(b);
   this[i] = b;
   if (result)
     break;
 }
 return result;
}

In case I want to accept const(BitArray) objects, it shall look like the
following (maybe using "ref const(bool)" for the delegate parameter?):

int opApply(scope int delegate(bool) dg) const
{
 int result;
 for (size_t i = 0; i < len; i++)
 {
   bool b = opIndex(i);
   result = dg(b);
   if (result)
     break;
 }
 return result;
}

Can one glue both things together into a single routine (using inout
magic or whatever)?

Best regards,

Matthias Walter
June 08, 2012
Re: const version for foreach/opApply
On Friday, 8 June 2012 at 16:33:28 UTC, Matthias Walter wrote:
> Hi,
>
> trying to traverse the entries of a std.bitmanip.BitArray I 
> stumbled upon the following problem:
>
> In case I want to accept const(BitArray) objects, it shall look 
> like the following (maybe using "ref const(bool)" for the 
> delegate parameter?):
>
> int opApply(scope int delegate(bool) dg) const

>
> Can one glue both things together into a single routine (using 
> inout magic or whatever)?

 I want to say you can't, because ref bool. If you ignore the 
reference, you don't need the non-const version (I think).

 I am currently working on BitArray updates, and it is 
const/immutable friendly according to as many tests as I could 
come up with for valid usage; This has taught me a lot on using 
templates, traits, constraints and how inout actually works. I 
haven't tried for a bit but I can try once more to send my code 
to GitHub, then you can give it a try.
June 09, 2012
Re: const version for foreach/opApply
On 2012-06-08 22:47, Era Scarecrow wrote:
> On Friday, 8 June 2012 at 16:33:28 UTC, Matthias Walter wrote:
>> Hi,
>>
>> trying to traverse the entries of a std.bitmanip.BitArray I stumbled
>> upon the following problem:
>>
>> In case I want to accept const(BitArray) objects, it shall look like
>> the following (maybe using "ref const(bool)" for the delegate
>> parameter?):
>>
>> int opApply(scope int delegate(bool) dg) const
> 
>>
>> Can one glue both things together into a single routine (using inout
>> magic or whatever)?
> 
>  I want to say you can't, because ref bool. If you ignore the reference,
> you don't need the non-const version (I think).
> 
>  I am currently working on BitArray updates, and it is const/immutable
> friendly according to as many tests as I could come up with for valid
> usage; This has taught me a lot on using templates, traits, constraints
> and how inout actually works. I haven't tried for a bit but I can try
> once more to send my code to GitHub, then you can give it a try.

First, thank you for your answer. I've already made some tiny
modifications in order to make BitArray work for my purposes:

https://github.com/xammy/phobos/commit/eb46d99217f2bf1e6d173964e2954248b08146d6

If you plan to create pull requests for your changes - please consider
my changes as well. When do you expect to finish, i.e., create a pull
request for phobos?
June 09, 2012
Re: const version for foreach/opApply
On Saturday, 9 June 2012 at 10:09:25 UTC, Matthias Walter wrote:
> First, thank you for your answer. I've already made some tiny 
> modifications in order to make BitArray work for my purposes:
>
> https://github.com/xammy/phobos/commit/eb46d99217f2bf1e6d173964e2954248b08146d6
>
> If you plan to create pull requests for your changes - please 
> consider my changes as well. When do you expect to finish, 
> I.e., create a pull request for phobos?

 Curious... Almost all of the changes you proposed I've already 
added in my version, the toHash is the only one missing and I 
don't know if I can work that very well. The new version is going 
to include 'slice-like' features, which is mostly a couple extra 
numbers specifying the offset in bits from the beginning to the 
end; The problem with that is hashing would have a huge speed 
drop.

 I'm adding an 'realign' function that handles those cases, but 
the downside is shared slices where you would want to make 
changes may or may not work. Caching the result would also be 
useful... Hmmm...

 I don't suppose you have a toHash where I can enter the odd bits 
and then also bulk ones and have the hash return the same could 
you? I can see xor easily having this type of effect...

 Anyways, here's some things I can do so far; Got a few 
improvements left to do, but not many. (const & immutable 
friendly of course :) )

--

const BitArray ba = BitArray([1,1,0,0,1]);
const BitArray slice = ba[1 .. ba.length];
BitArray m = slice.dup;
immutable BitArray im = slice.idup;

assert(slice == ba[1 .. ba.length]);
assert(slice == [1,0,0,1]);
assert(slice == m);
assert(slice == im);

assert(slice.isCompact);
writeln("GC not used");
June 11, 2012
Re: const version for foreach/opApply
On 06/10/2012 12:30 AM, Era Scarecrow wrote:
> On Saturday, 9 June 2012 at 10:09:25 UTC, Matthias Walter wrote:
>> First, thank you for your answer. I've already made some tiny
>> modifications in order to make BitArray work for my purposes:
>>
>> https://github.com/xammy/phobos/commit/eb46d99217f2bf1e6d173964e2954248b08146d6
>>
>>
>> If you plan to create pull requests for your changes - please consider
>> my changes as well. When do you expect to finish, I.e., create a pull
>> request for phobos?
> 
>  Curious... Almost all of the changes you proposed I've already added in
> my version, the toHash is the only one missing and I don't know if I can
> work that very well. The new version is going to include 'slice-like'
> features, which is mostly a couple extra numbers specifying the offset
> in bits from the beginning to the end; The problem with that is hashing
> would have a huge speed drop.
> 
>  I'm adding an 'realign' function that handles those cases, but the
> downside is shared slices where you would want to make changes may or
> may not work. Caching the result would also be useful... Hmmm...
> 
>  I don't suppose you have a toHash where I can enter the odd bits and
> then also bulk ones and have the hash return the same could you? I can

I see the problem. I don't know whether my hash function is a good one -
I just needed it to make AAs work with BitArray as a key type.

But the question is interesting. Finding a good hash function for bit
arrays which is invariant under realignment.

> see xor easily having this type of effect...
> 
>  Anyways, here's some things I can do so far; Got a few improvements
> left to do, but not many. (const & immutable friendly of course :) )
> 
> -- 
> 
> const BitArray ba = BitArray([1,1,0,0,1]);
> const BitArray slice = ba[1 .. ba.length];
> BitArray m = slice.dup;
> immutable BitArray im = slice.idup;
> 
> assert(slice == ba[1 .. ba.length]);
> assert(slice == [1,0,0,1]);
> assert(slice == m);
> assert(slice == im);
> 
> assert(slice.isCompact);
> writeln("GC not used");
> 

Looks interesting!
June 25, 2012
Re: const version for foreach/opApply
On Fri, 08 Jun 2012 12:33:20 -0400, Matthias Walter  
<xammy@xammy.homelinux.net> wrote:

> Hi,
>
> trying to traverse the entries of a std.bitmanip.BitArray I stumbled
> upon the following problem:
>
> The original code is as follows:
>
> int opApply(scope int delegate(ref bool) dg)
> {
>   int result;
>   for (size_t i = 0; i < len; i++)
>   {
>     bool b = opIndex(i);
>     result = dg(b);
>     this[i] = b;
>     if (result)
>       break;
>   }
>   return result;
> }
>
> In case I want to accept const(BitArray) objects, it shall look like the
> following (maybe using "ref const(bool)" for the delegate parameter?):
>
> int opApply(scope int delegate(bool) dg) const
> {
>   int result;
>   for (size_t i = 0; i < len; i++)
>   {
>     bool b = opIndex(i);
>     result = dg(b);
>     if (result)
>       break;
>   }
>   return result;
> }
>
> Can one glue both things together into a single routine (using inout
> magic or whatever)?

Not currently, because we have an issue of inout having two different  
meanings.

When a function's parameters or return values are adorned with inout,  
inout becomes sort of a wildcard.

When inside a function, however, inout turns into a restrictive form of  
const.

But what happens with a delegate parameter that *takes* an inout  
parameter?  For example:

int opApply(scope int delegate(ref inout(bool)) dg) inout

Is inout(bool) a wildcard for the delegate?  Or is part of the inout  
wildcard of the entire function?  Inside opApply, should it be the  
restrictive const type?

Currently, it is a wildcard for the delegate, and so it doesn't really  
help, once you go into opApply, you can't temporarily remove the inout  
type.

Note that for your particular instance I'd *recommend* two different  
versions, since the const version can be vastly optimized (passing a bool  
by value vs. by reference is much more efficient, and then there is no  
need to re-store the value after the delegate).

There are quite a few ideas being floated around as to how to make inout  
work for opApply, but for now, you should avoid it.

-Steve
Top | Discussion index | About this forum | D home