*** empty log message ***
[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 MProperty
23   {
24     [FlagsAttribute]
25     public enum Flags
26     {
27       None =            0x00,
28
29       /// On inserting a text in between two characters, if the
30       /// preceding and following characters have Sticky properties of
31       /// the same key with same values, the inserted text inherits
32       /// those properties.  In that case, properties of the inserted
33       /// text are overriden.
34       Sticky =          0x01,   // 00000001
35
36       /// On inserting a text before a character, if the character has
37       /// FrontSticky properties, the inserted text inherits those
38       /// properties.
39       FrontSticky =     0x03,   // 00000011
40
41       /// On inserting a text after a character, if the character has
42       /// RearSticky properties, the inserted text inherits those
43       /// properties.
44       RearSticky =      0x05,   // 00000101
45
46       /// Like RearSticky, but if the inserted text inherits no
47       /// properties from the preceding character, it inherits
48       /// BothSticky properties from the following character if any.
49       BothSticky =      0x07,   // 00000111
50
51       /// This property is deleted from a span of text if the span is
52       /// modified (i.e. one of a character is changed, a text is
53       /// inserted, some part is deleted).  Here, "span" means a
54       /// sequence of characters that has this property with the same
55       /// value.  This property is also deleted if a property of the
56       /// same key is added, which means that this property is not
57       /// stackable.  In addition this property is never merged with
58       /// the same value of preceding or following property.  At last,
59       /// this property can't be sticky in any way.
60       Sensitive =       0x10,   // 00010000
61
62       /// Like Sensitive but also this property is deleted from a span
63       /// of text if a characeter just before the span is modified,
64       /// inserted, or deleted.
65       FrontSensitive =  0x30,   // 00110000
66
67       /// Like Sensitive but also this property is deleted from a span
68       /// of text if a character just after the span is modified,
69       /// inserted, or deleted.
70       RearSensitive =   0x50,   // 01010000
71
72       /// Same as (FrontSensitive | RearSensitive).
73       BothSensitive =   0x70,   // 01110000
74     };
75
76     internal MSymbol key;
77     internal object val;
78
79     public MSymbol Key { get { return key; } }
80     public object Val { get { return val; } }
81
82     public MProperty (MSymbol key, object val)
83     {
84       if (key.flags == null)
85         key.flags = Flags.None;
86       this.key = key;
87       this.val = val;
88     }
89
90     public MProperty (string name, object val)
91     {
92       key = MSymbol.PropertyKey (name);
93       this.val = val;
94     }
95
96     public static bool HasFlags (MSymbol key, Flags flags)
97     {
98       return ((key.flags & flags) == flags);
99     }
100
101     public override string ToString ()
102     {
103       return key.ToString () + ":" + val;
104     }
105   }
106
107   public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
108   {
109 #if false
110     public enum MTextFormat format;
111 #endif
112     private StringBuilder sb;
113     private int nchars;
114     private int cache_pos;
115     private int cache_idx;
116     private MPlist intervals;
117     private MPlist default_property;
118     private bool read_only;
119
120     private static UTF8Encoding utf8 = new UTF8Encoding ();
121
122     private static int count_chars (String str)
123     {
124       int len = str.Length, n = 0;
125
126       for (int i = 0; i < len; i++, n++) 
127         if (surrogate_high_p (str[i]))
128           i++;
129       return n;
130     }
131
132     private static int count_chars (StringBuilder str)
133     {
134       int len = str.Length, n = 0;
135
136       for (int i = 0; i < len; i++, n++) 
137         if (surrogate_high_p (str[i]))
138           i++;
139       return n;
140     }
141
142     public MText ()
143       {
144         sb = new StringBuilder ();
145         intervals = new MPlist ();
146       }
147
148     public MText (byte[] str)
149       {
150         sb = new StringBuilder (utf8.GetString (str));
151         nchars = count_chars (sb);
152         intervals = new MPlist ();
153       }
154
155     public MText (String str)
156       {
157         sb = new StringBuilder (str);
158         nchars = count_chars (str);
159         intervals = new MPlist ();
160       }
161
162     public MText (StringBuilder str)
163       {
164         sb = str;
165         nchars = count_chars (str);
166         intervals = new MPlist ();
167       }
168
169     public static MText operator+ (object obj, MText mt)
170     {
171       if (obj is string)
172         {
173           MText mtnew = new MText ((string) obj);
174           return mtnew.Ins (mtnew.Length, mt);
175         }
176       throw new Exception ("Unknown object type: " + obj.GetType());
177     }
178
179     public static MText operator+ (MText mt, object obj)
180     {
181       if (obj is string)
182         return mt + new MText ((string) obj);
183       if (obj is int)
184         return mt.Dup ().Ins (mt.Length, (int) obj);
185       if (obj is char)
186         return mt.Dup ().Ins (mt.Length, (int) ((char) obj));
187       throw new Exception ("Unknown object type: " + obj.GetType());
188     }
189
190     public static MText operator+ (MText mt1, MText mt2)
191     {
192       return mt1.Dup ().Ins (mt1.Length, mt2);
193     }
194
195     // Public properties
196     public bool ReadOnly { get { return read_only; } }
197     public int Length { get { return nchars; } }
198
199     // Public methods
200
201     // for IEnumerable interface
202     public IEnumerator GetEnumerator() { return new MTextEnum (this); }
203
204     // for IEquatable interface
205     public bool Equals (MText other) { return this.sb.Equals (other.sb); }
206
207     // for IComparable interface
208     public int CompareTo (MText other)
209     {
210       return this.sb.ToString ().CompareTo (other.sb.ToString ());
211     }
212
213     public override string ToString () { return sb.ToString (); }
214
215     private static bool surrogate_high_p (char c)
216     {
217       return (c >= 0xD800 && c < 0xDC00);
218     }
219
220     private static bool surrogate_low_p (char c)
221     {
222       return (c >= 0xDC00 && c < 0xE000);
223     }
224
225     private static int inc_idx (StringBuilder sb, int i)
226     {
227       return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
228     }
229
230     private static int dec_idx (StringBuilder sb, int i)
231     {
232       return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
233     }
234
235     private static int pos_to_idx (MText mt, int pos)
236     {
237       if (pos == mt.cache_pos)
238         return mt.cache_idx;
239
240       int p, i;
241       bool forward;
242
243       if (pos < mt.cache_pos)
244         {
245           if (mt.cache_pos == mt.cache_idx)
246             return mt.cache_idx;
247           if (pos < mt.cache_pos - pos)
248             {
249               p = i = 0;
250               forward = true;
251             }
252           else
253             {
254               p = mt.cache_pos; i = mt.cache_idx;
255               forward = false;
256             }
257         }
258       else
259         {
260           if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
261             return (mt.cache_idx + pos - mt.cache_pos);
262           if (pos - mt.cache_pos < mt.nchars - pos)
263             {
264               p = mt.cache_pos; i = mt.cache_idx;
265               forward = true;
266             }
267           else
268             {
269               p = mt.nchars; i = mt.sb.Length;
270               forward = false;
271             }
272         }
273       if (forward)
274         for (; p < pos; i = inc_idx (mt.sb, i), p++);
275       else
276         for (; p > pos; i = dec_idx (mt.sb, i), p--);
277       mt.cache_pos = p;
278       mt.cache_idx = i;
279       return i;
280     }
281
282     private void check_pos (int pos, bool tail_ok)
283     {
284       if (pos < 0 || (tail_ok ? pos > nchars : pos >= nchars))
285         throw new Exception ("Invalid MText position:" + pos);
286     }
287
288     private bool check_range (int from, int to, bool zero_ok)
289     {
290       if (from < 0 || (zero_ok ? from > to : from >= to)
291           || to > nchars)
292         throw new Exception ("Invalid MText range");
293       return (from == to);
294     }
295
296     private void insert (int pos, MText mt2, int from, int to)
297     {
298       check_pos (pos, true);
299
300       if (M17n.debug)
301         {
302           Console.Write ("inserting {0} to {1} of ", from, to);
303           mt2.DumpPropNested ();
304         }
305       if (from == to)
306         return;
307       foreach (MPlist plist in intervals)
308         {
309           MInterval root = (MInterval) plist.Val;
310           MPlist p = mt2.intervals.Find (plist.Key);
311           MInterval i = p == null ? null : (MInterval) p.Val;
312
313           root.Insert (pos, i, from, to);
314         }
315       foreach (MPlist plist in mt2.intervals)
316         if (intervals.Find (plist.Key) == null)
317           {
318             MInterval root;
319
320             if (nchars == 0)
321               root = ((MInterval) plist.Val).Copy (this, from, to);
322             else
323               {
324                 root = new MInterval (plist.Key, this);
325                 root.Insert (pos, (MInterval) plist.Val, from, to);
326               }
327             intervals.Push (plist.Key, root);
328           }
329
330       int pos_idx = pos_to_idx (this, pos);
331       int from_idx = pos_to_idx (mt2, from);
332       int to_idx = pos_to_idx (mt2, to);
333
334       sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
335       nchars += to - from;
336     }
337
338     private void insert (int pos, int c)
339     {
340       check_pos (pos, true);
341
342       int pos_idx = pos_to_idx (this, pos);
343
344       if (c < 0x10000)
345         {
346           char ch = (char) c;
347           sb.Insert (pos_idx, ch);
348         }
349       else
350         {
351           char high = (char) (0xD800 + ((c - 0x10000) >> 10));
352           char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF));
353           sb.Insert (pos_idx, low);
354           sb.Insert (pos_idx, high);
355         }
356       nchars++;
357       foreach (MPlist plist in intervals)
358         ((MInterval) plist.Val).Insert (pos, null, 0, 1);
359     }
360
361     public int this[int i]
362     {
363       set {
364         i = pos_to_idx (this, i);
365         if (value < 0x10000)
366           {
367             if (surrogate_high_p (sb[i]))
368               sb.Remove (i, 1);
369             sb[i] = (char) value;
370           }
371         else
372           {
373             char high = (char) (0xD800 + ((value - 0x10000) >> 10));
374             char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
375
376             if (! surrogate_high_p (sb[i]))
377               sb.Insert (i, 0);
378             sb[i] = high;
379             sb[i + 1] = low;
380           }
381       }
382       get {
383         i = pos_to_idx (this, i);
384         return (surrogate_high_p (sb[i])
385                 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
386                 : sb[i]);
387       }
388     }
389
390     public MText Dup ()
391     {
392       MText mt = new MText (sb.ToString ());
393
394       foreach (MPlist p in intervals)
395         mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, 0, Length));
396       return mt;
397     }
398
399     public MText Dup (int from, int to)
400     {
401       if (check_range (from, to, true))
402         return new MText ();
403       int from_idx = pos_to_idx (this, from);
404       int len = pos_to_idx (this, to) - from_idx;
405       MText mt = new MText (sb.ToString ().Substring (from_idx, len));
406
407       foreach (MPlist p in intervals)
408         mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, from, to));
409       return mt;
410     }
411
412     public MText Ins (int pos, int c)
413     {
414       insert (pos, c);
415       return this;
416     }
417
418     public MText Ins (int pos, MText mt)
419     {
420       insert (pos, mt, 0, mt.nchars);
421       return this;
422     }
423
424     public MText Ins (int pos, MText mt, int from, int to)
425     {
426       insert (pos, mt, from, to);
427       return this;
428     }
429
430     public MText Cat (int c)
431     {
432       insert (nchars, c);
433       return this;
434     }
435
436     public MText Del (int from, int to)
437     {
438       if (check_range (from, to, true))
439         return this;
440
441       sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
442       nchars -= to - from;
443
444       if (nchars > 0)
445         foreach (MPlist plist in intervals)
446           {
447             MInterval root = (MInterval) plist.Val;
448             root.Delete (from, to);
449             if (from > 0 && from < nchars)
450               ((MInterval) plist.Val).MergeAfterChange (from, from);
451           }
452       else
453         intervals.Clear ();
454       if (M17n.debug)
455         DumpPropNested ();
456       return this;
457     }
458
459     public object GetProp (int pos, MSymbol key)
460     {
461       check_pos (pos, false);
462
463       MInterval i = (MInterval) intervals.Get (key);
464       if (i == null)
465         return null;
466
467       MProperty prop = i.Get (pos);
468       return (prop != null ? prop.Val : null);
469     }
470
471     public object GetProp (int pos, MSymbol key, out MProperty prop)
472     {
473       check_pos (pos, false);
474
475       MInterval i = (MInterval) intervals.Get (key);
476       if (i == null)
477         return (prop = null);
478       prop = i.Get (pos);
479       return (prop != null ? prop.Val : null);
480     }
481
482     public object GetProp (int pos, MSymbol key, out MProperty[] array)
483     {
484       check_pos (pos, false);
485
486       MInterval i = (MInterval) intervals.Get (key);
487       if (i == null)
488         return (array = null);
489       MProperty prop = i.Get (pos, out array);
490       return (prop != null ? prop.Val : null);
491     }
492
493     public void PushProp (int from, int to, MSymbol key, object val)
494     {
495       if (! check_range (from, to, true))
496         PushProp (from, to, new MProperty (key, val));
497     }
498
499     public void PushProp (int from, int to, MProperty prop)
500     {
501       if (from < 0)
502         {
503           if (default_property == null)
504             default_property = new MPlist ();
505           default_property.Push (prop.key, prop.val);
506         }
507       else
508         {
509           if (check_range (from, to, true))
510             return;
511
512           MPlist p = intervals.Find (prop.key);
513           MInterval root;
514
515           if (p == null)
516             {
517               root = new MInterval (prop.key, this);
518               intervals.Push (prop.key, root);
519             }
520           else
521             {
522               root = (MInterval) p.Val;
523               if (root.isSensitive)
524                 {
525                   root.PopSensitive (from, to);
526                   root.MergeAfterChange (from, to);
527                   root = (MInterval) p.Val;
528                   if (M17n.debug)
529                     DumpPropNested ();
530                 }
531             }
532           root.Push (from, to, prop);
533           root.MergeAfterChange (from, to);
534           root.Balance ();
535         }
536     }
537
538     public void PopProp (int from, int to, MSymbol key)
539     {
540       if (from < 0)
541         {
542           if (default_property == null)
543             return;
544           MPlist p = default_property.Find (key);
545
546           if (p != null)
547             p.Pop ();
548         }
549       else
550         {
551           if (check_range (from, to, true))
552             return;
553
554           MPlist p = intervals.Find (key);
555
556           if (p != null)
557             {
558               MInterval root = (MInterval) p.Val;
559               if (root.isSensitive)
560                 root.PopSensitive (from, to);
561               else
562                 root.Pop (from, to);
563               root = (MInterval) p.Val;
564               if (M17n.debug)
565                 DumpPropNested ();
566               root.MergeAfterChange (from, to);
567               root.Balance ();
568             }
569         }
570     }
571
572     public void DumpProp ()
573     {
574       Console.Write ("(");
575       foreach (MPlist p in intervals)
576         ((MInterval) p.Val).Dump (true);
577       Console.WriteLine (")");
578     }
579
580     public void DumpPropNested ()
581     {
582       Console.WriteLine ("total length = {0}", Length);
583       foreach (MPlist p in intervals)
584         ((MInterval) p.Val).DumpNested (true);
585     }
586
587     private class MInterval
588     {
589       // position: 0   1   2   3   4   5   6   7
590       //           | A | B | C | D | E   F | G |
591       // interval  |---|---|---|<->|-------|---|
592       //           |---|<->|---|   |<----->|---|
593       //           |<->|   |<->|           |<->|
594       // 
595       //                      [7 (3 4)]
596       //              [3 (1 2)]       [3 (4 6)]
597       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
598       //
599       private static int count = 0;
600       private int ID;
601       private int Length;
602       private int From, To;
603       private MSymbol Key;
604       private MPlist Stack;
605       private MInterval Left, Right, Parent;
606       private MText mtext;
607
608       public MInterval (MSymbol key, MText mt, int length)
609       {
610         if (length <= 0)
611           throw new Exception ("Invalid interval length");
612         Key = key;
613         mtext = mt;
614         Length = length;
615         Stack = new MPlist ();
616         ID = count++;
617       }
618
619       public MInterval (MSymbol key, MText mt)
620       {
621         Key = key;
622         mtext = mt;
623         Length = mt.sb.Length;
624         From = 0;
625         To = Length;
626         Stack = new MPlist ();
627         ID = count++;
628       }
629
630       /// POS must be smaller than Length;
631       public MProperty Get (int pos)
632       {
633         MInterval i = find_head (pos);
634
635         return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val);
636       }
637
638       /// POS must be smaller than Length;
639       public MProperty Get (int pos, out MProperty[] array)
640       {
641         MInterval i = find_head (pos);
642
643         if (i.To == pos)
644           i = i.Next;
645         if (i.Stack.IsEmpty)
646           {
647             array = null;
648             return null;
649           }
650         array = new MProperty[i.Stack.Count];
651
652         int idx;
653         MPlist p;
654         for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
655           array[idx] = (MProperty) p.Val;
656         return array[0];
657       }
658
659       private MInterval (MSymbol key, MText mt, int length, MPlist stack)
660       {
661         Key = key;
662         mtext = mt;
663         Length = length;
664         From = 0;
665         To = Length;
666         Stack = stack == null ? new MPlist () : stack.Clone ();
667         ID = count++;
668       }
669
670       private bool isRearSticky
671       {
672         get { return MProperty.HasFlags (Key, MProperty.Flags.RearSticky) ; }
673       }
674
675       private bool isFrontSticky
676       {
677         get { return MProperty.HasFlags (Key, MProperty.Flags.FrontSticky) ; }
678       }
679
680       public bool isSensitive
681       {
682         get { return MProperty.HasFlags (Key, MProperty.Flags.Sensitive) ; }
683       }
684
685       public bool isFrontSensitive
686       {
687         get { return MProperty.HasFlags (Key,
688                                          MProperty.Flags.FrontSensitive) ; }
689       }
690
691       public bool isRearSensitive
692       {
693         get { return MProperty.HasFlags (Key,
694                                          MProperty.Flags.RearSensitive) ; }
695       }
696
697       private void update_from_to ()
698       {
699         if (Parent == null)
700           {
701             From = LeftLength;
702             To = Length - RightLength;
703           }
704         else if (Parent.Left == this)
705           {
706             From = Parent.From - Length + LeftLength;
707             To = Parent.From - RightLength;
708           }
709         else
710           {
711             From = Parent.To + LeftLength;
712             To = Parent.To + Length - RightLength;
713           }
714       }
715
716       private int LeftLength
717       {
718         get { return (Left == null ? 0 : Left.Length); }
719       }
720
721       private int RightLength
722       {
723         get { return (Right == null ? 0 : Right.Length); }
724       }
725
726       private MInterval LeftMost
727       {
728         get {
729           update_from_to ();
730           if (Left == null)
731             return this;
732           return Left.LeftMost;
733         }
734       }
735
736       private MInterval RightMost
737       {
738         get {
739           update_from_to ();
740           if (Right == null)
741             return this;
742           return Right.RightMost;
743         }
744       }
745
746       private MInterval Prev {
747         get {
748           MInterval i;
749
750           if (Left != null)
751             {
752               for (i = Left; i.Right != null; i = i.Right)
753                 i.update_from_to ();
754               i.update_from_to ();
755             }
756           else
757             {
758               MInterval child = this;
759               for (i = Parent; i != null && i.Left == child;
760                    child = i, i = i.Parent);
761             }
762           return i;
763         }
764       }
765
766       private MInterval Next {
767         get {
768           MInterval i;
769
770           if (Right != null)
771             {
772               for (i = Right; i.Left != null; i = i.Left)
773                 i.update_from_to ();
774               i.update_from_to ();
775             }
776           else
777             {
778               MInterval child = this;
779               for (i = Parent; i != null && i.Right == child;
780                    child = i, i = i.Parent);
781             }
782           return i;
783         }
784       }
785
786       private MInterval find_head (int pos)
787       {
788         update_from_to ();
789         if (pos < From)
790           return Left.find_head (pos);
791         if (pos >= To)
792           return Right.find_head (pos);
793         return this;
794       }
795
796       private MInterval find_tail (int pos)
797       {
798         update_from_to ();
799         if (pos <= From)
800           return Left.find_tail (pos);
801         if (pos > To)
802           return Right.find_tail (pos);
803         return this;
804       }
805
806       private bool mergeable (MInterval i)
807       {
808         MPlist p1, p2;
809
810         if (Stack.IsEmpty && i.Stack.IsEmpty)
811           return true;
812         if (isSensitive)
813           return false;
814         for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
815              p1 = p1.Next, p2 = p2.Next)
816           if (p1.Val != p2.Val)
817             return false;
818         return (p1.IsEmpty && p2.IsEmpty);
819       }
820
821       //      p-. or .-p              p-. or .-p
822       //       .-this-.                .-right-.
823       //    left   .-right-.  ->   .-this-.    c2
824       //          c1       c2    left     c1
825       private MInterval promote_right ()
826       {
827         MInterval c1 = Right.Left;
828
829         // Update Parent.
830         if (Parent == null)
831           mtext.intervals.Put (Key, Right);
832         else if (Parent.Left == this)
833           Parent.Left = Right;
834         else
835           Parent.Right = Right;
836
837         // Update Right.
838         Right.Parent = Parent;
839         Right.Left = this;
840         Right.Length += LeftLength + (To - From);
841
842         // Update this.
843         Parent = Right;
844         Right = c1;
845         Length = LeftLength + (To - From) + RightLength;
846
847         // Update C1 if necessary.
848         if (c1 != null)
849           c1.Parent = this;
850
851         Parent.update_from_to ();
852         return Parent;
853       }
854
855       //      p-. or .-p              p-. or .-p
856       //       .-this-.                .-left-.
857       //  .-left-.  .-right-.  ->     c1    .-this-.
858       // c1      c2                        c2     right
859       private MInterval promote_left ()
860       {
861         MInterval c2 = Left.Right;
862
863         // Update Parent.
864         if (Parent == null)
865           mtext.intervals.Put (Key, Left);
866         else if (Parent.Left == this)
867           Parent.Left = Left;
868         else
869           Parent.Right = Left;
870
871         // Update Left.
872         Left.Parent = Parent;
873         Left.Right = this;
874         Left.Length += (To - From) + RightLength;
875
876         // Update this.
877         Parent = Left;
878         Left = c2;
879         Length = LeftLength + (To - From) + RightLength;
880
881         // Update C2 if necessary.
882         if (c2 != null)
883           c2.Parent = this;
884
885         Parent.update_from_to ();
886         return Parent;
887       }
888
889       public MInterval Balance ()
890       {
891         MInterval i = this;
892
893         update_from_to ();
894         while (true)
895           {
896             //       .-this-.
897             //  .-left-.  .-right-.
898             // c1     c2  c3      c4
899             int diff = i.LeftLength - i.RightLength;
900             int new_diff;
901
902             if (diff > 0)
903               {
904                 new_diff = (i.Length - i.LeftLength
905                             + i.Left.RightLength - i.Left.LeftLength);
906                 if (Math.Abs (new_diff) >= diff)
907                   break;
908                 M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
909                 i = i.promote_left ();
910                 M17n.DebugPrint ("done\n");
911                 i.Right.Balance ();
912               }
913             else if (diff < 0)
914               {
915                 new_diff = (i.Length - i.RightLength
916                             + i.Right.LeftLength - i.Right.RightLength);
917                 if (Math.Abs (new_diff) >= diff)
918                   break;
919                 M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
920                 i = i.promote_right ();
921                 i.Left.Balance ();
922               }
923             else
924               break;
925           }
926         return i;
927       }
928
929       public MInterval Copy (MText mt, int start, int end)
930       {
931         MInterval copy, left_copy = null, right_copy = null;
932
933         update_from_to ();
934
935         if (start < From)
936           {
937             if (end <= From)
938               return Left.Copy (mt, start, end);
939             left_copy = Left.Copy (mt, start, From);
940           }
941         if (end > To)
942           {
943             if (start >= To)
944               return Right.Copy (mt, start, end);
945             right_copy = Right.Copy (mt, To, end);
946           }
947
948         copy = new MInterval (Key, null, end - start, Stack);
949         copy.mtext = mt;
950         if (isSensitive && (From < start || end < To))
951           copy.Stack.Clear ();
952         if (left_copy != null)
953           {
954             copy.Left = left_copy;
955             left_copy.Parent = copy;
956           }
957         if (right_copy != null)
958           {
959             copy.Right = right_copy;
960             right_copy.Parent = copy;
961           }
962         return copy;
963       }
964
965       public MInterval Copy (MText mt, int start, int end,
966                              bool first, bool last)
967       {
968         MInterval copy = Copy (mt, start, end);
969         MInterval head = find_head (start);
970         MInterval tail = find_tail (end);
971
972         M17n.DebugPrint ("Copying: {0}", copy);
973
974         if (! head.Stack.IsEmpty
975             && (isSensitive && head.From < start
976                 || (isFrontSensitive && ! first)))
977           {
978             M17n.DebugPrint (" clear head");
979             head = copy.find_head (0);
980             head.Stack.Clear ();
981           }
982         if (! tail.Stack.IsEmpty
983             && (isSensitive && end < tail.To
984                 || (isRearSensitive && ! last)))
985           {
986             M17n.DebugPrint (" clear tail");
987             tail = copy.find_tail (copy.Length);
988             tail.Stack.Clear ();
989           }
990         M17n.DebugPrint ("\n");
991         return copy;
992       }
993
994       //  this-.   ==>   this-.
995       //     right          newright-.
996       //                            right
997       private MInterval divide_right (int pos)
998       {
999         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
1000
1001         M17n.DebugPrint ("divide-right({0}) at {1}\n", pos, this);
1002         To = pos;
1003         if (Right != null)
1004           {
1005             interval.Right = Right;
1006             Right.Parent = interval;
1007             interval.Length += Right.Length;
1008           }
1009         interval.Parent = this;
1010         Right = interval;
1011         return interval;
1012       }
1013
1014       //    .-this   ==>       .-this
1015       //  left             .-newleft
1016       //                 left
1017       private MInterval divide_left (int pos)
1018       {
1019         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
1020
1021         M17n.DebugPrint ("divide-left({0}) at {1}\n", pos, this);
1022         From = pos;
1023         if (Left != null)
1024           {
1025             interval.Left = Left;
1026             Left.Parent = interval;
1027             interval.Length += Left.Length;
1028           }
1029         interval.Parent = this;
1030         Left = interval;
1031         return interval;
1032       }
1033
1034       private void set_mtext (MText mt)
1035       {
1036         mtext = mt;
1037         if (Left != null)
1038           Left.set_mtext (mt);
1039         if (Right != null)
1040           Right.set_mtext (mt);
1041       }
1042
1043       private void enlarge (int len)
1044       {
1045         Length += len;
1046         To += len;
1047         for (MInterval prev = this, i = this.Parent; i != null;
1048              prev = i, i = i.Parent)
1049           {
1050             i.Length += len;
1051             if (prev == i.Left)
1052               {
1053                 i.From += len;
1054                 i.To += len;;
1055               }
1056           }
1057       }
1058
1059       private int graft_forward (MInterval interval, int start, int end)
1060       {
1061         int len;
1062
1063         if (! Stack.IsEmpty && isRearSticky)
1064           len = end - start;
1065         else if (interval == null)
1066           len = Stack.IsEmpty ? end - start : 0;
1067         else
1068           {
1069             MInterval i = interval.find_head (start);
1070
1071             len = 0;
1072             if (Stack.IsEmpty
1073                 && (isFrontSensitive || (isSensitive && i.From < start)))
1074               {
1075                 M17n.DebugPrint (" forward grafting {0}", i);
1076                 if (i.To < end)
1077                   len = i.To - start;
1078                 else
1079                   len = end - start;
1080                 i = i.Next;
1081               }
1082             while (i != null && i.From < end && mergeable (i))
1083               {
1084                 M17n.DebugPrint (" forward grafting {0}", i);
1085                 len += i.To - i.From;
1086                 if (i.From < start)
1087                   len -= start - i.From;
1088                 if (i.To >= end)
1089                   {
1090                     len -= i.To - end;
1091                     break;
1092                   }
1093                 i = i.Next;
1094               }
1095           }
1096
1097         M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1098         if (len > 0)
1099           enlarge (len);
1100         return len;
1101       }
1102
1103       private int graft_backward (MInterval interval, int start, int end)
1104       {
1105         int len;
1106
1107         if (! Stack.IsEmpty && isFrontSticky)
1108           len = end - start;
1109         else if (interval == null)
1110           len = Stack.IsEmpty ? end - start : 0;
1111         else
1112           {
1113             MInterval i = interval.find_tail (end);
1114
1115             len = 0;
1116             if (Stack.IsEmpty
1117                 && (isRearSensitive || (isSensitive && end < i.To)))
1118               {
1119                 M17n.DebugPrint (" backward grafting {0}", i);
1120                 if (i.From <= start)
1121                   len = end - start;
1122                 else
1123                   len = end - i.From;
1124                 i = i.Prev;
1125               }
1126             while (i != null && i.To <= start && mergeable (i))
1127               {
1128                 M17n.DebugPrint (" backward grafting {0}", i);
1129                 len += i.To - i.From;
1130                 if (end < i.To)
1131                   len -= i.To - end;
1132                 if (i.From <= start)
1133                   {
1134                     len -= start - i.From;
1135                     break;
1136                   }
1137                 i = i.Prev;
1138               }
1139           }
1140
1141         M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1142         if (len > 0)
1143           enlarge (len);
1144         return len;
1145       }
1146
1147       public void Insert (int pos, MInterval interval, int start, int end)
1148       {
1149         update_from_to ();
1150
1151         M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}",
1152                          start, end, pos, this);
1153
1154         if (pos < From)
1155           Left.Insert (pos, interval, start, end);
1156         else if (pos == From)
1157           {
1158             MInterval prev = Left != null ? Prev : null;
1159
1160             if (isFrontSensitive)
1161               Stack.Clear ();
1162             if (prev != null && isRearSensitive)
1163               prev.Stack.Clear ();
1164             if (prev != null && isRearSticky && ! prev.Stack.IsEmpty)
1165               {
1166                 prev.enlarge (end - start);
1167                 M17n.DebugPrint (" done\n");
1168                 return;
1169               }
1170             if (isFrontSticky && ! Stack.IsEmpty)
1171               {
1172                 enlarge (end - start);
1173                 M17n.DebugPrint (" done\n");
1174                 return;
1175               }
1176             bool front_grafted = false, rear_grafted = false;
1177             int grafted;
1178             if (prev != null
1179                 && (grafted = prev.graft_forward (interval, start, end)) > 0)
1180               {
1181                 start += grafted;
1182                 if (start == end)
1183                   {
1184                     M17n.DebugPrint (" done\n");
1185                     return;
1186                   }
1187                 front_grafted = true;
1188               }
1189             if ((grafted = graft_backward (interval, start, end)) > 0)
1190               {
1191                 end -= grafted;
1192                 if (start == end)
1193                   {
1194                     M17n.DebugPrint (" done\n");
1195                     return;
1196                   }
1197                 rear_grafted = true;
1198               }
1199
1200             if (interval != null)
1201               interval = interval.Copy (mtext, start, end,
1202                                         (front_grafted
1203                                          || (prev == null && start == 0)),
1204                                         rear_grafted);
1205             else
1206               interval = new MInterval (Key, mtext, end - start, null);
1207
1208             MInterval i;
1209             if (Left != null)
1210               {
1211                 //    .-this-.   ==>          .-this-.
1212                 // left-.                 .-left-.
1213                 //    child                     child-.
1214                 //                                 interval
1215                 i = Left.RightMost;
1216                 i.Right = interval;
1217               }
1218             else
1219               {
1220                 Left = interval;
1221                 i = this;
1222               }
1223             interval.Parent = i;
1224             for (; i != null; i = i.Parent)
1225               i.Length += interval.Length;
1226           }
1227         else if (pos < To)
1228           {
1229             if (! Stack.IsEmpty)
1230               {
1231                 if (isSensitive)
1232                   Stack.Clear ();
1233                 else if (isFrontSticky || isRearSticky)
1234                   {
1235                     enlarge (end - start);
1236                     return;
1237                   }
1238               }
1239             bool front_grafted = false, rear_grafted = false;
1240             int grafted;
1241             if ((grafted = graft_forward (interval, start, end)) > 0)
1242               {
1243                 start += grafted;
1244                 if (start == end)
1245                   {
1246                     M17n.DebugPrint (" done\n");
1247                     return;
1248                   }
1249                 front_grafted = true;
1250                 pos += grafted;
1251               }
1252             if ((grafted = graft_backward (interval, start, end)) > 0)
1253               {
1254                 end -= grafted;
1255                 if (start == end)
1256                   {
1257                     M17n.DebugPrint (" done\n");
1258                     return;
1259                   }
1260                 rear_grafted = true;
1261               }
1262             if (interval != null)
1263               interval = interval.Copy (mtext, start, end,
1264                                         front_grafted, rear_grafted);
1265             else
1266               interval = new MInterval (Key, mtext, end - start, null);
1267
1268             divide_right (pos);
1269             Right.Left = interval;
1270             interval.Parent = Right;
1271             for (MInterval i = Right; i != null; i = i.Parent)
1272               i.Length += interval.Length;
1273           }
1274         else if (pos == To)
1275           {
1276             MInterval next = Right != null ? Next : null;
1277
1278             if (isRearSensitive)
1279               Stack.Clear ();
1280             if (next != null && isFrontSensitive)
1281               next.Stack.Clear ();
1282             if (isRearSticky && ! Stack.IsEmpty)
1283               {
1284                 enlarge (end - start);
1285                 M17n.DebugPrint (" done by enlarging this\n");
1286                 return;
1287               }
1288             if (next != null && isFrontSticky && ! next.Stack.IsEmpty)
1289               {
1290                 M17n.DebugPrint (" next is {0}\n", next);
1291                 next.enlarge (end - start);
1292                 M17n.DebugPrint (" done by enlarging next\n");
1293                 return;
1294               }
1295             bool front_grafted = false, rear_grafted = false;
1296             int grafted;
1297             if (next != null
1298                 && (grafted = next.graft_backward (interval, start, end)) > 0)
1299               {
1300                 end -= grafted;
1301                 if (start == end)
1302                   {
1303                     M17n.DebugPrint (" done\n");
1304                     return;
1305                   }
1306                 rear_grafted = true;
1307               }
1308             if ((grafted = graft_forward (interval, start, end)) > 0)
1309               {
1310                 start += grafted;
1311                 if (start == end)
1312                   {
1313                     M17n.DebugPrint (" done\n");
1314                     return;
1315                   }
1316                 front_grafted = true;
1317               }
1318             if (interval != null)
1319               interval = interval.Copy (mtext, start, end,
1320                                         front_grafted,
1321                                         (rear_grafted
1322                                          || (next == null && end == interval.mtext.Length)));
1323             else
1324               interval = new MInterval (Key, mtext, end - start, null);
1325
1326             MInterval i;
1327             if (Right != null)
1328               {
1329                 //    .-this-.   ==>          .-this-.
1330                 //         .-right                 .-right
1331                 //     child                  .-child
1332                 //                        interval
1333
1334                 i = Right.LeftMost;
1335                 i.Left = interval;
1336               }
1337             else
1338               {
1339                 Right = interval;
1340                 i = this;
1341               }
1342             interval.Parent = i;
1343             for (; i != null; i = i.Parent)
1344               i.Length += interval.Length;
1345           }
1346         else                    // (pos > To)
1347           Right.Insert (pos, interval, start, end);
1348         M17n.DebugPrint (" done\n");
1349       }
1350
1351       private void vacate_node (MInterval interval)
1352       {
1353         vacate_node (interval, null);
1354       }
1355
1356       private void vacate_node (MInterval interval, MInterval stop)
1357       {
1358         if (interval != null)
1359           M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
1360         else
1361           M17n.DebugPrint ("vacate #{0} to null\n", ID);
1362         if (interval != null)
1363           interval.Parent = Parent;
1364         if (Parent == null)
1365           {
1366             if (mtext != null)
1367               mtext.intervals.Put (Key, interval);
1368           }
1369         else
1370           {
1371             if (this == Parent.Right)
1372               Parent.Right = interval;
1373             else
1374               Parent.Left = interval;
1375
1376             int diff = Length;
1377             if (interval != null)
1378               diff -= interval.Length;
1379             for (MInterval i = Parent; i != stop; i = i.Parent)
1380               i.Length -= diff;
1381           }
1382       }
1383
1384       public void Delete (int start, int end)
1385       {
1386         update_from_to ();
1387         M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this);
1388
1389         bool front_checked = false;
1390         bool rear_checked = false;
1391
1392         if (start < From)
1393           {
1394             if (end <= From)
1395               {
1396                 if (end == From && isFrontSensitive)
1397                   Stack.Clear ();
1398                 Left.Delete (start, end);
1399                 return;
1400               }
1401             if (isSensitive)
1402               Stack.Clear ();
1403             Left.Delete (start, From);
1404             To -= From - start;
1405             end -= From - start;
1406             From = start;
1407             front_checked = true;
1408           }
1409         if (end > To)
1410           {
1411             if (start >= To)
1412               {
1413                 if (start == To && isRearSensitive)
1414                   Stack.Clear ();
1415                 Right.Delete (start, end);
1416                 return;
1417               }
1418             if (isSensitive)
1419               Stack.Clear ();
1420             Right.Delete (To, end);
1421             end = To;
1422             rear_checked = true;
1423           }
1424         if (start == From
1425             && ! front_checked
1426             && start > 0
1427             && isRearSensitive)
1428           Prev.Stack.Clear ();
1429         if (end == To
1430             && ! rear_checked
1431             && Next != null
1432             && isFrontSensitive)
1433           Next.Stack.Clear ();
1434         if (start == From && end == To)
1435           {
1436             if (Right == null)
1437               {
1438                 vacate_node (Left);
1439               }
1440             else
1441               {
1442                 if (Left != null)
1443                   {
1444                     MInterval i;
1445                 
1446                     for (i = Right; i.Left != null; i = i.Left)
1447                       i.Length += Left.Length;
1448                     i.Length += Left.Length;
1449                     i.Left = Left;
1450                     Left.Parent = i;
1451                   }
1452                 vacate_node (Right);
1453               }
1454           }
1455         else
1456           {
1457             int len = end - start;
1458
1459             if (isSensitive)
1460               Stack.Clear ();
1461             for (MInterval i = this; i != null; i = i.Parent)
1462               i.Length -= len;
1463           }
1464       }
1465
1466       public void Push (int start, int end, MProperty prop)
1467       {
1468         update_from_to ();
1469         M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this);
1470         if (start < From)
1471           {
1472             if (end <= From)
1473               {
1474                 Left.Push (start, end, prop);
1475                 return;
1476               }
1477             Left.Push (start, From, prop);
1478             start = From;
1479           }
1480         if (end > To)
1481           {
1482             if (start >= To)
1483               {
1484                 Right.Push (start, end, prop);
1485                 return;
1486               }
1487             Right.Push (To, end, prop);
1488             end = To;
1489           }
1490
1491         if (! Stack.IsEmpty && isSensitive)
1492           Stack.Clear ();
1493         if (start > From)
1494           divide_left (start);
1495         if (end < To)
1496           divide_right (end);
1497         Stack.Push (prop.key, prop);
1498       }
1499
1500       /// Combine intervals between HEAD and TAIL (both inclusive) to
1501       /// the common parent of HEAD and TAIL.  Callers should assure
1502       /// that the intervals are mergeable in advance.
1503       private static void combine (MInterval head, MInterval tail)
1504       {
1505         M17n.DebugPrint ("combining {0} through {1}", head, tail);
1506
1507         head.update_from_to ();
1508         tail.update_from_to ();
1509         int from = head.From;
1510         int to = tail.To;
1511
1512         // The nearest common parent of HEAD and TAIL.
1513         MInterval root;
1514         for (root = head; root.To + root.RightLength < to;
1515              root = root.Parent);
1516         
1517         M17n.DebugPrint (" with common root {0}\n", root);
1518
1519         if (from < root.From)
1520           {
1521             MInterval prev = root.Prev;
1522
1523             while (true)
1524               {
1525                 M17n.DebugPrint ("merging {0}\n", prev);
1526                 prev.vacate_node (prev.Left, root);
1527                 if (prev == head)
1528                   break;
1529                 if (prev.Left != null)
1530                   prev = prev.Left.RightMost;
1531                 else
1532                   prev = prev.Parent;
1533               }
1534             root.update_from_to ();
1535           }
1536         if (root.To < to)
1537           {
1538             MInterval next = root.Next;
1539
1540             while (true)
1541               {
1542                 M17n.DebugPrint ("merging {0}\n", next);
1543                 next.vacate_node (next.Right, root);
1544                 if (next == tail)
1545                   break;
1546                 if (next.Right != null)
1547                   next = next.Right.LeftMost;
1548                 else
1549                   next = next.Parent;
1550               }
1551             root.update_from_to ();
1552           }
1553       }
1554
1555       public void MergeAfterChange (int start, int end)
1556       {
1557         update_from_to ();
1558
1559         MInterval head = find_head (start), i = head;
1560         MInterval tail = start < end ? find_tail (end) : head;
1561
1562         if (tail.To < Length)
1563           tail = tail.Next;
1564
1565         if (start == head.From && start > 0)
1566           {
1567             MInterval prev = head.Prev;
1568             if (head.mergeable (prev))
1569               head = prev;
1570           }
1571         M17n.DebugPrint ("merge between {0} and {1}\n", head, tail);
1572         while (i != tail)
1573           {
1574             MInterval next = i.Next;
1575
1576             if (! i.mergeable (next))
1577               {
1578                 if (head != i)
1579                   combine (head, i);
1580                 head = next;
1581               }
1582             i = next;
1583           }
1584         if (head != i)
1585           combine (head, i);
1586       }
1587
1588       public void Pop (int start, int end)
1589       {
1590         update_from_to ();
1591         M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this);
1592         if (start < From)
1593           {
1594             if (end <= From)
1595               {
1596                 Left.Pop (start, end);
1597                 return;
1598               }
1599             Left.Pop (start, From);
1600             start = From;
1601           }
1602         if (end > To)
1603           {
1604             if (start >= To)
1605               {
1606                 Right.Pop (start, end);
1607                 return;
1608               }
1609             Right.Pop (To, end);
1610             end = To;
1611           }
1612
1613         if (! Stack.IsEmpty)
1614           {
1615             if (isSensitive)
1616               Stack.Clear ();
1617             else
1618               {
1619                 if (start > From)
1620                   divide_left (start);
1621                 if (end < To)
1622                   divide_right (end);
1623                 Stack.Pop ();
1624               }
1625           }
1626       }
1627
1628       public void PopSensitive (int start, int end)
1629       {
1630         update_from_to ();
1631         MInterval head = find_head (start);
1632         MInterval tail = find_tail (end);
1633         Pop (head.From, tail.To);
1634       }
1635
1636       public override string ToString ()
1637       {
1638         string str = String.Format ("#{0}({1} {2} {3} [", ID, Length, From, To);
1639         bool first = true;
1640         foreach (MPlist p in Stack)
1641           {
1642             if (first)
1643               {
1644                 str += ((MProperty) p.Val).Val;
1645                 first = false;
1646               }
1647             else
1648               str += " " + ((MProperty) p.Val).Val;
1649           }
1650         return (str + "])");
1651       }
1652
1653       private void DumpOne (bool with_prop, bool newline, bool force)
1654       {
1655         if (force || M17n.debug)
1656           {
1657             Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1658             if (with_prop && ! Stack.IsEmpty)
1659               {
1660                 string prepend = " [";
1661                 foreach (MPlist p in Stack)
1662                   {
1663                     Console.Write (prepend + ((MProperty) p.Val).Val);
1664                     prepend = " ";
1665                   }
1666                 Console.Write ("]");
1667               }
1668             Console.Write (")");
1669             if (newline)
1670               Console.WriteLine ();
1671             if (Length <= 0)
1672               throw new Exception ("Invalid interval length");
1673           }
1674       }
1675
1676       public void Dump () { Dump (false); }
1677
1678       public void Dump (bool force)
1679       {
1680         if (force || M17n.debug)
1681           {
1682             update_from_to ();
1683
1684             if (Left != null)
1685               Left.Dump (force);
1686             if (From > 0)
1687               Console.Write (" ");
1688             DumpOne (true, false, force);
1689             if (Right != null)
1690               Right.Dump (force);
1691           }
1692       }
1693
1694       private int Depth {
1695         get { return (Parent == null ? 0 : Parent.Depth + 1); }
1696       }
1697
1698       public void DumpNested (bool force)
1699       {
1700         DumpNested ("  " + Key.ToString () + ":", force);
1701       }
1702
1703       public void DumpNested (string indent, bool force)
1704       {
1705         if (force || M17n.debug)
1706           {
1707             int indent_type = (Parent == null ? 1
1708                                : Parent.Left == this ? 0 : 2);
1709
1710             update_from_to ();
1711             if (Left != null)
1712               {
1713                 if (indent_type <= 1)
1714                   Left.DumpNested (indent + "  ", force);
1715                 else
1716                   Left.DumpNested (indent + "| ", force);
1717               }
1718             Console.Write (indent);
1719             if (indent_type == 0)
1720               Console.Write (".-");
1721             else if (indent_type == 2)
1722               Console.Write ("`-");
1723             DumpOne (true, true, true);
1724             if (Right != null)
1725               {
1726                 if (indent_type >= 1)
1727                   Right.DumpNested (indent + "  ", force);
1728                 else
1729                   Right.DumpNested (indent + "| ", force);
1730               }
1731           }
1732       }
1733     }
1734
1735     private class MTextEnum : IEnumerator
1736     {
1737       private MText mt;
1738       private int pos = -1;
1739
1740       public MTextEnum (MText mt)
1741         {
1742           this.mt = mt;
1743         }
1744
1745       public bool MoveNext ()
1746       {
1747         pos++;
1748         return (pos < mt.nchars);
1749       }
1750
1751       public void Reset ()
1752       {
1753         pos = -1;
1754       }
1755
1756       public object Current
1757       {
1758         get {
1759           //if (pos < 0 || pos >= mt.nchars)
1760           //throw new InvalidOperationException ();
1761           return mt[pos];
1762         }
1763       }
1764     }
1765   }
1766 }