<div class="gmail_quote">On Sat, May 29, 2010 at 23:30, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
On 05/29/2010 03:05 PM, Philippe Sigaud wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br><div class="im">
Does that mean that you changed some other parts recently?<br>
</div></blockquote>
<br>
Not recently, I think I made the last changes before you joined the gang.<br></blockquote><div><br>OK, I wondered whether std.container had reverberations I wasn't aware of.<br>Btw, I plan to play with trees and graphs and algorithms on them. I will modify my code to respect your container interface and see what sticks.<br>
<br><br>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="im">
1. First, I want to define this:<br>
<br>
// inside range type SomeRange<br>
@property SomeRange save();<br>
<br>
<br></div><div class="im">
vote++<br>
That should make it clear you need a forward range for an algorithm.<br>
</div></blockquote>
<br>
Yah.<br></blockquote><div><br>Will the definition of a forward range change to incorporate save, or do you intend to distinguish ranges that can do<br><br> R r2 = r1;<br>and those that have:<br> auto r2 = r1.save;<br>
?<br>Until now, they were one and the same to me.<br><br> <br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
The idea is that save() provides a guaranteed means to take a<br>
snapshot in a range's state. The notable absents are input ranges -<br>
they are unable to define save(), and therefore some algorithms<br>
won't apply to them.<br>
<br>
<br></div><div class="im">
I think many ranges and algorithm that you put in std have a constraint<br>
on InputRange that should be changed to ForwardRange. Most (all?) of the<br>
lazy ones should probably ask for a ForwardRange. Don't forget to update<br>
that part.<br>
</div></blockquote>
<br>
I'm not sure about that. Could you give an example? Why would map() not work with an input range?<br></blockquote><div><br>Because you make a copy of the input range in Map's constructor?<br><br>this(Range input) { _input = input; fillCache; }<br>
<br>I supposed _input = input was not possible with an input range? It's the very definition of a forward range, no?<br><br>An eager version of map could use an InputRange as input:<br><br>template eagerMap(alias fun)<br>
{<br> typeof(unaryFun!fun(ElementType!R.init))[] eagerMap(R)(R r) if (isInputRange!R && !isInfinite!R)<br> {<br> typeof(unaryFun!fun(ElementType!R.init))[] mapped;<br> static if (hasLength!R)<br>
{<br> mapped.length = r.length;<br> foreach(i, elem; r) mapped[i] = unaryFun!fun(elem);<br> }<br> else<br> {<br> foreach(elem; r) mapped ~= unaryFun!fun(elem); // maybe with an ArrayAppender?<br>
}<br> return mapped;<br> }<br>}<br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
2. swapFront, swapBack, and swapAt methods<br>
<br>
// inside range type SomeRange<br>
void swapFront(ref ElementType!SomeRange obj);<br>
void swapBack(ref ElementType!SomeRange obj);<br>
void swapAt(size_t i, ref ElementType!SomeRange obj);<br>
<br></div></blockquote>
They will be methods because they must be primitive operations of the respective ranges. However, there will be wrappers like this:<br>
<br>
// at module scope<br>
void swapFront(Range)(Range r1, Range r2)<br>
{<br>
static if (is(typeof(&(r1.front)) == ElementType!(Range)*)) {<br>
swap(r1.front, r2.front);<br>
} else {<br>
static assert(is(typeof(&(r1.swapFront)), "Cannot swap ranges");<br>
r1.swapFront(r2);<br>
}<br>
}<br></blockquote><div><br>OK. I really like this possibility to test for members and activate them when possible. Maybe it could be abstracted away into a Select-like template?<br><br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
3. sameFront()<br>
<br>
The gnarly bringToFront() algorithm needs the primitive:<br>
<br>
// inside range type SomeRange<br>
bool sameFront(SomeRange another);<br>
<br>
I think it's necessary for future algorithms as well. It's an<br>
optional primitive. In particular, if front() returns by reference<br>
it's easy to infer that two ranges have the same front by comparing<br>
the addresses of their front()s.<br>
<br></div><div class="im">
And if front does not return by ref? Do you then define the fronts to be<br>
different or compare the values?<br>
</div></blockquote>
<br>
If front() does not return by ref, the range should define sameFront() as a member. If it doesn't, it won't have access to a number of algorithms.</blockquote><div><br>OK. So it's really sameFront and not equalFront or somesuch.<br>
<br><br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
About returning by ref, did you try to use 'auto ref'? I think I tried<br>
the day the feature appeared, without success, IIRC. Many ranges in<br>
Phobos return by ref and won't compose with other ranges because of that.<br>
</blockquote>
<br></div>
Yah, auto ref was meant for that kind of work. But generally note that certain ranges actively refuse to return by ref in order to not expose addresses of their elements. Such ranges are fit for perfectly encapsulated containers.<br>
</blockquote><div><br>I was thinking of frustrating obstacles like:<br><br>auto m = map!"a*a"([0,1,2,3]);<br>auto c = cycle(m); // won't compile, m.front is not an lvalue, whereas c.front asks for one.<br><br>
Putting auto ref front() {...} in Cycle does not change anything. Too bad.<br><br><br>Philippe<br><br></div></div>