On Tuesday, 6 December 2016 at 01:46:38 UTC, Nicholas Wilson
wrote:
On Monday, 5 December 2016 at 22:10:34 UTC, Nordlöw wrote:
On Monday, 5 December 2016 at 21:48:49 UTC, Nordlöw wrote:
Ahh, setops has intersection aswell:
https://dlang.org/phobos/std_algorithm_setops.html#setIntersection
I should have a guessed that.
Ahh again, but current Phobos is currently not optimized for
the case when all inputs are SortedArrays. In that case a
double binary search algorithm as describe here
http://cs.stackexchange.com/a/37124/25769
might be faster.
Has anybody already done this?
The double binary search linked only finds *one* element of the
intersection.
It should be as simple as a linear find (over the range of
ranges) that returns (i.e. caches to .front) if the elements
intersect.
Hmm not sure that will work.
The annoying property of this problem is calculating .empty and
having .empty not mutate the ranges. however if you settle for an
eager empty something like
auto setIntersect(RoR,alias _pred)(RoR ror) if (allSatisfy!(RoR,
isSortedRange!_pred) &&
allSatisfy!(RoR, isSame!(ElementType) &&
!allSatisfy!(RoR, isRandomAccessRange))
{
enum lengths = RoR.length;
alias elem = ElementType!(RoR[0]);
alias pred = BinaryFun!_pred;
struct SetIntersect
{
RoR ror;
elem[lengths] fronts = void;
elem front = void;
bool valid = false;
this(RoR r)
{
ror = r;
populate();
}
void populate()
{
foreach(i, ref r; ror)
fronts[i] = r.front;
}
void advance()
{
foreach( ref r; ror)
r.popFront();
}
void popFront() { valid = false; }
bool empty()
{
if (valid) return false;
advance();
populate();
if (reduce!(equal)(fronts)) return false;
elem m = reduce!(pred)(fronts);
foreach(i, ref r; ror)
{
while(!pred(r.front,m))
r.popFront();
}
populate();
valid = reduce!(equal)(fronts));
return !valid;
}
}
}
