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 enum MTextPropertyFlagMask
29 internal MProperty prop;
39 public bool FrontSticky
41 get { return (flags & MTextPropertyFlagMask.FRONT_STICKY) != 0; }
43 public bool RearSticky
45 get { return (flags & MTextPropertyFlagMask.REAR_STICKY) != 0; }
60 public MTextProperty (bool front_sticky, bool rear_sticky)
62 this.flags = ((front_sticky ? MTextPropertyFlagMask.FRONT_STICKY : 0)
63 | (rear_sticky ? MTextPropertyFlagMask.REAR_STICKY : 0));
67 public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
70 public enum MTextFormat format;
73 private struct KeyIntervalPair
79 private StringBuilder sb;
81 private int cache_pos;
82 private int cache_idx;
83 private stack<KeyIntervalPair> root_intervals;
84 private MProperty default_property;
85 private bool read_only;
87 private static UTF8Encoding utf8 = new UTF8Encoding ();
89 private static int count_chars (String str)
91 int len = str.Length, n = 0;
93 for (int i = 0; i < len; i++, n++)
94 if (surrogate_high_p (str[i]))
99 private static int count_chars (StringBuilder str)
101 int len = str.Length, n = 0;
103 for (int i = 0; i < len; i++, n++)
104 if (surrogate_high_p (str[i]))
111 sb = new StringBuilder ();
114 public MText (byte[] str)
116 sb = new StringBuilder (utf8.GetString (str));
117 nchars = count_chars (sb);
120 public MText (String str)
122 sb = new StringBuilder (str);
123 nchars = count_chars (str);
126 public MText (StringBuilder str)
129 nchars = count_chars (str);
132 public static MText operator+ (MText mt1, MText mt2)
134 MText mt = new MText ();
136 mt.sb.Append (mt1.sb);
137 mt.sb.Append (mt2.sb);
138 mt.nchars = mt1.nchars + mt2.nchars;
143 public bool ReadOnly { get { return read_only; } }
144 public int Length { get { return nchars; } }
148 // for IEnumerable interface
149 public IEnumerator GetEnumerator() { return new MTextEnum (this); }
151 // for IEquatable interface
152 public bool Equals (MText other) { return this.sb.Equals (other.sb); }
154 // for IComparable interface
155 public int CompareTo (MText other)
157 return this.sb.ToString ().CompareTo (other.sb.ToString ());
160 public override String ToString () { return sb.ToString (); }
162 private static bool surrogate_high_p (char c)
164 return (c >= 0xD800 && c < 0xDC00);
167 private static bool surrogate_low_p (char c)
169 return (c >= 0xDC00 && c < 0xE000);
172 private static int inc_idx (StringBuilder sb, int i)
174 return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
177 private static int dec_idx (StringBuilder sb, int i)
179 return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
182 private static int pos_to_idx (MText mt, int pos)
184 if (pos == mt.cache_pos)
190 if (pos < mt.cache_pos)
192 if (mt.cache_pos == mt.cache_idx)
194 if (pos < mt.cache_pos - pos)
201 p = mt.cache_pos; i = mt.cache_idx;
207 if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
208 return (mt.cache_idx + pos - mt.cache_pos);
209 if (pos - mt.cache_pos < mt.nchars - pos)
211 p = mt.cache_pos; i = mt.cache_idx;
216 p = mt.nchars; i = mt.sb.Length;
221 for (; p < pos; i = inc_idx (mt.sb, i), p++);
223 for (; p > pos; i = dec_idx (mt.sb, i), p--);
229 private void insert (int pos, MText mt2, int from, int to)
231 int pos_idx = pos_to_idx (this, pos);
232 int from_idx = pos_to_idx (mt2, from);
233 int to_idx = pos_to_idx (mt2, to);
235 sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
237 if (root_interval != null)
239 MInterval interval = (mt2.root_interval == null
241 : mt2.root_interval.CopyTree (from, to));
242 root_interval.Insert (pos, interval);
246 public int this[int i]
249 i = pos_to_idx (this, i);
252 if (surrogate_high_p (sb[i]))
254 sb[i] = (char) value;
258 char high = (char) (0xD800 + ((value - 0x10000) >> 10));
259 char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
261 if (! surrogate_high_p (sb[i]))
268 i = pos_to_idx (this, i);
269 return (surrogate_high_p (sb[i])
270 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
277 return (new MText (sb.ToString ()));
280 public MText ins (int pos, MText mt)
282 insert (pos, mt, 0, mt.nchars);
286 public MText ins (int pos, MText mt, int from, int to)
288 insert (pos, mt, from, to);
292 public MText del (int from, int to)
294 sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
299 public void PushProp (int from, int to, MTextProperty prop)
301 if (root_interval == null)
302 root_interval = new MInterval (this);
303 root_interval.Push (from, to, prop);
306 private class MInterval
310 // interval |<--------->|<--------->|<--------->|
313 // [1 (0 1)] [1 (2 3)]
314 private int total_length;
315 private int from, to;
317 private Stack<MTextProperty> stack;
318 private MInterval left, right, parent;
321 public MInterval (object key, int length)
324 throw new Exception ("Invalid interval length");
326 total_length = length;
327 stack = new Stack<MTextProperty> ();
330 private MInterval (object key, int length, Stack<MTextProperty> stack)
333 total_length = length;
336 stack = new Stack<MTextProperty> (stack);
339 public MInterval (object key, MText mt)
343 total_length = mt.sb.Length;
346 stack = new Stack<MTextProperty> ();
349 private MInterval find (int pos)
353 from = parent.from - total_length;
355 from += left.total_length;
358 to -= right.total_length;
361 return left.find (pos);
363 return right.find (pos);
367 // p-. or .-p p-. or .-p
368 // .-this-. .-right-.
369 // left .-right-. -> .-this-. c2
371 private MInterval promote_right ()
373 int right_length = right.total_length;
377 mtext.update_root_interval (key, right);
378 else if (parent.left == this)
381 parent.right = right;
382 right.parent = parent;
388 parent.total_length += total_length;
389 total_length -= right_length;
393 parent.total_length -= c1.total_length;
394 total_length += c1.total_length;
399 // p-. or .-p p-. or .-p
401 // .-left-. .-right-. -> c1 .-this-.
403 private MInterval promote_left ()
405 int left_length = left.total_length;
409 mtext.update_root_interval (key, left);
410 else if (parent.left == this)
414 left.parent = parent;
420 parent.total_length += total_length;
421 total_length -= left_length;
425 parent.total_length -= c1.total_length;
426 total_length += c1.total_length;
431 private MInterval balance ()
433 MInterval interval = this;
438 // .-left-. .-right-.
439 int left_length = (left == null ? 0 : left.total_length);
440 int right_length = (right == null ? 0 : right.total_length);
441 int length = total_length - left_length - right_length;
442 int diff = ((left_length + length) -
443 - (interval.total_end - this_end));
444 int abs = Math.Abs (diff);
449 if (abs < this_end - this_start)
453 interval = interval.promote_right ();
454 interval.left.balance ();
458 interval = interval.promote_left ();
459 interval.right.balance ();
465 public MInterval CopyTree (int start, int end)
467 MInterval interval_start, interval_end, interval;
468 int offset_start, offset_end;
472 interval_start = find (start, out offset_start);
473 interval_end = find (end, out offset_end);
475 interval = new MInterval ();
476 interval.total_start = 0;
477 interval.total_end = end - start;
478 interval.stack = new Stack<MTextProperty> (interval_start.stack);
479 interval = interval.divide_right (offset_start);
480 while (interval_start != interval_end)
482 interval_start = interval_start.Right;
483 interval = interval.divide_right (interval_start.End
484 - interval_start.Start);
489 private MInterval CopyNode ()
491 return new MInterval (total_start, total_end, stack);
496 return (left == null ? total_start : total_start + left.total_end);
502 return (right == null ? total_end : total_end + right.total_start);
506 private MInterval Left {
510 for (i = left; i.right != null; i = i.right);
512 for (i = parent; i != null && i.total_start == 0; i = i.parent);
517 private MInterval Right {
521 for (i = right; i.left != null; i = i.left);
523 for (i = parent; i != null && i.total_start < 0; i = i.parent);
528 public void Push (int start, int end, MTextProperty prop)
531 if (prop.FrontSticky)
541 throw new Exception ("Invalid Text Property Range");
543 push (start, end, prop);
546 public void Insert (int pos, MInterval interval)
549 Left.Insert (pos - total_start, interval);
551 Right.Insert (pos - total_end, interval);
555 // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
556 // this |-----------<-----a----->-----|
557 // |-----b-----| |--c--|
559 // interval <--A-->----------->
563 // new |-----------<-a-A->-----------------------|
564 // |-----b-----| |-----------<--a-->-----|
565 // |-a-B->-----| |--c--|
567 int len = interval.total_end - interval.total_start;
571 for (temp = this; temp.parent != null;
573 temp.parent.total_end += len;
574 temp = new MInterval ();
575 temp.stack = new Stack<MTextProperty> (stack);
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 ();