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