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.
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.
-
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.
-
the return value is true if ... the expression pred(x,y) is true.
```
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.
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?
-
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.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 calledis_sorted_until
, andnext
is the last element known to be sorted i.e. itis_sorted_until
the element pointed to bynext
.
-
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
. Atnext
, it has become unsorted. So, it would be correct for:{ 1, 2, 3, 4}
But incorrect for
{ 1, 2, 4, 3 }
-
So it
is_sorted_until
the first unsorted elementnext
.
Paging @OffByOneStill, 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)
-
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?
-
What's your predicate?
-
Getting warmer...
-
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?
-
x<=y
?Seriously dude, why do you have to be so cryptic? Are you ashamed to discuss the actual WTF?
-
What would be a valid predicate under which this sequence is sorted?
<=
and>=
, and they're just the obvious ones.
-
Seriously dude, why do you have to be so cryptic?
I like riddles.<= and >=, and they're just the obvious ones.
I think you'd want to check what the function there will return with these predicates.
-
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.
-
I like riddles.
The riddle was that there is no WTF!
Why don't you just explain the issue?
-
You guys are no fun
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.
-
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?
-
-
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.
-
@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...
-
-
Did you include the explanation as microfiche embedded in the period?
No, I wrote it in plain text in post above.the spec says p(x,y) must be true, while the implementation checks if p(y,x) is false
-
And
p(x,y)
being true impliesp(y,x)
is false. So what's the problem?
-
Think again.
-
This is the 31st post in this thread, and no-one has a fucking clue what you're on about.
Explain. The. Problem.
-
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)
?
-
Do you really not see the difference between "a
I see the difference between that and a complete sentence.
edit: Damn,
-
This post is deleted!
-
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 onis_sorted
part.
-
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 casea==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 s go, this one is pretty minor; it's little more than an off-by-one bug.
-
And let's be honest, as 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.
-
I see that they are not logically opposite
You didn't see it here, or here, or here, or here, or here.
-
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.
-
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.
-
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?
-
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 ( )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:
- You're relying on
p(x,y)
being called on every pair of elements in the array - 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
andx<y
what does 'sorted' even mean?
- You're relying on
-
Just a shame it took over 40 posts for you to actually explain it
-
So… is the WTF that if you do something dumbass with ordering predicate selection, the code punishes you?
-
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.
-
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?
-
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".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 ( )
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.
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!!!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?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.