www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Fixing the SortedRange

reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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.

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

Same goes for upperBound and others.

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

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?


-- 
Dmitry Olshansky
Mar 03 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Mar 03 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Mar 04 2012
next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
 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.


Great. It's a big nuisance of std.algorithm.
Mar 04 2012
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Mar 04 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/4/12 10:24 AM, Dmitry Olshansky wrote:

 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 ;)


Yah, you'd need a == b too. I think it's reasonable to demand that both 
a < b and b < a work.

Thanks,

Andrei
Mar 04 2012