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
