Simen kjaeraas schrieb:
Daniel Gibson <[email protected]> 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).
