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