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