MText.cs

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