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