MText.cs

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