Do sorted ranges have any special properties?

[Philippe Sigaud]

On Wed, Jul 28, 2010 at 00:18, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

> Tomek Sowiński wrote:
>
>> Andrei Alexandrescu wrote:
>>
>> - All binary search operators (lowerBound, upperBound, equalRange)
>>> should be made members of Sorted!Range. So instead of writing:
>>>
>>> // We know r is sorted, baby
>>> auto r1 = upperBound(r, x);
>>>
>>> you'd write:
>>>
>>> auto r1 = assumeSorted(r).upperBound(x);
>>>
>>
>> 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?
>>
>
> Affirmative.



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.

Also, the .sort properties for arrays may be ditched and use std.algo
instead, by way of a free function in std.array.


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,...


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.
That may be interesting to produce a new template constraint:

template isArrayLike(R) // aka "Rich Range"
{...}



>
>
> This all raises the question: where should this Sorted(R) in the making
>>> go? It's a range so it should go in std.range, but it's mostly a
>>> motivator for algorithms, so it should go in std.algorithm. Tiebreakers?
>>>
>>
>> If members are algorithms then in algorithm...
>>
>
> Yah but the type is a range.


But then, so are Map and Filter.
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.

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.


Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100728/d70257b0/attachment-0001.html>