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