[PATCH] Sort "loose" dives properly in-between trips

Linus Torvalds torvalds at linux-foundation.org
Mon Jan 7 10:07:52 PST 2013


On Mon, Jan 7, 2013 at 9:56 AM, Miika Turkia <miika.turkia at gmail.com> wrote:
>
> Your extension is clearly required. (I only had one dive not in trip,
> thus didn't even consider this part of the sorting.)
>
> When comparing the original sorting code and my code, a difference I
> can see is that my code does not return 0 when the times are the same.
> I believe the times should never be the same, but I am not sure about
> it.

It can happen if you load the XML files for two people. We don't want
the trips to mix, but there's a possibility (although remote) that
there are times that just happen to be the same.

However, the much *bigger* possibility is that there are dive trips
that overlap, and dives that are outside those dive trips, and then
the real issue is that the sort really does have to be transitive.
Otherwise you can get really nasty bugs (not just wrong ordering -
unexpected lockups due to infinite loops in the sorting that happen
under just very special cases, and only with particular sorting
algorithms).

One thing to look out for is to make sure we never compare two dives
in separate trips with the dive time. And that's where it worries me
to compare a dive time with a trip time: the transitivity means that

 - dive a in trip A
 - dive b in no trip
 - dive c in trip C

has to be *very* careful about comparing dives a/b and b/c, because
the transitivity implies that it implicitly then compares dives a/c.
We need to make sure that a comparison of a/c gets a result that is
consistent with the comparisons of a/b and b/c.

I *think* your patch is ok (because a and c will be compared by the
dates of A/C, and then a/b will compare A/b times, and b/c will
compare b/C times), but I worry about this a bit.

The main thing I want you to think about is that it's actually more
complicated than just ever looking at two particular dives. The full
ordering is about all the edges between all the dives, and if you can
create a loop in that graph, you can confuse the sorting algorithm.

              Linus


More information about the subsurface mailing list