Do sorted ranges have any special properties?

[Philippe Sigaud]

On Tue, Jul 27, 2010 at 07:20, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

>
> * slicing a sorted range should produce a sorted range. so your wrapper
> range opIndex must be modified to account for this.
>
> Cool, makes sense.
>
>

Another thing, though I'm not sure it's a good idea, it to have them define
an opIndex[ElementType!R e], that would just either forward to .find() or do
a simple binary search by itself: O(lg(n)) is quite good.

Yeah, isAssociativeRange!R  ;)
But that's blurring the line between container and range, I guess.


In the same vein, a sorted range could optionally define opIn_r that also
promises O(lg(n)) complexity.

As for taking ideas from other languages: in Clojure, data structures for
which it makes sense (maps, sets?) are functions of their element and return
true if the provided value is in the structure. That allows one to use them
as predicate for finding and such, which makes for very clean code, as they
also have encoded literal values.




>  * ditto for .save()
>>
>
> Yah.
>
>
>  * Take(sortedRange, 5) should indicate it's also sorted.
>>
>
> Fortunately take already returns the type of the slice if the range
> supports slice, so that's in place already.


I was about to reply that not all sorted ranges have slicing, but I think
it's better to restrict this to 'rich' ranges: Random-Access and slicing.
So, OK.



>
>  * The same for retro(sorted), but with a predicate being Not!pred (or
>> something akin to this anyway)
>>
>
> Whoa, interesting.


It's the only case where I found that you could act on the predicate without
analyzing it.


>
>
>  * filter ! predicate (sortedRange) is also sorted
>> * stride
>> etc, etc.
>>
>
> Yah... that is all cool. My only reservations are that with what we have
> right now this looks like a lot of manual special casing. By the way,
> chain() with ranges sorted with the same predicate is also sorted...
>
> Then, such an effort would be much better motivated if sorted ranges had
> some really interesting properties. Aside from those discussed - there's not
> a lot of them!
>

Yes, I agree. Maybe for retro() it's interesting, as retro could replace
foreach_reverse...

Btw, should they really be called "sorted" or "ordered"? "sorted" implies
there was a sorting action, which is not always the case. It may very well
have been created that way.

Maybe (just maybe, I'm extending myself there) it's because you tend to use
ranges this way:

- read from a file some content over which you had no control.
- act on the read stuff, most probably sort it to prepare for the real
action
- do the heavy-duty computation.

Whereas I tend to produce my own ranges, so I design them to be
ordered/sorted, always positive or whatever.


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