MText.cs

   1 using System;
   2 using System.Text;
   3 using System.Collections;
   4 using System.Collections.Generic;
   5 using M17N.Core;
   6
   7 namespace M17N.Core
   8 {
   9 #if false
  10   public enum MTextFormat
  11     {
  12       MTEXT_FORMAT_US_ASCII,
  13       MTEXT_FORMAT_UTF_8,
  14       MTEXT_FORMAT_UTF_16BE,
  15       MTEXT_FORMAT_UTF_16LE,
  16       MTEXT_FORMAT_UTF_32BE,
  17       MTEXT_FORMAT_UTF_32LE,
  18     }
  19 #endif
  20
  21   public class MTextProperty
  22   {
  23     internal MProperty prop;
  24     internal bool front_sticky;
  25     internal bool rear_sticky;
  26     internal bool merginable;
  27     public MProperty Prop { get { return prop; } }
  28     public bool FrontSticky { get { return front_sticky; } }
  29     public bool RearSticky { get { return rear_sticky; } }
  30     public bool Merginable { get { return merginable; } }
  31
  32     public MTextProperty (bool front_sticky, bool rear_sticky)
  33     {
  34       this.front_sticky = front_sticky;
  35       this.rear_sticky = rear_sticky;
  36     }
  37     public MTextProperty (bool front_sticky, bool rear_sticky, bool merginable)
  38     {
  39       this.front_sticky = front_sticky;
  40       this.rear_sticky = rear_sticky;
  41       this.merginable = merginable;
  42     }
  43   }
  44
  45   public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
  46   {
  47 #if false
  48     public enum MTextFormat format;
  49 #endif
  50
  51     private StringBuilder sb;
  52     private int nchars;
  53     private int cache_pos;
  54     private int cache_idx;
  55     private MInterval root_interval;
  56     private bool read_only;
  57
  58     private static UTF8Encoding utf8 = new UTF8Encoding ();
  59
  60     private static int count_chars (String str)
  61     {
  62       int len = str.Length, n = 0;
  63
  64       for (int i = 0; i < len; i++, n++)
  65         if (surrogate_high_p (str[i]))
  66           i++;
  67       return n;
  68     }
  69
  70     private static int count_chars (StringBuilder str)
  71     {
  72       int len = str.Length, n = 0;
  73
  74       for (int i = 0; i < len; i++, n++)
  75         if (surrogate_high_p (str[i]))
  76           i++;
  77       return n;
  78     }
  79
  80     public MText ()
  81       {
  82         sb = new StringBuilder ();
  83       }
  84
  85     public MText (byte[] str)
  86       {
  87         sb = new StringBuilder (utf8.GetString (str));
  88         nchars = count_chars (sb);
  89       }
  90
  91     public MText (String str)
  92       {
  93         sb = new StringBuilder (str);
  94         nchars = count_chars (str);
  95       }
  96
  97     public MText (StringBuilder str)
  98       {
  99         sb = str;
 100         nchars = count_chars (str);
 101       }
 102
 103     public static MText operator+ (MText mt1, MText mt2)
 104     {
 105       MText mt = new MText ();
 106
 107       mt.sb.Append (mt1.sb);
 108       mt.sb.Append (mt2.sb);
 109       mt.nchars = mt1.nchars + mt2.nchars;
 110       return mt;
 111     }
 112
 113     // Public properties
 114     public bool ReadOnly { get { return read_only; } }
 115     public int Length { get { return nchars; } }
 116
 117     // Public methods
 118
 119     // for IEnumerable interface
 120     public IEnumerator GetEnumerator() { return new MTextEnum (this); }
 121
 122     // for IEquatable interface
 123     public bool Equals (MText other) { return this.sb.Equals (other.sb); }
 124
 125     // for IComparable interface
 126     public int CompareTo (MText other)
 127     {
 128       return this.sb.ToString ().CompareTo (other.sb.ToString ());
 129     }
 130
 131     public override String ToString () { return sb.ToString (); }
 132
 133     private static bool surrogate_high_p (char c)
 134     {
 135       return (c >= 0xD800 && c < 0xDC00);
 136     }
 137
 138     private static bool surrogate_low_p (char c)
 139     {
 140       return (c >= 0xDC00 && c < 0xE000);
 141     }
 142
 143     private static int inc_idx (StringBuilder sb, int i)
 144     {
 145       return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
 146     }
 147
 148     private static int dec_idx (StringBuilder sb, int i)
 149     {
 150       return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
 151     }
 152
 153     private static int pos_to_idx (MText mt, int pos)
 154     {
 155       if (pos == mt.cache_pos)
 156         return mt.cache_idx;
 157
 158       int p, i;
 159       bool forward;
 160
 161       if (pos < mt.cache_pos)
 162         {
 163           if (mt.cache_pos == mt.cache_idx)
 164             return mt.cache_idx;
 165           if (pos < mt.cache_pos - pos)
 166             {
 167               p = i = 0;
 168               forward = true;
 169             }
 170           else
 171             {
 172               p = mt.cache_pos; i = mt.cache_idx;
 173               forward = false;
 174             }
 175         }
 176       else
 177         {
 178           if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
 179             return (mt.cache_idx + pos - mt.cache_pos);
 180           if (pos - mt.cache_pos < mt.nchars - pos)
 181             {
 182               p = mt.cache_pos; i = mt.cache_idx;
 183               forward = true;
 184             }
 185           else
 186             {
 187               p = mt.nchars; i = mt.sb.Length;
 188               forward = false;
 189             }
 190         }
 191       if (forward)
 192         for (; p < pos; i = inc_idx (mt.sb, i), p++);
 193       else
 194         for (; p > pos; i = dec_idx (mt.sb, i), p--);
 195       mt.cache_pos = p;
 196       mt.cache_idx = i;
 197       return i;
 198     }
 199
 200     private void insert (int pos, MText mt2, int from, int to)
 201     {
 202       int pos_idx = pos_to_idx (this, pos);
 203       int from_idx = pos_to_idx (mt2, from);
 204       int to_idx = pos_to_idx (mt2, to);
 205
 206       sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
 207       nchars += to - from;
 208       if (root_interval != null)
 209         {
 210           MInterval interval = (mt2.root_interval == null
 211                                 ? new MInterval (0, false, to - from, false)
 212                                 : mt2.root_interval.CopyTree (from, to));
 213           root_interval.Insert (pos, interval);
 214         }
 215     }
 216
 217     public int this[int i]
 218     {
 219       set {
 220         i = pos_to_idx (this, i);
 221         if (value < 0x10000)
 222           {
 223             if (surrogate_high_p (sb[i]))
 224               sb.Remove (i, 1);
 225             sb[i] = (char) value;
 226           }
 227         else
 228           {
 229             char high = (char) (0xD800 + ((value - 0x10000) >> 10));
 230             char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
 231
 232             if (! surrogate_high_p (sb[i]))
 233               sb.Insert (i, 0);
 234             sb[i] = high;
 235             sb[i + 1] = low;
 236           }
 237       }
 238       get {
 239         i = pos_to_idx (this, i);
 240         return (surrogate_high_p (sb[i])
 241                 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
 242                 : sb[i]);
 243       }
 244     }
 245
 246     public MText dup ()
 247     {
 248       return (new MText (sb.ToString ()));
 249     }
 250
 251     public MText ins (int pos, MText mt)
 252     {
 253       insert (pos, mt, 0, mt.nchars);
 254       return this;
 255     }
 256
 257     public MText ins (int pos, MText mt, int from, int to)
 258     {
 259       insert (pos, mt, from, to);
 260       return this;
 261     }
 262
 263     public MText del (int from, int to)
 264     {
 265       sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
 266       nchars -= to - from;
 267       return this;
 268     }
 269
 270     public void PushProp (int from, int to, MTextProperty prop)
 271     {
 272       if (root_interval == null)
 273         root_interval = new MInterval (this);
 274       root_interval.Push (from, to, prop);
 275     }
 276
 277     private class MInterval
 278     {
 279       // position:    0           1           2           3
 280       // index:   -1  0  1  2  3  4  5  6  7  8  9  10 11 12 13
 281       //           |     |  A  |     |  B  |     |  C  |     |
 282       // interval  |<--------->|<--->|<--------------->|<----|
 283       //
 284       //                   [-1 99 (9 89)]
 285       //       [0 10 (-1 9)]            [-10 0 (89 99)]
 286       // [0 4 (-1 3)] [-4 0 (5 9)] [0 4 (89 93)] [-2 0 (97 99)]
 287       //
 288       // Start and end positions of this interval and its children.
 289       // If this is the left node, the values are relative to the
 290       // parent's total_start.  Otherwise, the values are relative to
 291       // the parent's total_end.  So:
 292       //                       total_start    total_end
 293       //   left-side interval  0              positive even
 294       //   right-side interval negative even  0
 295       //   top-most interval   -1             positive odd
 296       private int total_start, total_end;
 297       // Stack of MTextProperty
 298       private Stack<MTextProperty> stack;
 299       private MInterval left, right, parent;
 300       private MText mt;
 301
 302       private static int adjust_position (int pos, bool front_inclusive)
 303       {
 304         return (pos << 2) + (front_inclusive ? -1 : 1);
 305       }
 306
 307       private static bool before_point_p (int pos)
 308       {
 309         return ((pos + 1) % 4) == 0;
 310       }
 311
 312       public MInterval (int start, bool front_inclusive,
 313                         int end, bool rear_inclusive)
 314       {
 315         if (start > end)
 316           throw new Exception ("Invalid Interval Range");
 317         this.total_start = (start << 2) + (front_inclusive ? -1 : 1);
 318         this.total_end = (end << 2) + (rear_inclusive ? 1 : -1);
 319         this.stack = new Stack<MTextProperty> ();
 320       }
 321
 322       public MInterval (MText mt)
 323       {
 324         this.mt = mt;
 325         this.total_start = -1;
 326         this.total_end = (mt.sb.Length << 2) + 1;
 327         this.stack = new Stack<MTextProperty> ();
 328       }
 329
 330       private MInterval () { }
 331
 332       private MInterval (int start, int end, Stack<MTextProperty> stack)
 333       {
 334         this.total_start = start;
 335         this.total_end = end;
 336         this.stack = new Stack<MTextProperty> (stack);
 337       }
 338
 339       private MInterval find (int pos, out int offset)
 340       {
 341         if (pos < total_start || total_end < pos)
 342           {
 343             offset = 0;
 344             return null;
 345           }
 346         if (pos < Start)
 347           return left.find (pos, out offset);
 348         if (End < pos)
 349           return right.find (pos - total_end, out offset);
 350         offset = pos - Start;
 351         return this;
 352       }
 353
 354       //      p-. or .-p              p-. or .-p
 355       //       .-this-.                .-right-.
 356       //    left   .-right-.  ->   .-this-.    c2
 357       //          c1       c2    left     c1
 358       private MInterval promote_right ()
 359       {
 360         int right_length = - right.total_start;
 361         MInterval c1;
 362
 363         if (parent == null)
 364           mt.root_interval = right;
 365         else if (total_start == 0)
 366           parent.left = right;
 367         else
 368           parent.right = right;
 369         right.parent = parent;
 370         c1 = right.left;
 371         right.left = this;
 372
 373         parent = right;
 374         right = c1;
 375         if (c1 != null)
 376           c1.parent = this;
 377
 378         parent.total_start = total_start;
 379         parent.total_end = total_end;
 380         total_start = 0;
 381         total_end -= right_length - (c1 == null ? 0 : c1.total_end);
 382
 383         if (c1 != null)
 384           {
 385             c1.total_end = - c1.total_start;
 386             c1.total_start = 0;
 387           }
 388         return parent;
 389       }
 390
 391       //      p-. or .-p              p-. or .-p
 392       //       .-this-.                .-left-.
 393       //  .-left-.  .-right-.  ->     c1    .-this-.
 394       // c1      c2                        c2     right
 395       private MInterval promote_left ()
 396       {
 397         int left_length = left.total_end;
 398         MInterval c2;
 399
 400         if (parent == null)
 401           mt.root_interval = left;
 402         else if (total_start == 0)
 403           parent.left = left;
 404         else
 405           parent.right = left;
 406         left.parent = parent;
 407         c2 = left.right;
 408         left.right = this;
 409
 410         parent = left;
 411         left = c2;
 412         if (c2 != null)
 413           c2.parent = this;
 414
 415         parent.total_start = total_start;
 416         parent.total_end = total_end;
 417         total_start -= left_length + (c2 == null ? 0 : c2.total_end);;
 418         total_end = 0;
 419
 420         if (c2 != null)
 421           {
 422             c2.total_start = - c2.total_end;
 423             c2.total_end = 0;
 424           }
 425         return parent;
 426       }
 427
 428       private MInterval balance ()
 429       {
 430         MInterval interval = this;
 431
 432         while (true)
 433           {
 434             int this_start = interval.Start;
 435             int this_end = interval.End;
 436             int diff = ((this_start - interval.total_start)
 437                         - (interval.total_end - this_end));
 438             int abs = Math.Abs (diff);
 439
 440             if (abs < this_end - this_start)
 441               break;
 442             if (diff < 0)
 443               {
 444                 interval = interval.promote_right ();
 445                 interval.left.balance ();
 446               }
 447             else
 448               {
 449                 interval = interval.promote_left ();
 450                 interval.right.balance ();
 451               }
 452           }
 453         return interval;
 454       }
 455
 456       public MInterval CopyTree (int start, int end)
 457       {
 458         MInterval interval_start, interval_end, interval;
 459         int offset_start, offset_end;
 460
 461         start <<= 2;
 462         end  <<= 2;
 463         interval_start = find (start, out offset_start);
 464         interval_end = find (end, out offset_end);
 465
 466         interval = new MInterval ();
 467         interval.total_start = 0;
 468         interval.total_end = end - start;
 469         interval.stack = new Stack<MTextProperty> (interval_start.stack);
 470         interval = interval.divide_right (offset_start);
 471         while (interval_start != interval_end)
 472           {
 473             interval_start = interval_start.Right;
 474             interval = interval.divide_right (interval_start.End
 475                                               - interval_start.Start);
 476           }
 477         return interval;
 478       }
 479
 480       private MInterval CopyNode ()
 481       {
 482         return new MInterval (total_start, total_end, stack);
 483       }
 484
 485       private int Start {
 486         get {
 487           return (left == null ? total_start : total_start + left.total_end);
 488         }
 489       }
 490
 491       private int End {
 492         get {
 493           return (right == null ? total_end : total_end + right.total_start);
 494         }
 495       }
 496
 497       private MInterval Left {
 498         get {
 499           MInterval i;
 500           if (left != null)
 501             for (i = left; i.right != null; i = i.right);
 502           else
 503             for (i = parent; i != null && i.total_start == 0; i = i.parent);
 504           return i;
 505         }
 506       }
 507
 508       private MInterval Right {
 509         get {
 510           MInterval i;
 511           if (right != null)
 512             for (i = right; i.left != null; i = i.left);
 513           else
 514             for (i = parent; i != null && i.total_start < 0; i = i.parent);
 515           return i;
 516         }
 517       }
 518
 519       public void Push (int start, int end, MTextProperty prop)
 520       {
 521         start <<= 2;
 522         if (prop.FrontSticky)
 523           start--;
 524         else
 525           start++;
 526         end <<= 2;
 527         if (prop.RearSticky)
 528           end++;
 529         else
 530           end--;
 531         if (start >= end)
 532           throw new Exception ("Invalid Text Property Range");
 533
 534         push (start, end, prop);
 535       }
 536
 537       public void Insert (int pos, MInterval interval)
 538       {
 539         if (pos < Start)
 540           Left.Insert (pos - total_start, interval);
 541         else if (pos > End)
 542           Right.Insert (pos - total_end, interval);
 543         else
 544           {
 545             // position:    0           1           2           3
 546             // index:   -1  0  1  2  3  4  5  6  7  8  9  10 11 12 13
 547             // this      |<----------<----------->---->|
 548             //           |<--------->|           |<--->|
 549             //
 550             //                              BBBBB
 551             //                             AAAAA
 552             // interval                    |<--->|
 553             //
 554             // new       |<----------<----->----->-->------------>->|
 555             //           |<--------->|     |<---->-->------------>->|
 556             //                                      |<----------->->|
 557             //                                                   |<>|
 558             int len = interval.total_end - interval.total_start;
 559             MInterval temp;
 560
 561             total_end += len;
 562             for (temp = this; temp.parent != null;
 563                  temp = temp.parent)
 564               temp.parent.total_end += len;
 565             if (End - pos < interval.End)
 566               {
 567
 568
 569               }
 570
 571             temp = divide_right (Start + 2);
 572             temp.left = interval;
 573             right = interval;
 574           }
 575
 576
 577       }
 578
 579       private MInterval divide_right (int pos)
 580       {
 581         MInterval interval = CopyNode ();
 582         int this_start = Start;
 583         int this_end = End;
 584
 585         if (left == null
 586             || (right != null && left.total_end < - right.total_start))
 587           {
 588             interval.left = this;
 589             interval.right = right;
 590             interval.parent = parent;
 591             if (parent != null)
 592               {
 593                 if (total_start == 0)
 594                   parent.left = interval;
 595                 else
 596                   parent.right = interval;
 597               }
 598             total_start = 0;
 599             total_end = pos - this_start;
 600           }
 601         else
 602           {
 603             interval.total_start = pos - this_end;
 604             interval.total_end = 0;
 605             if (right != null)
 606               right.parent = interval;
 607             right = interval;
 608           }
 609
 610         return interval;
 611       }
 612
 613       private MInterval divide_left (int pos)
 614       {
 615         MInterval interval = CopyNode ();
 616         int this_start = Start;
 617         int this_end = End;
 618
 619         if (left == null
 620             || (right != null && left.total_end < - right.total_start))
 621           {
 622             interval.total_start = 0;
 623             interval.total_end = pos - this_start;
 624             if (left != null)
 625               left.parent = interval;
 626             left = interval;
 627           }
 628         else
 629           {
 630             interval.right = this;
 631             interval.left = left;
 632             interval.parent = parent;
 633             if (parent != null)
 634               {
 635                 if (total_start == 0)
 636                   parent.left = interval;
 637                 else
 638                   parent.right = interval;
 639               }
 640             total_start = pos - this_end;
 641             total_end = 0;
 642           }
 643
 644         return interval;
 645       }
 646
 647       private void push (int start, int end, MTextProperty prop)
 648       {
 649         int this_start = Start;
 650         int this_end = End;
 651
 652         if (start < this_start)
 653           {
 654             if (end <= this_start)
 655               {
 656                 Left.push (start, end, prop);
 657                 return;
 658               }
 659             Left.push (start, this_start, prop);
 660             start = this_start;
 661           }
 662         if (this_end < end)
 663           {
 664             if (this_end < start)
 665               {
 666                 Right.push (start, end, prop);
 667                 return;
 668               }
 669             Right.push (this_end, end, prop);
 670             end = this_end;
 671           }
 672         if (this_start < start)
 673           divide_left (start);
 674         if (end < this_end)
 675           divide_right (end);
 676         stack.Push (prop);
 677       }
 678     }
 679
 680     private class MTextEnum : IEnumerator
 681     {
 682       private MText mt;
 683       private int pos = -1;
 684
 685       public MTextEnum (MText mt)
 686         {
 687           this.mt = mt;
 688         }
 689
 690       public bool MoveNext ()
 691       {
 692         pos++;
 693         return (pos < mt.nchars);
 694       }
 695
 696       public void Reset ()
 697       {
 698         pos = -1;
 699       }
 700
 701       public object Current
 702       {
 703         get {
 704           //if (pos < 0 || pos >= mt.nchars)
 705           //throw new InvalidOperationException ();
 706           return mt[pos];
 707         }
 708       }
 709     }
 710   }
 711 }