improving the join function

[Daniel Gibson]

Simen kjaeraas schrieb:
> Daniel Gibson <metalcaedes at gmail.com> wrote:
> 
>> (*) Something like
>> Range!(Tuple!(T1, T2)) join(T1, T2)(Range!(T1) r1, Range!(T2) r2, 
>> BinaryPredicate!(T1, T2) joinPred)
>> just pseudo-code, I'm not really familiar with D2 and std.algorithm.
>> The idea is you have a Range r1 with elements of type T1, a Range r1 
>> with elements of type T2 and a predicate that gets a T1 value and a T2 
>> value and returns bool if they match and in that case a Tuple with 
>> those two values is part of the Range that is returned.
> 
> Once again I see the combinatorial range in the background. Man, why does
> this have to be so hard?
> 
> That is, your join could be implemented as follows, given the
> combinatorial product range combine:
> 
> 
> auto join( alias fun, R... )( R ranges ) if ( allSatisfy!( 
> isForwardRange, R ) ) {
>     return filter!fun( combine( ranges );
> }
> 

Yes, but if:
* at least the second input range is a sorted random access range join could be calculated a lot 
cheaper, especially on the (common) case that the predicate checks for equality (=> binary search)
* both ranges are sorted and the predicate checks for equality the join can even be done in linear 
time (instead of quadratic like when using a cross product/combinatorical product)

However for generic cases combine() would certainly be very helpful (on the other hand if there were 
a proper join() you could get combine() by just using a predicate that is always true).


But right now the point is: join() does something completely different and should be renamed (or 
deprecated in std.string and replaced by union() - a real join isn't needed in std.string anyway, 
but when join() is deprecated in std.string you can implement a real join in std.algorithm without 
causing too much confusion).