Comment #0 by bearophile_hugs — 2013-08-08T07:33:34Z
This is the signature of std.algorithm.multiSort:
void multiSort(Range)(Range r) if (validPredicates!(ElementType!Range, less));
I suggest to modify multiSort to make it return a SortedRange, just like std.algorithm.sort(). This is handy to use multiSort in UFCS chains (sometimes even using release).
Currently the implementation of SortedRange is:
struct SortedRange(Range, alias pred = "a < b")
if (isRandomAccessRange!Range && hasLength!Range)
{
private alias binaryFun!pred predFun;
...
So perhaps SortedRange too should change a little to be usable for multiSort, to support more than one sorting predicate.
Comment #1 by szymon.kielbasa+dlang — 2014-08-05T22:42:36Z
I often use multiSort in bioinformatics applications.
To make multiSort more usable I (hopefully carefully) extended the range.d and algorithm.d code (of 2.065) to add the following functionality:
- SortedRange has been extended to support one or more predicates; it internally constructs the full predicate function out of separately provided ones
- multiSort has been converted to return the modified SortedRange object
- assumeSorted has been modified to handle multiple predicates
The existing unittests do compile without any modifications; a few new ones have been added.
The above changes are mostly of cosmetics nature.
But my primary motivation was to provide possibility to perform binary searches with equalRange family of functions based not only on all predicates, but also on a subset of leading ones (an example: a range of persons, sorted first by surnames and then by given names should provide possibility to find a range of persons with requested (surname and given name) as well as a range of persons with requested surname). To achieve that I added:
- SortedRange.keepPreds!( numPreds ) function which returns the same range annotated as SortedRange with possibly a smaller number of predicates.
Comment #2 by szymon.kielbasa+dlang — 2014-08-05T22:44:09Z
Created attachment 1377
range.d with SortedRange changes
Comment #3 by szymon.kielbasa+dlang — 2014-08-05T22:44:47Z
Created attachment 1378
algorithm.d with multiSort changes
Comment #4 by code — 2015-11-09T12:38:34Z
Your work seems pretty useful, care to convert it into a PR?
Comment #5 by greeenify — 2016-03-04T12:23:02Z
nice idea @bearophile and @SzMK - how about sharing it as a PR?
Comment #6 by szymon.kielbasa+dlang — 2016-03-06T21:40:06Z