On Monday, 18 August 2014 at 05:27:11 UTC, Andrei Alexandrescu
wrote:
On 8/17/14, 9:06 AM, Fool wrote:
http://dpaste.dzfl.pl/8fc83cb06de8
Yah, it's a good option. Relevant code:
if (right is whole)
{
//writeln("case identical");
return tuple(right, whole.dropExactly(whole.length));
}
(Prolly it would be better to use "whole.sameHead(right)"
instead of "right is whole". Also whole may not define length
so the actual algo is just a tad different.)
A cleaned-up version is here: http://dpaste.dzfl.pl/a8c36a0c36d0
Trouble is it takes O(n) for that trivial case and for what may
be in all likelihood a useless return (iterate right all the
way through the end and return the empty balance).
Yah, on the other hand you can only expect to get what you pay
for.
The strategy that naturally arises from the basic algorithm is
even worse. In the case at hand, it suggests executing n trivial
swaps.
Loosely related, Xinok wrote a nice piece on in-place merge:
http://goo.gl/AS2P4A. A great use of rotateTail.
Thanks for that link. It's a nice writeup.
-- Fool
