[Issue 13936] groupBy must be redone

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=13936

--- Comment #4 from hsteoh at quickfur.ath.cx ---
@andrei:

The current implementation of groupBy only traverses the range once if it's an
input range (non-forward).

The difference between equivalence and non-equivalence relations is actually
important; it's not a "fussy" issue. A non-equivalence relation requires that
you always evaluate the predicate on two adjacent elements, because you cannot
assume transitivity: the fact that pred(r[0], r[1]) and pred(r[1], r[2]) holds,
does not imply pred(r[0], r[2]) also holds, so you have to .save every previous
position of the range instead of just once per subrange (determining the end of
the subrange simply by evaluating the predicate with the head element of that
subrange), when you know that pred is an equivalence relation.

Your fast/slow range idea is flawed, because the outer range's .front must
return an independent instance of the subrange. This is an artifact of the
range API. There is no way for the outer range to keep track of how far the
subrange has moved ahead without introducing some kind of reference semantics
to it, which becomes messy if the caller invokes .front multiple times. For
example, if the user calls .front twice and .save's both subranges, then
randomly iterates one or the other, what should happen? Should the outer
range's 'fast' range track the first subrange, the second, or both, or neither
(because they are .save'd copies)? Does advancing the first copy of the
subrange also advance the second? (Which, btw, breaks the semantics of .save)?

The only way for your fast/slow range idea to work is to make subranges
non-forward, so that there is only one copy of the 'fast' range that gets
advanced no matter which copy of it you call popFront on. But this means users
can no longer call .save on subranges, which sux if they handed you a forward
range precisely for that purpose.

--