C# to D

[Ivan Kazmenko via Digitalmars-d-learn]

On Wednesday, 25 March 2015 at 19:32:43 UTC, Dennis Ritchie wrote:
> On Wednesday, 25 March 2015 at 19:01:43 UTC, bearophile wrote:
>> One solution:
>
> Thanks.
>
> On Wednesday, 25 March 2015 at 19:03:27 UTC, bearophile wrote:
>> But calling "count" for each item is not efficient (in both C# 
>> and D). If your array is largish, then you need a more 
>> efficient solution.
>
> A more effective solution for C ++:
>
> #include <iostream>
> #include <vector>
> #include <range/v3/all.hpp>
>
> int main() {
>   using namespace ranges;
>
>   auto rng = istream<int>( std::cin )
>            | to_vector
>            | action::sort
>            | view::group_by( std::equal_to<int>() )
>            | copy
>            | action::stable_sort( []( const auto& e1, const 
> auto& e2 ) { return distance( e1 ) < distance( e2 ); } );
>   std::cout << ( rng );
> }

Here is my take at it:

1. A more verbose comparison function:

-----
import std.algorithm, std.conv, std.range, std.stdio;
void main () {
     auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
     arr.sort !((x, y) => arr.count (x) > arr.count (y) ||
         (arr.count (x) == arr.count (y) && x < y))
         .map !(to !(string))
         .join (" ")
         .writeln;
     // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 0 7 7
}
-----

This surprised me by printing ...0 7 7 instead of ...7 0 0, which 
is plain wrong.  Reproducible in 2.066 and 2.067 on win32.  With 
-debug, it triggers an assertion in Phobos:

-----
core.exception.AssertError at c:\Tools\dmd\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(900): 
Failed to sort range of type int[]
----------------
0x0041708D in _d_assert_msg
0x00416C2F in void rt.dmain2._d_run_main(int, char**, extern (C) 
int function(char[][])*).runAll()
0x00416B47 in _d_run_main
0x00416848 in main
0x76AD33CA in BaseThreadInitThunk
0x770C9ED2 in RtlInitializeExceptionChain
0x770C9EA5 in RtlInitializeExceptionChain
-----

Will file an issue soon.

2. As above, but use the other sorting algorithm:

-----
import std.algorithm, std.conv, std.range, std.stdio;
void main () {
     auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
     arr.sort !((x, y) => arr.count (x) > arr.count (y) ||
         (arr.count (x) == arr.count (y) && x < y), 
SwapStrategy.stable)
         .map !(to !(string))
         .join (" ")
         .writeln;
     // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
}
-----

All fine here.

3. Sort by comparing a transform of the data, for some reason 
disguised by the name schwartzSort:

-----
import std.algorithm, std.conv, std.range, std.stdio, 
std.typecons;
void main () {
     auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
     arr.sort ()
         .schwartzSort !(x => tuple (-arr.count (x), x))
         .map !(to !(string))
         .join (' ')
         .writeln;
     // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
}
-----

Similar to bearophile's solution.
(1) For me, the name of the function is obscure.  Something like 
sortBy would be a lot easier to find than schwartzSort.
(2) It does not offer multiple transforms (sort by this, then by 
that).  This seems doable as a Phobos enhancement.

4. Sort by a few binary predicates in one pass.

-----
import std.algorithm, std.conv, std.range, std.stdio;
void main () {
     auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
     arr.multiSort !((a, b) => arr.count (a) > arr.count (b),
         (a, b) => a < b);
     arr.map !(to !(string))
         .join (' ')
         .writeln;
     // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
}
-----

Two concerns here.
(1) It returns void instead of a sorted range, so can't be 
chained as the others.  This seems doable as a Phobos 
enhancement.  Or is there a reason not to?
(2) The documentation says it is more efficient than the first 
version in the number of comparisons (verbose lambda with plain 
sort) [1], but I don't get how it is possible: unless we know 
than (not pred1(a,b)) and (not !pred1(a,b)), we can not proceed 
by evaluating pred2(a,b).

Ivan Kazmenko.