www.digitalmars.com         C & C++   DMDScript  

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

reply d-bugmail puremagic.com writes:
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 puremagic.com
        ReportedBy: sandford jhu.edu


--- Comment #0 from Rob Jacques <sandford 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: -------
Apr 26 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5894


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |andrei metalanguage.com
         Resolution|                            |INVALID


--- Comment #1 from Andrei Alexandrescu <andrei metalanguage.com> 2011-04-26
15:06:14 PDT ---
isSorted!pred assesses whether the range has been sorted by using pred. So what
you want is isSorted!"a < b", which will pass [1, 2, 2, 3].

The bug would stand if adjancentFind!"a <= b" would fail.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 26 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5894


Rob Jacques <sandford jhu.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|patch                       |


--- Comment #2 from Rob Jacques <sandford jhu.edu> 2011-04-26 18:59:03 PDT ---
Thank you for the clarification. I was definitely confused by the docs on this.
What I read was, isSorted tested to see if all element pairs obeyed the
predicate, whereas what it actually tests in whether the range conforms to what
a range sorted by the predicate would be like.

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