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