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