Re: [Lilypond-auto] Issue 2838 in lilypond: Patch: Changes less<Grob *> to Grob::less.

[lilypond]

Updates:
        Status: Invalid

Comment #1 on issue 2838 by address@hidden: Patch: Changes less<Grob *> to  
Grob::less.
http://code.google.com/p/lilypond/issues/detail?id=2838

I am not sure about that: sometimes you can reduce algorithmic complexity  
of some algorithms by putting sets into any old order as long as it is  
reproducible in the current session. eq-based hashing works on that  
premise: if you do a hash-for-each afterwards, you'll get the elements out  
in consistent order, but the order might differ from run to run.

Comparing two sets for common elements can be done O(n lg n) by first  
sorting the sets, then using a list-merge algorithm.  Sorting on memory  
address is quite feasible for that as long as the garbage collector does  
not reallocate elements.

Finding a more predictable sorting order will in general be preferable.  It  
is possibly more expensive, and it is likely to mask decisions which are  
actually made arbitrarily when they probably shouldn't.

In the use cases I see, this sorting happens right before calling uniq on  
the result.  Uniq removes equal successive elements.  Since the elements of  
the vectors here are indeed pointers, the previous sorting pass should sort  
on pointer values in order to make this work reliably.  The resulting array  
will still be sorted according to pointer values.  If that has an influence  
on further processing, it might be conceivable to do a post-sort on some  
other more reproducible criterion.

But in the given combination with uniq working with actual pointer  
equivalence, this patch is wrong.  It most certainly violates exactly the  
intent of the people writing it and combining it with uniq and makes the  
intended behavior less reliable in the case of different grobs comparing  
equal, since in that case the following uniq will stop working reliably.

Since the underlying assumption for this patch and issue is clearly wrong,  
I am marking the issue as invalid.