edit.c: fix bad selection ranges.

[C. Scott Ananian]

ChangeLog:
  - EDIT_EM_SetSel: Old/new selection range ordering code would break when
      old_end < start < end < old_start
    Rearrange the comparisons slightly to fix this; also document
    the ordering relation this code is supposed to produce, and
    verify optimality.
  --scott

DC counter-intelligence Shoal Bay shortwave CABOUNCE NSA AES SUMAC 
BOND Sigint domestic disruption overthrow BGGYPSY OVER THE HORIZON RADAR
                          ( http://cscott.net/ )

Index: dlls/user/edit.c
===================================================================
RCS file: /home/wine/wine/dlls/user/edit.c,v
retrieving revision 1.20
diff -u -p -r1.20 edit.c
--- dlls/user/edit.c	25 Feb 2005 16:51:13 -0000	1.20
+++ dlls/user/edit.c	17 Mar 2005 21:07:43 -0000
@@ -3603,11 +3603,23 @@ static void EDIT_EM_SetSel(EDITSTATE *es
  		es->flags |= EF_AFTER_WRAP;
  	else
  		es->flags &= ~EF_AFTER_WRAP;
-/* This is a little bit more efficient than before, not sure if it can be improved. FIXME? */
-        ORDER_UINT(start, end);
+	/* Compute the necessary invalidation region. */
+	/* Note that we don't need to invalidate regions which have
+	 * "never" been selected, or those which are "still" selected.
+	 * In fact, every time we hit a selection boundary, we can
+	 * *toggle* whether we need to invalidate.  Thus we can optimize by
+	 * *sorting* the interval endpoints.  Let's assume that we sort them
+	 * in this order:
+	 *        start <= end <= old_start <= old_end
+	 * Knuth 5.3.1 (p 183) asssures us that this can be done optimally
+	 * in 5 comparisons; ie it's impossible to do better than the
+	 * following: */
          ORDER_UINT(end, old_end);
          ORDER_UINT(start, old_start);
          ORDER_UINT(old_start, old_end);
+        ORDER_UINT(start, end);
+	/* Note that at this point 'end' and 'old_start' are not in order, but
+	 * start is definitely the min. and old_end is definitely the max. */
  	if (end != old_start)
          {
  /*
@@ -3616,6 +3628,7 @@ static void EDIT_EM_SetSel(EDITSTATE *es
   *          EDIT_InvalidateText(es, start, end);
   *          EDIT_InvalidateText(es, old_start, old_end);
   * in place of the following if statement.
+ * (That would complete the optimal five-comparison four-element sort.)
   */
              if (old_start > end )
              {