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