phobos commit, revision 1566


user: rsinfu

msg:
Fixed bugzilla 3876: std.range.Take back/popBack methods don't work correctly.
Thanks to Philippe Sigaud for the proposed solution.  It was helpful.

The former implementation simply used input.back for Take.back.  It didn't work if input.length was larger than maxAvailable.  For example:
  input = [ 1, 2, 3, 4, 5 ]
  s = take(input, 3)            // [ 1, 2, 3 ]
  s.back == input.back == 5     // wrong!

Take must pop all the excess elements from the input ([4,5] in the above example) to provide correct back element.  This change makes it to do so if input is purely bidirectional.  (random access is used instead if possible.)

- Added Take.opSlice
- Added some enforcement error messages

http://www.dsource.org/projects/phobos/changeset/1566

Typo: "Attenpting" (at least two places)

I think popBack for bidirectional ranges is broken. Consider I have a range of 1000 elements and I take 5 of them. Then popBack would have to back off 996 elements. That is not what your code is doing, and it would not satisfy the complexity requirements of popBack.

Please keep the popBack code only for random-access ranges.


Thanks,

Andrei

On 05/29/2010 08:44 AM, dsource.org wrote:
> phobos commit, revision 1566
>
>
> user: rsinfu
>
> msg:
> Fixed bugzilla 3876: std.range.Take back/popBack methods don't work correctly.
> Thanks to Philippe Sigaud for the proposed solution.  It was helpful.
>
> The former implementation simply used input.back for Take.back.  It didn't work if input.length was larger than maxAvailable.  For example:
>    input = [ 1, 2, 3, 4, 5 ]
>    s = take(input, 3)            // [ 1, 2, 3 ]
>    s.back == input.back == 5     // wrong!
>
> Take must pop all the excess elements from the input ([4,5] in the above example) to provide correct back element.  This change makes it to do so if input is purely bidirectional.  (random access is used instead if possible.)
>
> - Added Take.opSlice
> - Added some enforcement error messages
>
> http://www.dsource.org/projects/phobos/changeset/1566
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

Actually I was looking in the wrong place. The problem is this constructor:

	1214        this(R input, size_t maxAvailable)
  	1215	    {
  	1216	        static if (backByBack)
  	1217	        {
  	1218	            while (input.length > maxAvailable)
  	1219	                input.popBack;
  	1220	        }
  	1221	        _input = input;
  	1222	        _maxAvailable = maxAvailable;
  	1223	    }

This constructor is O(n), which is unacceptable. The whole backByBack logic must be erased.


Andrei

On 05/29/2010 08:44 AM, dsource.org wrote:
> phobos commit, revision 1566
>
>
> user: rsinfu
>
> msg:
> Fixed bugzilla 3876: std.range.Take back/popBack methods don't work correctly.
> Thanks to Philippe Sigaud for the proposed solution.  It was helpful.
>
> The former implementation simply used input.back for Take.back.  It didn't work if input.length was larger than maxAvailable.  For example:
>    input = [ 1, 2, 3, 4, 5 ]
>    s = take(input, 3)            // [ 1, 2, 3 ]
>    s.back == input.back == 5     // wrong!
>
> Take must pop all the excess elements from the input ([4,5] in the above example) to provide correct back element.  This change makes it to do so if input is purely bidirectional.  (random access is used instead if possible.)
>
> - Added Take.opSlice
> - Added some enforcement error messages
>
> http://www.dsource.org/projects/phobos/changeset/1566
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

Arguably, Take should never support back and popBack.  If you have a random access range, why wouldn't you just do r[0..3]?

-Steve




----- Original Message ----
> From: Andrei Alexandrescu <andrei at erdani.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Cc: dsource.org <noreply at dsource.org>
> Sent: Sat, May 29, 2010 9:54:58 AM
> Subject: Re: [phobos] phobos commit, revision 1566
> 
> Typo: "Attenpting" (at least two places)

I think popBack for
> bidirectional ranges is broken. Consider I have a
range of 1000 elements and
> I take 5 of them. Then popBack would have to
back off 996 elements. That is
> not what your code is doing, and it would
not satisfy the complexity
> requirements of popBack.

Please keep the popBack code only for
> random-access ranges.


Thanks,

Andrei

On 05/29/2010
> 08:44 AM, dsource.org
> wrote:
> phobos commit, revision 1566
>
>
> user: rsinfu
>
> msg:
> Fixed bugzilla 3876: std.range.Take
> back/popBack methods don't work correctly.
> Thanks to Philippe Sigaud for
> the proposed solution.  It was helpful.
>
> The former
> implementation simply used input.back for Take.back.  It didn't work if
> input.length was larger than maxAvailable.  For example:
> 
>   input = [ 1, 2, 3, 4, 5 ]
>    s = take(input, 3)
>           // [ 1, 2, 3 ]
>    s.back ==
> input.back == 5     // wrong!
>
> Take must pop all the excess elements from the input ([4,5] in the above example) to provide correct back element.  This change makes it to do so if input is purely bidirectional.  (random access is used instead if possible.)
>
> - Added Take.opSlice
> - Added some enforcement
> error messages
>
> 
> http://www.dsource.org/projects/phobos/changeset/1566
>
> 
> _______________________________________________
> phobos mailing
> list
> 
> href="mailto:phobos at puremagic.com">phobos at puremagic.com
> 
> http://lists.puremagic.com/mailman/listinfo/phobos
_______________________________________________
phobos
> mailing list

> href="mailto:phobos at puremagic.com">phobos at puremagic.com

> href="http://lists.puremagic.com/mailman/listinfo/phobos" target=_blank
> >http://lists.puremagic.com/mailman/listinfo/phobos

Andrei Alexandrescu <andrei at erdani.com> wrote:
> Actually I was looking in the wrong place. The problem is this constructor:
> 
> 	1214        this(R input, size_t maxAvailable)
>   	1215	    {
>   	1216	        static if (backByBack)
>   	1217	        {
>   	1218	            while (input.length > maxAvailable)
>   	1219	                input.popBack;
>   	1220	        }
>   	1221	        _input = input;
>   	1222	        _maxAvailable = maxAvailable;
>   	1223	    }
> 
> This constructor is O(n), which is unacceptable. The whole backByBack logic must be erased.
> 

Agreed.  Actually I tested the code with a 10,000,000-elements range and experienced 'it'.  backByBack was just for a backward compatibility. Now I erased it from the svn.


Shin

I think it's ok for uniformity's sake.

Andrei

On 05/29/2010 09:17 AM, Steve Schveighoffer wrote:
> Arguably, Take should never support back and popBack.  If you have a random access range, why wouldn't you just do r[0..3]?
>
> -Steve
>
>
>
>
> ----- Original Message ----
>> From: Andrei Alexandrescu<andrei at erdani.com>
>> To: Discuss the phobos library for D<phobos at puremagic.com>
>> Cc: dsource.org<noreply at dsource.org>
>> Sent: Sat, May 29, 2010 9:54:58 AM
>> Subject: Re: [phobos] phobos commit, revision 1566
>>
>> Typo: "Attenpting" (at least two places)
>
> I think popBack for
>> bidirectional ranges is broken. Consider I have a
> range of 1000 elements and
>> I take 5 of them. Then popBack would have to
> back off 996 elements. That is
>> not what your code is doing, and it would
> not satisfy the complexity
>> requirements of popBack.
>
> Please keep the popBack code only for
>> random-access ranges.
>
>
> Thanks,
>
> Andrei
>
> On 05/29/2010
>> 08:44 AM, dsource.org
>> wrote:
>> phobos commit, revision 1566
>>
>>
>> user:
>> rsinfu
>>
>> msg:
>> Fixed bugzilla 3876: std.range.Take
>> back/popBack methods don't work correctly.
>> Thanks to Philippe Sigaud for
>> the proposed solution.  It was helpful.
>>
>> The former
>> implementation simply used input.back for Take.back.  It didn't work if
>> input.length was larger than maxAvailable.  For example:
>>
>>    input = [ 1, 2, 3, 4, 5 ]
>>     s = take(input, 3)
>>            // [ 1, 2, 3 ]
>>     s.back ==
>> input.back == 5     // wrong!
>>
>> Take must pop all the
>> excess elements from the input ([4,5] in the above example) to provide correct
>> back element.  This change makes it to do so if input is purely
>> bidirectional.  (random access is used instead if
>> possible.)
>>
>> - Added Take.opSlice
>> - Added some enforcement
>> error messages
>>
>>
>> http://www.dsource.org/projects/phobos/changeset/1566
>>
>>
>> _______________________________________________
>> phobos mailing
>> list
>>
>> href="mailto:phobos at puremagic.com">phobos at puremagic.com
>>
>> http://lists.puremagic.com/mailman/listinfo/phobos
> _______________________________________________
> phobos
>> mailing list
>
>> href="mailto:phobos at puremagic.com">phobos at puremagic.com
>
>> href="http://lists.puremagic.com/mailman/listinfo/phobos" target=_blank
>>> http://lists.puremagic.com/mailman/listinfo/phobos
>
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

On Sat, May 29, 2010 at 15:54, Andrei Alexandrescu <andrei at erdani.com>wrote:

> Typo: "Attenpting" (at least two places)
>
> I think popBack for bidirectional ranges is broken. Consider I have a range of 1000 elements and I take 5 of them. Then popBack would have to back off 996 elements. That is not what your code is doing, and it would not satisfy the complexity requirements of popBack.
>
> Please keep the popBack code only for random-access ranges.
>
>
> Thanks,
>
> Andrei
>
>
Yes, I think that's why in the bug report I posted something that defined
back/popBack only for bidir ranges even though it was an
'overspecification'.
AKAIK, there is no clean way to define them otherwise.

 Steve:
> Arguably, Take should never support back and popBack.
> If you have a random access range, why wouldn't you just do r[0..3]?

Because your range may not have opSlice defined. And is such a slice always lazy? The difficulty in std.range/algo is to keep them lazy as much as possible. Eager versions of these functions are easy to do (and could well be part of std.array or std.algo.eager)

I *think* at some time I had a version of take that changed if the range has slicing and returned just r[0..n]. But I dropped it not long afterwards, maybe because it caused too much headache with the changing type (R or Take!R), even hiding it in a template.

Anyway, the idea was just to extend map/filter/take and such as much as
cleanly possible (see bugs #3871 and #3872), to have them play nice when
composed.
map particularly cries out to have opIndex/back/popBack/opSlice defined when
possible. It a workhorse, used in many range transformation.

Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100529/a9fd2087/attachment.html>

On 05/29/2010 02:51 PM, Philippe Sigaud wrote:
>   Steve:
>  > Arguably, Take should never support back and popBack.
>  > If you have a random access range, why wouldn't you just do r[0..3]?
>
> Because your range may not have opSlice defined. And is such a slice always lazy?

I think the correct answer is that with take(r, 5) you take maximum 5 elements from any range (more general), whereas with r[0 .. 5] you take exactly 5 elements from a range defining opSlice (most often, random access) - which is a more specialized function.

There's a tacit rule that has r.opSlice(a, b) return the same type as r itself.

I'm not sure if take does that already, but it should simply morph into opSlice() if opSlice() is available. No need to use another layer when opSlice does what you need.


Andrei

On Sat, May 29, 2010 at 23:17, Andrei Alexandrescu <andrei at erdani.com>wrote:

There's a tacit rule that has r.opSlice(a, b) return the same type as r
> itself.
>
> I'm not sure if take does that already, but it should simply morph into
> opSlice() if opSlice() is available. No need to use another layer when
> opSlice does what you need.
>

No, it does not do that already. OK, I'm a pain, but what if the range does not know its length? How do you know if r[0..n] is OK?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100530/4a6bfb2b/attachment-0001.html>

On 05/30/2010 01:39 AM, Philippe Sigaud wrote:
> On Sat, May 29, 2010 at 23:17, Andrei Alexandrescu <andrei at erdani.com <mailto:andrei at erdani.com>> wrote:
>
>     There's a tacit rule that has r.opSlice(a, b) return the same type
>     as r itself.
>
>     I'm not sure if take does that already, but it should simply morph
>     into opSlice() if opSlice() is available. No need to use another
>     layer when opSlice does what you need.
>
>
> No, it does not do that already. OK, I'm a pain, but what if the range does not know its length? How do you know if r[0..n] is OK?

Just like every other range in std.range, you support various primitives depending on what your wrapped range supports. Per your question, in this case, if the range doesn't know its length but does support r[0 .. n], you conservatively wrap it with Take.

But I have to say that would be a pretty bizarre range.


Andrei