From 95e3e1ef659f459fcae242391351ef404352c6a2 Mon Sep 17 00:00:00 2001
From: "Richard M. Stallman" <rms@gnu.org>
Date: Sat, 5 Jun 1993 07:57:32 +0000
Subject: (copy_intervals): Don't adjust total_length at the end. Set lengths
 of subintervals properly. (balance_intervals): Balance left as well as right.

---
 src/intervals.c | 44 +++++++++++++++++++++++++-------------------
 1 file changed, 25 insertions(+), 19 deletions(-)

(limited to 'src/intervals.c')

diff --git a/src/intervals.c b/src/intervals.c
index b262412930f..c4bb4c381db 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -1555,23 +1555,30 @@ balance_an_interval (i)
   register int threshold = (XFASTINT (interval_balance_threshold)
 			    * (total_children_size / 100));
 
-  if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
-      && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
-    return rotate_right (i);
+  /* Balance within each side.  */
+  balance_intervals (i->left);
+  balance_intervals (i->right);
 
   if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
       && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
-    return rotate_right (i);
-
-#if 0
-  if (LEFT_TOTAL_LENGTH (i) >
-      (RIGHT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold)))
-    return rotate_right (i);
+    {
+      i = rotate_right (i);
+      /* If that made it unbalanced the other way, take it back.  */
+      if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
+	  && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold)
+	return rotate_left (i);
+      return i;
+    }
 
-  if (RIGHT_TOTAL_LENGTH (i) >
-      (LEFT_TOTAL_LENGTH (i) + XINT (interval_balance_threshold)))
-    return rotate_left (i);
-#endif
+  if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
+      && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold)
+    {
+      i = rotate_left (i);
+      if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
+	  && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
+	return rotate_right (i);
+      return i;
+    }
 
   return i;
 }
@@ -1608,7 +1615,7 @@ copy_intervals (tree, start, length)
      int start, length;
 {
   register INTERVAL i, new, t;
-  register int got;
+  register int got, prevlen;
 
   if (NULL_INTERVAL_P (tree) || length <= 0)
     return NULL_INTERVAL;
@@ -1629,17 +1636,16 @@ copy_intervals (tree, start, length)
   copy_properties (i, new);
 
   t = new;
+  prevlen = got;
   while (got < length)
     {
       i = next_interval (i);
-      t = split_interval_right (t, got + 1);
+      t = split_interval_right (t, prevlen + 1);
       copy_properties (i, t);
-      got += LENGTH (i);
+      prevlen = LENGTH (i);
+      got += prevlen;
     }
 
-  if (got > length)
-    t->total_length -= (got - length);
-
   return balance_intervals (new);
 }
 
-- 
cgit v1.2.3-70-g09d2