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