design question

[Denis Koroskin]

On Fri, 03 Apr 2009 20:53:18 +0400, Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:

> I'm toying with a rather new approach to a certain problem, and wanted  
> to ask for some feedback before coding with it.
>
> The STL has two functions with a "stable" variant: stable_sort and  
> stable_partition. They differ from sort and partition in that they  
> preserve the order of equivalent objects. They are more costly, hence  
> the default is "unstable".
>
> I started with the same approach in std.algorithm, but before long I  
> figured two things:
>
> a) There are many more algorithms that can benefit from stable vs.  
> unstable versions: remove, topN, schwartzSort, partialSort, completeSort  
> (take a sorted range and an unsorted one and make a sorted range out of  
> them), and makeIndex.
>
> b) Aside from stable and unstable, there's a semistable notion: when  
> partitioning, the left half stays stable and the right half is unstable.
>
> Clearly encoding stability in the function name isn't faring very well,  
> so I made a policy of it:
>
> enum SwapStrategy { stable, semistable, unstable }
>
> and parameterized the appropriate functions with SwapStrategy. A use  
> case looks like this:
>
> // even to the left, odd to the right
> auto arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
> auto p = partition!("(a & 1) == 0", SwapStrategy.stable)(arr);
> assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]);
> assert(p == arr[5 .. $]);
>
> Ok, until now there's only been background :o|. The new part starts here.
>
> I think the stability request could be better encoded as a wrapper of  
> the range making the request. For example:
>
> auto p = partition!("(a & 1) == 0")(keepStable(arr));
>
> So in order to tell partition you want stability, you just wrap the  
> range with a call to keepStable. (The runtime cost is negligible).  
> Similarly, say you want a stable sort. You'd say:
>
> sort(keepStable(arr));
>
> instead of:
>
> sort!(SwapStrategy.stable)(arr);
>
> I have the feeling this approach will scale better in the future. Also  
> it is less verbose and in sync with the current way of doing searches:
>
> auto f = find(assumeSorted(haystack), needle);
>
> In that case, assumeSorted uses the same means of transmitting  
> information about a range into an algorithm.
>
> So... I'd appreciate any thoughts you might have. Thanks.
>
>
> Andrei

This sounds interesting, but I don't thing it's good idea overall.

assumeSorted(range) is fine, because "sorted" is a property of a range.
auto r = assumeSorted(range); // makes sense

keepStable(range) is not okay, because stable is not a property of a range. It's a property of an algorithm.
auto r = keepStable(range); // makes no sense to me