<div class="gmail_quote"><br><br><div class="gmail_quote">On Wed, Jul 28, 2010 at 00:18, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
<div class="im">Tomek Sowiński wrote:<br><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
Andrei Alexandrescu wrote:<br><br><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
- All binary search operators (lowerBound, upperBound, equalRange)<br>should be made members of Sorted!Range. So instead of writing:<br><br>// We know r is sorted, baby<br>auto r1 = upperBound(r, x);<br><br>you'd write:<br>
<br>auto r1 = assumeSorted(r).upperBound(x);<br></blockquote><br>Some of std.algorithm (e.g. find, partition) can profit on sortedness, others (e.g. group, setIntersection, setDifference, nWayUnion) require it. Do you want to put *all* of them as members of Sorted?<br>
</blockquote><br></div>Affirmative.</blockquote><div><br></div><div><br></div><div>btw, std.algorithm.sort does an in-place sort and as such does not affect the input type. It might be interesting to call it sortInPlace instead (or anything that has your fancy) and have sort() _returns_ a Sorted!Range and automatically get all the goodies.</div>
<div><br></div><div>Also, the .sort properties for arrays may be ditched and use std.algo instead, by way of a free function in std.array.</div><div><br></div><div><br></div><div>And, while I'm at it, most of these primitives do not work for infinite ranges, which may perfectly be sorted, have random-access and slicing. Case in point: the natural numbers 0,1,2,...</div>
<div><br></div><div><br></div><div>I guess infinity will not be accepted in that case... If that's so, my impression is that most algorithms will require something very array-like: random-access && hasLength && hasSlicing && !isInfinite.</div>
<div>That may be interesting to produce a new template constraint:</div><div><br></div><div>template isArrayLike(R) // aka "Rich Range"</div><div>{...}</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
<div class="im"><br><br><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
<blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
This all raises the question: where should this Sorted(R) in the making<br>go? It's a range so it should go in std.range, but it's mostly a<br>motivator for algorithms, so it should go in std.algorithm. Tiebreakers?<br>
</blockquote><br>If members are algorithms then in algorithm...<br></blockquote><br></div>Yah but the type is a range.</blockquote><div><br></div><div>But then, so are Map and Filter. </div><div>Personally, I do not consider them algorithms per se, they are too low-level: they're building blocks and, as ranges, should go in std.range. LevenshteinDistance or bringToFront, those are algorithms. </div>
<div><br></div><div>My own experience of this is that most of the time, I import std.range _only_ to get map/filter/reduce. That is, without reaching for a real algorithm. They are in std.algo for 'historical' reasons, because std.algo precedes std.range.</div>
<div><br></div><div><br></div><div>Philippe</div><div><br></div><div><br></div></div></div>