Scott McMurray wrote:
2009/8/5 Andrei Alexandrescu <andrei@metalanguage.com>:
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