[Issue 5076] New: std.algorithm.sorted / schwartzSorted

d-bugmail at puremagic.com d-bugmail at puremagic.com
Mon Oct 18 19:06:37 PDT 2010


http://d.puremagic.com/issues/show_bug.cgi?id=5076

           Summary: std.algorithm.sorted / schwartzSorted
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: patch
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2010-10-18 19:05:59 PDT ---
I propose to add two new little functions to Phobos, named
sorted()/schwartzSorted(). Their purpose is to copy the input items, sort them
and return them.

The -ed versions are more functional, they don't modify the input data, so they
may work with a immutable input sequence too. They may be used as expressions
instead of as statements, so in theory they allow code like (currently this
doesn't work, see bug 5074 ):


auto foo(immutable(int)[] data) {
    return map!q{ -a }(sorted(data));
}


Instead of:

auto foo(immutable(int)[] data) {
    int[] arr = data.dup;
    sort(arr);
    return map!q{ -a }(arr);
}


sorted()/schwartzSorted() may be seen as less efficient than
sort()/schwartzSort() because they copy the input data, but there are many
situations (like script-like D code) where the programmer wants short and quick
code, and knows the number of input items will be low enough to not cause
memory shortage. Python too has both list.sort() and sorted() built-ins.


A possible simple implementation, for DMD 2.049 (Code not tested much):


import std.algorithm: SwapStrategy, schwartzSort, sort;
import std.range: isRandomAccessRange, hasLength;
import std.array: array;

auto sorted(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
        Range)(Range r)
{
    auto auxr = array(r);
    sort!(less, ss)(auxr);
    return auxr;
}

auto schwartzSorted(alias transform, alias less = "a < b",
        SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)
    if (isRandomAccessRange!(Range) && hasLength!(Range))
{
    auto auxr = array(r);
    schwartzSort!(transform, less, ss)(auxr);
    return auxr;
}

import std.typecons: Tuple;
import std.stdio: writeln;

alias Tuple!(int, "x", int, "y") P;

void main() {
    P[] data = [P(1,4), P(2,3), P(3,1), P(4,0)];
    writeln(data);
    writeln(schwartzSorted!((x) { return x.y; })(data));
    writeln(data);
    writeln(sorted!q{ a.y < b.y }(data));
    writeln(data);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------


More information about the Digitalmars-d-bugs mailing list