MText.cs

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