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