www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 12188] New: std.algorithm.nextPermutation requires random access

reply d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12188

           Summary: std.algorithm.nextPermutation requires random access
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: peter.alexander.au gmail.com


--- Comment #0 from Peter Alexander <peter.alexander.au gmail.com> 2014-02-17
12:20:14 PST ---
The constraints says it requires bidirectional, but it actually requires random
access due to this line:

reverse(takeExactly(retro(range), n));

'reverse' requires a bidirectional range, but 'takeExactly' on a bidirectional
range returns a forward range. You need to provide a random access range to
'takeExactly' to get bidirectional, so this becomes a requirement of
'nextPermutation'.

nextPermutation must be modified to support bidirectional ranges. Changing the
constraint to random access is not an acceptable fix.

Here's a simple test case where a bidirectional range fails:

---------------------
import std.algorithm, std.array;

struct MyRange
{
    int[] a = [1, 2, 3];
     property
    {
        auto ref front() { return a.front; }
        auto ref back() { return a.back; }
        auto empty() { return a.empty; }
        auto save() { return MyRange(a); }
    }
    void popFront() { a.popFront(); }
    void popBack() { a.popBack(); }
}

void main()
{
    MyRange r;
    nextPermutation(r);
} 
---------------------

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 17 2014
next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12188



--- Comment #1 from Peter Alexander <peter.alexander.au gmail.com> 2014-02-18
12:51:15 PST ---
BTW, you may already know this, but it's impossible to solve this with the
current range primitives. See the discussion here:

http://www.digitalmars.com/d/archives/digitalmars/D/Retrieving_the_traversed_range_116085.html#N116085

To summarise the discussion: it is impossible currently, and Andrei recommends
two approaches:

1. Just make it random access only for now.

2. Define a new primitive: allBefore, like this:

R allBefore(R)(R all, R tail) if (isRandomAccessRange!R && hasLength!R)
{
     // assume tail starts somewhere inside all and ends where all ends
     enforce(all.length >= tail.length);
     return all[0 .. all.length - tail.length);
}

R allBefore(R)(R all, R tail)
         if (isBidirectionalRange!R &&
             is(typeof(all.allBeforeImpl(tail)) : R))
{
     return all.allBeforeImpl(tail);
}

And require that for nextPermutation

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 18 2014
prev sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12188



--- Comment #2 from hsteoh quickfur.ath.cx 2014-02-18 13:14:25 PST ---
Hmm this sucks. It didn't occur to me that takeN on a bidirectional range
doesn't return a bidirectional range. :-(  In retrospect, it makes sense (takeN
doesn't know the internals of the range, so it has no way to know what .back
and .popBack should do when only the first N elements are desired).

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 18 2014