using System;
using System.Text;
+using System.Collections;
+using System.Collections.Generic;
using M17N.Core;
namespace M17N.Core
{
#if false
public enum MTextFormat
+ {
+ MTEXT_FORMAT_US_ASCII,
+ MTEXT_FORMAT_UTF_8,
+ MTEXT_FORMAT_UTF_16BE,
+ MTEXT_FORMAT_UTF_16LE,
+ MTEXT_FORMAT_UTF_32BE,
+ MTEXT_FORMAT_UTF_32LE,
+ }
+#endif
+
+ public class MTextProperty
{
- MTEXT_FORMAT_US_ASCII,
- MTEXT_FORMAT_UTF_8,
- MTEXT_FORMAT_UTF_16BE,
- MTEXT_FORMAT_UTF_16LE,
- MTEXT_FORMAT_UTF_32BE,
- MTEXT_FORMAT_UTF_32LE,
+ internal MProperty prop;
+ internal bool front_sticky;
+ internal bool rear_sticky;
+ internal bool merginable;
+ public MProperty Prop { get { return prop; } }
+ public bool FrontSticky { get { return front_sticky; } }
+ public bool RearSticky { get { return rear_sticky; } }
+ public bool Merginable { get { return merginable; } }
+
+ public MTextProperty (bool front_sticky, bool rear_sticky)
+ {
+ this.front_sticky = front_sticky;
+ this.rear_sticky = rear_sticky;
+ }
+ public MTextProperty (bool front_sticky, bool rear_sticky, bool merginable)
+ {
+ this.front_sticky = front_sticky;
+ this.rear_sticky = rear_sticky;
+ this.merginable = merginable;
+ }
}
-#endif
- public class MText
+ public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
{
#if false
public enum MTextFormat format;
#endif
- private class MTextPlist : MPlist
+ private StringBuilder sb;
+ private int nchars;
+ private int cache_pos;
+ private int cache_idx;
+ private MInterval root_interval;
+ private bool read_only;
+
+ private static UTF8Encoding utf8 = new UTF8Encoding ();
+
+ private static int count_chars (String str)
{
- public class MInterval
+ int len = str.Length, n = 0;
+
+ for (int i = 0; i < len; i++, n++)
+ if (surrogate_high_p (str[i]))
+ i++;
+ return n;
+ }
+
+ private static int count_chars (StringBuilder str)
+ {
+ int len = str.Length, n = 0;
+
+ for (int i = 0; i < len; i++, n++)
+ if (surrogate_high_p (str[i]))
+ i++;
+ return n;
+ }
+
+ public MText ()
+ {
+ sb = new StringBuilder ();
+ }
+
+ public MText (byte[] str)
{
- MPlist stack;
- int nprops;
- public int start, end;
- public MInterval prev, next;
+ sb = new StringBuilder (utf8.GetString (str));
+ nchars = count_chars (sb);
}
- MInterval head, tail;
+ public MText (String str)
+ {
+ sb = new StringBuilder (str);
+ nchars = count_chars (str);
+ }
- public MTextPlist (MText mt)
+ public MText (StringBuilder str)
{
- head = tail = new MInterval ();
- head.start = 0;
- head.end = mt.sb.Length;
+ sb = str;
+ nchars = count_chars (str);
}
+
+ public static MText operator+ (MText mt1, MText mt2)
+ {
+ MText mt = new MText ();
+
+ mt.sb.Append (mt1.sb);
+ mt.sb.Append (mt2.sb);
+ mt.nchars = mt1.nchars + mt2.nchars;
+ return mt;
}
- private StringBuilder sb;
- private int cache_pos;
- private int cache_idx;
- private MTextPlist plist;
+ // Public properties
+ public bool ReadOnly { get { return read_only; } }
+ public int Length { get { return nchars; } }
- private static UTF8Encoding utf8 = new UTF8Encoding ();
- private static UTF32Encoding utf32 = new UTF8Encoding ();
+ // Public methods
- public MText ()
+ // for IEnumerable interface
+ public IEnumerator GetEnumerator() { return new MTextEnum (this); }
+
+ // for IEquatable interface
+ public bool Equals (MText other) { return this.sb.Equals (other.sb); }
+
+ // for IComparable interface
+ public int CompareTo (MText other)
{
- cache_pos = cache_idx = 0;
- plist = null;
- sb = new StringBuilder ();
+ return this.sb.ToString ().CompareTo (other.sb.ToString ());
}
- public MText (byte[] str)
+ public override String ToString () { return sb.ToString (); }
+
+ private static bool surrogate_high_p (char c)
{
- sb = new StringBuilder (utf8.GetString (str));
+ return (c >= 0xD800 && c < 0xDC00);
}
- public MText (String str)
+ private static bool surrogate_low_p (char c)
{
- sb = new StringBuilder (str);
+ return (c >= 0xDC00 && c < 0xE000);
}
- private static int inc_idx (int i)
+ private static int inc_idx (StringBuilder sb, int i)
{
- return ((sb[i] >= 0xD800 && sb[i] < 0xDC00)
- ? i + 2 : i + 1);
+ return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
}
- private static int dec_idx (int i)
+ private static int dec_idx (StringBuilder sb, int i)
{
- return ((sb[i - 1] >= 0xDC00 && sb[i - 1] < 0xE000)
- ? i - 2 : i - 1);
+ return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
}
- private static int pos_to_idx (int pos)
+ private static int pos_to_idx (MText mt, int pos)
{
+ if (pos == mt.cache_pos)
+ return mt.cache_idx;
+
int p, i;
bool forward;
- if (pos < cache_pos)
+ if (pos < mt.cache_pos)
{
- if (cache_pos == cache_idx)
- return cache_idx;
- if (pos < cache_pos - pos)
+ if (mt.cache_pos == mt.cache_idx)
+ return mt.cache_idx;
+ if (pos < mt.cache_pos - pos)
{
p = i = 0;
forward = true;
}
else
{
- p = cache_pos; i = cache_idx;
+ p = mt.cache_pos; i = mt.cache_idx;
forward = false;
}
}
else
{
- if (nchars - cache_pos == sb.Length - cache_idx)
- return (cache_idx + pos - cache_pos);
- if (pos - cache_pos < nchars - pos)
+ if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
+ return (mt.cache_idx + pos - mt.cache_pos);
+ if (pos - mt.cache_pos < mt.nchars - pos)
{
- p = char_pos; i = char_idx;
+ p = mt.cache_pos; i = mt.cache_idx;
forward = true;
}
else
{
- p = nchars; i = sb.Length;
+ p = mt.nchars; i = mt.sb.Length;
forward = false;
}
}
if (forward)
- for (; p < pos; i = inc_idx (i), p++);
+ for (; p < pos; i = inc_idx (mt.sb, i), p++);
else
- for (; p > pos; i = dec_idx (i), p--);
- cache_pos = p;
- cache_idx = i;
+ for (; p > pos; i = dec_idx (mt.sb, i), p--);
+ mt.cache_pos = p;
+ mt.cache_idx = i;
return i;
}
+ private void insert (int pos, MText mt2, int from, int to)
+ {
+ int pos_idx = pos_to_idx (this, pos);
+ int from_idx = pos_to_idx (mt2, from);
+ int to_idx = pos_to_idx (mt2, to);
+
+ sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
+ nchars += to - from;
+ if (root_interval != null)
+ {
+ MInterval interval = (mt2.root_interval == null
+ ? new MInterval (0, false, to - from, false)
+ : mt2.root_interval.CopyTree (from, to));
+ root_interval.Insert (pos, interval);
+ }
+ }
+
public int this[int i]
{
set {
- if (i != cache_pos)
- i = pos_to_idx (i);
+ i = pos_to_idx (this, i);
if (value < 0x10000)
- this.sb[i] = (char) value;
+ {
+ if (surrogate_high_p (sb[i]))
+ sb.Remove (i, 1);
+ sb[i] = (char) value;
+ }
+ else
+ {
+ char high = (char) (0xD800 + ((value - 0x10000) >> 10));
+ char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));
+
+ if (! surrogate_high_p (sb[i]))
+ sb.Insert (i, 0);
+ sb[i] = high;
+ sb[i + 1] = low;
+ }
+ }
+ get {
+ i = pos_to_idx (this, i);
+ return (surrogate_high_p (sb[i])
+ ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
+ : sb[i]);
+ }
+ }
+
+ public MText dup ()
+ {
+ return (new MText (sb.ToString ()));
+ }
+
+ public MText ins (int pos, MText mt)
+ {
+ insert (pos, mt, 0, mt.nchars);
+ return this;
+ }
+
+ public MText ins (int pos, MText mt, int from, int to)
+ {
+ insert (pos, mt, from, to);
+ return this;
+ }
+
+ public MText del (int from, int to)
+ {
+ sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
+ nchars -= to - from;
+ return this;
+ }
+
+ public void PushProp (int from, int to, MTextProperty prop)
+ {
+ if (root_interval == null)
+ root_interval = new MInterval (this);
+ root_interval.Push (from, to, prop);
+ }
+
+ private class MInterval
+ {
+ // position: 0 1 2 3
+ // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
+ // | | A | | B | | C | |
+ // interval |<--------->|<--->|<--------------->|<------
+ //
+ // [-1 99 (9 89)]
+ // [0 10 (-1 9)] [-10 0 (89 99)]
+ // [0 4 (-1 3)] [-4 0 (5 9)] [0 4 (89 93)] [-2 0 (97 99)]
+ //
+ // Start and end positions of this interval and its children.
+ // If this is the left node, the values are relative to the
+ // parent's total_start. Otherwise, the values are relatie to
+ // the parent's total_end.
+ private int total_start, total_end;
+ // Stack of MTextProperty
+ private Stack<MTextProperty> stack;
+ private MInterval left, right, parent;
+ private MText mt;
+
+ private static int adjust_position (int pos, bool front_inclusive)
+ {
+ return (pos << 2) + (front_inclusive ? -1 : 1);
+ }
+
+ private static bool before_point_p (int pos)
+ {
+ return ((pos + 1) % 4) == 0;
+ }
+
+ public MInterval (int start, bool front_inclusive,
+ int end, bool rear_inclusive)
+ {
+ if (start > end)
+ throw new Exception ("Invalid Interval Range");
+ this.total_start = (start << 2) + (front_inclusive ? -1 : 1);
+ this.total_end = (end << 2) + (rear_inclusive ? 1 : -1);
+ this.stack = new Stack<MTextProperty> ();
+ }
+
+ public MInterval (MText mt)
+ {
+ this.mt = mt;
+ this.total_start = -1;
+ this.total_end = (mt.sb.Length << 2) + 1;
+ this.stack = new Stack<MTextProperty> ();
+ }
+
+ private MInterval () { }
+
+ private MInterval (int start, int end, Stack<MTextProperty> stack)
+ {
+ this.total_start = start;
+ this.total_end = end;
+ this.stack = new Stack<MTextProperty> (stack);
+ }
+
+ private MInterval find (int pos, out int offset)
+ {
+ if (pos < total_start || total_end < pos)
+ {
+ offset = 0;
+ return null;
+ }
+ if (pos < Start)
+ return left.find (pos, out offset);
+ if (End < pos)
+ return right.find (pos - total_end, out offset);
+ offset = pos - Start;
+ return this;
+ }
+
+ // p-. or .-p p-. or .-p
+ // .-this-. .-right-.
+ // left .-right-. -> .-this-. c2
+ // c1 c2 left c1
+ private MInterval promote_right ()
+ {
+ int right_length = - right.total_start;
+ MInterval c1;
+
+ if (parent == null)
+ mt.root_interval = right;
+ else if (total_start == 0)
+ parent.left = right;
+ else
+ parent.right = right;
+ right.parent = parent;
+ c1 = right.left;
+ right.left = this;
+
+ parent = right;
+ right = c1;
+ if (c1 != null)
+ c1.parent = this;
+
+ parent.total_start = total_start;
+ parent.total_end = total_end;
+ total_start = 0;
+ total_end -= right_length - (c1 == null ? 0 : c1.total_end);
+
+ if (c1 != null)
+ {
+ c1.total_end = - c1.total_start;
+ c1.total_start = 0;
+ }
+ return parent;
+ }
+
+ // p-. or .-p p-. or .-p
+ // .-this-. .-left-.
+ // .-left-. .-right-. -> c1 .-this-.
+ // c1 c2 c2 right
+ private MInterval promote_left ()
+ {
+ int left_length = left.total_end;
+ MInterval c2;
+
+ if (parent == null)
+ mt.root_interval = left;
+ else if (total_start == 0)
+ parent.left = left;
+ else
+ parent.right = left;
+ left.parent = parent;
+ c2 = left.right;
+ left.right = this;
+
+ parent = left;
+ left = c2;
+ if (c2 != null)
+ c2.parent = this;
+
+ parent.total_start = total_start;
+ parent.total_end = total_end;
+ total_start -= left_length + (c2 == null ? 0 : c2.total_end);;
+ total_end = 0;
+
+ if (c2 != null)
+ {
+ c2.total_start = - c2.total_end;
+ c2.total_end = 0;
+ }
+ return parent;
+ }
+
+ private MInterval balance ()
+ {
+ MInterval interval = this;
+
+ while (true)
+ {
+ int this_start = interval.Start;
+ int this_end = interval.End;
+ int diff = ((this_start - interval.total_start)
+ - (interval.total_end - this_end));
+ int abs = Math.Abs (diff);
+
+ if (abs < this_end - this_start)
+ break;
+ if (diff < 0)
+ {
+ interval = interval.promote_right ();
+ interval.left.balance ();
+ }
+ else
+ {
+ interval = interval.promote_left ();
+ interval.right.balance ();
+ }
+ }
+ return interval;
+ }
+
+ public MInterval CopyTree (int start, int end)
+ {
+ MInterval interval_start, interval_end, interval;
+ int offset_start, offset_end;
+
+ start <<= 2;
+ end <<= 2;
+ interval_start = find (start, out offset_start);
+ interval_end = find (end, out offset_end);
+
+ interval = new MInterval ();
+ interval.total_start = 0;
+ interval.total_end = end - start;
+ interval.stack = new Stack<MTextProperty> (interval_start.stack);
+ interval = interval.divide_right (offset_start);
+ while (interval_start != interval_end)
+ {
+ interval_start = interval_start.Right;
+ interval = interval.divide_right (interval_start.End
+ - interval_start.Start);
+ }
+ return interval;
+ }
+
+ private MInterval CopyNode ()
+ {
+ return new MInterval (total_start, total_end, stack);
+ }
+
+ private int Start {
+ get {
+ return (left == null ? total_start : total_start + left.total_end);
+ }
+ }
+
+ private int End {
+ get {
+ return (right == null ? total_end : total_end + right.total_start);
+ }
+ }
+
+ private MInterval Left {
+ get {
+ MInterval interval;
+
+ if (left != null)
+ for (interval = left;
+ interval.right != null;
+ interval = interval.right);
+ else
+ for (interval = parent;
+ interval != null && interval.total_start == 0;
+ interval = interval.parent);
+
+ return interval;
+ }
+ }
+
+ private MInterval Right {
+ get {
+ MInterval interval;
+
+ if (right != null)
+ for (interval = right;
+ interval.left != null;
+ interval = interval.left);
+ else
+ for (interval = parent;
+ interval != null && interval.total_start < 0;
+ interval = interval.parent);
+
+ return interval;
+ }
+ }
+
+ public void Push (int start, int end, MTextProperty prop)
+ {
+ start <<= 2;
+ if (prop.FrontSticky)
+ start--;
+ else
+ start++;
+ end <<= 2;
+ if (prop.RearSticky)
+ end++;
+ else
+ end--;
+ if (start >= end)
+ throw new Exception ("Invalid Text Property Range");
+
+ push (start, end, prop);
+ }
+
+ public void Insert (int pos, MInterval interval)
+ {
+ if (pos < Start)
+ Left.Insert (pos - total_start, interval);
+ else if (pos > End)
+ Right.Insert (pos - total_end, interval);
else
{
+ // position: 0 1 2 3
+ // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
+ // this |<----------<-------------->->|
+ // |<--------->| |<>|
+ //
+ // interval |<->----->->|
+ //
+ // new |<----------<----->----->-->------------>->|
+ // |<--------->| |<---->-->------------>->|
+ // |<----------->->|
+ // |<>|
+ int len = interval.total_end - interval.total_start;
+ MInterval temp;
+
+ total_end += len;
+ for (temp = this; temp.parent != null;
+ temp = temp.parent)
+ temp.parent.total_end += len;
+ if (End - pos < interval.End)
+ {
+
+
+ }
+
+ temp = divide_right (Start + 2);
+ temp.left = interval;
+ right = interval;
+ }
+
+ }
+
+ private MInterval divide_right (int pos)
+ {
+ MInterval interval = CopyNode ();
+ int this_start = Start;
+ int this_end = End;
+
+ if (left == null
+ || (right != null && left.total_end < - right.total_start))
+ {
+ interval.left = this;
+ interval.right = right;
+ interval.parent = parent;
+ if (parent != null)
+ {
+ if (total_start == 0)
+ parent.left = interval;
+ else
+ parent.right = interval;
+ }
+ total_start = 0;
+ total_end = pos - this_start;
+ }
+ else
+ {
+ interval.total_start = pos - this_end;
+ interval.total_end = 0;
+ if (right != null)
+ right.parent = interval;
+ right = interval;
+ }
+
+ return interval;
+ }
+
+ private MInterval divide_left (int pos)
+ {
+ MInterval interval = CopyNode ();
+ int this_start = Start;
+ int this_end = End;
+
+ if (left == null
+ || (right != null && left.total_end < - right.total_start))
+ {
+ interval.total_start = 0;
+ interval.total_end = pos - this_start;
+ if (left != null)
+ left.parent = interval;
+ left = interval;
+ }
+ else
+ {
+ interval.right = this;
+ interval.left = left;
+ interval.parent = parent;
+ if (parent != null)
+ {
+ if (total_start == 0)
+ parent.left = interval;
+ else
+ parent.right = interval;
+ }
+ total_start = pos - this_end;
+ total_end = 0;
}
+
+ return interval;
+ }
+
+ private void push (int start, int end, MTextProperty prop)
+ {
+ int this_start = Start;
+ int this_end = End;
+
+ if (start < this_start)
+ {
+ if (end <= this_start)
+ {
+ Left.push (start, end, prop);
+ return;
+ }
+ Left.push (start, this_start, prop);
+ start = this_start;
+ }
+ if (this_end < end)
+ {
+ if (this_end < start)
+ {
+ Right.push (start, end, prop);
+ return;
+ }
+ Right.push (this_end, end, prop);
+ end = this_end;
+ }
+ if (this_start < start)
+ divide_left (start);
+ if (end < this_end)
+ divide_right (end);
+ stack.Push (prop);
}
- get { return this.sb[i]; }
}
- public class MTextProperty
- {
+ private class MTextEnum : IEnumerator
+ {
+ private MText mt;
+ private int pos = -1;
+
+ public MTextEnum (MText mt)
+ {
+ this.mt = mt;
+ }
+
+ public bool MoveNext ()
+ {
+ pos++;
+ return (pos < mt.nchars);
+ }
+
+ public void Reset ()
+ {
+ pos = -1;
+ }
+
+ public object Current
+ {
+ get {
+ //if (pos < 0 || pos >= mt.nchars)
+ //throw new InvalidOperationException ();
+ return mt[pos];
+ }
+ }
+ }
}
}
projects / m17n / m17n-lib-cs.git / blobdiff