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 = (MInterval) p.Val;
 525               if (M17n.debug)
 526                 DumpPropNested ();
 527               root.MergeAfterChange (from, to);
 528               root.Balance ();
 529             }
 530         }
 531     }
 532
 533     public void DumpProp ()
 534     {
 535       Console.Write ("(");
 536       foreach (MPlist p in intervals)
 537         ((MInterval) p.Val).Dump (true);
 538       Console.WriteLine (")");
 539     }
 540
 541     public void DumpPropNested ()
 542     {
 543       Console.WriteLine ("total length = {0}", Length);
 544       foreach (MPlist p in intervals)
 545         ((MInterval) p.Val).DumpNested (true);
 546     }
 547
 548     private class MInterval
 549     {
 550       // position: 0   1   2   3   4   5   6   7
 551       //           | A | B | C | D | E   F | G |
 552       // interval  |---|---|---|<->|-------|---|
 553       //           |---|<->|---|   |<----->|---|
 554       //           |<->|   |<->|           |<->|
 555       //
 556       //                      [7 (3 4)]
 557       //              [3 (1 2)]       [3 (4 6)]
 558       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
 559       //
 560       private static int count = 0;
 561       private int ID;
 562       private int Length;
 563       private int From, To;
 564       private MSymbol Key;
 565       private MPlist Stack;
 566       private MInterval Left, Right, Parent;
 567       private MText mtext;
 568
 569       public MInterval (MSymbol key, MText mt, int length)
 570       {
 571         if (length <= 0)
 572           throw new Exception ("Invalid interval length");
 573         Key = key;
 574         mtext = mt;
 575         Length = length;
 576         Stack = new MPlist ();
 577         ID = count++;
 578       }
 579
 580       public MInterval (MSymbol key, MText mt)
 581       {
 582         Key = key;
 583         mtext = mt;
 584         Length = mt.sb.Length;
 585         From = 0;
 586         To = Length;
 587         Stack = new MPlist ();
 588         ID = count++;
 589       }
 590
 591       /// POS must be smaller than Length;
 592       public MProperty Get (int pos)
 593       {
 594         MInterval i = find_head (pos);
 595
 596         return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val);
 597       }
 598
 599       /// POS must be smaller than Length;
 600       public MProperty Get (int pos, out MProperty[] array)
 601       {
 602         MInterval i = find_head (pos);
 603
 604         if (i.To == pos)
 605           i = i.Next;
 606         if (i.Stack.IsEmpty)
 607           {
 608             array = null;
 609             return null;
 610           }
 611         array = new MProperty[i.Stack.Count];
 612
 613         int idx;
 614         MPlist p;
 615         for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
 616           array[idx] = (MProperty) p.Val;
 617         return array[0];
 618       }
 619
 620       private MInterval (MSymbol key, MText mt, int length, MPlist stack)
 621       {
 622         Key = key;
 623         mtext = mt;
 624         Length = length;
 625         From = 0;
 626         To = Length;
 627         Stack = stack == null ? new MPlist () : stack.Clone ();
 628         ID = count++;
 629       }
 630
 631       private bool isRearSticky
 632       {
 633         get { return ((Key.flags & MProperty.Flags.RearSticky)
 634                       != MProperty.Flags.None); }
 635       }
 636
 637       private bool isFrontSticky
 638       {
 639         get { return ((Key.flags & MProperty.Flags.FrontSticky)
 640                       != MProperty.Flags.None); }
 641       }
 642
 643       public bool isSensitive
 644       {
 645         get { return ((Key.flags & MProperty.Flags.Sensitive)
 646                       != MProperty.Flags.None); }
 647       }
 648
 649       private void update_from_to ()
 650       {
 651         if (Parent == null)
 652           {
 653             From = LeftLength;
 654             To = Length - RightLength;
 655           }
 656         else if (Parent.Left == this)
 657           {
 658             From = Parent.From - Length + LeftLength;
 659             To = Parent.From - RightLength;
 660           }
 661         else
 662           {
 663             From = Parent.To + LeftLength;
 664             To = Parent.To + Length - RightLength;
 665           }
 666       }
 667
 668       private int LeftLength
 669       {
 670         get { return (Left == null ? 0 : Left.Length); }
 671       }
 672
 673       private int RightLength
 674       {
 675         get { return (Right == null ? 0 : Right.Length); }
 676       }
 677
 678       private MInterval LeftMost
 679       {
 680         get {
 681           update_from_to ();
 682           if (Left == null)
 683             return this;
 684           return Left.LeftMost;
 685         }
 686       }
 687
 688       private MInterval RightMost
 689       {
 690         get {
 691           update_from_to ();
 692           if (Right == null)
 693             return this;
 694           return Right.RightMost;
 695         }
 696       }
 697
 698       private MInterval Prev {
 699         get {
 700           MInterval i;
 701
 702           if (Left != null)
 703             {
 704               for (i = Left; i.Right != null; i = i.Right)
 705                 i.update_from_to ();
 706               i.update_from_to ();
 707             }
 708           else
 709             {
 710               MInterval child = this;
 711               for (i = Parent; i != null && i.Left == child;
 712                    child = i, i = i.Parent);
 713             }
 714           return i;
 715         }
 716       }
 717
 718       private MInterval Next {
 719         get {
 720           MInterval i;
 721
 722           if (Right != null)
 723             {
 724               for (i = Right; i.Left != null; i = i.Left)
 725                 i.update_from_to ();
 726               i.update_from_to ();
 727             }
 728           else
 729             {
 730               MInterval child = this;
 731               for (i = Parent; i != null && i.Right == child;
 732                    child = i, i = i.Parent);
 733             }
 734           return i;
 735         }
 736       }
 737
 738       private MInterval find_head (int pos)
 739       {
 740         update_from_to ();
 741         if (pos < From)
 742           return Left.find_head (pos);
 743         if (pos >= To)
 744           return Right.find_head (pos);
 745         return this;
 746       }
 747
 748       private MInterval find_tail (int pos)
 749       {
 750         update_from_to ();
 751         if (pos <= From)
 752           return Left.find_tail (pos);
 753         if (pos > To)
 754           return Right.find_tail (pos);
 755         return this;
 756       }
 757
 758       private bool mergeable (MInterval i)
 759       {
 760         MPlist p1, p2;
 761
 762         for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
 763              p1 = p1.Next, p2 = p2.Next)
 764           if (p1.Val != p2.Val)
 765             return false;
 766         return (p1.IsEmpty && p2.IsEmpty);
 767       }
 768
 769       //      p-. or .-p              p-. or .-p
 770       //       .-this-.                .-right-.
 771       //    left   .-right-.  ->   .-this-.    c2
 772       //          c1       c2    left     c1
 773       private MInterval promote_right ()
 774       {
 775         MInterval c1 = Right.Left;
 776
 777         // Update Parent.
 778         if (Parent == null)
 779           mtext.intervals.Put (Key, Right);
 780         else if (Parent.Left == this)
 781           Parent.Left = Right;
 782         else
 783           Parent.Right = Right;
 784
 785         // Update Right.
 786         Right.Parent = Parent;
 787         Right.Left = this;
 788         Right.Length += LeftLength + (To - From);
 789
 790         // Update this.
 791         Parent = Right;
 792         Right = c1;
 793         Length = LeftLength + (To - From) + RightLength;
 794
 795         // Update C1 if necessary.
 796         if (c1 != null)
 797           c1.Parent = this;
 798
 799         Parent.update_from_to ();
 800         return Parent;
 801       }
 802
 803       //      p-. or .-p              p-. or .-p
 804       //       .-this-.                .-left-.
 805       //  .-left-.  .-right-.  ->     c1    .-this-.
 806       // c1      c2                        c2     right
 807       private MInterval promote_left ()
 808       {
 809         MInterval c2 = Left.Right;
 810
 811         // Update Parent.
 812         if (Parent == null)
 813           mtext.intervals.Put (Key, Left);
 814         else if (Parent.Left == this)
 815           Parent.Left = Left;
 816         else
 817           Parent.Right = Left;
 818
 819         // Update Left.
 820         Left.Parent = Parent;
 821         Left.Right = this;
 822         Left.Length += (To - From) + RightLength;
 823
 824         // Update this.
 825         Parent = Left;
 826         Left = c2;
 827         Length = LeftLength + (To - From) + RightLength;
 828
 829         // Update C2 if necessary.
 830         if (c2 != null)
 831           c2.Parent = this;
 832
 833         Parent.update_from_to ();
 834         return Parent;
 835       }
 836
 837       public MInterval Balance ()
 838       {
 839         MInterval i = this;
 840
 841         update_from_to ();
 842         while (true)
 843           {
 844             //       .-this-.
 845             //  .-left-.  .-right-.
 846             // c1     c2  c3      c4
 847             int diff = i.LeftLength - i.RightLength;
 848             int new_diff;
 849
 850             if (diff > 0)
 851               {
 852                 new_diff = (i.Length - i.LeftLength
 853                             + i.Left.RightLength - i.Left.LeftLength);
 854                 if (Math.Abs (new_diff) >= diff)
 855                   break;
 856                 M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
 857                 i = i.promote_left ();
 858                 M17n.DebugPrint ("done\n");
 859                 i.Right.Balance ();
 860               }
 861             else if (diff < 0)
 862               {
 863                 new_diff = (i.Length - i.RightLength
 864                             + i.Right.LeftLength - i.Right.RightLength);
 865                 if (Math.Abs (new_diff) >= diff)
 866                   break;
 867                 M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
 868                 i = i.promote_right ();
 869                 i.Left.Balance ();
 870               }
 871             else
 872               break;
 873           }
 874         return i;
 875       }
 876
 877       public MInterval Copy (MText mt, int start, int end)
 878       {
 879         MInterval copy, left_copy = null, right_copy = null;
 880
 881         update_from_to ();
 882
 883         if (start < From)
 884           {
 885             if (end <= From)
 886               return Left.Copy (mt, start, end);
 887             left_copy = Left.Copy (mt, start, From);
 888           }
 889         if (end > To)
 890           {
 891             if (start >= To)
 892               return Right.Copy (mt, start, end);
 893             right_copy = Right.Copy (mt, To, end);
 894           }
 895
 896         copy = new MInterval (Key, null, end - start, Stack);
 897         copy.mtext = mt;
 898         if (isSensitive && (From < start || end < To))
 899           copy.Stack.Clear ();
 900         if (left_copy != null)
 901           {
 902             copy.Left = left_copy;
 903             left_copy.Parent = copy;
 904           }
 905         if (right_copy != null)
 906           {
 907             copy.Right = right_copy;
 908             right_copy.Parent = copy;
 909           }
 910         return copy;
 911       }
 912
 913       //  this-.   ==>   this-.
 914       //     right          newright-.
 915       //                            right
 916       private MInterval divide_right (int pos)
 917       {
 918         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
 919
 920         M17n.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
 921         To = pos;
 922         if (Right != null)
 923           {
 924             interval.Right = Right;
 925             Right.Parent = interval;
 926             interval.Length += Right.Length;
 927           }
 928         interval.Parent = this;
 929         Right = interval;
 930         return interval;
 931       }
 932
 933       //    .-this   ==>       .-this
 934       //  left             .-newleft
 935       //                 left
 936       private MInterval divide_left (int pos)
 937       {
 938         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
 939
 940         M17n.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
 941         From = pos;
 942         if (Left != null)
 943           {
 944             interval.Left = Left;
 945             Left.Parent = interval;
 946             interval.Length += Left.Length;
 947           }
 948         interval.Parent = this;
 949         Left = interval;
 950         return interval;
 951       }
 952
 953       private void set_mtext (MText mt)
 954       {
 955         mtext = mt;
 956         if (Left != null)
 957           Left.set_mtext (mt);
 958         if (Right != null)
 959           Right.set_mtext (mt);
 960       }
 961
 962       private void enlarge (int len)
 963       {
 964         Length += len;
 965         To += len;
 966         for (MInterval prev = this, i = this.Parent; i != null;
 967              prev = i, i = i.Parent)
 968           {
 969             i.Length += len;
 970             if (prev == i.Left)
 971               {
 972                 i.From += len;
 973                 i.To += len;;
 974               }
 975           }
 976       }
 977
 978       private int graft_forward (MInterval interval, int start, int end)
 979       {
 980         int len;
 981
 982         if (! Stack.IsEmpty && isRearSticky)
 983           len = end - start;
 984         else if (interval == null)
 985           len = Stack.IsEmpty ? end - start : 0;
 986         else
 987           {
 988             MInterval i = interval.find_head (start);
 989
 990             len = 0;
 991             while (i != null && mergeable (i))
 992               {
 993                 M17n.DebugPrint (" grafting "); i.DumpOne (false, false);
 994                 len += i.To - i.From;
 995                 if (i.From < start)
 996                   len -= start - i.From;
 997                 if (i.To >= end)
 998                   {
 999                     len -= i.To - end;
1000                     break;
1001                   }
1002                 i = i.Next;
1003               }
1004           }
1005
1006         M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true);
1007         if (len > 0)
1008           enlarge (len);
1009         return len;
1010       }
1011
1012       private int graft_backward (MInterval interval, int start, int end)
1013       {
1014         int len;
1015
1016         if (! Stack.IsEmpty && isFrontSticky)
1017           len = end - start;
1018         else if (interval == null)
1019           len = Stack.IsEmpty ? end - start : 0;
1020         else
1021           {
1022             MInterval i = interval.find_tail (end);
1023
1024             len = 0;
1025             while (i != null && mergeable (i))
1026               {
1027                 M17n.DebugPrint (" grafting "); i.DumpOne (false, false);
1028                 len += i.To - i.From;
1029                 if (end < i.To)
1030                   len -= i.To - end;
1031                 if (i.From <= start)
1032                   {
1033                     len -= start - i.From;
1034                     break;
1035                   }
1036                 i = i.Prev;
1037               }
1038           }
1039
1040         M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true);
1041         if (len > 0)
1042           enlarge (len);
1043         return len;
1044       }
1045
1046       public void Insert (int pos, MInterval interval, int start, int end)
1047       {
1048         update_from_to ();
1049
1050         M17n.DebugPrint ("insert({0} to {1}) at {2} in ", start, end, pos);
1051         DumpOne (false, false);
1052
1053         if (pos < From)
1054           Left.Insert (pos, interval, start, end);
1055         else if (pos == From)
1056           {
1057             if (Left != null)
1058               {
1059                 MInterval prev = Prev;
1060
1061                 if (prev.isSensitive && prev.isRearSticky)
1062                   prev.Stack.Clear ();
1063                 start += prev.graft_forward (interval, start, end);
1064               }
1065             if (isSensitive && isFrontSticky)
1066               Stack.Clear ();
1067             if (start < end)
1068               {
1069                 end -= graft_backward (interval, start, end);
1070                 if (start < end)
1071                   {
1072                     if (interval != null)
1073                       interval = interval.Copy (mtext, start, end);
1074                     else
1075                       interval = new MInterval (Key, mtext, end - start, null);
1076
1077                     MInterval i;
1078                     if (Left != null)
1079                       {
1080                         //    .-this-.   ==>          .-this-.
1081                         // left-.                 .-left-.
1082                         //    child                     child-.
1083                         //                                 interval
1084                         i = Left.RightMost;
1085                         i.Right = interval;
1086                       }
1087                     else
1088                       {
1089                         Left = interval;
1090                         i = this;
1091                       }
1092                     interval.Parent = i;
1093                     for (; i != null; i = i.Parent)
1094                       i.Length += interval.Length;
1095                   }
1096               }
1097           }
1098         else if (pos < To)
1099           {
1100             if (isSensitive)
1101               Stack.Clear ();
1102
1103             int len = graft_forward (interval, start, end);
1104             start += len;
1105             pos += len;
1106             if (start < end)
1107               {
1108                 end -= graft_backward (interval, start, end);
1109                 if (start < end)
1110                   {
1111                     if (interval != null)
1112                       interval = interval.Copy (mtext, start, end);
1113                     else
1114                       interval = new MInterval (Key, mtext, end - start, null);
1115
1116                     divide_right (pos);
1117                     Right.Left = interval;
1118                     interval.Parent = Right;
1119                     for (MInterval i = Right; i != null; i = i.Parent)
1120                       i.Length += interval.Length;
1121                   }
1122               }
1123           }
1124         else if (pos == To)
1125           {
1126             if (Right != null)
1127               {
1128                 MInterval next = Next;
1129
1130                 if (next.isSensitive && next.isFrontSticky)
1131                   next.Stack.Clear ();
1132                 end -= next.graft_backward (interval, start, end);
1133               }
1134             if (isSensitive && isRearSticky)
1135               Stack.Clear ();
1136             if (start < end)
1137               {
1138                 start += graft_forward (interval, start, end);
1139                 if (start < end)
1140                   {
1141                     if (interval != null)
1142                       interval = interval.Copy (mtext, start, end);
1143                     else
1144                       interval = new MInterval (Key, mtext, end - start, null);
1145
1146                     MInterval i;
1147                     if (Right != null)
1148                       {
1149                         //    .-this-.   ==>          .-this-.
1150                         //         .-right                 .-right
1151                         //     child                  .-child
1152                         //                        interval
1153
1154                         i = Right.LeftMost;
1155                         i.Left = interval;
1156                       }
1157                     else
1158                       {
1159                         Right = interval;
1160                         i = this;
1161                       }
1162                     interval.Parent = i;
1163                     for (; i != null; i = i.Parent)
1164                       i.Length += interval.Length;
1165                   }
1166               }
1167           }
1168         else                    // (pos > To)
1169           Next.Insert (pos, interval, start, end);
1170         M17n.DebugPrint (" done\n");
1171       }
1172
1173       private void vacate_node (MInterval interval)
1174       {
1175         vacate_node (interval, null);
1176       }
1177
1178       private void vacate_node (MInterval interval, MInterval stop)
1179       {
1180         if (interval != null)
1181           M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
1182         else
1183           M17n.DebugPrint ("vacate #{0} to null\n", ID);
1184         if (interval != null)
1185           interval.Parent = Parent;
1186         if (Parent == null)
1187           {
1188             if (mtext != null)
1189               mtext.intervals.Put (Key, interval);
1190           }
1191         else
1192           {
1193             if (this == Parent.Right)
1194               Parent.Right = interval;
1195             else
1196               Parent.Left = interval;
1197
1198             int diff = Length;
1199             if (interval != null)
1200               diff -= interval.Length;
1201             for (MInterval i = Parent; i != stop; i = i.Parent)
1202               i.Length -= diff;
1203           }
1204       }
1205
1206       public void Delete (int start, int end)
1207       {
1208         update_from_to ();
1209         M17n.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
1210         if (start < From)
1211           {
1212             if (end <= From)
1213               {
1214                 Left.Delete (start, end);
1215                 return;
1216               }
1217             Left.Delete (start, From);
1218             To -= From - start;
1219             end -= From - start;
1220             From = start;
1221           }
1222         if (end > To)
1223           {
1224             if (start >= To)
1225               {
1226                 Right.Delete (start, end);
1227                 return;
1228               }
1229             Right.Delete (To, end);
1230             end = To;
1231           }
1232         if (start == From && end == To)
1233           {
1234             if (Right == null)
1235               {
1236                 vacate_node (Left);
1237               }
1238             else
1239               {
1240                 if (Left != null)
1241                   {
1242                     MInterval i;
1243
1244                     for (i = Right; i.Left != null; i = i.Left)
1245                       i.Length += Left.Length;
1246                     i.Length += Left.Length;
1247                     i.Left = Left;
1248                     Left.Parent = i;
1249                   }
1250                 vacate_node (Right);
1251               }
1252           }
1253         else
1254           {
1255             int len = end - start;
1256
1257             for (MInterval i = this; i != null; i = i.Parent)
1258               i.Length -= len;
1259           }
1260       }
1261
1262       public void Push (int start, int end, MProperty prop)
1263       {
1264         update_from_to ();
1265         M17n.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
1266         if (start < From)
1267           {
1268             if (end <= From)
1269               {
1270                 Left.Push (start, end, prop);
1271                 return;
1272               }
1273             Left.Push (start, From, prop);
1274             start = From;
1275           }
1276         if (end > To)
1277           {
1278             if (start >= To)
1279               {
1280                 Right.Push (start, end, prop);
1281                 return;
1282               }
1283             Right.Push (To, end, prop);
1284             end = To;
1285           }
1286
1287         if (start > From)
1288           divide_left (start);
1289         if (end < To)
1290           divide_right (end);
1291         Stack.Push (prop.key, prop);
1292       }
1293
1294       /// Combine intervals between HEAD and TAIL (both inclusive) to
1295       /// the common parent of HEAD and TAIL while assuming that the
1296       /// intervals are mergeable.
1297       private static void combine (MInterval head, MInterval tail)
1298       {
1299         M17n.DebugPrint ("combining "); head.DumpOne (true, false);
1300         M17n.DebugPrint (" through "); tail.DumpOne (true, false);
1301
1302         int from = head.From;
1303         int to = tail.To;
1304         // The nearest common parent of HEAD and TAIL.
1305         MInterval root;
1306
1307         for (root = head; root.To + root.RightLength < to;
1308              root = root.Parent);
1309
1310         M17n.DebugPrint (" common root is "); root.DumpOne (false, true);
1311
1312         if (from < root.From)
1313           {
1314             MInterval prev = root.Prev;
1315
1316             while (true)
1317               {
1318                 M17n.DebugPrint ("merging "); prev.DumpOne (false, true);
1319                 prev.vacate_node (prev.Left, root);
1320                 if (prev == head)
1321                   break;
1322                 if (prev.Left != null)
1323                   prev = prev.Left.RightMost;
1324                 else
1325                   prev = prev.Parent;
1326               }
1327             root.update_from_to ();
1328           }
1329         if (root.To < to)
1330           {
1331             MInterval next = root.Next;
1332
1333             while (true)
1334               {
1335                 M17n.DebugPrint ("merging "); next.DumpOne (false, true);
1336                 next.vacate_node (next.Right, root);
1337                 if (next == tail)
1338                   break;
1339                 if (next.Right != null)
1340                   next = next.Right.LeftMost;
1341                 else
1342                   next = next.Parent;
1343               }
1344             root.update_from_to ();
1345           }
1346       }
1347
1348       public void MergeAfterChange (int start, int end)
1349       {
1350         update_from_to ();
1351
1352         MInterval head = find_head (start), tail = head, i;
1353
1354         if (start == head.From && start > 0)
1355           {
1356             i = head.Prev;
1357             if (head.mergeable (i))
1358               head = i;
1359           }
1360         while (tail.To < end)
1361           {
1362             i = tail.Next;
1363             if (! tail.mergeable (i))
1364               {
1365                 if (head != tail)
1366                   combine (head, tail);
1367                 i.update_from_to ();
1368                 head = i;
1369               }
1370             tail = i;
1371           }
1372         while (true)
1373           {
1374             i = tail.Next;
1375             if (i == null || ! tail.mergeable (i))
1376               break;
1377             tail = i;
1378           }
1379         if (head != tail)
1380           combine (head, tail);
1381       }
1382
1383       public void Pop (int start, int end)
1384       {
1385         update_from_to ();
1386         M17n.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
1387         if (start < From)
1388           {
1389             if (end <= From)
1390               {
1391                 Left.Pop (start, end);
1392                 return;
1393               }
1394             Left.Pop (start, From);
1395             start = From;
1396           }
1397         if (end > To)
1398           {
1399             if (start >= To)
1400               {
1401                 Right.Pop (start, end);
1402                 return;
1403               }
1404             Right.Pop (To, end);
1405             end = To;
1406           }
1407
1408         if (! Stack.IsEmpty)
1409           {
1410             if (start > From)
1411               divide_left (start);
1412             if (end < To)
1413               divide_right (end);
1414             Stack.Pop ();
1415           }
1416       }
1417
1418       public void PopSensitive (int start, int end)
1419       {
1420         update_from_to ();
1421         MInterval head = find_head (start);
1422         MInterval tail = find_tail (end);
1423         while (! head.Stack.IsEmpty && head.From > 0)
1424           {
1425             MInterval prev = head.Prev;
1426
1427             if (prev.Stack.IsEmpty || head.Stack.Val != prev.Stack.Val)
1428               break;
1429             head = head.Prev;
1430           }
1431         while (! tail.Stack.IsEmpty && tail.To < mtext.Length)
1432           {
1433             MInterval next = tail.Next;
1434
1435             if (next.Stack.IsEmpty || tail.Stack.Val != next.Stack.Val)
1436               break;
1437             tail = tail.Next;
1438           }
1439         Pop (head.From, tail.To);
1440       }
1441
1442       private void DumpOne (bool with_prop, bool newline)
1443       {
1444         DumpOne (with_prop, newline, false);
1445       }
1446
1447       private void DumpOne (bool with_prop, bool newline, bool force)
1448       {
1449         if (force || M17n.debug)
1450           {
1451             Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1452             if (with_prop)
1453               foreach (MPlist p in Stack)
1454                 Console.Write (" " + p.Val);
1455             Console.Write (")");
1456             if (newline)
1457               Console.WriteLine ();
1458             if (Length <= 0)
1459               throw new Exception ("Invalid interval length");
1460           }
1461       }
1462
1463       public void Dump () { Dump (false); }
1464
1465       public void Dump (bool force)
1466       {
1467         if (force || M17n.debug)
1468           {
1469             update_from_to ();
1470
1471             if (Left != null)
1472               Left.Dump (force);
1473             if (From > 0)
1474               Console.Write (" ");
1475             DumpOne (true, false, force);
1476             if (Right != null)
1477               Right.Dump (force);
1478           }
1479       }
1480
1481       private int Depth {
1482         get { return (Parent == null ? 0 : Parent.Depth + 1); }
1483       }
1484
1485       public void DumpNested (bool force)
1486       {
1487         DumpNested (Key.ToString () + ":", force);
1488       }
1489
1490       public void DumpNested (string indent, bool force)
1491       {
1492         if (force || M17n.debug)
1493           {
1494             int indent_type = (Parent == null ? 1
1495                                : Parent.Left == this ? 0 : 2);
1496
1497             update_from_to ();
1498             if (Left != null)
1499               {
1500                 if (indent_type <= 1)
1501                   Left.DumpNested (indent + "  ", force);
1502                 else
1503                   Left.DumpNested (indent + "| ", force);
1504               }
1505             Console.Write (indent);
1506             if (indent_type == 0)
1507               Console.Write (".-");
1508             else if (indent_type == 2)
1509               Console.Write ("`-");
1510             DumpOne (true, true, true);
1511             if (Right != null)
1512               {
1513                 if (indent_type >= 1)
1514                   Right.DumpNested (indent + "  ", force);
1515                 else
1516                   Right.DumpNested (indent + "| ", force);
1517               }
1518           }
1519       }
1520     }
1521
1522     private class MTextEnum : IEnumerator
1523     {
1524       private MText mt;
1525       private int pos = -1;
1526
1527       public MTextEnum (MText mt)
1528         {
1529           this.mt = mt;
1530         }
1531
1532       public bool MoveNext ()
1533       {
1534         pos++;
1535         return (pos < mt.nchars);
1536       }
1537
1538       public void Reset ()
1539       {
1540         pos = -1;
1541       }
1542
1543       public object Current
1544       {
1545         get {
1546           //if (pos < 0 || pos >= mt.nchars)
1547           //throw new InvalidOperationException ();
1548           return mt[pos];
1549         }
1550       }
1551     }
1552   }
1553 }