D-Programming-Language/phobos — pull request #1801 by monarchdodra (2013-12-21 18:53:26+00:00)
Title: rework setIntersection

Forked from #1798 : I was able to rework the algorithm into something both very simple, and efficient. The "trick", is instead of iterating on all pairs in 0 .. $ - 1, to go all the way to $, and have "$ - 1" match up with "0".

I'd describe this as a "continuous circular bubble". The fact that it is circular means we can also run the checks in only 1 direction: If all elements in a circular buffer are smaller than their predecessor, then they have to all be equivalent.

Benches:
```
wideTest
bubble: 27284ms, shaker: 2400ms, composed: 4734ms, circular: 2264ms
bubble: 1, shaker: 11.3658, composed: 5.76286, linear: 12.0471

quadTest
bubble: 218ms, shaker: 290ms, composed: 208ms, circular: 190ms
bubble: 1, shaker: 0.751943, composed: 1.04846, linear: 1.14866

tripleTest
bubble: 217ms, shaker: 304ms, composed: 204ms, circular: 187ms
bubble: 1, shaker: 0.713614, composed: 1.06307, linear: 1.16154

trivialTest
bubble: 169ms, shaker: 166ms, composed: 171ms, circular: 157ms
bubble: 1, shaker: 1.02392, composed: 0.990549, linear: 1.07631
```

Look at that: It's better than *every* other algorithm, regardless of input size! And the algo is really very small:
```D
void adjustPosition()
{
if (empty) return;

size_t done = Rs.length;
static if (Rs.length > 1) while (true)
{
foreach (I, R; Rs)
{
alias r = _input[I];
alias next = _input[(I + 1) % Rs.length];

if (comp(next.front, r.front))
{
next.popFront();
if (next.empty) return;
done = Rs.length + 1;
}
if (--done == 0) return;
}
}
}
```