3 using System.Collections;
4 using System.Collections.Generic;
10 public enum MTextFormat
12 MTEXT_FORMAT_US_ASCII,
14 MTEXT_FORMAT_UTF_16BE,
15 MTEXT_FORMAT_UTF_16LE,
16 MTEXT_FORMAT_UTF_32BE,
17 MTEXT_FORMAT_UTF_32LE,
21 public class MTextProperty
23 private MProperty prop;
24 private bool front_sticky;
25 private bool rear_sticky;
28 public MProperty Prop { get { return prop; } }
29 public bool FrontSticky { get { return front_sticky; } }
30 public bool RearSticky { get { return rear_sticky; } }
31 public MText Mtext { get { return mtext; } }
33 public MTextProperty (MProperty prop, bool front_sticky, bool rear_sticky)
36 this.front_sticky = front_sticky;
37 this.rear_sticky = rear_sticky;
41 public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
44 public enum MTextFormat format;
46 private StringBuilder sb;
48 private int cache_pos;
49 private int cache_idx;
50 private MPlist intervals;
51 private MProperty default_property;
52 private bool read_only;
54 private static UTF8Encoding utf8 = new UTF8Encoding ();
56 private static int count_chars (String str)
58 int len = str.Length, n = 0;
60 for (int i = 0; i < len; i++, n++)
61 if (surrogate_high_p (str[i]))
66 private static int count_chars (StringBuilder str)
68 int len = str.Length, n = 0;
70 for (int i = 0; i < len; i++, n++)
71 if (surrogate_high_p (str[i]))
78 sb = new StringBuilder ();
81 public MText (byte[] str)
83 sb = new StringBuilder (utf8.GetString (str));
84 nchars = count_chars (sb);
87 public MText (String str)
89 sb = new StringBuilder (str);
90 nchars = count_chars (str);
93 public MText (StringBuilder str)
96 nchars = count_chars (str);
99 public static MText operator+ (MText mt1, MText mt2)
101 MText mt = new MText ();
103 mt.sb.Append (mt1.sb);
104 mt.sb.Append (mt2.sb);
105 mt.nchars = mt1.nchars + mt2.nchars;
110 public bool ReadOnly { get { return read_only; } }
111 public int Length { get { return nchars; } }
115 // for IEnumerable interface
116 public IEnumerator GetEnumerator() { return new MTextEnum (this); }
118 // for IEquatable interface
119 public bool Equals (MText other) { return this.sb.Equals (other.sb); }
121 // for IComparable interface
122 public int CompareTo (MText other)
124 return this.sb.ToString ().CompareTo (other.sb.ToString ());
127 public override String ToString () { return sb.ToString (); }
129 private static bool surrogate_high_p (char c)
131 return (c >= 0xD800 && c < 0xDC00);
134 private static bool surrogate_low_p (char c)
136 return (c >= 0xDC00 && c < 0xE000);
139 private static int inc_idx (StringBuilder sb, int i)
141 return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
144 private static int dec_idx (StringBuilder sb, int i)
146 return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
149 private static int pos_to_idx (MText mt, int pos)
151 if (pos == mt.cache_pos)
157 if (pos < mt.cache_pos)
159 if (mt.cache_pos == mt.cache_idx)
161 if (pos < mt.cache_pos - pos)
168 p = mt.cache_pos; i = mt.cache_idx;
174 if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
175 return (mt.cache_idx + pos - mt.cache_pos);
176 if (pos - mt.cache_pos < mt.nchars - pos)
178 p = mt.cache_pos; i = mt.cache_idx;
183 p = mt.nchars; i = mt.sb.Length;
188 for (; p < pos; i = inc_idx (mt.sb, i), p++);
190 for (; p > pos; i = dec_idx (mt.sb, i), p--);
196 private void insert (int pos, MText mt2, int from, int to)
198 int pos_idx = pos_to_idx (this, pos);
199 int from_idx = pos_to_idx (mt2, from);
200 int to_idx = pos_to_idx (mt2, to);
202 sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
205 if (mt2.intervals != null
206 && ! mt2.intervals.tailp)
208 if (intervals == null)
209 intervals = new MPlist ();
210 foreach (MInterval interval in mt2.intervals)
211 if (intervals.find (interval.key) == null)
212 intervals.push (interval.key, new MInterval (interval.key, mt));
215 if (intervals != null)
217 foreach (MInterval root in intervals)
221 if (mt2.intervals != null
222 && ! mt2.intervals.tailp)
224 interval = mt2.intervals.find (root.key);
225 if (interval != null)
226 interval = interval.CopyTree (from, to);
228 if (interval == null)
229 interval = new MInterval (root.key, to - from);
230 root.Insert (pos, interval);
234 public int this[int i]
237 i = pos_to_idx (this, i);
240 if (surrogate_high_p (sb[i]))
242 sb[i] = (char) value;
246 char high = (char) (0xD800 + ((value - 0x10000) >> 10));
247 char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
249 if (! surrogate_high_p (sb[i]))
256 i = pos_to_idx (this, i);
257 return (surrogate_high_p (sb[i])
258 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
265 return (new MText (sb.ToString ()));
268 public MText ins (int pos, MText mt)
270 insert (pos, mt, 0, mt.nchars);
274 public MText ins (int pos, MText mt, int from, int to)
276 insert (pos, mt, from, to);
280 public MText del (int from, int to)
282 sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
287 public void PushProp (int from, int to, MTextProperty prop)
291 if (intervals == null
292 || (root = intervals.find (prop.key)) )
293 intervals = new MPlist (prop.key, new MInterval (prop.key, this));
295 root_interval.Push (from, to, prop);
298 private class MInterval
302 // interval |<--------->|<--------->|<--------->|
305 // [1 (0 1)] [1 (2 3)]
306 private int total_length;
307 private int from, to;
309 private Stack<MTextProperty> stack;
310 private MInterval left, right, parent;
313 public MInterval (MSymbol key, int length)
316 throw new Exception ("Invalid interval length");
318 total_length = length;
319 stack = new Stack<MTextProperty> ();
322 private MInterval (MSymbol key, int length, Stack<MTextProperty> stack)
325 total_length = length;
328 stack = new Stack<MTextProperty> (stack);
331 public MInterval (MSymbol key, MText mt)
335 total_length = mt.sb.Length;
338 stack = new Stack<MTextProperty> ();
341 private void update_from_to ()
345 from = parent.from - total_length + LeftLength;
346 to = parent.from - RightLength;
350 private int LeftLength
352 get { return (left == null ? 0 : left.total_length); }
355 private int RightLength
357 get { return (right == null ? 0 : right.total_length); }
360 private MInterval LeftMostNode
362 get { return (left == null ? this : left.LeftMostNode); }
365 private MInterval RightMostNode
367 get { return (right == null ? this : right.RightMostNode); }
370 private MInterval LeftNode {
375 for (i = left; i.right != null; i = i.right);
377 for (i = parent; i != null && i.left == null; i = i.parent);
382 private MInterval RightNode {
387 for (i = right; i.left != null; i = i.left);
389 for (i = parent; i != null && i.right == null; i = i.parent);
394 private MInterval find (int pos)
398 return left.find (pos);
400 return right.find (pos);
404 // p-. or .-p p-. or .-p
405 // .-this-. .-right-.
406 // left .-right-. -> .-this-. c2
408 private MInterval promote_right ()
410 int right_length = right.total_length;
414 mtext.root_intervals.put (key, right);
415 else if (parent.left == this)
418 parent.right = right;
419 right.parent = parent;
425 parent.total_length += total_length;
426 total_length -= right_length;
430 parent.total_length -= c1.total_length;
431 total_length += c1.total_length;
436 // p-. or .-p p-. or .-p
438 // .-left-. .-right-. -> c1 .-this-.
440 private MInterval promote_left ()
442 int left_length = left.total_length;
446 mtext.update_root_interval (key, left);
447 else if (parent.left == this)
451 left.parent = parent;
457 parent.total_length += total_length;
458 total_length -= left_length;
462 parent.total_length -= c1.total_length;
463 total_length += c1.total_length;
468 private MInterval balance ()
475 // .-left-. .-right-.
477 int diff = i.LeftLength - i.RightLength;
482 new_diff = (i.total_length - i.LeftLength
483 + i.left.RightLength - i.left.LeftLength);
484 if (Math.Abs (new_diff) >= diff)
486 i = i.promote_left ();
491 new_diff = (i.total_length - i.RightLength
492 + i.right.LeftLength - i.right.RightLength);
493 if (Math.Abs (new_diff) >= diff)
495 i = i.promote_right ();
502 public MInterval CopyTree (int start, int end)
504 MInterval this_copy, left_copy, right_copy;
510 return left.CopyTree (start, end);
511 left_copy = left.CopyTree (start, from);
516 return right.CopyTree (start, end);
517 right_copy = right.CopyTree (to, end);
519 this_copy = MInteval (key, end - start, stack);
520 this_copy.left = left_copy;
521 this_copy.right = right_copy;
529 private MInterval divide_right (int pos)
534 interval = new MInterval (key, to - pos, stack);
536 total_length -= to - pos;
539 right->parent = interval;
540 interval.total_length += right->total_length;
542 interval->parent = this;
550 private MInterval divide_left (int pos)
552 MInterval interval = CopyNode ();
553 int this_start = Start;
557 || (right != null && left.total_end < - right.total_start))
559 interval.total_start = 0;
560 interval.total_end = pos - this_start;
562 left.parent = interval;
567 interval.right = this;
568 interval.left = left;
569 interval.parent = parent;
572 if (total_start == 0)
573 parent.left = interval;
575 parent.right = interval;
577 total_start = pos - this_end;
584 public void Insert (int pos, MInterval interval)
589 LeftNode.Insert (pos, interval);
594 RightNode.Insert (pos, interval);
599 divide_right (pos).Insert (pos, interval);
604 if (left != null && LeftNode.stack.Count > 0)
606 Stack<MTextProperty> s = new Stack<MTextProperty> ();
608 foreach (MTextProperty p in LeftNode.stack)
613 for (MInterval i = interval.LeftMost;
614 i != null && i.stack.Count == 0;
616 foreach (MTextProperty p in s)
622 Stack<MTextProperty> s = new Stack<MTextProperty> ();
624 foreach (MTextProperty p in stack)
629 for (MInterval i = interval.RightMostNode;
630 i != null && i.stack.Count == 0;
632 foreach (MTextProperty p in s)
637 // INTERVAL is ready to insert.
639 // .-this-. ==> .-this-.
646 MInterval i = left.RightMostNode;
649 interval->parent = i;
650 for (; i != null; i = i.parent)
651 i.total_length += interval.total_length;
657 for (MInterval i = this; i != null; i = i.parent)
658 i.total_length += interval.total_length;
662 public MTextProperty Push (int start, int end, MTextProperty prop)
667 left.Push (start, end, prop);
674 right.Push (start, end, prop);
689 private class MTextEnum : IEnumerator
692 private int pos = -1;
694 public MTextEnum (MText mt)
699 public bool MoveNext ()
702 return (pos < mt.nchars);
710 public object Current
713 //if (pos < 0 || pos >= mt.nchars)
714 //throw new InvalidOperationException ();