Holy cow, I wrote a book!
When you are writing a sort comparison function (say, to be passed to
ListView_SortItems or *gasp* to be used as
an IComparer), your comparison function needs to follow
Compare(a, a) = 0
Compare(a, b) ≤ 0
Compare(b, c) ≤ 0
Compare(a, c) ≤ 0
Here are some logical consequences of these rules (all easily proved).
The first two are obvious, but the third may be a surprise.
Compare(a, b) = 0
Compare(b, c) = 0
Compare(a, c) = 0
Compare(a, b) < 0
Compare(b, c) < 0
Compare(a, c) < 0
Of the original three rules,
the first two are hard to get wrong, but the third rule is
often hard to get right if you try to be clever in your comparison
For one thing, these rules require that you implement a total order.
If you merely have a partial order, you must extend your partial
order to a total order in a consistent manner.
I saw somebody get into trouble when they tried to implement their
comparison function on a set of tasks, where some tasks have other
tasks as prerequisites. The comparison function implemented
the following algorithm:
a < b
a > b
a = b
Sounds great. Then you can sort with this comparison function and you
get the tasks listed in some order such that all tasks come after
Except that it doesn't work. Trying to sort with this comparison
function results in all the tasks being jumbled together
with apparently no regard for which tasks are prerequisites of which.
What went wrong?
Consider this dependency diagram:
a ----> b
Task "a" is a prerequisite for "b", and task "c" is unrelated to both
of them. If you used the above comparison function, it would declare
that "a = c" and "b = c" (since "c" is unrelated to "a" or "b"),
which in turn implies by transitivity that "a = b", which contradicts
"a < b", since "a" is a prerequisite for "b".
If your comparison function is inconsistent, you will get garbled results.
Moral of the story: When you write a comparison function, you really
have to know which items are less than which other items.
Don't just declare two items "equal" because you don't know which order
they should be in.