1fbb3f0d6f244f65d1d68a638c96da846fd3eb46
[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 #if false
208       if (root_interval != null)
209         {
210           MInterval interval;
211
212           if (mt2.root_interval != null)
213             interval = mt2.root_interval.Copy (from, to);
214           root_interval.Insert (pos, interval);
215         }
216 #endif
217       nchars += to - from;
218     }
219
220     public int this[int i]
221     {
222       set {
223         i = pos_to_idx (this, i);
224         if (value < 0x10000)
225           {
226             if (surrogate_high_p (sb[i]))
227               sb.Remove (i, 1);
228             sb[i] = (char) value;
229           }
230         else
231           {
232             char high = (char) (0xD800 + ((value - 0x10000) >> 10));
233             char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
234
235             if (! surrogate_high_p (sb[i]))
236               sb.Insert (i, 0);
237             sb[i] = high;
238             sb[i + 1] = low;
239           }
240       }
241       get {
242         i = pos_to_idx (this, i);
243         return (surrogate_high_p (sb[i])
244                 ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
245                 : sb[i]);
246       }
247     }
248
249     public MText dup ()
250     {
251       return (new MText (sb.ToString ()));
252     }
253
254     public MText ins (int pos, MText mt)
255     {
256       insert (pos, mt, 0, mt.nchars);
257       return this;
258     }
259
260     public MText ins (int pos, MText mt, int from, int to)
261     {
262       insert (pos, mt, from, to);
263       return this;
264     }
265
266     public MText del (int from, int to)
267     {
268       sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
269       nchars -= to - from;
270       return this;
271     }
272
273     public void PushProp (int from, int to, MTextProperty prop)
274     {
275       if (root_interval == null)
276         root_interval = new MInterval (0, true, sb.Length, true);
277       root_interval.Push (from, to, prop);
278     }
279
280     private class MInterval
281     {
282       // Start and end positions of this interval and its children.
283       // If this is the left node, the values are relative to the
284       // parent's total_start.  Otherwise, the values are relatie to
285       // the parent's total_end.
286       private int total_start, total_end;
287       // Stack of MTextProperty
288       private Stack<MTextProperty> stack;
289       private int depth;
290       private MInterval left, right, parent;
291
292       private static int adjust_position (int pos, bool front_inclusive)
293       {
294         return (pos << 2) + (front_inclusive ? -1 : 1);
295       }
296
297       public MInterval (int start, bool front_inclusive,
298                         int end, bool rear_inclusive)
299       {
300         if (start > end)
301           throw new Exception ("Invalid Interval Range");
302         this.total_start = (start << 2) + (front_inclusive ? -1 : 1);
303         this.total_end = (end << 2) + (rear_inclusive ? 1 : -1);
304         this.stack = new Stack<MTextProperty> ();
305         this.depth = 1;
306       }
307
308       private MInterval (int start, int end, Stack<MTextProperty> stack)
309       {
310         this.total_start = start;
311         this.total_end = end;
312         this.stack = new Stack<MTextProperty> (stack);
313         this.depth = 1;
314       }
315
316       private MInterval find (int pos)
317       {
318         if (pos < total_start || total_end < pos)
319           return null;
320         if (pos < Start)
321           return left.find (pos);
322         if (End < pos)
323           return right.find (pos);
324         return this;
325       }
326
327       public MInterval Copy (int start, int end)
328       {
329         MInterval interval_start = find (start);
330         MInterval interval_end = find (end);
331         MInterval interval;
332
333         start = adjust_position (start, true);
334         end  = adjust_position (end, true);
335         interval = new MInterval (start, end, stack);
336         return interval;
337       }
338
339       private MInterval Copy ()
340       {
341         return new MInterval (total_start, total_end, stack);
342       }
343
344       private int Start {
345         get {
346           return (left == null ? total_start : total_start + left.total_end);
347         }
348       }
349
350       private int End {
351         get {
352           return (right == null ? total_end : total_end + right.total_start);
353         }
354       }
355
356       private MInterval Left {
357         get {
358           MInterval interval;
359
360           if (left != null)
361             for (interval = left;
362                  interval.right != null;
363                  interval = interval.right);
364           else
365             for (interval = parent;
366                  interval != null && interval.total_start == 0;
367                  interval = interval.parent);
368
369           return interval;
370         }
371       }
372
373       private MInterval Right {
374         get {
375           MInterval interval;
376
377           if (right != null)
378             for (interval = right;
379                  interval.left != null;
380                  interval = interval.left);
381           else
382             for (interval = parent;
383                  interval != null && interval.total_start < 0;
384                  interval = interval.parent);
385
386           return interval;
387         }
388       }
389
390       public void Push (int start, int end, MTextProperty prop)
391       {
392         start <<= 2;
393         if (prop.FrontSticky)
394           start--;
395         else
396           start++;
397         end <<= 2;
398         if (prop.RearSticky)
399           end++;
400         else
401           end--;
402         if (start >= end)
403           throw new Exception ("Invalid Text Property Range");
404
405         push (start, end, prop);
406       }
407
408       public void Insert (int start, int end, MInterval interval)
409       {
410       }
411
412       private MInterval divide_right (int pos)
413       {
414         MInterval interval = Copy ();
415         int this_start = Start;
416         int this_end = End;
417
418         if (left == null || (right != null && left.depth < right.depth))
419           {
420             interval.left = this;
421             interval.right = right;
422             interval.parent = parent;
423             if (parent != null)
424               {
425                 if (total_start == 0)
426                   parent.left = interval;
427                 else
428                   parent.right = interval;
429               }
430             interval.depth = depth;
431             if (right == null)
432               interval.depth++;
433             total_start = 0;
434             total_end = pos - this_start;
435           }
436         else
437           {
438             interval.total_start = pos - this_end;
439             interval.total_end = 0;
440             if (right != null)
441               right.parent = interval;
442             right = interval;
443           }
444
445         return interval;
446       }
447
448       private MInterval divide_left (int pos)
449       {
450         MInterval interval = Copy ();
451         int this_start = Start;
452         int this_end = End;
453
454         if (left == null || (right != null && left.depth < right.depth))
455           {
456             interval.total_start = 0;
457             interval.total_end = pos - this_start;
458             if (left != null)
459               left.parent = interval;
460             left = interval;
461           }
462         else
463           {
464             interval.right = this;
465             interval.left = left;
466             interval.parent = parent;
467             if (parent != null)
468               {
469                 if (total_start == 0)
470                   parent.left = interval;
471                 else
472                   parent.right = interval;
473               }
474             interval.depth = depth;
475             if (left == null)
476               interval.depth++;
477             total_start = pos - this_end;
478             total_end = 0;
479           }
480
481         return interval;
482       }
483
484       private void push (int start, int end, MTextProperty prop)
485       {
486         int this_start = Start;
487         int this_end = End;
488
489         if (start < this_start)
490           {
491             if (end <= this_start)
492               {
493                 Left.push (start, end, prop);
494                 return;
495               }
496             Left.push (start, this_start, prop);
497             start = this_start;
498           }
499         if (this_end < end)
500           {
501             if (this_end < start)
502               {
503                 Right.push (start, end, prop);
504                 return;
505               }
506             Right.push (this_end, end, prop);
507             end = this_end;
508           }
509         if (this_start < start)
510           divide_left (start);
511         if (end < this_end)
512           divide_right (end);
513         stack.Push (prop);
514       }
515     }
516
517     private class MTextEnum : IEnumerator
518     {
519       private MText mt;
520       private int pos = -1;
521
522       public MTextEnum (MText mt)
523         {
524           this.mt = mt;
525         }
526
527       public bool MoveNext ()
528       {
529         pos++;
530         return (pos < mt.nchars);
531       }
532
533       public void Reset ()
534       {
535         pos = -1;
536       }
537
538       public object Current
539       {
540         get {
541           //if (pos < 0 || pos >= mt.nchars)
542           //throw new InvalidOperationException ();
543           return mt[pos];
544         }
545       }
546     }
547   }
548 }