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 void 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     }
 248
 249     private void insert (int pos, MText mt2, int from, int to)
 250     {
 251       check_pos (pos, true);
 252
 253       int pos_idx = pos_to_idx (this, pos);
 254       int from_idx = pos_to_idx (mt2, from);
 255       int to_idx = pos_to_idx (mt2, to);
 256
 257       sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
 258       nchars += to - from;
 259
 260       foreach (MPlist plist in mt2.intervals)
 261         if (intervals.Find (plist.Key) == null)
 262           intervals.Push (plist.Key, new MInterval (plist.Key, this));
 263       foreach (MPlist plist in intervals)
 264         {
 265           MPlist p = mt2.intervals.Find (plist.Key);
 266           MInterval interval;
 267
 268           if (p.IsEmpty)
 269             interval = new MInterval (plist.Key, to - from);
 270           else
 271             interval = ((MInterval) p.Val).copy (from, to);
 272           ((MInterval) plist.Val).Insert (pos, interval);
 273         }
 274     }
 275
 276     public int this[int i]
 277     {
 278       set {
 279         i = pos_to_idx (this, i);
 280         if (value < 0x10000)
 281           {
 282             if (surrogate_high_p (sb[i]))
 283               sb.Remove (i, 1);
 284             sb[i] = (char) value;
 285           }
 286         else
 287           {
 288             char high = (char) (0xD800 + ((value - 0x10000) >> 10));
 289             char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
 290
 291             if (! surrogate_high_p (sb[i]))
 292               sb.Insert (i, 0);
 293             sb[i] = high;
 294             sb[i + 1] = low;
 295           }
 296       }
 297       get {
 298         i = pos_to_idx (this, i);
 299         return (surrogate_high_p (sb[i])
 300                 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
 301                 : sb[i]);
 302       }
 303     }
 304
 305     public MText Dup ()
 306     {
 307       return (new MText (sb.ToString ()));
 308     }
 309
 310     public MText Ins (int pos, MText mt)
 311     {
 312       insert (pos, mt, 0, mt.nchars);
 313       return this;
 314     }
 315
 316     public MText Ins (int pos, MText mt, int from, int to)
 317     {
 318       insert (pos, mt, from, to);
 319       return this;
 320     }
 321
 322     public MText Del (int from, int to)
 323     {
 324       check_range (from, to, true);
 325
 326       sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
 327       nchars -= to - from;
 328
 329       if (nchars > 0)
 330         foreach (MPlist plist in intervals)
 331           ((MInterval) plist.Val).Delete (from, to);
 332       else
 333         intervals = new MPlist ();
 334       return this;
 335     }
 336
 337     public object GetProp (int pos, MSymbol key)
 338     {
 339       check_pos (pos, false);
 340
 341       MInterval i = (MInterval) intervals.Find (key).Val;
 342
 343       if (i == null)
 344         return null;
 345
 346       MTextProperty prop = i.Get (pos);
 347       return (prop != null ? prop.Val : null);
 348     }
 349
 350     public object GetProp (int pos, MSymbol key, out MTextProperty prop)
 351     {
 352       check_pos (pos, false);
 353
 354       MInterval i = (MInterval) intervals.Find (key).Val;
 355
 356       if (i == null)
 357         return (prop = null);
 358       prop = i.Get (pos);
 359       return (prop != null ? prop.Val : null);
 360     }
 361
 362     public object GetProp (int pos, MSymbol key, out MTextProperty[] array)
 363     {
 364       check_pos (pos, false);
 365
 366       MInterval i = (MInterval) intervals.Find (key).Val;
 367
 368       if (i == null)
 369         return (array = null);
 370       MTextProperty prop = i.Get (pos, out array);
 371       return (prop != null ? prop.Val : null);
 372     }
 373
 374     public void PushProp (int from, int to, MSymbol key, object val)
 375     {
 376       check_range (from, to, false);
 377
 378       PushProp (from, to, new MTextProperty (key, val));
 379     }
 380
 381     public void PushProp (int from, int to, MTextProperty prop)
 382     {
 383       if (from < 0)
 384         {
 385           if (default_property == null)
 386             default_property = new MPlist ();
 387           default_property.Push (prop.key, prop.val);
 388         }
 389       else
 390         {
 391           MInterval root = (MInterval) intervals.Find (prop.key).Val;
 392
 393           if (root == null)
 394             {
 395               root = new MInterval (prop.key, this);
 396               intervals.Push (prop.key, root);
 397             }
 398           root.Push (from, to, prop);
 399         }
 400     }
 401
 402     public void DumpProp ()
 403     {
 404       Console.Write ("(");
 405       foreach (MPlist p in intervals)
 406         ((MInterval) p.Val).Dump ();
 407       Console.WriteLine (")");
 408     }
 409
 410     private class MInterval
 411     {
 412       // position: 0   1   2   3   4   5   6   7
 413       //           | A | B | C | D | E   F | G |
 414       // interval  |---|---|---|<->|-------|---|
 415       //           |---|<->|---|   |<----->|---|
 416       //           |<->|   |<->|           |<->|
 417       //
 418       //                      [7 (3 4)]
 419       //              [3 (1 2)]       [3 (4 6)]
 420       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
 421       //
 422       private static int count = 0;
 423       private int id;
 424       private int total_length;
 425       private int from, to;
 426       private MSymbol key;
 427       private MPlist stack;
 428       private MInterval left, right, parent;
 429       private MText mtext;
 430
 431       public MInterval (MSymbol key, int length)
 432       {
 433         if (length <= 0)
 434           throw new Exception ("Invalid interval length");
 435         this.key = key;
 436         total_length = length;
 437         stack = new MPlist ();
 438         id = count++;
 439       }
 440
 441       public MInterval (MSymbol key, MText mt)
 442       {
 443         this.key = key;
 444         mtext = mt;
 445         total_length = mt.sb.Length;
 446         from = 0;
 447         to = total_length;
 448         stack = new MPlist ();
 449         id = count++;
 450       }
 451
 452       public MTextProperty Get (int pos)
 453       {
 454         MInterval i = find (pos);
 455
 456         return (i.stack.IsEmpty ? null : (MTextProperty) i.stack.Val);
 457       }
 458
 459       public MTextProperty Get (int pos, out MTextProperty[] array)
 460       {
 461         MInterval i = find (pos);
 462
 463         if (i.stack.IsEmpty)
 464           {
 465             array = null;
 466             return null;
 467           }
 468         array = new MTextProperty[i.stack.Count];
 469
 470         int idx;
 471         MPlist p;
 472         for (idx = 0, p = i.stack; ! p.IsEmpty; idx++, p = p.Next)
 473           array[idx] = (MTextProperty) p.Val;
 474         return array[idx - 1];
 475       }
 476
 477       private MInterval (MSymbol key, int length, MPlist stack)
 478       {
 479         this.key = key;
 480         total_length = length;
 481         from = 0;
 482         to = total_length;
 483         this.stack = stack.Clone ();
 484         id = count++;
 485       }
 486
 487       private void update_from_to ()
 488       {
 489         if (parent == null)
 490           {
 491             from = LeftLength;
 492             to = total_length - RightLength;
 493           }
 494         else if (parent.left == this)
 495           {
 496             from = parent.from - total_length + LeftLength;
 497             to = parent.from - RightLength;
 498           }
 499         else
 500           {
 501             from = parent.to + LeftLength;
 502             to = parent.to + total_length - RightLength;
 503           }
 504       }
 505
 506       private int LeftLength
 507       {
 508         get { return (left == null ? 0 : left.total_length); }
 509       }
 510
 511       private int RightLength
 512       {
 513         get { return (right == null ? 0 : right.total_length); }
 514       }
 515
 516       private MInterval left_most_node
 517       {
 518         get { return (left == null ? this : left.left_most_node); }
 519       }
 520
 521       private MInterval right_most_node
 522       {
 523         get { return (right == null ? this : right.right_most_node); }
 524       }
 525
 526       private MInterval prev {
 527         get {
 528           MInterval i;
 529
 530           if (left != null)
 531             for (i = left; i.right != null; i = i.right);
 532           else
 533             for (i = parent; i != null && i.left == null; i = i.parent);
 534           return i;
 535         }
 536       }
 537
 538       private MInterval next {
 539         get {
 540           MInterval i;
 541
 542           if (right != null)
 543             for (i = right; i.left != null; i = i.left);
 544           else
 545             for (i = parent; i != null && i.right == null; i = i.parent);
 546           return i;
 547         }
 548       }
 549
 550       private MInterval find (int pos)
 551       {
 552         update_from_to ();
 553         if (pos < from)
 554           return left.find (pos);
 555         if (pos >= to)
 556           return right.find (pos);
 557         return this;
 558       }
 559
 560       //      p-. or .-p              p-. or .-p
 561       //       .-this-.                .-right-.
 562       //    left   .-right-.  ->   .-this-.    c2
 563       //          c1       c2    left     c1
 564       private MInterval promote_right ()
 565       {
 566         int right_length = right.total_length;
 567         MInterval c1;
 568
 569         if (parent == null)
 570           mtext.intervals.Put (key, right);
 571         else if (parent.left == this)
 572           parent.left = right;
 573         else
 574           parent.right = right;
 575         right.parent = parent;
 576         c1 = right.left;
 577         right.left = this;
 578
 579         parent = right;
 580         right = c1;
 581         parent.total_length += total_length;
 582         total_length -= right_length;
 583         if (c1 != null)
 584           {
 585             c1.parent = this;
 586             parent.total_length -= c1.total_length;
 587             total_length += c1.total_length;
 588           }
 589         return parent;
 590       }
 591
 592       //      p-. or .-p              p-. or .-p
 593       //       .-this-.                .-left-.
 594       //  .-left-.  .-right-.  ->     c1    .-this-.
 595       // c1      c2                        c2     right
 596       private MInterval promote_left ()
 597       {
 598         int left_length = left.total_length;
 599         MInterval c1;
 600
 601         if (parent == null)
 602           mtext.intervals.Put (key, left);
 603         else if (parent.left == this)
 604           parent.left = left;
 605         else
 606           parent.right = left;
 607         left.parent = parent;
 608         c1 = left.left;
 609         left.right = this;
 610
 611         parent = left;
 612         left = c1;
 613         parent.total_length += total_length;
 614         total_length -= left_length;
 615         if (c1 != null)
 616           {
 617             c1.parent = this;
 618             parent.total_length -= c1.total_length;
 619             total_length += c1.total_length;
 620           }
 621         return parent;
 622       }
 623
 624       private MInterval balance ()
 625       {
 626         MInterval i = this;
 627
 628         while (true)
 629           {
 630             //       .-this-.
 631             //  .-left-.  .-right-.
 632             // c1     c2  c3      c4
 633             int diff = i.LeftLength - i.RightLength;
 634             int new_diff;
 635
 636             if (diff > 0)
 637               {
 638                 new_diff = (i.total_length - i.LeftLength
 639                             + i.left.RightLength - i.left.LeftLength);
 640                 if (Math.Abs (new_diff) >= diff)
 641                   break;
 642                 i = i.promote_left ();
 643                 i.right.balance ();
 644               }
 645             else if (diff < 0)
 646               {
 647                 new_diff = (i.total_length - i.RightLength
 648                             + i.right.LeftLength - i.right.RightLength);
 649                 if (Math.Abs (new_diff) >= diff)
 650                   break;
 651                 i = i.promote_right ();
 652                 i.left.balance ();
 653               }
 654           }
 655         return i;
 656       }
 657
 658       public MInterval copy (int start, int end)
 659       {
 660         MInterval this_copy, left_copy = null, right_copy = null;
 661
 662         update_from_to ();
 663         if (start < from)
 664           {
 665             if (end <= from)
 666               return left.copy (start, end);
 667             left_copy = left.copy (start, from);
 668           }
 669         else if (end > to)
 670           {
 671             if (start >= to)
 672               return right.copy (start, end);
 673             right_copy = right.copy (to, end);
 674           }
 675         this_copy = new MInterval (key, end - start, stack);
 676         this_copy.left = left_copy;
 677         this_copy.right = right_copy;
 678
 679         return this_copy;
 680       }
 681
 682       //  this-.   ==>   this-.
 683       //     right          newright-.
 684       //                            right
 685       private MInterval divide_right (int pos)
 686       {
 687         MInterval interval = new MInterval (key, to - pos, stack);
 688
 689         Console.Write ("divide-right({0}) at ", pos); DumpOne (false, true);
 690         to = pos;
 691         if (right != null)
 692           {
 693             interval.right = right;
 694             right.parent = interval;
 695             interval.total_length += right.total_length;
 696           }
 697         interval.parent = this;
 698         right = interval;
 699         return interval;
 700       }
 701
 702       //    .-this   ==>       .-this
 703       //  left             .-newleft
 704       //                 left
 705       private MInterval divide_left (int pos)
 706       {
 707         MInterval interval = new MInterval (key, pos - from, stack);
 708
 709         Console.Write ("divide-reft({0}) at ", pos); DumpOne (false, true);
 710         from = pos;
 711         if (left != null)
 712           {
 713             interval.left = left;
 714             left.parent = interval;
 715             interval.total_length += left.total_length;
 716           }
 717         interval.parent = this;
 718         left = interval;
 719         return interval;
 720       }
 721
 722       private void remove_properties (MTextProperty.Flag flags)
 723       {
 724         for (MPlist p = stack; ! p.IsEmpty;)
 725           {
 726             MTextProperty prop = (MTextProperty) p.Val;
 727
 728             if ((prop.flags & flags) == flags)
 729               p.Pop ();
 730             else
 731               p = p.Next;
 732           }
 733       }
 734
 735       private void merge_front_properties (MPlist plist)
 736       {
 737         for (MInterval i = left_most_node; i != null; i = i.next)
 738           {
 739             if (! stack.IsEmpty)
 740               break;
 741             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 742               {
 743                 MTextProperty prop = (MTextProperty) p.Val;
 744
 745                 if ((prop.flags & MTextProperty.Flag.RearSticky)
 746                     == MTextProperty.Flag.RearSticky)
 747                   i.stack.Push (prop.key, prop);
 748               }
 749           }
 750       }
 751
 752       private void merge_rear_properties (MPlist plist)
 753       {
 754         for (MInterval i = right_most_node; i != null; i = i.prev)
 755           {
 756             if (! stack.IsEmpty)
 757               break;
 758             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 759               {
 760                 MTextProperty prop = (MTextProperty) p.Val;
 761
 762                 if ((prop.flags & MTextProperty.Flag.FrontSticky)
 763                     == MTextProperty.Flag.FrontSticky)
 764                   i.stack.Push (prop.key, prop);
 765               }
 766           }
 767       }
 768
 769       public void Insert (int pos, MInterval interval)
 770       {
 771         update_from_to ();
 772         Console.Write ("insert({0}) at ", pos); DumpOne (false, true);
 773         if (pos < from || (pos == from && left == null && pos > 0))
 774           {
 775             prev.Insert (pos, interval);
 776             return;
 777           }
 778         if (pos > to || (pos == to && right == null && next != null))
 779           {
 780             next.Insert (pos, interval);
 781             return;
 782           }
 783         if (pos > from && pos < to)
 784           {
 785             remove_properties (MTextProperty.Flag.Sensitive);
 786             divide_right (pos).Insert (pos, interval);
 787             return;
 788           }
 789         if (pos == from)
 790           {
 791             if (pos > 0)
 792               {
 793                 prev.remove_properties
 794                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
 795                 interval.merge_front_properties (prev.stack);
 796               }
 797             remove_properties
 798               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
 799             interval.merge_rear_properties (stack);
 800
 801             // INTERVAL is ready to insert.
 802             //
 803             //    .-this-.   ==>          .-this-.
 804             // left-.                  left-.
 805             //     child                  .-interval
 806             //                         child
 807
 808             if (pos > 0)
 809               {
 810                 MInterval i = left.right_most_node;
 811
 812                 i.left = interval;
 813                 interval.parent = i;
 814                 for (; i != null; i = i.parent)
 815                   i.total_length += interval.total_length;
 816               }
 817             else
 818               {
 819                 left = interval;
 820
 821                 for (MInterval i = this; i != null; i = i.parent)
 822                   i.total_length += interval.total_length;
 823               }
 824           }
 825         else                    // pos == to
 826           {
 827             if (right != null)
 828               {
 829                 MInterval left_most = right.left_most_node;
 830
 831                 left_most.remove_properties
 832                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
 833                 interval.merge_rear_properties (left_most.stack);
 834               }
 835             remove_properties
 836               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
 837             interval.merge_front_properties (stack);
 838
 839             // INTERVAL is ready to insert.
 840             //
 841             //    .-this-.   ==>          .-this-.
 842             //         .-right                 .-right
 843             //     child                  interval-.
 844             //                                    child
 845
 846             if (right != null)
 847               {
 848                 MInterval i = right.left_most_node;
 849
 850                 i.left = interval;
 851                 interval.parent = i;
 852                 for (; i != null; i = i.parent)
 853                   i.total_length += interval.total_length;
 854               }
 855             else
 856               {
 857                 right = interval;
 858
 859                 for (MInterval i = this; i != null; i = i.parent)
 860                   i.total_length += interval.total_length;
 861               }
 862           }
 863       }
 864
 865       private void vacate_node (MInterval interval)
 866       {
 867         Console.WriteLine ("vacate #{0} to #{1}", id, interval.id);
 868         if (interval != null)
 869           interval.parent = parent;
 870         if (parent == null)
 871           {
 872             mtext.intervals.Put (key, interval);
 873           }
 874         else
 875           {
 876             if (this == parent.right)
 877               parent.right = interval;
 878             else
 879               parent.left = interval;
 880
 881             int diff = total_length;
 882             if (interval != null)
 883               diff -= interval.total_length;
 884             for (MInterval i = parent; i != null; i = i.parent)
 885               i.total_length -= diff;
 886           }
 887       }
 888
 889       public void Delete (int start, int end)
 890       {
 891         update_from_to ();
 892         Console.Write ("delete({0} {1}) at ", start, end); DumpOne (false, true);
 893         if (start < from)
 894           {
 895             if (end <= from)
 896               {
 897                 left.Delete (start, end);
 898                 return;
 899               }
 900             left.Delete (start, from);
 901             to -= from - start;
 902             end -= from - start;
 903             from = start;
 904           }
 905         if (end > to)
 906           {
 907             if (start >= to)
 908               {
 909                 right.Delete (start, end);
 910                 return;
 911               }
 912             right.Delete (to, end);
 913             end = to;
 914           }
 915         if (start == from && end == to)
 916           {
 917             if (right == null)
 918               {
 919                 vacate_node (left);
 920               }
 921             else
 922               {
 923                 if (left != null)
 924                   {
 925                     MInterval i;
 926
 927                     for (i = right; i.left != null; i = i.left)
 928                       i.total_length += left.total_length;
 929                     i.total_length += left.total_length;
 930                     i.left = left;
 931                     left.parent = i;
 932                   }
 933                 vacate_node (right);
 934               }
 935           }
 936         else
 937           {
 938             int len = end - start;
 939
 940             for (MInterval i = this; i != null; i = i.parent)
 941               i.total_length -= len;
 942           }
 943       }
 944
 945       public void Push (int start, int end, MTextProperty prop)
 946       {
 947         update_from_to ();
 948         Console.Write ("push({0} {1}) at ", start, end); DumpOne (false, true);
 949         if (start < from)
 950           {
 951             if (end <= from)
 952               {
 953                 left.Push (start, end, prop);
 954                 return;
 955               }
 956             left.Push (start, from, prop);
 957             start = from;
 958           }
 959         if (end > to)
 960           {
 961             if (start >= to)
 962               {
 963                 right.Push (start, end, prop);
 964                 return;
 965               }
 966             right.Push (to, end, prop);
 967             end = to;
 968           }
 969
 970         if (start > from)
 971           divide_left (start);
 972         if (end < to)
 973           divide_right (end);
 974         stack.Push (prop.key, prop);
 975       }
 976
 977       private void DumpOne (bool with_prop, bool newline)
 978       {
 979         Console.Write ("#{0}({1} {2} {3}", id, total_length, from, to);
 980         if (with_prop)
 981           foreach (MPlist p in stack)
 982             Console.Write (" " + p.Val);
 983         Console.Write (")");
 984         if (newline)
 985           Console.WriteLine ();
 986       }
 987
 988       public void Dump ()
 989       {
 990         update_from_to ();
 991
 992         if (left != null)
 993           left.Dump ();
 994         if (from > 0)
 995           Console.Write (" ");
 996         DumpOne (true, false);
 997         if (right != null)
 998           right.Dump ();
 999       }
1000     }
1001
1002     private class MTextEnum : IEnumerator
1003     {
1004       private MText mt;
1005       private int pos = -1;
1006
1007       public MTextEnum (MText mt)
1008         {
1009           this.mt = mt;
1010         }
1011
1012       public bool MoveNext ()
1013       {
1014         pos++;
1015         return (pos < mt.nchars);
1016       }
1017
1018       public void Reset ()
1019       {
1020         pos = -1;
1021       }
1022
1023       public object Current
1024       {
1025         get {
1026           //if (pos < 0 || pos >= mt.nchars)
1027           //throw new InvalidOperationException ();
1028           return mt[pos];
1029         }
1030       }
1031     }
1032   }
1033 }