Swap front for char[] input ranges

Ali Çehreli via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Mon Dec 19 12:26:26 PST 2016


On 12/19/2016 06:09 AM, RazvanN wrote:
 > On Monday, 19 December 2016 at 12:25:02 UTC, Ali Çehreli wrote:
 >> On 12/19/2016 02:41 AM, RazvanN wrote:
 >> > [...]
 >>
 >> As your comments make it clear below, they cannot be InputRanges.
 >>
 >> > [...]
 >> swapping code
 >> >          [...]
 >>
 >> Obivously, tmp1 and tmp2 are unusued there. :)
 >>
 >> > [...]
 >> passed.
 >> > [...]
 >> state
 >> > [...]
 >> is:
 >> > [...]
 >> input ranges
 >> > [...]
 >>
 >> Not possible... It's ok to use something similar to the following
 >> template constraint:
 >>
 >> void foo(R1, R2)(R1 r1, R2 r2)
 >> if ((hasSwappableElements!R1 && hasSwappableElements!R2) ||
 >>     (hasLvalueElements!R1 && hasLvalueElements!R2)) {
 >>     // ...
 >> }
 >>
 >> Ali
 >
 > In this case, the bringToFront function [1] should not accept char[]
 > as parameters? Or a special path should be added in the function, so
 > that char[] are treated specially?
 >
 > [1] http://dlang.org/phobos/std_algorithm_mutation.html#bringToFront

First, thanks to you and to your colleagues very much for improving D 
with these fixes. :)

I think you're working on the following bug:

   https://issues.dlang.org/show_bug.cgi?id=16959

Regarding the compilation error inside swapFront, its template 
constraints should be fixed as I suggested earlier. It cannot work with 
any two InputRanges. I think it warrants its separate bug.

private void swapFront(R1, R2)(R1 r1, R2 r2)
     if (isInputRange!R1 && isInputRange!R2)
{
     static if (is(typeof(swap(r1.front, r2.front))))
     {
         swap(r1.front, r2.front);
     }
     else
     {
         auto t1 = moveFront(r1), t2 = moveFront(r2);
         r1.front = move(t2);
         r2.front = move(t1);
     }
}

Regarding bringToFront:

1) Reading its documentation, bringToFront() seems to be an algorithms 
that mutates its ranges (not just give a brought-to-front view of 
existing data). If so, its argument cannot simply be an InputRange 
because there are InputRanges out there where you cannot write it their 
.front. (char[] is just one example.):

size_t bringToFront(Range1, Range2)(Range1 front, Range2 back)
     if (isInputRange!Range1 && isForwardRange!Range2)
{
     // ...
}

Its template constraint must also be changed to include a combination of 
hasLvalueElements() and hasMobileElements().

2) After fixing that, a char[] can indeed bring characters to front but 
it would be an expensive operation where a multi-byte Unicode character 
would necessarily move a single-byte Unicode character to the right. 
(Additionally, depending on its length, the first argument may allow 
only a partial UTF-8 encoding at its end. Fail! :) )

I don't know how to allow or encode such an expensive operation which is 
outside the documented "Ο(max(front.length, back.length))" complexity of 
bringToFront(). If it were me, I would look for possibilities to change 
the behavior and make bringToFront() a non-mutating algorithm.

What do others think?

Ali



More information about the Digitalmars-d-learn mailing list