Fixing the SortedRange

[Andrei Alexandrescu]

On 3/3/12 12:44 PM, Dmitry Olshansky wrote:
> It's annoyingly strange that e.g. the following won't work as of yet:
>
> auto sorted = assumeSorted(["hello", "world"]); //assume lots of strings
> auto x = sorted.lowerBound("Try that?"d);
>
> Yeah, I know the immutable(dchar)[] vs immutable(char)[] can't be
> compared using straight <. That's acceptable, even if not convenient.

Interesting.

> Ok, take 2, via std.algorithm cmp:
> auto sorted = assumeSorted!"cmp(a,b) < 0"(["hello", "world"]);
> auto x = sorted.lowerBound("Try that?"d);
>
> Now that fails, because of lowerBound signature. And that is
>
> auto lowerBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value)
> if (is(V : ElementType!Range))

That's a bug. The sig should be:

auto lowerBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value)
     if (is(typeof(pred((ElementType!Range).init, value))

> Same goes for upperBound and others.

Agreed.

> And why the hell I need to convert the value to type of range element?
> It's not like there is any value = range[x]; necessary, and indeed it
> works without the signature (+ a one liner fix).

When I put together the SortedRange design there were a ton of bugs in 
the compiler and I barely brought it together. We can definitely improve 
it.

> Seeking the proper signature I've come up with the following:
>
> auto lowerBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value)
> if (isTwoWayCompatible!(predFun, ElementType!Range, V))
>
> isTwoWayCompatible!(pred,A,B) means ether of the following works:
> pred(a,b) and pred(b,a) where a has type A, b typed as B
>
> Seem fine to me, so I'm looking for a better name for this trait.
> Does it sound like it belongs in std.traits or is there more general
> better abstraction for this kind of thing?

Should be fine for the predicate to consistently be applied to one side 
only. Not sure which is the most natural. Probably the range element 
should be first.


Andrei