Re: [boost] Formal Review: Boost.RangeEx - missing algorithms

Subject: Re: [boost] Formal Review: Boost.RangeEx - missing algorithms
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-02-22 07:13:56

----- Original Message ----- 
From: "Neil Groves" <neil_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Sunday, February 22, 2009 12:14 PM
Subject: Re: [boost] Formal Review: Boost.RangeEx - missing algorithms

> 
> Dear Vicente,
> 
> I appreciate you taking the time to review Boost.RangeEx.
> 
> On Sat, Feb 21, 2009 at 5:58 PM, vicente.botet <vicente.botet_at_[hidden]>wrote:
> 
>>
>> ----- Original Message -----
>> From: "Thorsten Ottosen" <thorsten.ottosen_at_[hidden]>
>> To: <boost_at_[hidden]>; <boost-users_at_[hidden]>; <
>> boost-announce_at_[hidden]>
>> Sent: Friday, February 20, 2009 10:03 AM
>> Subject: [boost] Formal Review: Boost.RangeEx
>>
>>
>> >
>> > Dear Developers and Users,
>> >
>> > It's my pleasure to announce that the review of Neil Groves' RangeEx
>> > library starts today and lasts until March 3, 2009.
>>
>> Hi,
>>
>> Excelent library Neil.
>>
>> I was wondering if the following SGI algorithms should't be included in the
>> library.
>>
>> count_if
>> search_n
>> copy_n
>> fill_n
>> generate_n
>> remove_copy
>> remove_copy_if
>> unique_copy
>> reverse_copy
>> rotate_copy
>> random_shuffle
>> random_sample
>> random_sample_n
>> partial_sort_copy
>> is_sorted
>> is_heap
>>
> 
> Many of these are deliberately missing, although I am inviting comments
> about this design decision. The rationale for ot including the _n and _if
> versions is covered under the adaptor documentation. It is probably
> necessary to add an obvious link in the algorithm section. The algorithm
> section is where people are going to go to find out about the algorithms I
> suppose! Ooops!

Oh, I read the adaptors section some time ago, and I have forgotten. Yes a link will be welcome.

> count_if can be achieved using boost::count( input | filtered(pred) ) and
> similar arrangements work for the other _if algorithms with the exception of
> remove_copy_if.
> 
> remove_copy_if can be achieved by boost::copy( input | filtered(pred),
> output ), or preferably by the safer and quicker extension boost::push_back(
> output, input | filtered );
> The same applies to all _copy algorithms. The standard library
> implementation is more dangerous and less efficient, and requires algorithm
> developers to provide numerous additional overloads. This is fundamentally
> because the _if and the _copy are in essence orthogonal operations that can
> benefit from being factored out. This leaves a more consistent, safer
> interface and better performance, while reducing the development overhead of
> those providing algorithms that are intended to work with ranges. The
> algorithms supplied, I hope, are just the beginning.

May be it will be godd to add the equivalences. The user can always include them in their application if they found useful.
 
> The _n operations are replaced if the input is a model of the
> RandomAccessRangeConcept with boost::copy( output, input | sliced(0, n) )
> for example, but on reflection this can and must be improved before release.
> If I simply add a first_n adaptor then we can replace all _n algorithms with
> a superior adaptor for all valid ranges. Hence I propose to add something
> that would allow:
> boost::copy( output, input | first_n(n) );
>
> I am pleased that you made me justify dropping the _n versions, because
> frankly my solution is currently insufficient to be a perfect substition.

Yes, somthing like that should work, but what will be the difference between
first_n(n) and sliced(0, n)?

> As for is_sorted and is_heap, these seem like useful additions to the
> algorithm_ext.hpp.
> 
> And horror of horrors, the random_sample is missing due to no good
> justifiable reason what-so-ever. This I will address.

waiting for them.

>>
>> There are surely hidden reasons to don't include some of them.
>>
<snip>
 
> I definately like the idea of carefully adding partitioning that is
> compatible with Boost.Range. I need to revist posts and suggestions made by
> others on this list.
> IIRC Dr. Arnold Schodl had some interesting ideas, and partitioning is
> actively being worked on.
>
>> But a dynamic one would also be interesting. What do you think?
>>
> 
> The only comment I can make at this point is that it requires some
> investigation. There are others that have investigate partitioning in much
> more detail and I it would be silly for me to comment before studying their
> contributions. It appears to be something that can be extended and made
> compatible with range very easily without affecting the core. Hopefully I
> can still find enough time to make this happen before release.

Could you give me some pointers? 

I have just a last question, is there any difference between 
using directly a Range
    Range range;

using a sub_range
    boost::sub_range<Range> sub_rng(boost::begin(range), boost::end(range));

and using a sliced adaptor
    range | sliced(0, boost:size(range)) 
?

Thanks,
Vicente