9a4434aae211f83780223f83f669cfd8f1880949
[m17n/m17n-lib-cs.git] / 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             // interval  |<====>---------->|
551             //                 |<aaaa>---->|
552             //                       |<...>|
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 }