+ public MText Cat (int c)
+ {
+ insert (nchars, c);
+ return this;
+ }
+
+ public MText Cat (MText mt)
+ {
+ insert (nchars, mt, 0, mt.Length);
+ return this;
+ }
+
+ public MText Cat (MText mt, int from, int to)
+ {
+ insert (nchars, mt, from, to);
+ return this;
+ }
+
+ public MText Del ()
+ {
+ return Del (0, Length);
+ }
+
+ public MText Del (int from, int to)
+ {
+ if (check_range (from, to, true))
+ return this;
+ sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
+ nchars -= to - from;
+ if (nchars > 0)
+ foreach (MPlist plist in intervals)
+ {
+ MInterval root = (MInterval) plist.Val;
+ root.Delete (from, to);
+ if (from > 0 && from < nchars)
+ ((MInterval) plist.Val).MergeAfterChange (from, from);
+ }
+ else
+ intervals.Clear ();
+ if (M17n.debug)
+ DumpPropNested ();
+ return this;
+ }
+
+ public object GetProp (int pos, MSymbol key)
+ {
+ check_pos (pos, false);
+
+ MInterval i = (MInterval) intervals.Get (key);
+ if (i == null)
+ return null;
+
+ MProperty prop = i.Get (pos);
+ return (prop != null ? prop.Val : null);
+ }
+
+ public object GetProp (int pos, MSymbol key, out MProperty prop)
+ {
+ check_pos (pos, false);
+
+ MInterval i = (MInterval) intervals.Get (key);
+ if (i == null)
+ return (prop = null);
+ prop = i.Get (pos);
+ return (prop != null ? prop.Val : null);
+ }
+
+ public object GetProp (int pos, MSymbol key, out MProperty[] array)
+ {
+ check_pos (pos, false);
+
+ MInterval i = (MInterval) intervals.Get (key);
+ if (i == null)
+ return (array = null);
+ MProperty prop = i.Get (pos, out array);
+ return (prop != null ? prop.Val : null);
+ }
+
+ public void PushProp (int from, int to, MSymbol key, object val)
+ {
+ if (! check_range (from, to, true))
+ PushProp (from, to, new MProperty (key, val));
+ }
+
+ public void PushProp (int from, int to, MProperty prop)
+ {
+ if (from < 0)
+ {
+ if (default_property == null)
+ default_property = new MPlist ();
+ default_property.Push (prop.key, prop.val);
+ }
+ else
+ {
+ if (check_range (from, to, true))
+ return;
+
+ MPlist p = intervals.Find (prop.key);
+ MInterval root;
+
+ if (p == null)
+ {
+ root = new MInterval (prop.key, this);
+ intervals.Push (prop.key, root);
+ }
+ else
+ {
+ root = (MInterval) p.Val;
+ if (root.isSensitive)
+ {
+ root.PopSensitive (from, to);
+ root.MergeAfterChange (from, to);
+ root = (MInterval) p.Val;
+ if (M17n.debug)
+ DumpPropNested ();
+ }
+ }
+ root.Push (from, to, prop);
+ root.MergeAfterChange (from, to);
+ root.Balance ();
+ }
+ }
+
+ public void PopProp (int from, int to)
+ {
+ if (from < 0)
+ {
+ default_property = null;
+ }
+ else
+ {
+ if (check_range (from, to, true))
+ return;
+ for (MPlist p = intervals; ! p.IsEmpty; p = p.next)
+ {
+ MInterval root = (MInterval) p.Val;
+ root.PopAll (from, to);
+ root = (MInterval) p.Val;
+ if (M17n.debug)
+ DumpPropNested ();
+ root.MergeAfterChange (from, to);
+ root.Balance ();
+ }
+ }
+ }
+
+ public void PopProp (int from, int to, MSymbol key)
+ {
+ if (from < 0)
+ {
+ if (default_property == null)
+ return;
+ MPlist p = default_property.Find (key);
+
+ if (p != null)
+ p.Pop ();
+ }
+ else
+ {
+ if (check_range (from, to, true))
+ return;
+
+ MPlist p = intervals.Find (key);
+
+ if (p != null)
+ {
+ MInterval root = (MInterval) p.Val;
+ if (root.isSensitive)
+ root.PopSensitive (from, to);
+ else
+ root.Pop (from, to);
+ root = (MInterval) p.Val;
+ if (M17n.debug)
+ DumpPropNested ();
+ root.MergeAfterChange (from, to);
+ root.Balance ();
+ }
+ }
+ }
+
+ public object FindProp (MSymbol key, int pos, out int from, out int to)
+ {
+ from = 0;
+ to = Length;
+ check_pos (pos, false);
+
+ MInterval i = (MInterval) intervals.Get (key);
+ if (i != null
+ && (i = i.Find (pos, out from, out to)) != null)
+ return GetProp (from, key);
+ return null;
+ }
+
+ public void DumpProp ()
+ {
+ Console.Write ("(");
+ foreach (MPlist p in intervals)
+ ((MInterval) p.Val).Dump (true);
+ Console.WriteLine (")");
+ }
+
+ public void DumpPropNested ()
+ {
+ Console.WriteLine ("total length = {0}", Length);
+ foreach (MPlist p in intervals)
+ ((MInterval) p.Val).DumpNested (true);
+ }
+
+ private class MInterval
+ {
+ // position: 0 1 2 3 4 5 6 7
+ // | A | B | C | D | E F | G |
+ // interval |---|---|---|<->|-------|---|
+ // |---|<->|---| |<----->|---|
+ // |<->| |<->| |<->|
+ //
+ // [7 (3 4)]
+ // [3 (1 2)] [3 (4 6)]
+ // [1 (0 1)] [2 (2 3)] [1 (6 7)]
+ //
+ private static int count = 0;
+ private int ID;
+ private int Length;
+ private int From, To;
+ private MSymbol Key;
+ private MPlist Stack;
+ private MInterval Left, Right, Parent;
+ private MText mtext;
+
+ public MInterval (MSymbol key, MText mt, int length)
+ {
+ if (length <= 0)
+ throw new Exception ("Invalid interval length");
+ Key = key;
+ mtext = mt;
+ Length = length;
+ Stack = new MPlist ();
+ ID = count++;
+ }
+
+ public MInterval (MSymbol key, MText mt)
+ {
+ Key = key;
+ mtext = mt;
+ Length = mt.sb.Length;
+ From = 0;
+ To = Length;
+ Stack = new MPlist ();
+ ID = count++;
+ }
+
+ /// POS must be smaller than Length;
+ public MProperty Get (int pos)
+ {
+ MInterval i = find_head (pos);
+
+ return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val);
+ }
+
+ /// POS must be smaller than Length;
+ public MProperty Get (int pos, out MProperty[] array)
+ {
+ MInterval i = find_head (pos);
+
+ if (i.To == pos)
+ i = i.Next;
+ if (i.Stack.IsEmpty)
+ {
+ array = null;
+ return null;
+ }
+ array = new MProperty[i.Stack.Count];
+
+ int idx;
+ MPlist p;
+ for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
+ array[idx] = (MProperty) p.Val;
+ return array[0];
+ }
+
+ private MInterval (MSymbol key, MText mt, int length, MPlist stack)
+ {
+ Key = key;
+ mtext = mt;
+ Length = length;
+ From = 0;
+ To = Length;
+ Stack = stack == null ? new MPlist () : stack.Clone ();
+ ID = count++;
+ }
+
+ private bool isRearSticky
+ {
+ get { return MProperty.HasFlags (Key, MProperty.Flags.RearSticky) ; }
+ }
+
+ private bool isFrontSticky
+ {
+ get { return MProperty.HasFlags (Key, MProperty.Flags.FrontSticky) ; }
+ }
+
+ public bool isSensitive
+ {
+ get { return MProperty.HasFlags (Key, MProperty.Flags.Sensitive) ; }
+ }
+
+ public bool isFrontSensitive
+ {
+ get { return MProperty.HasFlags (Key,
+ MProperty.Flags.FrontSensitive) ; }
+ }
+
+ public bool isRearSensitive
+ {
+ get { return MProperty.HasFlags (Key,
+ MProperty.Flags.RearSensitive) ; }
+ }
+
+ private void update_from_to ()
+ {
+ if (Parent == null)
+ {
+ From = LeftLength;
+ To = Length - RightLength;
+ }
+ else if (Parent.Left == this)
+ {
+ From = Parent.From - Length + LeftLength;
+ To = Parent.From - RightLength;
+ }
+ else
+ {
+ From = Parent.To + LeftLength;
+ To = Parent.To + Length - RightLength;
+ }
+ }
+
+ private int LeftLength
+ {
+ get { return (Left == null ? 0 : Left.Length); }
+ }
+
+ private int RightLength
+ {
+ get { return (Right == null ? 0 : Right.Length); }
+ }
+
+ private MInterval LeftMost
+ {
+ get {
+ update_from_to ();
+ if (Left == null)
+ return this;
+ return Left.LeftMost;
+ }
+ }
+
+ private MInterval RightMost
+ {
+ get {
+ update_from_to ();
+ if (Right == null)
+ return this;
+ return Right.RightMost;
+ }
+ }
+
+ private MInterval Prev {
+ get {
+ MInterval i;
+
+ if (Left != null)
+ {
+ for (i = Left; i.Right != null; i = i.Right)
+ i.update_from_to ();
+ i.update_from_to ();
+ }
+ else
+ {
+ MInterval child = this;
+ for (i = Parent; i != null && i.Left == child;
+ child = i, i = i.Parent);
+ }
+ return i;
+ }
+ }
+
+ private MInterval Next {
+ get {
+ MInterval i;
+
+ if (Right != null)
+ {
+ for (i = Right; i.Left != null; i = i.Left)
+ i.update_from_to ();
+ i.update_from_to ();
+ }
+ else
+ {
+ MInterval child = this;
+ for (i = Parent; i != null && i.Right == child;
+ child = i, i = i.Parent);
+ }
+ return i;
+ }
+ }
+
+ private MInterval find_head (int pos)
+ {
+ update_from_to ();
+ if (pos < From)
+ return Left.find_head (pos);
+ if (pos >= To)
+ return Right.find_head (pos);
+ return this;
+ }
+
+ private MInterval find_tail (int pos)
+ {
+ update_from_to ();
+ if (pos <= From)
+ return Left.find_tail (pos);
+ if (pos > To)
+ return Right.find_tail (pos);
+ return this;
+ }
+
+ private bool mergeable (MInterval i)
+ {
+ MPlist p1, p2;
+
+ if (Stack.IsEmpty && i.Stack.IsEmpty)
+ return true;
+ if (isSensitive)
+ return false;
+ for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
+ p1 = p1.Next, p2 = p2.Next)
+ if (p1.Val != p2.Val)
+ return false;
+ return (p1.IsEmpty && p2.IsEmpty);
+ }
+
+ // p-. or .-p p-. or .-p
+ // .-this-. .-right-.
+ // left .-right-. -> .-this-. c2
+ // c1 c2 left c1
+ private MInterval promote_right ()
+ {
+ MInterval c1 = Right.Left;
+
+ // Update Parent.
+ if (Parent == null)
+ mtext.intervals.Put (Key, Right);
+ else if (Parent.Left == this)
+ Parent.Left = Right;
+ else
+ Parent.Right = Right;
+
+ // Update Right.
+ Right.Parent = Parent;
+ Right.Left = this;
+ Right.Length += LeftLength + (To - From);
+
+ // Update this.
+ Parent = Right;
+ Right = c1;
+ Length = LeftLength + (To - From) + RightLength;
+
+ // Update C1 if necessary.
+ if (c1 != null)
+ c1.Parent = this;
+
+ Parent.update_from_to ();
+ return Parent;
+ }
+
+ // p-. or .-p p-. or .-p
+ // .-this-. .-left-.
+ // .-left-. .-right-. -> c1 .-this-.
+ // c1 c2 c2 right
+ private MInterval promote_left ()
+ {
+ MInterval c2 = Left.Right;
+
+ // Update Parent.
+ if (Parent == null)
+ mtext.intervals.Put (Key, Left);
+ else if (Parent.Left == this)
+ Parent.Left = Left;
+ else
+ Parent.Right = Left;
+
+ // Update Left.
+ Left.Parent = Parent;
+ Left.Right = this;
+ Left.Length += (To - From) + RightLength;
+
+ // Update this.
+ Parent = Left;
+ Left = c2;
+ Length = LeftLength + (To - From) + RightLength;
+
+ // Update C2 if necessary.
+ if (c2 != null)
+ c2.Parent = this;
+
+ Parent.update_from_to ();
+ return Parent;
+ }
+
+ public MInterval Find (int pos, out int from, out int to)
+ {
+ MInterval i = find_head (pos);
+
+ from = to = pos;
+ if (i.Stack.IsEmpty)
+ i = i.Next;
+ if (i != null)
+ {
+ from = i.From;
+ to = i.To;
+ }
+ return i;
+ }
+
+ public MInterval Balance ()
+ {
+ MInterval i = this;
+
+ update_from_to ();
+ while (true)
+ {
+ // .-this-.
+ // .-left-. .-right-.
+ // c1 c2 c3 c4
+ int diff = i.LeftLength - i.RightLength;
+ int new_diff;
+
+ if (diff > 0)
+ {
+ new_diff = (i.Length - i.LeftLength
+ + i.Left.RightLength - i.Left.LeftLength);
+ if (Math.Abs (new_diff) >= diff)
+ break;
+ M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
+ i = i.promote_left ();
+ M17n.DebugPrint ("done\n");
+ i.Right.Balance ();
+ }
+ else if (diff < 0)
+ {
+ new_diff = (i.Length - i.RightLength
+ + i.Right.LeftLength - i.Right.RightLength);
+ if (Math.Abs (new_diff) >= diff)
+ break;
+ M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
+ i = i.promote_right ();
+ i.Left.Balance ();
+ }
+ else
+ break;
+ }
+ return i;
+ }
+
+ public MInterval Copy (MText mt, int start, int end)
+ {
+ MInterval copy, left_copy = null, right_copy = null;
+
+ update_from_to ();
+
+ if (start < From)
+ {
+ if (end <= From)
+ return Left.Copy (mt, start, end);
+ left_copy = Left.Copy (mt, start, From);
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ return Right.Copy (mt, start, end);
+ right_copy = Right.Copy (mt, To, end);
+ }
+
+ copy = new MInterval (Key, null, end - start, Stack);
+ copy.mtext = mt;
+ if (isSensitive && (From < start || end < To))
+ copy.Stack.Clear ();
+ if (left_copy != null)
+ {
+ copy.Left = left_copy;
+ left_copy.Parent = copy;
+ }
+ if (right_copy != null)
+ {
+ copy.Right = right_copy;
+ right_copy.Parent = copy;
+ }
+ return copy;
+ }
+
+ public MInterval Copy (MText mt, int start, int end,
+ bool first, bool last)
+ {
+ MInterval copy = Copy (mt, start, end);
+ MInterval head = find_head (start);
+ MInterval tail = find_tail (end);
+
+ M17n.DebugPrint ("Copying: {0}", copy);
+
+ if (! head.Stack.IsEmpty
+ && (isSensitive && head.From < start
+ || (isFrontSensitive && ! first)))
+ {
+ M17n.DebugPrint (" clear head");
+ head = copy.find_head (0);
+ head.Stack.Clear ();
+ }
+ if (! tail.Stack.IsEmpty
+ && (isSensitive && end < tail.To
+ || (isRearSensitive && ! last)))
+ {
+ M17n.DebugPrint (" clear tail");
+ tail = copy.find_tail (copy.Length);
+ tail.Stack.Clear ();
+ }
+ M17n.DebugPrint ("\n");
+ return copy;
+ }
+
+ // this-. ==> this-.
+ // right newright-.
+ // right
+ private MInterval divide_right (int pos)
+ {
+ MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
+
+ M17n.DebugPrint ("divide-right({0}) at {1}\n", pos, this);
+ To = pos;
+ if (Right != null)
+ {
+ interval.Right = Right;
+ Right.Parent = interval;
+ interval.Length += Right.Length;
+ }
+ interval.Parent = this;
+ Right = interval;
+ return interval;
+ }
+
+ // .-this ==> .-this
+ // left .-newleft
+ // left
+ private MInterval divide_left (int pos)
+ {
+ MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
+
+ M17n.DebugPrint ("divide-left({0}) at {1}\n", pos, this);
+ From = pos;
+ if (Left != null)
+ {
+ interval.Left = Left;
+ Left.Parent = interval;
+ interval.Length += Left.Length;
+ }
+ interval.Parent = this;
+ Left = interval;
+ return interval;
+ }
+
+ private void set_mtext (MText mt)
+ {
+ mtext = mt;
+ if (Left != null)
+ Left.set_mtext (mt);
+ if (Right != null)
+ Right.set_mtext (mt);
+ }
+
+ private void enlarge (int len)
+ {
+ Length += len;
+ To += len;
+ for (MInterval prev = this, i = this.Parent; i != null;
+ prev = i, i = i.Parent)
+ {
+ i.Length += len;
+ if (prev == i.Left)
+ {
+ i.From += len;
+ i.To += len;;
+ }
+ }
+ }
+
+ private int graft_forward (MInterval interval, int start, int end)
+ {
+ int len;
+
+ if (! Stack.IsEmpty && isRearSticky)
+ len = end - start;
+ else if (interval == null)
+ len = Stack.IsEmpty ? end - start : 0;
+ else
+ {
+ MInterval i = interval.find_head (start);
+
+ len = 0;
+ if (Stack.IsEmpty
+ && (isFrontSensitive || (isSensitive && i.From < start)))
+ {
+ M17n.DebugPrint (" forward grafting {0}", i);
+ if (i.To < end)
+ len = i.To - start;
+ else
+ len = end - start;
+ i = i.Next;
+ }
+ while (i != null && i.From < end && mergeable (i))
+ {
+ M17n.DebugPrint (" forward grafting {0}", i);
+ len += i.To - i.From;
+ if (i.From < start)
+ len -= start - i.From;
+ if (i.To >= end)
+ {
+ len -= i.To - end;
+ break;
+ }
+ i = i.Next;
+ }
+ }
+
+ M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
+ if (len > 0)
+ enlarge (len);
+ return len;
+ }
+
+ private int graft_backward (MInterval interval, int start, int end)
+ {
+ int len;
+
+ if (! Stack.IsEmpty && isFrontSticky)
+ len = end - start;
+ else if (interval == null)
+ len = Stack.IsEmpty ? end - start : 0;
+ else
+ {
+ MInterval i = interval.find_tail (end);
+
+ len = 0;
+ if (Stack.IsEmpty
+ && (isRearSensitive || (isSensitive && end < i.To)))
+ {
+ M17n.DebugPrint (" backward grafting {0}", i);
+ if (i.From <= start)
+ len = end - start;
+ else
+ len = end - i.From;
+ i = i.Prev;
+ }
+ while (i != null && i.To <= start && mergeable (i))
+ {
+ M17n.DebugPrint (" backward grafting {0}", i);
+ len += i.To - i.From;
+ if (end < i.To)
+ len -= i.To - end;
+ if (i.From <= start)
+ {
+ len -= start - i.From;
+ break;
+ }
+ i = i.Prev;
+ }
+ }
+
+ M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
+ if (len > 0)
+ enlarge (len);
+ return len;
+ }
+
+ public void Insert (int pos, MInterval interval, int start, int end)
+ {
+ update_from_to ();
+
+ M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}",
+ start, end, pos, this);
+
+ if (pos < From)
+ Left.Insert (pos, interval, start, end);
+ else if (pos == From)
+ {
+ MInterval prev = Left != null ? Prev : null;
+
+ if (isFrontSensitive)
+ Stack.Clear ();
+ if (prev != null && isRearSensitive)
+ prev.Stack.Clear ();
+ if (prev != null && isRearSticky && ! prev.Stack.IsEmpty)
+ {
+ prev.enlarge (end - start);
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ if (isFrontSticky && ! Stack.IsEmpty)
+ {
+ enlarge (end - start);
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ bool front_grafted = false, rear_grafted = false;
+ int grafted;
+ if (prev != null
+ && (grafted = prev.graft_forward (interval, start, end)) > 0)
+ {
+ start += grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ front_grafted = true;
+ }
+ if ((grafted = graft_backward (interval, start, end)) > 0)
+ {
+ end -= grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ rear_grafted = true;
+ }
+
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end,
+ (front_grafted
+ || (prev == null && start == 0)),
+ rear_grafted);
+ else
+ interval = new MInterval (Key, mtext, end - start, null);
+
+ MInterval i;
+ if (Left != null)
+ {
+ // .-this-. ==> .-this-.
+ // left-. .-left-.
+ // child child-.
+ // interval
+ i = Left.RightMost;
+ i.Right = interval;
+ }
+ else
+ {
+ Left = interval;
+ i = this;
+ }
+ interval.Parent = i;
+ for (; i != null; i = i.Parent)
+ i.Length += interval.Length;
+ }
+ else if (pos < To)
+ {
+ if (! Stack.IsEmpty)
+ {
+ if (isSensitive)
+ Stack.Clear ();
+ else if (isFrontSticky || isRearSticky)
+ {
+ enlarge (end - start);
+ return;
+ }
+ }
+ bool front_grafted = false, rear_grafted = false;
+ int grafted;
+ if ((grafted = graft_forward (interval, start, end)) > 0)
+ {
+ start += grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ front_grafted = true;
+ pos += grafted;
+ }
+ if ((grafted = graft_backward (interval, start, end)) > 0)
+ {
+ end -= grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ rear_grafted = true;
+ }
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end,
+ front_grafted, rear_grafted);
+ else
+ interval = new MInterval (Key, mtext, end - start, null);
+
+ divide_right (pos);
+ Right.Left = interval;
+ interval.Parent = Right;
+ for (MInterval i = Right; i != null; i = i.Parent)
+ i.Length += interval.Length;
+ }
+ else if (pos == To)
+ {
+ MInterval next = Right != null ? Next : null;
+
+ if (isRearSensitive)
+ Stack.Clear ();
+ if (next != null && isFrontSensitive)
+ next.Stack.Clear ();
+ if (isRearSticky && ! Stack.IsEmpty)
+ {
+ enlarge (end - start);
+ M17n.DebugPrint (" done by enlarging this\n");
+ return;
+ }
+ if (next != null && isFrontSticky && ! next.Stack.IsEmpty)
+ {
+ M17n.DebugPrint (" next is {0}\n", next);
+ next.enlarge (end - start);
+ M17n.DebugPrint (" done by enlarging next\n");
+ return;
+ }
+ bool front_grafted = false, rear_grafted = false;
+ int grafted;
+ if (next != null
+ && (grafted = next.graft_backward (interval, start, end)) > 0)
+ {
+ end -= grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ rear_grafted = true;
+ }
+ if ((grafted = graft_forward (interval, start, end)) > 0)
+ {
+ start += grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ front_grafted = true;
+ }
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end,
+ front_grafted,
+ (rear_grafted
+ || (next == null && end == interval.mtext.Length)));
+ else
+ interval = new MInterval (Key, mtext, end - start, null);
+
+ MInterval i;
+ if (Right != null)
+ {
+ // .-this-. ==> .-this-.
+ // .-right .-right
+ // child .-child
+ // interval
+
+ i = Right.LeftMost;
+ i.Left = interval;
+ }
+ else
+ {
+ Right = interval;
+ i = this;
+ }
+ interval.Parent = i;
+ for (; i != null; i = i.Parent)
+ i.Length += interval.Length;
+ }
+ else // (pos > To)
+ Right.Insert (pos, interval, start, end);
+ M17n.DebugPrint (" done\n");
+ }
+
+ private void vacate_node (MInterval interval)
+ {
+ vacate_node (interval, null);
+ }
+
+ private void vacate_node (MInterval interval, MInterval stop)
+ {
+ if (interval != null)
+ M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
+ else
+ M17n.DebugPrint ("vacate #{0} to null\n", ID);
+ if (interval != null)
+ interval.Parent = Parent;
+ if (Parent == null)
+ {
+ if (mtext != null)
+ mtext.intervals.Put (Key, interval);
+ }
+ else
+ {
+ if (this == Parent.Right)
+ Parent.Right = interval;
+ else
+ Parent.Left = interval;
+
+ int diff = Length;
+ if (interval != null)
+ diff -= interval.Length;
+ for (MInterval i = Parent; i != stop; i = i.Parent)
+ i.Length -= diff;
+ }
+ }
+
+ public void Delete (int start, int end)
+ {
+ update_from_to ();
+ M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this);
+
+ bool front_checked = false;
+ bool rear_checked = false;
+
+ if (start < From)
+ {
+ if (end <= From)
+ {
+ if (end == From && isFrontSensitive)
+ Stack.Clear ();
+ Left.Delete (start, end);
+ return;
+ }
+ if (isSensitive)
+ Stack.Clear ();
+ Left.Delete (start, From);
+ To -= From - start;
+ end -= From - start;
+ From = start;
+ front_checked = true;
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ {
+ if (start == To && isRearSensitive)
+ Stack.Clear ();
+ Right.Delete (start, end);
+ return;
+ }
+ if (isSensitive)
+ Stack.Clear ();
+ Right.Delete (To, end);
+ end = To;
+ rear_checked = true;
+ }
+ if (start == From
+ && ! front_checked
+ && start > 0
+ && isRearSensitive)
+ Prev.Stack.Clear ();
+ if (end == To
+ && ! rear_checked
+ && Next != null
+ && isFrontSensitive)
+ Next.Stack.Clear ();
+ if (start == From && end == To)
+ {
+ if (Right == null)
+ {
+ vacate_node (Left);
+ }
+ else
+ {
+ if (Left != null)
+ {
+ MInterval i;
+
+ for (i = Right; i.Left != null; i = i.Left)
+ i.Length += Left.Length;
+ i.Length += Left.Length;
+ i.Left = Left;
+ Left.Parent = i;
+ }
+ vacate_node (Right);
+ }
+ }
+ else
+ {
+ int len = end - start;
+
+ if (isSensitive)
+ Stack.Clear ();
+ for (MInterval i = this; i != null; i = i.Parent)
+ i.Length -= len;
+ }
+ }
+
+ public void Push (int start, int end, MProperty prop)
+ {
+ update_from_to ();
+ M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this);
+ if (start < From)
+ {
+ if (end <= From)
+ {
+ Left.Push (start, end, prop);
+ return;
+ }
+ Left.Push (start, From, prop);
+ start = From;
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ {
+ Right.Push (start, end, prop);
+ return;
+ }
+ Right.Push (To, end, prop);
+ end = To;
+ }
+
+ if (! Stack.IsEmpty && isSensitive)
+ Stack.Clear ();
+ if (start > From)
+ divide_left (start);
+ if (end < To)
+ divide_right (end);
+ Stack.Push (prop.key, prop);
+ }
+
+ /// Combine intervals between HEAD and TAIL (both inclusive) to
+ /// the common parent of HEAD and TAIL. Callers should assure
+ /// that the intervals are mergeable in advance.
+ private static void combine (MInterval head, MInterval tail)
+ {
+ M17n.DebugPrint ("combining {0} through {1}", head, tail);
+
+ head.update_from_to ();
+ tail.update_from_to ();
+ int from = head.From;
+ int to = tail.To;
+
+ // The nearest common parent of HEAD and TAIL.
+ MInterval root;
+ for (root = head; root.To + root.RightLength < to;
+ root = root.Parent);
+
+ M17n.DebugPrint (" with common root {0}\n", root);
+
+ if (from < root.From)
+ {
+ MInterval prev = root.Prev;
+
+ while (true)
+ {
+ M17n.DebugPrint ("merging {0}\n", prev);
+ prev.vacate_node (prev.Left, root);
+ if (prev == head)
+ break;
+ if (prev.Left != null)
+ prev = prev.Left.RightMost;
+ else
+ prev = prev.Parent;
+ }
+ root.update_from_to ();
+ }
+ if (root.To < to)
+ {
+ MInterval next = root.Next;
+
+ while (true)
+ {
+ M17n.DebugPrint ("merging {0}\n", next);
+ next.vacate_node (next.Right, root);
+ if (next == tail)
+ break;
+ if (next.Right != null)
+ next = next.Right.LeftMost;
+ else
+ next = next.Parent;
+ }
+ root.update_from_to ();
+ }
+ }
+
+ public void MergeAfterChange (int start, int end)
+ {
+ update_from_to ();
+
+ MInterval head = find_head (start), i = head;
+ MInterval tail = start < end ? find_tail (end) : head;
+
+ if (tail.To < Length)
+ tail = tail.Next;
+
+ if (start == head.From && start > 0)
+ {
+ MInterval prev = head.Prev;
+ if (head.mergeable (prev))
+ head = prev;
+ }
+ M17n.DebugPrint ("merge between {0} and {1}\n", head, tail);
+ while (i != tail)
+ {
+ MInterval next = i.Next;
+
+ if (! i.mergeable (next))
+ {
+ if (head != i)
+ combine (head, i);
+ head = next;
+ }
+ i = next;
+ }
+ if (head != i)
+ combine (head, i);
+ }
+
+ public void Pop (int start, int end)
+ {
+ update_from_to ();
+ M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this);
+ if (start < From)
+ {
+ if (end <= From)
+ {
+ Left.Pop (start, end);
+ return;
+ }
+ Left.Pop (start, From);
+ start = From;
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ {
+ Right.Pop (start, end);
+ return;
+ }
+ Right.Pop (To, end);
+ end = To;
+ }
+
+ if (! Stack.IsEmpty)
+ {
+ if (isSensitive)
+ Stack.Clear ();
+ else
+ {
+ if (start > From)
+ divide_left (start);
+ if (end < To)
+ divide_right (end);
+ Stack.Pop ();
+ }
+ }
+ }
+
+ public void PopSensitive (int start, int end)
+ {
+ update_from_to ();
+ MInterval head = find_head (start);
+ MInterval tail = find_tail (end);
+ Pop (head.From, tail.To);
+ }
+
+ public void PopAll (int start, int end)
+ {
+ update_from_to ();
+ M17n.DebugPrint ("popall({0} {1}) at {2}\n", start, end, this);
+ if (start < From)
+ {
+ if (end <= From)
+ {
+ Left.PopAll (start, end);
+ return;
+ }
+ Left.PopAll (start, From);
+ start = From;
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ {
+ Right.PopAll (start, end);
+ return;
+ }
+ Right.PopAll (To, end);
+ end = To;
+ }
+
+ if (! Stack.IsEmpty)
+ {
+ if (isSensitive)
+ Stack.Clear ();
+ else
+ {
+ if (start > From)
+ divide_left (start);
+ if (end < To)
+ divide_right (end);
+ Stack.Clear ();
+ }
+ }
+ }
+
+ public override string ToString ()
+ {
+ string str = String.Format ("#{0}({1} {2} {3} [", ID, Length, From, To);
+ bool first = true;
+ foreach (MPlist p in Stack)
+ {
+ if (first)
+ {
+ str += ((MProperty) p.Val).Val;
+ first = false;
+ }
+ else
+ str += " " + ((MProperty) p.Val).Val;
+ }
+ return (str + "])");
+ }
+
+ private void DumpOne (bool with_prop, bool newline, bool force)
+ {
+ if (force || M17n.debug)
+ {
+ Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
+ if (with_prop && ! Stack.IsEmpty)
+ {
+ string prepend = " [";
+ foreach (MPlist p in Stack)
+ {
+ Console.Write (prepend + ((MProperty) p.Val).Val);
+ prepend = " ";
+ }
+ Console.Write ("]");
+ }
+ Console.Write (")");
+ if (newline)
+ Console.WriteLine ();
+ if (Length <= 0)
+ throw new Exception ("Invalid interval length");
+ }
+ }
+
+ public void Dump () { Dump (false); }
+
+ public void Dump (bool force)
+ {
+ if (force || M17n.debug)
+ {
+ update_from_to ();
+
+ if (Left != null)
+ Left.Dump (force);
+ if (From > 0)
+ Console.Write (" ");
+ DumpOne (true, false, force);
+ if (Right != null)
+ Right.Dump (force);
+ }
+ }
+
+ private int Depth {
+ get { return (Parent == null ? 0 : Parent.Depth + 1); }
+ }
+
+ public void DumpNested (bool force)
+ {
+ DumpNested (" " + Key.ToString () + ":", force);
+ }
+
+ public void DumpNested (string indent, bool force)
+ {
+ if (force || M17n.debug)
+ {
+ int indent_type = (Parent == null ? 1
+ : Parent.Left == this ? 0 : 2);
+
+ update_from_to ();
+ if (Left != null)
+ {
+ if (indent_type <= 1)
+ Left.DumpNested (indent + " ", force);
+ else
+ Left.DumpNested (indent + "| ", force);
+ }
+ Console.Write (indent);
+ if (indent_type == 0)
+ Console.Write (".-");
+ else if (indent_type == 2)
+ Console.Write ("`-");
+ DumpOne (true, true, true);
+ if (Right != null)
+ {
+ if (indent_type >= 1)
+ Right.DumpNested (indent + " ", force);
+ else
+ Right.DumpNested (indent + "| ", force);
+ }
+ }
+ }
+ }
+
+ private class MTextEnum : IEnumerator
+ {
+ private MText mt;
+ private int pos = -1;
+
+ public MTextEnum (MText mt)
+ {
+ this.mt = mt;
+ }
+
+ public bool MoveNext ()
+ {
+ pos++;
+ return (pos < mt.nchars);
+ }
+
+ public void Reset ()
+ {
+ pos = -1;
+ }
+
+ public object Current
+ {
+ get {
+ //if (pos < 0 || pos >= mt.nchars)
+ //throw new InvalidOperationException ();
+ return mt[pos];
+ }
+ }
+ }