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             {
 468               MInterval root = (MInterval) p.Val;
 469               root.Pop (from, to);
 470               root.MergeAfterChange (from, to);
 471             }
 472         }
 473     }
 474
 475     public void DumpProp ()
 476     {
 477       Console.Write ("(");
 478       foreach (MPlist p in intervals)
 479         ((MInterval) p.Val).Dump (true);
 480       Console.WriteLine (")");
 481     }
 482
 483     public void DumpPropNested ()
 484     {
 485       foreach (MPlist p in intervals)
 486         ((MInterval) p.Val).DumpNested (true);
 487     }
 488
 489     private class MInterval
 490     {
 491       // position: 0   1   2   3   4   5   6   7
 492       //           | A | B | C | D | E   F | G |
 493       // interval  |---|---|---|<->|-------|---|
 494       //           |---|<->|---|   |<----->|---|
 495       //           |<->|   |<->|           |<->|
 496       //
 497       //                      [7 (3 4)]
 498       //              [3 (1 2)]       [3 (4 6)]
 499       //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
 500       //
 501       private static int count = 0;
 502       private int ID;
 503       private int Length;
 504       private int From, To;
 505       private MSymbol Key;
 506       private MPlist Stack;
 507       private MInterval Left, Right, Parent;
 508       private MText mtext;
 509
 510       public MInterval (MSymbol key, MText mt, int length)
 511       {
 512         if (length <= 0)
 513           throw new Exception ("Invalid interval length");
 514         Key = key;
 515         mtext = mt;
 516         Length = length;
 517         Stack = new MPlist ();
 518         ID = count++;
 519       }
 520
 521       public MInterval (MSymbol key, MText mt)
 522       {
 523         Key = key;
 524         mtext = mt;
 525         Length = mt.sb.Length;
 526         From = 0;
 527         To = Length;
 528         Stack = new MPlist ();
 529         ID = count++;
 530       }
 531
 532       public MTextProperty Get (int pos)
 533       {
 534         MInterval i = find (pos);
 535
 536         return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val);
 537       }
 538
 539       public MTextProperty Get (int pos, out MTextProperty[] array)
 540       {
 541         MInterval i = find (pos);
 542
 543         if (i.Stack.IsEmpty)
 544           {
 545             array = null;
 546             return null;
 547           }
 548         array = new MTextProperty[i.Stack.Count];
 549
 550         int idx;
 551         MPlist p;
 552         for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
 553           array[idx] = (MTextProperty) p.Val;
 554         return array[0];
 555       }
 556
 557       private MInterval (MSymbol key, MText mt, int length, MPlist stack)
 558       {
 559         Key = key;
 560         mtext = mt;
 561         Length = length;
 562         From = 0;
 563         To = Length;
 564         Stack = stack.Clone ();
 565         ID = count++;
 566       }
 567
 568       private void update_from_to ()
 569       {
 570         if (Parent == null)
 571           {
 572             From = LeftLength;
 573             To = Length - RightLength;
 574           }
 575         else if (Parent.Left == this)
 576           {
 577             From = Parent.From - Length + LeftLength;
 578             To = Parent.From - RightLength;
 579           }
 580         else
 581           {
 582             From = Parent.To + LeftLength;
 583             To = Parent.To + Length - RightLength;
 584           }
 585       }
 586
 587       private int LeftLength
 588       {
 589         get { return (Left == null ? 0 : Left.Length); }
 590       }
 591
 592       private int RightLength
 593       {
 594         get { return (Right == null ? 0 : Right.Length); }
 595       }
 596
 597       private MInterval LeftMost
 598       {
 599         get { return (Left == null ? this : Left.LeftMost); }
 600       }
 601
 602       private MInterval RightMost
 603       {
 604         get { return (Right == null ? this : Right.RightMost); }
 605       }
 606
 607       private MInterval Prev {
 608         get {
 609           MInterval i;
 610
 611           if (Left != null)
 612             for (i = Left; i.Right != null; i = i.Right);
 613           else
 614             {
 615               MInterval child = this;
 616               for (i = Parent; i != null && i.Left == child;
 617                    child = i, i = i.Parent);
 618             }
 619           return i;
 620         }
 621       }
 622
 623       private MInterval Next {
 624         get {
 625           MInterval i;
 626
 627           if (Right != null)
 628             for (i = Right; i.Left != null; i = i.Left);
 629           else
 630             {
 631               MInterval child = this;
 632               for (i = Parent; i != null && i.Right == child;
 633                    child = i, i = i.Parent);
 634             }
 635           return i;
 636         }
 637       }
 638
 639       private MInterval find (int pos)
 640       {
 641         update_from_to ();
 642         if (pos < From)
 643           return Left.find (pos);
 644         if (pos >= To)
 645           return Right.find (pos);
 646         return this;
 647       }
 648
 649       private bool mergeable (MInterval i)
 650       {
 651         MPlist p1, p2;
 652
 653         for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
 654              p1 = p1.Next, p2 = p2.Next)
 655           if (p1.Val != p2.Val)
 656             return false;
 657         return (p1.IsEmpty && p2.IsEmpty);
 658       }
 659
 660       //      p-. or .-p              p-. or .-p
 661       //       .-this-.                .-right-.
 662       //    left   .-right-.  ->   .-this-.    c2
 663       //          c1       c2    left     c1
 664       private MInterval promote_right ()
 665       {
 666         int right_length = Right.Length;
 667         MInterval c1;
 668
 669         if (Parent == null)
 670           mtext.intervals.Put (Key, Right);
 671         else if (Parent.Left == this)
 672           Parent.Left = Right;
 673         else
 674           Parent.Right = Right;
 675         Right.Parent = Parent;
 676         c1 = Right.Left;
 677         Right.Left = this;
 678
 679         Parent = Right;
 680         Right = c1;
 681         Parent.Length += Length;
 682         Length -= right_length;
 683         if (c1 != null)
 684           {
 685             c1.Parent = this;
 686             Parent.Length -= c1.Length;
 687             Length += c1.Length;
 688           }
 689         return Parent;
 690       }
 691
 692       //      p-. or .-p              p-. or .-p
 693       //       .-this-.                .-left-.
 694       //  .-left-.  .-right-.  ->     c1    .-this-.
 695       // c1      c2                        c2     right
 696       private MInterval promote_left ()
 697       {
 698         int left_length = Left.Length;
 699         MInterval c1;
 700
 701         if (Parent == null)
 702           mtext.intervals.Put (Key, Left);
 703         else if (Parent.Left == this)
 704           Parent.Left = Left;
 705         else
 706           Parent.Right = Left;
 707         Left.Parent = Parent;
 708         c1 = Left.Left;
 709         Left.Right = this;
 710
 711         Parent = Left;
 712         Left = c1;
 713         Parent.Length += Length;
 714         Length -= left_length;
 715         if (c1 != null)
 716           {
 717             c1.Parent = this;
 718             Parent.Length -= c1.Length;
 719             Length += c1.Length;
 720           }
 721         return Parent;
 722       }
 723
 724       private MInterval balance ()
 725       {
 726         MInterval i = this;
 727
 728         while (true)
 729           {
 730             //       .-this-.
 731             //  .-left-.  .-right-.
 732             // c1     c2  c3      c4
 733             int diff = i.LeftLength - i.RightLength;
 734             int new_diff;
 735
 736             if (diff > 0)
 737               {
 738                 new_diff = (i.Length - i.LeftLength
 739                             + i.Left.RightLength - i.Left.LeftLength);
 740                 if (Math.Abs (new_diff) >= diff)
 741                   break;
 742                 i = i.promote_left ();
 743                 i.Right.balance ();
 744               }
 745             else if (diff < 0)
 746               {
 747                 new_diff = (i.Length - i.RightLength
 748                             + i.Right.LeftLength - i.Right.RightLength);
 749                 if (Math.Abs (new_diff) >= diff)
 750                   break;
 751                 i = i.promote_right ();
 752                 i.Left.balance ();
 753               }
 754           }
 755         return i;
 756       }
 757
 758       public MInterval Copy (int start, int end)
 759       {
 760         MInterval copy, left_copy = null, right_copy = null;
 761
 762         update_from_to ();
 763
 764         if (start < From)
 765           {
 766             if (end <= From)
 767               return Left.Copy (start, end);
 768             left_copy = Left.Copy (start, From);
 769           }
 770         if (end > To)
 771           {
 772             if (start >= To)
 773               return Right.Copy (start, end);
 774             right_copy = Right.Copy (To, end);
 775           }
 776
 777         copy = new MInterval (Key, null, end - start, Stack);
 778         remove_properties (MTextProperty.Flag.Sensitive);
 779         if (left_copy != null)
 780           {
 781             copy.Left = left_copy;
 782             left_copy.Parent = copy;
 783           }
 784         if (right_copy != null)
 785           {
 786             copy.Right = right_copy;
 787             right_copy.Parent = copy;
 788           }
 789         return copy;
 790       }
 791
 792       //  this-.   ==>   this-.
 793       //     right          newright-.
 794       //                            right
 795       private MInterval divide_right (int pos)
 796       {
 797         MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
 798
 799         M17N.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
 800         To = pos;
 801         if (Right != null)
 802           {
 803             interval.Right = Right;
 804             Right.Parent = interval;
 805             interval.Length += Right.Length;
 806           }
 807         interval.Parent = this;
 808         Right = interval;
 809         return interval;
 810       }
 811
 812       //    .-this   ==>       .-this
 813       //  left             .-newleft
 814       //                 left
 815       private MInterval divide_left (int pos)
 816       {
 817         MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
 818
 819         M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
 820         From = pos;
 821         if (Left != null)
 822           {
 823             interval.Left = Left;
 824             Left.Parent = interval;
 825             interval.Length += Left.Length;
 826           }
 827         interval.Parent = this;
 828         Left = interval;
 829         return interval;
 830       }
 831
 832       private void remove_properties (MTextProperty.Flag flags)
 833       {
 834         for (MPlist p = Stack; ! p.IsEmpty;)
 835           {
 836             MTextProperty prop = (MTextProperty) p.Val;
 837
 838             if ((prop.flags & flags) == flags)
 839               p.Pop ();
 840             else
 841               p = p.Next;
 842           }
 843       }
 844
 845       private void inherit_front_properties (MPlist plist)
 846       {
 847         for (MInterval i = LeftMost; i != null; i = i.Next)
 848           {
 849             if (! Stack.IsEmpty)
 850               break;
 851             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 852               {
 853                 MTextProperty prop = (MTextProperty) p.Val;
 854
 855                 if ((prop.flags & MTextProperty.Flag.RearSticky)
 856                     == MTextProperty.Flag.RearSticky)
 857                   i.Stack.Add (prop.key, prop);
 858               }
 859           }
 860       }
 861
 862       private void inherit_rear_properties (MPlist plist)
 863       {
 864         for (MInterval i = RightMost; i != null; i = i.Prev)
 865           {
 866             if (! Stack.IsEmpty)
 867               break;
 868             for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
 869               {
 870                 MTextProperty prop = (MTextProperty) p.Val;
 871
 872                 if ((prop.flags & MTextProperty.Flag.FrontSticky)
 873                     == MTextProperty.Flag.FrontSticky)
 874                   i.Stack.Add (prop.key, prop);
 875               }
 876           }
 877       }
 878
 879       private MInterval delete_node_forward ()
 880       {
 881         if (Parent != null)
 882           {
 883             int len = Length - RightLength;
 884
 885             for (MInterval i = Parent; i != null; i = i.Parent)
 886               i.Length -= len;
 887             if (Parent.Left == this)
 888               Parent.Left = Right;
 889             else
 890               Parent.Right = Right;
 891           }
 892
 893         if (Right != null)
 894           {
 895             Right.Parent = Parent;
 896             return Right.LeftMost;
 897           }
 898         return Parent;
 899       }
 900
 901       private MInterval delete_node_backward ()
 902       {
 903         if (Parent != null)
 904           {
 905             int len = Length - RightLength;
 906
 907             for (MInterval i = Parent; i != null; i = i.Parent)
 908               i.Length -= len;
 909             if (Parent.Left == this)
 910               Parent.Left = Left;
 911             else
 912               Parent.Right = Left;
 913           }
 914
 915         if (Left != null)
 916           {
 917             Left.Parent = Parent;
 918             return Left.RightMost;
 919           }
 920         return Parent;
 921       }
 922
 923       private void set_mtext (MText mt)
 924       {
 925         mtext = mt;
 926         if (Left != null)
 927           Left.set_mtext (mt);
 928         if (Right != null)
 929           Right.set_mtext (mt);
 930       }
 931
 932       private MInterval graft (MInterval interval, bool forward, out int len)
 933       {
 934         MInterval i;
 935
 936         len = 0;
 937         if (forward)
 938           {
 939             i = interval.LeftMost;
 940             while (i != null)
 941               {
 942                 if (! mergeable (i))
 943                   break;
 944                 len += i.Length - i.RightLength;
 945                 i = i.delete_node_forward ();
 946               }
 947           }
 948         else
 949           {
 950             i = interval.RightMost;
 951             while (i != null)
 952               {
 953                 if (! mergeable (i))
 954                   break;
 955                 len += i.Length - i.LeftLength;
 956                 i = i.delete_node_backward ();
 957               }
 958           }
 959
 960         Length += len;
 961         To += len;
 962         for (MInterval prev = this, ii = this.Parent; ii != null;
 963              prev = ii, ii = ii.Parent)
 964           {
 965             ii.Length += len;
 966             if (prev == ii.Left)
 967               {
 968                 ii.From += len;
 969                 ii.To += len;;
 970               }
 971           }
 972         if (i != null)
 973           while (i.Parent != null) i = i.Parent;
 974         return i;
 975       }
 976
 977       public void Insert (int pos, MInterval interval)
 978       {
 979         update_from_to ();
 980         M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos);
 981         DumpOne (false, true);
 982
 983         interval.set_mtext (mtext);
 984
 985         if (pos < From)
 986           Prev.Insert (pos, interval);
 987         else if (pos == From)
 988           {
 989             MInterval prev = Prev;
 990
 991             if (prev != null)
 992               {
 993                 if (Left == null)
 994                   {
 995                     prev.Insert (pos, interval);
 996                     return;
 997                   }
 998                 prev.remove_properties
 999                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
1000                 interval.inherit_front_properties (prev.Stack);
1001               }
1002             remove_properties
1003               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1004             interval.inherit_rear_properties (Stack);
1005
1006             int len;
1007             interval = graft (interval, false, out len);
1008             if (interval != null && prev != null)
1009               interval = prev.graft (interval, true, out len);
1010             if (interval != null)
1011               {
1012                 MInterval i;
1013
1014                 if (Left != null)
1015                   {
1016                     //    .-this-.   ==>          .-this-.
1017                     // left-.                 .-left-.
1018                     //    child                     child-.
1019                     //                                 interval
1020                     i = Left.RightMost;
1021                     i.Right = interval;
1022                   }
1023                 else
1024                   {
1025                     Left = interval;
1026                     i = this;
1027                   }
1028                 interval.Parent = i;
1029                 for (; i != null; i = i.Parent)
1030                   i.Length += interval.Length;
1031               }
1032           }
1033         else if (pos < To)
1034           {
1035             remove_properties (MTextProperty.Flag.Sensitive);
1036
1037             int len;
1038             interval = graft (interval, true, out len);
1039             pos += len;
1040             if (interval != null)
1041               interval = graft (interval, false, out len);
1042             if (interval != null)
1043               {
1044                 divide_right (pos);
1045                 Right.Left = interval;
1046                 interval.Parent = Right;
1047                 for (MInterval i = Right; i != null; i = i.Parent)
1048                   i.Length += interval.Length;
1049               }
1050           }
1051         else if (pos == To)
1052           {
1053             MInterval next = Next;
1054
1055             if (next != null)
1056               {
1057                 if (Right == null)
1058                   {
1059                     next.Insert (pos, interval);
1060                     return;
1061                   }
1062                 next.remove_properties
1063                   (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
1064                 interval.inherit_rear_properties (next.Stack);
1065               }
1066             remove_properties
1067               (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
1068             interval.inherit_front_properties (Stack);
1069
1070             int len;
1071             interval = graft (interval, true, out len);
1072             if (interval != null && next != null)
1073               interval = next.graft (interval, false, out len);
1074             if (interval != null)
1075               {
1076                 MInterval i;
1077
1078                 if (Right != null)
1079                   {
1080                     //    .-this-.   ==>          .-this-.
1081                     //         .-right                 .-right
1082                     //     child                  .-child
1083                     //                        interval
1084
1085                     i = Right.LeftMost;
1086                     i.Left = interval;
1087                   }
1088                 else
1089                   {
1090                     Right = interval;
1091                     i = this;
1092                   }
1093                 interval.Parent = i;
1094                 for (; i != null; i = i.Parent)
1095                   i.Length += interval.Length;
1096               }
1097           }
1098         else                    // (pos > To)
1099           Next.Insert (pos, interval);
1100       }
1101
1102       private void vacate_node (MInterval interval)
1103       {
1104         M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID);
1105         if (interval != null)
1106           interval.Parent = Parent;
1107         if (Parent == null)
1108           {
1109             if (mtext != null)
1110               mtext.intervals.Put (Key, interval);
1111           }
1112         else
1113           {
1114             if (this == Parent.Right)
1115               Parent.Right = interval;
1116             else
1117               Parent.Left = interval;
1118
1119             int diff = Length;
1120             if (interval != null)
1121               diff -= interval.Length;
1122             for (MInterval i = Parent; i != null; i = i.Parent)
1123               i.Length -= diff;
1124           }
1125       }
1126
1127       public void Delete (int start, int end)
1128       {
1129         update_from_to ();
1130         M17N.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
1131         if (start < From)
1132           {
1133             if (end <= From)
1134               {
1135                 Left.Delete (start, end);
1136                 return;
1137               }
1138             Left.Delete (start, From);
1139             To -= From - start;
1140             end -= From - start;
1141             From = start;
1142           }
1143         if (end > To)
1144           {
1145             if (start >= To)
1146               {
1147                 Right.Delete (start, end);
1148                 return;
1149               }
1150             Right.Delete (To, end);
1151             end = To;
1152           }
1153         if (start == From && end == To)
1154           {
1155             if (Right == null)
1156               {
1157                 vacate_node (Left);
1158               }
1159             else
1160               {
1161                 if (Left != null)
1162                   {
1163                     MInterval i;
1164
1165                     for (i = Right; i.Left != null; i = i.Left)
1166                       i.Length += Left.Length;
1167                     i.Length += Left.Length;
1168                     i.Left = Left;
1169                     Left.Parent = i;
1170                   }
1171                 vacate_node (Right);
1172               }
1173           }
1174         else
1175           {
1176             int len = end - start;
1177
1178             for (MInterval i = this; i != null; i = i.Parent)
1179               i.Length -= len;
1180           }
1181       }
1182
1183       public void Push (int start, int end, MTextProperty prop)
1184       {
1185         update_from_to ();
1186         M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
1187         if (start < From)
1188           {
1189             if (end <= From)
1190               {
1191                 Left.Push (start, end, prop);
1192                 return;
1193               }
1194             Left.Push (start, From, prop);
1195             start = From;
1196           }
1197         if (end > To)
1198           {
1199             if (start >= To)
1200               {
1201                 Right.Push (start, end, prop);
1202                 return;
1203               }
1204             Right.Push (To, end, prop);
1205             end = To;
1206           }
1207
1208         if (start > From)
1209           divide_left (start);
1210         if (end < To)
1211           divide_right (end);
1212         Stack.Push (prop.key, prop);
1213       }
1214
1215       private static void merge_nodes (MInterval head, MInterval tail)
1216       {
1217         M17N.DebugPrint ("merging "); head.DumpOne (true, false);
1218         M17N.DebugPrint (" through "); tail.DumpOne (true, true);
1219
1220         int from = head.From;
1221         int to = tail.To;
1222         MInterval root;
1223
1224         for (root = head; root.To + head.RightLength < to;
1225              root = root.Parent);
1226
1227         M17N.DebugPrint ("common root is "); root.DumpOne (false, true);
1228
1229         if (from < root.From)
1230           {
1231             MInterval prev = root.Prev;
1232
1233             while (true)
1234               {
1235                 int len = prev.Length - prev.LeftLength;
1236
1237                 M17N.DebugPrint ("merging "); prev.DumpOne (false, true);
1238                 if (prev.Left != null)
1239                   {
1240                     prev.Left.Parent = prev.Parent;
1241                     if (prev.Parent.Right == prev)
1242                       prev.Parent.Right = prev.Left;
1243                     else
1244                       prev.Parent.Left = prev.Left;
1245                     for (MInterval i = prev.Parent; i != root; i = i.Parent)
1246                       i.Length -= len;
1247                     if (prev == head)
1248                       break;
1249                     prev = prev.Left.RightMost;
1250                   }
1251                 else
1252                   {
1253                     prev.Parent.Right = null;
1254                     for (MInterval i = prev.Parent; i != root; i = i.Parent)
1255                       i.Length -= len;
1256                     if (prev == head)
1257                       break;
1258                     prev = prev.Parent;
1259                   }
1260               }
1261           }
1262         if (root.To < to)
1263           {
1264             MInterval next = root.Next;
1265
1266             while (true)
1267               {
1268                 int len = next.Length - next.RightLength;
1269
1270                 M17N.DebugPrint ("merging "); next.DumpOne (false, true);
1271                 if (next.Right != null)
1272                   {
1273                     next.Right.Parent = next.Parent;
1274                     if (next.Parent.Left == next)
1275                       next.Parent.Left = next.Right;
1276                     else
1277                       next.Parent.Right = next.Right;
1278                     for (MInterval i = next.Parent; i != root; i = i.Parent)
1279                       i.Length -= len;
1280                     if (next == tail)
1281                       break;
1282                     next = next.Right.LeftMost;
1283                   }
1284                 else
1285                   {
1286                     next.Parent.Left = null;
1287                     for (MInterval i = next.Parent; i != root; i = i.Parent)
1288                       i.Length -= len;
1289                     if (next == tail)
1290                       break;
1291                     next = next.Parent;
1292                   }
1293               }
1294           }
1295       }
1296
1297       public void MergeAfterChange (int start, int end)
1298       {
1299         update_from_to ();
1300         if (start < From)
1301           {
1302             Prev.MergeAfterChange (start, end);
1303             return;
1304           }
1305
1306         MInterval head = this, tail = this, i;
1307
1308         if (start == From && start > 0)
1309           {
1310             i = Prev;
1311             if (mergeable (i))
1312               head = i;
1313           }
1314         while (tail.To < end)
1315           {
1316             i = tail.Next;
1317             if (! tail.mergeable (i))
1318               {
1319                 if (head != tail)
1320                   merge_nodes (head, tail);
1321                 head = i;
1322               }
1323             tail = i;
1324           }
1325         while (true)
1326           {
1327             i = tail.Next;
1328             if (i == null || ! tail.mergeable (i))
1329               break;
1330             tail = i;
1331           }
1332         if (head != tail)
1333           merge_nodes (head, tail);
1334       }
1335
1336       public void Pop (int start, int end)
1337       {
1338         update_from_to ();
1339         M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
1340         if (start < From)
1341           {
1342             if (end <= From)
1343               {
1344                 Left.Pop (start, end);
1345                 return;
1346               }
1347             Left.Pop (start, From);
1348             start = From;
1349           }
1350         if (end > To)
1351           {
1352             if (start >= To)
1353               {
1354                 Right.Pop (start, end);
1355                 return;
1356               }
1357             Right.Pop (To, end);
1358             end = To;
1359           }
1360
1361         if (! Stack.IsEmpty)
1362           {
1363             if (start > From)
1364               divide_left (start);
1365             if (end < To)
1366               divide_right (end);
1367             Stack.Pop ();
1368           }
1369       }
1370
1371       private void DumpOne (bool with_prop, bool newline)
1372       {
1373         DumpOne (with_prop, newline, false);
1374       }
1375
1376       private void DumpOne (bool with_prop, bool newline, bool force)
1377       {
1378         if (force || M17N.debug)
1379           {
1380             Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
1381             if (with_prop)
1382               foreach (MPlist p in Stack)
1383                 Console.Write (" " + p.Val);
1384             Console.Write (")");
1385             if (newline)
1386               Console.WriteLine ();
1387             if (Length <= 0)
1388               throw new Exception ("Invalid interval length");
1389           }
1390       }
1391
1392       public void Dump () { Dump (false); }
1393
1394       public void Dump (bool force)
1395       {
1396         if (force || M17N.debug)
1397           {
1398             update_from_to ();
1399
1400             if (Left != null)
1401               Left.Dump (force);
1402             if (From > 0)
1403               Console.Write (" ");
1404             DumpOne (true, false, force);
1405             if (Right != null)
1406               Right.Dump (force);
1407           }
1408       }
1409
1410       private int Depth {
1411         get { return (Parent == null ? 0 : Parent.Depth + 1); }
1412       }
1413
1414       public void DumpNested (bool force)
1415       {
1416         DumpNested ("", force);
1417       }
1418
1419       public void DumpNested (string indent, bool force)
1420       {
1421         if (force || M17N.debug)
1422           {
1423             int indent_type = (Parent == null ? 1
1424                                : Parent.Left == this ? 0 : 2);
1425
1426             update_from_to ();
1427             if (Left != null)
1428               {
1429                 if (indent_type <= 1)
1430                   Left.DumpNested (indent + "  ", force);
1431                 else
1432                   Left.DumpNested (indent + "| ", force);
1433               }
1434             if (indent_type == 0)
1435               Console.Write (indent + ".-");
1436             else if (indent_type == 2)
1437               Console.Write (indent + "`-");
1438             DumpOne (true, true, true);
1439             if (Right != null)
1440               {
1441                 if (indent_type >= 1)
1442                   Right.DumpNested (indent + "  ", force);
1443                 else
1444                   Right.DumpNested (indent + "| ", force);
1445               }
1446           }
1447       }
1448     }
1449
1450     private class MTextEnum : IEnumerator
1451     {
1452       private MText mt;
1453       private int pos = -1;
1454
1455       public MTextEnum (MText mt)
1456         {
1457           this.mt = mt;
1458         }
1459
1460       public bool MoveNext ()
1461       {
1462         pos++;
1463         return (pos < mt.nchars);
1464       }
1465
1466       public void Reset ()
1467       {
1468         pos = -1;
1469       }
1470
1471       public object Current
1472       {
1473         get {
1474           //if (pos < 0 || pos >= mt.nchars)
1475           //throw new InvalidOperationException ();
1476           return mt[pos];
1477         }
1478       }
1479     }
1480   }
1481 }