I was in a situation where I wanted to remove duplicates from an OnlyResult.
To do this with uniq, I needed to sort it. OnlyResult doesn't satisfy the template constraints of sort, but this seems easy enough to fix. I made front, back, and opIndex return by ref. With this, the following compiles:

    assert(only(3,1,2).sort.equal(only(1,2,3)));

However, it fails with:

    core.exception.AssertError@std/algorithm/sorting.d(1052): Failed to sort range of type OnlyResult!(int, 3LU)

So, if you have a range for which sort compiles, what does it take to make sorting actually work?

For reference, my two attempts were:

https://github.com/rcorre/phobos/commit/d89b3cfab7a0938e178a506b4ceb8faae6ecbfe2

https://github.com/rcorre/phobos/commit/512d9b8db6f311db6a9b6ccb077a691cec66ce70

On Wednesday, 9 March 2016 at 03:05:52 UTC, rcorre wrote:
> I was in a situation where I wanted to remove duplicates from an OnlyResult.
> To do this with uniq, I needed to sort it. OnlyResult doesn't satisfy the template constraints of sort, but this seems easy enough to fix. I made front, back, and opIndex return by ref. With this, the following compiles:
>
>     assert(only(3,1,2).sort.equal(only(1,2,3)));
>
> However, it fails with:
>
>     core.exception.AssertError@std/algorithm/sorting.d(1052): Failed to sort range of type OnlyResult!(int, 3LU)
>
> So, if you have a range for which sort compiles, what does it take to make sorting actually work?
>
> For reference, my two attempts were:
>
> https://github.com/rcorre/phobos/commit/d89b3cfab7a0938e178a506b4ceb8faae6ecbfe2
>
> https://github.com/rcorre/phobos/commit/512d9b8db6f311db6a9b6ccb077a691cec66ce70

I'm not sure why your fix didn't work, but generally I work around this by converting the OnlyResult into an array:

import std.array : array;
assert(only(3,1,2).array.sort.equal(only(1,2,3)));


If you are looking for a lazy uniq that works on non sorted ranges, I implemented one not to long ago:
http://github.com/BlackEdder/ggplotd/blob/master/source/ggplotd/range.d

On Wednesday, 9 March 2016 at 09:15:01 UTC, Edwin van Leeuwen wrote:
>
> I'm not sure why your fix didn't work, but generally I work around this by converting the OnlyResult into an array:
>
> import std.array : array;
> assert(only(3,1,2).array.sort.equal(only(1,2,3)));

I'd like to avoid allocating here.

>
>
> If you are looking for a lazy uniq that works on non sorted ranges, I implemented one not to long ago:
> http://github.com/BlackEdder/ggplotd/blob/master/source/ggplotd/range.d

That sounds like the kind of thing I was looking for. I'll take a look, thanks!

On Wednesday, 9 March 2016 at 12:21:55 UTC, rcorre wrote:
>> If you are looking for a lazy uniq that works on non sorted ranges, I implemented one not to long ago:
>> http://github.com/BlackEdder/ggplotd/blob/master/source/ggplotd/range.d
>
> That sounds like the kind of thing I was looking for. I'll take a look, thanks!

Well that one does allocate, because it keeps track of which values have already been seen.

On Wednesday, 9 March 2016 at 12:31:18 UTC, Edwin van Leeuwen wrote:
> On Wednesday, 9 March 2016 at 12:21:55 UTC, rcorre wrote:
>>> If you are looking for a lazy uniq that works on non sorted ranges, I implemented one not to long ago:
>>> http://github.com/BlackEdder/ggplotd/blob/master/source/ggplotd/range.d
>>
>> That sounds like the kind of thing I was looking for. I'll take a look, thanks!
>
> Well that one does allocate, because it keeps track of which values have already been seen.

Yup, just noticed that >.<

On Wednesday, 9 March 2016 at 13:04:31 UTC, rcorre wrote:
> On Wednesday, 9 March 2016 at 12:31:18 UTC, Edwin van Leeuwen wrote:
>> On Wednesday, 9 March 2016 at 12:21:55 UTC, rcorre wrote:
>>>> If you are looking for a lazy uniq that works on non sorted ranges, I implemented one not to long ago:
>>>> http://github.com/BlackEdder/ggplotd/blob/master/source/ggplotd/range.d
>>>
>>> That sounds like the kind of thing I was looking for. I'll take a look, thanks!
>>
>> Well that one does allocate, because it keeps track of which values have already been seen.
>
> Yup, just noticed that >.<

Of course it only allocates when the actual result is used, so this will probably be more efficient if you only need a small number of unique results or need to keep the unsorted range around/intact. Sorting without allocating and then using uniq should indeed be more efficient in other cases.

Did you try different SwapStrategy values in your original?

On Wednesday, 9 March 2016 at 12:21:55 UTC, rcorre wrote:
> On Wednesday, 9 March 2016 at 09:15:01 UTC, Edwin van Leeuwen wrote:
>>
>> I'm not sure why your fix didn't work, but generally I work around this by converting the OnlyResult into an array:
>>
>> import std.array : array;
>> assert(only(3,1,2).array.sort.equal(only(1,2,3)));
>
> I'd like to avoid allocating here.

Note that an input range isn't even remotely a container, it's a way to iterate on a container. As you don't have all elements at hand you can't sort them, that's why you have to use array here. If you don't want to allocate using the GC just allocate your own memory and store your range elements in it before sorting but sort has to have access to all elements one way or another.

On Wednesday, 9 March 2016 at 14:28:11 UTC, cym13 wrote:
> On Wednesday, 9 March 2016 at 12:21:55 UTC, rcorre wrote:
>> On Wednesday, 9 March 2016 at 09:15:01 UTC, Edwin van Leeuwen wrote:
>>>
>>> I'm not sure why your fix didn't work, but generally I work around this by converting the OnlyResult into an array:
>>>
>>> import std.array : array;
>>> assert(only(3,1,2).array.sort.equal(only(1,2,3)));
>>
>> I'd like to avoid allocating here.
>
> Note that an input range isn't even remotely a container, it's a way to iterate on a container. As you don't have all elements at hand you can't sort them, that's why you have to use array here.

In the general case, yes. However only is a range wrapper around a static array, and does have all elements at hand. Maybe I should just be using a static array...

Still curious as to why it fails; maybe the range is getting copied at some point? I guess I need to step through it.

I did try different SwapStrategies with no luck.

On Wednesday, 9 March 2016 at 15:39:55 UTC, rcorre wrote:
> On Wednesday, 9 March 2016 at 14:28:11 UTC, cym13 wrote:
>
> Still curious as to why it fails; maybe the range is getting copied at some point? I guess I need to step through it.
>
> I did try different SwapStrategies with no luck.

Since you are adapting phobos anyway you could try commenting out the assert and see what the result of the sort is. That might give you some clue:

//assert(isSorted!lessFun(r), "Failed to sort range of type " ~ Range.stringof);


Also I notice the line numbering is different in my sorted.d file. Did you test the latest version of dmd/phobos?

On Wednesday, 9 March 2016 at 14:28:11 UTC, cym13 wrote:
>
> Note that an input range isn't even remotely a container, it's a way to iterate on a container. As you don't have all elements at hand you can't sort them, that's why you have to use array here.

Oh, I think it just clicked. I was thinking 'sort takes a range, so it must be used for sorting ranges', but I should have thought 'sort takes a range so it can sort a container via a range over that container'.