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);
+ }
}
}
public void DumpPropNested ()
{
- Console.Write ("(");
foreach (MPlist p in intervals)
((MInterval) p.Val).DumpNested (true);
- Console.WriteLine (")");
}
private class MInterval
MPlist p;
for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
array[idx] = (MTextProperty) p.Val;
- return array[idx - 1];
+ return array[0];
}
private MInterval (MSymbol key, MText mt, int length, MPlist stack)
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;
- 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)
+ {
+ MInterval prev = root.Prev;
+
+ while (true)
+ {
+ int len = prev.Length - prev.LeftLength;
+
+ M17N.DebugPrint ("merging "); prev.DumpOne (false, true);
+ 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;
+ for (MInterval i = prev.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (prev == head)
+ break;
+ prev = prev.Left.RightMost;
+ }
+ else
+ {
+ prev.Parent.Right = null;
+ for (MInterval i = prev.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (prev == head)
+ break;
+ prev = prev.Parent;
+ }
+ }
+ }
+ if (root.To < to)
{
- prev.Parent.Right = prev.Left;
- while (prev.Parent != Left)
+ MInterval next = root.Next;
+
+ while (true)
{
- prev.Length -= len;
- prev = prev.Parent;
+ int len = next.Length - next.RightLength;
+
+ M17N.DebugPrint ("merging "); next.DumpOne (false, true);
+ 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;
+ for (MInterval i = next.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (next == tail)
+ break;
+ next = next.Right.LeftMost;
+ }
+ else
+ {
+ next.Parent.Left = null;
+ for (MInterval i = next.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (next == tail)
+ break;
+ next = next.Parent;
+ }
}
}
- Left.Length -= len;
- if (Left.Length == Left.LeftLength)
- Left = Left.Left;
- return true;
}
- private bool try_merge_next ()
+ public void MergeAfterChange (int start, int end)
{
- MInterval next = Next;
-
- if (! mergeable (next))
- return false;
+ update_from_to ();
+ if (start < From)
+ {
+ Prev.MergeAfterChange (start, end);
+ return;
+ }
- int len = next.Length - next.LeftLength;
+ MInterval head = this, tail = this, i;
- // NEXT is Right, Right.Left, ..., or Right....Left.
- if (next != Right)
+ if (start == From && start > 0)
+ {
+ i = Prev;
+ if (mergeable (i))
+ head = i;
+ }
+ while (tail.To < end)
{
- next.Parent.Left = next.Right;
- while (next.Parent != Right)
+ 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.LeftLength)
- Right = Right.Left;
-
- return true;
+ while (true)
+ {
+ i = tail.Next;
+ if (i == null || ! tail.mergeable (i))
+ break;
+ tail = i;
+ }
+ if (head != tail)
+ merge_nodes (head, tail);
}
-
public void Pop (int start, int end)
{
update_from_to ();
if (! Stack.IsEmpty)
{
- bool check_prev = start == From && start > 0;
- bool check_next = end == To && end < mtext.Length;
-
- if (! check_prev)
+ if (start > From)
divide_left (start);
- if (! check_next)
+ 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 ();
- }
}
}
Console.Write (")");
if (newline)
Console.WriteLine ();
+ if (Length <= 0)
+ throw new Exception ("Invalid interval length");
}
}
}
}
+ private int Depth {
+ get { return (Parent == null ? 0 : Parent.Depth + 1); }
+ }
+
public void DumpNested (bool force)
{
+ DumpNested ("", force);
+ }
+
+ public void DumpNested (string indent, bool force)
+ {
if (force || M17N.debug)
{
- update_from_to ();
+ int indent_type = (Parent == null ? 1
+ : Parent.Left == this ? 0 : 2);
- Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
- foreach (MPlist p in Stack)
- Console.Write (" " + p.Val);
+ update_from_to ();
if (Left != null)
{
- Console.Write (" left=");
- Left.DumpNested (force);
+ if (indent_type <= 1)
+ Left.DumpNested (indent + " ", force);
+ else
+ Left.DumpNested (indent + "| ", force);
}
+ if (indent_type == 0)
+ Console.Write (indent + ".-");
+ else if (indent_type == 2)
+ Console.Write (indent + "`-");
+ DumpOne (true, true, true);
if (Right != null)
{
- Console.Write (" right=");
- Right.DumpNested (force);
+ if (indent_type >= 1)
+ Right.DumpNested (indent + " ", force);
+ else
+ Right.DumpNested (indent + "| ", force);
}
- Console.Write (")");
}
}
}
projects / m17n / m17n-lib-cs.git / blobdiff