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?

Although, the only case, where this would be
a problem is with a range of type T, where:

1) It's impossible to provide random access to T
2) T can't return a reference from its 'front' property
3) T is a finite range (not infinite)
4) 'front' property may return the same value at different indexes

Something like:

struct R
{
    int _value = 0;
    int _round = 1;

    @property bool empty() const
    {
        return _value == 100 && _round == 2;
    }

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

    void popFront()
    {
        if (_value == 99)
        {
            if (_round == 1)
            {
                _value = 0;
                _round = 2;
            }
            else
            {
                _value = 100;
            }
        }
        else
        {
            ++_value;
        }
    }
}

Albeit, in this simple example it would be possible to provide random access to R, because the sequential definition of it could be easily replaced with an algebraic one. But for a more complex sequential definition, it might not be possible. So, the situation, where this (potential) defect of the range concept would be a problem, seems very rare, but it's nevertheless possible.

Scratch all that. Even if range's 'front' property returned a reference, there's no guarantee that it references the same data as a copy of that range (created through the 'copy' property). So, my D version of that C++ function simply doesn't work... not even if 'front' is guaranteed to return a reference. Now this seems like a serious defect to me, please tell me I'm wrong.

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

On Friday, 5 October 2012 at 09:37:51 UTC, Ali Çehreli wrote:
>
> 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).

But even if the range concept was altered so that all ranges have to implement opEquals(), it wouldn't be a very satisfying solution. That's because opEquals() could be a very slow function for some ranges, e.g. forward ranges, where you have to check each element's equality one by one. Using opEquals() like that could make traversing those subset iterations very slow.

Uh... never mind. I guess this one was kind of like a magic trick; the solution was so obvious and simple I neglected it:


void fun(R)(R r)
    if (isForwardRange!R)
{
    writeln("idx x y");

    auto idx = 0;
    auto rsaved = r.save;

    for (size_t n = 0; !r.empty; r.popFront(), ++n)
    {
        size_t n2 = 0;

        for (auto r2 = rsaved; n2 < n; r2.popFront(), ++n2)
        {
            writefln("%s : %s %s", idx, r2.front, r.front);
            ++idx;
        }
    }
}