Add template mixin for Range Primitives using random access

[dlangBugzillaToGithub]

Jesse.K.Phillips+D reported this on 2010-12-14T09:27:14Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=5351

CC List

• edi33416
• Jesse.K.Phillips+D
• lt.infiltrator
• simen.kjaras
• snarwin+bugzilla

Description

This came form a post by Lars on how to remove the boilerplate if you already have a random access interface:

To avoid the boilerplate, you could write a mixin that defines the iteration primitives for you.

mixin template IterationFuncs() { int index; bool empty() { return index == length; } auto front() { return opIndex(index); } void popFront() { ++index; } // ... etc. }

Then you'd just have to define opIndex() and length(), and the mixin does the rest for you.

struct MyRange(T) { T opIndex(int i) { ... } @property int length() { ... } mixin IterationFuncs!(); }

(I haven't tested the code above, so it probably has bugs, but you get the point.)

-Lars

[dlangBugzillaToGithub]

lt.infiltrator commented on 2015-12-09T10:39:27Z

Are you suggesting that this boilerplate mixin should be added to phobos? It seems too inflexible for general use.

[dlangBugzillaToGithub]

Jesse.K.Phillips+D commented on 2016-02-11T00:29:25Z

(In reply to Infiltrator from comment #1)

Are you suggesting that this boilerplate mixin should be added to phobos? It seems too inflexible for general use.

Yes that is what's being requested http://forum.dlang.org/post/rewptfpubrsjifwblump@forum.dlang.org

I agree it isn't flexible, that isn't the point. It only has to do one thing well.

[dlangBugzillaToGithub]

simen.kjaras commented on 2017-10-30T20:16:55Z

The implementation above will fail for this simple case:

MyRange!int a = [1,2,3]; a.popFront(); assert(a[0] == a.front);

It could be made to work for ranges that support slicing, and assignment from the slice to the range:

void popFront() { this = this[1..$]; }

front and empty are then trivial calls to this[0] and length == 0, respectively.

One option that only requires opIndex and length would use a wrapper struct. This solution would leave MyRange as a non-range, though - only its sliced result would be a range:

struct MyRange(T) { T[] arr; T opIndex(size_t idx) { return arr[idx]; }

@property
size_t length() {
    return arr.length;
}

mixin rangeFuncs!();

}

template rangeFuncs() { auto opSlice() { alias TT = typeof(this); struct Result { size_t _index; TT* _range;

        auto front() {
            return (*_range)[_index];
        }

        @property
        bool empty() {
            return _index == _range.length;
        }

        void popFront() {
            _index++;
        }

        auto opIndex(size_t idx) {
            return (*_range)[_index + idx];
        }
    }

    Result result;
    result._range = &this;
    return result;
}

}

unittest { import std.range.primitives : isInputRange; import std.algorithm.comparison : equal;

auto a = MyRange!int([1,2,3,4]);

static assert(!isInputRange!(typeof(a)));
static assert(isInputRange!(typeof(a[])));
assert(a[].equal([1,2,3,4]));

}

In conclusion, opIndex + length is insufficient functionality to turn something into a range.

[dlangBugzillaToGithub]

Jesse.K.Phillips+D commented on 2017-12-01T22:57:41Z

(In reply to Simen Kjaeraas from comment #3)

The implementation above will fail for this simple case:

MyRange!int a = [1,2,3]; a.popFront(); assert(a[0] == a.front);

It could be made to work for ranges that support slicing, and assignment from the slice to the range:

void popFront() { this = this[1..$]; }

Actually this would be a good verification to add to isRandomAccessRange because your correct that this wouldn't match for random access, but such a behavior is fine for forward and bidirectional.

Now that being said, the confusion of having an indexable, non-randomAccessRange with this kind of behavior would be there.

[dlangBugzillaToGithub]

simen.kjaras commented on 2017-12-04T09:55:27Z

isRandomAccessRange is a compile-time construct, and checking foo[0] == foo.front is generally not possible at compile-time. Even if it is, the fact they're equal right now doesn't mean they always will be (consider the fibonacci sequence 1,1,2,3,5,8,13,21..., which would have foo[0] == foo.front after one popFront, but not two).

In addition, as you say, having an indexable range with semantics different from random access ranges is not at all desirable, and a recipe for disaster at some later point.

I agree having this kind of functionality in Phobos would be nice, but I don't see a workable path to that goal. I'm closing this - please reopen if there are revelations that make it possible in the future.

[dlangBugzillaToGithub]

snarwin+bugzilla commented on 2023-03-05T19:00:20Z

Reopening this, since the proposed addition is still useful, even if (as discussed) it would require more from the "host" type than just indexing and length.