Do sorted ranges have any special properties?

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> On Sun, 25 Jul 2010 15:44:36 -0400, Tomek Sowiński <just at ask.me> wrote:
> 
>> Andrei Alexandrescu wrote:
>>
>>> I'm trying to find justifications for keeping assumeSorted and friends
>>> within Phobos. Background: assumeSorted(r) where r is some range returns
>>> a value that wraps r and clarifies to the caller that it can assume r
>>> has been sorted.
>>>
>>> The obvious use case in Phobos is that find(haystack, needle) can
>>> proceed faster if haystack == assumeSorted(something).
>>>
>>> The nicest way to go about this is to make the type returned by
>>> assumeSorted a kind of "range with benefits". That is, it would
>>> implement all range primitives, plus a few more primitives that are
>>> advantageous for sorted ranges. Question is: what are those? What kind
>>> of cool primitives could a sorted range define?
>>>
>>> Here are a few I can think of:
>>>
>>> find -> uses binary search if random-access, or at least early stopping
>>> otherwise.
>>>
>>> minElement -> r.front
>>>
>>> maxElement -> r.back
>>>
>>> topN -> essentially does nothing
>>>
>>> median -> r[r.length / 2]
>>>
>>> Such functions could have free counterparts in std.algorithm. The free
>>> functions check whether the range already implements the fast functions
>>> and uses them transparently if present. So then we have e.g. find()
>>> which works in linear time for most ranges, but logarithmic time on
>>> random-access sorted ranges.
>>
>> Sort of trivial, but I'd like to see the predicate with which it's 
>> sorted.
> 
> I think the "range" returned by assumeSorted has a predicate alias in it 
> already (which defaults to "a < b")

We just need to do the STL trick of re-exposing the template argument 
from within the template:

struct SortedRange(alias _less)
{
     alias binaryFun!_less less;
     ...
}

Clients will use SomeType.less.

>> BTW, would it be a big deal if sort() returned assumeSorted!Range? 
>> Many uses
>> are a re-sort + binary search combo.
> 
> Yeah, that would be good.
> 
> The only problem I see with this is that "sortedness" is broken quite 
> easily in ways that does not remove the assumeSorted type.  For example, 
> if assumeSorted just forwards its underlying range's methods, then given 
> an array arr:
> 
> auto x = assumeSorted(arr.sort);
> 
> x[0] = 999999; // probably no longer sorted
> 
> x.find(999999); // probably doesn't work.

I was considering disabling that by having SortedRange's operators 
return rvalues instead of lvalues.

> And there are other subtle ways to break it in ways that you couldn't 
> even program assumeSorted to deal with:
> 
> arr[0] = 999999; // how does x detect this?

That's pretty brutal :o).

> I feel like assumeSorted is something that's temporary.  It can only be 
> used as a parameter or return decoration, but as soon as you assign it 
> to a variable, it's gone.  Not sure if that can work.  User-defined 
> attributes would be nice here :)

I agree that assumeSorted is somewhat evanescent. I'm still undecided 
whether it deserves a place in Phobos or not.


Andrei