www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Adapting foreign iterators to D ranges

reply =?UTF-8?B?Q2hsb8Op?= <chloekek use.startmail.com> writes:
Assume a third-party API of the following signature:

     T* next(I iter);

which advances an iterator of sorts and returns the next element, or 
null when iteration is done. No other information about the state of the 
iterator is available.

I wish to adapt this interface to a forward range for use with foreach 
and Phobos' range utilities. This amounts to implementing empty, front, 
and popFront, in terms of next and some state. But there is a choice to 
be made regarding the first call to next.

One could call next during range construction:

     struct Range
     {
         private I iter;
         private T* current;
         this(I iter) { this.iter = iter; current = next(iter); }
         bool empty() const => current is null;
         inout(T)* front() inout => current;
         void popFront() { current = next(iter); }
     }

Or do not call it until the first call to empty:

     struct Range
     {
         private bool initialized;
         private I iter;
         private T* current;
         this(I iter) { this.iter = iter; }
         bool empty()
         {
             if (!initialized) {
                 current = next(iter);
                 initialized = true;
             }
             return current is null;
         }
         inout(T)* front() inout => current;
         void popFront() { current = next(iter); }
     }

The first implementation has the advantage is being simpler and empty 
being const, but has the downside that next is called even if the range 
ends up not being used. Is either approach used consistently across the 
D ecosystem?
Apr 22
next sibling parent Alexandru Ermicioi <alexandru.ermicioi gmail.com> writes:
On Monday, 22 April 2024 at 11:36:43 UTC, Chloé wrote:

 The first implementation has the advantage is being simpler and 
 empty being const, but has the downside that next is called 
 even if the range ends up not being used. Is either approach 
 used consistently across the D ecosystem?


You can also place initialization logic inside front, then empty 
could become const.

I don't think there is a preffered way of initializing such 
ranges, so imho consider what's best for your use case.
Apr 22
prev sibling next sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On Monday, 22 April 2024 at 11:36:43 UTC, Chloé wrote:


 The first implementation has the advantage is being simpler and 
 empty being const, but has the downside that next is called 
 even if the range ends up not being used. Is either approach 
 used consistently across the D ecosystem?


I always go for the simplest approach. So that means, pre-fill in 
the constructor.

Yes, the downside is, if you don't use it, then the iterator has 
moved, but the range hasn't. But returning to the iterator after 
using the range is always a dicey proposition anyway.

The huge benefit is that all the functions become simple and 
straightforward.

But there is no "right" approach. And using composition, you may 
be able to achieve all approaches with wrappers. Phobos does 
various things depending on what people thought was good at the 
time. It sometimes causes some very unexpected behavior.

I recommend always using the same approach for the same library, 
that way your users know what to expect!

-Steve
Apr 22
prev sibling parent reply cc <cc nevernet.com> writes:
On Monday, 22 April 2024 at 11:36:43 UTC, Chloé wrote:

 I wish to adapt this interface to a forward range for use with 
 foreach and Phobos' range utilities. This amounts to 
 implementing empty, front, and popFront, in terms of next and 
 some state. But there is a choice to be made regarding the 
 first call to next.


Just to offer an alternative solution (since it sometimes gets 
overlooked), there is also the `opApply` approach.  You don't get 
full forward range status, and checking whether it's empty 
essentially requires doing something like std.algorithm 
`walkLength`, but if all you need is basic iteration, it can be a 
simpler solution:

```d
struct Range {
	private I iter;
	this(I iter) { this.iter = iter; }
	int opApply(scope int delegate(T* t) dg) {
		while (auto current = next(iter)) {
			if (auto r = dg(current))
				return r;
		}
		return 0;
	}
}
void main() {
	I someIter; // = ...
	auto range = Range(someIter);
	foreach (const t; range) {
		writeln(*t);
	}
}
```
Apr 22
parent reply Salih Dincer <salihdb hotmail.com> writes:
On Tuesday, 23 April 2024 at 06:02:18 UTC, cc wrote:

 Just to offer an alternative solution (since it sometimes gets 
 overlooked), there is also the `opApply` approach.  You don't 
 get full forward range status, and checking whether it's empty 
 essentially requires doing something like std.algorithm 
 `walkLength`, but if all you need is basic iteration, it can be 
 a simpler solution:


Yes, `opApply()` works! You just need to use `do while()` instead 
of `while()` because it skips the first item.

```d
struct Node
{
   int item;
   Node* next;
}

class List
{
   Node* root, iter;

   this(int item = 0)
   {
     iter = new Node(item, null);
     root = iter;
   }

   List dup()
   {
     auto backup = new List();
     backup.root = root;
     backup.iter = iter;

     return backup;
   }

   void insertFront(T)(T item)
   {
     (*iter).next = new Node(item, null);
     this.Next;
   }

   bool empty() const => iter is null;
   auto front() inout => iter;
   auto popFront()    => iter = this.Next;
   auto getItem()     => iter.item;
   auto rewind()      => iter = root;
}

auto Next(List list) => list.iter = list.iter.next;
auto gaussian(T)(T n)=> (n * n + n) / 2;

void main()
{
   import std.stdio;
   enum LIMIT = 10;

   auto list = new List(1);
   foreach(t; 2 .. LIMIT + 1)
   {
     list.insertFront(t);
   }

   auto tmp = list.dup;
   list.rewind();

   size_t sum;
   do sum += list.getItem; while(list.Next);
   assert(gaussian(LIMIT) == sum);

   sum.writeln; // 55

   auto next = LIMIT + 1;
   tmp.insertFront(next);
   tmp.rewind();
   sum = 0;

   foreach(t; tmp) sum += t.item;
   assert(gaussian(LIMIT) + next == sum);

   sum.writeln; // 66
   tmp.rewind();

   auto range = Range(tmp);

   foreach(r; range) r.item.write(" ");
   writeln; //  2 3 4 5 6 7 8 9 10 11
   // ? (1) --^
}

struct Range
{
   private List iter;

   int opApply(scope int delegate(Node* t) dg)
   {
     while(auto current = iter.Next)
     {
       if (auto r = dg(current))
         return r;
     }
     return 0;
   }
}
```

SDB 79
Apr 23
parent cc <cc nevernet.com> writes:
On Wednesday, 24 April 2024 at 05:08:25 UTC, Salih Dincer wrote:

 Yes, `opApply()` works! You just need to use `do while()` 
 instead of `while()` because it skips the first item.


It depends on the type of structure being consumed, if it 
provides "next" as a direct pointer then yeah you would need to 
consume the item first before iterating to the next in line.  
However some APIs provide an opaque iterator type where you call 
a "next" method to get the first element, IIRC Lua does something 
like this.
Apr 24