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