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.
