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, this, 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 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, MText mt, int length)
 463       {
 464         if (length <= 0)
 465           throw new Exception ("Invalid interval length");
 466         Key = key;
 467         mtext = mt;
 468         Length = length;
 469         Stack = new MPlist ();
 470         ID = count++;
 471       }
 472
 473       public MInterval (MSymbol key, MText mt)
 474       {
 475         Key = key;
 476         mtext = mt;
 477         Length = mt.sb.Length;
 478         From = 0;
 479         To = Length;
 480         Stack = new MPlist ();
 481         ID = count++;
 482       }
 483
 484       public MTextProperty Get (int pos)
 485       {
 486         MInterval i = find (pos);
 487
 488         return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val);
 489       }
 490
 491       public MTextProperty Get (int pos, out MTextProperty[] array)
 492       {
 493         MInterval i = find (pos);
 494
 495         if (i.Stack.IsEmpty)
 496           {
 497             array = null;
 498             return null;
 499           }
 500         array = new MTextProperty[i.Stack.Count];
 501
 502         int idx;
 503         MPlist p;
 504         for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
 505           array[idx] = (MTextProperty) p.Val;
 506         return array[idx - 1];
 507       }
 508
 509       private MInterval (MSymbol key, MText mt, int length, MPlist stack)
 510       {
 511         Key = key;
 512         mtext = mt;
 513         Length = length;
 514         From = 0;
 515         To = Length;
 516         Stack = stack.Clone ();
 517         ID = count++;
 518       }
 519
 520       private void update_from_to ()
 521       {
 522         if (Parent == null)
 523           {
 524             From = LeftLength;
 525             To = Length - RightLength;
 526           }
 527         else if (Parent.Left == this)
 528           {
 529             From = Parent.From - Length + LeftLength;
 530             To = Parent.From - RightLength;
 531           }
 532         else
 533           {
 534             From = Parent.To + LeftLength;
 535             To = Parent.To + Length - RightLength;
 536           }
 537       }
 538
 539       private int LeftLength
 540       {
 541         get { return (Left == null ? 0 : Left.Length); }
 542       }
 543
 544       private int RightLength
 545       {
 546         get { return (Right == null ? 0 : Right.Length); }
 547       }
 548
 549       private MInterval LeftMost
 550       {
 551         get { return (Left == null ? this : Left.LeftMost); }
 552       }
 553
 554       private MInterval RightMost
 555       {
 556         get { return (Right == null ? this : Right.RightMost); }
 557       }
 558
 559       private MInterval Prev {
 560         get {
 561           MInterval i;
 562
 563           if (Left != null)
 564             for (i = Left; i.Right != null; i = i.Right);
 565           else
 566             {
 567               MInterval child = this;
 568               for (i = Parent; i != null && i.Left == child;
 569                    child = i, i = i.Parent);
 570             }
 571           return i;
 572         }
 573       }
 574
 575       private MInterval Next {
 576         get {
 577           MInterval i;
 578
 579           if (Right != null)
 580             for (i = Right; i.Left != null; i = i.Left);
 581           else
 582             {
 583               MInterval child = this;
 584               for (i = Parent; i != null && i.Right == child;
 585                    child = i, i = i.Parent);
 586             }
 587           return i;
 588         }
 589       }
 590
 591       private MInterval find (int pos)
 592       {
 593         update_from_to ();
 594         if (pos < From)
 595           return Left.find (pos);
 596         if (pos >= To)
 597           return Right.find (pos);
 598         return this;
 599       }
 600
 601       private bool mergeable (MInterval i)
 602       {
 603         MPlist p1, p2;
 604
 605         for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
 606              p1 = p1.Next, p2 = p2.Next)
 607           if (p1.Val != p2.Val)
 608             return false;
 609         return (p1.IsEmpty && p2.IsEmpty);
 610       }
 611
 612       //      p-. or .-p              p-. or .-p
 613       //       .-this-.                .-right-.
 614       //    left   .-right-.  ->   .-this-.    c2
 615       //          c1       c2    left     c1
 616       private MInterval promote_right ()
 617       {
 618         int right_length = Right.Length;
 619         MInterval c1;
 620
 621         if (Parent == null)
 622           mtext.intervals.Put (Key, Right);
 623         else if (Parent.Left == this)
 624           Parent.Left = Right;
 625         else
 626           Parent.Right = Right;
 627         Right.Parent = Parent;
 628         c1 = Right.Left;
 629         Right.Left = this;
 630
 631         Parent = Right;
 632         Right = c1;
 633         Parent.Length += Length;
 634         Length -= right_length;
 635         if (c1 != null)
 636           {
 637             c1.Parent = this;
 638             Parent.Length -= c1.Length;
 639             Length += c1.Length;
 640           }
 641         return Parent;
 642       }
 643
 644       //      p-. or .-p              p-. or .-p
 645       //       .-this-.                .-left-.
 646       //  .-left-.  .-right-.  ->     c1    .-this-.
 647       // c1      c2                        c2     right
 648       private MInterval promote_left ()
 649       {
 650         int left_length = Left.Length;
 651         MInterval c1;
 652
 653         if (Parent == null)
 654           mtext.intervals.Put (Key, Left);
 655         else if (Parent.Left == this)
 656           Parent.Left = Left;
 657         else
 658           Parent.Right = Left;
 659         Left.Parent = Parent;
 660         c1 = Left.Left;
 661         Left.Right = this;
 662
 663         Parent = Left;
 664         Left = c1;
 665         Parent.Length += Length;
 666         Length -= left_length;
 667         if (c1 != null)
 668           {
 669             c1.Parent = this;
 670             Parent.Length -= c1.Length;
 671             Length += c1.Length;
 672           }
 673         return Parent;
 674       }
 675
 676       private MInterval balance ()
 677       {
 678         MInterval i = this;
 679
 680         while (true)
 681           {
 682             //       .-this-.
 683             //  .-left-.  .-right-.
 684             // c1     c2  c3      c4
 685             int diff = i.LeftLength - i.RightLength;
 686             int new_diff;
 687
 688             if (diff > 0)
 689               {
 690                 new_diff = (i.Length - i.LeftLength
 691                             + i.Left.RightLength - i.Left.LeftLength);
 692                 if (Math.Abs (new_diff) >= diff)
 693                   break;
 694                 i = i.promote_left ();
 695                 i.Right.balance ();
 696               }
 697             else if (diff < 0)
 698               {
 699                 new_diff = (i.Length - i.RightLength
 700                             + i.Right.LeftLength - i.Right.RightLength);
 701                 if (Math.Abs (new_diff) >= diff)
 702                   break;
 703                 i = i.promote_right ();
 704                 i.Left.balance ();
 705               }
 706           }
 707         return i;
 708       }
 709
 710       public MInterval Copy (int start, int end)
 711       {
 712         MInterval copy, left_copy = null, right_copy = null;
 713
 714         update_from_to ();
 715         if (start < From)
 716           {
 717             if (end <= From)
 718               return Left.Copy (start, end);
 719             left_copy = Left.Copy (start, From);
 720           }
 721         else if (end > To)
 722           {
 723             if (start >= To)
 724               return Right.Copy (start, end);
 725             right_copy = Right.Copy (To, end);
 726           }
 727
 728         copy = new MInterval (Key, null, end - start, Stack);
 729         remove_properties (MTextProperty.Flag.Sensitive);
 730         copy.Left = left_copy;
 731         copy.Right = right_copy;
 732
 733         return copy;
 734       }
 735
 736       //  this-.   ==>   this-.
 737       //     right          newright-.
 738       //                            right
 739       private MInterval divide_right (int pos)
 740       {
 741         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
 742
 743         Console.Write ("divide-right({0}) at ", pos); DumpOne (false, true);
 744         To = pos;
 745         if (Right != null)
 746           {
 747             interval.Right = Right;
 748             Right.Parent = interval;
 749             interval.Length += Right.Length;
 750           }
 751         interval.Parent = this;
 752         Right = interval;
 753         return interval;
 754       }
 755
 756       //    .-this   ==>       .-this
 757       //  left             .-newleft
 758       //                 left
 759       private MInterval divide_left (int pos)
 760       {
 761         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
 762
 763         Console.Write ("divide-left({0}) at ", pos); DumpOne (false, true);
 764         From = pos;
 765         if (Left != null)
 766           {
 767             interval.Left = Left;
 768             Left.Parent = interval;
 769             interval.Length += Left.Length;
 770           }
 771         interval.Parent = this;
 772         Left = interval;
 773         return interval;
 774       }
 775
 776       private void remove_properties (MTextProperty.Flag flags)
 777       {
 778         for (MPlist p = Stack; ! p.IsEmpty;)
 779           {
 780             MTextProperty prop = (MTextProperty) p.Val;
 781
 782             if ((prop.flags & flags) == flags)
 783               p.Pop ();
 784             else
 785               p = p.Next;
 786           }
 787       }
 788
 789       private void inherit_front_properties (MPlist plist)
 790       {
 791         for (MInterval i = LeftMost; i != null; i = i.Next)
 792           {
 793             if (! Stack.IsEmpty)
 794               break;
 795             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 796               {
 797                 MTextProperty prop = (MTextProperty) p.Val;
 798
 799                 if ((prop.flags & MTextProperty.Flag.RearSticky)
 800                     == MTextProperty.Flag.RearSticky)
 801                   i.Stack.Add (prop.key, prop);
 802               }
 803           }
 804       }
 805
 806       private void inherit_rear_properties (MPlist plist)
 807       {
 808         for (MInterval i = RightMost; i != null; i = i.Prev)
 809           {
 810             if (! Stack.IsEmpty)
 811               break;
 812             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 813               {
 814                 MTextProperty prop = (MTextProperty) p.Val;
 815
 816                 if ((prop.flags & MTextProperty.Flag.FrontSticky)
 817                     == MTextProperty.Flag.FrontSticky)
 818                   i.Stack.Add (prop.key, prop);
 819               }
 820           }
 821       }
 822
 823       private MInterval delete_node_forward ()
 824       {
 825         if (Parent != null)
 826           {
 827             int len = Length - RightLength;
 828
 829             for (MInterval i = Parent; i != null; i = i.Parent)
 830               i.Length -= len;
 831             if (Parent.Left == this)
 832               Parent.Left = Right;
 833             else
 834               Parent.Right = Right;
 835           }
 836
 837         if (Right != null)
 838           {
 839             Right.Parent = Parent;
 840             return Right.LeftMost;
 841           }
 842         return Parent;
 843       }
 844
 845       private MInterval delete_node_backward ()
 846       {
 847         if (Parent != null)
 848           {
 849             int len = Length - RightLength;
 850
 851             for (MInterval i = Parent; i != null; i = i.Parent)
 852               i.Length -= len;
 853             if (Parent.Left == this)
 854               Parent.Left = Left;
 855             else
 856               Parent.Right = Left;
 857           }
 858
 859         if (Left != null)
 860           {
 861             Left.Parent = Parent;
 862             return Left.RightMost;
 863           }
 864         return Parent;
 865       }
 866
 867       private void set_mtext (MText mt)
 868       {
 869         mtext = mt;
 870         if (Left != null)
 871           Left.set_mtext (mt);
 872         if (Right != null)
 873           Right.set_mtext (mt);
 874       }
 875
 876       private MInterval graft (MInterval interval, bool forward, out int len)
 877       {
 878         MInterval i;
 879
 880         len = 0;
 881         if (forward)
 882           {
 883             i = interval.LeftMost;
 884             while (i != null)
 885               {
 886                 if (! mergeable (i))
 887                   break;
 888                 len += i.Length - i.RightLength;
 889                 i = i.delete_node_forward ();
 890               }
 891           }
 892         else
 893           {
 894             i = interval.RightMost;
 895             while (i != null)
 896               {
 897                 if (! mergeable (i))
 898                   break;
 899                 len += i.Length - i.LeftLength;
 900                 i = i.delete_node_backward ();
 901               }
 902           }
 903
 904         Length += len;
 905         To += len;
 906         for (MInterval prev = this, ii = this.Parent; ii != null;
 907              prev = ii, ii = ii.Parent)
 908           {
 909             ii.Length += len;
 910             if (prev == ii.Left)
 911               {
 912                 ii.From += len;
 913                 ii.To += len;;
 914               }
 915           }
 916         if (i != null)
 917           while (i.Parent != null) i = i.Parent;
 918         return i;
 919       }
 920
 921       public void Insert (int pos, MInterval interval)
 922       {
 923         update_from_to ();
 924         Console.Write ("insert({0}) at {1} in ", interval.Length, pos);
 925         DumpOne (false, true);
 926
 927         interval.set_mtext (mtext);
 928
 929         if (pos < From)
 930           Prev.Insert (pos, interval);
 931         else if (pos == From)
 932           {
 933             MInterval prev = Prev;
 934
 935             if (prev != null)
 936               {
 937                 if (Left == null)
 938                   {
 939                     prev.Insert (pos, interval);
 940                     return;
 941                   }
 942                 prev.remove_properties
 943                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
 944                 interval.inherit_front_properties (prev.Stack);
 945               }
 946             remove_properties
 947               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
 948             interval.inherit_rear_properties (Stack);
 949
 950             int len;
 951             interval = graft (interval, false, out len);
 952             if (interval != null && prev != null)
 953               interval = prev.graft (interval, true, out len);
 954             if (interval != null)
 955               {
 956                 MInterval i;
 957
 958                 if (Left != null)
 959                   {
 960                     //    .-this-.   ==>          .-this-.
 961                     // left-.                 .-left-.
 962                     //    child                     child-.
 963                     //                                 interval
 964                     i = Left.RightMost;
 965                     i.Right = interval;
 966                   }
 967                 else
 968                   {
 969                     Left = interval;
 970                     i = this;
 971                   }
 972                 interval.Parent = i;
 973                 for (; i != null; i = i.Parent)
 974                   i.Length += interval.Length;
 975               }
 976           }
 977         else if (pos < To)
 978           {
 979             remove_properties (MTextProperty.Flag.Sensitive);
 980
 981             int len;
 982             interval = graft (interval, true, out len);
 983             pos += len;
 984             if (interval != null)
 985               interval = graft (interval, false, out len);
 986             if (interval != null)
 987               {
 988                 divide_right (pos);
 989                 Right.Left = interval;
 990                 interval.Parent = Right;
 991                 for (MInterval i = Right; i != null; i = i.Parent)
 992                   i.Length += interval.Length;
 993               }
 994           }
 995         else if (pos == To)
 996           {
 997             MInterval next = Next;
 998
 999             if (next != null)
1000               {
1001                 if (Right == null)
1002                   {
1003                     next.Insert (pos, interval);
1004                     return;
1005                   }
1006                 next.remove_properties
1007                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1008                 interval.inherit_rear_properties (next.Stack);
1009               }
1010             remove_properties
1011               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
1012             interval.inherit_front_properties (Stack);
1013
1014             int len;
1015             interval = graft (interval, true, out len);
1016             if (interval != null && next != null)
1017               interval = next.graft (interval, false, out len);
1018             if (interval != null)
1019               {
1020                 MInterval i;
1021
1022                 if (Right != null)
1023                   {
1024                     //    .-this-.   ==>          .-this-.
1025                     //         .-right                 .-right
1026                     //     child                  .-child
1027                     //                        interval
1028
1029                     i = Right.LeftMost;
1030                     i.Left = interval;
1031                   }
1032                 else
1033                   {
1034                     Right = interval;
1035                     i = this;
1036                   }
1037                 interval.Parent = i;
1038                 for (; i != null; i = i.Parent)
1039                   i.Length += interval.Length;
1040               }
1041           }
1042         else                    // (pos > To)
1043           Next.Insert (pos, interval);
1044       }
1045
1046       private void vacate_node (MInterval interval)
1047       {
1048         Console.WriteLine ("vacate #{0} to #{1}", ID, interval.ID);
1049         if (interval != null)
1050           interval.Parent = Parent;
1051         if (Parent == null)
1052           {
1053             if (mtext != null)
1054               mtext.intervals.Put (Key, interval);
1055           }
1056         else
1057           {
1058             if (this == Parent.Right)
1059               Parent.Right = interval;
1060             else
1061               Parent.Left = interval;
1062
1063             int diff = Length;
1064             if (interval != null)
1065               diff -= interval.Length;
1066             for (MInterval i = Parent; i != null; i = i.Parent)
1067               i.Length -= diff;
1068           }
1069       }
1070
1071       public void Delete (int start, int end)
1072       {
1073         update_from_to ();
1074         Console.Write ("delete({0} {1}) from ", start, end); DumpOne (false, true);
1075         if (start < From)
1076           {
1077             if (end <= From)
1078               {
1079                 Left.Delete (start, end);
1080                 return;
1081               }
1082             Left.Delete (start, From);
1083             To -= From - start;
1084             end -= From - start;
1085             From = start;
1086           }
1087         if (end > To)
1088           {
1089             if (start >= To)
1090               {
1091                 Right.Delete (start, end);
1092                 return;
1093               }
1094             Right.Delete (To, end);
1095             end = To;
1096           }
1097         if (start == From && end == To)
1098           {
1099             if (Right == null)
1100               {
1101                 vacate_node (Left);
1102               }
1103             else
1104               {
1105                 if (Left != null)
1106                   {
1107                     MInterval i;
1108
1109                     for (i = Right; i.Left != null; i = i.Left)
1110                       i.Length += Left.Length;
1111                     i.Length += Left.Length;
1112                     i.Left = Left;
1113                     Left.Parent = i;
1114                   }
1115                 vacate_node (Right);
1116               }
1117           }
1118         else
1119           {
1120             int len = end - start;
1121
1122             for (MInterval i = this; i != null; i = i.Parent)
1123               i.Length -= len;
1124           }
1125       }
1126
1127       public void Push (int start, int end, MTextProperty prop)
1128       {
1129         update_from_to ();
1130         Console.Write ("push({0} {1}) at ", start, end); DumpOne (false, true);
1131         if (start < From)
1132           {
1133             if (end <= From)
1134               {
1135                 Left.Push (start, end, prop);
1136                 return;
1137               }
1138             Left.Push (start, From, prop);
1139             start = From;
1140           }
1141         if (end > To)
1142           {
1143             if (start >= To)
1144               {
1145                 Right.Push (start, end, prop);
1146                 return;
1147               }
1148             Right.Push (To, end, prop);
1149             end = To;
1150           }
1151
1152         if (start > From)
1153           divide_left (start);
1154         if (end < To)
1155           divide_right (end);
1156         Stack.Push (prop.key, prop);
1157       }
1158
1159       private bool try_merge_prev ()
1160       {
1161         MInterval prev = Prev;
1162
1163         if (! mergeable (prev))
1164           return false;
1165
1166         int len = prev.Length - prev.LeftLength;
1167
1168         // PREV is Left, Left.Right, ..., or Left....Right.
1169         if (prev != Left)
1170           {
1171             prev.Parent.Right = prev.Left;
1172             while (prev.Parent != Left)
1173               {
1174                 prev.Length -= len;
1175                 prev = prev.Parent;
1176               }
1177           }
1178         Left.Length -= len;
1179         if (Left.Length == Left.LeftLength)
1180           Left = Left.Left;
1181         return true;
1182       }
1183
1184       private bool try_merge_next ()
1185       {
1186         MInterval next = Next;
1187
1188         if (! mergeable (next))
1189           return false;
1190
1191         int len = next.Length - next.LeftLength;
1192
1193         // NEXT is Right, Right.Left, ..., or Right....Left.
1194         if (next != Right)
1195           {
1196             next.Parent.Left = next.Right;
1197             while (next.Parent != Right)
1198               {
1199                 next.Length -= len;
1200                 next = next.Parent;
1201               }
1202           }
1203         Right.Length -= len;
1204         if (Right.Length == Right.LeftLength)
1205           Right = Right.Left;
1206
1207         return true;
1208       }
1209
1210
1211       public void Pop (int start, int end)
1212       {
1213         update_from_to ();
1214         Console.Write ("pop({0} {1}) at ", start, end); DumpOne (false, true);
1215         if (start < From)
1216           {
1217             if (end <= From)
1218               {
1219                 Left.Pop (start, end);
1220                 return;
1221               }
1222             Left.Pop (start, From);
1223             start = From;
1224           }
1225         if (end > To)
1226           {
1227             if (start >= To)
1228               {
1229                 Right.Pop (start, end);
1230                 return;
1231               }
1232             Right.Pop (To, end);
1233             end = To;
1234           }
1235
1236         if (! Stack.IsEmpty)
1237           {
1238             bool check_prev = start == From && start > 0;
1239             bool check_next = end == To && end < mtext.Length;
1240
1241             if (! check_prev)
1242               divide_left (start);
1243             if (! check_next)
1244               divide_right (end);
1245             Stack.Pop ();
1246             if (check_prev && Left != null)
1247               check_prev = try_merge_prev () && (Left != null);
1248             if (check_next && Right != null)
1249               check_next = try_merge_next () && (Right != null);
1250             if (check_prev)
1251               {
1252                 if (Prev.try_merge_next () && check_next)
1253                   Prev.try_merge_next ();
1254               }
1255             else if (check_next)
1256               {
1257                 Next.try_merge_prev ();
1258               }
1259           }
1260       }
1261
1262       private void DumpOne (bool with_prop, bool newline)
1263       {
1264         Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1265         if (with_prop)
1266           foreach (MPlist p in Stack)
1267             Console.Write (" " + p.Val);
1268         Console.Write (")");
1269         if (newline)
1270           Console.WriteLine ();
1271       }
1272
1273       public void Dump ()
1274       {
1275         update_from_to ();
1276
1277         if (Left != null)
1278           Left.Dump ();
1279         if (From > 0)
1280           Console.Write (" ");
1281         DumpOne (true, false);
1282         if (Right != null)
1283           Right.Dump ();
1284       }
1285     }
1286
1287     private class MTextEnum : IEnumerator
1288     {
1289       private MText mt;
1290       private int pos = -1;
1291
1292       public MTextEnum (MText mt)
1293         {
1294           this.mt = mt;
1295         }
1296
1297       public bool MoveNext ()
1298       {
1299         pos++;
1300         return (pos < mt.nchars);
1301       }
1302
1303       public void Reset ()
1304       {
1305         pos = -1;
1306       }
1307
1308       public object Current
1309       {
1310         get {
1311           //if (pos < 0 || pos >= mt.nchars)
1312           //throw new InvalidOperationException ();
1313           return mt[pos];
1314         }
1315       }
1316     }
1317   }
1318 }