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 relatie to
291 // the parent's total_end.
292 private int total_start, total_end;
293 // Stack of MTextProperty
294 private Stack<MTextProperty> stack;
295 private MInterval left, right, parent;
298 private static int adjust_position (int pos, bool front_inclusive)
300 return (pos << 2) + (front_inclusive ? -1 : 1);
303 private static bool before_point_p (int pos)
305 return ((pos + 1) % 4) == 0;
308 public MInterval (int start, bool front_inclusive,
309 int end, bool rear_inclusive)
312 throw new Exception ("Invalid Interval Range");
313 this.total_start = (start << 2) + (front_inclusive ? -1 : 1);
314 this.total_end = (end << 2) + (rear_inclusive ? 1 : -1);
315 this.stack = new Stack<MTextProperty> ();
318 public MInterval (MText mt)
321 this.total_start = -1;
322 this.total_end = (mt.sb.Length << 2) + 1;
323 this.stack = new Stack<MTextProperty> ();
326 private MInterval () { }
328 private MInterval (int start, int end, Stack<MTextProperty> stack)
330 this.total_start = start;
331 this.total_end = end;
332 this.stack = new Stack<MTextProperty> (stack);
335 private MInterval find (int pos, out int offset)
337 if (pos < total_start || total_end < pos)
343 return left.find (pos, out offset);
345 return right.find (pos - total_end, out offset);
346 offset = pos - Start;
350 // p-. or .-p p-. or .-p
351 // .-this-. .-right-.
352 // left .-right-. -> .-this-. c2
354 private MInterval promote_right ()
356 int right_length = - right.total_start;
360 mt.root_interval = right;
361 else if (total_start == 0)
364 parent.right = right;
365 right.parent = parent;
374 parent.total_start = total_start;
375 parent.total_end = total_end;
377 total_end -= right_length - (c1 == null ? 0 : c1.total_end);
381 c1.total_end = - c1.total_start;
387 // p-. or .-p p-. or .-p
389 // .-left-. .-right-. -> c1 .-this-.
391 private MInterval promote_left ()
393 int left_length = left.total_end;
397 mt.root_interval = left;
398 else if (total_start == 0)
402 left.parent = parent;
411 parent.total_start = total_start;
412 parent.total_end = total_end;
413 total_start -= left_length + (c2 == null ? 0 : c2.total_end);;
418 c2.total_start = - c2.total_end;
424 private MInterval balance ()
426 MInterval interval = this;
430 int this_start = interval.Start;
431 int this_end = interval.End;
432 int diff = ((this_start - interval.total_start)
433 - (interval.total_end - this_end));
434 int abs = Math.Abs (diff);
436 if (abs < this_end - this_start)
440 interval = interval.promote_right ();
441 interval.left.balance ();
445 interval = interval.promote_left ();
446 interval.right.balance ();
452 public MInterval CopyTree (int start, int end)
454 MInterval interval_start, interval_end, interval;
455 int offset_start, offset_end;
459 interval_start = find (start, out offset_start);
460 interval_end = find (end, out offset_end);
462 interval = new MInterval ();
463 interval.total_start = 0;
464 interval.total_end = end - start;
465 interval.stack = new Stack<MTextProperty> (interval_start.stack);
466 interval = interval.divide_right (offset_start);
467 while (interval_start != interval_end)
469 interval_start = interval_start.Right;
470 interval = interval.divide_right (interval_start.End
471 - interval_start.Start);
476 private MInterval CopyNode ()
478 return new MInterval (total_start, total_end, stack);
483 return (left == null ? total_start : total_start + left.total_end);
489 return (right == null ? total_end : total_end + right.total_start);
493 private MInterval Left {
498 for (interval = left;
499 interval.right != null;
500 interval = interval.right);
502 for (interval = parent;
503 interval != null && interval.total_start == 0;
504 interval = interval.parent);
510 private MInterval Right {
515 for (interval = right;
516 interval.left != null;
517 interval = interval.left);
519 for (interval = parent;
520 interval != null && interval.total_start < 0;
521 interval = interval.parent);
527 public void Push (int start, int end, MTextProperty prop)
530 if (prop.FrontSticky)
540 throw new Exception ("Invalid Text Property Range");
542 push (start, end, prop);
545 public void Insert (int pos, MInterval interval)
548 Left.Insert (pos - total_start, interval);
550 Right.Insert (pos - total_end, interval);
554 // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
555 // this |<----------<-------------->->|
556 // |<--------->| |<>|
558 // interval |<->----->->|
560 // new |<----------<----->----->-->------------>->|
561 // |<--------->| |<---->-->------------>->|
564 int len = interval.total_end - interval.total_start;
568 for (temp = this; temp.parent != null;
570 temp.parent.total_end += len;
571 if (End - pos < interval.End)
577 temp = divide_right (Start + 2);
578 temp.left = interval;
585 private MInterval divide_right (int pos)
587 MInterval interval = CopyNode ();
588 int this_start = Start;
592 || (right != null && left.total_end < - right.total_start))
594 interval.left = this;
595 interval.right = right;
596 interval.parent = parent;
599 if (total_start == 0)
600 parent.left = interval;
602 parent.right = interval;
605 total_end = pos - this_start;
609 interval.total_start = pos - this_end;
610 interval.total_end = 0;
612 right.parent = interval;
619 private MInterval divide_left (int pos)
621 MInterval interval = CopyNode ();
622 int this_start = Start;
626 || (right != null && left.total_end < - right.total_start))
628 interval.total_start = 0;
629 interval.total_end = pos - this_start;
631 left.parent = interval;
636 interval.right = this;
637 interval.left = left;
638 interval.parent = parent;
641 if (total_start == 0)
642 parent.left = interval;
644 parent.right = interval;
646 total_start = pos - this_end;
653 private void push (int start, int end, MTextProperty prop)
655 int this_start = Start;
658 if (start < this_start)
660 if (end <= this_start)
662 Left.push (start, end, prop);
665 Left.push (start, this_start, prop);
670 if (this_end < start)
672 Right.push (start, end, prop);
675 Right.push (this_end, end, prop);
678 if (this_start < start)
686 private class MTextEnum : IEnumerator
689 private int pos = -1;
691 public MTextEnum (MText mt)
696 public bool MoveNext ()
699 return (pos < mt.nchars);
707 public object Current
710 //if (pos < 0 || pos >= mt.nchars)
711 //throw new InvalidOperationException ();