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.