[Issue 5894] New: [patch] std.algorithm.isSorted doesn't handle monotonicity (i.e. "<=")

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=5894

           Summary: [patch] std.algorithm.isSorted doesn't handle
                    monotonicity (i.e. "<=")
           Product: D
           Version: future
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Keywords: patch
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: sandford at jhu.edu


--- Comment #0 from Rob Jacques <sandford at jhu.edu> 2011-04-26 13:24:14 PDT ---
I was trying to use isSorted to check for monotonicity. For example, [1,2,2,3]
is monotonically increasing, but not strictly increasing. I was therefore
trying to use isSorted!"a <= b"( [1,2,2,3] ), which failed. Looking at the
implementation of isSorted:

bool isSorted(alias less = "a < b", Range)(Range r) if (isForwardRange!(Range))
{
    // @@@BUG@@@ Should work with inlined predicate
    bool pred(ElementType!Range a, ElementType!Range b)
    {
        return binaryFun!less(b, a);
    }
    return findAdjacent!pred(r).empty;
}

which would attempts to validate that all pairs in r conform to "a <= b" by not
finding any "b <= a" pairs, which isn't logically correct. I've written a
one-line patch below to fix this error. It changes the test from not finding "b
<= a" pairs to not finding !"a <= b" pairs (i.e. any pairs ! conforming to the
predicate).

bool isSorted(alias less = "a < b", Range)(Range r) if (isForwardRange!(Range))
{
    // @@@BUG@@@ Should work with inlined predicate
    bool pred(ElementType!Range a, ElementType!Range b)
    {
+        return !binaryFun!less(a, b);
-        return binaryFun!less(b, a);
    }
    return findAdjacent!pred(r).empty;
}

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