MText.cs

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