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 internal MProperty prop;
24 internal bool front_sticky;
25 internal bool rear_sticky;
26 internal bool merginable;
27 public MProperty Prop { get { return prop; } }
28 public bool FrontSticky { get { return front_sticky; } }
29 public bool RearSticky { get { return rear_sticky; } }
30 public bool Merginable { get { return merginable; } }
32 public MTextProperty (bool front_sticky, bool rear_sticky)
34 this.front_sticky = front_sticky;
35 this.rear_sticky = rear_sticky;
37 public MTextProperty (bool front_sticky, bool rear_sticky, bool merginable)
39 this.front_sticky = front_sticky;
40 this.rear_sticky = rear_sticky;
41 this.merginable = merginable;
45 public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
48 public enum MTextFormat format;
51 private StringBuilder sb;
53 private int cache_pos;
54 private int cache_idx;
55 private MInterval root_interval;
56 private bool read_only;
58 private static UTF8Encoding utf8 = new UTF8Encoding ();
60 private static int count_chars (String str)
62 int len = str.Length, n = 0;
64 for (int i = 0; i < len; i++, n++)
65 if (surrogate_high_p (str[i]))
70 private static int count_chars (StringBuilder str)
72 int len = str.Length, n = 0;
74 for (int i = 0; i < len; i++, n++)
75 if (surrogate_high_p (str[i]))
82 sb = new StringBuilder ();
85 public MText (byte[] str)
87 sb = new StringBuilder (utf8.GetString (str));
88 nchars = count_chars (sb);
91 public MText (String str)
93 sb = new StringBuilder (str);
94 nchars = count_chars (str);
97 public MText (StringBuilder str)
100 nchars = count_chars (str);
103 public static MText operator+ (MText mt1, MText mt2)
105 MText mt = new MText ();
107 mt.sb.Append (mt1.sb);
108 mt.sb.Append (mt2.sb);
109 mt.nchars = mt1.nchars + mt2.nchars;
114 public bool ReadOnly { get { return read_only; } }
115 public int Length { get { return nchars; } }
119 // for IEnumerable interface
120 public IEnumerator GetEnumerator() { return new MTextEnum (this); }
122 // for IEquatable interface
123 public bool Equals (MText other) { return this.sb.Equals (other.sb); }
125 // for IComparable interface
126 public int CompareTo (MText other)
128 return this.sb.ToString ().CompareTo (other.sb.ToString ());
131 public override String ToString () { return sb.ToString (); }
133 private static bool surrogate_high_p (char c)
135 return (c >= 0xD800 && c < 0xDC00);
138 private static bool surrogate_low_p (char c)
140 return (c >= 0xDC00 && c < 0xE000);
143 private static int inc_idx (StringBuilder sb, int i)
145 return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
148 private static int dec_idx (StringBuilder sb, int i)
150 return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
153 private static int pos_to_idx (MText mt, int pos)
155 if (pos == mt.cache_pos)
161 if (pos < mt.cache_pos)
163 if (mt.cache_pos == mt.cache_idx)
165 if (pos < mt.cache_pos - pos)
172 p = mt.cache_pos; i = mt.cache_idx;
178 if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
179 return (mt.cache_idx + pos - mt.cache_pos);
180 if (pos - mt.cache_pos < mt.nchars - pos)
182 p = mt.cache_pos; i = mt.cache_idx;
187 p = mt.nchars; i = mt.sb.Length;
192 for (; p < pos; i = inc_idx (mt.sb, i), p++);
194 for (; p > pos; i = dec_idx (mt.sb, i), p--);
200 private void insert (int pos, MText mt2, int from, int to)
202 int pos_idx = pos_to_idx (this, pos);
203 int from_idx = pos_to_idx (mt2, from);
204 int to_idx = pos_to_idx (mt2, to);
206 sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
208 if (root_interval != null)
210 MInterval interval = (mt2.root_interval == null
211 ? new MInterval (0, false, to - from, false)
212 : mt2.root_interval.CopyTree (from, to));
213 root_interval.Insert (pos, interval);
217 public int this[int i]
220 i = pos_to_idx (this, i);
223 if (surrogate_high_p (sb[i]))
225 sb[i] = (char) value;
229 char high = (char) (0xD800 + ((value - 0x10000) >> 10));
230 char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
232 if (! surrogate_high_p (sb[i]))
239 i = pos_to_idx (this, i);
240 return (surrogate_high_p (sb[i])
241 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
248 return (new MText (sb.ToString ()));
251 public MText ins (int pos, MText mt)
253 insert (pos, mt, 0, mt.nchars);
257 public MText ins (int pos, MText mt, int from, int to)
259 insert (pos, mt, from, to);
263 public MText del (int from, int to)
265 sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
270 public void PushProp (int from, int to, MTextProperty prop)
272 if (root_interval == null)
273 root_interval = new MInterval (this);
274 root_interval.Push (from, to, prop);
277 private class MInterval
280 // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
281 // | | A | | B | | C | |
282 // interval |<--------->|<--->|<--------------->|<----|
285 // [0 10 (-1 9)] [-10 0 (89 99)]
286 // [0 4 (-1 3)] [-4 0 (5 9)] [0 4 (89 93)] [-2 0 (97 99)]
288 // Start and end positions of this interval and its children.
289 // If this is the left node, the values are relative to the
290 // parent's total_start. Otherwise, the values are relative to
291 // the parent's total_end. So:
292 // total_start total_end
293 // left-side interval 0 positive even
294 // right-side interval negative even 0
295 // top-most interval -1 positive odd
296 private int total_start, total_end;
297 // Stack of MTextProperty
298 private Stack<MTextProperty> stack;
299 private MInterval left, right, parent;
302 private static int adjust_position (int pos, bool front_inclusive)
304 return (pos << 2) + (front_inclusive ? -1 : 1);
307 private static bool before_point_p (int pos)
309 return ((pos + 1) % 4) == 0;
312 public MInterval (int start, bool front_inclusive,
313 int end, bool rear_inclusive)
316 throw new Exception ("Invalid Interval Range");
317 this.total_start = (start << 2) + (front_inclusive ? -1 : 1);
318 this.total_end = (end << 2) + (rear_inclusive ? 1 : -1);
319 this.stack = new Stack<MTextProperty> ();
322 public MInterval (MText mt)
325 this.total_start = -1;
326 this.total_end = (mt.sb.Length << 2) + 1;
327 this.stack = new Stack<MTextProperty> ();
330 private MInterval () { }
332 private MInterval (int start, int end, Stack<MTextProperty> stack)
334 this.total_start = start;
335 this.total_end = end;
336 this.stack = new Stack<MTextProperty> (stack);
339 private MInterval find (int pos, out int offset)
341 if (pos < total_start || total_end < pos)
347 return left.find (pos, out offset);
349 return right.find (pos - total_end, out offset);
350 offset = pos - Start;
354 // p-. or .-p p-. or .-p
355 // .-this-. .-right-.
356 // left .-right-. -> .-this-. c2
358 private MInterval promote_right ()
360 int right_length = - right.total_start;
364 mt.root_interval = right;
365 else if (total_start == 0)
368 parent.right = right;
369 right.parent = parent;
378 parent.total_start = total_start;
379 parent.total_end = total_end;
381 total_end -= right_length - (c1 == null ? 0 : c1.total_end);
385 c1.total_end = - c1.total_start;
391 // p-. or .-p p-. or .-p
393 // .-left-. .-right-. -> c1 .-this-.
395 private MInterval promote_left ()
397 int left_length = left.total_end;
401 mt.root_interval = left;
402 else if (total_start == 0)
406 left.parent = parent;
415 parent.total_start = total_start;
416 parent.total_end = total_end;
417 total_start -= left_length + (c2 == null ? 0 : c2.total_end);;
422 c2.total_start = - c2.total_end;
428 private MInterval balance ()
430 MInterval interval = this;
434 int this_start = interval.Start;
435 int this_end = interval.End;
436 int diff = ((this_start - interval.total_start)
437 - (interval.total_end - this_end));
438 int abs = Math.Abs (diff);
440 if (abs < this_end - this_start)
444 interval = interval.promote_right ();
445 interval.left.balance ();
449 interval = interval.promote_left ();
450 interval.right.balance ();
456 public MInterval CopyTree (int start, int end)
458 MInterval interval_start, interval_end, interval;
459 int offset_start, offset_end;
463 interval_start = find (start, out offset_start);
464 interval_end = find (end, out offset_end);
466 interval = new MInterval ();
467 interval.total_start = 0;
468 interval.total_end = end - start;
469 interval.stack = new Stack<MTextProperty> (interval_start.stack);
470 interval = interval.divide_right (offset_start);
471 while (interval_start != interval_end)
473 interval_start = interval_start.Right;
474 interval = interval.divide_right (interval_start.End
475 - interval_start.Start);
480 private MInterval CopyNode ()
482 return new MInterval (total_start, total_end, stack);
487 return (left == null ? total_start : total_start + left.total_end);
493 return (right == null ? total_end : total_end + right.total_start);
497 private MInterval Left {
501 for (i = left; i.right != null; i = i.right);
503 for (i = parent; i != null && i.total_start == 0; i = i.parent);
508 private MInterval Right {
512 for (i = right; i.left != null; i = i.left);
514 for (i = parent; i != null && i.total_start < 0; i = i.parent);
519 public void Push (int start, int end, MTextProperty prop)
522 if (prop.FrontSticky)
532 throw new Exception ("Invalid Text Property Range");
534 push (start, end, prop);
537 public void Insert (int pos, MInterval interval)
540 Left.Insert (pos - total_start, interval);
542 Right.Insert (pos - total_end, interval);
546 // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
547 // this |<----------<----------->---->|
548 // |<--------->| |<--->|
550 // interval |<====>---------->|
554 // new |<----------<----->----->-->------------>->|
555 // |<--------->| |<---->-->------------>->|
558 int len = interval.total_end - interval.total_start;
562 for (temp = this; temp.parent != null;
564 temp.parent.total_end += len;
565 if (End - pos < interval.End)
571 temp = divide_right (Start + 2);
572 temp.left = interval;
579 private MInterval divide_right (int pos)
581 MInterval interval = CopyNode ();
582 int this_start = Start;
586 || (right != null && left.total_end < - right.total_start))
588 interval.left = this;
589 interval.right = right;
590 interval.parent = parent;
593 if (total_start == 0)
594 parent.left = interval;
596 parent.right = interval;
599 total_end = pos - this_start;
603 interval.total_start = pos - this_end;
604 interval.total_end = 0;
606 right.parent = interval;
613 private MInterval divide_left (int pos)
615 MInterval interval = CopyNode ();
616 int this_start = Start;
620 || (right != null && left.total_end < - right.total_start))
622 interval.total_start = 0;
623 interval.total_end = pos - this_start;
625 left.parent = interval;
630 interval.right = this;
631 interval.left = left;
632 interval.parent = parent;
635 if (total_start == 0)
636 parent.left = interval;
638 parent.right = interval;
640 total_start = pos - this_end;
647 private void push (int start, int end, MTextProperty prop)
649 int this_start = Start;
652 if (start < this_start)
654 if (end <= this_start)
656 Left.push (start, end, prop);
659 Left.push (start, this_start, prop);
664 if (this_end < start)
666 Right.push (start, end, prop);
669 Right.push (this_end, end, prop);
672 if (this_start < start)
680 private class MTextEnum : IEnumerator
683 private int pos = -1;
685 public MTextEnum (MText mt)
690 public bool MoveNext ()
693 return (pos < mt.nchars);
701 public object Current
704 //if (pos < 0 || pos >= mt.nchars)
705 //throw new InvalidOperationException ();