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