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               root.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         return Parent;
 797       }
 798
 799       //      p-. or .-p              p-. or .-p
 800       //       .-this-.                .-left-.
 801       //  .-left-.  .-right-.  ->     c1    .-this-.
 802       // c1      c2                        c2     right
 803       private MInterval promote_left ()
 804       {
 805         MInterval c2 = Left.Right;
 806
 807         // Update Parent.
 808         if (Parent == null)
 809           mtext.intervals.Put (Key, Left);
 810         else if (Parent.Left == this)
 811           Parent.Left = Left;
 812         else
 813           Parent.Right = Left;
 814
 815         // Update Left.
 816         Left.Parent = Parent;
 817         Left.Right = this;
 818         Left.Length += (To - From) + RightLength;
 819
 820         // Update this.
 821         Parent = Left;
 822         Left = c2;
 823         Length = LeftLength + (To - From) + RightLength;
 824
 825         // Update C2 if necessary.
 826         if (c2 != null)
 827           c2.Parent = this;
 828
 829         return Parent;
 830       }
 831
 832       public MInterval Balance ()
 833       {
 834         MInterval i = this;
 835
 836         while (true)
 837           {
 838             //       .-this-.
 839             //  .-left-.  .-right-.
 840             // c1     c2  c3      c4
 841             int diff = i.LeftLength - i.RightLength;
 842             int new_diff;
 843
 844             if (diff > 0)
 845               {
 846                 new_diff = (i.Length - i.LeftLength
 847                             + i.Left.RightLength - i.Left.LeftLength);
 848                 if (Math.Abs (new_diff) >= diff)
 849                   break;
 850                 M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
 851                 i = i.promote_left ();
 852                 M17n.DebugPrint ("done\n");
 853                 i.Right.Balance ();
 854               }
 855             else if (diff < 0)
 856               {
 857                 new_diff = (i.Length - i.RightLength
 858                             + i.Right.LeftLength - i.Right.RightLength);
 859                 if (Math.Abs (new_diff) >= diff)
 860                   break;
 861                 M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
 862                 i = i.promote_right ();
 863                 i.Left.Balance ();
 864               }
 865             else
 866               break;
 867           }
 868         return i;
 869       }
 870
 871       public MInterval Copy (MText mt, int start, int end)
 872       {
 873         MInterval copy, left_copy = null, right_copy = null;
 874
 875         update_from_to ();
 876
 877         if (start < From)
 878           {
 879             if (end <= From)
 880               return Left.Copy (mt, start, end);
 881             left_copy = Left.Copy (mt, start, From);
 882           }
 883         if (end > To)
 884           {
 885             if (start >= To)
 886               return Right.Copy (mt, start, end);
 887             right_copy = Right.Copy (mt, To, end);
 888           }
 889
 890         copy = new MInterval (Key, null, end - start, Stack);
 891         copy.mtext = mt;
 892         if (isSensitive && (From < start || end < To))
 893           copy.Stack.Clear ();
 894         if (left_copy != null)
 895           {
 896             copy.Left = left_copy;
 897             left_copy.Parent = copy;
 898           }
 899         if (right_copy != null)
 900           {
 901             copy.Right = right_copy;
 902             right_copy.Parent = copy;
 903           }
 904         return copy;
 905       }
 906
 907       //  this-.   ==>   this-.
 908       //     right          newright-.
 909       //                            right
 910       private MInterval divide_right (int pos)
 911       {
 912         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
 913
 914         M17n.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
 915         To = pos;
 916         if (Right != null)
 917           {
 918             interval.Right = Right;
 919             Right.Parent = interval;
 920             interval.Length += Right.Length;
 921           }
 922         interval.Parent = this;
 923         Right = interval;
 924         return interval;
 925       }
 926
 927       //    .-this   ==>       .-this
 928       //  left             .-newleft
 929       //                 left
 930       private MInterval divide_left (int pos)
 931       {
 932         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
 933
 934         M17n.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
 935         From = pos;
 936         if (Left != null)
 937           {
 938             interval.Left = Left;
 939             Left.Parent = interval;
 940             interval.Length += Left.Length;
 941           }
 942         interval.Parent = this;
 943         Left = interval;
 944         return interval;
 945       }
 946
 947       private void set_mtext (MText mt)
 948       {
 949         mtext = mt;
 950         if (Left != null)
 951           Left.set_mtext (mt);
 952         if (Right != null)
 953           Right.set_mtext (mt);
 954       }
 955
 956       private void enlarge (int len)
 957       {
 958         Length += len;
 959         To += len;
 960         for (MInterval prev = this, i = this.Parent; i != null;
 961              prev = i, i = i.Parent)
 962           {
 963             i.Length += len;
 964             if (prev == i.Left)
 965               {
 966                 i.From += len;
 967                 i.To += len;;
 968               }
 969           }
 970       }
 971
 972       private int graft_forward (MInterval interval, int start, int end)
 973       {
 974         int len;
 975
 976         if (! Stack.IsEmpty && isRearSticky)
 977           len = end - start;
 978         else if (interval == null)
 979           len = Stack.IsEmpty ? end - start : 0;
 980         else
 981           {
 982             MInterval i = interval.find_head (start);
 983
 984             len = 0;
 985             while (i != null && mergeable (i))
 986               {
 987                 M17n.DebugPrint (" grafting "); i.DumpOne (false, false);
 988                 len += i.To - i.From;
 989                 if (i.From < start)
 990                   len -= start - i.From;
 991                 if (i.To >= end)
 992                   {
 993                     len -= i.To - end;
 994                     break;
 995                   }
 996                 i = i.Next;
 997               }
 998           }
 999
1000         M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true);
1001         if (len > 0)
1002           enlarge (len);
1003         return len;
1004       }
1005
1006       private int graft_backward (MInterval interval, int start, int end)
1007       {
1008         int len;
1009
1010         if (! Stack.IsEmpty && isFrontSticky)
1011           len = end - start;
1012         else if (interval == null)
1013           len = Stack.IsEmpty ? end - start : 0;
1014         else
1015           {
1016             MInterval i = interval.find_tail (end);
1017
1018             len = 0;
1019             while (i != null && mergeable (i))
1020               {
1021                 M17n.DebugPrint (" grafting "); i.DumpOne (false, false);
1022                 len += i.To - i.From;
1023                 if (end < i.To)
1024                   len -= i.To - end;
1025                 if (i.From <= start)
1026                   {
1027                     len -= start - i.From;
1028                     break;
1029                   }
1030                 i = i.Prev;
1031               }
1032           }
1033
1034         M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true);
1035         if (len > 0)
1036           enlarge (len);
1037         return len;
1038       }
1039
1040       public void Insert (int pos, MInterval interval, int start, int end)
1041       {
1042         update_from_to ();
1043
1044         M17n.DebugPrint ("insert({0} to {1}) at {2} in ", start, end, pos);
1045         DumpOne (false, false);
1046
1047         if (pos < From)
1048           Left.Insert (pos, interval, start, end);
1049         else if (pos == From)
1050           {
1051             if (Left != null)
1052               {
1053                 MInterval prev = Prev;
1054
1055                 if (prev.isSensitive && prev.isRearSticky)
1056                   prev.Stack.Clear ();
1057                 start += prev.graft_forward (interval, start, end);
1058               }
1059             if (isSensitive && isFrontSticky)
1060               Stack.Clear ();
1061             if (start < end)
1062               {
1063                 end -= graft_backward (interval, start, end);
1064                 if (start < end)
1065                   {
1066                     if (interval != null)
1067                       interval = interval.Copy (mtext, start, end);
1068                     else
1069                       interval = new MInterval (Key, mtext, end - start, null);
1070
1071                     MInterval i;
1072                     if (Left != null)
1073                       {
1074                         //    .-this-.   ==>          .-this-.
1075                         // left-.                 .-left-.
1076                         //    child                     child-.
1077                         //                                 interval
1078                         i = Left.RightMost;
1079                         i.Right = interval;
1080                       }
1081                     else
1082                       {
1083                         Left = interval;
1084                         i = this;
1085                       }
1086                     interval.Parent = i;
1087                     for (; i != null; i = i.Parent)
1088                       i.Length += interval.Length;
1089                   }
1090               }
1091           }
1092         else if (pos < To)
1093           {
1094             if (isSensitive)
1095               Stack.Clear ();
1096
1097             int len = graft_forward (interval, start, end);
1098             start += len;
1099             pos += len;
1100             if (start < end)
1101               {
1102                 end -= graft_backward (interval, start, end);
1103                 if (start < end)
1104                   {
1105                     if (interval != null)
1106                       interval = interval.Copy (mtext, start, end);
1107                     else
1108                       interval = new MInterval (Key, mtext, end - start, null);
1109
1110                     divide_right (pos);
1111                     Right.Left = interval;
1112                     interval.Parent = Right;
1113                     for (MInterval i = Right; i != null; i = i.Parent)
1114                       i.Length += interval.Length;
1115                   }
1116               }
1117           }
1118         else if (pos == To)
1119           {
1120             if (Right != null)
1121               {
1122                 MInterval next = Next;
1123
1124                 if (next.isSensitive && next.isFrontSticky)
1125                   next.Stack.Clear ();
1126                 end -= next.graft_backward (interval, start, end);
1127               }
1128             if (isSensitive && isRearSticky)
1129               Stack.Clear ();
1130             if (start < end)
1131               {
1132                 start += graft_forward (interval, start, end);
1133                 if (start < end)
1134                   {
1135                     if (interval != null)
1136                       interval = interval.Copy (mtext, start, end);
1137                     else
1138                       interval = new MInterval (Key, mtext, end - start, null);
1139
1140                     MInterval i;
1141                     if (Right != null)
1142                       {
1143                         //    .-this-.   ==>          .-this-.
1144                         //         .-right                 .-right
1145                         //     child                  .-child
1146                         //                        interval
1147
1148                         i = Right.LeftMost;
1149                         i.Left = interval;
1150                       }
1151                     else
1152                       {
1153                         Right = interval;
1154                         i = this;
1155                       }
1156                     interval.Parent = i;
1157                     for (; i != null; i = i.Parent)
1158                       i.Length += interval.Length;
1159                   }
1160               }
1161           }
1162         else                    // (pos > To)
1163           Next.Insert (pos, interval, start, end);
1164         M17n.DebugPrint (" done\n");
1165       }
1166
1167       private void vacate_node (MInterval interval)
1168       {
1169         vacate_node (interval, null);
1170       }
1171
1172       private void vacate_node (MInterval interval, MInterval stop)
1173       {
1174         if (interval != null)
1175           M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
1176         else
1177           M17n.DebugPrint ("vacate #{0} to null\n", ID);
1178         if (interval != null)
1179           interval.Parent = Parent;
1180         if (Parent == null)
1181           {
1182             if (mtext != null)
1183               mtext.intervals.Put (Key, interval);
1184           }
1185         else
1186           {
1187             if (this == Parent.Right)
1188               Parent.Right = interval;
1189             else
1190               Parent.Left = interval;
1191
1192             int diff = Length;
1193             if (interval != null)
1194               diff -= interval.Length;
1195             for (MInterval i = Parent; i != stop; i = i.Parent)
1196               i.Length -= diff;
1197           }
1198       }
1199
1200       public void Delete (int start, int end)
1201       {
1202         update_from_to ();
1203         M17n.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
1204         if (start < From)
1205           {
1206             if (end <= From)
1207               {
1208                 Left.Delete (start, end);
1209                 return;
1210               }
1211             Left.Delete (start, From);
1212             To -= From - start;
1213             end -= From - start;
1214             From = start;
1215           }
1216         if (end > To)
1217           {
1218             if (start >= To)
1219               {
1220                 Right.Delete (start, end);
1221                 return;
1222               }
1223             Right.Delete (To, end);
1224             end = To;
1225           }
1226         if (start == From && end == To)
1227           {
1228             if (Right == null)
1229               {
1230                 vacate_node (Left);
1231               }
1232             else
1233               {
1234                 if (Left != null)
1235                   {
1236                     MInterval i;
1237
1238                     for (i = Right; i.Left != null; i = i.Left)
1239                       i.Length += Left.Length;
1240                     i.Length += Left.Length;
1241                     i.Left = Left;
1242                     Left.Parent = i;
1243                   }
1244                 vacate_node (Right);
1245               }
1246           }
1247         else
1248           {
1249             int len = end - start;
1250
1251             for (MInterval i = this; i != null; i = i.Parent)
1252               i.Length -= len;
1253           }
1254       }
1255
1256       public void Push (int start, int end, MProperty prop)
1257       {
1258         update_from_to ();
1259         M17n.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
1260         if (start < From)
1261           {
1262             if (end <= From)
1263               {
1264                 Left.Push (start, end, prop);
1265                 return;
1266               }
1267             Left.Push (start, From, prop);
1268             start = From;
1269           }
1270         if (end > To)
1271           {
1272             if (start >= To)
1273               {
1274                 Right.Push (start, end, prop);
1275                 return;
1276               }
1277             Right.Push (To, end, prop);
1278             end = To;
1279           }
1280
1281         if (start > From)
1282           divide_left (start);
1283         if (end < To)
1284           divide_right (end);
1285         Stack.Push (prop.key, prop);
1286       }
1287
1288       /// Combine intervals between HEAD and TAIL (both inclusive) to
1289       /// the common parent of HEAD and TAIL while assuming that the
1290       /// intervals are mergeable.
1291       private static void combine (MInterval head, MInterval tail)
1292       {
1293         M17n.DebugPrint ("merging "); head.DumpOne (true, false);
1294         M17n.DebugPrint (" through "); tail.DumpOne (true, false);
1295
1296         int from = head.From;
1297         int to = tail.To;
1298         // The nearest common parent of HEAD and TAIL.
1299         MInterval root;
1300
1301         for (root = head; root.To + root.RightLength < to;
1302              root = root.Parent);
1303
1304         M17n.DebugPrint (" common root is "); root.DumpOne (false, true);
1305
1306         if (from < root.From)
1307           {
1308             MInterval prev = root.Prev;
1309
1310             while (true)
1311               {
1312                 M17n.DebugPrint ("merging "); prev.DumpOne (false, true);
1313                 prev.vacate_node (prev.Left, root);
1314                 if (prev == head)
1315                   break;
1316                 if (prev.Left != null)
1317                   prev = prev.Left.RightMost;
1318                 else
1319                   prev = prev.Parent;
1320               }
1321           }
1322         if (root.To < to)
1323           {
1324             MInterval next = root.Next;
1325
1326             while (true)
1327               {
1328                 M17n.DebugPrint ("merging "); next.DumpOne (false, true);
1329                 next.vacate_node (next.Right, root);
1330                 if (next == tail)
1331                   break;
1332                 if (next.Right != null)
1333                   next = next.Right.LeftMost;
1334                 else
1335                   next = next.Parent;
1336               }
1337           }
1338       }
1339
1340       public void MergeAfterChange (int start, int end)
1341       {
1342         update_from_to ();
1343
1344         MInterval head = find_head (start), tail = head, i;
1345
1346         if (start == head.From && start > 0)
1347           {
1348             i = head.Prev;
1349             if (head.mergeable (i))
1350               head = i;
1351           }
1352         while (tail.To < end)
1353           {
1354             i = tail.Next;
1355             if (! tail.mergeable (i))
1356               {
1357                 if (head != tail)
1358                   combine (head, tail);
1359                 head = i;
1360               }
1361             tail = i;
1362           }
1363         while (true)
1364           {
1365             i = tail.Next;
1366             if (i == null || ! tail.mergeable (i))
1367               break;
1368             tail = i;
1369           }
1370         if (head != tail)
1371           combine (head, tail);
1372       }
1373
1374       public void Pop (int start, int end)
1375       {
1376         update_from_to ();
1377         M17n.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
1378         if (start < From)
1379           {
1380             if (end <= From)
1381               {
1382                 Left.Pop (start, end);
1383                 return;
1384               }
1385             Left.Pop (start, From);
1386             start = From;
1387           }
1388         if (end > To)
1389           {
1390             if (start >= To)
1391               {
1392                 Right.Pop (start, end);
1393                 return;
1394               }
1395             Right.Pop (To, end);
1396             end = To;
1397           }
1398
1399         if (! Stack.IsEmpty)
1400           {
1401             if (start > From)
1402               divide_left (start);
1403             if (end < To)
1404               divide_right (end);
1405             Stack.Pop ();
1406           }
1407       }
1408
1409       public void PopSensitive (int start, int end)
1410       {
1411         update_from_to ();
1412         MInterval head = find_head (start);
1413         MInterval tail = find_tail (end);
1414         while (! head.Stack.IsEmpty && head.From > 0)
1415           {
1416             MInterval prev = head.Prev;
1417
1418             if (prev.Stack.IsEmpty || head.Stack.Val != prev.Stack.Val)
1419               break;
1420             head = head.Prev;
1421           }
1422         while (! tail.Stack.IsEmpty && tail.To < mtext.Length)
1423           {
1424             MInterval next = tail.Next;
1425
1426             if (next.Stack.IsEmpty || tail.Stack.Val != next.Stack.Val)
1427               break;
1428             tail = tail.Next;
1429           }
1430         Pop (head.From, tail.To);
1431       }
1432
1433       private void DumpOne (bool with_prop, bool newline)
1434       {
1435         DumpOne (with_prop, newline, false);
1436       }
1437
1438       private void DumpOne (bool with_prop, bool newline, bool force)
1439       {
1440         if (force || M17n.debug)
1441           {
1442             Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1443             if (with_prop)
1444               foreach (MPlist p in Stack)
1445                 Console.Write (" " + p.Val);
1446             Console.Write (")");
1447             if (newline)
1448               Console.WriteLine ();
1449             if (Length <= 0)
1450               throw new Exception ("Invalid interval length");
1451           }
1452       }
1453
1454       public void Dump () { Dump (false); }
1455
1456       public void Dump (bool force)
1457       {
1458         if (force || M17n.debug)
1459           {
1460             update_from_to ();
1461
1462             if (Left != null)
1463               Left.Dump (force);
1464             if (From > 0)
1465               Console.Write (" ");
1466             DumpOne (true, false, force);
1467             if (Right != null)
1468               Right.Dump (force);
1469           }
1470       }
1471
1472       private int Depth {
1473         get { return (Parent == null ? 0 : Parent.Depth + 1); }
1474       }
1475
1476       public void DumpNested (bool force)
1477       {
1478         DumpNested (Key.ToString () + ":", force);
1479       }
1480
1481       public void DumpNested (string indent, bool force)
1482       {
1483         if (force || M17n.debug)
1484           {
1485             int indent_type = (Parent == null ? 1
1486                                : Parent.Left == this ? 0 : 2);
1487
1488             update_from_to ();
1489             if (Left != null)
1490               {
1491                 if (indent_type <= 1)
1492                   Left.DumpNested (indent + "  ", force);
1493                 else
1494                   Left.DumpNested (indent + "| ", force);
1495               }
1496             Console.Write (indent);
1497             if (indent_type == 0)
1498               Console.Write (".-");
1499             else if (indent_type == 2)
1500               Console.Write ("`-");
1501             DumpOne (true, true, true);
1502             if (Right != null)
1503               {
1504                 if (indent_type >= 1)
1505                   Right.DumpNested (indent + "  ", force);
1506                 else
1507                   Right.DumpNested (indent + "| ", force);
1508               }
1509           }
1510       }
1511     }
1512
1513     private class MTextEnum : IEnumerator
1514     {
1515       private MText mt;
1516       private int pos = -1;
1517
1518       public MTextEnum (MText mt)
1519         {
1520           this.mt = mt;
1521         }
1522
1523       public bool MoveNext ()
1524       {
1525         pos++;
1526         return (pos < mt.nchars);
1527       }
1528
1529       public void Reset ()
1530       {
1531         pos = -1;
1532       }
1533
1534       public object Current
1535       {
1536         get {
1537           //if (pos < 0 || pos >= mt.nchars)
1538           //throw new InvalidOperationException ();
1539           return mt[pos];
1540         }
1541       }
1542     }
1543   }
1544 }