www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - When does take modify the underlying iterator?

reply cy <dlang verge.info.tm> writes:
InputRanges that are not ForwardRanges seem to lack a possibly 
crucial operation. I want to start with an arbitrary range, take 
1 from it, then process the rest. But there doesn't seem to be 
any way to do that, because there's no way to tell whether "take" 
will advance the range, or whether it will leave the range as-is.

When you know a range implements front, empty, and popFront, and 
you take from that range, there seems to be a secret requirement 
that the iterator supports save() via copy constructor. And if it 
doesn't... your program just breaks silently when you drop 
elements that haven't been processed yet.

Is there some way around that, that I'm not aware of?

struct CertainlyNotAForwardRange(A) {
	static int i = 0;
	A a;
	auto front() {
		return a[i];
	}
	auto empty() {
		return i == a.length;
	}
	auto popFront() {
		++i;
	}
}

struct SecretlyForwardRange(A) {
	A a;
	int i = 0;
	auto front() {
		return a[i];
	}
	auto empty() {
		return i == a.length;
	}
	auto popFront() {
		++i;
	}
}

auto failhard(T)(T iter) {
	import std.stdio;
	import std.range: take, drop;
	import std.array: array;

	writeln("We have some range:");
	writeln(typeid(T));
	writeln("We take 1 from it...");
	writeln(iter.take(1));
	writeln("The rest of the range has:");
	writeln(iter.drop(1).array);
	writeln("");
}	

void main() {
	auto arr = [0, 1, 2, 3];
	failhard(arr);
	failhard(SecretlyForwardRange!(typeof(arr))(arr));
	failhard(CertainlyNotAForwardRange!(typeof(arr))(arr));
}
Aug 16 2016
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 8/16/16 5:01 PM, cy wrote:

     writeln("We take 1 from it...");
     writeln(iter.take(1));
     writeln("The rest of the range has:");
     writeln(iter.drop(1).array);


The fact that copying a forward range is generally the same operation as 
.save is a huge problem. But there isn't really a way to deal with that.

In any case, I would probably write the code in the following way:

static if(isForwardRange!(typeof(iter)))
{
    writeln(iter.save.take(1));
    writeln(iter.drop(1)); // not sure why .array was here
}
else
{
    writeln(iter.take(1));
    writeln(iter);
}

But this may not work for any input range, since any time you copy the 
range, you are copying internal state that may cache an element or more.

What we need is a take function that accepts input ranges by reference, 
so it modifies the original. Then things get very strange and clunky.

-Steve
Aug 16 2016
parent cy <dlang verge.info.tm> writes:
On Tuesday, 16 August 2016 at 21:13:38 UTC, Steven Schveighoffer 
wrote:

 static if(isForwardRange!(typeof(iter)))



 But this may not work for any input range, since any time you 
 copy the range, you are copying internal state that may cache 
 an element or more.


Yes, that was the problem with SecretlyForwardRange, is that it 
acts like a ForwardRange because it's implicitly copied, but 
doesn't implement .save, so isForwardRange would return false.


 What we need is a take function that accepts input ranges by 
 reference, so it modifies the original.


What we need is a way to split a range into two sub-ranges, the 
head and the tail.

auto res = a.take(1)
auto head = res.head
a = res.tail

...or something. Like what findSplit does, but with an index 
instead of a delimiter.
Aug 16 2016
prev sibling next sibling parent Cauterite <cauterite gmail.com> writes:
On Tuesday, 16 August 2016 at 21:01:14 UTC, cy wrote:


This has also been annoying me lately, so I came up with this 
workaround:

InputRange!T X = inputRangeObject(Src);

X.take(6); // remove+return items 0 to 5
X.take(3); // remove+return items 6 to 8



 Aug 16 2016



prev sibling  parent reply ag0aep6g <anonymous example.com>  writes:


On 08/16/2016 11:01 PM, cy wrote:

 auto failhard(T)(T iter) {


[...]

     writeln("We take 1 from it...");
     writeln(iter.take(1));


This line may or may not pop the first element of the original iter.

That's because copying a range may or may not be same as calling .save 
on it. For many forward ranges it is the same, and then the original 
iter is unaffected. For true input ranges (that cannot be forward 
ranges), it cannot be the same. In that case, the original iter is 
invalidated, and must not be used anymore.

Whenever you want to keep using a range after passing it to some 
function, either .save it or make sure it acts like a reference. You've 
got reference behavior when the function uses a `ref` parameter, or when 
the range is a class/pointer, or when you use std.range.refRange to 
force it.


     writeln("The rest of the range has:");
     writeln(iter.drop(1).array);
     writeln("");
 }


As for the example, you can rewrite it like so:

----
auto failhard(T)(T iter) {
     import std.stdio;
     import std.range: take, drop, refRange;

     writeln("We have some range:");
     writeln(typeid(T));
     writeln("We take 1 from it...");
     writeln(refRange(&iter).take(1));
     writeln("The rest of the range has:");
     writeln(iter);
     writeln("");
}
----

Also need to add  property to `front` and `empty` in the ranges. 
refRange is picky about this.



 Aug 16 2016



  parent reply ag0aep6g <anonymous example.com>  writes:


On 08/16/2016 11:34 PM, ag0aep6g wrote:

 As for the example, you can rewrite it like so:

 ----
 auto failhard(T)(T iter) {
     import std.stdio;
     import std.range: take, drop, refRange;

     writeln("We have some range:");
     writeln(typeid(T));
     writeln("We take 1 from it...");
     writeln(refRange(&iter).take(1));
     writeln("The rest of the range has:");
     writeln(iter);
     writeln("");
 }
 ----

 Also need to add  property to `front` and `empty` in the ranges.
 refRange is picky about this.


My apologies, that actually prints "[0, 1, 2, 3]" in the array case. I 
don't what's going on. That should work. Maybe I'm misunderstanding 
something about refRange.



 Aug 16 2016



  parent  ag0aep6g <anonymous example.com>  writes:


On 08/16/2016 11:41 PM, ag0aep6g wrote:

 My apologies, that actually prints "[0, 1, 2, 3]" in the array case. I
 don't what's going on. That should work. Maybe I'm misunderstanding
 something about refRange.


Oh, I see. `take` is being clever. When possible, it slices the given 
range instead of popping it. Can't use `take` here then. May have to 
write a custom one that acts more predictable. Or maybe std.range.take 
can be fixed.



 Aug 16 2016