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     private void insert (int pos, int c)
 279     {
 280       check_pos (pos, true);
 281
 282       int pos_idx = pos_to_idx (this, pos);
 283
 284       if (c < 0x10000)
 285         {
 286           char ch = (char) c;
 287           sb.Insert (pos_idx, ch);
 288         }
 289       else
 290         {
 291           char high = (char) (0xD800 + ((c - 0x10000) >> 10));
 292           char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF));
 293           sb.Insert (pos_idx, low);
 294           sb.Insert (pos_idx, high);
 295         }
 296       nchars++;
 297       foreach (MPlist plist in intervals)
 298         ((MInterval) plist.Val).Insert (pos,
 299                                         new MInterval (plist.Key, this, 1));
 300     }
 301
 302     public int this[int i]
 303     {
 304       set {
 305         i = pos_to_idx (this, i);
 306         if (value < 0x10000)
 307           {
 308             if (surrogate_high_p (sb[i]))
 309               sb.Remove (i, 1);
 310             sb[i] = (char) value;
 311           }
 312         else
 313           {
 314             char high = (char) (0xD800 + ((value - 0x10000) >> 10));
 315             char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
 316
 317             if (! surrogate_high_p (sb[i]))
 318               sb.Insert (i, 0);
 319             sb[i] = high;
 320             sb[i + 1] = low;
 321           }
 322       }
 323       get {
 324         i = pos_to_idx (this, i);
 325         return (surrogate_high_p (sb[i])
 326                 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
 327                 : sb[i]);
 328       }
 329     }
 330
 331     public MText Dup ()
 332     {
 333       return (new MText (sb.ToString ()));
 334     }
 335
 336     public MText Ins (int pos, int c)
 337     {
 338       insert (pos, c);
 339       return this;
 340     }
 341
 342     public MText Ins (int pos, MText mt)
 343     {
 344       insert (pos, mt, 0, mt.nchars);
 345       return this;
 346     }
 347
 348     public MText Ins (int pos, MText mt, int from, int to)
 349     {
 350       insert (pos, mt, from, to);
 351       return this;
 352     }
 353
 354     public MText Cat (int c)
 355     {
 356       insert (nchars, c);
 357       return this;
 358     }
 359
 360     public MText Del (int from, int to)
 361     {
 362       if (check_range (from, to, true))
 363         return this;
 364
 365       sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
 366       nchars -= to - from;
 367
 368       if (nchars > 0)
 369         foreach (MPlist plist in intervals)
 370           ((MInterval) plist.Val).Delete (from, to);
 371       else
 372         intervals = new MPlist ();
 373       return this;
 374     }
 375
 376     public object GetProp (int pos, MSymbol key)
 377     {
 378       check_pos (pos, false);
 379
 380       MInterval i = (MInterval) intervals.Find (key).Val;
 381
 382       if (i == null)
 383         return null;
 384
 385       MTextProperty prop = i.Get (pos);
 386       return (prop != null ? prop.Val : null);
 387     }
 388
 389     public object GetProp (int pos, MSymbol key, out MTextProperty prop)
 390     {
 391       check_pos (pos, false);
 392
 393       MInterval i = (MInterval) intervals.Find (key).Val;
 394
 395       if (i == null)
 396         return (prop = null);
 397       prop = i.Get (pos);
 398       return (prop != null ? prop.Val : null);
 399     }
 400
 401     public object GetProp (int pos, MSymbol key, out MTextProperty[] array)
 402     {
 403       check_pos (pos, false);
 404
 405       MInterval i = (MInterval) intervals.Find (key).Val;
 406
 407       if (i == null)
 408         return (array = null);
 409       MTextProperty prop = i.Get (pos, out array);
 410       return (prop != null ? prop.Val : null);
 411     }
 412
 413     public void PushProp (int from, int to, MSymbol key, object val)
 414     {
 415       if (! check_range (from, to, true))
 416         PushProp (from, to, new MTextProperty (key, val));
 417     }
 418
 419     public void PushProp (int from, int to, MTextProperty prop)
 420     {
 421       if (from < 0)
 422         {
 423           if (default_property == null)
 424             default_property = new MPlist ();
 425           default_property.Push (prop.key, prop.val);
 426         }
 427       else
 428         {
 429           if (check_range (from, to, true))
 430             return;
 431
 432           MPlist p = intervals.Find (prop.key);
 433           MInterval root;
 434
 435           if (p == null)
 436             {
 437               root = new MInterval (prop.key, this);
 438               intervals.Push (prop.key, root);
 439             }
 440           else
 441             root = (MInterval) p.Val;
 442
 443           root.Push (from, to, prop);
 444         }
 445     }
 446
 447     public void PopProp (int from, int to, MSymbol key)
 448     {
 449       if (from < 0)
 450         {
 451           if (default_property == null)
 452             return;
 453           MPlist p = default_property.Find (key);
 454
 455           if (p != null)
 456             p.Pop ();
 457         }
 458       else
 459         {
 460           if (check_range (from, to, true))
 461             return;
 462
 463           MPlist p = intervals.Find (key);
 464
 465           if (p != null)
 466             ((MInterval) p.Val).Pop (from, to);
 467         }
 468     }
 469
 470     public void DumpProp ()
 471     {
 472       Console.Write ("(");
 473       foreach (MPlist p in intervals)
 474         ((MInterval) p.Val).Dump (true);
 475       Console.WriteLine (")");
 476     }
 477
 478     private class MInterval
 479     {
 480       // position: 0   1   2   3   4   5   6   7
 481       //           | A | B | C | D | E   F | G |
 482       // interval  |---|---|---|<->|-------|---|
 483       //           |---|<->|---|   |<----->|---|
 484       //           |<->|   |<->|           |<->|
 485       //
 486       //                      [7 (3 4)]
 487       //              [3 (1 2)]       [3 (4 6)]
 488       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
 489       //
 490       private static int count = 0;
 491       private int ID;
 492       private int Length;
 493       private int From, To;
 494       private MSymbol Key;
 495       private MPlist Stack;
 496       private MInterval Left, Right, Parent;
 497       private MText mtext;
 498
 499       public MInterval (MSymbol key, MText mt, int length)
 500       {
 501         if (length <= 0)
 502           throw new Exception ("Invalid interval length");
 503         Key = key;
 504         mtext = mt;
 505         Length = length;
 506         Stack = new MPlist ();
 507         ID = count++;
 508       }
 509
 510       public MInterval (MSymbol key, MText mt)
 511       {
 512         Key = key;
 513         mtext = mt;
 514         Length = mt.sb.Length;
 515         From = 0;
 516         To = Length;
 517         Stack = new MPlist ();
 518         ID = count++;
 519       }
 520
 521       public MTextProperty Get (int pos)
 522       {
 523         MInterval i = find (pos);
 524
 525         return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val);
 526       }
 527
 528       public MTextProperty Get (int pos, out MTextProperty[] array)
 529       {
 530         MInterval i = find (pos);
 531
 532         if (i.Stack.IsEmpty)
 533           {
 534             array = null;
 535             return null;
 536           }
 537         array = new MTextProperty[i.Stack.Count];
 538
 539         int idx;
 540         MPlist p;
 541         for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
 542           array[idx] = (MTextProperty) p.Val;
 543         return array[idx - 1];
 544       }
 545
 546       private MInterval (MSymbol key, MText mt, int length, MPlist stack)
 547       {
 548         Key = key;
 549         mtext = mt;
 550         Length = length;
 551         From = 0;
 552         To = Length;
 553         Stack = stack.Clone ();
 554         ID = count++;
 555       }
 556
 557       private void update_from_to ()
 558       {
 559         if (Parent == null)
 560           {
 561             From = LeftLength;
 562             To = Length - RightLength;
 563           }
 564         else if (Parent.Left == this)
 565           {
 566             From = Parent.From - Length + LeftLength;
 567             To = Parent.From - RightLength;
 568           }
 569         else
 570           {
 571             From = Parent.To + LeftLength;
 572             To = Parent.To + Length - RightLength;
 573           }
 574       }
 575
 576       private int LeftLength
 577       {
 578         get { return (Left == null ? 0 : Left.Length); }
 579       }
 580
 581       private int RightLength
 582       {
 583         get { return (Right == null ? 0 : Right.Length); }
 584       }
 585
 586       private MInterval LeftMost
 587       {
 588         get { return (Left == null ? this : Left.LeftMost); }
 589       }
 590
 591       private MInterval RightMost
 592       {
 593         get { return (Right == null ? this : Right.RightMost); }
 594       }
 595
 596       private MInterval Prev {
 597         get {
 598           MInterval i;
 599
 600           if (Left != null)
 601             for (i = Left; i.Right != null; i = i.Right);
 602           else
 603             {
 604               MInterval child = this;
 605               for (i = Parent; i != null && i.Left == child;
 606                    child = i, i = i.Parent);
 607             }
 608           return i;
 609         }
 610       }
 611
 612       private MInterval Next {
 613         get {
 614           MInterval i;
 615
 616           if (Right != null)
 617             for (i = Right; i.Left != null; i = i.Left);
 618           else
 619             {
 620               MInterval child = this;
 621               for (i = Parent; i != null && i.Right == child;
 622                    child = i, i = i.Parent);
 623             }
 624           return i;
 625         }
 626       }
 627
 628       private MInterval find (int pos)
 629       {
 630         update_from_to ();
 631         if (pos < From)
 632           return Left.find (pos);
 633         if (pos >= To)
 634           return Right.find (pos);
 635         return this;
 636       }
 637
 638       private bool mergeable (MInterval i)
 639       {
 640         MPlist p1, p2;
 641
 642         for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
 643              p1 = p1.Next, p2 = p2.Next)
 644           if (p1.Val != p2.Val)
 645             return false;
 646         return (p1.IsEmpty && p2.IsEmpty);
 647       }
 648
 649       //      p-. or .-p              p-. or .-p
 650       //       .-this-.                .-right-.
 651       //    left   .-right-.  ->   .-this-.    c2
 652       //          c1       c2    left     c1
 653       private MInterval promote_right ()
 654       {
 655         int right_length = Right.Length;
 656         MInterval c1;
 657
 658         if (Parent == null)
 659           mtext.intervals.Put (Key, Right);
 660         else if (Parent.Left == this)
 661           Parent.Left = Right;
 662         else
 663           Parent.Right = Right;
 664         Right.Parent = Parent;
 665         c1 = Right.Left;
 666         Right.Left = this;
 667
 668         Parent = Right;
 669         Right = c1;
 670         Parent.Length += Length;
 671         Length -= right_length;
 672         if (c1 != null)
 673           {
 674             c1.Parent = this;
 675             Parent.Length -= c1.Length;
 676             Length += c1.Length;
 677           }
 678         return Parent;
 679       }
 680
 681       //      p-. or .-p              p-. or .-p
 682       //       .-this-.                .-left-.
 683       //  .-left-.  .-right-.  ->     c1    .-this-.
 684       // c1      c2                        c2     right
 685       private MInterval promote_left ()
 686       {
 687         int left_length = Left.Length;
 688         MInterval c1;
 689
 690         if (Parent == null)
 691           mtext.intervals.Put (Key, Left);
 692         else if (Parent.Left == this)
 693           Parent.Left = Left;
 694         else
 695           Parent.Right = Left;
 696         Left.Parent = Parent;
 697         c1 = Left.Left;
 698         Left.Right = this;
 699
 700         Parent = Left;
 701         Left = c1;
 702         Parent.Length += Length;
 703         Length -= left_length;
 704         if (c1 != null)
 705           {
 706             c1.Parent = this;
 707             Parent.Length -= c1.Length;
 708             Length += c1.Length;
 709           }
 710         return Parent;
 711       }
 712
 713       private MInterval balance ()
 714       {
 715         MInterval i = this;
 716
 717         while (true)
 718           {
 719             //       .-this-.
 720             //  .-left-.  .-right-.
 721             // c1     c2  c3      c4
 722             int diff = i.LeftLength - i.RightLength;
 723             int new_diff;
 724
 725             if (diff > 0)
 726               {
 727                 new_diff = (i.Length - i.LeftLength
 728                             + i.Left.RightLength - i.Left.LeftLength);
 729                 if (Math.Abs (new_diff) >= diff)
 730                   break;
 731                 i = i.promote_left ();
 732                 i.Right.balance ();
 733               }
 734             else if (diff < 0)
 735               {
 736                 new_diff = (i.Length - i.RightLength
 737                             + i.Right.LeftLength - i.Right.RightLength);
 738                 if (Math.Abs (new_diff) >= diff)
 739                   break;
 740                 i = i.promote_right ();
 741                 i.Left.balance ();
 742               }
 743           }
 744         return i;
 745       }
 746
 747       public MInterval Copy (int start, int end)
 748       {
 749         MInterval copy, left_copy = null, right_copy = null;
 750
 751         update_from_to ();
 752         if (start < From)
 753           {
 754             if (end <= From)
 755               return Left.Copy (start, end);
 756             left_copy = Left.Copy (start, From);
 757           }
 758         else if (end > To)
 759           {
 760             if (start >= To)
 761               return Right.Copy (start, end);
 762             right_copy = Right.Copy (To, end);
 763           }
 764
 765         copy = new MInterval (Key, null, end - start, Stack);
 766         remove_properties (MTextProperty.Flag.Sensitive);
 767         copy.Left = left_copy;
 768         copy.Right = right_copy;
 769
 770         return copy;
 771       }
 772
 773       //  this-.   ==>   this-.
 774       //     right          newright-.
 775       //                            right
 776       private MInterval divide_right (int pos)
 777       {
 778         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
 779
 780         M17N.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
 781         To = pos;
 782         if (Right != null)
 783           {
 784             interval.Right = Right;
 785             Right.Parent = interval;
 786             interval.Length += Right.Length;
 787           }
 788         interval.Parent = this;
 789         Right = interval;
 790         return interval;
 791       }
 792
 793       //    .-this   ==>       .-this
 794       //  left             .-newleft
 795       //                 left
 796       private MInterval divide_left (int pos)
 797       {
 798         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
 799
 800         M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
 801         From = pos;
 802         if (Left != null)
 803           {
 804             interval.Left = Left;
 805             Left.Parent = interval;
 806             interval.Length += Left.Length;
 807           }
 808         interval.Parent = this;
 809         Left = interval;
 810         return interval;
 811       }
 812
 813       private void remove_properties (MTextProperty.Flag flags)
 814       {
 815         for (MPlist p = Stack; ! p.IsEmpty;)
 816           {
 817             MTextProperty prop = (MTextProperty) p.Val;
 818
 819             if ((prop.flags & flags) == flags)
 820               p.Pop ();
 821             else
 822               p = p.Next;
 823           }
 824       }
 825
 826       private void inherit_front_properties (MPlist plist)
 827       {
 828         for (MInterval i = LeftMost; i != null; i = i.Next)
 829           {
 830             if (! Stack.IsEmpty)
 831               break;
 832             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 833               {
 834                 MTextProperty prop = (MTextProperty) p.Val;
 835
 836                 if ((prop.flags & MTextProperty.Flag.RearSticky)
 837                     == MTextProperty.Flag.RearSticky)
 838                   i.Stack.Add (prop.key, prop);
 839               }
 840           }
 841       }
 842
 843       private void inherit_rear_properties (MPlist plist)
 844       {
 845         for (MInterval i = RightMost; i != null; i = i.Prev)
 846           {
 847             if (! Stack.IsEmpty)
 848               break;
 849             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 850               {
 851                 MTextProperty prop = (MTextProperty) p.Val;
 852
 853                 if ((prop.flags & MTextProperty.Flag.FrontSticky)
 854                     == MTextProperty.Flag.FrontSticky)
 855                   i.Stack.Add (prop.key, prop);
 856               }
 857           }
 858       }
 859
 860       private MInterval delete_node_forward ()
 861       {
 862         if (Parent != null)
 863           {
 864             int len = Length - RightLength;
 865
 866             for (MInterval i = Parent; i != null; i = i.Parent)
 867               i.Length -= len;
 868             if (Parent.Left == this)
 869               Parent.Left = Right;
 870             else
 871               Parent.Right = Right;
 872           }
 873
 874         if (Right != null)
 875           {
 876             Right.Parent = Parent;
 877             return Right.LeftMost;
 878           }
 879         return Parent;
 880       }
 881
 882       private MInterval delete_node_backward ()
 883       {
 884         if (Parent != null)
 885           {
 886             int len = Length - RightLength;
 887
 888             for (MInterval i = Parent; i != null; i = i.Parent)
 889               i.Length -= len;
 890             if (Parent.Left == this)
 891               Parent.Left = Left;
 892             else
 893               Parent.Right = Left;
 894           }
 895
 896         if (Left != null)
 897           {
 898             Left.Parent = Parent;
 899             return Left.RightMost;
 900           }
 901         return Parent;
 902       }
 903
 904       private void set_mtext (MText mt)
 905       {
 906         mtext = mt;
 907         if (Left != null)
 908           Left.set_mtext (mt);
 909         if (Right != null)
 910           Right.set_mtext (mt);
 911       }
 912
 913       private MInterval graft (MInterval interval, bool forward, out int len)
 914       {
 915         MInterval i;
 916
 917         len = 0;
 918         if (forward)
 919           {
 920             i = interval.LeftMost;
 921             while (i != null)
 922               {
 923                 if (! mergeable (i))
 924                   break;
 925                 len += i.Length - i.RightLength;
 926                 i = i.delete_node_forward ();
 927               }
 928           }
 929         else
 930           {
 931             i = interval.RightMost;
 932             while (i != null)
 933               {
 934                 if (! mergeable (i))
 935                   break;
 936                 len += i.Length - i.LeftLength;
 937                 i = i.delete_node_backward ();
 938               }
 939           }
 940
 941         Length += len;
 942         To += len;
 943         for (MInterval prev = this, ii = this.Parent; ii != null;
 944              prev = ii, ii = ii.Parent)
 945           {
 946             ii.Length += len;
 947             if (prev == ii.Left)
 948               {
 949                 ii.From += len;
 950                 ii.To += len;;
 951               }
 952           }
 953         if (i != null)
 954           while (i.Parent != null) i = i.Parent;
 955         return i;
 956       }
 957
 958       public void Insert (int pos, MInterval interval)
 959       {
 960         update_from_to ();
 961         M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos);
 962         DumpOne (false, true);
 963
 964         interval.set_mtext (mtext);
 965
 966         if (pos < From)
 967           Prev.Insert (pos, interval);
 968         else if (pos == From)
 969           {
 970             MInterval prev = Prev;
 971
 972             if (prev != null)
 973               {
 974                 if (Left == null)
 975                   {
 976                     prev.Insert (pos, interval);
 977                     return;
 978                   }
 979                 prev.remove_properties
 980                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
 981                 interval.inherit_front_properties (prev.Stack);
 982               }
 983             remove_properties
 984               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
 985             interval.inherit_rear_properties (Stack);
 986
 987             int len;
 988             interval = graft (interval, false, out len);
 989             if (interval != null && prev != null)
 990               interval = prev.graft (interval, true, out len);
 991             if (interval != null)
 992               {
 993                 MInterval i;
 994
 995                 if (Left != null)
 996                   {
 997                     //    .-this-.   ==>          .-this-.
 998                     // left-.                 .-left-.
 999                     //    child                     child-.
1000                     //                                 interval
1001                     i = Left.RightMost;
1002                     i.Right = interval;
1003                   }
1004                 else
1005                   {
1006                     Left = interval;
1007                     i = this;
1008                   }
1009                 interval.Parent = i;
1010                 for (; i != null; i = i.Parent)
1011                   i.Length += interval.Length;
1012               }
1013           }
1014         else if (pos < To)
1015           {
1016             remove_properties (MTextProperty.Flag.Sensitive);
1017
1018             int len;
1019             interval = graft (interval, true, out len);
1020             pos += len;
1021             if (interval != null)
1022               interval = graft (interval, false, out len);
1023             if (interval != null)
1024               {
1025                 divide_right (pos);
1026                 Right.Left = interval;
1027                 interval.Parent = Right;
1028                 for (MInterval i = Right; i != null; i = i.Parent)
1029                   i.Length += interval.Length;
1030               }
1031           }
1032         else if (pos == To)
1033           {
1034             MInterval next = Next;
1035
1036             if (next != null)
1037               {
1038                 if (Right == null)
1039                   {
1040                     next.Insert (pos, interval);
1041                     return;
1042                   }
1043                 next.remove_properties
1044                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1045                 interval.inherit_rear_properties (next.Stack);
1046               }
1047             remove_properties
1048               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
1049             interval.inherit_front_properties (Stack);
1050
1051             int len;
1052             interval = graft (interval, true, out len);
1053             if (interval != null && next != null)
1054               interval = next.graft (interval, false, out len);
1055             if (interval != null)
1056               {
1057                 MInterval i;
1058
1059                 if (Right != null)
1060                   {
1061                     //    .-this-.   ==>          .-this-.
1062                     //         .-right                 .-right
1063                     //     child                  .-child
1064                     //                        interval
1065
1066                     i = Right.LeftMost;
1067                     i.Left = interval;
1068                   }
1069                 else
1070                   {
1071                     Right = interval;
1072                     i = this;
1073                   }
1074                 interval.Parent = i;
1075                 for (; i != null; i = i.Parent)
1076                   i.Length += interval.Length;
1077               }
1078           }
1079         else                    // (pos > To)
1080           Next.Insert (pos, interval);
1081       }
1082
1083       private void vacate_node (MInterval interval)
1084       {
1085         M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID);
1086         if (interval != null)
1087           interval.Parent = Parent;
1088         if (Parent == null)
1089           {
1090             if (mtext != null)
1091               mtext.intervals.Put (Key, interval);
1092           }
1093         else
1094           {
1095             if (this == Parent.Right)
1096               Parent.Right = interval;
1097             else
1098               Parent.Left = interval;
1099
1100             int diff = Length;
1101             if (interval != null)
1102               diff -= interval.Length;
1103             for (MInterval i = Parent; i != null; i = i.Parent)
1104               i.Length -= diff;
1105           }
1106       }
1107
1108       public void Delete (int start, int end)
1109       {
1110         update_from_to ();
1111         M17N.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
1112         if (start < From)
1113           {
1114             if (end <= From)
1115               {
1116                 Left.Delete (start, end);
1117                 return;
1118               }
1119             Left.Delete (start, From);
1120             To -= From - start;
1121             end -= From - start;
1122             From = start;
1123           }
1124         if (end > To)
1125           {
1126             if (start >= To)
1127               {
1128                 Right.Delete (start, end);
1129                 return;
1130               }
1131             Right.Delete (To, end);
1132             end = To;
1133           }
1134         if (start == From && end == To)
1135           {
1136             if (Right == null)
1137               {
1138                 vacate_node (Left);
1139               }
1140             else
1141               {
1142                 if (Left != null)
1143                   {
1144                     MInterval i;
1145
1146                     for (i = Right; i.Left != null; i = i.Left)
1147                       i.Length += Left.Length;
1148                     i.Length += Left.Length;
1149                     i.Left = Left;
1150                     Left.Parent = i;
1151                   }
1152                 vacate_node (Right);
1153               }
1154           }
1155         else
1156           {
1157             int len = end - start;
1158
1159             for (MInterval i = this; i != null; i = i.Parent)
1160               i.Length -= len;
1161           }
1162       }
1163
1164       public void Push (int start, int end, MTextProperty prop)
1165       {
1166         update_from_to ();
1167         M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
1168         if (start < From)
1169           {
1170             if (end <= From)
1171               {
1172                 Left.Push (start, end, prop);
1173                 return;
1174               }
1175             Left.Push (start, From, prop);
1176             start = From;
1177           }
1178         if (end > To)
1179           {
1180             if (start >= To)
1181               {
1182                 Right.Push (start, end, prop);
1183                 return;
1184               }
1185             Right.Push (To, end, prop);
1186             end = To;
1187           }
1188
1189         if (start > From)
1190           divide_left (start);
1191         if (end < To)
1192           divide_right (end);
1193         Stack.Push (prop.key, prop);
1194       }
1195
1196       private bool try_merge_prev ()
1197       {
1198         MInterval prev = Prev;
1199
1200         if (! mergeable (prev))
1201           return false;
1202
1203         int len = prev.Length - prev.LeftLength;
1204
1205         // PREV is Left, Left.Right, ..., or Left....Right.
1206         if (prev != Left)
1207           {
1208             prev.Parent.Right = prev.Left;
1209             while (prev.Parent != Left)
1210               {
1211                 prev.Length -= len;
1212                 prev = prev.Parent;
1213               }
1214           }
1215         Left.Length -= len;
1216         if (Left.Length == Left.LeftLength)
1217           Left = Left.Left;
1218         return true;
1219       }
1220
1221       private bool try_merge_next ()
1222       {
1223         MInterval next = Next;
1224
1225         if (! mergeable (next))
1226           return false;
1227
1228         int len = next.Length - next.LeftLength;
1229
1230         // NEXT is Right, Right.Left, ..., or Right....Left.
1231         if (next != Right)
1232           {
1233             next.Parent.Left = next.Right;
1234             while (next.Parent != Right)
1235               {
1236                 next.Length -= len;
1237                 next = next.Parent;
1238               }
1239           }
1240         Right.Length -= len;
1241         if (Right.Length == Right.LeftLength)
1242           Right = Right.Left;
1243
1244         return true;
1245       }
1246
1247
1248       public void Pop (int start, int end)
1249       {
1250         update_from_to ();
1251         M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
1252         if (start < From)
1253           {
1254             if (end <= From)
1255               {
1256                 Left.Pop (start, end);
1257                 return;
1258               }
1259             Left.Pop (start, From);
1260             start = From;
1261           }
1262         if (end > To)
1263           {
1264             if (start >= To)
1265               {
1266                 Right.Pop (start, end);
1267                 return;
1268               }
1269             Right.Pop (To, end);
1270             end = To;
1271           }
1272
1273         if (! Stack.IsEmpty)
1274           {
1275             bool check_prev = start == From && start > 0;
1276             bool check_next = end == To && end < mtext.Length;
1277
1278             if (! check_prev)
1279               divide_left (start);
1280             if (! check_next)
1281               divide_right (end);
1282             Stack.Pop ();
1283             if (check_prev && Left != null)
1284               check_prev = try_merge_prev () && (Left != null);
1285             if (check_next && Right != null)
1286               check_next = try_merge_next () && (Right != null);
1287             if (check_prev)
1288               {
1289                 if (Prev.try_merge_next () && check_next)
1290                   Prev.try_merge_next ();
1291               }
1292             else if (check_next)
1293               {
1294                 Next.try_merge_prev ();
1295               }
1296           }
1297       }
1298
1299       private void DumpOne (bool with_prop, bool newline)
1300       {
1301         DumpOne (with_prop, newline, false);
1302       }
1303
1304       private void DumpOne (bool with_prop, bool newline, bool force)
1305       {
1306         if (force || M17N.debug)
1307           {
1308             Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1309             if (with_prop)
1310               foreach (MPlist p in Stack)
1311                 Console.Write (" " + p.Val);
1312             Console.Write (")");
1313             if (newline)
1314               Console.WriteLine ();
1315           }
1316       }
1317
1318       public void Dump () { Dump (false); }
1319
1320
1321       public void Dump (bool force)
1322       {
1323         if (force || M17N.debug)
1324           {
1325             update_from_to ();
1326
1327             if (Left != null)
1328               Left.Dump (force);
1329             if (From > 0)
1330               Console.Write (" ");
1331             DumpOne (true, false, force);
1332             if (Right != null)
1333               Right.Dump (force);
1334           }
1335       }
1336     }
1337
1338     private class MTextEnum : IEnumerator
1339     {
1340       private MText mt;
1341       private int pos = -1;
1342
1343       public MTextEnum (MText mt)
1344         {
1345           this.mt = mt;
1346         }
1347
1348       public bool MoveNext ()
1349       {
1350         pos++;
1351         return (pos < mt.nchars);
1352       }
1353
1354       public void Reset ()
1355       {
1356         pos = -1;
1357       }
1358
1359       public object Current
1360       {
1361         get {
1362           //if (pos < 0 || pos >= mt.nchars)
1363           //throw new InvalidOperationException ();
1364           return mt[pos];
1365         }
1366       }
1367     }
1368   }
1369 }