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             root = (MInterval) p.Val;
 522
 523           if (root.isSensitive)
 524             root.PopSensitive (from, to);
 525           root.Push (from, to, prop);
 526           root.MergeAfterChange (from, to);
 527           root.Balance ();
 528         }
 529     }
 530
 531     public void PopProp (int from, int to, MSymbol key)
 532     {
 533       if (from < 0)
 534         {
 535           if (default_property == null)
 536             return;
 537           MPlist p = default_property.Find (key);
 538
 539           if (p != null)
 540             p.Pop ();
 541         }
 542       else
 543         {
 544           if (check_range (from, to, true))
 545             return;
 546
 547           MPlist p = intervals.Find (key);
 548
 549           if (p != null)
 550             {
 551               MInterval root = (MInterval) p.Val;
 552               if (root.isSensitive)
 553                 root.PopSensitive (from, to);
 554               else
 555                 root.Pop (from, to);
 556               root = (MInterval) p.Val;
 557               if (M17n.debug)
 558                 DumpPropNested ();
 559               root.MergeAfterChange (from, to);
 560               root.Balance ();
 561             }
 562         }
 563     }
 564
 565     public void DumpProp ()
 566     {
 567       Console.Write ("(");
 568       foreach (MPlist p in intervals)
 569         ((MInterval) p.Val).Dump (true);
 570       Console.WriteLine (")");
 571     }
 572
 573     public void DumpPropNested ()
 574     {
 575       Console.WriteLine ("total length = {0}", Length);
 576       foreach (MPlist p in intervals)
 577         ((MInterval) p.Val).DumpNested (true);
 578     }
 579
 580     private class MInterval
 581     {
 582       // position: 0   1   2   3   4   5   6   7
 583       //           | A | B | C | D | E   F | G |
 584       // interval  |---|---|---|<->|-------|---|
 585       //           |---|<->|---|   |<----->|---|
 586       //           |<->|   |<->|           |<->|
 587       //
 588       //                      [7 (3 4)]
 589       //              [3 (1 2)]       [3 (4 6)]
 590       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
 591       //
 592       private static int count = 0;
 593       private int ID;
 594       private int Length;
 595       private int From, To;
 596       private MSymbol Key;
 597       private MPlist Stack;
 598       private MInterval Left, Right, Parent;
 599       private MText mtext;
 600
 601       public MInterval (MSymbol key, MText mt, int length)
 602       {
 603         if (length <= 0)
 604           throw new Exception ("Invalid interval length");
 605         Key = key;
 606         mtext = mt;
 607         Length = length;
 608         Stack = new MPlist ();
 609         ID = count++;
 610       }
 611
 612       public MInterval (MSymbol key, MText mt)
 613       {
 614         Key = key;
 615         mtext = mt;
 616         Length = mt.sb.Length;
 617         From = 0;
 618         To = Length;
 619         Stack = new MPlist ();
 620         ID = count++;
 621       }
 622
 623       /// POS must be smaller than Length;
 624       public MProperty Get (int pos)
 625       {
 626         MInterval i = find_head (pos);
 627
 628         return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val);
 629       }
 630
 631       /// POS must be smaller than Length;
 632       public MProperty Get (int pos, out MProperty[] array)
 633       {
 634         MInterval i = find_head (pos);
 635
 636         if (i.To == pos)
 637           i = i.Next;
 638         if (i.Stack.IsEmpty)
 639           {
 640             array = null;
 641             return null;
 642           }
 643         array = new MProperty[i.Stack.Count];
 644
 645         int idx;
 646         MPlist p;
 647         for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
 648           array[idx] = (MProperty) p.Val;
 649         return array[0];
 650       }
 651
 652       private MInterval (MSymbol key, MText mt, int length, MPlist stack)
 653       {
 654         Key = key;
 655         mtext = mt;
 656         Length = length;
 657         From = 0;
 658         To = Length;
 659         Stack = stack == null ? new MPlist () : stack.Clone ();
 660         ID = count++;
 661       }
 662
 663       private bool isRearSticky
 664       {
 665         get { return MProperty.HasFlags (Key, MProperty.Flags.RearSticky) ; }
 666       }
 667
 668       private bool isFrontSticky
 669       {
 670         get { return MProperty.HasFlags (Key, MProperty.Flags.FrontSticky) ; }
 671       }
 672
 673       public bool isSensitive
 674       {
 675         get { return MProperty.HasFlags (Key, MProperty.Flags.Sensitive) ; }
 676       }
 677
 678       public bool isFrontSensitive
 679       {
 680         get { return MProperty.HasFlags (Key,
 681                                          MProperty.Flags.FrontSensitive) ; }
 682       }
 683
 684       public bool isRearSensitive
 685       {
 686         get { return MProperty.HasFlags (Key,
 687                                          MProperty.Flags.RearSensitive) ; }
 688       }
 689
 690       private void update_from_to ()
 691       {
 692         if (Parent == null)
 693           {
 694             From = LeftLength;
 695             To = Length - RightLength;
 696           }
 697         else if (Parent.Left == this)
 698           {
 699             From = Parent.From - Length + LeftLength;
 700             To = Parent.From - RightLength;
 701           }
 702         else
 703           {
 704             From = Parent.To + LeftLength;
 705             To = Parent.To + Length - RightLength;
 706           }
 707       }
 708
 709       private int LeftLength
 710       {
 711         get { return (Left == null ? 0 : Left.Length); }
 712       }
 713
 714       private int RightLength
 715       {
 716         get { return (Right == null ? 0 : Right.Length); }
 717       }
 718
 719       private MInterval LeftMost
 720       {
 721         get {
 722           update_from_to ();
 723           if (Left == null)
 724             return this;
 725           return Left.LeftMost;
 726         }
 727       }
 728
 729       private MInterval RightMost
 730       {
 731         get {
 732           update_from_to ();
 733           if (Right == null)
 734             return this;
 735           return Right.RightMost;
 736         }
 737       }
 738
 739       private MInterval Prev {
 740         get {
 741           MInterval i;
 742
 743           if (Left != null)
 744             {
 745               for (i = Left; i.Right != null; i = i.Right)
 746                 i.update_from_to ();
 747               i.update_from_to ();
 748             }
 749           else
 750             {
 751               MInterval child = this;
 752               for (i = Parent; i != null && i.Left == child;
 753                    child = i, i = i.Parent);
 754             }
 755           return i;
 756         }
 757       }
 758
 759       private MInterval Next {
 760         get {
 761           MInterval i;
 762
 763           if (Right != null)
 764             {
 765               for (i = Right; i.Left != null; i = i.Left)
 766                 i.update_from_to ();
 767               i.update_from_to ();
 768             }
 769           else
 770             {
 771               MInterval child = this;
 772               for (i = Parent; i != null && i.Right == child;
 773                    child = i, i = i.Parent);
 774             }
 775           return i;
 776         }
 777       }
 778
 779       private MInterval find_head (int pos)
 780       {
 781         update_from_to ();
 782         if (pos < From)
 783           return Left.find_head (pos);
 784         if (pos >= To)
 785           return Right.find_head (pos);
 786         return this;
 787       }
 788
 789       private MInterval find_tail (int pos)
 790       {
 791         update_from_to ();
 792         if (pos <= From)
 793           return Left.find_tail (pos);
 794         if (pos > To)
 795           return Right.find_tail (pos);
 796         return this;
 797       }
 798
 799       private bool mergeable (MInterval i)
 800       {
 801         MPlist p1, p2;
 802
 803         if (Stack.IsEmpty && i.Stack.IsEmpty)
 804           return true;
 805         if (isSensitive)
 806           return false;
 807         for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
 808              p1 = p1.Next, p2 = p2.Next)
 809           if (p1.Val != p2.Val)
 810             return false;
 811         return (p1.IsEmpty && p2.IsEmpty);
 812       }
 813
 814       //      p-. or .-p              p-. or .-p
 815       //       .-this-.                .-right-.
 816       //    left   .-right-.  ->   .-this-.    c2
 817       //          c1       c2    left     c1
 818       private MInterval promote_right ()
 819       {
 820         MInterval c1 = Right.Left;
 821
 822         // Update Parent.
 823         if (Parent == null)
 824           mtext.intervals.Put (Key, Right);
 825         else if (Parent.Left == this)
 826           Parent.Left = Right;
 827         else
 828           Parent.Right = Right;
 829
 830         // Update Right.
 831         Right.Parent = Parent;
 832         Right.Left = this;
 833         Right.Length += LeftLength + (To - From);
 834
 835         // Update this.
 836         Parent = Right;
 837         Right = c1;
 838         Length = LeftLength + (To - From) + RightLength;
 839
 840         // Update C1 if necessary.
 841         if (c1 != null)
 842           c1.Parent = this;
 843
 844         Parent.update_from_to ();
 845         return Parent;
 846       }
 847
 848       //      p-. or .-p              p-. or .-p
 849       //       .-this-.                .-left-.
 850       //  .-left-.  .-right-.  ->     c1    .-this-.
 851       // c1      c2                        c2     right
 852       private MInterval promote_left ()
 853       {
 854         MInterval c2 = Left.Right;
 855
 856         // Update Parent.
 857         if (Parent == null)
 858           mtext.intervals.Put (Key, Left);
 859         else if (Parent.Left == this)
 860           Parent.Left = Left;
 861         else
 862           Parent.Right = Left;
 863
 864         // Update Left.
 865         Left.Parent = Parent;
 866         Left.Right = this;
 867         Left.Length += (To - From) + RightLength;
 868
 869         // Update this.
 870         Parent = Left;
 871         Left = c2;
 872         Length = LeftLength + (To - From) + RightLength;
 873
 874         // Update C2 if necessary.
 875         if (c2 != null)
 876           c2.Parent = this;
 877
 878         Parent.update_from_to ();
 879         return Parent;
 880       }
 881
 882       public MInterval Balance ()
 883       {
 884         MInterval i = this;
 885
 886         update_from_to ();
 887         while (true)
 888           {
 889             //       .-this-.
 890             //  .-left-.  .-right-.
 891             // c1     c2  c3      c4
 892             int diff = i.LeftLength - i.RightLength;
 893             int new_diff;
 894
 895             if (diff > 0)
 896               {
 897                 new_diff = (i.Length - i.LeftLength
 898                             + i.Left.RightLength - i.Left.LeftLength);
 899                 if (Math.Abs (new_diff) >= diff)
 900                   break;
 901                 M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
 902                 i = i.promote_left ();
 903                 M17n.DebugPrint ("done\n");
 904                 i.Right.Balance ();
 905               }
 906             else if (diff < 0)
 907               {
 908                 new_diff = (i.Length - i.RightLength
 909                             + i.Right.LeftLength - i.Right.RightLength);
 910                 if (Math.Abs (new_diff) >= diff)
 911                   break;
 912                 M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
 913                 i = i.promote_right ();
 914                 i.Left.Balance ();
 915               }
 916             else
 917               break;
 918           }
 919         return i;
 920       }
 921
 922       public MInterval Copy (MText mt, int start, int end)
 923       {
 924         MInterval copy, left_copy = null, right_copy = null;
 925
 926         update_from_to ();
 927
 928         if (start < From)
 929           {
 930             if (end <= From)
 931               return Left.Copy (mt, start, end);
 932             left_copy = Left.Copy (mt, start, From);
 933           }
 934         if (end > To)
 935           {
 936             if (start >= To)
 937               return Right.Copy (mt, start, end);
 938             right_copy = Right.Copy (mt, To, end);
 939           }
 940
 941         copy = new MInterval (Key, null, end - start, Stack);
 942         copy.mtext = mt;
 943         if (isSensitive && (From < start || end < To))
 944           copy.Stack.Clear ();
 945         if (left_copy != null)
 946           {
 947             copy.Left = left_copy;
 948             left_copy.Parent = copy;
 949           }
 950         if (right_copy != null)
 951           {
 952             copy.Right = right_copy;
 953             right_copy.Parent = copy;
 954           }
 955         return copy;
 956       }
 957
 958       public MInterval Copy (MText mt, int start, int end,
 959                              bool first, bool last)
 960       {
 961         MInterval copy = Copy (mt, start, end);
 962         MInterval head = find_head (start);
 963         MInterval tail = find_tail (end);
 964
 965         if (! head.Stack.IsEmpty
 966             && (isSensitive && head.From < start
 967                 || isFrontSensitive && ! first))
 968           {
 969             head = copy.find_head (0);
 970             head.Stack.Clear ();
 971           }
 972         if (! tail.Stack.IsEmpty
 973             && (isSensitive && end < head.To
 974                 || isRearSensitive && ! last))
 975           {
 976             tail = copy.find_tail (copy.Length);
 977             tail.Stack.Clear ();
 978           }
 979         M17n.DebugPrint ("Copied: {0}\n", copy);
 980         return copy;
 981       }
 982
 983       //  this-.   ==>   this-.
 984       //     right          newright-.
 985       //                            right
 986       private MInterval divide_right (int pos)
 987       {
 988         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
 989
 990         M17n.DebugPrint ("divide-right({0}) at {1}\n", pos, this);
 991         To = pos;
 992         if (Right != null)
 993           {
 994             interval.Right = Right;
 995             Right.Parent = interval;
 996             interval.Length += Right.Length;
 997           }
 998         interval.Parent = this;
 999         Right = interval;
1000         return interval;
1001       }
1002
1003       //    .-this   ==>       .-this
1004       //  left             .-newleft
1005       //                 left
1006       private MInterval divide_left (int pos)
1007       {
1008         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
1009
1010         M17n.DebugPrint ("divide-left({0}) at {1}\n", pos, this);
1011         From = pos;
1012         if (Left != null)
1013           {
1014             interval.Left = Left;
1015             Left.Parent = interval;
1016             interval.Length += Left.Length;
1017           }
1018         interval.Parent = this;
1019         Left = interval;
1020         return interval;
1021       }
1022
1023       private void set_mtext (MText mt)
1024       {
1025         mtext = mt;
1026         if (Left != null)
1027           Left.set_mtext (mt);
1028         if (Right != null)
1029           Right.set_mtext (mt);
1030       }
1031
1032       private void enlarge (int len)
1033       {
1034         Length += len;
1035         To += len;
1036         for (MInterval prev = this, i = this.Parent; i != null;
1037              prev = i, i = i.Parent)
1038           {
1039             i.Length += len;
1040             if (prev == i.Left)
1041               {
1042                 i.From += len;
1043                 i.To += len;;
1044               }
1045           }
1046       }
1047
1048       private int graft_forward (MInterval interval, int start, int end)
1049       {
1050         int len;
1051
1052         if (! Stack.IsEmpty && isRearSticky)
1053           len = end - start;
1054         else if (interval == null)
1055           len = Stack.IsEmpty ? end - start : 0;
1056         else
1057           {
1058             MInterval i = interval.find_head (start);
1059
1060             len = 0;
1061             if (Stack.IsEmpty
1062                 && (isFrontSensitive || (isSensitive && i.From < start)))
1063               {
1064                 M17n.DebugPrint (" forward grafting {0}", i);
1065                 if (i.To < end)
1066                   len = i.To - start;
1067                 else
1068                   len = end - start;
1069                 i = i.Next;
1070               }
1071             while (i != null && i.From < end && mergeable (i))
1072               {
1073                 M17n.DebugPrint (" forward grafting {0}", i);
1074                 len += i.To - i.From;
1075                 if (i.From < start)
1076                   len -= start - i.From;
1077                 if (i.To >= end)
1078                   {
1079                     len -= i.To - end;
1080                     break;
1081                   }
1082                 i = i.Next;
1083               }
1084           }
1085
1086         M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1087         if (len > 0)
1088           enlarge (len);
1089         return len;
1090       }
1091
1092       private int graft_backward (MInterval interval, int start, int end)
1093       {
1094         int len;
1095
1096         if (! Stack.IsEmpty && isFrontSticky)
1097           len = end - start;
1098         else if (interval == null)
1099           len = Stack.IsEmpty ? end - start : 0;
1100         else
1101           {
1102             MInterval i = interval.find_tail (end);
1103
1104             len = 0;
1105             if (Stack.IsEmpty
1106                 && (isRearSensitive || (isSensitive && end < i.To)))
1107               {
1108                 M17n.DebugPrint (" backward grafting {0}", i);
1109                 if (i.From <= start)
1110                   len = end - start;
1111                 else
1112                   len = end - i.From;
1113                 i = i.Prev;
1114               }
1115             while (i != null && i.To <= start && mergeable (i))
1116               {
1117                 M17n.DebugPrint (" backward grafting {0}", i);
1118                 len += i.To - i.From;
1119                 if (end < i.To)
1120                   len -= i.To - end;
1121                 if (i.From <= start)
1122                   {
1123                     len -= start - i.From;
1124                     break;
1125                   }
1126                 i = i.Prev;
1127               }
1128           }
1129
1130         M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
1131         if (len > 0)
1132           enlarge (len);
1133         return len;
1134       }
1135
1136       public void Insert (int pos, MInterval interval, int start, int end)
1137       {
1138         update_from_to ();
1139
1140         M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}",
1141                          start, end, pos, this);
1142
1143         if (pos < From)
1144           Left.Insert (pos, interval, start, end);
1145         else if (pos == From)
1146           {
1147             MInterval prev = Left != null ? Prev : null;
1148
1149             if (isFrontSensitive)
1150               Stack.Clear ();
1151             if (prev != null && isRearSensitive)
1152               prev.Stack.Clear ();
1153             if (prev != null && isRearSticky && ! prev.Stack.IsEmpty)
1154               {
1155                 prev.enlarge (end - start);
1156                 M17n.DebugPrint (" done\n");
1157                 return;
1158               }
1159             if (isFrontSticky && ! Stack.IsEmpty)
1160               {
1161                 enlarge (end - start);
1162                 M17n.DebugPrint (" done\n");
1163                 return;
1164               }
1165             bool front_grafted = false, rear_grafted = false;
1166             int grafted;
1167             if (prev != null
1168                 && (grafted = prev.graft_forward (interval, start, end)) > 0)
1169               {
1170                 start += grafted;
1171                 if (start == end)
1172                   {
1173                     M17n.DebugPrint (" done\n");
1174                     return;
1175                   }
1176                 front_grafted = true;
1177               }
1178             if ((grafted = graft_backward (interval, start, end)) > 0)
1179               {
1180                 end -= grafted;
1181                 if (start == end)
1182                   {
1183                     M17n.DebugPrint (" done\n");
1184                     return;
1185                   }
1186                 rear_grafted = true;
1187               }
1188
1189             if (interval != null)
1190               interval = interval.Copy (mtext, start, end,
1191                                         (front_grafted
1192                                          || (prev == null && start == 0)),
1193                                         rear_grafted);
1194             else
1195               interval = new MInterval (Key, mtext, end - start, null);
1196
1197             MInterval i;
1198             if (Left != null)
1199               {
1200                 //    .-this-.   ==>          .-this-.
1201                 // left-.                 .-left-.
1202                 //    child                     child-.
1203                 //                                 interval
1204                 i = Left.RightMost;
1205                 i.Right = interval;
1206               }
1207             else
1208               {
1209                 Left = interval;
1210                 i = this;
1211               }
1212             interval.Parent = i;
1213             for (; i != null; i = i.Parent)
1214               i.Length += interval.Length;
1215           }
1216         else if (pos < To)
1217           {
1218             if (! Stack.IsEmpty)
1219               {
1220                 if (isSensitive)
1221                   Stack.Clear ();
1222                 else if (isFrontSticky || isRearSticky)
1223                   {
1224                     enlarge (end - start);
1225                     return;
1226                   }
1227               }
1228             bool front_grafted = false, rear_grafted = false;
1229             int grafted;
1230             if ((grafted = graft_forward (interval, start, end)) > 0)
1231               {
1232                 start += grafted;
1233                 if (start == end)
1234                   {
1235                     M17n.DebugPrint (" done\n");
1236                     return;
1237                   }
1238                 front_grafted = true;
1239                 pos += grafted;
1240               }
1241             if ((grafted = graft_backward (interval, start, end)) > 0)
1242               {
1243                 end -= grafted;
1244                 if (start == end)
1245                   {
1246                     M17n.DebugPrint (" done\n");
1247                     return;
1248                   }
1249                 rear_grafted = true;
1250               }
1251             if (interval != null)
1252               interval = interval.Copy (mtext, start, end,
1253                                         front_grafted, rear_grafted);
1254             else
1255               interval = new MInterval (Key, mtext, end - start, null);
1256
1257             divide_right (pos);
1258             Right.Left = interval;
1259             interval.Parent = Right;
1260             for (MInterval i = Right; i != null; i = i.Parent)
1261               i.Length += interval.Length;
1262           }
1263         else if (pos == To)
1264           {
1265             MInterval next = Right != null ? Next : null;
1266
1267             if (isRearSensitive)
1268               Stack.Clear ();
1269             if (next != null && isFrontSensitive)
1270               next.Stack.Clear ();
1271             if (isRearSticky && ! Stack.IsEmpty)
1272               {
1273                 enlarge (end - start);
1274                 M17n.DebugPrint (" done by enlarging this\n");
1275                 return;
1276               }
1277             if (next != null && isFrontSticky && ! next.Stack.IsEmpty)
1278               {
1279                 M17n.DebugPrint (" next is {0}\n", next);
1280                 next.enlarge (end - start);
1281                 M17n.DebugPrint (" done by enlarging next\n");
1282                 return;
1283               }
1284             bool front_grafted = false, rear_grafted = false;
1285             int grafted;
1286             if (next != null
1287                 && (grafted = next.graft_backward (interval, start, end)) > 0)
1288               {
1289                 end -= grafted;
1290                 if (start == end)
1291                   {
1292                     M17n.DebugPrint (" done\n");
1293                     return;
1294                   }
1295                 rear_grafted = true;
1296               }
1297             if ((grafted = graft_forward (interval, start, end)) > 0)
1298               {
1299                 start += grafted;
1300                 if (start == end)
1301                   {
1302                     M17n.DebugPrint (" done\n");
1303                     return;
1304                   }
1305                 front_grafted = true;
1306               }
1307             if (interval != null)
1308               interval = interval.Copy (mtext, start, end,
1309                                         front_grafted,
1310                                         (rear_grafted
1311                                          || (next == null && end < interval.mtext.Length)));
1312             else
1313               interval = new MInterval (Key, mtext, end - start, null);
1314
1315             MInterval i;
1316             if (Right != null)
1317               {
1318                 //    .-this-.   ==>          .-this-.
1319                 //         .-right                 .-right
1320                 //     child                  .-child
1321                 //                        interval
1322
1323                 i = Right.LeftMost;
1324                 i.Left = interval;
1325               }
1326             else
1327               {
1328                 Right = interval;
1329                 i = this;
1330               }
1331             interval.Parent = i;
1332             for (; i != null; i = i.Parent)
1333               i.Length += interval.Length;
1334           }
1335         else                    // (pos > To)
1336           Right.Insert (pos, interval, start, end);
1337         M17n.DebugPrint (" done\n");
1338       }
1339
1340       private void vacate_node (MInterval interval)
1341       {
1342         vacate_node (interval, null);
1343       }
1344
1345       private void vacate_node (MInterval interval, MInterval stop)
1346       {
1347         if (interval != null)
1348           M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
1349         else
1350           M17n.DebugPrint ("vacate #{0} to null\n", ID);
1351         if (interval != null)
1352           interval.Parent = Parent;
1353         if (Parent == null)
1354           {
1355             if (mtext != null)
1356               mtext.intervals.Put (Key, interval);
1357           }
1358         else
1359           {
1360             if (this == Parent.Right)
1361               Parent.Right = interval;
1362             else
1363               Parent.Left = interval;
1364
1365             int diff = Length;
1366             if (interval != null)
1367               diff -= interval.Length;
1368             for (MInterval i = Parent; i != stop; i = i.Parent)
1369               i.Length -= diff;
1370           }
1371       }
1372
1373       public void Delete (int start, int end)
1374       {
1375         update_from_to ();
1376         M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this);
1377
1378         bool front_checked = false;
1379         bool rear_checked = false;
1380
1381         if (start < From)
1382           {
1383             if (end <= From)
1384               {
1385                 if (end == From && isFrontSensitive)
1386                   Stack.Clear ();
1387                 Left.Delete (start, end);
1388                 return;
1389               }
1390             if (isSensitive)
1391               Stack.Clear ();
1392             Left.Delete (start, From);
1393             To -= From - start;
1394             end -= From - start;
1395             From = start;
1396             front_checked = true;
1397           }
1398         if (end > To)
1399           {
1400             if (start >= To)
1401               {
1402                 if (start == To && isRearSensitive)
1403                   Stack.Clear ();
1404                 Right.Delete (start, end);
1405                 return;
1406               }
1407             if (isSensitive)
1408               Stack.Clear ();
1409             Right.Delete (To, end);
1410             end = To;
1411             rear_checked = true;
1412           }
1413         if (start == From
1414             && ! front_checked
1415             && start > 0
1416             && isRearSensitive)
1417           Prev.Stack.Clear ();
1418         if (end == To
1419             && ! rear_checked
1420             && Next != null
1421             && isFrontSensitive)
1422           Next.Stack.Clear ();
1423         if (start == From && end == To)
1424           {
1425             if (Right == null)
1426               {
1427                 vacate_node (Left);
1428               }
1429             else
1430               {
1431                 if (Left != null)
1432                   {
1433                     MInterval i;
1434
1435                     for (i = Right; i.Left != null; i = i.Left)
1436                       i.Length += Left.Length;
1437                     i.Length += Left.Length;
1438                     i.Left = Left;
1439                     Left.Parent = i;
1440                   }
1441                 vacate_node (Right);
1442               }
1443           }
1444         else
1445           {
1446             int len = end - start;
1447
1448             if (isSensitive)
1449               Stack.Clear ();
1450             for (MInterval i = this; i != null; i = i.Parent)
1451               i.Length -= len;
1452           }
1453       }
1454
1455       public void Push (int start, int end, MProperty prop)
1456       {
1457         update_from_to ();
1458         M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this);
1459         if (start < From)
1460           {
1461             if (end <= From)
1462               {
1463                 Left.Push (start, end, prop);
1464                 return;
1465               }
1466             Left.Push (start, From, prop);
1467             start = From;
1468           }
1469         if (end > To)
1470           {
1471             if (start >= To)
1472               {
1473                 Right.Push (start, end, prop);
1474                 return;
1475               }
1476             Right.Push (To, end, prop);
1477             end = To;
1478           }
1479
1480         if (! Stack.IsEmpty && isSensitive)
1481           Stack.Clear ();
1482         if (start > From)
1483           divide_left (start);
1484         if (end < To)
1485           divide_right (end);
1486         Stack.Push (prop.key, prop);
1487       }
1488
1489       /// Combine intervals between HEAD and TAIL (both inclusive) to
1490       /// the common parent of HEAD and TAIL.  Callers should assure
1491       /// that the intervals are mergeable in advance.
1492       private static void combine (MInterval head, MInterval tail)
1493       {
1494         M17n.DebugPrint ("combining {0} through {1}", head, tail);
1495
1496         head.update_from_to ();
1497         tail.update_from_to ();
1498         int from = head.From;
1499         int to = tail.To;
1500
1501         // The nearest common parent of HEAD and TAIL.
1502         MInterval root;
1503         for (root = head; root.To + root.RightLength < to;
1504              root = root.Parent);
1505
1506         M17n.DebugPrint (" with common root {0}\n", root);
1507
1508         if (from < root.From)
1509           {
1510             MInterval prev = root.Prev;
1511
1512             while (true)
1513               {
1514                 M17n.DebugPrint ("merging {0}\n", prev);
1515                 prev.vacate_node (prev.Left, root);
1516                 if (prev == head)
1517                   break;
1518                 if (prev.Left != null)
1519                   prev = prev.Left.RightMost;
1520                 else
1521                   prev = prev.Parent;
1522               }
1523             root.update_from_to ();
1524           }
1525         if (root.To < to)
1526           {
1527             MInterval next = root.Next;
1528
1529             while (true)
1530               {
1531                 M17n.DebugPrint ("merging {0}\n", next);
1532                 next.vacate_node (next.Right, root);
1533                 if (next == tail)
1534                   break;
1535                 if (next.Right != null)
1536                   next = next.Right.LeftMost;
1537                 else
1538                   next = next.Parent;
1539               }
1540             root.update_from_to ();
1541           }
1542       }
1543
1544       public void MergeAfterChange (int start, int end)
1545       {
1546         update_from_to ();
1547
1548         MInterval head = find_head (start), i = head;
1549         MInterval tail = start < end ? find_tail (end) : head;
1550
1551         if (tail.To < Length)
1552           tail = tail.Next;
1553
1554         if (start == head.From && start > 0)
1555           {
1556             MInterval prev = head.Prev;
1557             if (head.mergeable (prev))
1558               head = prev;
1559           }
1560         M17n.DebugPrint ("merge between {0} and {1}\n", head, tail);
1561         while (i != tail)
1562           {
1563             MInterval next = i.Next;
1564
1565             if (! i.mergeable (next))
1566               {
1567                 if (head != i)
1568                   combine (head, i);
1569                 head = next;
1570               }
1571             i = next;
1572           }
1573         if (head != i)
1574           combine (head, i);
1575       }
1576
1577       public void Pop (int start, int end)
1578       {
1579         update_from_to ();
1580         M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this);
1581         if (start < From)
1582           {
1583             if (end <= From)
1584               {
1585                 Left.Pop (start, end);
1586                 return;
1587               }
1588             Left.Pop (start, From);
1589             start = From;
1590           }
1591         if (end > To)
1592           {
1593             if (start >= To)
1594               {
1595                 Right.Pop (start, end);
1596                 return;
1597               }
1598             Right.Pop (To, end);
1599             end = To;
1600           }
1601
1602         if (! Stack.IsEmpty)
1603           {
1604             if (isSensitive)
1605               Stack.Clear ();
1606             else
1607               {
1608                 if (start > From)
1609                   divide_left (start);
1610                 if (end < To)
1611                   divide_right (end);
1612                 Stack.Pop ();
1613               }
1614           }
1615       }
1616
1617       public void PopSensitive (int start, int end)
1618       {
1619         update_from_to ();
1620         MInterval head = find_head (start);
1621         MInterval tail = find_tail (end);
1622         while (! head.Stack.IsEmpty && head.From > 0)
1623           {
1624             MInterval prev = head.Prev;
1625
1626             if (prev.Stack.IsEmpty || head.Stack.Val != prev.Stack.Val)
1627               break;
1628             head = head.Prev;
1629           }
1630         while (! tail.Stack.IsEmpty && tail.To < mtext.Length)
1631           {
1632             MInterval next = tail.Next;
1633
1634             if (next.Stack.IsEmpty || tail.Stack.Val != next.Stack.Val)
1635               break;
1636             tail = tail.Next;
1637           }
1638         Pop (head.From, tail.To);
1639       }
1640
1641       public override string ToString ()
1642       {
1643         string str = String.Format ("#{0}({1} {2} {3} [", ID, Length, From, To);
1644         bool first = true;
1645         foreach (MPlist p in Stack)
1646           {
1647             if (first)
1648               {
1649                 str += ((MProperty) p.Val).Val;
1650                 first = false;
1651               }
1652             else
1653               str += " " + ((MProperty) p.Val).Val;
1654           }
1655         return (str + "])");
1656       }
1657
1658       private void DumpOne (bool with_prop, bool newline, bool force)
1659       {
1660         if (force || M17n.debug)
1661           {
1662             Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1663             if (with_prop && ! Stack.IsEmpty)
1664               {
1665                 string prepend = " [";
1666                 foreach (MPlist p in Stack)
1667                   {
1668                     Console.Write (prepend + ((MProperty) p.Val).Val);
1669                     prepend = " ";
1670                   }
1671                 Console.Write ("]");
1672               }
1673             Console.Write (")");
1674             if (newline)
1675               Console.WriteLine ();
1676             if (Length <= 0)
1677               throw new Exception ("Invalid interval length");
1678           }
1679       }
1680
1681       public void Dump () { Dump (false); }
1682
1683       public void Dump (bool force)
1684       {
1685         if (force || M17n.debug)
1686           {
1687             update_from_to ();
1688
1689             if (Left != null)
1690               Left.Dump (force);
1691             if (From > 0)
1692               Console.Write (" ");
1693             DumpOne (true, false, force);
1694             if (Right != null)
1695               Right.Dump (force);
1696           }
1697       }
1698
1699       private int Depth {
1700         get { return (Parent == null ? 0 : Parent.Depth + 1); }
1701       }
1702
1703       public void DumpNested (bool force)
1704       {
1705         DumpNested ("  " + Key.ToString () + ":", force);
1706       }
1707
1708       public void DumpNested (string indent, bool force)
1709       {
1710         if (force || M17n.debug)
1711           {
1712             int indent_type = (Parent == null ? 1
1713                                : Parent.Left == this ? 0 : 2);
1714
1715             update_from_to ();
1716             if (Left != null)
1717               {
1718                 if (indent_type <= 1)
1719                   Left.DumpNested (indent + "  ", force);
1720                 else
1721                   Left.DumpNested (indent + "| ", force);
1722               }
1723             Console.Write (indent);
1724             if (indent_type == 0)
1725               Console.Write (".-");
1726             else if (indent_type == 2)
1727               Console.Write ("`-");
1728             DumpOne (true, true, true);
1729             if (Right != null)
1730               {
1731                 if (indent_type >= 1)
1732                   Right.DumpNested (indent + "  ", force);
1733                 else
1734                   Right.DumpNested (indent + "| ", force);
1735               }
1736           }
1737       }
1738     }
1739
1740     private class MTextEnum : IEnumerator
1741     {
1742       private MText mt;
1743       private int pos = -1;
1744
1745       public MTextEnum (MText mt)
1746         {
1747           this.mt = mt;
1748         }
1749
1750       public bool MoveNext ()
1751       {
1752         pos++;
1753         return (pos < mt.nchars);
1754       }
1755
1756       public void Reset ()
1757       {
1758         pos = -1;
1759       }
1760
1761       public object Current
1762       {
1763         get {
1764           //if (pos < 0 || pos >= mt.nchars)
1765           //throw new InvalidOperationException ();
1766           return mt[pos];
1767         }
1768       }
1769     }
1770   }
1771 }