6f21e60e308976663a0f0144f5cda0812698a6f2
[m17n/m17n-lib-cs.git] / MText.cs
1 using System;
2 using System.Text;
3 using System.Collections;
4 using System.Collections.Generic;
5 using M17N;
6 using M17N.Core;
7
8 namespace M17N.Core
9 {
10 #if false
11   public enum MTextFormat
12     {
13       MTEXT_FORMAT_US_ASCII,
14       MTEXT_FORMAT_UTF_8,
15       MTEXT_FORMAT_UTF_16BE,
16       MTEXT_FORMAT_UTF_16LE,
17       MTEXT_FORMAT_UTF_32BE,
18       MTEXT_FORMAT_UTF_32LE,
19     }
20 #endif
21
22   public class MTextProperty
23   {
24     internal MSymbol key;
25     internal object val;
26
27     [FlagsAttribute]
28     internal enum Flag : byte
29       {
30         None =          0,
31         FrontSticky =   1,
32         RearSticky =    2,
33         Sensitive =     4
34       };
35     internal Flag flags;
36
37     public MSymbol Key { get { return key; } }
38     public object Val { get { return val; } }
39     public bool FrontSticky
40     {
41       get { return (flags & Flag.FrontSticky) != Flag.None; }
42     }
43     public bool RearSticky
44     {
45       get { return (flags & Flag.RearSticky) != Flag.None; }
46     }
47     public bool Sensitive
48     {
49       get { return (flags & Flag.Sensitive) != Flag.None; }
50     }
51
52     public MTextProperty (MSymbol key, object val)
53     {
54       this.key = key;
55       this.val = val;
56       flags |= Flag.RearSticky;
57     }
58
59     public MTextProperty (MSymbol key, object val,
60                           bool front_sticky, bool rear_sticky, bool sensitive)
61     {
62       this.key = key;
63       this.val = val;
64       if (front_sticky)
65         flags |= Flag.FrontSticky;
66       if (rear_sticky)
67         flags |= Flag.RearSticky;
68       if (sensitive)
69         flags |= Flag.Sensitive;
70     }
71
72     public override string ToString ()
73     {
74       return key.ToString () + ":" + val;
75     }
76   }
77
78   public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
79   {
80 #if false
81     public enum MTextFormat format;
82 #endif
83     private StringBuilder sb;
84     private int nchars;
85     private int cache_pos;
86     private int cache_idx;
87     private MPlist intervals;
88     private MPlist default_property;
89     private bool read_only;
90
91     private static UTF8Encoding utf8 = new UTF8Encoding ();
92
93     private static int count_chars (String str)
94     {
95       int len = str.Length, n = 0;
96
97       for (int i = 0; i < len; i++, n++) 
98         if (surrogate_high_p (str[i]))
99           i++;
100       return n;
101     }
102
103     private static int count_chars (StringBuilder str)
104     {
105       int len = str.Length, n = 0;
106
107       for (int i = 0; i < len; i++, n++) 
108         if (surrogate_high_p (str[i]))
109           i++;
110       return n;
111     }
112
113     public MText ()
114       {
115         sb = new StringBuilder ();
116         intervals = new MPlist ();
117       }
118
119     public MText (byte[] str)
120       {
121         sb = new StringBuilder (utf8.GetString (str));
122         nchars = count_chars (sb);
123         intervals = new MPlist ();
124       }
125
126     public MText (String str)
127       {
128         sb = new StringBuilder (str);
129         nchars = count_chars (str);
130         intervals = new MPlist ();
131       }
132
133     public MText (StringBuilder str)
134       {
135         sb = str;
136         nchars = count_chars (str);
137         intervals = new MPlist ();
138       }
139
140     public static MText operator+ (MText mt1, MText mt2)
141     {
142       MText mt = new MText ();
143
144       mt.sb.Append (mt1.sb);
145       mt.sb.Append (mt2.sb);
146       mt.nchars = mt1.nchars + mt2.nchars;
147       return mt;
148     }
149
150     // Public properties
151     public bool ReadOnly { get { return read_only; } }
152     public int Length { get { return nchars; } }
153
154     // Public methods
155
156     // for IEnumerable interface
157     public IEnumerator GetEnumerator() { return new MTextEnum (this); }
158
159     // for IEquatable interface
160     public bool Equals (MText other) { return this.sb.Equals (other.sb); }
161
162     // for IComparable interface
163     public int CompareTo (MText other)
164     {
165       return this.sb.ToString ().CompareTo (other.sb.ToString ());
166     }
167
168     public override String ToString () { return "\"" + sb.ToString () + "\""; }
169
170     private static bool surrogate_high_p (char c)
171     {
172       return (c >= 0xD800 && c < 0xDC00);
173     }
174
175     private static bool surrogate_low_p (char c)
176     {
177       return (c >= 0xDC00 && c < 0xE000);
178     }
179
180     private static int inc_idx (StringBuilder sb, int i)
181     {
182       return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
183     }
184
185     private static int dec_idx (StringBuilder sb, int i)
186     {
187       return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
188     }
189
190     private static int pos_to_idx (MText mt, int pos)
191     {
192       if (pos == mt.cache_pos)
193         return mt.cache_idx;
194
195       int p, i;
196       bool forward;
197
198       if (pos < mt.cache_pos)
199         {
200           if (mt.cache_pos == mt.cache_idx)
201             return mt.cache_idx;
202           if (pos < mt.cache_pos - pos)
203             {
204               p = i = 0;
205               forward = true;
206             }
207           else
208             {
209               p = mt.cache_pos; i = mt.cache_idx;
210               forward = false;
211             }
212         }
213       else
214         {
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)
218             {
219               p = mt.cache_pos; i = mt.cache_idx;
220               forward = true;
221             }
222           else
223             {
224               p = mt.nchars; i = mt.sb.Length;
225               forward = false;
226             }
227         }
228       if (forward)
229         for (; p < pos; i = inc_idx (mt.sb, i), p++);
230       else
231         for (; p > pos; i = dec_idx (mt.sb, i), p--);
232       mt.cache_pos = p;
233       mt.cache_idx = i;
234       return i;
235     }
236
237     private void check_pos (int pos, bool tail_ok)
238     {
239       if (pos < 0 || (tail_ok ? pos > nchars : pos >= nchars))
240         throw new Exception ("Invalid MText position:" + pos);
241     }
242
243     private bool check_range (int from, int to, bool zero_ok)
244     {
245       if (from < 0 || (zero_ok ? from > to : from >= to)
246           || to > nchars)
247         throw new Exception ("Invalid MText range");
248       return (from == to);
249     }
250
251     private void insert (int pos, MText mt2, int from, int to)
252     {
253       check_pos (pos, true);
254
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);
258
259       sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
260       nchars += to - from;
261
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)
266         {
267           MPlist p = mt2.intervals.Find (plist.Key);
268           MInterval interval;
269
270           if (p == null)
271             interval = new MInterval (plist.Key, this, to - from);
272           else
273             interval = ((MInterval) p.Val).Copy (from, to);
274           ((MInterval) plist.Val).Insert (pos, interval);
275         }
276     }
277
278     private void insert (int pos, int c)
279     {
280       check_pos (pos, true);
281
282       int pos_idx = pos_to_idx (this, pos);
283
284       if (c < 0x10000)
285         {
286           char ch = (char) c;
287           sb.Insert (pos_idx, ch);
288         }
289       else
290         {
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);
295         }
296       nchars++;
297       foreach (MPlist plist in intervals)
298         ((MInterval) plist.Val).Insert (pos,
299                                         new MInterval (plist.Key, this, 1));
300     }
301
302     public int this[int i]
303     {
304       set {
305         i = pos_to_idx (this, i);
306         if (value < 0x10000)
307           {
308             if (surrogate_high_p (sb[i]))
309               sb.Remove (i, 1);
310             sb[i] = (char) value;
311           }
312         else
313           {
314             char high = (char) (0xD800 + ((value - 0x10000) >> 10));
315             char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
316
317             if (! surrogate_high_p (sb[i]))
318               sb.Insert (i, 0);
319             sb[i] = high;
320             sb[i + 1] = low;
321           }
322       }
323       get {
324         i = pos_to_idx (this, i);
325         return (surrogate_high_p (sb[i])
326                 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
327                 : sb[i]);
328       }
329     }
330
331     public MText Dup ()
332     {
333       MText mt = new MText (sb.ToString ());
334
335       foreach (MPlist p in intervals)
336         mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (0, Length));
337       return mt;
338     }
339
340     public MText Ins (int pos, int c)
341     {
342       insert (pos, c);
343       return this;
344     }
345
346     public MText Ins (int pos, MText mt)
347     {
348       insert (pos, mt, 0, mt.nchars);
349       return this;
350     }
351
352     public MText Ins (int pos, MText mt, int from, int to)
353     {
354       insert (pos, mt, from, to);
355       return this;
356     }
357
358     public MText Cat (int c)
359     {
360       insert (nchars, c);
361       return this;
362     }
363
364     public MText Del (int from, int to)
365     {
366       if (check_range (from, to, true))
367         return this;
368
369       sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
370       nchars -= to - from;
371
372       if (nchars > 0)
373         foreach (MPlist plist in intervals)
374           ((MInterval) plist.Val).Delete (from, to);
375       else
376         intervals = new MPlist ();
377       return this;
378     }
379
380     public object GetProp (int pos, MSymbol key)
381     {
382       check_pos (pos, false);
383
384       MInterval i = (MInterval) intervals.Get (key);
385       if (i == null)
386         return null;
387
388       MTextProperty prop = i.Get (pos);
389       return (prop != null ? prop.Val : null);
390     }
391
392     public object GetProp (int pos, MSymbol key, out MTextProperty prop)
393     {
394       check_pos (pos, false);
395
396       MInterval i = (MInterval) intervals.Get (key);
397       if (i == null)
398         return (prop = null);
399       prop = i.Get (pos);
400       return (prop != null ? prop.Val : null);
401     }
402
403     public object GetProp (int pos, MSymbol key, out MTextProperty[] array)
404     {
405       check_pos (pos, false);
406
407       MInterval i = (MInterval) intervals.Get (key);
408       if (i == null)
409         return (array = null);
410       MTextProperty prop = i.Get (pos, out array);
411       return (prop != null ? prop.Val : null);
412     }
413
414     public void PushProp (int from, int to, MSymbol key, object val)
415     {
416       if (! check_range (from, to, true))
417         PushProp (from, to, new MTextProperty (key, val));
418     }
419
420     public void PushProp (int from, int to, MTextProperty prop)
421     {
422       if (from < 0)
423         {
424           if (default_property == null)
425             default_property = new MPlist ();
426           default_property.Push (prop.key, prop.val);
427         }
428       else
429         {
430           if (check_range (from, to, true))
431             return;
432
433           MPlist p = intervals.Find (prop.key);
434           MInterval root;
435
436           if (p == null)
437             {
438               root = new MInterval (prop.key, this);
439               intervals.Push (prop.key, root);
440             }
441           else
442             root = (MInterval) p.Val;
443
444           root.Push (from, to, prop);
445         }
446     }
447
448     public void PopProp (int from, int to, MSymbol key)
449     {
450       if (from < 0)
451         {
452           if (default_property == null)
453             return;
454           MPlist p = default_property.Find (key);
455
456           if (p != null)
457             p.Pop ();
458         }
459       else
460         {
461           if (check_range (from, to, true))
462             return;
463
464           MPlist p = intervals.Find (key);
465
466           if (p != null)
467             ((MInterval) p.Val).Pop (from, to);
468         }
469     }
470
471     public void DumpProp ()
472     {
473       Console.Write ("(");
474       foreach (MPlist p in intervals)
475         ((MInterval) p.Val).Dump (true);
476       Console.WriteLine (")");
477     }
478
479     public void DumpPropNested ()
480     {
481       foreach (MPlist p in intervals)
482         ((MInterval) p.Val).DumpNested (true);
483     }
484
485     private class MInterval
486     {
487       // position: 0   1   2   3   4   5   6   7
488       //           | A | B | C | D | E   F | G |
489       // interval  |---|---|---|<->|-------|---|
490       //           |---|<->|---|   |<----->|---|
491       //           |<->|   |<->|           |<->|
492       // 
493       //                      [7 (3 4)]
494       //              [3 (1 2)]       [3 (4 6)]
495       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
496       //
497       private static int count = 0;
498       private int ID;
499       private int Length;
500       private int From, To;
501       private MSymbol Key;
502       private MPlist Stack;
503       private MInterval Left, Right, Parent;
504       private MText mtext;
505
506       public MInterval (MSymbol key, MText mt, int length)
507       {
508         if (length <= 0)
509           throw new Exception ("Invalid interval length");
510         Key = key;
511         mtext = mt;
512         Length = length;
513         Stack = new MPlist ();
514         ID = count++;
515       }
516
517       public MInterval (MSymbol key, MText mt)
518       {
519         Key = key;
520         mtext = mt;
521         Length = mt.sb.Length;
522         From = 0;
523         To = Length;
524         Stack = new MPlist ();
525         ID = count++;
526       }
527
528       public MTextProperty Get (int pos)
529       {
530         MInterval i = find (pos);
531
532         return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val);
533       }
534
535       public MTextProperty Get (int pos, out MTextProperty[] array)
536       {
537         MInterval i = find (pos);
538
539         if (i.Stack.IsEmpty)
540           {
541             array = null;
542             return null;
543           }
544         array = new MTextProperty[i.Stack.Count];
545
546         int idx;
547         MPlist p;
548         for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
549           array[idx] = (MTextProperty) p.Val;
550         return array[0];
551       }
552
553       private MInterval (MSymbol key, MText mt, int length, MPlist stack)
554       {
555         Key = key;
556         mtext = mt;
557         Length = length;
558         From = 0;
559         To = Length;
560         Stack = stack.Clone ();
561         ID = count++;
562       }
563
564       private void update_from_to ()
565       {
566         if (Parent == null)
567           {
568             From = LeftLength;
569             To = Length - RightLength;
570           }
571         else if (Parent.Left == this)
572           {
573             From = Parent.From - Length + LeftLength;
574             To = Parent.From - RightLength;
575           }
576         else
577           {
578             From = Parent.To + LeftLength;
579             To = Parent.To + Length - RightLength;
580           }
581       }
582
583       private int LeftLength
584       {
585         get { return (Left == null ? 0 : Left.Length); }
586       }
587
588       private int RightLength
589       {
590         get { return (Right == null ? 0 : Right.Length); }
591       }
592
593       private MInterval LeftMost
594       {
595         get { return (Left == null ? this : Left.LeftMost); }
596       }
597
598       private MInterval RightMost
599       {
600         get { return (Right == null ? this : Right.RightMost); }
601       }
602
603       private MInterval Prev {
604         get {
605           MInterval i;
606
607           if (Left != null)
608             for (i = Left; i.Right != null; i = i.Right);
609           else
610             {
611               MInterval child = this;
612               for (i = Parent; i != null && i.Left == child;
613                    child = i, i = i.Parent);
614             }
615           return i;
616         }
617       }
618
619       private MInterval Next {
620         get {
621           MInterval i;
622
623           if (Right != null)
624             for (i = Right; i.Left != null; i = i.Left);
625           else
626             {
627               MInterval child = this;
628               for (i = Parent; i != null && i.Right == child;
629                    child = i, i = i.Parent);
630             }
631           return i;
632         }
633       }
634
635       private MInterval find (int pos)
636       {
637         update_from_to ();
638         if (pos < From)
639           return Left.find (pos);
640         if (pos >= To)
641           return Right.find (pos);
642         return this;
643       }
644
645       private bool mergeable (MInterval i)
646       {
647         MPlist p1, p2;
648
649         for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
650              p1 = p1.Next, p2 = p2.Next)
651           if (p1.Val != p2.Val)
652             return false;
653         return (p1.IsEmpty && p2.IsEmpty);
654       }
655
656       //      p-. or .-p              p-. or .-p
657       //       .-this-.                .-right-.
658       //    left   .-right-.  ->   .-this-.    c2
659       //          c1       c2    left     c1
660       private MInterval promote_right ()
661       {
662         int right_length = Right.Length;
663         MInterval c1;
664
665         if (Parent == null)
666           mtext.intervals.Put (Key, Right);
667         else if (Parent.Left == this)
668           Parent.Left = Right;
669         else
670           Parent.Right = Right;
671         Right.Parent = Parent;
672         c1 = Right.Left;
673         Right.Left = this;
674
675         Parent = Right;
676         Right = c1;
677         Parent.Length += Length;
678         Length -= right_length;
679         if (c1 != null)
680           {
681             c1.Parent = this;
682             Parent.Length -= c1.Length;
683             Length += c1.Length;
684           }
685         return Parent;
686       }
687
688       //      p-. or .-p              p-. or .-p
689       //       .-this-.                .-left-.
690       //  .-left-.  .-right-.  ->     c1    .-this-.
691       // c1      c2                        c2     right
692       private MInterval promote_left ()
693       {
694         int left_length = Left.Length;
695         MInterval c1;
696
697         if (Parent == null)
698           mtext.intervals.Put (Key, Left);
699         else if (Parent.Left == this)
700           Parent.Left = Left;
701         else
702           Parent.Right = Left;
703         Left.Parent = Parent;
704         c1 = Left.Left;
705         Left.Right = this;
706
707         Parent = Left;
708         Left = c1;
709         Parent.Length += Length;
710         Length -= left_length;
711         if (c1 != null)
712           {
713             c1.Parent = this;
714             Parent.Length -= c1.Length;
715             Length += c1.Length;
716           }
717         return Parent;
718       }
719
720       private MInterval balance ()
721       {
722         MInterval i = this;
723
724         while (true)
725           {
726             //       .-this-.
727             //  .-left-.  .-right-.
728             // c1     c2  c3      c4
729             int diff = i.LeftLength - i.RightLength;
730             int new_diff;
731
732             if (diff > 0)
733               {
734                 new_diff = (i.Length - i.LeftLength
735                             + i.Left.RightLength - i.Left.LeftLength);
736                 if (Math.Abs (new_diff) >= diff)
737                   break;
738                 i = i.promote_left ();
739                 i.Right.balance ();
740               }
741             else if (diff < 0)
742               {
743                 new_diff = (i.Length - i.RightLength
744                             + i.Right.LeftLength - i.Right.RightLength);
745                 if (Math.Abs (new_diff) >= diff)
746                   break;
747                 i = i.promote_right ();
748                 i.Left.balance ();
749               }
750           }
751         return i;
752       }
753
754       public MInterval Copy (int start, int end)
755       {
756         MInterval copy, left_copy = null, right_copy = null;
757
758         update_from_to ();
759
760         if (start < From)
761           {
762             if (end <= From)
763               return Left.Copy (start, end);
764             left_copy = Left.Copy (start, From);
765           }
766         if (end > To)
767           {
768             if (start >= To)
769               return Right.Copy (start, end);
770             right_copy = Right.Copy (To, end);
771           }
772
773         copy = new MInterval (Key, null, end - start, Stack);
774         remove_properties (MTextProperty.Flag.Sensitive);
775         if (left_copy != null)
776           {
777             copy.Left = left_copy;
778             left_copy.Parent = copy;
779           }
780         if (right_copy != null)
781           {
782             copy.Right = right_copy;
783             right_copy.Parent = copy;
784           }
785         return copy;
786       }
787
788       //  this-.   ==>   this-.
789       //     right          newright-.
790       //                            right
791       private MInterval divide_right (int pos)
792       {
793         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
794
795         M17N.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
796         To = pos;
797         if (Right != null)
798           {
799             interval.Right = Right;
800             Right.Parent = interval;
801             interval.Length += Right.Length;
802           }
803         interval.Parent = this;
804         Right = interval;
805         return interval;
806       }
807
808       //    .-this   ==>       .-this
809       //  left             .-newleft
810       //                 left
811       private MInterval divide_left (int pos)
812       {
813         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
814
815         M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
816         From = pos;
817         if (Left != null)
818           {
819             interval.Left = Left;
820             Left.Parent = interval;
821             interval.Length += Left.Length;
822           }
823         interval.Parent = this;
824         Left = interval;
825         return interval;
826       }
827
828       private void remove_properties (MTextProperty.Flag flags)
829       {
830         for (MPlist p = Stack; ! p.IsEmpty;)
831           {
832             MTextProperty prop = (MTextProperty) p.Val;
833
834             if ((prop.flags & flags) == flags)
835               p.Pop ();
836             else
837               p = p.Next;
838           }
839       }
840
841       private void inherit_front_properties (MPlist plist)
842       {
843         for (MInterval i = LeftMost; i != null; i = i.Next)
844           {
845             if (! Stack.IsEmpty)
846               break;
847             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
848               {
849                 MTextProperty prop = (MTextProperty) p.Val;
850
851                 if ((prop.flags & MTextProperty.Flag.RearSticky)
852                     == MTextProperty.Flag.RearSticky)
853                   i.Stack.Add (prop.key, prop);
854               }
855           }
856       }
857
858       private void inherit_rear_properties (MPlist plist)
859       {
860         for (MInterval i = RightMost; i != null; i = i.Prev)
861           {
862             if (! Stack.IsEmpty)
863               break;
864             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
865               {
866                 MTextProperty prop = (MTextProperty) p.Val;
867
868                 if ((prop.flags & MTextProperty.Flag.FrontSticky)
869                     == MTextProperty.Flag.FrontSticky)
870                   i.Stack.Add (prop.key, prop);
871               }
872           }
873       }
874
875       private MInterval delete_node_forward ()
876       {
877         if (Parent != null)
878           {
879             int len = Length - RightLength;
880
881             for (MInterval i = Parent; i != null; i = i.Parent)
882               i.Length -= len;
883             if (Parent.Left == this)
884               Parent.Left = Right;
885             else
886               Parent.Right = Right;
887           }
888
889         if (Right != null)
890           {
891             Right.Parent = Parent;
892             return Right.LeftMost;
893           }
894         return Parent;
895       }
896
897       private MInterval delete_node_backward ()
898       {
899         if (Parent != null)
900           {
901             int len = Length - RightLength;
902
903             for (MInterval i = Parent; i != null; i = i.Parent)
904               i.Length -= len;
905             if (Parent.Left == this)
906               Parent.Left = Left;
907             else
908               Parent.Right = Left;
909           }
910
911         if (Left != null)
912           {
913             Left.Parent = Parent;
914             return Left.RightMost;
915           }
916         return Parent;
917       }
918
919       private void set_mtext (MText mt)
920       {
921         mtext = mt;
922         if (Left != null)
923           Left.set_mtext (mt);
924         if (Right != null)
925           Right.set_mtext (mt);
926       }
927
928       private MInterval graft (MInterval interval, bool forward, out int len)
929       {
930         MInterval i;
931
932         len = 0;
933         if (forward)
934           {
935             i = interval.LeftMost;
936             while (i != null)
937               {
938                 if (! mergeable (i))
939                   break;
940                 len += i.Length - i.RightLength;
941                 i = i.delete_node_forward ();
942               }
943           }
944         else
945           {
946             i = interval.RightMost;
947             while (i != null)
948               {
949                 if (! mergeable (i))
950                   break;
951                 len += i.Length - i.LeftLength;
952                 i = i.delete_node_backward ();
953               }
954           }
955
956         Length += len;
957         To += len;
958         for (MInterval prev = this, ii = this.Parent; ii != null;
959              prev = ii, ii = ii.Parent)
960           {
961             ii.Length += len;
962             if (prev == ii.Left)
963               {
964                 ii.From += len;
965                 ii.To += len;;
966               }
967           }
968         if (i != null)
969           while (i.Parent != null) i = i.Parent;
970         return i;
971       }
972
973       public void Insert (int pos, MInterval interval)
974       {
975         update_from_to ();
976         M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos);
977         DumpOne (false, true);
978
979         interval.set_mtext (mtext);
980
981         if (pos < From)
982           Prev.Insert (pos, interval);
983         else if (pos == From)
984           {
985             MInterval prev = Prev;
986
987             if (prev != null)
988               {
989                 if (Left == null)
990                   {
991                     prev.Insert (pos, interval);
992                     return;
993                   }
994                 prev.remove_properties
995                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
996                 interval.inherit_front_properties (prev.Stack);
997               }
998             remove_properties
999               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1000             interval.inherit_rear_properties (Stack);
1001
1002             int len;
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)
1007               {
1008                 MInterval i;
1009
1010                 if (Left != null)
1011                   {
1012                     //    .-this-.   ==>          .-this-.
1013                     // left-.                 .-left-.
1014                     //    child                     child-.
1015                     //                                 interval
1016                     i = Left.RightMost;
1017                     i.Right = interval;
1018                   }
1019                 else
1020                   {
1021                     Left = interval;
1022                     i = this;
1023                   }
1024                 interval.Parent = i;
1025                 for (; i != null; i = i.Parent)
1026                   i.Length += interval.Length;
1027               }
1028           }
1029         else if (pos < To)
1030           {
1031             remove_properties (MTextProperty.Flag.Sensitive);
1032
1033             int len;
1034             interval = graft (interval, true, out len);
1035             pos += len;
1036             if (interval != null)
1037               interval = graft (interval, false, out len);
1038             if (interval != null)
1039               {
1040                 divide_right (pos);
1041                 Right.Left = interval;
1042                 interval.Parent = Right;
1043                 for (MInterval i = Right; i != null; i = i.Parent)
1044                   i.Length += interval.Length;
1045               }
1046           }
1047         else if (pos == To)
1048           {
1049             MInterval next = Next;
1050
1051             if (next != null)
1052               {
1053                 if (Right == null)
1054                   {
1055                     next.Insert (pos, interval);
1056                     return;
1057                   }
1058                 next.remove_properties
1059                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1060                 interval.inherit_rear_properties (next.Stack);
1061               }
1062             remove_properties
1063               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
1064             interval.inherit_front_properties (Stack);
1065
1066             int len;
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)
1071               {
1072                 MInterval i;
1073
1074                 if (Right != null)
1075                   {
1076                     //    .-this-.   ==>          .-this-.
1077                     //         .-right                 .-right
1078                     //     child                  .-child
1079                     //                        interval
1080
1081                     i = Right.LeftMost;
1082                     i.Left = interval;
1083                   }
1084                 else
1085                   {
1086                     Right = interval;
1087                     i = this;
1088                   }
1089                 interval.Parent = i;
1090                 for (; i != null; i = i.Parent)
1091                   i.Length += interval.Length;
1092               }
1093           }
1094         else                    // (pos > To)
1095           Next.Insert (pos, interval);
1096       }
1097
1098       private void vacate_node (MInterval interval)
1099       {
1100         M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID);
1101         if (interval != null)
1102           interval.Parent = Parent;
1103         if (Parent == null)
1104           {
1105             if (mtext != null)
1106               mtext.intervals.Put (Key, interval);
1107           }
1108         else
1109           {
1110             if (this == Parent.Right)
1111               Parent.Right = interval;
1112             else
1113               Parent.Left = interval;
1114
1115             int diff = Length;
1116             if (interval != null)
1117               diff -= interval.Length;
1118             for (MInterval i = Parent; i != null; i = i.Parent)
1119               i.Length -= diff;
1120           }
1121       }
1122
1123       public void Delete (int start, int end)
1124       {
1125         update_from_to ();
1126         M17N.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
1127         if (start < From)
1128           {
1129             if (end <= From)
1130               {
1131                 Left.Delete (start, end);
1132                 return;
1133               }
1134             Left.Delete (start, From);
1135             To -= From - start;
1136             end -= From - start;
1137             From = start;
1138           }
1139         if (end > To)
1140           {
1141             if (start >= To)
1142               {
1143                 Right.Delete (start, end);
1144                 return;
1145               }
1146             Right.Delete (To, end);
1147             end = To;
1148           }
1149         if (start == From && end == To)
1150           {
1151             if (Right == null)
1152               {
1153                 vacate_node (Left);
1154               }
1155             else
1156               {
1157                 if (Left != null)
1158                   {
1159                     MInterval i;
1160                 
1161                     for (i = Right; i.Left != null; i = i.Left)
1162                       i.Length += Left.Length;
1163                     i.Length += Left.Length;
1164                     i.Left = Left;
1165                     Left.Parent = i;
1166                   }
1167                 vacate_node (Right);
1168               }
1169           }
1170         else
1171           {
1172             int len = end - start;
1173
1174             for (MInterval i = this; i != null; i = i.Parent)
1175               i.Length -= len;
1176           }
1177       }
1178
1179       public void Push (int start, int end, MTextProperty prop)
1180       {
1181         update_from_to ();
1182         M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
1183         if (start < From)
1184           {
1185             if (end <= From)
1186               {
1187                 Left.Push (start, end, prop);
1188                 return;
1189               }
1190             Left.Push (start, From, prop);
1191             start = From;
1192           }
1193         if (end > To)
1194           {
1195             if (start >= To)
1196               {
1197                 Right.Push (start, end, prop);
1198                 return;
1199               }
1200             Right.Push (To, end, prop);
1201             end = To;
1202           }
1203
1204         if (start > From)
1205           divide_left (start);
1206         if (end < To)
1207           divide_right (end);
1208         Stack.Push (prop.key, prop);
1209       }
1210
1211       private bool try_merge_prev ()
1212       {
1213         MInterval prev = Prev;
1214
1215         if (! mergeable (prev))
1216           return false;
1217
1218         M17N.DebugPrint ("merging "); DumpOne (false, false);
1219         M17N.DebugPrint (" with prev "); prev.DumpOne (false, true);
1220         int len = prev.Length - prev.LeftLength;
1221
1222         // PREV is Left, Left.Right, ..., or Left....Right.
1223         if (prev != Left)
1224           {
1225             if (prev.Left != null)
1226               prev.Left.Parent = prev.Parent;
1227             prev.Parent.Right = prev.Left;
1228             while (prev.Parent != Left)
1229               {
1230                 prev.Length -= len;
1231                 prev = prev.Parent;
1232               }
1233           }
1234         Left.Length -= len;
1235         if (Left.Length == Left.LeftLength)
1236           {
1237             if (Left.Left != null)
1238               Left.Left.Parent = this;
1239             Left = Left.Left;
1240           }
1241         return true;
1242       }
1243
1244       private bool try_merge_next ()
1245       {
1246         MInterval next = Next;
1247
1248         if (! mergeable (next))
1249           return false;
1250
1251         M17N.DebugPrint ("merging "); DumpOne (false, false);
1252         M17N.DebugPrint (" with next "); next.DumpOne (false, true);
1253
1254         int len = next.Length - next.RightLength;
1255
1256         // NEXT is Right, Right.Left, ..., or Right....Left.
1257         if (next != Right)
1258           {
1259             if (next.Right != null)
1260               next.Right.Parent = next.Parent;
1261             next.Parent.Left = next.Right;
1262             while (next.Parent != Right)
1263               {
1264                 next.Length -= len;
1265                 next = next.Parent;
1266               }
1267           }
1268         Right.Length -= len;
1269         if (Right.Length == Right.RightLength)
1270           {
1271             if (Right.Right != null)
1272               Right.Right.Parent = this;
1273             Right = Right.Right;
1274           }
1275         return true;
1276       }
1277
1278       public void Pop (int start, int end)
1279       {
1280         update_from_to ();
1281         M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
1282         if (start < From)
1283           {
1284             if (end <= From)
1285               {
1286                 Left.Pop (start, end);
1287                 return;
1288               }
1289             Left.Pop (start, From);
1290             start = From;
1291           }
1292         if (end > To)
1293           {
1294             if (start >= To)
1295               {
1296                 Right.Pop (start, end);
1297                 return;
1298               }
1299             Right.Pop (To, end);
1300             end = To;
1301           }
1302
1303         if (! Stack.IsEmpty)
1304           {
1305             bool check_prev = start == From && start > 0;
1306             bool check_next = end == To && end < mtext.Length;
1307
1308             if (! check_prev && start > From)
1309               divide_left (start);
1310             if (! check_next && end < To)
1311               divide_right (end);
1312             Stack.Pop ();
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);
1317             if (check_prev)
1318               {
1319                 if (Prev.try_merge_next () && check_next)
1320                   Prev.try_merge_next ();
1321               }
1322             else if (check_next)
1323               {
1324                 Next.try_merge_prev ();
1325               }
1326           }
1327       }
1328
1329       private void DumpOne (bool with_prop, bool newline)
1330       {
1331         DumpOne (with_prop, newline, false);
1332       }
1333
1334       private void DumpOne (bool with_prop, bool newline, bool force)
1335       {
1336         if (force || M17N.debug)
1337           {
1338             Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1339             if (with_prop)
1340               foreach (MPlist p in Stack)
1341                 Console.Write (" " + p.Val);
1342             Console.Write (")");
1343             if (newline)
1344               Console.WriteLine ();
1345             if (Length <= 0)
1346               throw new Exception ("Invalid interval length");
1347           }
1348       }
1349
1350       public void Dump () { Dump (false); }
1351
1352       public void Dump (bool force)
1353       {
1354         if (force || M17N.debug)
1355           {
1356             update_from_to ();
1357
1358             if (Left != null)
1359               Left.Dump (force);
1360             if (From > 0)
1361               Console.Write (" ");
1362             DumpOne (true, false, force);
1363             if (Right != null)
1364               Right.Dump (force);
1365           }
1366       }
1367
1368       private int Depth {
1369         get { return (Parent == null ? 0 : Parent.Depth + 1); }
1370       }
1371
1372       public void DumpNested (bool force)
1373       {
1374         DumpNested ("", force);
1375       }
1376
1377       public void DumpNested (string indent, bool force)
1378       {
1379         if (force || M17N.debug)
1380           {
1381             int indent_type = (Parent == null ? 1
1382                                : Parent.Left == this ? 0 : 2);
1383
1384             update_from_to ();
1385             if (Left != null)
1386               {
1387                 if (indent_type <= 1)
1388                   Left.DumpNested (indent + "  ", force);
1389                 else
1390                   Left.DumpNested (indent + "| ", force);
1391               }
1392             if (indent_type == 0)
1393               Console.Write (indent + ".-");
1394             else if (indent_type == 2)
1395               Console.Write (indent + "`-");
1396             DumpOne (true, true);
1397             if (Right != null)
1398               {
1399                 if (indent_type >= 1)
1400                   Right.DumpNested (indent + "  ", force);
1401                 else if (indent_type == 2)
1402                   Right.DumpNested (indent + "| ", force);
1403               }
1404           }
1405       }
1406     }
1407
1408     private class MTextEnum : IEnumerator
1409     {
1410       private MText mt;
1411       private int pos = -1;
1412
1413       public MTextEnum (MText mt)
1414         {
1415           this.mt = mt;
1416         }
1417
1418       public bool MoveNext ()
1419       {
1420         pos++;
1421         return (pos < mt.nchars);
1422       }
1423
1424       public void Reset ()
1425       {
1426         pos = -1;
1427       }
1428
1429       public object Current
1430       {
1431         get {
1432           //if (pos < 0 || pos >= mt.nchars)
1433           //throw new InvalidOperationException ();
1434           return mt[pos];
1435         }
1436       }
1437     }
1438   }
1439 }