On 06/23/2013 01:34 PM, monarch_dodra wrote:
> ...
>
> But as soon as you need an algorithm that actually *handles* ranges:
> swaps them, merges them, searches in them and splices them, then things
> get hairy.
>
> For example, try implementing a sort (either merge or q) with a
> non-sliceable range... very very hard...

Challenge accepted.

http://dpaste.dzfl.pl/4407c36f

On Sunday, 23 June 2013 at 11:34:25 UTC, monarch_dodra wrote:
> For example, try implementing a sort (either merge or q) with a non-sliceable range... very very hard...

https://github.com/deadalnix/Dsort/blob/master/sort/bubble.d

On Sunday, 23 June 2013 at 01:34:53 UTC, Andrei Alexandrescu wrote:
> On 6/22/13 2:58 PM, monarch_dodra wrote:
>> long story short: we don't have rfind. C++ does.
>
> We do, just that it's for random-access ranges. C++ offers it for bidirectional ranges too. We could of course support it if bidirectional ranges were required to have something like r1.before(r2) that, assuming r2 is reachable from r1, returns the portion in r1 that's before r2.
>
> Andrei

How efficiently could before() be implemented?

On 06/24/2013 09:02 AM, deadalnix wrote:
> On Sunday, 23 June 2013 at 11:34:25 UTC, monarch_dodra wrote:
>> For example, try implementing a sort (either merge or q) with a
>> non-sliceable range... very very hard...
>
> https://github.com/deadalnix/Dsort/blob/master/sort/bubble.d

(That's neither merge- nor quicksort.)

Note:

https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L7952

On 06/23/2013 11:20 PM, Timon Gehr wrote:
> On 06/23/2013 01:34 PM, monarch_dodra wrote:
>> ...
>>
>> But as soon as you need an algorithm that actually *handles* ranges:
>> swaps them, merges them, searches in them and splices them, then things
>> get hairy.
>>
>> For example, try implementing a sort (either merge or q) with a
>> non-sliceable range... very very hard...
>
> Challenge accepted.
>
> http://dpaste.dzfl.pl/4407c36f

(stable merge sort, comparison function as template argument: http://dpaste.dzfl.pl/9bf21773)

On Monday, 24 June 2013 at 23:11:29 UTC, Timon Gehr wrote:
> On 06/23/2013 11:20 PM, Timon Gehr wrote:
>> On 06/23/2013 01:34 PM, monarch_dodra wrote:
>>> ...
>>>
>>> But as soon as you need an algorithm that actually *handles* ranges:
>>> swaps them, merges them, searches in them and splices them, then things
>>> get hairy.
>>>
>>> For example, try implementing a sort (either merge or q) with a
>>> non-sliceable range... very very hard...
>>
>> Challenge accepted.
>>
>> http://dpaste.dzfl.pl/4407c36f
>
> (stable merge sort, comparison function as template argument: http://dpaste.dzfl.pl/9bf21773)

Nice. You could probably get some better performance with a takeExactly (heck, take exactly would be a *better* choice, since it asserts there is actually what you asked for, rather than "up to").

All I can say is well done, though I still feel the use of "take"s are clutches that shouldn't actually be needed, and are making the overall code more complicated (and slower) than it should be.

It can be done, but I find it to be tougher and less enjoyable than with actual iterators: You iterate until you reach your pivot, and then you should be able to simply have two ranges on each side.

On Monday, 24 June 2013 at 22:27:19 UTC, Brad Anderson wrote:
> On Sunday, 23 June 2013 at 01:34:53 UTC, Andrei Alexandrescu wrote:
>> On 6/22/13 2:58 PM, monarch_dodra wrote:
>>> long story short: we don't have rfind. C++ does.
>>
>> We do, just that it's for random-access ranges. C++ offers it for bidirectional ranges too. We could of course support it if bidirectional ranges were required to have something like r1.before(r2) that, assuming r2 is reachable from r1, returns the portion in r1 that's before r2.
>>
>> Andrei
>
> How efficiently could before() be implemented?

In terms of efficiency, it would really depend on the range that implements it, but I'd say "o(1)": cheap. The problems are (imo):
*defining the exact semantics that go with it.
*defining the traits that go with it.

One big hurdle (I think), is that there is no way to provide a default implementation, even for RA ranges with slicing. And that's very bad.

I'm going to get bashed for this, but I think the concept of "iterable" range would be a much simpler concept: Far be for me to want iterators as the norm (puke), but being able to temporarily view a range (if possible), as two end points, before re-creating the range from said points, has some very simple, and easy to understand, yet efficient, semantics.

It's really the only way to provide slicing for ranges that aren't RA...

Eg:
Range r;
Range r10 = Range(r.begin, advance(r.begin, 10));

On Mon, Jun 24, 2013 at 11:46 PM, monarch_dodra <monarchdodra@gmail.com>wrote:

> On Monday, 24 June 2013 at 22:27:19 UTC, Brad Anderson wrote:
>
>> On Sunday, 23 June 2013 at 01:34:53 UTC, Andrei Alexandrescu wrote:
>>
>>> On 6/22/13 2:58 PM, monarch_dodra wrote:
>>>
>>>> long story short: we don't have rfind. C++ does.
>>>>
>>>
>>> We do, just that it's for random-access ranges. C++ offers it for bidirectional ranges too. We could of course support it if bidirectional ranges were required to have something like r1.before(r2) that, assuming r2 is reachable from r1, returns the portion in r1 that's before r2.
>>>
>>> Andrei
>>>
>>
>> How efficiently could before() be implemented?
>>
>
> In terms of efficiency, it would really depend on the range that
> implements it, but I'd say "o(1)": cheap. The problems are (imo):
> *defining the exact semantics that go with it.
> *defining the traits that go with it.
>
> One big hurdle (I think), is that there is no way to provide a default implementation, even for RA ranges with slicing. And that's very bad.
>
> I'm going to get bashed for this, but I think the concept of "iterable" range would be a much simpler concept: Far be for me to want iterators as the norm (puke), but being able to temporarily view a range (if possible), as two end points, before re-creating the range from said points, has some very simple, and easy to understand, yet efficient, semantics.
>
> It's really the only way to provide slicing for ranges that aren't RA...
>
> Eg:
> Range r;
> Range r10 = Range(r.begin, advance(r.begin, 10));
>

That seems possible in some cases, but not all.

the primitives for iterators should be roughly:
void iterator.popFront() (or ++)
bool iterator.equals(Iterator other);
auto iterator.front();

The tricky part is to define
bool iterator.equals(Iterator other);

there are cases where this is possible:
* range defined over an array
* range over elements assumed to be unique (interesting case)

but I don't see how that would work in general.
thoughts?

On 06/25/2013 08:39 AM, monarch_dodra wrote:
> On Monday, 24 June 2013 at 23:11:29 UTC, Timon Gehr wrote:
>> On 06/23/2013 11:20 PM, Timon Gehr wrote:
>>> On 06/23/2013 01:34 PM, monarch_dodra wrote:
>>>> ...
>>>>
>>>> But as soon as you need an algorithm that actually *handles* ranges:
>>>> swaps them, merges them, searches in them and splices them, then things
>>>> get hairy.
>>>>
>>>> For example, try implementing a sort (either merge or q) with a
>>>> non-sliceable range... very very hard...
>>>
>>> Challenge accepted.
>>>
>>> http://dpaste.dzfl.pl/4407c36f
>>
>> (stable merge sort, comparison function as template argument:
>> http://dpaste.dzfl.pl/9bf21773)
>
> Nice. You could probably get some better performance with a takeExactly
> (heck, take exactly would be a *better* choice, since it asserts there
> is actually what you asked for, rather than "up to").
>

Good point, but takeExactly currently is not a better choice due to its poor quality of implementation.

https://github.com/D-Programming-Language/phobos/blob/master/std/range.d#L2904

(eg. the msort will no longer work on the DList range when takeExactly is used rather than take.)

> All I can say is well done, though I still feel the use of "take"s are
> clutches that shouldn't actually be needed,

Note that qsort does not use take.

> and are making the overall code more complicated (and slower)

msort could use a fixed takeExactly or manually keep track of range lengths. (msort can be significantly improved in general, it's just a quick hack.)

> than it should be.
>
> It can be done, but I find it to be tougher and less enjoyable than with
> actual iterators: You iterate until you reach your pivot, and then you
> should be able to simply have two ranges on each side.

I see your point, but this primitive is not required, nor does every forward range support it in a natural way.

On Tuesday, June 25, 2013 13:47:19 Timon Gehr wrote:
> Good point, but takeExactly currently is not a better choice due to its poor quality of implementation.

What's the problem with takeExactly's implementation?

- Jonathan M Davis