using System;
using System.Text;
+using System.Collections;
+using System.Collections.Generic;
+using M17N;
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 MSymbol key;
+ internal object val;
+
+ [FlagsAttribute]
+ internal enum Flag : byte
+ {
+ None = 0,
+ FrontSticky = 1,
+ RearSticky = 2,
+ Sensitive = 4
+ };
+ internal Flag flags;
+
+ public MSymbol Key { get { return key; } }
+ public object Val { get { return val; } }
+ public bool FrontSticky
+ {
+ get { return (flags & Flag.FrontSticky) != Flag.None; }
+ }
+ public bool RearSticky
+ {
+ get { return (flags & Flag.RearSticky) != Flag.None; }
+ }
+ public bool Sensitive
+ {
+ get { return (flags & Flag.Sensitive) != Flag.None; }
+ }
+
+ public MTextProperty (MSymbol key, object val)
+ {
+ this.key = key;
+ this.val = val;
+ flags |= Flag.RearSticky;
+ }
+
+ public MTextProperty (MSymbol key, object val,
+ bool front_sticky, bool rear_sticky, bool sensitive)
+ {
+ this.key = key;
+ this.val = val;
+ if (front_sticky)
+ flags |= Flag.FrontSticky;
+ if (rear_sticky)
+ flags |= Flag.RearSticky;
+ if (sensitive)
+ flags |= Flag.Sensitive;
+ }
+
+ public override string ToString ()
+ {
+ return key.ToString () + ":" + val;
+ }
}
-#endif
- public class MText
+ public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
{
#if false
public enum MTextFormat format;
#endif
+ private StringBuilder sb;
+ private int nchars;
+ private int cache_pos;
+ private int cache_idx;
+ private MPlist intervals;
+ private MPlist default_property;
+ private bool read_only;
- private class MTextPlist : MPlist
+ 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 ()
{
- MPlist stack;
- int nprops;
- public int start, end;
- public MInterval prev, next;
+ sb = new StringBuilder ();
+ intervals = new MPlist ();
}
- MInterval head, tail;
+ public MText (byte[] str)
+ {
+ sb = new StringBuilder (utf8.GetString (str));
+ nchars = count_chars (sb);
+ intervals = new MPlist ();
+ }
- public MTextPlist (MText mt)
+ public MText (String str)
{
- head = tail = new MInterval ();
- head.start = 0;
- head.end = mt.sb.Length;
+ sb = new StringBuilder (str);
+ nchars = count_chars (str);
+ intervals = new MPlist ();
}
+
+ public MText (StringBuilder str)
+ {
+ sb = str;
+ nchars = count_chars (str);
+ intervals = new MPlist ();
+ }
+
+ 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 ();
+ // 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)
{
- cache_pos = cache_idx = 0;
- plist = null;
- sb = new StringBuilder (utf8.GetString (str));
+ return (c >= 0xD800 && c < 0xDC00);
}
- public MText (String str)
+ private static bool surrogate_low_p (char c)
+ {
+ return (c >= 0xDC00 && c < 0xE000);
+ }
+
+ private static int inc_idx (StringBuilder sb, int i)
+ {
+ return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
+ }
+
+ private static int dec_idx (StringBuilder sb, int i)
+ {
+ return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
+ }
+
+ 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 < mt.cache_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 = mt.cache_pos; i = mt.cache_idx;
+ forward = false;
+ }
+ }
+ else
+ {
+ 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 = mt.cache_pos; i = mt.cache_idx;
+ forward = true;
+ }
+ else
+ {
+ p = mt.nchars; i = mt.sb.Length;
+ forward = false;
+ }
+ }
+ if (forward)
+ for (; p < pos; i = inc_idx (mt.sb, i), p++);
+ else
+ for (; p > pos; i = dec_idx (mt.sb, i), p--);
+ mt.cache_pos = p;
+ mt.cache_idx = i;
+ return i;
+ }
+
+ private void check_pos (int pos, bool tail_ok)
+ {
+ if (pos < 0 || (tail_ok ? pos > nchars : pos >= nchars))
+ throw new Exception ("Invalid MText position:" + pos);
+ }
+
+ private bool check_range (int from, int to, bool zero_ok)
+ {
+ if (from < 0 || (zero_ok ? from > to : from >= to)
+ || to > nchars)
+ throw new Exception ("Invalid MText range");
+ return (from == to);
+ }
+
+ private void insert (int pos, MText mt2, int from, int to)
+ {
+ check_pos (pos, true);
+
+ 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;
+
+ foreach (MPlist plist in mt2.intervals)
+ if (intervals.Find (plist.Key) == null)
+ intervals.Push (plist.Key, new MInterval (plist.Key, this));
+ foreach (MPlist plist in intervals)
+ {
+ MPlist p = mt2.intervals.Find (plist.Key);
+ MInterval interval;
+
+ if (p == null)
+ interval = new MInterval (plist.Key, this, to - from);
+ else
+ interval = ((MInterval) p.Val).Copy (from, to);
+ ((MInterval) plist.Val).Insert (pos, interval);
+ }
+ }
+
+ private void insert (int pos, int c)
{
- cache_pos = cache_idx = 0;
- plist = null;
- sb = new StringBuilder (str);
+ check_pos (pos, true);
+
+ int pos_idx = pos_to_idx (this, pos);
+
+ if (c < 0x10000)
+ {
+ char ch = (char) c;
+ sb.Insert (pos_idx, ch);
+ }
+ else
+ {
+ char high = (char) (0xD800 + ((c - 0x10000) >> 10));
+ char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF));
+ sb.Insert (pos_idx, low);
+ sb.Insert (pos_idx, high);
+ }
+ nchars++;
+ foreach (MPlist plist in intervals)
+ ((MInterval) plist.Val).Insert (pos,
+ new MInterval (plist.Key, this, 1));
}
public int this[int i]
{
- set { this.sb[i] = (char) value; }
- get { return this.sb[i]; }
+ set {
+ i = pos_to_idx (this, i);
+ if (value < 0x10000)
+ {
+ 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 class MTextProperty
- {
+ public MText Dup ()
+ {
+ MText mt = new MText (sb.ToString ());
+
+ foreach (MPlist p in intervals)
+ mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (0, Length));
+ return mt;
+ }
+
+ public MText Ins (int pos, int c)
+ {
+ insert (pos, c);
+ return this;
+ }
+
+ 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 Cat (int c)
+ {
+ insert (nchars, c);
+ return this;
+ }
+
+ public MText Del (int from, int to)
+ {
+ if (check_range (from, to, true))
+ return this;
+
+ sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
+ nchars -= to - from;
+
+ if (nchars > 0)
+ foreach (MPlist plist in intervals)
+ ((MInterval) plist.Val).Delete (from, to);
+ else
+ intervals = new MPlist ();
+ return this;
+ }
+
+ public object GetProp (int pos, MSymbol key)
+ {
+ check_pos (pos, false);
+
+ MInterval i = (MInterval) intervals.Get (key);
+ if (i == null)
+ return null;
+
+ MTextProperty prop = i.Get (pos);
+ return (prop != null ? prop.Val : null);
+ }
+
+ public object GetProp (int pos, MSymbol key, out MTextProperty prop)
+ {
+ check_pos (pos, false);
+
+ MInterval i = (MInterval) intervals.Get (key);
+ if (i == null)
+ return (prop = null);
+ prop = i.Get (pos);
+ return (prop != null ? prop.Val : null);
+ }
+
+ public object GetProp (int pos, MSymbol key, out MTextProperty[] array)
+ {
+ check_pos (pos, false);
+
+ MInterval i = (MInterval) intervals.Get (key);
+ if (i == null)
+ return (array = null);
+ MTextProperty prop = i.Get (pos, out array);
+ return (prop != null ? prop.Val : null);
+ }
+
+ public void PushProp (int from, int to, MSymbol key, object val)
+ {
+ if (! check_range (from, to, true))
+ PushProp (from, to, new MTextProperty (key, val));
+ }
+
+ public void PushProp (int from, int to, MTextProperty prop)
+ {
+ if (from < 0)
+ {
+ if (default_property == null)
+ default_property = new MPlist ();
+ default_property.Push (prop.key, prop.val);
+ }
+ else
+ {
+ if (check_range (from, to, true))
+ return;
+
+ MPlist p = intervals.Find (prop.key);
+ MInterval root;
+
+ if (p == null)
+ {
+ root = new MInterval (prop.key, this);
+ intervals.Push (prop.key, root);
+ }
+ else
+ root = (MInterval) p.Val;
+
+ root.Push (from, to, prop);
+ }
+ }
+
+ public void PopProp (int from, int to, MSymbol key)
+ {
+ if (from < 0)
+ {
+ if (default_property == null)
+ return;
+ MPlist p = default_property.Find (key);
+
+ if (p != null)
+ p.Pop ();
+ }
+ else
+ {
+ if (check_range (from, to, true))
+ return;
+
+ MPlist p = intervals.Find (key);
+
+ if (p != null)
+ {
+ MInterval root = (MInterval) p.Val;
+ root.Pop (from, to);
+ root.MergeAfterChange (from, to);
+ }
+ }
+ }
+
+ public void DumpProp ()
+ {
+ Console.Write ("(");
+ foreach (MPlist p in intervals)
+ ((MInterval) p.Val).Dump (true);
+ Console.WriteLine (")");
+ }
+
+ public void DumpPropNested ()
+ {
+ foreach (MPlist p in intervals)
+ ((MInterval) p.Val).DumpNested (true);
+ }
+
+ private class MInterval
+ {
+ // position: 0 1 2 3 4 5 6 7
+ // | A | B | C | D | E F | G |
+ // interval |---|---|---|<->|-------|---|
+ // |---|<->|---| |<----->|---|
+ // |<->| |<->| |<->|
+ //
+ // [7 (3 4)]
+ // [3 (1 2)] [3 (4 6)]
+ // [1 (0 1)] [2 (2 3)] [1 (6 7)]
+ //
+ private static int count = 0;
+ private int ID;
+ private int Length;
+ private int From, To;
+ private MSymbol Key;
+ private MPlist Stack;
+ private MInterval Left, Right, Parent;
+ private MText mtext;
+
+ public MInterval (MSymbol key, MText mt, int length)
+ {
+ if (length <= 0)
+ throw new Exception ("Invalid interval length");
+ Key = key;
+ mtext = mt;
+ Length = length;
+ Stack = new MPlist ();
+ ID = count++;
+ }
+
+ public MInterval (MSymbol key, MText mt)
+ {
+ Key = key;
+ mtext = mt;
+ Length = mt.sb.Length;
+ From = 0;
+ To = Length;
+ Stack = new MPlist ();
+ ID = count++;
+ }
+
+ public MTextProperty Get (int pos)
+ {
+ MInterval i = find (pos);
+
+ return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val);
+ }
+
+ public MTextProperty Get (int pos, out MTextProperty[] array)
+ {
+ MInterval i = find (pos);
+
+ if (i.Stack.IsEmpty)
+ {
+ array = null;
+ return null;
+ }
+ array = new MTextProperty[i.Stack.Count];
+
+ int idx;
+ MPlist p;
+ for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
+ array[idx] = (MTextProperty) p.Val;
+ return array[0];
+ }
+
+ private MInterval (MSymbol key, MText mt, int length, MPlist stack)
+ {
+ Key = key;
+ mtext = mt;
+ Length = length;
+ From = 0;
+ To = Length;
+ Stack = stack.Clone ();
+ ID = count++;
+ }
+
+ private void update_from_to ()
+ {
+ if (Parent == null)
+ {
+ From = LeftLength;
+ To = Length - RightLength;
+ }
+ else if (Parent.Left == this)
+ {
+ From = Parent.From - Length + LeftLength;
+ To = Parent.From - RightLength;
+ }
+ else
+ {
+ From = Parent.To + LeftLength;
+ To = Parent.To + Length - RightLength;
+ }
+ }
+
+ private int LeftLength
+ {
+ get { return (Left == null ? 0 : Left.Length); }
+ }
+
+ private int RightLength
+ {
+ get { return (Right == null ? 0 : Right.Length); }
+ }
+
+ private MInterval LeftMost
+ {
+ get { return (Left == null ? this : Left.LeftMost); }
+ }
+
+ private MInterval RightMost
+ {
+ get { return (Right == null ? this : Right.RightMost); }
+ }
+
+ private MInterval Prev {
+ get {
+ MInterval i;
+
+ if (Left != null)
+ for (i = Left; i.Right != null; i = i.Right);
+ else
+ {
+ MInterval child = this;
+ for (i = Parent; i != null && i.Left == child;
+ child = i, i = i.Parent);
+ }
+ return i;
+ }
+ }
+
+ private MInterval Next {
+ get {
+ MInterval i;
+
+ if (Right != null)
+ for (i = Right; i.Left != null; i = i.Left);
+ else
+ {
+ MInterval child = this;
+ for (i = Parent; i != null && i.Right == child;
+ child = i, i = i.Parent);
+ }
+ return i;
+ }
+ }
+
+ private MInterval find (int pos)
+ {
+ update_from_to ();
+ if (pos < From)
+ return Left.find (pos);
+ if (pos >= To)
+ return Right.find (pos);
+ return this;
+ }
+
+ private bool mergeable (MInterval i)
+ {
+ MPlist p1, p2;
+
+ for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
+ p1 = p1.Next, p2 = p2.Next)
+ if (p1.Val != p2.Val)
+ return false;
+ return (p1.IsEmpty && p2.IsEmpty);
+ }
+
+ // p-. or .-p p-. or .-p
+ // .-this-. .-right-.
+ // left .-right-. -> .-this-. c2
+ // c1 c2 left c1
+ private MInterval promote_right ()
+ {
+ int right_length = Right.Length;
+ MInterval c1;
+
+ if (Parent == null)
+ mtext.intervals.Put (Key, Right);
+ else if (Parent.Left == this)
+ Parent.Left = Right;
+ else
+ Parent.Right = Right;
+ Right.Parent = Parent;
+ c1 = Right.Left;
+ Right.Left = this;
+
+ Parent = Right;
+ Right = c1;
+ Parent.Length += Length;
+ Length -= right_length;
+ if (c1 != null)
+ {
+ c1.Parent = this;
+ Parent.Length -= c1.Length;
+ Length += c1.Length;
+ }
+ 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.Length;
+ MInterval c1;
+
+ if (Parent == null)
+ mtext.intervals.Put (Key, Left);
+ else if (Parent.Left == this)
+ Parent.Left = Left;
+ else
+ Parent.Right = Left;
+ Left.Parent = Parent;
+ c1 = Left.Left;
+ Left.Right = this;
+
+ Parent = Left;
+ Left = c1;
+ Parent.Length += Length;
+ Length -= left_length;
+ if (c1 != null)
+ {
+ c1.Parent = this;
+ Parent.Length -= c1.Length;
+ Length += c1.Length;
+ }
+ return Parent;
+ }
+
+ private MInterval balance ()
+ {
+ MInterval i = this;
+
+ while (true)
+ {
+ // .-this-.
+ // .-left-. .-right-.
+ // c1 c2 c3 c4
+ int diff = i.LeftLength - i.RightLength;
+ int new_diff;
+
+ if (diff > 0)
+ {
+ new_diff = (i.Length - i.LeftLength
+ + i.Left.RightLength - i.Left.LeftLength);
+ if (Math.Abs (new_diff) >= diff)
+ break;
+ i = i.promote_left ();
+ i.Right.balance ();
+ }
+ else if (diff < 0)
+ {
+ new_diff = (i.Length - i.RightLength
+ + i.Right.LeftLength - i.Right.RightLength);
+ if (Math.Abs (new_diff) >= diff)
+ break;
+ i = i.promote_right ();
+ i.Left.balance ();
+ }
+ }
+ return i;
+ }
+
+ public MInterval Copy (int start, int end)
+ {
+ MInterval copy, left_copy = null, right_copy = null;
+
+ update_from_to ();
+
+ if (start < From)
+ {
+ if (end <= From)
+ return Left.Copy (start, end);
+ left_copy = Left.Copy (start, From);
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ return Right.Copy (start, end);
+ right_copy = Right.Copy (To, end);
+ }
+
+ copy = new MInterval (Key, null, end - start, Stack);
+ remove_properties (MTextProperty.Flag.Sensitive);
+ if (left_copy != null)
+ {
+ copy.Left = left_copy;
+ left_copy.Parent = copy;
+ }
+ if (right_copy != null)
+ {
+ copy.Right = right_copy;
+ right_copy.Parent = copy;
+ }
+ return copy;
+ }
+
+ // this-. ==> this-.
+ // right newright-.
+ // right
+ private MInterval divide_right (int pos)
+ {
+ MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
+
+ M17N.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
+ To = pos;
+ if (Right != null)
+ {
+ interval.Right = Right;
+ Right.Parent = interval;
+ interval.Length += Right.Length;
+ }
+ interval.Parent = this;
+ Right = interval;
+ return interval;
+ }
+
+ // .-this ==> .-this
+ // left .-newleft
+ // left
+ private MInterval divide_left (int pos)
+ {
+ MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
+
+ M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
+ From = pos;
+ if (Left != null)
+ {
+ interval.Left = Left;
+ Left.Parent = interval;
+ interval.Length += Left.Length;
+ }
+ interval.Parent = this;
+ Left = interval;
+ return interval;
+ }
+
+ private void remove_properties (MTextProperty.Flag flags)
+ {
+ for (MPlist p = Stack; ! p.IsEmpty;)
+ {
+ MTextProperty prop = (MTextProperty) p.Val;
+
+ if ((prop.flags & flags) == flags)
+ p.Pop ();
+ else
+ p = p.Next;
+ }
+ }
+
+ private void inherit_front_properties (MPlist plist)
+ {
+ for (MInterval i = LeftMost; i != null; i = i.Next)
+ {
+ if (! Stack.IsEmpty)
+ break;
+ for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
+ {
+ MTextProperty prop = (MTextProperty) p.Val;
+
+ if ((prop.flags & MTextProperty.Flag.RearSticky)
+ == MTextProperty.Flag.RearSticky)
+ i.Stack.Add (prop.key, prop);
+ }
+ }
+ }
+
+ private void inherit_rear_properties (MPlist plist)
+ {
+ for (MInterval i = RightMost; i != null; i = i.Prev)
+ {
+ if (! Stack.IsEmpty)
+ break;
+ for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
+ {
+ MTextProperty prop = (MTextProperty) p.Val;
+
+ if ((prop.flags & MTextProperty.Flag.FrontSticky)
+ == MTextProperty.Flag.FrontSticky)
+ i.Stack.Add (prop.key, prop);
+ }
+ }
+ }
+
+ private MInterval delete_node_forward ()
+ {
+ if (Parent != null)
+ {
+ int len = Length - RightLength;
+
+ for (MInterval i = Parent; i != null; i = i.Parent)
+ i.Length -= len;
+ if (Parent.Left == this)
+ Parent.Left = Right;
+ else
+ Parent.Right = Right;
+ }
+
+ if (Right != null)
+ {
+ Right.Parent = Parent;
+ return Right.LeftMost;
+ }
+ return Parent;
+ }
+
+ private MInterval delete_node_backward ()
+ {
+ if (Parent != null)
+ {
+ int len = Length - RightLength;
+
+ for (MInterval i = Parent; i != null; i = i.Parent)
+ i.Length -= len;
+ if (Parent.Left == this)
+ Parent.Left = Left;
+ else
+ Parent.Right = Left;
+ }
+
+ if (Left != null)
+ {
+ Left.Parent = Parent;
+ return Left.RightMost;
+ }
+ return Parent;
+ }
+
+ private void set_mtext (MText mt)
+ {
+ mtext = mt;
+ if (Left != null)
+ Left.set_mtext (mt);
+ if (Right != null)
+ Right.set_mtext (mt);
+ }
+
+ private MInterval graft (MInterval interval, bool forward, out int len)
+ {
+ MInterval i;
+
+ len = 0;
+ if (forward)
+ {
+ i = interval.LeftMost;
+ while (i != null)
+ {
+ if (! mergeable (i))
+ break;
+ len += i.Length - i.RightLength;
+ i = i.delete_node_forward ();
+ }
+ }
+ else
+ {
+ i = interval.RightMost;
+ while (i != null)
+ {
+ if (! mergeable (i))
+ break;
+ len += i.Length - i.LeftLength;
+ i = i.delete_node_backward ();
+ }
+ }
+
+ Length += len;
+ To += len;
+ for (MInterval prev = this, ii = this.Parent; ii != null;
+ prev = ii, ii = ii.Parent)
+ {
+ ii.Length += len;
+ if (prev == ii.Left)
+ {
+ ii.From += len;
+ ii.To += len;;
+ }
+ }
+ if (i != null)
+ while (i.Parent != null) i = i.Parent;
+ return i;
+ }
+
+ public void Insert (int pos, MInterval interval)
+ {
+ update_from_to ();
+ M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos);
+ DumpOne (false, true);
+
+ interval.set_mtext (mtext);
+
+ if (pos < From)
+ Prev.Insert (pos, interval);
+ else if (pos == From)
+ {
+ MInterval prev = Prev;
+
+ if (prev != null)
+ {
+ if (Left == null)
+ {
+ prev.Insert (pos, interval);
+ return;
+ }
+ prev.remove_properties
+ (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
+ interval.inherit_front_properties (prev.Stack);
+ }
+ remove_properties
+ (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
+ interval.inherit_rear_properties (Stack);
+
+ int len;
+ interval = graft (interval, false, out len);
+ if (interval != null && prev != null)
+ interval = prev.graft (interval, true, out len);
+ if (interval != null)
+ {
+ MInterval i;
+
+ if (Left != null)
+ {
+ // .-this-. ==> .-this-.
+ // left-. .-left-.
+ // child child-.
+ // interval
+ i = Left.RightMost;
+ i.Right = interval;
+ }
+ else
+ {
+ Left = interval;
+ i = this;
+ }
+ interval.Parent = i;
+ for (; i != null; i = i.Parent)
+ i.Length += interval.Length;
+ }
+ }
+ else if (pos < To)
+ {
+ remove_properties (MTextProperty.Flag.Sensitive);
+
+ int len;
+ interval = graft (interval, true, out len);
+ pos += len;
+ if (interval != null)
+ interval = graft (interval, false, out len);
+ if (interval != null)
+ {
+ divide_right (pos);
+ Right.Left = interval;
+ interval.Parent = Right;
+ for (MInterval i = Right; i != null; i = i.Parent)
+ i.Length += interval.Length;
+ }
+ }
+ else if (pos == To)
+ {
+ MInterval next = Next;
+
+ if (next != null)
+ {
+ if (Right == null)
+ {
+ next.Insert (pos, interval);
+ return;
+ }
+ next.remove_properties
+ (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
+ interval.inherit_rear_properties (next.Stack);
+ }
+ remove_properties
+ (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
+ interval.inherit_front_properties (Stack);
+
+ int len;
+ interval = graft (interval, true, out len);
+ if (interval != null && next != null)
+ interval = next.graft (interval, false, out len);
+ if (interval != null)
+ {
+ MInterval i;
+
+ if (Right != null)
+ {
+ // .-this-. ==> .-this-.
+ // .-right .-right
+ // child .-child
+ // interval
+
+ i = Right.LeftMost;
+ i.Left = interval;
+ }
+ else
+ {
+ Right = interval;
+ i = this;
+ }
+ interval.Parent = i;
+ for (; i != null; i = i.Parent)
+ i.Length += interval.Length;
+ }
+ }
+ else // (pos > To)
+ Next.Insert (pos, interval);
+ }
+
+ private void vacate_node (MInterval interval)
+ {
+ M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID);
+ if (interval != null)
+ interval.Parent = Parent;
+ if (Parent == null)
+ {
+ if (mtext != null)
+ mtext.intervals.Put (Key, interval);
+ }
+ else
+ {
+ if (this == Parent.Right)
+ Parent.Right = interval;
+ else
+ Parent.Left = interval;
+
+ int diff = Length;
+ if (interval != null)
+ diff -= interval.Length;
+ for (MInterval i = Parent; i != null; i = i.Parent)
+ i.Length -= diff;
+ }
+ }
+
+ public void Delete (int start, int end)
+ {
+ update_from_to ();
+ M17N.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
+ if (start < From)
+ {
+ if (end <= From)
+ {
+ Left.Delete (start, end);
+ return;
+ }
+ Left.Delete (start, From);
+ To -= From - start;
+ end -= From - start;
+ From = start;
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ {
+ Right.Delete (start, end);
+ return;
+ }
+ Right.Delete (To, end);
+ end = To;
+ }
+ if (start == From && end == To)
+ {
+ if (Right == null)
+ {
+ vacate_node (Left);
+ }
+ else
+ {
+ if (Left != null)
+ {
+ MInterval i;
+
+ for (i = Right; i.Left != null; i = i.Left)
+ i.Length += Left.Length;
+ i.Length += Left.Length;
+ i.Left = Left;
+ Left.Parent = i;
+ }
+ vacate_node (Right);
+ }
+ }
+ else
+ {
+ int len = end - start;
+
+ for (MInterval i = this; i != null; i = i.Parent)
+ i.Length -= len;
+ }
+ }
+
+ public void Push (int start, int end, MTextProperty prop)
+ {
+ update_from_to ();
+ M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
+ if (start < From)
+ {
+ if (end <= From)
+ {
+ Left.Push (start, end, prop);
+ return;
+ }
+ Left.Push (start, From, prop);
+ start = From;
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ {
+ Right.Push (start, end, prop);
+ return;
+ }
+ Right.Push (To, end, prop);
+ end = To;
+ }
+
+ if (start > From)
+ divide_left (start);
+ if (end < To)
+ divide_right (end);
+ Stack.Push (prop.key, prop);
+ }
+
+ private static void merge_nodes (MInterval head, MInterval tail)
+ {
+ M17N.DebugPrint ("merging "); head.DumpOne (true, false);
+ M17N.DebugPrint (" through "); tail.DumpOne (true, true);
+
+ int from = head.From;
+ int to = tail.To;
+ MInterval root;
+
+ for (root = head; root.To + head.RightLength < to;
+ root = root.Parent);
+
+ M17N.DebugPrint ("common root is "); root.DumpOne (false, true);
+
+ if (from < root.From)
+ {
+ MInterval prev = root.Prev;
+
+ while (true)
+ {
+ int len = prev.Length - prev.LeftLength;
+
+ M17N.DebugPrint ("merging "); prev.DumpOne (false, true);
+ if (prev.Left != null)
+ {
+ prev.Left.Parent = prev.Parent;
+ if (prev.Parent.Right == prev)
+ prev.Parent.Right = prev.Left;
+ else
+ prev.Parent.Left = prev.Left;
+ for (MInterval i = prev.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (prev == head)
+ break;
+ prev = prev.Left.RightMost;
+ }
+ else
+ {
+ prev.Parent.Right = null;
+ for (MInterval i = prev.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (prev == head)
+ break;
+ prev = prev.Parent;
+ }
+ }
+ }
+ if (root.To < to)
+ {
+ MInterval next = root.Next;
+
+ while (true)
+ {
+ int len = next.Length - next.RightLength;
+
+ M17N.DebugPrint ("merging "); next.DumpOne (false, true);
+ if (next.Right != null)
+ {
+ next.Right.Parent = next.Parent;
+ if (next.Parent.Left == next)
+ next.Parent.Left = next.Right;
+ else
+ next.Parent.Right = next.Right;
+ for (MInterval i = next.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (next == tail)
+ break;
+ next = next.Right.LeftMost;
+ }
+ else
+ {
+ next.Parent.Left = null;
+ for (MInterval i = next.Parent; i != root; i = i.Parent)
+ i.Length -= len;
+ if (next == tail)
+ break;
+ next = next.Parent;
+ }
+ }
+ }
+ }
+
+ public void MergeAfterChange (int start, int end)
+ {
+ update_from_to ();
+ if (start < From)
+ {
+ Prev.MergeAfterChange (start, end);
+ return;
+ }
+
+ MInterval head = this, tail = this, i;
+
+ if (start == From && start > 0)
+ {
+ i = Prev;
+ if (mergeable (i))
+ head = i;
+ }
+ while (tail.To < end)
+ {
+ i = tail.Next;
+ if (! tail.mergeable (i))
+ {
+ if (head != tail)
+ merge_nodes (head, tail);
+ head = i;
+ }
+ tail = i;
+ }
+ while (true)
+ {
+ i = tail.Next;
+ if (i == null || ! tail.mergeable (i))
+ break;
+ tail = i;
+ }
+ if (head != tail)
+ merge_nodes (head, tail);
+ }
+
+ public void Pop (int start, int end)
+ {
+ update_from_to ();
+ M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
+ if (start < From)
+ {
+ if (end <= From)
+ {
+ Left.Pop (start, end);
+ return;
+ }
+ Left.Pop (start, From);
+ start = From;
+ }
+ if (end > To)
+ {
+ if (start >= To)
+ {
+ Right.Pop (start, end);
+ return;
+ }
+ Right.Pop (To, end);
+ end = To;
+ }
+
+ if (! Stack.IsEmpty)
+ {
+ if (start > From)
+ divide_left (start);
+ if (end < To)
+ divide_right (end);
+ Stack.Pop ();
+ }
+ }
+
+ private void DumpOne (bool with_prop, bool newline)
+ {
+ DumpOne (with_prop, newline, false);
+ }
+
+ private void DumpOne (bool with_prop, bool newline, bool force)
+ {
+ if (force || M17N.debug)
+ {
+ Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
+ if (with_prop)
+ foreach (MPlist p in Stack)
+ Console.Write (" " + p.Val);
+ Console.Write (")");
+ if (newline)
+ Console.WriteLine ();
+ if (Length <= 0)
+ throw new Exception ("Invalid interval length");
+ }
+ }
+
+ public void Dump () { Dump (false); }
+
+ public void Dump (bool force)
+ {
+ if (force || M17N.debug)
+ {
+ update_from_to ();
+
+ if (Left != null)
+ Left.Dump (force);
+ if (From > 0)
+ Console.Write (" ");
+ DumpOne (true, false, force);
+ if (Right != null)
+ Right.Dump (force);
+ }
+ }
+
+ private int Depth {
+ get { return (Parent == null ? 0 : Parent.Depth + 1); }
+ }
+
+ public void DumpNested (bool force)
+ {
+ DumpNested ("", force);
+ }
+
+ public void DumpNested (string indent, bool force)
+ {
+ if (force || M17N.debug)
+ {
+ int indent_type = (Parent == null ? 1
+ : Parent.Left == this ? 0 : 2);
+
+ update_from_to ();
+ if (Left != null)
+ {
+ if (indent_type <= 1)
+ Left.DumpNested (indent + " ", force);
+ else
+ Left.DumpNested (indent + "| ", force);
+ }
+ if (indent_type == 0)
+ Console.Write (indent + ".-");
+ else if (indent_type == 2)
+ Console.Write (indent + "`-");
+ DumpOne (true, true, true);
+ if (Right != null)
+ {
+ if (indent_type >= 1)
+ Right.DumpNested (indent + " ", force);
+ else
+ Right.DumpNested (indent + "| ", force);
+ }
+ }
+ }
+ }
+
+ 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