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 MTextProperty
28 internal enum Flag : byte
37 public MSymbol Key { get { return key; } }
38 public object Val { get { return val; } }
39 public bool FrontSticky
41 get { return (flags & Flag.FrontSticky) != Flag.None; }
43 public bool RearSticky
45 get { return (flags & Flag.RearSticky) != Flag.None; }
49 get { return (flags & Flag.Sensitive) != Flag.None; }
52 public MTextProperty (MSymbol key, object val)
56 flags |= Flag.RearSticky;
59 public MTextProperty (MSymbol key, object val,
60 bool front_sticky, bool rear_sticky, bool sensitive)
65 flags |= Flag.FrontSticky;
67 flags |= Flag.RearSticky;
69 flags |= Flag.Sensitive;
72 public override string ToString ()
74 return key.ToString () + ":" + val;
78 public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
81 public enum MTextFormat format;
83 private StringBuilder sb;
85 private int cache_pos;
86 private int cache_idx;
87 private MPlist intervals;
88 private MPlist default_property;
89 private bool read_only;
91 private static UTF8Encoding utf8 = new UTF8Encoding ();
93 private static int count_chars (String str)
95 int len = str.Length, n = 0;
97 for (int i = 0; i < len; i++, n++)
98 if (surrogate_high_p (str[i]))
103 private static int count_chars (StringBuilder str)
105 int len = str.Length, n = 0;
107 for (int i = 0; i < len; i++, n++)
108 if (surrogate_high_p (str[i]))
115 sb = new StringBuilder ();
116 intervals = new MPlist ();
119 public MText (byte[] str)
121 sb = new StringBuilder (utf8.GetString (str));
122 nchars = count_chars (sb);
123 intervals = new MPlist ();
126 public MText (String str)
128 sb = new StringBuilder (str);
129 nchars = count_chars (str);
130 intervals = new MPlist ();
133 public MText (StringBuilder str)
136 nchars = count_chars (str);
137 intervals = new MPlist ();
140 public static MText operator+ (MText mt1, MText mt2)
142 MText mt = new MText ();
144 mt.sb.Append (mt1.sb);
145 mt.sb.Append (mt2.sb);
146 mt.nchars = mt1.nchars + mt2.nchars;
151 public bool ReadOnly { get { return read_only; } }
152 public int Length { get { return nchars; } }
156 // for IEnumerable interface
157 public IEnumerator GetEnumerator() { return new MTextEnum (this); }
159 // for IEquatable interface
160 public bool Equals (MText other) { return this.sb.Equals (other.sb); }
162 // for IComparable interface
163 public int CompareTo (MText other)
165 return this.sb.ToString ().CompareTo (other.sb.ToString ());
168 public override String ToString () { return "\"" + sb.ToString () + "\""; }
170 private static bool surrogate_high_p (char c)
172 return (c >= 0xD800 && c < 0xDC00);
175 private static bool surrogate_low_p (char c)
177 return (c >= 0xDC00 && c < 0xE000);
180 private static int inc_idx (StringBuilder sb, int i)
182 return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
185 private static int dec_idx (StringBuilder sb, int i)
187 return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
190 private static int pos_to_idx (MText mt, int pos)
192 if (pos == mt.cache_pos)
198 if (pos < mt.cache_pos)
200 if (mt.cache_pos == mt.cache_idx)
202 if (pos < mt.cache_pos - pos)
209 p = mt.cache_pos; i = mt.cache_idx;
215 if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
216 return (mt.cache_idx + pos - mt.cache_pos);
217 if (pos - mt.cache_pos < mt.nchars - pos)
219 p = mt.cache_pos; i = mt.cache_idx;
224 p = mt.nchars; i = mt.sb.Length;
229 for (; p < pos; i = inc_idx (mt.sb, i), p++);
231 for (; p > pos; i = dec_idx (mt.sb, i), p--);
237 private void check_pos (int pos, bool tail_ok)
239 if (pos < 0 || (tail_ok ? pos > nchars : pos >= nchars))
240 throw new Exception ("Invalid MText position:" + pos);
243 private bool check_range (int from, int to, bool zero_ok)
245 if (from < 0 || (zero_ok ? from > to : from >= to)
247 throw new Exception ("Invalid MText range");
251 private void insert (int pos, MText mt2, int from, int to)
253 check_pos (pos, true);
255 int pos_idx = pos_to_idx (this, pos);
256 int from_idx = pos_to_idx (mt2, from);
257 int to_idx = pos_to_idx (mt2, to);
259 sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
262 foreach (MPlist plist in mt2.intervals)
263 if (intervals.Find (plist.Key) == null)
264 intervals.Push (plist.Key, new MInterval (plist.Key, this));
265 foreach (MPlist plist in intervals)
267 MPlist p = mt2.intervals.Find (plist.Key);
271 interval = new MInterval (plist.Key, this, to - from);
273 interval = ((MInterval) p.Val).Copy (from, to);
274 ((MInterval) plist.Val).Insert (pos, interval);
278 private void insert (int pos, int c)
280 check_pos (pos, true);
282 int pos_idx = pos_to_idx (this, pos);
287 sb.Insert (pos_idx, ch);
291 char high = (char) (0xD800 + ((c - 0x10000) >> 10));
292 char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF));
293 sb.Insert (pos_idx, low);
294 sb.Insert (pos_idx, high);
297 foreach (MPlist plist in intervals)
298 ((MInterval) plist.Val).Insert (pos,
299 new MInterval (plist.Key, this, 1));
302 public int this[int i]
305 i = pos_to_idx (this, i);
308 if (surrogate_high_p (sb[i]))
310 sb[i] = (char) value;
314 char high = (char) (0xD800 + ((value - 0x10000) >> 10));
315 char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
317 if (! surrogate_high_p (sb[i]))
324 i = pos_to_idx (this, i);
325 return (surrogate_high_p (sb[i])
326 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
333 MText mt = new MText (sb.ToString ());
335 foreach (MPlist p in intervals)
336 mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (0, Length));
340 public MText Ins (int pos, int c)
346 public MText Ins (int pos, MText mt)
348 insert (pos, mt, 0, mt.nchars);
352 public MText Ins (int pos, MText mt, int from, int to)
354 insert (pos, mt, from, to);
358 public MText Cat (int c)
364 public MText Del (int from, int to)
366 if (check_range (from, to, true))
369 sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
373 foreach (MPlist plist in intervals)
374 ((MInterval) plist.Val).Delete (from, to);
376 intervals = new MPlist ();
380 public object GetProp (int pos, MSymbol key)
382 check_pos (pos, false);
384 MInterval i = (MInterval) intervals.Get (key);
388 MTextProperty prop = i.Get (pos);
389 return (prop != null ? prop.Val : null);
392 public object GetProp (int pos, MSymbol key, out MTextProperty prop)
394 check_pos (pos, false);
396 MInterval i = (MInterval) intervals.Get (key);
398 return (prop = null);
400 return (prop != null ? prop.Val : null);
403 public object GetProp (int pos, MSymbol key, out MTextProperty[] array)
405 check_pos (pos, false);
407 MInterval i = (MInterval) intervals.Get (key);
409 return (array = null);
410 MTextProperty prop = i.Get (pos, out array);
411 return (prop != null ? prop.Val : null);
414 public void PushProp (int from, int to, MSymbol key, object val)
416 if (! check_range (from, to, true))
417 PushProp (from, to, new MTextProperty (key, val));
420 public void PushProp (int from, int to, MTextProperty prop)
424 if (default_property == null)
425 default_property = new MPlist ();
426 default_property.Push (prop.key, prop.val);
430 if (check_range (from, to, true))
433 MPlist p = intervals.Find (prop.key);
438 root = new MInterval (prop.key, this);
439 intervals.Push (prop.key, root);
442 root = (MInterval) p.Val;
444 root.Push (from, to, prop);
448 public void PopProp (int from, int to, MSymbol key)
452 if (default_property == null)
454 MPlist p = default_property.Find (key);
461 if (check_range (from, to, true))
464 MPlist p = intervals.Find (key);
467 ((MInterval) p.Val).Pop (from, to);
471 public void DumpProp ()
474 foreach (MPlist p in intervals)
475 ((MInterval) p.Val).Dump (true);
476 Console.WriteLine (")");
479 public void DumpPropNested ()
481 foreach (MPlist p in intervals)
482 ((MInterval) p.Val).DumpNested (true);
485 private class MInterval
487 // position: 0 1 2 3 4 5 6 7
488 // | A | B | C | D | E F | G |
489 // interval |---|---|---|<->|-------|---|
490 // |---|<->|---| |<----->|---|
494 // [3 (1 2)] [3 (4 6)]
495 // [1 (0 1)] [2 (2 3)] [1 (6 7)]
497 private static int count = 0;
500 private int From, To;
502 private MPlist Stack;
503 private MInterval Left, Right, Parent;
506 public MInterval (MSymbol key, MText mt, int length)
509 throw new Exception ("Invalid interval length");
513 Stack = new MPlist ();
517 public MInterval (MSymbol key, MText mt)
521 Length = mt.sb.Length;
524 Stack = new MPlist ();
528 public MTextProperty Get (int pos)
530 MInterval i = find (pos);
532 return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val);
535 public MTextProperty Get (int pos, out MTextProperty[] array)
537 MInterval i = find (pos);
544 array = new MTextProperty[i.Stack.Count];
548 for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
549 array[idx] = (MTextProperty) p.Val;
553 private MInterval (MSymbol key, MText mt, int length, MPlist stack)
560 Stack = stack.Clone ();
564 private void update_from_to ()
569 To = Length - RightLength;
571 else if (Parent.Left == this)
573 From = Parent.From - Length + LeftLength;
574 To = Parent.From - RightLength;
578 From = Parent.To + LeftLength;
579 To = Parent.To + Length - RightLength;
583 private int LeftLength
585 get { return (Left == null ? 0 : Left.Length); }
588 private int RightLength
590 get { return (Right == null ? 0 : Right.Length); }
593 private MInterval LeftMost
595 get { return (Left == null ? this : Left.LeftMost); }
598 private MInterval RightMost
600 get { return (Right == null ? this : Right.RightMost); }
603 private MInterval Prev {
608 for (i = Left; i.Right != null; i = i.Right);
611 MInterval child = this;
612 for (i = Parent; i != null && i.Left == child;
613 child = i, i = i.Parent);
619 private MInterval Next {
624 for (i = Right; i.Left != null; i = i.Left);
627 MInterval child = this;
628 for (i = Parent; i != null && i.Right == child;
629 child = i, i = i.Parent);
635 private MInterval find (int pos)
639 return Left.find (pos);
641 return Right.find (pos);
645 private bool mergeable (MInterval i)
649 for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
650 p1 = p1.Next, p2 = p2.Next)
651 if (p1.Val != p2.Val)
653 return (p1.IsEmpty && p2.IsEmpty);
656 // p-. or .-p p-. or .-p
657 // .-this-. .-right-.
658 // left .-right-. -> .-this-. c2
660 private MInterval promote_right ()
662 int right_length = Right.Length;
666 mtext.intervals.Put (Key, Right);
667 else if (Parent.Left == this)
670 Parent.Right = Right;
671 Right.Parent = Parent;
677 Parent.Length += Length;
678 Length -= right_length;
682 Parent.Length -= c1.Length;
688 // p-. or .-p p-. or .-p
690 // .-left-. .-right-. -> c1 .-this-.
692 private MInterval promote_left ()
694 int left_length = Left.Length;
698 mtext.intervals.Put (Key, Left);
699 else if (Parent.Left == this)
703 Left.Parent = Parent;
709 Parent.Length += Length;
710 Length -= left_length;
714 Parent.Length -= c1.Length;
720 private MInterval balance ()
727 // .-left-. .-right-.
729 int diff = i.LeftLength - i.RightLength;
734 new_diff = (i.Length - i.LeftLength
735 + i.Left.RightLength - i.Left.LeftLength);
736 if (Math.Abs (new_diff) >= diff)
738 i = i.promote_left ();
743 new_diff = (i.Length - i.RightLength
744 + i.Right.LeftLength - i.Right.RightLength);
745 if (Math.Abs (new_diff) >= diff)
747 i = i.promote_right ();
754 public MInterval Copy (int start, int end)
756 MInterval copy, left_copy = null, right_copy = null;
763 return Left.Copy (start, end);
764 left_copy = Left.Copy (start, From);
769 return Right.Copy (start, end);
770 right_copy = Right.Copy (To, end);
773 copy = new MInterval (Key, null, end - start, Stack);
774 remove_properties (MTextProperty.Flag.Sensitive);
775 if (left_copy != null)
777 copy.Left = left_copy;
778 left_copy.Parent = copy;
780 if (right_copy != null)
782 copy.Right = right_copy;
783 right_copy.Parent = copy;
791 private MInterval divide_right (int pos)
793 MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
795 M17N.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
799 interval.Right = Right;
800 Right.Parent = interval;
801 interval.Length += Right.Length;
803 interval.Parent = this;
811 private MInterval divide_left (int pos)
813 MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
815 M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
819 interval.Left = Left;
820 Left.Parent = interval;
821 interval.Length += Left.Length;
823 interval.Parent = this;
828 private void remove_properties (MTextProperty.Flag flags)
830 for (MPlist p = Stack; ! p.IsEmpty;)
832 MTextProperty prop = (MTextProperty) p.Val;
834 if ((prop.flags & flags) == flags)
841 private void inherit_front_properties (MPlist plist)
843 for (MInterval i = LeftMost; i != null; i = i.Next)
847 for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
849 MTextProperty prop = (MTextProperty) p.Val;
851 if ((prop.flags & MTextProperty.Flag.RearSticky)
852 == MTextProperty.Flag.RearSticky)
853 i.Stack.Add (prop.key, prop);
858 private void inherit_rear_properties (MPlist plist)
860 for (MInterval i = RightMost; i != null; i = i.Prev)
864 for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
866 MTextProperty prop = (MTextProperty) p.Val;
868 if ((prop.flags & MTextProperty.Flag.FrontSticky)
869 == MTextProperty.Flag.FrontSticky)
870 i.Stack.Add (prop.key, prop);
875 private MInterval delete_node_forward ()
879 int len = Length - RightLength;
881 for (MInterval i = Parent; i != null; i = i.Parent)
883 if (Parent.Left == this)
886 Parent.Right = Right;
891 Right.Parent = Parent;
892 return Right.LeftMost;
897 private MInterval delete_node_backward ()
901 int len = Length - RightLength;
903 for (MInterval i = Parent; i != null; i = i.Parent)
905 if (Parent.Left == this)
913 Left.Parent = Parent;
914 return Left.RightMost;
919 private void set_mtext (MText mt)
925 Right.set_mtext (mt);
928 private MInterval graft (MInterval interval, bool forward, out int len)
935 i = interval.LeftMost;
940 len += i.Length - i.RightLength;
941 i = i.delete_node_forward ();
946 i = interval.RightMost;
951 len += i.Length - i.LeftLength;
952 i = i.delete_node_backward ();
958 for (MInterval prev = this, ii = this.Parent; ii != null;
959 prev = ii, ii = ii.Parent)
969 while (i.Parent != null) i = i.Parent;
973 public void Insert (int pos, MInterval interval)
976 M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos);
977 DumpOne (false, true);
979 interval.set_mtext (mtext);
982 Prev.Insert (pos, interval);
983 else if (pos == From)
985 MInterval prev = Prev;
991 prev.Insert (pos, interval);
994 prev.remove_properties
995 (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
996 interval.inherit_front_properties (prev.Stack);
999 (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1000 interval.inherit_rear_properties (Stack);
1003 interval = graft (interval, false, out len);
1004 if (interval != null && prev != null)
1005 interval = prev.graft (interval, true, out len);
1006 if (interval != null)
1012 // .-this-. ==> .-this-.
1024 interval.Parent = i;
1025 for (; i != null; i = i.Parent)
1026 i.Length += interval.Length;
1031 remove_properties (MTextProperty.Flag.Sensitive);
1034 interval = graft (interval, true, out len);
1036 if (interval != null)
1037 interval = graft (interval, false, out len);
1038 if (interval != null)
1041 Right.Left = interval;
1042 interval.Parent = Right;
1043 for (MInterval i = Right; i != null; i = i.Parent)
1044 i.Length += interval.Length;
1049 MInterval next = Next;
1055 next.Insert (pos, interval);
1058 next.remove_properties
1059 (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1060 interval.inherit_rear_properties (next.Stack);
1063 (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
1064 interval.inherit_front_properties (Stack);
1067 interval = graft (interval, true, out len);
1068 if (interval != null && next != null)
1069 interval = next.graft (interval, false, out len);
1070 if (interval != null)
1076 // .-this-. ==> .-this-.
1089 interval.Parent = i;
1090 for (; i != null; i = i.Parent)
1091 i.Length += interval.Length;
1095 Next.Insert (pos, interval);
1098 private void vacate_node (MInterval interval)
1100 M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID);
1101 if (interval != null)
1102 interval.Parent = Parent;
1106 mtext.intervals.Put (Key, interval);
1110 if (this == Parent.Right)
1111 Parent.Right = interval;
1113 Parent.Left = interval;
1116 if (interval != null)
1117 diff -= interval.Length;
1118 for (MInterval i = Parent; i != null; i = i.Parent)
1123 public void Delete (int start, int end)
1126 M17N.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
1131 Left.Delete (start, end);
1134 Left.Delete (start, From);
1136 end -= From - start;
1143 Right.Delete (start, end);
1146 Right.Delete (To, end);
1149 if (start == From && end == To)
1161 for (i = Right; i.Left != null; i = i.Left)
1162 i.Length += Left.Length;
1163 i.Length += Left.Length;
1167 vacate_node (Right);
1172 int len = end - start;
1174 for (MInterval i = this; i != null; i = i.Parent)
1179 public void Push (int start, int end, MTextProperty prop)
1182 M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
1187 Left.Push (start, end, prop);
1190 Left.Push (start, From, prop);
1197 Right.Push (start, end, prop);
1200 Right.Push (To, end, prop);
1205 divide_left (start);
1208 Stack.Push (prop.key, prop);
1211 private bool try_merge_prev ()
1213 MInterval prev = Prev;
1215 if (! mergeable (prev))
1218 M17N.DebugPrint ("merging "); DumpOne (false, false);
1219 M17N.DebugPrint (" with prev "); prev.DumpOne (false, true);
1220 int len = prev.Length - prev.LeftLength;
1222 // PREV is Left, Left.Right, ..., or Left....Right.
1225 if (prev.Left != null)
1226 prev.Left.Parent = prev.Parent;
1227 prev.Parent.Right = prev.Left;
1228 while (prev.Parent != Left)
1235 if (Left.Length == Left.LeftLength)
1237 if (Left.Left != null)
1238 Left.Left.Parent = this;
1244 private bool try_merge_next ()
1246 MInterval next = Next;
1248 if (! mergeable (next))
1251 M17N.DebugPrint ("merging "); DumpOne (false, false);
1252 M17N.DebugPrint (" with next "); next.DumpOne (false, true);
1254 int len = next.Length - next.RightLength;
1256 // NEXT is Right, Right.Left, ..., or Right....Left.
1259 if (next.Right != null)
1260 next.Right.Parent = next.Parent;
1261 next.Parent.Left = next.Right;
1262 while (next.Parent != Right)
1268 Right.Length -= len;
1269 if (Right.Length == Right.RightLength)
1271 if (Right.Right != null)
1272 Right.Right.Parent = this;
1273 Right = Right.Right;
1278 public void Pop (int start, int end)
1281 M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
1286 Left.Pop (start, end);
1289 Left.Pop (start, From);
1296 Right.Pop (start, end);
1299 Right.Pop (To, end);
1303 if (! Stack.IsEmpty)
1305 bool check_prev = start == From && start > 0;
1306 bool check_next = end == To && end < mtext.Length;
1308 if (! check_prev && start > From)
1309 divide_left (start);
1310 if (! check_next && end < To)
1313 if (check_prev && Left != null)
1314 check_prev = try_merge_prev () && (Left != null);
1315 if (check_next && Right != null)
1316 check_next = try_merge_next () && (Right != null);
1319 if (Prev.try_merge_next () && check_next)
1320 Prev.try_merge_next ();
1322 else if (check_next)
1324 Next.try_merge_prev ();
1329 private void DumpOne (bool with_prop, bool newline)
1331 DumpOne (with_prop, newline, false);
1334 private void DumpOne (bool with_prop, bool newline, bool force)
1336 if (force || M17N.debug)
1338 Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1340 foreach (MPlist p in Stack)
1341 Console.Write (" " + p.Val);
1342 Console.Write (")");
1344 Console.WriteLine ();
1346 throw new Exception ("Invalid interval length");
1350 public void Dump () { Dump (false); }
1352 public void Dump (bool force)
1354 if (force || M17N.debug)
1361 Console.Write (" ");
1362 DumpOne (true, false, force);
1369 get { return (Parent == null ? 0 : Parent.Depth + 1); }
1372 public void DumpNested (bool force)
1374 DumpNested ("", force);
1377 public void DumpNested (string indent, bool force)
1379 if (force || M17N.debug)
1381 int indent_type = (Parent == null ? 1
1382 : Parent.Left == this ? 0 : 2);
1387 if (indent_type <= 1)
1388 Left.DumpNested (indent + " ", force);
1390 Left.DumpNested (indent + "| ", force);
1392 if (indent_type == 0)
1393 Console.Write (indent + ".-");
1394 else if (indent_type == 2)
1395 Console.Write (indent + "`-");
1396 DumpOne (true, true);
1399 if (indent_type >= 1)
1400 Right.DumpNested (indent + " ", force);
1401 else if (indent_type == 2)
1402 Right.DumpNested (indent + "| ", force);
1408 private class MTextEnum : IEnumerator
1411 private int pos = -1;
1413 public MTextEnum (MText mt)
1418 public bool MoveNext ()
1421 return (pos < mt.nchars);
1424 public void Reset ()
1429 public object Current
1432 //if (pos < 0 || pos >= mt.nchars)
1433 //throw new InvalidOperationException ();