Fixing the SortedRange

[Dmitry Olshansky]

On 04.03.2012 12:59, Dmitry Olshansky wrote:
> 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.
>

Nah, that's not gonna work as !(b < a) is a >= b, not a > b, a kind of 
thing obvious on the second thought only. And anyway, looking at the 
implementation as lowerBound uses !pred(lhs, rhs) while upperBound uses 
pred(rhs, lhs). So I think it's okay and less fragile to always require 
both ways. It's all in regex pull btw, like I could fix one bug on it's 
own ;)

-- 
Dmitry Olshansky