www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Functional Sort

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
Is there a functional variant of std.algorithm.sort, say sorted, 
that returns a sorted copy of its input use typically as

     const y = x.sorted;

?

If not any recommendations on its implementation?
Nov 14 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Saturday, 15 November 2014 at 00:33:11 UTC, Nordlöw wrote:

 Is there a functional variant of std.algorithm.sort, say 
 sorted, that returns a sorted copy of its input use typically as

     const y = x.sorted;

 ?

 If not any recommendations on its implementation?


`sort` returns a SortedRange, so sort is the function you're 
looking for.
Nov 14 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 15 November 2014 at 00:45:11 UTC, Meta wrote:

 `sort` returns a SortedRange, so sort is the function you're 
 looking for.


Do you mean std.algorithm.sort?

I want a sort that doesn't mutate its input argument.
Nov 14 2014
parent "Meta" <jared771 gmail.com> writes:
On Saturday, 15 November 2014 at 00:47:41 UTC, Nordlöw wrote:

 On Saturday, 15 November 2014 at 00:45:11 UTC, Meta wrote:

 `sort` returns a SortedRange, so sort is the function you're 
 looking for.


 Do you mean std.algorithm.sort?

 I want a sort that doesn't mutate its input argument.


In that case, just .dup the array before sorting, as you want a 
copy anyway. I don't think there's a sorting function in Phobos 
that doesn't mutate its argument.
Nov 14 2014
prev sibling parent reply "Meta" <jared771 gmail.com> writes:
On Saturday, 15 November 2014 at 00:45:11 UTC, Meta wrote:

 On Saturday, 15 November 2014 at 00:33:11 UTC, Nordlöw wrote:

 Is there a functional variant of std.algorithm.sort, say 
 sorted, that returns a sorted copy of its input use typically 
 as

    const y = x.sorted;

 ?

 If not any recommendations on its implementation?


 `sort` returns a SortedRange, so sort is the function you're 
 looking for.


Sorry, and if you want a copy, just add a `.array` on the end to 
create a new array from the returned range.
Nov 14 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 15 November 2014 at 00:47:57 UTC, Meta wrote:

 `sort` returns a SortedRange, so sort is the function you're 
 looking for.


 Sorry, and if you want a copy, just add a `.array` on the end 
 to create a new array from the returned range.


Great!

Should I use std.algorithm.array or std.array.array in these 
cases?
Nov 14 2014
parent "Meta" <jared771 gmail.com> writes:
On Saturday, 15 November 2014 at 01:01:57 UTC, Nordlöw wrote:

 On Saturday, 15 November 2014 at 00:47:57 UTC, Meta wrote:

 `sort` returns a SortedRange, so sort is the function you're 
 looking for.


 Sorry, and if you want a copy, just add a `.array` on the end 
 to create a new array from the returned range.


 Great!

 Should I use std.algorithm.array or std.array.array in these 
 cases?


There's only std.array.array. I think std.algorithm just 
publically imports std.array.
Nov 14 2014
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/14/14 7:47 PM, Meta wrote:

 On Saturday, 15 November 2014 at 00:45:11 UTC, Meta wrote:

 On Saturday, 15 November 2014 at 00:33:11 UTC, Nordlöw wrote:

 Is there a functional variant of std.algorithm.sort, say sorted, that
 returns a sorted copy of its input use typically as

    const y = x.sorted;

 ?

 If not any recommendations on its implementation?


 `sort` returns a SortedRange, so sort is the function you're looking for.


 Sorry, and if you want a copy, just add a `.array` on the end to create
 a new array from the returned range.


err... this isn't what you want. That will sort the range, and then make 
a copy of the sorted range as an array.

Note, there isn't any generic way to say "give me a copy of this range, 
as the same type." array is probably the best you will get. Just make 
sure you call it *before* you sort, unless you want both ranges sorted :)

-Steve
Nov 14 2014
next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Saturday, 15 November 2014 at 03:47:25 UTC, Steven 
Schveighoffer wrote:

 err... this isn't what you want. That will sort the range, and 
 then make a copy of the sorted range as an array.


Yes, I didn't see the the second constraint to not sort the 
original range.

Sort before .array -> original will be sorted.

Sort after  .array -> original will not be sorted.
Nov 15 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 15 November 2014 at 08:52:45 UTC, Meta wrote:

 On Saturday, 15 November 2014 at 03:47:25 UTC, Steven 
 Schveighoffer wrote:

 err... this isn't what you want. That will sort the range, and 
 then make a copy of the sorted range as an array.


 Yes, I didn't see the the second constraint to not sort the 
 original range.

 Sort before .array -> original will be sorted.

 Sort after  .array -> original will not be sorted.


BTW: When I uncomment line

     /* assert(x.sorted == y); */

in string unittest it errors as

sort_ex.d(160,5): Error: can only sort a mutable array
sort_ex.d(178,13): Error: template instance sort_ex.sorted!string 
error instantiating

What's wrong with my isArray-overload of sorted?
Nov 15 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 15 November 2014 at 14:34:07 UTC, Nordlöw wrote:

 What's wrong with my isArray-overload of sorted?


I solved it by replacing

     R s = r.dup;

with

     auto s = r.dup;

As a follow up I know wonder if it is ok for isArray-overload of 
sorted() to have return type ubyte[] if input is a string?

I wonder because x.array.sort has type

     dchar[]

when x is a string.
Nov 15 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 15 November 2014 at 03:47:25 UTC, Steven 
Schveighoffer wrote:

 Note, there isn't any generic way to say "give me a copy of 
 this range, as the same type." array is probably the best you 
 will get. Just make sure you call it *before* you sort, unless 
 you want both ranges sorted :)

 -Steve


Does this mean that r.array is better than my current

auto sorted(R)(const R r) if (isInputRange!R &&
                               !(isArray!R))
{
     alias E = ElementType!R;
     import std.algorithm: sort, copy;
     auto s = new E[r.length]; // TODO length is probably not 
available here
     r.copy(s);
     s.sort;
     return s;
}

at https://github.com/nordlow/justd/blob/master/sort_ex.d#L117

?
Nov 15 2014