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

Subject: Re: [boost] Formal Review: Boost.RangeEx - missing algorithms
From: Neil Groves (neil_at_[hidden])
Date: 2009-02-22 06:14:58

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!

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.

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.

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.

>
> There are surely hidden reasons to don't include some of them.
>
> I have a particular need, create a partition view of a range in
> n-sub-ranges
>
> Currently I need to do for two partitions.
>
>        boost::sub_range<Range> p0(boost::begin(range),
> boost::begin(range)+(size/2));
>        boost::sub_range<Range> p1(boost::begin(range)+(size/2)+1,
> boost::end(range));
>
> and for thre
>        boost::sub_range<Range> p0(boost::begin(range),
> boost::begin(range)+(size/3));
>        boost::sub_range<Range> p1(boost::begin(range)+(size/3)+1,
> boost::begin(range)+2*(size/3));
>        boost::sub_range<Range> p2(boost::begin(range)+2*(size/3)+1,
> boost::end(range));
>
> I have created a static partition class as follows:
>
> template <typename Range, std::size_t Parts>
> class partition
> {
> public:
>    boost::array<boost::sub_range<Range>,Parts> parts;
>    partition(boost::sub_range<Range>& range)
>    {
>        std::size_t size = boost::size(range);
>        parts[0]=boost::sub_range<Range>(boost::begin(range),
> boost::begin(range)+(size/Parts));
>        for (std::size_t i=1; i< Parts-1; ++i) {
>
>  parts[i]=boost::sub_range<Range>(boost::begin(range)+i*(size/Parts)+1,
> boost::begin(range)+(i+1)*(size/Parts)+1);
>        }
>
>  parts[Parts-1]=boost::sub_range<Range>(boost::begin(range)+(Parts-1)*(size/Parts)+1,
> boost::end(range));
>    }
> };
>

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.

>
> Best,
> Vicente
>

Best Wishes,
Neil Groves

>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>