Re: [Adobe-source-devel] Fwd: gather and stable_gather

[Marshall C. <mar...@id...>]

Well, crud, Sean - you've taken my proposal and "improved" it until 
it's almost unrecognizable.
And your suggestions are good, too! ;-)

At 11:49 AM -0800 1/22/08, Sean Parent wrote:
>I will argue here that I don't see a need for an unstable gather - 
>do you have such a use case? In absence of one I'm likely to simply 
>call the stable form "gather". And drop the unstable form - for 
>partition often you don't care about stability but I don't see that 
>for gather.
>
>
>On implementation -
>
>	* I do not see a reason for the pre-condition/throw and there 
>is a fair amount of redundant checking - partition handles empty 
>ranges just fine.

That was just me being paranoid - I was not sure that partition 
handled empty ranges.

>	* Note that for a stable gather if the element pointed to 
>satisfies the predicate then it won't move.

D'oh!

>
>	* Since a good partition will return a partition point, the 
>obvious (and useful) result would seem to be the gathered range.

That's a much better return value.

>	* We should debate the parameter ordering - rotate takes 
>(first, middle, last) - but this form is easier to adapt to ranges.
>
>	* throwing in an extra boost::bind() on p allows functions to 
>take anything convertible to a function without bind (ASL follows 
>this for all algorithms).

Good suggestion.

>Minor items:
>	* Although I don't think std::stable_partition works with 
>ForwardIterator but we certainly have the code to do so... we could 
>loosen the requirements.
>	* The sense of the predicate is inverted in std::partition() 
>(and std::partition) [that is, it isn't consistent with sort and 
>partition is a form of sort] - if we provide our own partition this 
>would be one item to fix-up.
>
>---
>
>template <
>    typename I,	// I models BidrectionalIterator
>    typename P> // P models UnaryPredicate
>std::pair<I, I> gather(I f, I l, I m, P p)
>{
>	return std::make_pair(std::stable_partition(f, 
>m, !boost::bind(p, _1)), std:: stable_partition(m, l, boost::bind(p, 
>_1)));
>
>}

And that's much simpler than my code!


>Work that would need to be done for a complete submission:
>
>1) Provide the above and all the range based variants (look at the 
>current STL wrappers on partition for examples).
>2) Provide doxygen documentation
>3) Provide a unit test

I'm pretty sure that I can do that this weekend.

>Bonus:
>
>1) Provide a better implementation of partition and stable_partition 
>(lots of info on stepanovpapers.com, including some code, on how to 
>do this -
>2) Weaken the requirement on gather to ForwardIterator using the new 
>partition.

Less sure about these...

P.S.	Please use this email address, rather than my Qualcomm one.
-- 
-- Marshall

Marshall Clow     Idio Software   <mailto:mar...@id...>

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.