Use a stable sort when ordering MIDI items (issue 353790043 by address@hidden)

[MrBobo1239]

Reviewers: ,

Message:
Hi all,

this is a patch to fix the issue described here:
https://lists.gnu.org/archive/html/lilypond-user/2015-02/msg00035.html
(I'm surprised this hasn't been fixed until now.)
I'm not familiar with lilypond internals at all so I don't know whether
this is correct way to fix this but it does seem logical that an
unstable sort will cause these problems. My local .ly test file now
doesn't exhibit the issue anymore but I'd be great if somebody else who
has encountered this could confirm.

Description:
Use a stable sort when ordering MIDI items

Fixes the issue described here:
https://lists.gnu.org/archive/html/lilypond-user/2015-02/msg00035.html
(undeterministic reordering of events at the same MIDI timestamp; e.g.
"\sustainOff\sustainOn")

Please review this at https://codereview.appspot.com/353790043/

Affected files (+13, -1 lines):
  M flower/include/std-vector.hh
  M lily/midi-walker.cc


Index: flower/include/std-vector.hh
diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh
index  
589f7c0db2063a2110241668c5d2ac7ba39d39ce..4a46339bad5ca064f586b85815345e4c0a7c587a  
100644
--- a/flower/include/std-vector.hh
+++ b/flower/include/std-vector.hh
@@ -168,6 +168,18 @@ vector_sort (vector<T> &v,
   sort (v.begin () + b, v.begin () + e, less);
 }

+template<typename T, typename Compare>
+void
+vector_stable_sort (vector<T> &v,
+             Compare less,
+             vsize b = 0, vsize e = VPOS)
+{
+  if (e == VPOS)
+    e = v.size ();
+
+  stable_sort (v.begin () + b, v.begin () + e, less);
+}
+
 template<typename T>
 void
 reverse (vector<T> &v)
Index: lily/midi-walker.cc
diff --git a/lily/midi-walker.cc b/lily/midi-walker.cc
index  
c54bc6a6b458391e91a47812064fc9803d29ae2a..68b2c34de57e8667743be9253fffe0c929c913ed  
100644
--- a/lily/midi-walker.cc
+++ b/lily/midi-walker.cc
@@ -57,7 +57,7 @@ Midi_walker::Midi_walker (Audio_staff *audio_staff,  
Midi_track *track, int start
   track_ = track;
   index_ = 0;
   items_ = audio_staff->audio_items_;
-  vector_sort (items_, audio_item_less);
+  vector_stable_sort (items_, audio_item_less);
   //Scores that begin with grace notes start at negative times. This
   //is OK - MIDI output doesn't use absolute ticks, only differences.
   last_tick_ = start_tick;