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
28 /// A text inserted before a character that has this property
29 /// inherits this property. If the text already has properties
30 /// of the same key, they are deleted.
32 /// A text inserted after a character that has this property
33 /// inherits this property. If the text already has properties
34 /// of the same key, they are deleted.
36 /// This property is deleted from a span of text if the span is
37 /// modified (i.e. a character is changed, a text is inserted,
38 /// some part is deleted). This propery is also deleted if a
39 /// property of the same key is added, which means that this
40 /// property is not stackable.
42 /// Like Sensitive but also this property is deleted from a span
43 /// of text if a text just before the span is modified,
44 /// inserted, or deleted.
45 FrontSensitive = 0x08,
46 /// Like Sensitive but also this property is deleted from a span
47 /// of text if a text just after the span is modified, inserted,
55 public MSymbol Key { get { return key; } }
56 public object Val { get { return val; } }
58 public MProperty (MSymbol key, object val)
60 if (key.flags == null)
61 key.flags = Flags.None;
66 public MProperty (string name, object val)
68 key = MSymbol.PropertyKey (name);
72 public static bool HasFlags (MSymbol key, Flags flags)
74 return ((key.flags & flags) != Flags.None);
77 public override string ToString ()
79 return key.ToString () + ":" + val;
83 public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
86 public enum MTextFormat format;
88 private StringBuilder sb;
90 private int cache_pos;
91 private int cache_idx;
92 private MPlist intervals;
93 private MPlist default_property;
94 private bool read_only;
96 private static UTF8Encoding utf8 = new UTF8Encoding ();
98 private static int count_chars (String str)
100 int len = str.Length, n = 0;
102 for (int i = 0; i < len; i++, n++)
103 if (surrogate_high_p (str[i]))
108 private static int count_chars (StringBuilder str)
110 int len = str.Length, n = 0;
112 for (int i = 0; i < len; i++, n++)
113 if (surrogate_high_p (str[i]))
120 sb = new StringBuilder ();
121 intervals = new MPlist ();
124 public MText (byte[] str)
126 sb = new StringBuilder (utf8.GetString (str));
127 nchars = count_chars (sb);
128 intervals = new MPlist ();
131 public MText (String str)
133 sb = new StringBuilder (str);
134 nchars = count_chars (str);
135 intervals = new MPlist ();
138 public MText (StringBuilder str)
141 nchars = count_chars (str);
142 intervals = new MPlist ();
145 public static MText operator+ (object obj, MText mt)
149 MText mtnew = new MText ((string) obj);
150 return mtnew.Ins (mtnew.Length, mt);
152 throw new Exception ("Unknown object type: " + obj.GetType());
155 public static MText operator+ (MText mt, object obj)
158 return mt + new MText ((string) obj);
160 return mt.Dup ().Ins (mt.Length, (int) obj);
162 return mt.Dup ().Ins (mt.Length, (int) ((char) obj));
163 throw new Exception ("Unknown object type: " + obj.GetType());
166 public static MText operator+ (MText mt1, MText mt2)
168 return mt1.Dup ().Ins (mt1.Length, mt2);
172 public bool ReadOnly { get { return read_only; } }
173 public int Length { get { return nchars; } }
177 // for IEnumerable interface
178 public IEnumerator GetEnumerator() { return new MTextEnum (this); }
180 // for IEquatable interface
181 public bool Equals (MText other) { return this.sb.Equals (other.sb); }
183 // for IComparable interface
184 public int CompareTo (MText other)
186 return this.sb.ToString ().CompareTo (other.sb.ToString ());
189 public override string ToString () { return sb.ToString (); }
191 private static bool surrogate_high_p (char c)
193 return (c >= 0xD800 && c < 0xDC00);
196 private static bool surrogate_low_p (char c)
198 return (c >= 0xDC00 && c < 0xE000);
201 private static int inc_idx (StringBuilder sb, int i)
203 return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
206 private static int dec_idx (StringBuilder sb, int i)
208 return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
211 private static int pos_to_idx (MText mt, int pos)
213 if (pos == mt.cache_pos)
219 if (pos < mt.cache_pos)
221 if (mt.cache_pos == mt.cache_idx)
223 if (pos < mt.cache_pos - pos)
230 p = mt.cache_pos; i = mt.cache_idx;
236 if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
237 return (mt.cache_idx + pos - mt.cache_pos);
238 if (pos - mt.cache_pos < mt.nchars - pos)
240 p = mt.cache_pos; i = mt.cache_idx;
245 p = mt.nchars; i = mt.sb.Length;
250 for (; p < pos; i = inc_idx (mt.sb, i), p++);
252 for (; p > pos; i = dec_idx (mt.sb, i), p--);
258 private void check_pos (int pos, bool tail_ok)
260 if (pos < 0 || (tail_ok ? pos > nchars : pos >= nchars))
261 throw new Exception ("Invalid MText position:" + pos);
264 private bool check_range (int from, int to, bool zero_ok)
266 if (from < 0 || (zero_ok ? from > to : from >= to)
268 throw new Exception ("Invalid MText range");
272 private void insert (int pos, MText mt2, int from, int to)
274 check_pos (pos, true);
278 Console.Write ("inserting {0} to {1} of ", from, to);
279 mt2.DumpPropNested ();
283 foreach (MPlist plist in intervals)
285 MInterval root = (MInterval) plist.Val;
286 MPlist p = mt2.intervals.Find (plist.Key);
287 MInterval i = p == null ? null : (MInterval) p.Val;
289 root.Insert (pos, i, from, to);
291 foreach (MPlist plist in mt2.intervals)
292 if (intervals.Find (plist.Key) == null)
297 root = ((MInterval) plist.Val).Copy (this, from, to);
300 root = new MInterval (plist.Key, this);
301 root.Insert (pos, (MInterval) plist.Val, from, to);
303 intervals.Push (plist.Key, root);
306 int pos_idx = pos_to_idx (this, pos);
307 int from_idx = pos_to_idx (mt2, from);
308 int to_idx = pos_to_idx (mt2, to);
310 sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
314 private void insert (int pos, int c)
316 check_pos (pos, true);
318 int pos_idx = pos_to_idx (this, pos);
323 sb.Insert (pos_idx, ch);
327 char high = (char) (0xD800 + ((c - 0x10000) >> 10));
328 char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF));
329 sb.Insert (pos_idx, low);
330 sb.Insert (pos_idx, high);
333 foreach (MPlist plist in intervals)
334 ((MInterval) plist.Val).Insert (pos, null, 0, 1);
337 public int this[int i]
340 i = pos_to_idx (this, i);
343 if (surrogate_high_p (sb[i]))
345 sb[i] = (char) value;
349 char high = (char) (0xD800 + ((value - 0x10000) >> 10));
350 char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
352 if (! surrogate_high_p (sb[i]))
359 i = pos_to_idx (this, i);
360 return (surrogate_high_p (sb[i])
361 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
368 MText mt = new MText (sb.ToString ());
370 foreach (MPlist p in intervals)
371 mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, 0, Length));
375 public MText Dup (int from, int to)
377 if (check_range (from, to, true))
379 int from_idx = pos_to_idx (this, from);
380 int len = pos_to_idx (this, to) - from_idx;
381 MText mt = new MText (sb.ToString ().Substring (from_idx, len));
383 foreach (MPlist p in intervals)
384 mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, from, to));
388 public MText Ins (int pos, int c)
394 public MText Ins (int pos, MText mt)
396 insert (pos, mt, 0, mt.nchars);
400 public MText Ins (int pos, MText mt, int from, int to)
402 insert (pos, mt, from, to);
406 public MText Cat (int c)
412 public MText Del (int from, int to)
414 if (check_range (from, to, true))
417 sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
421 foreach (MPlist plist in intervals)
423 MInterval root = (MInterval) plist.Val;
424 root.Delete (from, to);
425 if (from > 0 && from < nchars)
426 ((MInterval) plist.Val).MergeAfterChange (from, from);
435 public object GetProp (int pos, MSymbol key)
437 check_pos (pos, false);
439 MInterval i = (MInterval) intervals.Get (key);
443 MProperty prop = i.Get (pos);
444 return (prop != null ? prop.Val : null);
447 public object GetProp (int pos, MSymbol key, out MProperty prop)
449 check_pos (pos, false);
451 MInterval i = (MInterval) intervals.Get (key);
453 return (prop = null);
455 return (prop != null ? prop.Val : null);
458 public object GetProp (int pos, MSymbol key, out MProperty[] array)
460 check_pos (pos, false);
462 MInterval i = (MInterval) intervals.Get (key);
464 return (array = null);
465 MProperty prop = i.Get (pos, out array);
466 return (prop != null ? prop.Val : null);
469 public void PushProp (int from, int to, MSymbol key, object val)
471 if (! check_range (from, to, true))
472 PushProp (from, to, new MProperty (key, val));
475 public void PushProp (int from, int to, MProperty prop)
479 if (default_property == null)
480 default_property = new MPlist ();
481 default_property.Push (prop.key, prop.val);
485 if (check_range (from, to, true))
488 MPlist p = intervals.Find (prop.key);
493 root = new MInterval (prop.key, this);
494 intervals.Push (prop.key, root);
497 root = (MInterval) p.Val;
499 if (root.isSensitive)
500 root.PopSensitive (from, to);
501 root.Push (from, to, prop);
502 root.MergeAfterChange (from, to);
507 public void PopProp (int from, int to, MSymbol key)
511 if (default_property == null)
513 MPlist p = default_property.Find (key);
520 if (check_range (from, to, true))
523 MPlist p = intervals.Find (key);
527 MInterval root = (MInterval) p.Val;
528 if (root.isSensitive)
529 root.PopSensitive (from, to);
532 root = (MInterval) p.Val;
535 root.MergeAfterChange (from, to);
541 public void DumpProp ()
544 foreach (MPlist p in intervals)
545 ((MInterval) p.Val).Dump (true);
546 Console.WriteLine (")");
549 public void DumpPropNested ()
551 Console.WriteLine ("total length = {0}", Length);
552 foreach (MPlist p in intervals)
553 ((MInterval) p.Val).DumpNested (true);
556 private class MInterval
558 // position: 0 1 2 3 4 5 6 7
559 // | A | B | C | D | E F | G |
560 // interval |---|---|---|<->|-------|---|
561 // |---|<->|---| |<----->|---|
565 // [3 (1 2)] [3 (4 6)]
566 // [1 (0 1)] [2 (2 3)] [1 (6 7)]
568 private static int count = 0;
571 private int From, To;
573 private MPlist Stack;
574 private MInterval Left, Right, Parent;
577 public MInterval (MSymbol key, MText mt, int length)
580 throw new Exception ("Invalid interval length");
584 Stack = new MPlist ();
588 public MInterval (MSymbol key, MText mt)
592 Length = mt.sb.Length;
595 Stack = new MPlist ();
599 /// POS must be smaller than Length;
600 public MProperty Get (int pos)
602 MInterval i = find_head (pos);
604 return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val);
607 /// POS must be smaller than Length;
608 public MProperty Get (int pos, out MProperty[] array)
610 MInterval i = find_head (pos);
619 array = new MProperty[i.Stack.Count];
623 for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
624 array[idx] = (MProperty) p.Val;
628 private MInterval (MSymbol key, MText mt, int length, MPlist stack)
635 Stack = stack == null ? new MPlist () : stack.Clone ();
639 private bool isRearSticky
641 get { return MProperty.HasFlags (Key, MProperty.Flags.RearSticky) ; }
644 private bool isFrontSticky
646 get { return MProperty.HasFlags (Key, MProperty.Flags.FrontSticky) ; }
649 public bool isSensitive
651 get { return MProperty.HasFlags (Key, MProperty.Flags.Sensitive) ; }
654 public bool isFrontSensitive
656 get { return MProperty.HasFlags (Key,
657 MProperty.Flags.FrontSensitive) ; }
660 public bool isRearSensitive
662 get { return MProperty.HasFlags (Key,
663 MProperty.Flags.RearSensitive) ; }
666 public bool isAnySensitive
668 get { return MProperty.HasFlags (Key,
669 (MProperty.Flags.Sensitive
670 | MProperty.Flags.RearSensitive
671 | MProperty.Flags.FrontSensitive)) ; }
674 private void update_from_to ()
679 To = Length - RightLength;
681 else if (Parent.Left == this)
683 From = Parent.From - Length + LeftLength;
684 To = Parent.From - RightLength;
688 From = Parent.To + LeftLength;
689 To = Parent.To + Length - RightLength;
693 private int LeftLength
695 get { return (Left == null ? 0 : Left.Length); }
698 private int RightLength
700 get { return (Right == null ? 0 : Right.Length); }
703 private MInterval LeftMost
709 return Left.LeftMost;
713 private MInterval RightMost
719 return Right.RightMost;
723 private MInterval Prev {
729 for (i = Left; i.Right != null; i = i.Right)
735 MInterval child = this;
736 for (i = Parent; i != null && i.Left == child;
737 child = i, i = i.Parent);
743 private MInterval Next {
749 for (i = Right; i.Left != null; i = i.Left)
755 MInterval child = this;
756 for (i = Parent; i != null && i.Right == child;
757 child = i, i = i.Parent);
763 private MInterval find_head (int pos)
767 return Left.find_head (pos);
769 return Right.find_head (pos);
773 private MInterval find_tail (int pos)
777 return Left.find_tail (pos);
779 return Right.find_tail (pos);
783 private bool mergeable (MInterval i)
787 for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
788 p1 = p1.Next, p2 = p2.Next)
789 if (p1.Val != p2.Val)
791 return (p1.IsEmpty && p2.IsEmpty);
794 // p-. or .-p p-. or .-p
795 // .-this-. .-right-.
796 // left .-right-. -> .-this-. c2
798 private MInterval promote_right ()
800 MInterval c1 = Right.Left;
804 mtext.intervals.Put (Key, Right);
805 else if (Parent.Left == this)
808 Parent.Right = Right;
811 Right.Parent = Parent;
813 Right.Length += LeftLength + (To - From);
818 Length = LeftLength + (To - From) + RightLength;
820 // Update C1 if necessary.
824 Parent.update_from_to ();
828 // p-. or .-p p-. or .-p
830 // .-left-. .-right-. -> c1 .-this-.
832 private MInterval promote_left ()
834 MInterval c2 = Left.Right;
838 mtext.intervals.Put (Key, Left);
839 else if (Parent.Left == this)
845 Left.Parent = Parent;
847 Left.Length += (To - From) + RightLength;
852 Length = LeftLength + (To - From) + RightLength;
854 // Update C2 if necessary.
858 Parent.update_from_to ();
862 public MInterval Balance ()
870 // .-left-. .-right-.
872 int diff = i.LeftLength - i.RightLength;
877 new_diff = (i.Length - i.LeftLength
878 + i.Left.RightLength - i.Left.LeftLength);
879 if (Math.Abs (new_diff) >= diff)
881 M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
882 i = i.promote_left ();
883 M17n.DebugPrint ("done\n");
888 new_diff = (i.Length - i.RightLength
889 + i.Right.LeftLength - i.Right.RightLength);
890 if (Math.Abs (new_diff) >= diff)
892 M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
893 i = i.promote_right ();
902 public MInterval Copy (MText mt, int start, int end)
904 MInterval copy, left_copy = null, right_copy = null;
911 return Left.Copy (mt, start, end);
912 left_copy = Left.Copy (mt, start, From);
917 return Right.Copy (mt, start, end);
918 right_copy = Right.Copy (mt, To, end);
921 copy = new MInterval (Key, null, end - start, Stack);
923 if (isSensitive && (From < start || end < To))
925 if (left_copy != null)
927 copy.Left = left_copy;
928 left_copy.Parent = copy;
930 if (right_copy != null)
932 copy.Right = right_copy;
933 right_copy.Parent = copy;
938 public MInterval Copy (MText mt, int start, int end,
939 bool first, bool last)
941 MInterval copy = Copy (mt, start, end);
942 MInterval head = find_head (start);
943 MInterval tail = find_tail (end);
945 if (! head.Stack.IsEmpty
946 && (isAnySensitive && head.From < start
947 || isFrontSensitive && ! first))
949 head = copy.find_head (0);
952 if (! tail.Stack.IsEmpty
953 && (isAnySensitive && end < head.To
954 || isRearSensitive && ! last))
956 tail = copy.find_tail (copy.Length);
965 private MInterval divide_right (int pos)
967 MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
969 M17n.DebugPrint ("divide-right({0}) at {1}\n", pos, this);
973 interval.Right = Right;
974 Right.Parent = interval;
975 interval.Length += Right.Length;
977 interval.Parent = this;
985 private MInterval divide_left (int pos)
987 MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
989 M17n.DebugPrint ("divide-left({0}) at {1}\n", pos, this);
993 interval.Left = Left;
994 Left.Parent = interval;
995 interval.Length += Left.Length;
997 interval.Parent = this;
1002 private void set_mtext (MText mt)
1006 Left.set_mtext (mt);
1008 Right.set_mtext (mt);
1011 private void enlarge (int len)
1015 for (MInterval prev = this, i = this.Parent; i != null;
1016 prev = i, i = i.Parent)
1027 private int graft_forward (MInterval interval, int start, int end)
1031 if (! Stack.IsEmpty && isRearSticky)
1033 else if (interval == null)
1034 len = Stack.IsEmpty ? end - start : 0;
1037 MInterval i = interval.find_head (start);
1041 && (isFrontSensitive
1042 || ((isSensitive || isRearSensitive) && i.From < start)))
1044 M17n.DebugPrint (" grafting {0}", i);
1051 while (i != null && i.From < end && mergeable (i))
1053 M17n.DebugPrint (" grafting {0}", i);
1054 len += i.To - i.From;
1056 len -= start - i.From;
1066 M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1072 private int graft_backward (MInterval interval, int start, int end)
1076 if (! Stack.IsEmpty && isFrontSticky)
1078 else if (interval == null)
1079 len = Stack.IsEmpty ? end - start : 0;
1082 MInterval i = interval.find_tail (end);
1087 || ((isSensitive || isFrontSensitive) && end < i.To)))
1089 M17n.DebugPrint (" grafting {0}", i);
1090 if (i.From <= start)
1096 while (i != null && i.To <= start && mergeable (i))
1098 M17n.DebugPrint (" grafting {0}", i);
1099 len += i.To - i.From;
1102 if (i.From <= start)
1104 len -= start - i.From;
1111 M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1117 public void Insert (int pos, MInterval interval, int start, int end)
1121 M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}",
1122 start, end, pos, this);
1125 Left.Insert (pos, interval, start, end);
1126 else if (pos == From)
1128 MInterval prev = Left != null ? Prev : null;
1130 if (isFrontSensitive)
1132 if (prev != null && isRearSensitive)
1133 prev.Stack.Clear ();
1134 if (prev != null && isRearSticky && ! prev.Stack.IsEmpty)
1136 prev.enlarge (end - start);
1139 if (isFrontSticky && ! Stack.IsEmpty)
1141 enlarge (end - start);
1144 bool front_grafted = false, rear_grafted = false;
1147 && (grafted = prev.graft_forward (interval, start, end)) > 0)
1152 front_grafted = true;
1154 if ((grafted = graft_backward (interval, start, end)) > 0)
1159 rear_grafted = true;
1162 if (interval != null)
1163 interval = interval.Copy (mtext, start, end,
1164 front_grafted || prev == null,
1167 interval = new MInterval (Key, mtext, end - start, null);
1172 // .-this-. ==> .-this-.
1184 interval.Parent = i;
1185 for (; i != null; i = i.Parent)
1186 i.Length += interval.Length;
1190 if (! Stack.IsEmpty)
1192 if (isSensitive || isFrontSensitive || isRearSensitive)
1194 else if (isFrontSticky || isRearSticky)
1196 enlarge (end - start);
1200 bool front_grafted = false, rear_grafted = false;
1202 if ((grafted = graft_forward (interval, start, end)) > 0)
1207 front_grafted = true;
1210 if ((grafted = graft_backward (interval, start, end)) > 0)
1215 rear_grafted = true;
1217 if (interval != null)
1218 interval = interval.Copy (mtext, start, end,
1219 front_grafted, rear_grafted);
1221 interval = new MInterval (Key, mtext, end - start, null);
1224 Right.Left = interval;
1225 interval.Parent = Right;
1226 for (MInterval i = Right; i != null; i = i.Parent)
1227 i.Length += interval.Length;
1231 MInterval next = Right != null ? Next : null;
1233 if (isRearSensitive)
1235 if (next != null && isFrontSensitive)
1236 next.Stack.Clear ();
1237 if (isRearSticky && ! Stack.IsEmpty)
1239 enlarge (end - start);
1242 if (next != null && isFrontSticky && ! next.Stack.IsEmpty)
1244 next.enlarge (end - start);
1247 bool front_grafted = false, rear_grafted = false;
1250 && (grafted = next.graft_backward (interval, start, end)) > 0)
1255 rear_grafted = true;
1257 if ((grafted = graft_forward (interval, start, end)) > 0)
1262 front_grafted = true;
1264 if (interval != null)
1265 interval = interval.Copy (mtext, start, end,
1267 rear_grafted || next == null);
1269 interval = new MInterval (Key, mtext, end - start, null);
1274 // .-this-. ==> .-this-.
1287 interval.Parent = i;
1288 for (; i != null; i = i.Parent)
1289 i.Length += interval.Length;
1292 Right.Insert (pos, interval, start, end);
1293 M17n.DebugPrint (" done\n");
1296 private void vacate_node (MInterval interval)
1298 vacate_node (interval, null);
1301 private void vacate_node (MInterval interval, MInterval stop)
1303 if (interval != null)
1304 M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
1306 M17n.DebugPrint ("vacate #{0} to null\n", ID);
1307 if (interval != null)
1308 interval.Parent = Parent;
1312 mtext.intervals.Put (Key, interval);
1316 if (this == Parent.Right)
1317 Parent.Right = interval;
1319 Parent.Left = interval;
1322 if (interval != null)
1323 diff -= interval.Length;
1324 for (MInterval i = Parent; i != stop; i = i.Parent)
1329 public void Delete (int start, int end)
1332 M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this);
1334 bool front_checked = false;
1335 bool rear_checked = false;
1341 if (end == From && isFrontSensitive)
1343 Left.Delete (start, end);
1346 if (isSensitive || isFrontSensitive)
1348 Left.Delete (start, From);
1350 end -= From - start;
1352 front_checked = true;
1358 if (start == To && isRearSensitive)
1360 Right.Delete (start, end);
1363 if (isSensitive || isRearSensitive)
1365 Right.Delete (To, end);
1367 rear_checked = true;
1369 if (start == From && end == To)
1374 Prev.Stack.Clear ();
1376 && end < mtext.Length
1377 && isFrontSensitive)
1378 Next.Stack.Clear ();
1389 for (i = Right; i.Left != null; i = i.Left)
1390 i.Length += Left.Length;
1391 i.Length += Left.Length;
1395 vacate_node (Right);
1400 int len = end - start;
1404 for (MInterval i = this; i != null; i = i.Parent)
1409 public void Push (int start, int end, MProperty prop)
1412 M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this);
1417 Left.Push (start, end, prop);
1420 Left.Push (start, From, prop);
1427 Right.Push (start, end, prop);
1430 Right.Push (To, end, prop);
1434 if (! Stack.IsEmpty && isAnySensitive)
1437 divide_left (start);
1440 Stack.Push (prop.key, prop);
1443 /// Combine intervals between HEAD and TAIL (both inclusive) to
1444 /// the common parent of HEAD and TAIL. Callers should assure
1445 /// that the intervals are mergeable in advance.
1446 private static void combine (MInterval head, MInterval tail)
1448 M17n.DebugPrint ("combining {0} through {1}", head, tail);
1450 head.update_from_to ();
1451 tail.update_from_to ();
1452 int from = head.From;
1455 // The nearest common parent of HEAD and TAIL.
1457 for (root = head; root.To + root.RightLength < to;
1458 root = root.Parent);
1460 M17n.DebugPrint (" with common root {0}\n", root);
1462 if (from < root.From)
1464 MInterval prev = root.Prev;
1468 M17n.DebugPrint ("merging {0}\n", prev);
1469 prev.vacate_node (prev.Left, root);
1472 if (prev.Left != null)
1473 prev = prev.Left.RightMost;
1477 root.update_from_to ();
1481 MInterval next = root.Next;
1485 M17n.DebugPrint ("merging {0}\n", next);
1486 next.vacate_node (next.Right, root);
1489 if (next.Right != null)
1490 next = next.Right.LeftMost;
1494 root.update_from_to ();
1498 public void MergeAfterChange (int start, int end)
1502 MInterval head = find_head (start), i = head;
1503 MInterval tail = start < end ? find_tail (end) : head;
1505 if (tail.To < Length)
1508 if (start == head.From && start > 0)
1510 MInterval prev = head.Prev;
1511 if (head.mergeable (prev))
1514 M17n.DebugPrint ("merge between {0} and {1}\n", head, tail);
1517 MInterval next = i.Next;
1519 if (! i.mergeable (next))
1531 public void Pop (int start, int end)
1534 M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this);
1539 Left.Pop (start, end);
1542 Left.Pop (start, From);
1549 Right.Pop (start, end);
1552 Right.Pop (To, end);
1556 if (! Stack.IsEmpty)
1563 divide_left (start);
1571 public void PopSensitive (int start, int end)
1574 MInterval head = find_head (start);
1575 MInterval tail = find_tail (end);
1576 while (! head.Stack.IsEmpty && head.From > 0)
1578 MInterval prev = head.Prev;
1580 if (prev.Stack.IsEmpty || head.Stack.Val != prev.Stack.Val)
1584 while (! tail.Stack.IsEmpty && tail.To < mtext.Length)
1586 MInterval next = tail.Next;
1588 if (next.Stack.IsEmpty || tail.Stack.Val != next.Stack.Val)
1592 Pop (head.From, tail.To);
1595 public override string ToString ()
1597 string str = String.Format ("#{0}({1} {2} {3} [", ID, Length, From, To);
1599 foreach (MPlist p in Stack)
1603 str += ((MProperty) p.Val).Val;
1607 str += " " + ((MProperty) p.Val).Val;
1609 return (str + "])");
1612 private void DumpOne (bool with_prop, bool newline, bool force)
1614 if (force || M17n.debug)
1616 Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1617 if (with_prop && ! Stack.IsEmpty)
1619 string prepend = " [";
1620 foreach (MPlist p in Stack)
1622 Console.Write (prepend + ((MProperty) p.Val).Val);
1625 Console.Write ("]");
1627 Console.Write (")");
1629 Console.WriteLine ();
1631 throw new Exception ("Invalid interval length");
1635 public void Dump () { Dump (false); }
1637 public void Dump (bool force)
1639 if (force || M17n.debug)
1646 Console.Write (" ");
1647 DumpOne (true, false, force);
1654 get { return (Parent == null ? 0 : Parent.Depth + 1); }
1657 public void DumpNested (bool force)
1659 DumpNested (Key.ToString () + ":", force);
1662 public void DumpNested (string indent, bool force)
1664 if (force || M17n.debug)
1666 int indent_type = (Parent == null ? 1
1667 : Parent.Left == this ? 0 : 2);
1672 if (indent_type <= 1)
1673 Left.DumpNested (indent + " ", force);
1675 Left.DumpNested (indent + "| ", force);
1677 Console.Write (indent);
1678 if (indent_type == 0)
1679 Console.Write (".-");
1680 else if (indent_type == 2)
1681 Console.Write ("`-");
1682 DumpOne (true, true, true);
1685 if (indent_type >= 1)
1686 Right.DumpNested (indent + " ", force);
1688 Right.DumpNested (indent + "| ", force);
1694 private class MTextEnum : IEnumerator
1697 private int pos = -1;
1699 public MTextEnum (MText mt)
1704 public bool MoveNext ()
1707 return (pos < mt.nchars);
1710 public void Reset ()
1715 public object Current
1718 //if (pos < 0 || pos >= mt.nchars)
1719 //throw new InvalidOperationException ();