Boost::documentation == false



  • Documentation for boost::is_sorted:

    For the predicate version the return value is true is and only if for each adjacent elements [x,y] the expression pred(x,y) is true.

    Implementation:

        template <typename ForwardIterator, typename Pred>
        bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p )
        {
            return boost::algorithm::is_sorted_until (first, last, p) == last;
        }
    

    Function they used above:

        template <typename ForwardIterator, typename Pred>
        ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p )
        {
            if ( first == last ) return last;  // the empty sequence is ordered
            ForwardIterator next = first;
            while ( ++next != last )
            {
                if ( p ( *next, *first ))
                    return next;
                first = next;
            }
            return last;    
        }
    

    ...Okay, it might not be immediately obvious, but if we use "<" operator instead of predicate, return bool instead of iterator, and make the code more readable, it should be clear what's my problem:

        template <typename ForwardIterator>
        bool is_sorted ( ForwardIterator first, ForwardIterator last)
        {
            if ( first == last ) return true;  // the empty sequence is ordered
    
            for (ForwardIterator x = first, y = ++first; y != last; x = y, ++y)
            {
                if ( *y < *x )
                {
                    return false;
                }
            }
            return true;    
        }
    

    Fucking liars.


  • @Gaska said:

    it should be clear what's my problem:

    Could you make it a little clearer please? I'm assuming the issue isn't the extra ) in the if.



  • Since you mocked my mistake, I assume you know the actual answer and don't need to have it spelled out for you.



  • @Gaska said:

    the return value is true if ... the expression pred(x,y) is true.

    @Gaska said:

    ```
    if ( p ( *next, *first ))
    return next;

    
    This is returning false if the predicate returns true, which contradicts the documentation.


  • This post is deleted!


  • No. That was just the only obvious thing that was wrong to me. Maybe someone nicer than you will help explain it.

    @NedFodder said:

    This is returning false if the predicate returns true, which contradicts the documentation.

    Sorry, I'm reading that as backwards to what you're saying. Because the order of the arguments as passed to the predicate are reversed.

    But now I guess it should be returning first there, since it will be wrong if the last element isn't sorted?


  • SockDev

    @NedFodder said:

    This is returning false if the predicate returns true, which contradicts the documentation.

    Are you sure about that?

    My understanding of the code is that is_sorted_until() returns the last element that is sorted; if that element is the last element of the list, then the whole list is sorted.

    @boomzilla said:

    But now I guess it should be returning first there, since it will be wrong if the last element isn't sorted?

    No; the function is called is_sorted_until, and next is the last element known to be sorted i.e. it is_sorted_until the element pointed to by next.



  • @RaceProUK said:

    No; the function is called is_sorted_until, and next is the last element known to be sorted i.e. it is_sorted_until the element pointed to by next.

    No, it's sorted until the previous element to next. At next, it has become unsorted. So, it would be correct for: { 1, 2, 3, 4}

    But incorrect for { 1, 2, 4, 3 }


  • SockDev

    So it is_sorted_until the first unsorted element next.
    Paging @OffByOne

    Still, it's clear that whatever problem @Gaska is seeing isn't a problem at all; AFAICT, the two functions are behaving correctly.



  • Does the boost code actually check p(*last, *last-but-one)



  • @RaceProUK said:

    Still, it's clear that whatever problem @Gaska is seeing isn't a problem at all; AFAICT, the two functions are behaving correctly.

    Hint: is {1, 1} sorted?


  • SockDev

    What's your predicate?



  • Getting warmer...


  • SockDev

    The predicate Getting warmer... is not a valid predicate for generating an ordering.



  • What would be a valid predicate under which this sequence is sorted?


  • kills Dumbledore

    x<=y?

    Seriously dude, why do you have to be so cryptic? Are you ashamed to discuss the actual WTF?


  • SockDev

    @Gaska said:

    What would be a valid predicate under which this sequence is sorted?

    <= and >=, and they're just the obvious ones.



  • @Jaloopa said:

    Seriously dude, why do you have to be so cryptic?

    I like riddles.

    @RaceProUK said:

    <= and >=, and they're just the obvious ones.

    I think you'd want to check what the function there will return with these predicates.


  • SockDev

    @Gaska said:

    I think you'd want to check what the function there will return with these predicates.

    It'll say {1,1} is a sorted list, which is exactly what a mathematician would say.


    Why don't you just explain the issue? Maybe that way we'll actually know what the fuck you're blabbering on about.



  • @Gaska said:

    I like riddles.

    The riddle was that there is no WTF!

    @RaceProUK said:

    Why don't you just explain the issue?

    :+1:



  • You guys are no fun :fa_frown_o:

    So, the WTF here is that the spec says p(x,y) must be true, while the implementation checks if p(y,x) is false. Which causes understandable confusion in case of equal elements, if you were to stick to docs and not common sense.


  • SockDev

    Does the function is_sorted_until behave as documented? If so, then what's the problem? Why are you so bothered about the internals when they get the job done correctly?



  • @RaceProUK said:

    Does the function is_sorted_until behave as documented?

    No.



  • Well I don't know what the phrase "is and only if" means, so maybe the documentation's right and my limited understanding of English is the problem.

    Or maybe the dumbshit who wrote this documentation didn't even read his own writing once to correct fucking basic errors like that.

    EDIT: regardless of the debate over Gaska's code, "is and only if" is clearly a WTF, so. Still valid topic.

    EDIT EDIT: oh look it's an open source project and has terrible documentation, what a shocking surprise.


  • SockDev

    @Gaska said:

    @RaceProUK said:
    Does the function is_sorted_until behave as documented?

    No.

    Did you include the explanation as microfiche embedded in the period? Because I don't have a microfiche reader to hand.



  • I have been summoned, so I come to say hello.

    Now I leave again.

     
    EDIT: FFS Dicksauce, that is not the post I replied to...



  • @OffByOne said:

    I come to say hello.

    :wave:



  • @RaceProUK said:

    Did you include the explanation as microfiche embedded in the period?

    No, I wrote it in plain text in post above.

    @Gaska said:

    the spec says p(x,y) must be true, while the implementation checks if p(y,x) is false


  • SockDev

    And p(x,y) being true implies p(y,x) is false. So what's the problem?



  • Think again.


  • SockDev

    This is the 31st post in this thread, and no-one has a fucking clue what you're on about.

    Explain. The. Problem.


  • kills Dumbledore

    @RaceProUK said:

    And p(x,y) being true implies p(y,x) is false

    No, if the predicate is equality they should both be true, for example.

    Certainly not clear but there might actually be a genuine WTF in among all the "I'm so smart I can see this obvious thing that I refuse to explain"



  • No. I. Will. Not. Explain. Basic. Maths. To. A. Professional. Programmer. For. Fuck's. Sake.

    Do you really not see the difference between a<b and !(b<a)?



  • @Gaska said:

    Do you really not see the difference between "a

    I see the difference between that and a complete sentence.

    edit: Damn, :hanzo:



  • This post is deleted!


  • @Jaloopa said:

    No, if the predicate is equality they should both be true, for example.

    C++ sort predicates tend to require strict weak ordering, in which case equality is not correct implementation (p(x, x) must be false). boost::sort from range algos does, so I'd guess it's just documentation bug on is_sorted part.


  • SockDev

    @Gaska said:

    Do you really not see the difference between a<b and !(b<a)?

    I see that they are not logically opposite, as together they fail to cover the case a==b.

    Oh, is that the problem? The one you could have explained in the first post like, I dunno, a person would? Ah well, that explains it then. And let's be honest, as :wtf:s go, this one is pretty minor; it's little more than an off-by-one bug.



  • @RaceProUK said:

    And let's be honest, as :wtf:s go, this one is pretty minor

    Unless you're entangled in the mess of unexplainable race conditions in sometimes-not-passing unit tests because someone sticked to the documentation.



  • @RaceProUK said:

    I see that they are not logically opposite

    You didn't see it here, or here, or here, or here, or here.


  • SockDev

    I asked you what your predicate was, and you refused to tell me. Without that information, how was I meant to know what you were talking about? At the risk of sounding like a certain rat, I'm not psychic; if you leave out the one key piece of information that ties the whole thing together, don't act like such a douche when people ask for it.



  • @RaceProUK said:

    I asked you what your predicate was, and you refused to tell me.

    Well, I included it in THE VERY FIRST POST OF THIS TOPIC. Also, the WTF stays the same regardless of predicate.


  • SockDev

    Oh, you mean the random predicate you may as well have just pulled out your arse? The one you never actually said you were using?



  • @RaceProUK said:

    Oh, you mean the random predicate you may as well have just pulled out your arse? The one you never actually said you were using?

    Yes, I mean the one I used in the code snippet in the OP. Whether I pulled it out of my arse or not doesn't matter, because WTF IS THERE FOR ANY PREDICATE. Literally any.



  • Wait, I'm not sure I get this one.

    There's the problem that last-but-one and actually-last are never compared but that's not what gaska is complaining about.

    Lets do a little truth table, shall we?
    p(x,y) = true, p(y,x) = true (elements are 'equal', is_sorted reports sorted)
    p(x,y)=true, p(y,x) = false ([x,y] is the correct ordering)
    p(x,y)=false, p(y,x)= true ([y,x] is the correct ordering)
    p(x,y)=false, p(x,y)=false (:wtf: )

    So yes, the sort algorithm will fail to sort correctly(due to the non-equivalence of p(x,y) and !p(y,x)) when you pick a predicate that returns false for all orderings.

    There are two scenarios where this is a real problem:

    1. You're relying on p(x,y) being called on every pair of elements in the array
    2. Your predicate is stupid

    If (1.) how the hell were you going to handle quicksort? If (2.) what does a correct sort even look like? if y<x and x<y what does 'sorted' even mean?


  • SockDev

    Just a shame it took over 40 posts for you to actually explain it


  • Discourse touched me in a no-no place

    So… is the WTF that if you do something dumbass with ordering predicate selection, the code punishes you?


  • I survived the hour long Uno hand

    So basically, the code assumes a strict order, and you gave it a weak order?



  • We'll never know because he'll refuse to tell us. Fuck...he's turning the whole forum into blakey alts.


  • Discourse touched me in a no-no place

    @Yamikuronue said:

    So basically, the code assumes a strict order, and you gave it a weak order?

    If you give it a weak order, it gives you a run that is weakly ordered. If you give it a strict order, you get a run that is strictly ordered. If you (well, not you you; non-specific “you”) don't know which you want, perhaps you should take some time to figure it out first?



  • @AyGeePlus said:

    There's the problem that last-but-one and actually-last are never compared

    There's no such problem. In C++ cloudcuckooland, "last" means "the thing immediately after the last element".

    @AyGeePlus said:

    p(x,y) = true, p(y,x) = true (elements are 'equal', is_sorted reports sorted)

    @AyGeePlus said:
    p(x,y)=false, p(x,y)=false (:wtf: )

    If you look at documentation, you're right. If you look at the code, you've got it backwards. I don't blame you - documentation should be the place to check how the code works. If it doesn't match the behavior of code, why bother having documentation at all? Especially if it's Open Sores. That's the problem I was talking about.

    The rest of your post is irrelevant.

    @dkf said:

    So… is the WTF that if you do something dumbass with ordering predicate selection, the code punishes you?

    No, the WTF is that what they say your predicate should look like is ALL LIES!!!

    @Yamikuronue said:

    So basically, the code assumes a strict order, and you gave it a weak order?

    The documentation explicitly states that weak ordering should be used. How else could you achieve the "for each adjacent elements [x,y] the expression pred(x,y) is true" property?

    @boomzilla said:

    We'll never know because he'll refuse to tell us.

    If it was just you, I would. But it's @Yamikuronue asking. I like her.


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.