[Issue 6788] std.range.pairwise

[via Digitalmars-d-bugs]

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

--- Comment #8 from bearophile_hugs at eml.cc ---
(In reply to hsteoh from comment #7)

> If order doesn't matter,

The order matters, this:

foreach (tup; iota(1, 5).pairwise)
    tup.writeln;

Should print only in this order:

Tuple!(int,int)(1, 2)
Tuple!(int,int)(1, 3)
Tuple!(int,int)(1, 4)
Tuple!(int,int)(2, 3)
Tuple!(int,int)(2, 4)
Tuple!(int,int)(3, 4)


> However, we can't actually use nested loops for a generic algorithm,
> since (1) the nesting level depends on how many elements you want in the
> subset, and (2) we have to lazy-fy the loops to conform to the range API
> anyway.

The function name "pairwise" refers to "pairs", because 95% of the times I only
need two indexes. And code like "[1, 2, 3, 4].pairwise" doesn't contain a "2"
to specify two indexes.

So if you want to reduce your implementation work, you can just use the version
that yields pairs, like in #Comment 4.

But if you want to also implement the generation of 3-tuples or more, then I
guess you can use a syntax like:

iota(1, 5).pairwise!3

But now the name "pairwise" sounds like a falsity.


> I'm thinking that a forward range should be sufficient for such an
> enumeration.

We can make the range more powerful later, if necessary.


> So if we have a stack of .save'd ranges, that should do the
> trick. First, to generate k-element subsets, we prime the stack with .save'd
> copies of the range up to the k'th element, then .front simply walks the
> stack and retrieves .front from each item on the stack. In popFront(), we
> simply advance the range at the top of the stack. If it's empty, we pop it
> off, and advance the previous range on the stack, then fill up the stack
> again with the subsequent element. Each time, if advancing a range makes it
> empty, we pop it off and advance the previous range on the stack instead,
> then fill up the stack again. Yes, I think this will work... PR time! :-)

I suggest to add a compile-time optimization for the most general case (n=2) to
make it fast, because it's the most common and it should be very fast.

--