MText.cs

   1 using System;
   2 using System.Text;
   3 using System.Collections;
   4 using System.Collections.Generic;
   5 using M17N.Core;
   6
   7 namespace M17N.Core
   8 {
   9 #if false
  10   public enum MTextFormat
  11     {
  12       MTEXT_FORMAT_US_ASCII,
  13       MTEXT_FORMAT_UTF_8,
  14       MTEXT_FORMAT_UTF_16BE,
  15       MTEXT_FORMAT_UTF_16LE,
  16       MTEXT_FORMAT_UTF_32BE,
  17       MTEXT_FORMAT_UTF_32LE,
  18     }
  19 #endif
  20
  21   public class MTextProperty
  22   {
  23     internal MSymbol key;
  24     internal object val;
  25
  26     [FlagsAttribute]
  27     internal enum Flag : byte
  28       {
  29         None =          0,
  30         FrontSticky =   1,
  31         RearSticky =    2,
  32         Sensitive =     4
  33       };
  34     internal Flag flags;
  35
  36     public MSymbol Key { get { return key; } }
  37     public object Val { get { return val; } }
  38     public bool FrontSticky
  39     {
  40       get { return (flags & Flag.FrontSticky) != Flag.None; }
  41     }
  42     public bool RearSticky
  43     {
  44       get { return (flags & Flag.RearSticky) != Flag.None; }
  45     }
  46     public bool Sensitive
  47     {
  48       get { return (flags & Flag.Sensitive) != Flag.None; }
  49     }
  50
  51     public MTextProperty (MSymbol key, object val)
  52     {
  53       this.key = key;
  54       this.val = val;
  55       flags |= Flag.RearSticky;
  56     }
  57
  58     public MTextProperty (MSymbol key, object val,
  59                           bool front_sticky, bool rear_sticky, bool sensitive)
  60     {
  61       this.key = key;
  62       this.val = val;
  63       if (front_sticky)
  64         flags |= Flag.FrontSticky;
  65       if (rear_sticky)
  66         flags |= Flag.RearSticky;
  67       if (sensitive)
  68         flags |= Flag.Sensitive;
  69     }
  70   }
  71
  72   public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
  73   {
  74 #if false
  75     public enum MTextFormat format;
  76 #endif
  77     private StringBuilder sb;
  78     private int nchars;
  79     private int cache_pos;
  80     private int cache_idx;
  81     private MPlist intervals;
  82     private MPlist default_property;
  83     private bool read_only;
  84
  85     private static UTF8Encoding utf8 = new UTF8Encoding ();
  86
  87     private static int count_chars (String str)
  88     {
  89       int len = str.Length, n = 0;
  90
  91       for (int i = 0; i < len; i++, n++)
  92         if (surrogate_high_p (str[i]))
  93           i++;
  94       return n;
  95     }
  96
  97     private static int count_chars (StringBuilder str)
  98     {
  99       int len = str.Length, n = 0;
 100
 101       for (int i = 0; i < len; i++, n++)
 102         if (surrogate_high_p (str[i]))
 103           i++;
 104       return n;
 105     }
 106
 107     public MText ()
 108       {
 109         sb = new StringBuilder ();
 110         intervals = new MPlist ();
 111       }
 112
 113     public MText (byte[] str)
 114       {
 115         sb = new StringBuilder (utf8.GetString (str));
 116         nchars = count_chars (sb);
 117         intervals = new MPlist ();
 118       }
 119
 120     public MText (String str)
 121       {
 122         sb = new StringBuilder (str);
 123         nchars = count_chars (str);
 124         intervals = new MPlist ();
 125       }
 126
 127     public MText (StringBuilder str)
 128       {
 129         sb = str;
 130         nchars = count_chars (str);
 131         intervals = new MPlist ();
 132       }
 133
 134     public static MText operator+ (MText mt1, MText mt2)
 135     {
 136       MText mt = new MText ();
 137
 138       mt.sb.Append (mt1.sb);
 139       mt.sb.Append (mt2.sb);
 140       mt.nchars = mt1.nchars + mt2.nchars;
 141       return mt;
 142     }
 143
 144     // Public properties
 145     public bool ReadOnly { get { return read_only; } }
 146     public int Length { get { return nchars; } }
 147
 148     // Public methods
 149
 150     // for IEnumerable interface
 151     public IEnumerator GetEnumerator() { return new MTextEnum (this); }
 152
 153     // for IEquatable interface
 154     public bool Equals (MText other) { return this.sb.Equals (other.sb); }
 155
 156     // for IComparable interface
 157     public int CompareTo (MText other)
 158     {
 159       return this.sb.ToString ().CompareTo (other.sb.ToString ());
 160     }
 161
 162     public override String ToString () { return "\"" + sb.ToString () + "\""; }
 163
 164     private static bool surrogate_high_p (char c)
 165     {
 166       return (c >= 0xD800 && c < 0xDC00);
 167     }
 168
 169     private static bool surrogate_low_p (char c)
 170     {
 171       return (c >= 0xDC00 && c < 0xE000);
 172     }
 173
 174     private static int inc_idx (StringBuilder sb, int i)
 175     {
 176       return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
 177     }
 178
 179     private static int dec_idx (StringBuilder sb, int i)
 180     {
 181       return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
 182     }
 183
 184     private static int pos_to_idx (MText mt, int pos)
 185     {
 186       if (pos == mt.cache_pos)
 187         return mt.cache_idx;
 188
 189       int p, i;
 190       bool forward;
 191
 192       if (pos < mt.cache_pos)
 193         {
 194           if (mt.cache_pos == mt.cache_idx)
 195             return mt.cache_idx;
 196           if (pos < mt.cache_pos - pos)
 197             {
 198               p = i = 0;
 199               forward = true;
 200             }
 201           else
 202             {
 203               p = mt.cache_pos; i = mt.cache_idx;
 204               forward = false;
 205             }
 206         }
 207       else
 208         {
 209           if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
 210             return (mt.cache_idx + pos - mt.cache_pos);
 211           if (pos - mt.cache_pos < mt.nchars - pos)
 212             {
 213               p = mt.cache_pos; i = mt.cache_idx;
 214               forward = true;
 215             }
 216           else
 217             {
 218               p = mt.nchars; i = mt.sb.Length;
 219               forward = false;
 220             }
 221         }
 222       if (forward)
 223         for (; p < pos; i = inc_idx (mt.sb, i), p++);
 224       else
 225         for (; p > pos; i = dec_idx (mt.sb, i), p--);
 226       mt.cache_pos = p;
 227       mt.cache_idx = i;
 228       return i;
 229     }
 230
 231     private void insert (int pos, MText mt2, int from, int to)
 232     {
 233       int pos_idx = pos_to_idx (this, pos);
 234       int from_idx = pos_to_idx (mt2, from);
 235       int to_idx = pos_to_idx (mt2, to);
 236
 237       sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
 238       nchars += to - from;
 239
 240       foreach (MPlist plist in mt2.intervals)
 241         if (intervals.find (plist.Key) == null)
 242           intervals.push (plist.Key, new MInterval (plist.Key, this));
 243       foreach (MPlist plist in intervals)
 244         {
 245           MPlist p = mt2.intervals.find (plist.Key);
 246           MInterval interval;
 247
 248           if (p.IsEmpty)
 249             interval = new MInterval (plist.Key, to - from);
 250           else
 251             interval = ((MInterval) p.Val).copy (from, to);
 252           ((MInterval) plist.Val).insert (pos, interval);
 253         }
 254     }
 255
 256     public int this[int i]
 257     {
 258       set {
 259         i = pos_to_idx (this, i);
 260         if (value < 0x10000)
 261           {
 262             if (surrogate_high_p (sb[i]))
 263               sb.Remove (i, 1);
 264             sb[i] = (char) value;
 265           }
 266         else
 267           {
 268             char high = (char) (0xD800 + ((value - 0x10000) >> 10));
 269             char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
 270
 271             if (! surrogate_high_p (sb[i]))
 272               sb.Insert (i, 0);
 273             sb[i] = high;
 274             sb[i + 1] = low;
 275           }
 276       }
 277       get {
 278         i = pos_to_idx (this, i);
 279         return (surrogate_high_p (sb[i])
 280                 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
 281                 : sb[i]);
 282       }
 283     }
 284
 285     public MText dup ()
 286     {
 287       return (new MText (sb.ToString ()));
 288     }
 289
 290     public MText ins (int pos, MText mt)
 291     {
 292       insert (pos, mt, 0, mt.nchars);
 293       return this;
 294     }
 295
 296     public MText ins (int pos, MText mt, int from, int to)
 297     {
 298       insert (pos, mt, from, to);
 299       return this;
 300     }
 301
 302     public MText del (int from, int to)
 303     {
 304       sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
 305       nchars -= to - from;
 306
 307       foreach (MPlist plist in intervals)
 308         ((MInterval) plist.Val).delete (from, to);
 309       return this;
 310     }
 311
 312     public object get_prop (int pos, MSymbol key)
 313     {
 314       MInterval i = (MInterval) intervals.find (key).Val;
 315
 316       if (i == null)
 317         return null;
 318
 319       MTextProperty prop = i.get (pos);
 320       return (prop != null ? prop.Val : null);
 321     }
 322
 323     public object get_prop (int pos, MSymbol key, out MTextProperty prop)
 324     {
 325       MInterval i = (MInterval) intervals.find (key).Val;
 326
 327       if (i == null)
 328         return (prop = null);
 329       prop = i.get (pos);
 330       return (prop != null ? prop.Val : null);
 331     }
 332
 333     public object get_prop (int pos, MSymbol key, out MTextProperty[] array)
 334     {
 335       MInterval i = (MInterval) intervals.find (key).Val;
 336
 337       if (i == null)
 338         return (array = null);
 339       MTextProperty prop = i.get (pos, out array);
 340       return (prop != null ? prop.Val : null);
 341     }
 342
 343     public void push_prop (int from, int to, MSymbol key, object val)
 344     {
 345       push_prop (from, to, new MTextProperty (key, val));
 346     }
 347
 348     public void push_prop (int from, int to, MTextProperty prop)
 349     {
 350       if (from < 0)
 351         {
 352           if (default_property == null)
 353             default_property = new MPlist ();
 354           default_property.push (prop.key, prop.val);
 355         }
 356       else
 357         {
 358           MInterval root = (MInterval) intervals.find (prop.key).Val;
 359
 360           if (root == null)
 361             {
 362               root = new MInterval (prop.key, this);
 363               intervals.push (prop.key, root);
 364             }
 365           root.Push (from, to, prop);
 366         }
 367     }
 368
 369     private class MInterval
 370     {
 371       // position: 0   1   2   3   4   5   6   7
 372       //           | A | B | C | D | E   F | G |
 373       // interval  |---|---|---|<->|-------|---|
 374       //           |---|<->|---|   |<----->|---|
 375       //           |<->|   |<->|           |<->|
 376       //
 377       //                      [7 (3 4)]
 378       //              [3 (1 2)]       [3 (4 6)]
 379       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
 380       private int total_length;
 381       private int from, to;
 382       private MSymbol key;
 383       private MPlist stack;
 384       private MInterval left, right, parent;
 385       private MText mtext;
 386
 387       public MInterval (MSymbol key, int length)
 388       {
 389         if (length <= 0)
 390           throw new Exception ("Invalid interval length");
 391         this.key = key;
 392         total_length = length;
 393         stack = new MPlist ();
 394       }
 395
 396       public MInterval (MSymbol key, MText mt)
 397       {
 398         this.key = key;
 399         mtext = mt;
 400         total_length = mt.sb.Length;
 401         from = 0;
 402         to = total_length;
 403         stack = new MPlist ();
 404       }
 405
 406       public MTextProperty get (int pos)
 407       {
 408         MInterval i = find (pos);
 409
 410         return (i.stack.IsEmpty ? null : (MTextProperty) i.stack.Val);
 411       }
 412
 413       public MTextProperty get (int pos, out MTextProperty[] array)
 414       {
 415         MInterval i = find (pos);
 416
 417         if (i.stack.IsEmpty)
 418           {
 419             array = null;
 420             return null;
 421           }
 422         array = new MTextProperty[i.stack.Count];
 423
 424         int idx;
 425         MPlist p;
 426         for (idx = 0, p = i.stack; ! p.IsEmpty; idx++, p = p.Next)
 427           array[idx] = (MTextProperty) p.Val;
 428         return array[idx - 1];
 429       }
 430
 431       private MInterval (MSymbol key, int length, MPlist stack)
 432       {
 433         this.key = key;
 434         total_length = length;
 435         from = 0;
 436         to = total_length;
 437         this.stack = stack.Clone ();
 438       }
 439
 440       private void update_from_to ()
 441       {
 442         if (parent != null)
 443           {
 444             from = parent.from - total_length + LeftLength;
 445             to = parent.from - RightLength;
 446           }
 447       }
 448
 449       private int LeftLength
 450       {
 451         get { return (left == null ? 0 : left.total_length); }
 452       }
 453
 454       private int RightLength
 455       {
 456         get { return (right == null ? 0 : right.total_length); }
 457       }
 458
 459       private MInterval left_most_node
 460       {
 461         get { return (left == null ? this : left.left_most_node); }
 462       }
 463
 464       private MInterval right_most_node
 465       {
 466         get { return (right == null ? this : right.right_most_node); }
 467       }
 468
 469       private MInterval prev {
 470         get {
 471           MInterval i;
 472
 473           if (left != null)
 474             for (i = left; i.right != null; i = i.right);
 475           else
 476             for (i = parent; i != null && i.left == null; i = i.parent);
 477           return i;
 478         }
 479       }
 480
 481       private MInterval next {
 482         get {
 483           MInterval i;
 484
 485           if (right != null)
 486             for (i = right; i.left != null; i = i.left);
 487           else
 488             for (i = parent; i != null && i.right == null; i = i.parent);
 489           return i;
 490         }
 491       }
 492
 493       private MInterval find (int pos)
 494       {
 495         update_from_to ();
 496         if (pos < from)
 497           return left.find (pos);
 498         if (pos >= to)
 499           return right.find (pos);
 500         return this;
 501       }
 502
 503       //      p-. or .-p              p-. or .-p
 504       //       .-this-.                .-right-.
 505       //    left   .-right-.  ->   .-this-.    c2
 506       //          c1       c2    left     c1
 507       private MInterval promote_right ()
 508       {
 509         int right_length = right.total_length;
 510         MInterval c1;
 511
 512         if (parent == null)
 513           mtext.intervals.put (key, right);
 514         else if (parent.left == this)
 515           parent.left = right;
 516         else
 517           parent.right = right;
 518         right.parent = parent;
 519         c1 = right.left;
 520         right.left = this;
 521
 522         parent = right;
 523         right = c1;
 524         parent.total_length += total_length;
 525         total_length -= right_length;
 526         if (c1 != null)
 527           {
 528             c1.parent = this;
 529             parent.total_length -= c1.total_length;
 530             total_length += c1.total_length;
 531           }
 532         return parent;
 533       }
 534
 535       //      p-. or .-p              p-. or .-p
 536       //       .-this-.                .-left-.
 537       //  .-left-.  .-right-.  ->     c1    .-this-.
 538       // c1      c2                        c2     right
 539       private MInterval promote_left ()
 540       {
 541         int left_length = left.total_length;
 542         MInterval c1;
 543
 544         if (parent == null)
 545           mtext.intervals.put (key, left);
 546         else if (parent.left == this)
 547           parent.left = left;
 548         else
 549           parent.right = left;
 550         left.parent = parent;
 551         c1 = left.left;
 552         left.right = this;
 553
 554         parent = left;
 555         left = c1;
 556         parent.total_length += total_length;
 557         total_length -= left_length;
 558         if (c1 != null)
 559           {
 560             c1.parent = this;
 561             parent.total_length -= c1.total_length;
 562             total_length += c1.total_length;
 563           }
 564         return parent;
 565       }
 566
 567       private MInterval balance ()
 568       {
 569         MInterval i = this;
 570
 571         while (true)
 572           {
 573             //       .-this-.
 574             //  .-left-.  .-right-.
 575             // c1     c2  c3      c4
 576             int diff = i.LeftLength - i.RightLength;
 577             int new_diff;
 578
 579             if (diff > 0)
 580               {
 581                 new_diff = (i.total_length - i.LeftLength
 582                             + i.left.RightLength - i.left.LeftLength);
 583                 if (Math.Abs (new_diff) >= diff)
 584                   break;
 585                 i = i.promote_left ();
 586                 i.right.balance ();
 587               }
 588             else if (diff < 0)
 589               {
 590                 new_diff = (i.total_length - i.RightLength
 591                             + i.right.LeftLength - i.right.RightLength);
 592                 if (Math.Abs (new_diff) >= diff)
 593                   break;
 594                 i = i.promote_right ();
 595                 i.left.balance ();
 596               }
 597           }
 598         return i;
 599       }
 600
 601       public MInterval copy (int start, int end)
 602       {
 603         MInterval this_copy, left_copy = null, right_copy = null;
 604
 605         update_from_to ();
 606         if (start < from)
 607           {
 608             if (end <= from)
 609               return left.copy (start, end);
 610             left_copy = left.copy (start, from);
 611           }
 612         else if (end > to)
 613           {
 614             if (start >= to)
 615               return right.copy (start, end);
 616             right_copy = right.copy (to, end);
 617           }
 618         this_copy = new MInterval (key, end - start, stack);
 619         this_copy.left = left_copy;
 620         this_copy.right = right_copy;
 621
 622         return this_copy;
 623       }
 624
 625       //  this-.   ==>   this-.
 626       //     right          newright-.
 627       //                            right
 628       private MInterval divide_right (int pos)
 629       {
 630         update_from_to ();
 631
 632         MInterval interval = new MInterval (key, to - pos, stack);
 633
 634         total_length -= to - pos;
 635         if (right != null)
 636           {
 637             right.parent = interval;
 638             interval.total_length += right.total_length;
 639           }
 640         interval.parent = this;
 641         right = interval;
 642         return interval;
 643       }
 644
 645       //    .-this   ==>       .-this
 646       //  left             .-newleft
 647       //                 left
 648       private MInterval divide_left (int pos)
 649       {
 650         update_from_to ();
 651
 652         MInterval interval = new MInterval (key, to - pos, stack);
 653
 654         total_length -= to - pos;
 655         if (left != null)
 656           {
 657             left.parent = interval;
 658             interval.total_length += left.total_length;
 659           }
 660         interval.parent = this;
 661         left = interval;
 662         return interval;
 663       }
 664
 665       private void remove_properties (MTextProperty.Flag flags)
 666       {
 667         for (MPlist p = stack; ! p.IsEmpty;)
 668           {
 669             MTextProperty prop = (MTextProperty) p.Val;
 670
 671             if ((prop.flags & flags) == flags)
 672               p.pop ();
 673             else
 674               p = p.Next;
 675           }
 676       }
 677
 678       private void merge_properties (MPlist plist, MTextProperty.Flag flags)
 679       {
 680         if (left != null)
 681           left.merge_properties (plist, flags);
 682         if (right != null)
 683           right.merge_properties (plist, flags);
 684         for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 685           {
 686             MTextProperty prop = (MTextProperty) p.Val;
 687
 688             if ((prop.flags & flags) == flags
 689                 && stack.get (prop.Key) == null)
 690               stack.push (prop.key, prop);
 691           }
 692       }
 693
 694       public void insert (int pos, MInterval interval)
 695       {
 696         update_from_to ();
 697         if (pos < from || (pos == from && left == null && pos > 0))
 698           {
 699             prev.insert (pos, interval);
 700             return;
 701           }
 702         if (pos > to || (pos == to && right == null && next != null))
 703           {
 704             next.insert (pos, interval);
 705             return;
 706           }
 707         if (pos > from && pos < to)
 708           {
 709             remove_properties (MTextProperty.Flag.Sensitive);
 710             divide_right (pos).insert (pos, interval);
 711             return;
 712           }
 713         if (pos == from)
 714           {
 715             if (pos > 0)
 716               {
 717                 prev.remove_properties
 718                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
 719                 interval.merge_properties
 720                   (prev.stack, MTextProperty.Flag.RearSticky);
 721               }
 722             remove_properties
 723               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
 724             interval.merge_properties
 725               (stack, MTextProperty.Flag.FrontSticky);
 726
 727             // INTERVAL is ready to insert.
 728             //
 729             //    .-this-.   ==>          .-this-.
 730             // left-.                  left-.
 731             //     child                  .-interval
 732             //                         child
 733
 734             if (pos > 0)
 735               {
 736                 MInterval i = left.right_most_node;
 737
 738                 i.left = interval;
 739                 interval.parent = i;
 740                 for (; i != null; i = i.parent)
 741                   i.total_length += interval.total_length;
 742               }
 743             else
 744               {
 745                 left = interval;
 746
 747                 for (MInterval i = this; i != null; i = i.parent)
 748                   i.total_length += interval.total_length;
 749               }
 750           }
 751         else                    // pos == to
 752           {
 753             if (right != null)
 754               {
 755                 MInterval left_most = right.left_most_node;
 756
 757                 left_most.remove_properties
 758                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
 759                 interval.merge_properties
 760                   (stack, MTextProperty.Flag.FrontSticky);
 761               }
 762             remove_properties
 763               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
 764             interval.merge_properties
 765               (stack, MTextProperty.Flag.RearSticky);
 766
 767             // INTERVAL is ready to insert.
 768             //
 769             //    .-this-.   ==>          .-this-.
 770             //         .-right                 .-right
 771             //     child                  interval-.
 772             //                                    child
 773
 774             if (right != null)
 775               {
 776                 MInterval i = right.left_most_node;
 777
 778                 i.left = interval;
 779                 interval.parent = i;
 780                 for (; i != null; i = i.parent)
 781                   i.total_length += interval.total_length;
 782               }
 783             else
 784               {
 785                 right = interval;
 786
 787                 for (MInterval i = this; i != null; i = i.parent)
 788                   i.total_length += interval.total_length;
 789               }
 790           }
 791       }
 792
 793       private void update_parent (MInterval i)
 794       {
 795         if (parent == null)
 796           mtext.intervals.put (key, i);
 797         else
 798           {
 799             int diff;
 800
 801             if (parent.right == i)
 802               {
 803                 diff = parent.right.total_length - i.total_length;
 804                 parent.right = i;
 805               }
 806             else
 807               {
 808                 diff = parent.left.total_length - i.total_length;
 809                 parent.left = i;
 810               }
 811             for (i = parent; i != null; i = i.parent)
 812               i.total_length += diff;
 813           }
 814       }
 815
 816       public void delete (int start, int end)
 817       {
 818         update_from_to ();
 819         if (start < from)
 820           {
 821             if (end <= from)
 822               {
 823                 left.delete (start, end);
 824                 return;
 825               }
 826             left.delete (start, from);
 827             start = from;
 828           }
 829         else if (end > to)
 830           {
 831             if (start >= to)
 832               {
 833                 right.delete (start, end);
 834                 return;
 835               }
 836             right.delete (to, end);
 837             end = to;
 838           }
 839         if (start == from && end == to)
 840           {
 841             if (left == null)
 842               update_parent (right);
 843             else if (right == null)
 844               update_parent (left);
 845             else
 846               {
 847                 MInterval i;
 848
 849                 for (i = right; i.left != null; i = i.left)
 850                   i.total_length += left.total_length;
 851                 i.total_length += left.total_length;
 852                 i.left = left;
 853                 update_parent (right);
 854               }
 855           }
 856         else
 857           {
 858             int len = end - start;
 859
 860             for (MInterval i = this; i != null; i = i.parent)
 861               i.total_length -= len;
 862           }
 863       }
 864
 865       public MTextProperty Push (int start, int end, MTextProperty prop)
 866       {
 867         update_from_to ();
 868         if (start < from)
 869           {
 870             left.Push (start, end, prop);
 871             if (end <= from)
 872               return prop;
 873             start = from;
 874           }
 875         else if (end > to)
 876           {
 877             right.Push (start, end, prop);
 878             if (start >= to)
 879               return prop;
 880             end = to;
 881           }
 882
 883         if (start > from)
 884           divide_left (from);
 885         if (end < to)
 886           divide_right (end);
 887         stack.push (prop.key, prop);
 888         return prop;
 889       }
 890     }
 891
 892     private class MTextEnum : IEnumerator
 893     {
 894       private MText mt;
 895       private int pos = -1;
 896
 897       public MTextEnum (MText mt)
 898         {
 899           this.mt = mt;
 900         }
 901
 902       public bool MoveNext ()
 903       {
 904         pos++;
 905         return (pos < mt.nchars);
 906       }
 907
 908       public void Reset ()
 909       {
 910         pos = -1;
 911       }
 912
 913       public object Current
 914       {
 915         get {
 916           //if (pos < 0 || pos >= mt.nchars)
 917           //throw new InvalidOperationException ();
 918           return mt[pos];
 919         }
 920       }
 921     }
 922   }
 923 }