How to iterate all k-subsets of a range in a specific order?

[Ali Çehreli]

On 10/05/2012 01:08 AM, Tommi wrote:
 > I can write the following in C++ to iterate through all 2-subsets of a
 > forward-range in that specific order:
 >
 > #include <iterator>
 > #include <boost/range/concepts.hpp>
 >
 > template <typename R>
 > void fun(const R& r)
 > {
 > BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<R> ));
 >
 > for (auto i = std::next(std::begin(r)); i != std::end(r); ++i)
 > {
 > for (auto j = std::begin(r); j != i; ++j)
 > {
 > _cprintf("%d %d", *j, *i);
 > }
 > }
 > }
 >
 > But I can't see a generic way of accomplishing the same with D's
 > forward-ranges. The following works only if the 'front' property of the
 > range returns a reference:
 >
 > import std.range;
 > import std.stdio;
 >
 > void fun(R)(R r)
 > if (isForwardRange!R)
 > {
 > writeln("idx x y");
 >
 > auto idx = 0;
 > auto rsaved = r.save;
 >
 > for (; !r.empty; r.popFront())
 > {
 > for (auto r2 = rsaved;
 > &r2.front != &r.front; // front could return rvalue
 > r2.popFront())
 > {
 > writefln("%s : %s %s", idx, r2.front, r.front);
 > ++idx;
 > }
 > }
 > }
 >
 > void main()
 > {
 > auto r = [0, 1, 2, 3, 4];
 >
 > fun(r);
 > readln();
 > }
 >
 > Prints:
 > -------
 > idx x y
 > 0 : 0 1
 > 1 : 0 2
 > 2 : 1 2
 > 3 : 0 3
 > 4 : 1 3
 > 5 : 2 3
 > 6 : 0 4
 > 7 : 1 4
 > 8 : 2 4
 > 9 : 3 4
 >
 >
 > If you're wondering what's so special about that ordering of k-subsets,
 > it's because then:
 >
 > idx == x.nCr(1) + y.nCr(2)
 >
 > ...where nCr (n choose r) does what the homonym button in calculators 
does.
 >
 > So, is there a generic way to write a function in D that corresponds to
 > that C++ version, or is this a defect of the D's range concept?

The != operator on the two ranges works for this case:

     for (; !r.empty; r.popFront()) {
         for (auto r2 = rsaved.save; r2 != r; r2.popFront()) {
             writefln("%s : %s %s", idx, r2.front, r.front);
             ++idx;
         }
     }

I tried it with an infinite range that is implemented as a struct, which 
in turn is passed through take():

struct FibonacciSeries
{
     int first = 0;
     int second = 1;

     enum empty = false;

     @property int front() const
     {
         return first;
     }

     void popFront()
     {
         int third = first + second;
         first = second;
         second = third;
     }

     FibonacciSeries save() const
     {
         return this;
     }
}

     fun(FibonacciSeries().take(6));

That worked.

But when I tried it with an infinite range that is implemented as a 
class, the != operator failed because std.range.Take does not implement 
opEquals:

class SquaresRange
{
     int first;

     this(int first = 0)
     {
         this.first = first;
     }

     enum empty = false;

     @property int front() const
     {
         return opIndex(0);
     }

     void popFront()
     {
         ++first;
     }

     SquaresRange save() const
     {
         return new SquaresRange(first);
     }

     int opIndex(size_t index) const
     {
         immutable integerValue = first + cast(int)index;
         return integerValue * integerValue;
     }

// Does have a special opEquals:

     override equals_t opEquals(Object o)
     {
         const rhs = cast(const SquaresRange)o;
         return rhs && (first == rhs.first);
     }
}

// Unfortunately this never stops:
     fun((new SquaresRange()).take(4));

I think if Take had an opEquals() defined, it could apply == explicitly 
on the range member that it uses for its iteration.

This brings up a question: Should all range types implement opEquals() 
for "range equality" as opposed to "identity equality" of the underlying 
range (i.e. Take.source in this case).

Ali