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