Fixing the SortedRange

[Dmitry Olshansky]

On 04.03.2012 6:28, Andrei Alexandrescu wrote:
> 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.
>

Yup, compiler bugs largely defined the shape of Phobos :)


>> 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.
>

That was my thought, though it could be very annoying to always check 
the docs for which way it goes. With some meta magic, it could be 
deduced like:
If is(typeof(pred(ElementType!(Range).init,value) works then it's used 
as is.
If the opposite order works, then pred is wrapped as !pred, and it's 
compiler job to optimize away this extra operation.
I'll take a shot on it, to see how it works out.

-- 
Dmitry Olshansky