3 using System.Collections;
4 using System.Collections.Generic;
11 public enum MTextFormat
13 MTEXT_FORMAT_US_ASCII,
15 MTEXT_FORMAT_UTF_16BE,
16 MTEXT_FORMAT_UTF_16LE,
17 MTEXT_FORMAT_UTF_32BE,
18 MTEXT_FORMAT_UTF_32LE,
22 public class MProperty
29 /// On inserting a text in between two characters, if the
30 /// preceding and following characters have Sticky properties of
31 /// the same key with same values, the inserted text inherits
32 /// those properties. In that case, properties of the inserted
33 /// text are overriden.
34 Sticky = 0x01, // 00000001
36 /// On inserting a text before a character, if the character has
37 /// FrontSticky properties, the inserted text inherits those
39 FrontSticky = 0x03, // 00000011
41 /// On inserting a text after a character, if the character has
42 /// RearSticky properties, the inserted text inherits those
44 RearSticky = 0x05, // 00000101
46 /// Like RearSticky, but if the inserted text inherits no
47 /// properties from the preceding character, it inherits
48 /// BothSticky properties from the following character if any.
49 BothSticky = 0x07, // 00000111
51 /// This property is deleted from a span of text if the span is
52 /// modified (i.e. one of a character is changed, a text is
53 /// inserted, some part is deleted). Here, "span" means a
54 /// sequence of characters that has this property with the same
55 /// value. This property is also deleted if a property of the
56 /// same key is added, which means that this property is not
57 /// stackable. In addition this property is never merged with
58 /// the same value of preceding or following property. At last,
59 /// this property can't be sticky in any way.
60 Sensitive = 0x10, // 00010000
62 /// Like Sensitive but also this property is deleted from a span
63 /// of text if a characeter just before the span is modified,
64 /// inserted, or deleted.
65 FrontSensitive = 0x30, // 00110000
67 /// Like Sensitive but also this property is deleted from a span
68 /// of text if a character just after the span is modified,
69 /// inserted, or deleted.
70 RearSensitive = 0x50, // 01010000
72 /// Same as (FrontSensitive | RearSensitive).
73 BothSensitive = 0x70, // 01110000
79 public MSymbol Key { get { return key; } }
80 public object Val { get { return val; } }
82 public MProperty (MSymbol key, object val)
84 if (key.flags == null)
85 key.flags = Flags.None;
90 public MProperty (string name, object val)
92 key = MSymbol.PropertyKey (name);
96 public static bool HasFlags (MSymbol key, Flags flags)
98 return ((key.flags & flags) == flags);
101 public override string ToString ()
103 return key.ToString () + ":" + val;
107 public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
110 public enum MTextFormat format;
112 private StringBuilder sb;
114 private int cache_pos;
115 private int cache_idx;
116 private MPlist intervals;
117 private MPlist default_property;
118 private bool read_only = false;
120 private static UTF8Encoding utf8 = new UTF8Encoding ();
122 private static int count_chars (String str)
124 int len = str.Length, n = 0;
126 for (int i = 0; i < len; i++, n++)
127 if (Char.IsHighSurrogate (str[i]))
132 private static int count_chars (StringBuilder str)
134 int len = str.Length, n = 0;
136 for (int i = 0; i < len; i++, n++)
137 if (Char.IsHighSurrogate (str[i]))
144 sb = new StringBuilder ();
145 intervals = new MPlist ();
148 public MText (byte[] str)
150 sb = new StringBuilder (utf8.GetString (str));
151 nchars = count_chars (sb);
152 intervals = new MPlist ();
155 public MText (byte[] str, int offset, int length)
157 sb = new StringBuilder (utf8.GetString (str, offset, length));
158 nchars = count_chars (sb);
159 intervals = new MPlist ();
162 public MText (String str)
164 sb = new StringBuilder (str);
165 nchars = count_chars (str);
166 intervals = new MPlist ();
169 public MText (StringBuilder str)
172 nchars = count_chars (str);
173 intervals = new MPlist ();
176 public MText (int c, int len) : this ()
182 public MText (int c) : this (c, 1) { }
184 public static MText operator+ (object obj, MText mt)
188 MText mtnew = new MText ((string) obj);
189 return mtnew.Ins (mtnew.Length, mt);
191 throw new Exception ("Unknown object type: " + obj.GetType());
194 public static MText operator+ (MText mt, object obj)
197 return mt + new MText ((string) obj);
199 return mt.Dup ().Ins (mt.Length, (int) obj);
201 return mt.Dup ().Ins (mt.Length, (int) ((char) obj));
202 throw new Exception ("Unknown object type: " + obj.GetType());
205 public static MText operator+ (MText mt1, MText mt2)
207 return mt1.Dup ().Ins (mt1.Length, mt2);
211 public bool ReadOnly { get { return read_only; } }
212 public int Length { get { return nchars; } }
216 // for IEnumerable interface
217 public IEnumerator GetEnumerator() { return new MTextEnum (this); }
219 // for IEquatable interface
220 public bool Equals (MText other) { return this.sb.Equals (other.sb); }
222 // for IComparable interface
223 public int CompareTo (MText other)
225 return this.sb.ToString ().CompareTo (other.sb.ToString ());
228 public override string ToString () { return sb.ToString (); }
230 public static implicit operator MText (string str)
232 return new MText (str);
235 public static explicit operator string (MText mt)
237 return mt.ToString ();
240 private static int inc_idx (StringBuilder sb, int i)
242 return (i + (Char.IsHighSurrogate (sb[i]) ? 2 : 1));
245 private static int dec_idx (StringBuilder sb, int i)
247 return (i - (Char.IsLowSurrogate (sb[i - 1]) ? 2 : 1));
250 private static int pos_to_idx (MText mt, int pos)
252 if (pos == mt.cache_pos)
258 if (pos < mt.cache_pos)
260 if (mt.cache_pos == mt.cache_idx)
262 if (pos < mt.cache_pos - pos)
269 p = mt.cache_pos; i = mt.cache_idx;
275 if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
276 return (mt.cache_idx + pos - mt.cache_pos);
277 if (pos - mt.cache_pos < mt.nchars - pos)
279 p = mt.cache_pos; i = mt.cache_idx;
284 p = mt.nchars; i = mt.sb.Length;
289 for (; p < pos; i = inc_idx (mt.sb, i), p++);
291 for (; p > pos; i = dec_idx (mt.sb, i), p--);
297 private void check_pos (int pos, bool tail_ok)
299 if (pos < 0 || (tail_ok ? pos > nchars : pos >= nchars))
300 throw new Exception ("Invalid MText position:" + pos);
303 private bool check_range (int from, int to, bool zero_ok)
305 if (from < 0 || (zero_ok ? from > to : from >= to)
307 throw new Exception ("Invalid MText range");
311 private void insert (int pos, MText mt2, int from, int to)
313 check_pos (pos, true);
317 Console.Write ("inserting {0} to {1} of ", from, to);
318 mt2.DumpPropNested ();
322 foreach (MPlist plist in intervals)
324 MInterval root = (MInterval) plist.Val;
325 MPlist p = mt2.intervals.Find (plist.Key);
326 MInterval i = p == null ? null : (MInterval) p.Val;
328 root.Insert (pos, i, from, to);
330 foreach (MPlist plist in mt2.intervals)
331 if (intervals.Find (plist.Key) == null)
336 root = ((MInterval) plist.Val).Copy (this, from, to);
339 root = new MInterval (plist.Key, this);
340 root.Insert (pos, (MInterval) plist.Val, from, to);
342 intervals.Push (plist.Key, root);
345 int pos_idx = pos_to_idx (this, pos);
346 int from_idx = pos_to_idx (mt2, from);
347 int to_idx = pos_to_idx (mt2, to);
349 sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
353 private void insert (int pos, int c)
355 check_pos (pos, true);
357 int pos_idx = pos_to_idx (this, pos);
362 sb.Insert (pos_idx, ch);
366 char high = (char) (0xD800 + ((c - 0x10000) >> 10));
367 char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF));
368 sb.Insert (pos_idx, low);
369 sb.Insert (pos_idx, high);
372 foreach (MPlist plist in intervals)
373 ((MInterval) plist.Val).Insert (pos, null, 0, 1);
376 public int this[int i]
379 i = pos_to_idx (this, i);
382 if (Char.IsHighSurrogate (sb[i]))
384 sb[i] = (char) value;
388 char high = (char) (0xD800 + ((value - 0x10000) >> 10));
389 char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
391 if (! Char.IsHighSurrogate (sb[i]))
399 i = pos_to_idx (this, i);
400 return (Char.IsHighSurrogate (sb[i])
401 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
406 public MText this[int from, int to]
414 get { return Dup (from, to); }
419 MText mt = new MText (sb.ToString ());
421 foreach (MPlist p in intervals)
422 mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, 0, Length));
426 public MText Dup (int from, int to)
428 if (check_range (from, to, true))
430 int from_idx = pos_to_idx (this, from);
431 int len = pos_to_idx (this, to) - from_idx;
432 MText mt = new MText (sb.ToString ().Substring (from_idx, len));
434 foreach (MPlist p in intervals)
435 mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, from, to));
439 public MText Ins (int pos, int c)
445 public MText Ins (int pos, MText mt)
447 insert (pos, mt, 0, mt.nchars);
451 public MText Ins (int pos, MText mt, int from, int to)
453 insert (pos, mt, from, to);
457 public MText Cat (int c)
463 public MText Cat (MText mt)
465 insert (nchars, mt, 0, mt.Length);
469 public MText Cat (MText mt, int from, int to)
471 insert (nchars, mt, from, to);
477 return Del (0, Length);
480 public MText Del (int from, int to)
482 if (check_range (from, to, true))
484 sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
487 foreach (MPlist plist in intervals)
489 MInterval root = (MInterval) plist.Val;
490 root.Delete (from, to);
491 if (from > 0 && from < nchars)
492 ((MInterval) plist.Val).MergeAfterChange (from, from);
501 public object GetProp (int pos, MSymbol key)
503 check_pos (pos, false);
505 MInterval i = (MInterval) intervals.Get (key);
509 MProperty prop = i.Get (pos);
510 return (prop != null ? prop.Val : null);
513 public object GetProp (int pos, MSymbol key, out MProperty prop)
515 check_pos (pos, false);
517 MInterval i = (MInterval) intervals.Get (key);
519 return (prop = null);
521 return (prop != null ? prop.Val : null);
524 public object GetProp (int pos, MSymbol key, out MProperty[] array)
526 check_pos (pos, false);
528 MInterval i = (MInterval) intervals.Get (key);
530 return (array = null);
531 MProperty prop = i.Get (pos, out array);
532 return (prop != null ? prop.Val : null);
535 public void PushProp (int from, int to, MSymbol key, object val)
537 if (! check_range (from, to, true))
538 PushProp (from, to, new MProperty (key, val));
541 public void PushProp (int from, int to, MProperty prop)
545 if (default_property == null)
546 default_property = new MPlist ();
547 default_property.Push (prop.key, prop.val);
551 if (check_range (from, to, true))
554 MPlist p = intervals.Find (prop.key);
559 root = new MInterval (prop.key, this);
560 intervals.Push (prop.key, root);
564 root = (MInterval) p.Val;
565 if (root.isSensitive)
567 root.PopSensitive (from, to);
568 root.MergeAfterChange (from, to);
569 root = (MInterval) p.Val;
574 root.Push (from, to, prop);
575 root.MergeAfterChange (from, to);
580 public void PopProp (int from, int to)
584 default_property = null;
588 if (check_range (from, to, true))
590 for (MPlist p = intervals; ! p.IsEmpty; p = p.next)
592 MInterval root = (MInterval) p.Val;
593 root.PopAll (from, to);
594 root = (MInterval) p.Val;
597 root.MergeAfterChange (from, to);
603 public void PopProp (int from, int to, MSymbol key)
607 if (default_property == null)
609 MPlist p = default_property.Find (key);
616 if (check_range (from, to, true))
619 MPlist p = intervals.Find (key);
623 MInterval root = (MInterval) p.Val;
624 if (root.isSensitive)
625 root.PopSensitive (from, to);
628 root = (MInterval) p.Val;
631 root.MergeAfterChange (from, to);
637 public object FindProp (MSymbol key, int pos, out int from, out int to)
641 check_pos (pos, false);
643 MInterval i = (MInterval) intervals.Get (key);
645 && (i = i.Find (pos, out from, out to)) != null)
646 return GetProp (from, key);
650 public void DumpProp ()
653 foreach (MPlist p in intervals)
654 ((MInterval) p.Val).Dump (true);
655 Console.WriteLine (")");
658 public void DumpPropNested ()
660 Console.WriteLine ("total length = {0}", Length);
661 foreach (MPlist p in intervals)
662 ((MInterval) p.Val).DumpNested (true);
665 private class MInterval
667 // position: 0 1 2 3 4 5 6 7
668 // | A | B | C | D | E F | G |
669 // interval |---|---|---|<->|-------|---|
670 // |---|<->|---| |<----->|---|
674 // [3 (1 2)] [3 (4 6)]
675 // [1 (0 1)] [2 (2 3)] [1 (6 7)]
677 private static int count = 0;
680 private int From, To;
682 private MPlist Stack;
683 private MInterval Left, Right, Parent;
686 public MInterval (MSymbol key, MText mt, int length)
689 throw new Exception ("Invalid interval length");
693 Stack = new MPlist ();
697 public MInterval (MSymbol key, MText mt)
701 Length = mt.sb.Length;
704 Stack = new MPlist ();
708 /// POS must be smaller than Length;
709 public MProperty Get (int pos)
711 MInterval i = find_head (pos);
713 return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val);
716 /// POS must be smaller than Length;
717 public MProperty Get (int pos, out MProperty[] array)
719 MInterval i = find_head (pos);
728 array = new MProperty[i.Stack.Count];
732 for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
733 array[idx] = (MProperty) p.Val;
737 private MInterval (MSymbol key, MText mt, int length, MPlist stack)
744 Stack = stack == null ? new MPlist () : stack.Clone ();
748 private bool isRearSticky
750 get { return MProperty.HasFlags (Key, MProperty.Flags.RearSticky) ; }
753 private bool isFrontSticky
755 get { return MProperty.HasFlags (Key, MProperty.Flags.FrontSticky) ; }
758 public bool isSensitive
760 get { return MProperty.HasFlags (Key, MProperty.Flags.Sensitive) ; }
763 public bool isFrontSensitive
765 get { return MProperty.HasFlags (Key,
766 MProperty.Flags.FrontSensitive) ; }
769 public bool isRearSensitive
771 get { return MProperty.HasFlags (Key,
772 MProperty.Flags.RearSensitive) ; }
775 private void update_from_to ()
780 To = Length - RightLength;
782 else if (Parent.Left == this)
784 From = Parent.From - Length + LeftLength;
785 To = Parent.From - RightLength;
789 From = Parent.To + LeftLength;
790 To = Parent.To + Length - RightLength;
794 private int LeftLength
796 get { return (Left == null ? 0 : Left.Length); }
799 private int RightLength
801 get { return (Right == null ? 0 : Right.Length); }
804 private MInterval LeftMost
810 return Left.LeftMost;
814 private MInterval RightMost
820 return Right.RightMost;
824 private MInterval Prev {
830 for (i = Left; i.Right != null; i = i.Right)
836 MInterval child = this;
837 for (i = Parent; i != null && i.Left == child;
838 child = i, i = i.Parent);
844 private MInterval Next {
850 for (i = Right; i.Left != null; i = i.Left)
856 MInterval child = this;
857 for (i = Parent; i != null && i.Right == child;
858 child = i, i = i.Parent);
864 private MInterval find_head (int pos)
868 return Left.find_head (pos);
870 return Right.find_head (pos);
874 private MInterval find_tail (int pos)
878 return Left.find_tail (pos);
880 return Right.find_tail (pos);
884 private bool mergeable (MInterval i)
888 if (Stack.IsEmpty && i.Stack.IsEmpty)
892 for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
893 p1 = p1.Next, p2 = p2.Next)
894 if (p1.Val != p2.Val)
896 return (p1.IsEmpty && p2.IsEmpty);
899 // p-. or .-p p-. or .-p
900 // .-this-. .-right-.
901 // left .-right-. -> .-this-. c2
903 private MInterval promote_right ()
905 MInterval c1 = Right.Left;
909 mtext.intervals.Put (Key, Right);
910 else if (Parent.Left == this)
913 Parent.Right = Right;
916 Right.Parent = Parent;
918 Right.Length += LeftLength + (To - From);
923 Length = LeftLength + (To - From) + RightLength;
925 // Update C1 if necessary.
929 Parent.update_from_to ();
933 // p-. or .-p p-. or .-p
935 // .-left-. .-right-. -> c1 .-this-.
937 private MInterval promote_left ()
939 MInterval c2 = Left.Right;
943 mtext.intervals.Put (Key, Left);
944 else if (Parent.Left == this)
950 Left.Parent = Parent;
952 Left.Length += (To - From) + RightLength;
957 Length = LeftLength + (To - From) + RightLength;
959 // Update C2 if necessary.
963 Parent.update_from_to ();
967 public MInterval Find (int pos, out int from, out int to)
969 MInterval i = find_head (pos);
982 public MInterval Balance ()
990 // .-left-. .-right-.
992 int diff = i.LeftLength - i.RightLength;
997 new_diff = (i.Length - i.LeftLength
998 + i.Left.RightLength - i.Left.LeftLength);
999 if (Math.Abs (new_diff) >= diff)
1001 M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
1002 i = i.promote_left ();
1003 M17n.DebugPrint ("done\n");
1008 new_diff = (i.Length - i.RightLength
1009 + i.Right.LeftLength - i.Right.RightLength);
1010 if (Math.Abs (new_diff) >= diff)
1012 M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
1013 i = i.promote_right ();
1022 public MInterval Copy (MText mt, int start, int end)
1024 MInterval copy, left_copy = null, right_copy = null;
1031 return Left.Copy (mt, start, end);
1032 left_copy = Left.Copy (mt, start, From);
1037 return Right.Copy (mt, start, end);
1038 right_copy = Right.Copy (mt, To, end);
1041 copy = new MInterval (Key, null, end - start, Stack);
1043 if (isSensitive && (From < start || end < To))
1044 copy.Stack.Clear ();
1045 if (left_copy != null)
1047 copy.Left = left_copy;
1048 left_copy.Parent = copy;
1050 if (right_copy != null)
1052 copy.Right = right_copy;
1053 right_copy.Parent = copy;
1058 public MInterval Copy (MText mt, int start, int end,
1059 bool first, bool last)
1061 MInterval copy = Copy (mt, start, end);
1062 MInterval head = find_head (start);
1063 MInterval tail = find_tail (end);
1065 M17n.DebugPrint ("Copying: {0}", copy);
1067 if (! head.Stack.IsEmpty
1068 && (isSensitive && head.From < start
1069 || (isFrontSensitive && ! first)))
1071 M17n.DebugPrint (" clear head");
1072 head = copy.find_head (0);
1073 head.Stack.Clear ();
1075 if (! tail.Stack.IsEmpty
1076 && (isSensitive && end < tail.To
1077 || (isRearSensitive && ! last)))
1079 M17n.DebugPrint (" clear tail");
1080 tail = copy.find_tail (copy.Length);
1081 tail.Stack.Clear ();
1083 M17n.DebugPrint ("\n");
1087 // this-. ==> this-.
1090 private MInterval divide_right (int pos)
1092 MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
1094 M17n.DebugPrint ("divide-right({0}) at {1}\n", pos, this);
1098 interval.Right = Right;
1099 Right.Parent = interval;
1100 interval.Length += Right.Length;
1102 interval.Parent = this;
1107 // .-this ==> .-this
1110 private MInterval divide_left (int pos)
1112 MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
1114 M17n.DebugPrint ("divide-left({0}) at {1}\n", pos, this);
1118 interval.Left = Left;
1119 Left.Parent = interval;
1120 interval.Length += Left.Length;
1122 interval.Parent = this;
1127 private void set_mtext (MText mt)
1131 Left.set_mtext (mt);
1133 Right.set_mtext (mt);
1136 private void enlarge (int len)
1140 for (MInterval prev = this, i = this.Parent; i != null;
1141 prev = i, i = i.Parent)
1152 private int graft_forward (MInterval interval, int start, int end)
1156 if (! Stack.IsEmpty && isRearSticky)
1158 else if (interval == null)
1159 len = Stack.IsEmpty ? end - start : 0;
1162 MInterval i = interval.find_head (start);
1166 && (isFrontSensitive || (isSensitive && i.From < start)))
1168 M17n.DebugPrint (" forward grafting {0}", i);
1175 while (i != null && i.From < end && mergeable (i))
1177 M17n.DebugPrint (" forward grafting {0}", i);
1178 len += i.To - i.From;
1180 len -= start - i.From;
1190 M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1196 private int graft_backward (MInterval interval, int start, int end)
1200 if (! Stack.IsEmpty && isFrontSticky)
1202 else if (interval == null)
1203 len = Stack.IsEmpty ? end - start : 0;
1206 MInterval i = interval.find_tail (end);
1210 && (isRearSensitive || (isSensitive && end < i.To)))
1212 M17n.DebugPrint (" backward grafting {0}", i);
1213 if (i.From <= start)
1219 while (i != null && i.To <= start && mergeable (i))
1221 M17n.DebugPrint (" backward grafting {0}", i);
1222 len += i.To - i.From;
1225 if (i.From <= start)
1227 len -= start - i.From;
1234 M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1240 public void Insert (int pos, MInterval interval, int start, int end)
1244 M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}",
1245 start, end, pos, this);
1248 Left.Insert (pos, interval, start, end);
1249 else if (pos == From)
1251 MInterval prev = Left != null ? Prev : null;
1253 if (isFrontSensitive)
1255 if (prev != null && isRearSensitive)
1256 prev.Stack.Clear ();
1257 if (prev != null && isRearSticky && ! prev.Stack.IsEmpty)
1259 prev.enlarge (end - start);
1260 M17n.DebugPrint (" done\n");
1263 if (isFrontSticky && ! Stack.IsEmpty)
1265 enlarge (end - start);
1266 M17n.DebugPrint (" done\n");
1269 bool front_grafted = false, rear_grafted = false;
1272 && (grafted = prev.graft_forward (interval, start, end)) > 0)
1277 M17n.DebugPrint (" done\n");
1280 front_grafted = true;
1282 if ((grafted = graft_backward (interval, start, end)) > 0)
1287 M17n.DebugPrint (" done\n");
1290 rear_grafted = true;
1293 if (interval != null)
1294 interval = interval.Copy (mtext, start, end,
1296 || (prev == null && start == 0)),
1299 interval = new MInterval (Key, mtext, end - start, null);
1304 // .-this-. ==> .-this-.
1316 interval.Parent = i;
1317 for (; i != null; i = i.Parent)
1318 i.Length += interval.Length;
1322 if (! Stack.IsEmpty)
1326 else if (isFrontSticky || isRearSticky)
1328 enlarge (end - start);
1332 bool front_grafted = false, rear_grafted = false;
1334 if ((grafted = graft_forward (interval, start, end)) > 0)
1339 M17n.DebugPrint (" done\n");
1342 front_grafted = true;
1345 if ((grafted = graft_backward (interval, start, end)) > 0)
1350 M17n.DebugPrint (" done\n");
1353 rear_grafted = true;
1355 if (interval != null)
1356 interval = interval.Copy (mtext, start, end,
1357 front_grafted, rear_grafted);
1359 interval = new MInterval (Key, mtext, end - start, null);
1362 Right.Left = interval;
1363 interval.Parent = Right;
1364 for (MInterval i = Right; i != null; i = i.Parent)
1365 i.Length += interval.Length;
1369 MInterval next = Right != null ? Next : null;
1371 if (isRearSensitive)
1373 if (next != null && isFrontSensitive)
1374 next.Stack.Clear ();
1375 if (isRearSticky && ! Stack.IsEmpty)
1377 enlarge (end - start);
1378 M17n.DebugPrint (" done by enlarging this\n");
1381 if (next != null && isFrontSticky && ! next.Stack.IsEmpty)
1383 M17n.DebugPrint (" next is {0}\n", next);
1384 next.enlarge (end - start);
1385 M17n.DebugPrint (" done by enlarging next\n");
1388 bool front_grafted = false, rear_grafted = false;
1391 && (grafted = next.graft_backward (interval, start, end)) > 0)
1396 M17n.DebugPrint (" done\n");
1399 rear_grafted = true;
1401 if ((grafted = graft_forward (interval, start, end)) > 0)
1406 M17n.DebugPrint (" done\n");
1409 front_grafted = true;
1411 if (interval != null)
1412 interval = interval.Copy (mtext, start, end,
1415 || (next == null && end == interval.mtext.Length)));
1417 interval = new MInterval (Key, mtext, end - start, null);
1422 // .-this-. ==> .-this-.
1435 interval.Parent = i;
1436 for (; i != null; i = i.Parent)
1437 i.Length += interval.Length;
1440 Right.Insert (pos, interval, start, end);
1441 M17n.DebugPrint (" done\n");
1444 private void vacate_node (MInterval interval)
1446 vacate_node (interval, null);
1449 private void vacate_node (MInterval interval, MInterval stop)
1451 if (interval != null)
1452 M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
1454 M17n.DebugPrint ("vacate #{0} to null\n", ID);
1455 if (interval != null)
1456 interval.Parent = Parent;
1460 mtext.intervals.Put (Key, interval);
1464 if (this == Parent.Right)
1465 Parent.Right = interval;
1467 Parent.Left = interval;
1470 if (interval != null)
1471 diff -= interval.Length;
1472 for (MInterval i = Parent; i != stop; i = i.Parent)
1477 public void Delete (int start, int end)
1480 M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this);
1482 bool front_checked = false;
1483 bool rear_checked = false;
1489 if (end == From && isFrontSensitive)
1491 Left.Delete (start, end);
1496 Left.Delete (start, From);
1498 end -= From - start;
1500 front_checked = true;
1506 if (start == To && isRearSensitive)
1508 Right.Delete (start, end);
1513 Right.Delete (To, end);
1515 rear_checked = true;
1521 Prev.Stack.Clear ();
1525 && isFrontSensitive)
1526 Next.Stack.Clear ();
1527 if (start == From && end == To)
1539 for (i = Right; i.Left != null; i = i.Left)
1540 i.Length += Left.Length;
1541 i.Length += Left.Length;
1545 vacate_node (Right);
1550 int len = end - start;
1554 for (MInterval i = this; i != null; i = i.Parent)
1559 public void Push (int start, int end, MProperty prop)
1562 M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this);
1567 Left.Push (start, end, prop);
1570 Left.Push (start, From, prop);
1577 Right.Push (start, end, prop);
1580 Right.Push (To, end, prop);
1584 if (! Stack.IsEmpty && isSensitive)
1587 divide_left (start);
1590 Stack.Push (prop.key, prop);
1593 /// Combine intervals between HEAD and TAIL (both inclusive) to
1594 /// the common parent of HEAD and TAIL. Callers should assure
1595 /// that the intervals are mergeable in advance.
1596 private static void combine (MInterval head, MInterval tail)
1598 M17n.DebugPrint ("combining {0} through {1}", head, tail);
1600 head.update_from_to ();
1601 tail.update_from_to ();
1602 int from = head.From;
1605 // The nearest common parent of HEAD and TAIL.
1607 for (root = head; root.To + root.RightLength < to;
1608 root = root.Parent);
1610 M17n.DebugPrint (" with common root {0}\n", root);
1612 if (from < root.From)
1614 MInterval prev = root.Prev;
1618 M17n.DebugPrint ("merging {0}\n", prev);
1619 prev.vacate_node (prev.Left, root);
1622 if (prev.Left != null)
1623 prev = prev.Left.RightMost;
1627 root.update_from_to ();
1631 MInterval next = root.Next;
1635 M17n.DebugPrint ("merging {0}\n", next);
1636 next.vacate_node (next.Right, root);
1639 if (next.Right != null)
1640 next = next.Right.LeftMost;
1644 root.update_from_to ();
1648 public void MergeAfterChange (int start, int end)
1652 MInterval head = find_head (start), i = head;
1653 MInterval tail = start < end ? find_tail (end) : head;
1655 if (tail.To < Length)
1658 if (start == head.From && start > 0)
1660 MInterval prev = head.Prev;
1661 if (head.mergeable (prev))
1664 M17n.DebugPrint ("merge between {0} and {1}\n", head, tail);
1667 MInterval next = i.Next;
1669 if (! i.mergeable (next))
1681 public void Pop (int start, int end)
1684 M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this);
1689 Left.Pop (start, end);
1692 Left.Pop (start, From);
1699 Right.Pop (start, end);
1702 Right.Pop (To, end);
1706 if (! Stack.IsEmpty)
1713 divide_left (start);
1721 public void PopSensitive (int start, int end)
1724 MInterval head = find_head (start);
1725 MInterval tail = find_tail (end);
1726 Pop (head.From, tail.To);
1729 public void PopAll (int start, int end)
1732 M17n.DebugPrint ("popall({0} {1}) at {2}\n", start, end, this);
1737 Left.PopAll (start, end);
1740 Left.PopAll (start, From);
1747 Right.PopAll (start, end);
1750 Right.PopAll (To, end);
1754 if (! Stack.IsEmpty)
1761 divide_left (start);
1769 public override string ToString ()
1771 string str = String.Format ("#{0}({1} {2} {3} [", ID, Length, From, To);
1773 foreach (MPlist p in Stack)
1777 str += ((MProperty) p.Val).Val;
1781 str += " " + ((MProperty) p.Val).Val;
1783 return (str + "])");
1786 private void DumpOne (bool with_prop, bool newline, bool force)
1788 if (force || M17n.debug)
1790 Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1791 if (with_prop && ! Stack.IsEmpty)
1793 string prepend = " [";
1794 foreach (MPlist p in Stack)
1796 Console.Write (prepend + ((MProperty) p.Val).Val);
1799 Console.Write ("]");
1801 Console.Write (")");
1803 Console.WriteLine ();
1805 throw new Exception ("Invalid interval length");
1809 public void Dump () { Dump (false); }
1811 public void Dump (bool force)
1813 if (force || M17n.debug)
1820 Console.Write (" ");
1821 DumpOne (true, false, force);
1828 get { return (Parent == null ? 0 : Parent.Depth + 1); }
1831 public void DumpNested (bool force)
1833 DumpNested (" " + Key.ToString () + ":", force);
1836 public void DumpNested (string indent, bool force)
1838 if (force || M17n.debug)
1840 int indent_type = (Parent == null ? 1
1841 : Parent.Left == this ? 0 : 2);
1846 if (indent_type <= 1)
1847 Left.DumpNested (indent + " ", force);
1849 Left.DumpNested (indent + "| ", force);
1851 Console.Write (indent);
1852 if (indent_type == 0)
1853 Console.Write (".-");
1854 else if (indent_type == 2)
1855 Console.Write ("`-");
1856 DumpOne (true, true, true);
1859 if (indent_type >= 1)
1860 Right.DumpNested (indent + " ", force);
1862 Right.DumpNested (indent + "| ", force);
1868 private class MTextEnum : IEnumerator
1871 private int pos = -1;
1873 public MTextEnum (MText mt)
1878 public bool MoveNext ()
1881 return (pos < mt.nchars);
1884 public void Reset ()
1889 public object Current
1892 //if (pos < 0 || pos >= mt.nchars)
1893 //throw new InvalidOperationException ();