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