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