From e287f100440394e2e25513a9c5d926aaf4d482da Mon Sep 17 00:00:00 2001
From: handa <handa>
Date: Wed, 22 Apr 2009 07:19:49 +0000
Subject: [PATCH] *** empty log message ***

---
 MText.cs |  168 +++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 106 insertions(+), 62 deletions(-)

diff --git a/MText.cs b/MText.cs
index 482e1d2..50b573c 100644
--- a/MText.cs
+++ b/MText.cs
@@ -464,7 +464,11 @@ namespace M17N.Core
 	  MPlist p = intervals.Find (key);
 
 	  if (p != null)
-	    ((MInterval) p.Val).Pop (from, to);
+	    {
+	      MInterval root = (MInterval) p.Val;
+	      root.Pop (from, to);
+	      root.MergeAfterChange (from, to);
+	    }
 	}
     }
 
@@ -1208,71 +1212,127 @@ namespace M17N.Core
 	Stack.Push (prop.key, prop);
       }
 
-      private bool try_merge_prev ()
+      private static void merge_nodes (MInterval head, MInterval tail)
       {
-	MInterval prev = Prev;
+	M17N.DebugPrint ("merging "); head.DumpOne (true, false);
+	M17N.DebugPrint (" through "); tail.DumpOne (true, true);
 
-	if (! mergeable (prev))
-	  return false;
+	int from = head.From;
+	int to = tail.To;
+	MInterval root;
 
-	M17N.DebugPrint ("merging "); DumpOne (false, false);
-	M17N.DebugPrint (" with prev "); prev.DumpOne (false, true);
-	int len = prev.Length - prev.LeftLength;
+	for (root = head; root.To + head.RightLength < to;
+	     root = root.Parent);
+	
+	M17N.DebugPrint ("common root is "); root.DumpOne (false, true);
 
-	// PREV is Left, Left.Right, ..., or Left....Right.
-	if (prev != Left)
+	if (from < root.From)
 	  {
-	    if (prev.Left != null)
-	      prev.Left.Parent = prev.Parent;
-	    prev.Parent.Right = prev.Left;
-	    while (prev.Parent != Left)
+	    MInterval prev = root.Prev;
+	    int deleting = root.From - from;
+	    int deleted = 0;
+
+	    while (deleted < deleting)
+	      {
+		int len = prev.Length - prev.LeftLength;
+
+		M17N.DebugPrint ("merging "); prev.DumpOne (false, true);
+		deleted += len;
+		if (prev.Left != null)
+		  {
+		    prev.Left.Parent = prev.Parent;
+		    if (prev.Parent.Right == prev)
+		      prev.Parent.Right = prev.Left;
+		    else
+		      prev.Parent.Left = prev.Left;
+		    prev = prev.Left.RightMost;
+		  }
+		else
+		  {
+		    prev = prev.Parent;
+		    prev.Right = null;
+		    prev.Length -= deleted;
+		  }
+	      }
+	    while (prev.Parent != root)
 	      {
-		prev.Length -= len;
+		prev.Length -= deleted;
 		prev = prev.Parent;
 	      }
 	  }
-	Left.Length -= len;
-	if (Left.Length == Left.LeftLength)
+	if (root.To < to)
 	  {
-	    if (Left.Left != null)
-	      Left.Left.Parent = this;
-	    Left = Left.Left;
+	    MInterval next = root.Next;
+	    int deleting = root.To - to;
+	    int deleted = 0;
+
+	    while (deleted < deleting)
+	      {
+		int len = next.Length - next.RightLength;
+
+		M17N.DebugPrint ("merging "); next.DumpOne (false, true);
+		deleted += len;
+		if (next.Right != null)
+		  {
+		    next.Right.Parent = next.Parent;
+		    if (next.Parent.Left == next)
+		      next.Parent.Left = next.Right;
+		    else
+		      next.Parent.Right = next.Right;
+		    next = next.Right.LeftMost;
+		  }
+		else
+		  {
+		    next = next.Parent;
+		    next.Left = null;
+		    next.Length -= deleted;
+		  }
+	      }
+	    while (next.Parent != root)
+	      {
+		next.Length -= deleted;
+		next = next.Parent;
+	      }
 	  }
-	return true;
       }
 
-      private bool try_merge_next ()
+      public void MergeAfterChange (int start, int end)
       {
-	MInterval next = Next;
-
-	if (! mergeable (next))
-	  return false;
-
-	M17N.DebugPrint ("merging "); DumpOne (false, false);
-	M17N.DebugPrint (" with next "); next.DumpOne (false, true);
+	update_from_to ();
+	if (start < From)
+	  {
+	    Prev.MergeAfterChange (start, end);
+	    return;
+	  }
 
-	int len = next.Length - next.RightLength;
+	MInterval head = this, tail = this, i;
 
-	// NEXT is Right, Right.Left, ..., or Right....Left.
-	if (next != Right)
+	if (start == From && start > 0)
 	  {
-	    if (next.Right != null)
-	      next.Right.Parent = next.Parent;
-	    next.Parent.Left = next.Right;
-	    while (next.Parent != Right)
+	    i = Prev;
+	    if (mergeable (i))
+	      head = i;
+	  }
+	while (tail.To < end)
+	  {
+	    i = tail.Next;
+	    if (! tail.mergeable (i))
 	      {
-		next.Length -= len;
-		next = next.Parent;
+		if (head != tail)
+		  merge_nodes (head, tail);
+		head = i;
 	      }
+	    tail = i;
 	  }
-	Right.Length -= len;
-	if (Right.Length == Right.RightLength)
+	while (true)
 	  {
-	    if (Right.Right != null)
-	      Right.Right.Parent = this;
-	    Right = Right.Right;
+	    i = tail.Next;
+	    if (i == null || ! tail.mergeable (i))
+	      break;
+	    tail = i;
 	  }
-	return true;
+	if (head != tail)
+	  merge_nodes (head, tail);
       }
 
       public void Pop (int start, int end)
@@ -1302,27 +1362,11 @@ namespace M17N.Core
 
 	if (! Stack.IsEmpty)
 	  {
-	    bool check_prev = start == From && start > 0;
-	    bool check_next = end == To && end < mtext.Length;
-
-	    if (! check_prev && start > From)
+	    if (start > From)
 	      divide_left (start);
-	    if (! check_next && end < To)
+	    if (end < To)
 	      divide_right (end);
 	    Stack.Pop ();
-	    if (check_prev && Left != null)
-	      check_prev = try_merge_prev () && (Left != null);
-	    if (check_next && Right != null)
-	      check_next = try_merge_next () && (Right != null);
-	    if (check_prev)
-	      {
-		if (Prev.try_merge_next () && check_next)
-		  Prev.try_merge_next ();
-	      }
-	    else if (check_next)
-	      {
-		Next.try_merge_prev ();
-	      }
 	  }
       }
 
-- 
1.7.10.4