Re: [boost] Partial Sort and Partition with Ranges [was: Boostcon Keynote available]

Subject: Re: [boost] Partial Sort and Partition with Ranges [was: Boostcon Keynote available]
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-08-05 13:55:50

Scott McMurray wrote:
> 2009/8/5 Andrei Alexandrescu <andrei_at_[hidden]>:
>> Scott McMurray wrote:
>>> On a related note, how would I, using ranges, sort only the first half
>>> of a partition?  It appears I can only get a range for the second
>>> half[2].  In code, I'm looking for the equivalent of sort(b,
>>> partition(b, e, pred));
>> I made partial sorting available for random-access ranges (just like STL).
>> For those it's easy to select the first half (e.g. in D by using r[0 ..
>> r.length / 2]).
>>
> 
> Sorry, that was unclear of me.  When I said "half" I meant "the
> contiguous subsequence at the from of the original range in which the
> predicate is true".  It looks like I have to do this (guessing at D
> syntax):
> 
> falsepart = partition(r, pred);
> sort(r[0 .. r.size()-falsepart.size()]);
> 
> Is there a more elegant way to do that?  I don't have confidence that
> I haven't made an off-by-one error.

Not that I know of.

> Also, I presume partition works
> on bidirectional ranges for which I cannot use [] to get the range
> where the predicate is true.

partition requires bidirectional ranges but if you pass a random-access 
range it gives you back a portion of it, which is also a random-access 
range.

> What if I wanted to run a
> bottom_up_merge_sort function on the "predicate is true" subrange of
> my list, for example?
> 
> In short, it feels like partition should be returning a pair of ranges.
> 
> (Though I haven't thought all the way through sentinel-terminated
> ranges and such.  But I suppose they aren't bidirectional in the first
> place.)

Interesting point. Partition actually works on forward ranges if no 
stability is required. There are different algorithms that work best 
depending on stability requirements. If you look at the implementation 
of std.partition, you'll see that I use different algorithms for stable 
vs. semistable vs. unstable partition. In particular, I don't know of 
efficient stable partition for bidirectional ranges.

I could return two ranges *if* the range is bidirectional and the 
partition is not stable; that would complicate the interface a bit by 
spilling subtle realities about the algorithm into the client.

Note that if you know the length of the range, you can always use 
take(n, range) to restrict a range to its first n elements. This, I 
think, takes care of all situations of interest (if you have a range 
that you don't know the length of *and* want to do bottom_up_merge_sort 
on it, I guess that won't work).

Andrei