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. What is it? +++++++++++ The library provide two very useful extensions to the range library 1. Range-based algorithms. E.g. boost::sort( rng ); which is a convenient wrapper of instead of std::sort( boost::begin(rng), boost::end(rng) ); But the new interface also allows for more expressive code because (on the fly) composition of algorithms suddenly is possible. 2. Range adaptors. E.g. std::vector<int> vec = ...; boost::copy( vec | boost::adaptors::reversed, std::ostream_iterator<int>( std::cout ) ); where the expression "vec | boost::adaptors::reversed" wraps the iterators of the range on the left in reverse iterators. The library provides a wide range (no pun intended) of Range adaptors, and they are a powerful way to create ranges on the fly and pass them to algorithms. Getting the library +++++++++++++++++++ The library may be downloaded from http://www.cs.aau.dk/~nesotto/boost/range_ex.zip or from the Boost vault under "Algorithms". The docs may be browsed online here http://www.cs.aau.dk/~nesotto/boost/libs/range/ Please note that the documentation is integrated with the current Range ilbrary. Therefore the relevant sections for the review is http://www.cs.aau.dk/~nesotto/boost/libs/range/doc/adaptors.html and http://www.cs.aau.dk/~nesotto/boost/libs/range/doc/algorithms.html The code may be browsed here: http://www.cs.aau.dk/~nesotto/boost/boost/range/ Notice the library is header only (exception: the adaptor tokenized() depends on Boost.Regex). Writing a review ++++++++++++++++ If you feel this is an interesting library, then please submit your review to the developer list (preferably), or to the review manager. Here are some questions you might want to answer in your review: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick - reading? In-depth study? - Are you knowledgeable about the problem domain? And finally, every review should answer this question: - Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Special considerations ++++++++++++++++++++++ Various RangeEx like libraries have been implemented in the past. You might want to compare with those libraries when you form your oppinion: 1. John Torjo's range lib http://rangelib.synesis.com.au/libs/boost-rangelib-20040913.zip http://torjo.com/rangelib/index.html 2. Adobe's ASL libraries include range-based algorithms: http://stlab.adobe.com/group__algorithm.html I'm looking forward to your review. best regards Thorsten, Review Manager
----- Original Message ----- From: "Thorsten Ottosen" <thorsten.ottosen@dezide.com> To: <boost@lists.boost.org>; <boost-users@lists.boost.org>; <boost-announce@lists.boost.org> 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 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)); } }; But a dynamic one would also be interesting. What do you think? Best, Vicente
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@wanadoo.fr>wrote:
----- Original Message ----- From: "Thorsten Ottosen" <thorsten.ottosen@dezide.com> To: <boost@lists.boost.org>; <boost-users@lists.boost.org>; < boost-announce@lists.boost.org> 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
Neil Groves skrev:
Dear Vicente, e 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.
We should investigate all possiblites to partition the sequence [x1,...,xm] here. We might have | first_n(n) ~ sliced(0,n) ~ [x1,...,xn] | sliced(y,z) ~ [y,y+1...,z-1,z] | last_n(n) ~ sliced(m-n,n) ~ [x(m-n),...,xm] maybe this suggest a more intuitive name for sliced(), but I don't know. -Thorsten
----- Original Message ----- From: "Neil Groves" <neil@grovescomputing.com> To: <boost@lists.boost.org> 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@wanadoo.fr>wrote:
----- Original Message ----- From: "Thorsten Ottosen" <thorsten.ottosen@dezide.com> To: <boost@lists.boost.org>; <boost-users@lists.boost.org>; < boost-announce@lists.boost.org> 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
Dear Vicente, On Sun, Feb 22, 2009 at 12:13 PM, vicente.botet <vicente.botet@wanadoo.fr>wrote: <snip> </snip>
May be it will be godd to add the equivalences. The user can always include them in their application if they found useful.
I'm not sure about this issue. I really want to obtain feedback from as many people as possible. I understand the appeal of providing everything that is in <algorithm> but I dislike setting what is, in essence, a bad example of how to write algorithms. My personal preference is to drop the inferior technique, this will hopefully make it easy to do the right thing, and hard to do the wrong thing. I am, of course, open to feedback on this issue. Ultimately the library is for it's users.
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)?
The key difference is that while sliced works perfectly fine for RandomAccessRange's it does not work for SinglePassRange's. It is possible to make a first_n work for all valid Ranges. Hence I can't correctly state that I have currently provided the tools to make the _n versions of the algorithms always replacable with a superior alternative. I shall, because I want to get rid of them, I should have provided a better alternative first.
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)) ?
The idea is that the algorithm may be written without regard for what actual range is being used. There are reasons to have iterator_range, sub_range and special returns from the adaptors. I believe these are all documented, so I'm going to be cheeky and ask that you look in the documentation for sub_range. Indeed it is a core design goal that the user may provide free functions to allow other containers to work with the range library seamlessly. This indeed is exemplified by the code that allows ATL and MFC 'collections' to operate as ranges without requiring modification. The relevant documentation is here index.html -> reference -> extending the library. The use of anything that is a valid model of the appropriate Range Concept must work. It's a defect if it doesn't.
Thanks, Vicente
Best Wishes, Neil Groves
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
----- Original Message ----- From: "Neil Groves" <neil@grovescomputing.com> To: <boost@lists.boost.org> Sent: Sunday, February 22, 2009 3:11 PM Subject: Re: [boost] Formal Review: Boost.RangeEx - missing algorithms
Dear Vicente,
On Sun, Feb 22, 2009 at 12:13 PM, vicente.botet <vicente.botet@wanadoo.fr>wrote: <snip> </snip>
May be it will be godd to add the equivalences. The user can always include them in their application if they found useful.
I'm not sure about this issue. I really want to obtain feedback from as many people as possible. I understand the appeal of providing everything that is in <algorithm> but I dislike setting what is, in essence, a bad example of how to write algorithms. My personal preference is to drop the inferior technique, this will hopefully make it easy to do the right thing, and hard to do the wrong thing. I am, of course, open to feedback on this issue. Ultimately the library is for it's users.
It's OK. I will wait from feedback from others also.
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)?
The key difference is that while sliced works perfectly fine for RandomAccessRange's it does not work for SinglePassRange's. It is possible to make a first_n work for all valid Ranges. Hence I can't correctly state that I have currently provided the tools to make the _n versions of the algorithms always replacable with a superior alternative. I shall, because I want to get rid of them, I should have provided a better alternative first.
Ok, I see.
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 already found the thread in this ML, but I'm not sure we address the same partition concept. I need to reread it.
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)) ?
The idea is that the algorithm may be written without regard for what actual range is being used. There are reasons to have iterator_range, sub_range and special returns from the adaptors. I believe these are all documented, so I'm going to be cheeky and ask that you look in the documentation for sub_range.
Sorry, I was not enough explicit. My question was related to performances. So is there any performance difference between ... BTW, if I need to make a function that gets the i-th partition of a range divided on k-parts template <typename Range> ??? get_partition(Range& range, unsigned i, unsigned parts) { std::size_t size = boost::size(range); if (i==parts - 1) return range | sliced(boost::begin(range_)+i*(size/parts_), boost::end(range_)); else return range | sliced(boost::begin(range_)+i*(size/parts_), boost::begin(range_)+((i+1)*(size/parts_))-1); } Which will be the type of get_partition? Should this be done in another way?
Indeed it is a core design goal that the user may provide free functions to allow other containers to work with the range library seamlessly. This indeed is exemplified by the code that allows ATL and MFC 'collections' to operate as ranges without requiring modification. The relevant documentation is here index.html -> reference -> extending the library.
The use of anything that is a valid model of the appropriate Range Concept must work. It's a defect if it doesn't.
I'm not sure if my example is a counter-example. I'm trying to define a parallel_sort function taking a Range as parameter. I have started with template <typename Range> void parallel_sort(Range& range, unsigned cutoff=10000) { pool_type pool( boost::tp::poolsize( 2) ); x_sort fct( pool, cutoff); fct.execute(range); } class x_sort { private: pool_type & pool_; unsigned cutoff_; template <typename Range> void seq_( Range& range) { sort_fct()(range); } template <typename Range> void par_( Range& range) { unsigned size = boost::size(range); if ( size <= cutoff_) return seq_( range); else { boost::sub_range<Range> left(boost::begin(range), boost::begin(range)+(size/2)); boost::sub_range<Range> right(boost::begin(range)+(size/2)+1, boost::end(range)); task_type task(pool_.submit( boost::bind(& x_sort::par_<Range>, boost::ref( * this), boost::ref(left)))); this->par_(right); task.wait(); inplace_merge_fct()(range, boost::begin(range)+(size/2)); } } public: x_sort( pool_type & pool, unsigned cutoff) : pool_( pool), cutoff_( cutoff) {} template <typename Range> void execute( boost::sub_range<Range>& range) { par_( range); } }; The problem is that the instantiation of par_<Range> requests the instantiation of par_<boost::sub_range<Range>>, and ..., which fall in an recursive instantiation that do not finish. Should the types boost::sub_range<Range> and boost::sub_range<boost::sub_range<Range> > be convertibles? I have taken a workaround, create a sub_range before calling to the internal function execute. template <typename Range> void parallel_sort(Range& range, unsigned cutoff=10000) { pool_type pool( boost::tp::poolsize( 2) ); x_sort fct( pool, cutoff); boost::sub_range<Range> rng(range); fct.execute(range); } The internal templates have a boost::sub_range<Range> parameter instead of a Range, so the single tempalte instantiation is par_<boost::sub_range<Range> >. class x_sort { private: pool_type & pool_; unsigned cutoff_; template <typename Range> void seq_( boost::sub_range<Range>& range) { sort_fct()(range); } template <typename Range> void par_( boost::sub_range<Range>& range) { unsigned size = boost::size(range); if ( size <= cutoff_) return seq_( range); else { boost::sub_range<Range> left(boost::begin(range), boost::begin(range)+(size/2)); boost::sub_range<Range> right(boost::begin(range)+(size/2)+1, boost::end(range)); // fork a new sub-action t1 in pool task_type task(pool_.submit( boost::bind(& x_sort::par_<Range>, boost::ref( * this), boost::ref(left)))); this->par_(right); task.wait(); inplace_merge_fct()(range, boost::begin(range)+(size/2)); } } public: x_sort( pool_type & pool, unsigned cutoff) : pool_( pool), cutoff_( cutoff) {} template <typename Range> void execute( boost::sub_range<Range>& range) { par_( range); } }; Is this the correct way to use Range and sub_range? Best, Vicente
Dear Vincente, On Sun, Feb 22, 2009 at 3:08 PM, vicente.botet <vicente.botet@wanadoo.fr>wrote:
----- Original Message ----- From: "Neil Groves" <neil@grovescomputing.com> To: <boost@lists.boost.org> Sent: Sunday, February 22, 2009 3:11 PM Subject: Re: [boost] Formal Review: Boost.RangeEx - missing algorithms
Dear Vicente,
On Sun, Feb 22, 2009 at 12:13 PM, vicente.botet <
vicente.botet@wanadoo.fr>wrote:
<snip> </snip>
May be it will be godd to add the equivalences. The user can always
include
them in their application if they found useful.
I'm not sure about this issue. I really want to obtain feedback from as many people as possible. I understand the appeal of providing everything that is in <algorithm> but I dislike setting what is, in essence, a bad example of how to write algorithms. My personal preference is to drop the inferior technique, this will hopefully make it easy to do the right thing, and hard to do the wrong thing. I am, of course, open to feedback on this issue. Ultimately the library is for it's users.
It's OK. I will wait from feedback from others also.
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)?
The key difference is that while sliced works perfectly fine for RandomAccessRange's it does not work for SinglePassRange's. It is possible to make a first_n work for all valid Ranges. Hence I can't correctly state that I have currently provided the tools to make the _n versions of the algorithms always replacable with a superior alternative. I shall, because I want to get rid of them, I should have provided a better alternative first.
Ok, I see.
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 already found the thread in this ML, but I'm not sure we address the same partition concept. I need to reread it.
I do too!
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)) ?
The idea is that the algorithm may be written without regard for what actual range is being used. There are reasons to have iterator_range, sub_range and special returns from the adaptors. I believe these are all documented, so I'm going to be cheeky and ask that you look in the documentation for sub_range.
Sorry, I was not enough explicit. My question was related to performances. So is there any performance difference between ...
Actually having re-read my paragraph I state something I don't really mean. The user of the algorithm must be able to call it for any range that models a valid Range concept. In very few cases when implementing an algorithm you can benefit from using the sub_range as a tool to help build the algorithm. There is no performance difference between iterator_range, and sub_range to the best of my knowledge and belief. I have not yet measured so this is slightly speculative.
BTW, if I need to make a function that gets the i-th partition of a range divided on k-parts
template <typename Range> ??? get_partition(Range& range, unsigned i, unsigned parts) { std::size_t size = boost::size(range); if (i==parts - 1) return range | sliced(boost::begin(range_)+i*(size/parts_), boost::end(range_)); else return range | sliced(boost::begin(range_)+i*(size/parts_), boost::begin(range_)+((i+1)*(size/parts_))-1); }
Which will be the type of get_partition? Should this be done in another way?
I can't see any reason why you should not be able to do it this way. What this example shows is that I was wrong to state that the return type of adaptors did not need to be known. I will add the return type information into the documentation. The answer in this particular case is: iterator_range<typename range_iterator<Range>::type >
Indeed it is a core design goal that the user may provide free functions to allow other containers to work with the range library seamlessly. This indeed is exemplified by the code that allows ATL and MFC 'collections' to operate as ranges without requiring modification. The relevant documentation is here index.html -> reference -> extending the library.
The use of anything that is a valid model of the appropriate Range Concept must work. It's a defect if it doesn't.
I'm not sure if my example is a counter-example. I'm trying to define a parallel_sort function taking a Range as parameter. I have started with
template <typename Range> void parallel_sort(Range& range, unsigned cutoff=10000) { pool_type pool( boost::tp::poolsize( 2) ); x_sort fct( pool, cutoff); fct.execute(range); }
class x_sort { private: pool_type & pool_; unsigned cutoff_;
template <typename Range> void seq_( Range& range) { sort_fct()(range); }
template <typename Range> void par_( Range& range) { unsigned size = boost::size(range); if ( size <= cutoff_) return seq_( range); else { boost::sub_range<Range> left(boost::begin(range), boost::begin(range)+(size/2)); boost::sub_range<Range> right(boost::begin(range)+(size/2)+1, boost::end(range)); task_type task(pool_.submit( boost::bind(& x_sort::par_<Range>, boost::ref( * this), boost::ref(left)))); this->par_(right); task.wait(); inplace_merge_fct()(range, boost::begin(range)+(size/2)); } } public: x_sort( pool_type & pool, unsigned cutoff) : pool_( pool), cutoff_( cutoff) {} template <typename Range> void execute( boost::sub_range<Range>& range) { par_( range); } };
I think it's a good example of where the differing range types are not as easy to implement an algorithm as we would wish. The finished algorithm should be able to work with anything that is a model of a Range Concept.
The problem is that the instantiation of par_<Range> requests the instantiation of par_<boost::sub_range<Range>>, and ..., which fall in an recursive instantiation that do not finish. Should the types boost::sub_range<Range> and boost::sub_range<boost::sub_range<Range> > be convertibles? I have taken a workaround, create a sub_range before calling to the internal function execute.
template <typename Range> void parallel_sort(Range& range, unsigned cutoff=10000) { pool_type pool( boost::tp::poolsize( 2) ); x_sort fct( pool, cutoff); boost::sub_range<Range> rng(range); fct.execute(range); }
The internal templates have a boost::sub_range<Range> parameter instead of a Range, so the single tempalte instantiation is par_<boost::sub_range<Range> >.
class x_sort { private: pool_type & pool_; unsigned cutoff_;
template <typename Range> void seq_( boost::sub_range<Range>& range) { sort_fct()(range); }
template <typename Range> void par_( boost::sub_range<Range>& range) { unsigned size = boost::size(range); if ( size <= cutoff_) return seq_( range); else { boost::sub_range<Range> left(boost::begin(range), boost::begin(range)+(size/2)); boost::sub_range<Range> right(boost::begin(range)+(size/2)+1, boost::end(range)); // fork a new sub-action t1 in pool task_type task(pool_.submit( boost::bind(& x_sort::par_<Range>, boost::ref( * this), boost::ref(left)))); this->par_(right); task.wait(); inplace_merge_fct()(range, boost::begin(range)+(size/2)); } } public: x_sort( pool_type & pool, unsigned cutoff) : pool_( pool), cutoff_( cutoff) {}
template <typename Range> void execute( boost::sub_range<Range>& range) { par_( range); } };
Is this the correct way to use Range and sub_range?
Yes, this is exactly what I intend. The public algorithm exposes an interface that can accept any Range Concept, and the internal implementation has to, occasionally jump through some hoops to handle sub_range etc. I haven't been able to think of a way to eliminate this need. Fortunately for most algorithm implementations it is not necessary, and I think the extra function call is not a huge deal. If anyone knows a technique to avoid the need to use sub_range that simplifies matters, I would gladly use it.
Best, Vicente
Thanks, Neil Groves
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
on Sun Feb 22 2009, Neil Groves <neil-AT-grovescomputing.com> wrote:
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!
If I were you, I'd take a careful look at what's in the Adobe Source Library. Alex Stepanov &co. spent years researching the essential elements of this domain, and his idea of what's important may have evolved quite a bit since he was at SGI. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
At 6:58 PM +0100 2/21/09, vicente.botet wrote:
----- Original Message ----- From: "Thorsten Ottosen" <thorsten.ottosen@dezide.com> To: <boost@lists.boost.org>; <boost-users@lists.boost.org>; <boost-announce@lists.boost.org> 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
Sorry- I was AFK this weekend. Some of these are in the sandbox in boost/algorithms: copy.hpp: copy_if, reverse_copy_if, copy_while, reverse_copy_while, copy_n, uninitialized_copy_n, copy_backwards, partition_copy all.hpp: all, all_if, none, none_if, any, any_if, exists_and_only, exists_and_only_if apply.hpp: apply, apply_if find_if_not.hpp: find_if_not iota.hpp: iota for_each_if.hpp: for_each_if transform_if.hpp: transform_if select.hpp: select1st, select2nd Many of these algorithms have range-based versions, too. -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> It is by caffeine alone I set my mind in motion. It is by the beans of Java that thoughts acquire speed, the hands acquire shaking, the shaking becomes a warning. It is by caffeine alone I set my mind in motion.
Hi Neil, Here are some comments from Sean. I think they raises several aspects that we shuold discuss.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Some comments after taking a quick look (sorry, I don't have time for a full review) - Some important range concepts are missing - specifically: counted range (a range denoted by an iterator and an integer count) sentinel range (a range denoted by an iterator and a sentinel, a NTBS is an example) I believe such concepts could also clean up the char* vs. char[] for NTBS ambiguities as well as keep cstr library efficiency. In ASL we've been slowing extending the algorithms for such cases, for example, see lower_bound_n. <http://stlab.adobe.com/lower__bound_8hpp.html> Also, the range based algorithms in ASL are not just about ranges, we also bind function arguments to avoid having to clutter binds in interfaces, "find_if(range, &my_type::member)" We've also been extending the algorithms to take key/projection functions. For example: --- struct my_type { int member; double another_member; }; //... my_type a[] = { { 1, 2.5 }, ... }; // sort the array by the first member: sort(a, less(), &my_type::member); my_type* i = lower_bound(a, 5, less(), &my_type::member); --- In ASL, I believe we get far more bang out these extension then we do out of the range extensions. I haven't looked at the Range.Ex code, but many such libraries refine mutating container algorithms such as sort() to call list<>::sort() - I object to refining algorithms where the semantics differ (in this case, std::sort(list.begin(), list.end()) is identity preserving where list<>::sort() is not. I would rather see the introduction of node based algorithms, such as sort_nodes() and specialize those for list<>. The addition of bounded functions (which take output ranges) would also be a nice addition - see copy_bounded as an example: <http://stlab.adobe.com/group__copy.htm> If anyone would like to take the code from ASL as a starting point for inclusion in boost, they have my permission. Sean
Hi, On Thu, Feb 26, 2009 at 2:04 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
Hi Neil,
Here are some comments from Sean. I think they raises several aspects that we shuold discuss.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Some comments after taking a quick look (sorry, I don't have time for a full review) -
Some important range concepts are missing - specifically:
counted range (a range denoted by an iterator and an integer count)
This seems very similar to the indexed range adaptor in the current library.
sentinel range (a range denoted by an iterator and a sentinel, a NTBS is an example)
I haven't implemented one of these. If I could get one from Adobe that would be marvelous, otherwise I can write one.
I believe such concepts could also clean up the char* vs. char[] for NTBS ambiguities as well as keep cstr library efficiency.
In ASL we've been slowing extending the algorithms for such cases, for example, see lower_bound_n.
<http://stlab.adobe.com/lower__bound_8hpp.html>
Also, the range based algorithms in ASL are not just about ranges, we also bind function arguments to avoid having to clutter binds in interfaces, "find_if(range, &my_type::member)"
It seems like this really is a combinatorial explosion. I'd like to take some time to consider this further.
We've also been extending the algorithms to take key/projection functions. For example:
---
struct my_type { int member; double another_member; };
//...
my_type a[] = { { 1, 2.5 }, ... };
// sort the array by the first member:
sort(a, less(), &my_type::member);
my_type* i = lower_bound(a, 5, less(), &my_type::member);
---
In ASL, I believe we get far more bang out these extension then we do out of the range extensions.
I haven't looked at the Range.Ex code, but many such libraries refine mutating container algorithms such as sort() to call list<>::sort() - I object to refining algorithms where the semantics differ (in this case, std::sort(list.begin(), list.end()) is identity preserving where list<>::sort() is not. I would rather see the introduction of node based algorithms, such as sort_nodes() and specialize those for list<>.
Yes this would be very good. I share your view about overloading sort(). It's just not going to happen! The current implementation does not overload sort with differing semantics. Adding new functions such as sort_nodes is definately the way to go, but hasn't been done yet.
The addition of bounded functions (which take output ranges) would also be a nice addition - see copy_bounded as an example:
<http://stlab.adobe.com/group__copy.htm>
If anyone would like to take the code from ASL as a starting point for inclusion in boost, they have my permission.
I have a preference to use the boost/range/algorithm_ext.hpp where they can be used, as these have several advantages in terms of performance and inability to express defective code. However there are of course cases where we need the other output range types I will definately add better output range support. This is very generous. I would be delighted to pilage your library to add the functionality you have discussed!
Sean
Thank you for taking the time, especially as you are busy, and have considerable experience with a similar library. Best wishes, Neil Groves
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Thorsten Ottosen wrote:
sentinel range (a range denoted by an iterator and a sentinel, a NTBS is an example)
I believe such concepts could also clean up the char* vs. char[] for NTBS ambiguities as well as keep cstr library efficiency.
You just need to allow the past-the-end iterator to be of a different type for that. That way, you can get something equivalent to a hasNext() function.
participants (6)
-
David Abrahams -
Marshall Clow -
Mathias Gaunard -
Neil Groves -
Thorsten Ottosen -
vicente.botet