using System.Text;
using System.Collections;
using System.Collections.Generic;
+using M17N;
using M17N.Core;
namespace M17N.Core
}
#endif
- public class MTextProperty
+ public class MProperty
{
+ [FlagsAttribute]
+ public enum Flags
+ {
+ None = 0,
+ /// A text inserted before a character that has this property
+ /// inherits this property. If the text already has properties
+ /// of the same key, they are deleted. See the documentation of
+ /// Sensitive for exception.
+ FrontSticky = 1,
+ /// A text inserted after a character that has this property
+ /// inherits this property. If the text already has properties
+ /// of the same key, they are deleted. See the documentation of
+ /// Sensitive for exception.
+ RearSticky = 2,
+ /// This property is deleted from a span of text if the span is
+ /// modified (i.e. a character is changed, a text is inserted,
+ /// some part is deleted). This propery is also deleted if a
+ /// property of the same key is added, which means that this
+ /// property is not stackable. If this property is also
+ /// FrontSticky (or RearSticky), text insertion just before (or
+ /// after) the span also deletes this property from the span of
+ /// text.
+ Sensitive = 4,
+ };
+
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)
+ public MProperty (MSymbol key, object val)
{
+ if (key.flags == null)
+ key.flags = MProperty.Flags.None;
this.key = key;
this.val = val;
- flags |= Flag.RearSticky;
}
- public MTextProperty (MSymbol key, object val,
- bool front_sticky, bool rear_sticky, bool sensitive)
+ public MProperty (string name, object val)
{
- this.key = key;
+ key = MSymbol.PropertyKey (name);
this.val = val;
- if (front_sticky)
- flags |= Flag.FrontSticky;
- if (rear_sticky)
- flags |= Flag.RearSticky;
- if (sensitive)
- flags |= Flag.Sensitive;
}
public override string ToString ()
intervals = new MPlist ();
}
+ public static MText operator+ (object obj, MText mt)
+ {
+ if (obj is string)
+ return new MText ((string) obj) + mt;
+ throw new Exception ("Unknown object type: " + obj.GetType());
+ }
+
public static MText operator+ (MText mt1, MText mt2)
{
MText mt = new MText ();
return mt;
}
+ public static MText operator+ (string str, MText mt)
+ {
+ MText mtnew = new MText (str);
+
+ mtnew.sb.Append (mt.sb);
+ mtnew.nchars += mt.nchars;
+ return mtnew;
+ }
+
// Public properties
public bool ReadOnly { get { return read_only; } }
public int Length { get { return nchars; } }
throw new Exception ("Invalid MText position:" + pos);
}
- private void check_range (int from, int to, bool zero_ok)
+ 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);
+ if (M17n.debug)
+ {
+ Console.Write ("inserting {0} to {1} of ", from, to);
+ mt2.DumpPropNested ();
+ }
+ if (from == to)
+ return;
+ foreach (MPlist plist in intervals)
+ {
+ MInterval root = (MInterval) plist.Val;
+ MPlist p = mt2.intervals.Find (plist.Key);
+ MInterval i = p == null ? null : (MInterval) p.Val;
+
+ root.Insert (pos, i, from, to);
+ }
+ foreach (MPlist plist in mt2.intervals)
+ if (intervals.Find (plist.Key) == null)
+ {
+ MInterval root;
+
+ if (nchars == 0)
+ root = ((MInterval) plist.Val).Copy (this, from, to);
+ else
+ {
+ root = new MInterval (plist.Key, this);
+ root.Insert (pos, (MInterval) plist.Val, from, to);
+ }
+ intervals.Push (plist.Key, root);
+ }
+
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;
+ private void insert (int pos, int c)
+ {
+ check_pos (pos, true);
- if (p.IsEmpty)
- interval = new MInterval (plist.Key, to - from);
- else
- interval = ((MInterval) p.Val).copy (from, to);
- ((MInterval) plist.Val).Insert (pos, interval);
+ 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, null, 0, 1);
}
public int this[int i]
public MText Dup ()
{
- return (new MText (sb.ToString ()));
+ MText mt = new MText (sb.ToString ());
+
+ foreach (MPlist p in intervals)
+ mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, 0, Length));
+ return mt;
+ }
+
+ public MText Dup (int from, int to)
+ {
+ if (check_range (from, to, true))
+ return new MText ();
+ int from_idx = pos_to_idx (this, from);
+ int len = pos_to_idx (this, to) - from_idx;
+ MText mt = new MText (sb.ToString ().Substring (from_idx, len));
+
+ foreach (MPlist p in intervals)
+ mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, from, to));
+ return mt;
+ }
+
+ public MText Ins (int pos, int c)
+ {
+ insert (pos, c);
+ return this;
}
public MText Ins (int pos, MText mt)
return this;
}
+ public MText Cat (int c)
+ {
+ insert (nchars, c);
+ return this;
+ }
+
public MText Del (int from, int to)
{
- check_range (from, to, true);
+ 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);
+ {
+ MInterval root = (MInterval) plist.Val;
+ root.Delete (from, to);
+ if (from > 0 && from < nchars)
+ ((MInterval) plist.Val).MergeAfterChange (from, from);
+ }
else
- intervals = new MPlist ();
+ intervals.Clear ();
+ if (M17n.debug)
+ DumpPropNested ();
return this;
}
{
check_pos (pos, false);
- MInterval i = (MInterval) intervals.Find (key).Val;
-
+ MInterval i = (MInterval) intervals.Get (key);
if (i == null)
return null;
- MTextProperty prop = i.Get (pos);
+ MProperty prop = i.Get (pos);
return (prop != null ? prop.Val : null);
}
- public object GetProp (int pos, MSymbol key, out MTextProperty prop)
+ public object GetProp (int pos, MSymbol key, out MProperty prop)
{
check_pos (pos, false);
- MInterval i = (MInterval) intervals.Find (key).Val;
-
+ 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)
+ public object GetProp (int pos, MSymbol key, out MProperty[] array)
{
check_pos (pos, false);
- MInterval i = (MInterval) intervals.Find (key).Val;
-
+ MInterval i = (MInterval) intervals.Get (key);
if (i == null)
return (array = null);
- MTextProperty prop = i.Get (pos, out array);
+ MProperty prop = i.Get (pos, out array);
return (prop != null ? prop.Val : null);
}
public void PushProp (int from, int to, MSymbol key, object val)
{
- check_range (from, to, false);
-
- PushProp (from, to, new MTextProperty (key, val));
+ if (! check_range (from, to, true))
+ PushProp (from, to, new MProperty (key, val));
}
- public void PushProp (int from, int to, MTextProperty prop)
+ public void PushProp (int from, int to, MProperty prop)
{
if (from < 0)
{
}
else
{
- MInterval root = (MInterval) intervals.Find (prop.key).Val;
+ if (check_range (from, to, true))
+ return;
+
+ MPlist p = intervals.Find (prop.key);
+ MInterval root;
- if (root == null)
+ if (p == null)
{
root = new MInterval (prop.key, this);
intervals.Push (prop.key, root);
}
+ else
+ root = (MInterval) p.Val;
+
+ if (root.isSensitive)
+ root.PopSensitive (from, to);
root.Push (from, to, prop);
+ root.MergeAfterChange (from, to);
+ root.Balance ();
+ }
+ }
+
+ 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;
+ if (root.isSensitive)
+ root.PopSensitive (from, to);
+ else
+ root.Pop (from, to);
+ root = (MInterval) p.Val;
+ if (M17n.debug)
+ DumpPropNested ();
+ root.MergeAfterChange (from, to);
+ root.Balance ();
+ }
}
}
{
Console.Write ("(");
foreach (MPlist p in intervals)
- ((MInterval) p.Val).Dump ();
+ ((MInterval) p.Val).Dump (true);
Console.WriteLine (")");
}
+ public void DumpPropNested ()
+ {
+ Console.WriteLine ("total length = {0}", Length);
+ foreach (MPlist p in intervals)
+ ((MInterval) p.Val).DumpNested (true);
+ }
+
private class MInterval
{
// position: 0 1 2 3 4 5 6 7
// [1 (0 1)] [2 (2 3)] [1 (6 7)]
//
private static int count = 0;
- private int id;
- private int total_length;
- private int from, to;
- private MSymbol key;
- private MPlist stack;
- private MInterval left, right, parent;
+ 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, int length)
+ public MInterval (MSymbol key, MText mt, int length)
{
if (length <= 0)
throw new Exception ("Invalid interval length");
- this.key = key;
- total_length = length;
- stack = new MPlist ();
- id = count++;
+ Key = key;
+ mtext = mt;
+ Length = length;
+ Stack = new MPlist ();
+ ID = count++;
}
public MInterval (MSymbol key, MText mt)
{
- this.key = key;
+ Key = key;
mtext = mt;
- total_length = mt.sb.Length;
- from = 0;
- to = total_length;
- stack = new MPlist ();
- id = count++;
+ Length = mt.sb.Length;
+ From = 0;
+ To = Length;
+ Stack = new MPlist ();
+ ID = count++;
}
- public MTextProperty Get (int pos)
+ /// POS must be smaller than Length;
+ public MProperty Get (int pos)
{
- MInterval i = find (pos);
+ MInterval i = find_head (pos);
- return (i.stack.IsEmpty ? null : (MTextProperty) i.stack.Val);
+ return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val);
}
- public MTextProperty Get (int pos, out MTextProperty[] array)
+ /// POS must be smaller than Length;
+ public MProperty Get (int pos, out MProperty[] array)
{
- MInterval i = find (pos);
+ MInterval i = find_head (pos);
- if (i.stack.IsEmpty)
+ if (i.To == pos)
+ i = i.Next;
+ if (i.Stack.IsEmpty)
{
array = null;
return null;
}
- array = new MTextProperty[i.stack.Count];
+ array = new MProperty[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[idx - 1];
+ for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
+ array[idx] = (MProperty) p.Val;
+ return array[0];
}
- private MInterval (MSymbol key, int length, MPlist stack)
+ private MInterval (MSymbol key, MText mt, int length, MPlist stack)
{
- this.key = key;
- total_length = length;
- from = 0;
- to = total_length;
- this.stack = stack.Clone ();
- id = count++;
+ Key = key;
+ mtext = mt;
+ Length = length;
+ From = 0;
+ To = Length;
+ Stack = stack == null ? new MPlist () : stack.Clone ();
+ ID = count++;
+ }
+
+ private bool isRearSticky
+ {
+ get { return ((Key.flags & MProperty.Flags.RearSticky)
+ != MProperty.Flags.None); }
+ }
+
+ private bool isFrontSticky
+ {
+ get { return ((Key.flags & MProperty.Flags.FrontSticky)
+ != MProperty.Flags.None); }
+ }
+
+ public bool isSensitive
+ {
+ get { return ((Key.flags & MProperty.Flags.Sensitive)
+ != MProperty.Flags.None); }
}
private void update_from_to ()
{
- if (parent == null)
+ if (Parent == null)
{
- from = LeftLength;
- to = total_length - RightLength;
+ From = LeftLength;
+ To = Length - RightLength;
}
- else if (parent.left == this)
+ else if (Parent.Left == this)
{
- from = parent.from - total_length + LeftLength;
- to = parent.from - RightLength;
+ From = Parent.From - Length + LeftLength;
+ To = Parent.From - RightLength;
}
else
{
- from = parent.to + LeftLength;
- to = parent.to + total_length - RightLength;
+ From = Parent.To + LeftLength;
+ To = Parent.To + Length - RightLength;
}
}
private int LeftLength
{
- get { return (left == null ? 0 : left.total_length); }
+ get { return (Left == null ? 0 : Left.Length); }
}
private int RightLength
{
- get { return (right == null ? 0 : right.total_length); }
+ get { return (Right == null ? 0 : Right.Length); }
}
- private MInterval left_most_node
+ private MInterval LeftMost
{
- get { return (left == null ? this : left.left_most_node); }
+ get {
+ update_from_to ();
+ if (Left == null)
+ return this;
+ return Left.LeftMost;
+ }
}
- private MInterval right_most_node
+ private MInterval RightMost
{
- get { return (right == null ? this : right.right_most_node); }
+ get {
+ update_from_to ();
+ if (Right == null)
+ return this;
+ return Right.RightMost;
+ }
}
- private MInterval prev {
+ private MInterval Prev {
get {
MInterval i;
- if (left != null)
- for (i = left; i.right != null; i = i.right);
+ if (Left != null)
+ {
+ for (i = Left; i.Right != null; i = i.Right)
+ i.update_from_to ();
+ i.update_from_to ();
+ }
else
- for (i = parent; i != null && i.left == null; i = i.parent);
+ {
+ MInterval child = this;
+ for (i = Parent; i != null && i.Left == child;
+ child = i, i = i.Parent);
+ }
return i;
}
}
- private MInterval next {
+ private MInterval Next {
get {
MInterval i;
- if (right != null)
- for (i = right; i.left != null; i = i.left);
+ if (Right != null)
+ {
+ for (i = Right; i.Left != null; i = i.Left)
+ i.update_from_to ();
+ i.update_from_to ();
+ }
else
- for (i = parent; i != null && i.right == null; i = i.parent);
+ {
+ MInterval child = this;
+ for (i = Parent; i != null && i.Right == child;
+ child = i, i = i.Parent);
+ }
return i;
}
}
- private MInterval find (int pos)
+ private MInterval find_head (int pos)
{
update_from_to ();
- if (pos < from)
- return left.find (pos);
- if (pos >= to)
- return right.find (pos);
+ if (pos < From)
+ return Left.find_head (pos);
+ if (pos >= To)
+ return Right.find_head (pos);
return this;
}
+ private MInterval find_tail (int pos)
+ {
+ update_from_to ();
+ if (pos <= From)
+ return Left.find_tail (pos);
+ if (pos > To)
+ return Right.find_tail (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.total_length;
- MInterval c1;
+ MInterval c1 = Right.Left;
- if (parent == null)
- mtext.intervals.Put (key, right);
- else if (parent.left == this)
- parent.left = right;
+ // Update Parent.
+ 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.total_length += total_length;
- total_length -= right_length;
+ Parent.Right = Right;
+
+ // Update Right.
+ Right.Parent = Parent;
+ Right.Left = this;
+ Right.Length += LeftLength + (To - From);
+
+ // Update this.
+ Parent = Right;
+ Right = c1;
+ Length = LeftLength + (To - From) + RightLength;
+
+ // Update C1 if necessary.
if (c1 != null)
- {
- c1.parent = this;
- parent.total_length -= c1.total_length;
- total_length += c1.total_length;
- }
- return parent;
+ c1.Parent = this;
+
+ Parent.update_from_to ();
+ return Parent;
}
// p-. or .-p p-. or .-p
// c1 c2 c2 right
private MInterval promote_left ()
{
- int left_length = left.total_length;
- MInterval c1;
+ MInterval c2 = Left.Right;
- if (parent == null)
- mtext.intervals.Put (key, left);
- else if (parent.left == this)
- parent.left = left;
+ // Update Parent.
+ 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.total_length += total_length;
- total_length -= left_length;
- if (c1 != null)
- {
- c1.parent = this;
- parent.total_length -= c1.total_length;
- total_length += c1.total_length;
- }
- return parent;
+ Parent.Right = Left;
+
+ // Update Left.
+ Left.Parent = Parent;
+ Left.Right = this;
+ Left.Length += (To - From) + RightLength;
+
+ // Update this.
+ Parent = Left;
+ Left = c2;
+ Length = LeftLength + (To - From) + RightLength;
+
+ // Update C2 if necessary.
+ if (c2 != null)
+ c2.Parent = this;
+
+ Parent.update_from_to ();
+ return Parent;
}
- private MInterval balance ()
+ public MInterval Balance ()
{
MInterval i = this;
+ update_from_to ();
while (true)
{
// .-this-.
if (diff > 0)
{
- new_diff = (i.total_length - i.LeftLength
- + i.left.RightLength - i.left.LeftLength);
+ new_diff = (i.Length - i.LeftLength
+ + i.Left.RightLength - i.Left.LeftLength);
if (Math.Abs (new_diff) >= diff)
break;
+ M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
i = i.promote_left ();
- i.right.balance ();
+ M17n.DebugPrint ("done\n");
+ i.Right.Balance ();
}
else if (diff < 0)
{
- new_diff = (i.total_length - i.RightLength
- + i.right.LeftLength - i.right.RightLength);
+ new_diff = (i.Length - i.RightLength
+ + i.Right.LeftLength - i.Right.RightLength);
if (Math.Abs (new_diff) >= diff)
break;
+ M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
i = i.promote_right ();
- i.left.balance ();
+ i.Left.Balance ();
}
+ else
+ break;
}
return i;
}
- public MInterval copy (int start, int end)
+ public MInterval Copy (MText mt, int start, int end)
{
- MInterval this_copy, left_copy = null, right_copy = null;
+ MInterval copy, left_copy = null, right_copy = null;
update_from_to ();
- if (start < from)
+
+ if (start < From)
{
- if (end <= from)
- return left.copy (start, end);
- left_copy = left.copy (start, from);
+ if (end <= From)
+ return Left.Copy (mt, start, end);
+ left_copy = Left.Copy (mt, start, From);
}
- else if (end > to)
+ if (end > To)
{
- if (start >= to)
- return right.copy (start, end);
- right_copy = right.copy (to, end);
+ if (start >= To)
+ return Right.Copy (mt, start, end);
+ right_copy = Right.Copy (mt, To, end);
}
- this_copy = new MInterval (key, end - start, stack);
- this_copy.left = left_copy;
- this_copy.right = right_copy;
- return this_copy;
+ copy = new MInterval (Key, null, end - start, Stack);
+ copy.mtext = mt;
+ if (isSensitive && (From < start || end < To))
+ copy.Stack.Clear ();
+ 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
private MInterval divide_right (int pos)
{
- MInterval interval = new MInterval (key, to - pos, stack);
+ MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
- Console.Write ("divide-right({0}) at ", pos); DumpOne (false, true);
- to = pos;
- if (right != null)
+ M17n.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
+ To = pos;
+ if (Right != null)
{
- interval.right = right;
- right.parent = interval;
- interval.total_length += right.total_length;
+ interval.Right = Right;
+ Right.Parent = interval;
+ interval.Length += Right.Length;
}
- interval.parent = this;
- right = interval;
+ interval.Parent = this;
+ Right = interval;
return interval;
}
// left
private MInterval divide_left (int pos)
{
- MInterval interval = new MInterval (key, pos - from, stack);
+ MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
- Console.Write ("divide-reft({0}) at ", pos); DumpOne (false, true);
- from = pos;
- if (left != null)
+ M17n.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
+ From = pos;
+ if (Left != null)
{
- interval.left = left;
- left.parent = interval;
- interval.total_length += left.total_length;
+ interval.Left = Left;
+ Left.Parent = interval;
+ interval.Length += Left.Length;
}
- interval.parent = this;
- left = interval;
+ interval.Parent = this;
+ Left = interval;
return interval;
}
- private void remove_properties (MTextProperty.Flag flags)
+ private void set_mtext (MText mt)
{
- for (MPlist p = stack; ! p.IsEmpty;)
- {
- MTextProperty prop = (MTextProperty) p.Val;
+ mtext = mt;
+ if (Left != null)
+ Left.set_mtext (mt);
+ if (Right != null)
+ Right.set_mtext (mt);
+ }
- if ((prop.flags & flags) == flags)
- p.Pop ();
- else
- p = p.Next;
+ private void enlarge (int len)
+ {
+ Length += len;
+ To += len;
+ for (MInterval prev = this, i = this.Parent; i != null;
+ prev = i, i = i.Parent)
+ {
+ i.Length += len;
+ if (prev == i.Left)
+ {
+ i.From += len;
+ i.To += len;;
+ }
}
}
- private void merge_front_properties (MPlist plist)
+ private int graft_forward (MInterval interval, int start, int end)
{
- for (MInterval i = left_most_node; i != null; i = i.next)
+ int len;
+
+ if (! Stack.IsEmpty && isRearSticky)
+ len = end - start;
+ else if (interval == null)
+ len = Stack.IsEmpty ? end - start : 0;
+ else
{
- if (! stack.IsEmpty)
- break;
- for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
- {
- MTextProperty prop = (MTextProperty) p.Val;
+ MInterval i = interval.find_head (start);
- if ((prop.flags & MTextProperty.Flag.RearSticky)
- == MTextProperty.Flag.RearSticky)
- i.stack.Push (prop.key, prop);
+ len = 0;
+ while (i != null && mergeable (i))
+ {
+ M17n.DebugPrint (" grafting "); i.DumpOne (false, false);
+ len += i.To - i.From;
+ if (i.From < start)
+ len -= start - i.From;
+ if (i.To >= end)
+ {
+ len -= i.To - end;
+ break;
+ }
+ i = i.Next;
}
}
+
+ M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true);
+ if (len > 0)
+ enlarge (len);
+ return len;
}
- private void merge_rear_properties (MPlist plist)
+ private int graft_backward (MInterval interval, int start, int end)
{
- for (MInterval i = right_most_node; i != null; i = i.prev)
+ int len;
+
+ if (! Stack.IsEmpty && isFrontSticky)
+ len = end - start;
+ else if (interval == null)
+ len = Stack.IsEmpty ? end - start : 0;
+ else
{
- if (! stack.IsEmpty)
- break;
- for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
- {
- MTextProperty prop = (MTextProperty) p.Val;
+ MInterval i = interval.find_tail (end);
- if ((prop.flags & MTextProperty.Flag.FrontSticky)
- == MTextProperty.Flag.FrontSticky)
- i.stack.Push (prop.key, prop);
+ len = 0;
+ while (i != null && mergeable (i))
+ {
+ M17n.DebugPrint (" grafting "); i.DumpOne (false, false);
+ len += i.To - i.From;
+ if (end < i.To)
+ len -= i.To - end;
+ if (i.From <= start)
+ {
+ len -= start - i.From;
+ break;
+ }
+ i = i.Prev;
}
}
+
+ M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true);
+ if (len > 0)
+ enlarge (len);
+ return len;
}
- public void Insert (int pos, MInterval interval)
+ public void Insert (int pos, MInterval interval, int start, int end)
{
update_from_to ();
- Console.Write ("insert({0}) at ", pos); DumpOne (false, true);
- if (pos < from || (pos == from && left == null && pos > 0))
- {
- prev.Insert (pos, interval);
- return;
- }
- if (pos > to || (pos == to && right == null && next != null))
- {
- next.Insert (pos, interval);
- return;
- }
- if (pos > from && pos < to)
- {
- remove_properties (MTextProperty.Flag.Sensitive);
- divide_right (pos).Insert (pos, interval);
- return;
- }
- if (pos == from)
+
+ M17n.DebugPrint ("insert({0} to {1}) at {2} in ", start, end, pos);
+ DumpOne (false, false);
+
+ if (pos < From)
+ Left.Insert (pos, interval, start, end);
+ else if (pos == From)
{
- if (pos > 0)
+ if (Left != null)
{
- prev.remove_properties
- (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
- interval.merge_front_properties (prev.stack);
- }
- remove_properties
- (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
- interval.merge_rear_properties (stack);
-
- // INTERVAL is ready to insert.
- //
- // .-this-. ==> .-this-.
- // left-. left-.
- // child .-interval
- // child
-
- if (pos > 0)
- {
- MInterval i = left.right_most_node;
-
- i.left = interval;
- interval.parent = i;
- for (; i != null; i = i.parent)
- i.total_length += interval.total_length;
+ MInterval prev = Prev;
+
+ if (prev.isSensitive && prev.isRearSticky)
+ prev.Stack.Clear ();
+ start += prev.graft_forward (interval, start, end);
}
- else
+ if (isSensitive && isFrontSticky)
+ Stack.Clear ();
+ if (start < end)
{
- left = interval;
+ end -= graft_backward (interval, start, end);
+ if (start < end)
+ {
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end);
+ else
+ interval = new MInterval (Key, mtext, end - start, null);
- for (MInterval i = this; i != null; i = i.parent)
- i.total_length += interval.total_length;
+ 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 // pos == to
+ else if (pos < To)
{
- if (right != null)
- {
- MInterval left_most = right.left_most_node;
+ if (isSensitive)
+ Stack.Clear ();
- left_most.remove_properties
- (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
- interval.merge_rear_properties (left_most.stack);
+ int len = graft_forward (interval, start, end);
+ start += len;
+ pos += len;
+ if (start < end)
+ {
+ end -= graft_backward (interval, start, end);
+ if (start < end)
+ {
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end);
+ else
+ interval = new MInterval (Key, mtext, end - start, null);
+
+ divide_right (pos);
+ Right.Left = interval;
+ interval.Parent = Right;
+ for (MInterval i = Right; i != null; i = i.Parent)
+ i.Length += interval.Length;
+ }
}
- remove_properties
- (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
- interval.merge_front_properties (stack);
-
- // INTERVAL is ready to insert.
- //
- // .-this-. ==> .-this-.
- // .-right .-right
- // child interval-.
- // child
-
- if (right != null)
+ }
+ else if (pos == To)
+ {
+ if (Right != null)
{
- MInterval i = right.left_most_node;
-
- i.left = interval;
- interval.parent = i;
- for (; i != null; i = i.parent)
- i.total_length += interval.total_length;
+ MInterval next = Next;
+
+ if (next.isSensitive && next.isFrontSticky)
+ next.Stack.Clear ();
+ end -= next.graft_backward (interval, start, end);
}
- else
+ if (isSensitive && isRearSticky)
+ Stack.Clear ();
+ if (start < end)
{
- right = interval;
+ start += graft_forward (interval, start, end);
+ if (start < end)
+ {
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end);
+ else
+ interval = new MInterval (Key, mtext, end - start, null);
- for (MInterval i = this; i != null; i = i.parent)
- i.total_length += interval.total_length;
+ 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, start, end);
+ M17n.DebugPrint (" done\n");
}
private void vacate_node (MInterval interval)
{
- Console.WriteLine ("vacate #{0} to #{1}", id, interval.id);
+ vacate_node (interval, null);
+ }
+
+ private void vacate_node (MInterval interval, MInterval stop)
+ {
if (interval != null)
- interval.parent = parent;
- if (parent == null)
+ M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
+ else
+ M17n.DebugPrint ("vacate #{0} to null\n", ID);
+ if (interval != null)
+ interval.Parent = Parent;
+ if (Parent == null)
{
- mtext.intervals.Put (key, interval);
+ if (mtext != null)
+ mtext.intervals.Put (Key, interval);
}
else
{
- if (this == parent.right)
- parent.right = interval;
+ if (this == Parent.Right)
+ Parent.Right = interval;
else
- parent.left = interval;
+ Parent.Left = interval;
- int diff = total_length;
+ int diff = Length;
if (interval != null)
- diff -= interval.total_length;
- for (MInterval i = parent; i != null; i = i.parent)
- i.total_length -= diff;
+ diff -= interval.Length;
+ for (MInterval i = Parent; i != stop; i = i.Parent)
+ i.Length -= diff;
}
}
public void Delete (int start, int end)
{
update_from_to ();
- Console.Write ("delete({0} {1}) at ", start, end); DumpOne (false, true);
- if (start < from)
+ M17n.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
+ if (start < From)
{
- if (end <= from)
+ if (end <= From)
{
- left.Delete (start, end);
+ Left.Delete (start, end);
return;
}
- left.Delete (start, from);
- to -= from - start;
- end -= from - start;
- from = start;
+ Left.Delete (start, From);
+ To -= From - start;
+ end -= From - start;
+ From = start;
}
- if (end > to)
+ if (end > To)
{
- if (start >= to)
+ if (start >= To)
{
- right.Delete (start, end);
+ Right.Delete (start, end);
return;
}
- right.Delete (to, end);
- end = to;
+ Right.Delete (To, end);
+ end = To;
}
- if (start == from && end == to)
+ if (start == From && end == To)
{
- if (right == null)
+ if (Right == null)
{
- vacate_node (left);
+ vacate_node (Left);
}
else
{
- if (left != null)
+ if (Left != null)
{
MInterval i;
- for (i = right; i.left != null; i = i.left)
- i.total_length += left.total_length;
- i.total_length += left.total_length;
- i.left = left;
- left.parent = 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);
+ vacate_node (Right);
}
}
else
{
int len = end - start;
- for (MInterval i = this; i != null; i = i.parent)
- i.total_length -= len;
+ for (MInterval i = this; i != null; i = i.Parent)
+ i.Length -= len;
}
}
- public void Push (int start, int end, MTextProperty prop)
+ public void Push (int start, int end, MProperty prop)
{
update_from_to ();
- Console.Write ("push({0} {1}) at ", start, end); DumpOne (false, true);
- if (start < from)
+ M17n.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
+ if (start < From)
{
- if (end <= from)
+ if (end <= From)
{
- left.Push (start, end, prop);
+ Left.Push (start, end, prop);
return;
}
- left.Push (start, from, prop);
- start = from;
+ Left.Push (start, From, prop);
+ start = From;
}
- if (end > to)
+ if (end > To)
{
- if (start >= to)
+ if (start >= To)
{
- right.Push (start, end, prop);
+ Right.Push (start, end, prop);
return;
}
- right.Push (to, end, prop);
- end = to;
+ Right.Push (To, end, prop);
+ end = To;
}
- if (start > from)
+ if (start > From)
divide_left (start);
- if (end < to)
+ if (end < To)
divide_right (end);
- stack.Push (prop.key, prop);
+ Stack.Push (prop.key, prop);
}
- private void DumpOne (bool with_prop, bool newline)
+ /// Combine intervals between HEAD and TAIL (both inclusive) to
+ /// the common parent of HEAD and TAIL while assuming that the
+ /// intervals are mergeable.
+ private static void combine (MInterval head, MInterval tail)
+ {
+ M17n.DebugPrint ("combining "); head.DumpOne (true, false);
+ M17n.DebugPrint (" through "); tail.DumpOne (true, false);
+
+ int from = head.From;
+ int to = tail.To;
+ // The nearest common parent of HEAD and TAIL.
+ MInterval root;
+
+ for (root = head; root.To + root.RightLength < to;
+ root = root.Parent);
+
+ M17n.DebugPrint (" common root is "); root.DumpOne (false, true);
+
+ if (from < root.From)
+ {
+ MInterval prev = root.Prev;
+
+ while (true)
+ {
+ M17n.DebugPrint ("merging "); prev.DumpOne (false, true);
+ prev.vacate_node (prev.Left, root);
+ if (prev == head)
+ break;
+ if (prev.Left != null)
+ prev = prev.Left.RightMost;
+ else
+ prev = prev.Parent;
+ }
+ root.update_from_to ();
+ }
+ if (root.To < to)
+ {
+ MInterval next = root.Next;
+
+ while (true)
+ {
+ M17n.DebugPrint ("merging "); next.DumpOne (false, true);
+ next.vacate_node (next.Right, root);
+ if (next == tail)
+ break;
+ if (next.Right != null)
+ next = next.Right.LeftMost;
+ else
+ next = next.Parent;
+ }
+ root.update_from_to ();
+ }
+ }
+
+ public void MergeAfterChange (int start, int end)
{
- Console.Write ("#{0}({1} {2} {3}", id, total_length, from, to);
- if (with_prop)
- foreach (MPlist p in stack)
- Console.Write (" " + p.Val);
- Console.Write (")");
- if (newline)
- Console.WriteLine ();
+ update_from_to ();
+
+ MInterval head = find_head (start), tail = head, i;
+
+ if (start == head.From && start > 0)
+ {
+ i = head.Prev;
+ if (head.mergeable (i))
+ head = i;
+ }
+ while (tail.To < end)
+ {
+ i = tail.Next;
+ if (! tail.mergeable (i))
+ {
+ if (head != tail)
+ combine (head, tail);
+ i.update_from_to ();
+ head = i;
+ }
+ tail = i;
+ }
+ while (true)
+ {
+ i = tail.Next;
+ if (i == null || ! tail.mergeable (i))
+ break;
+ tail = i;
+ }
+ if (head != tail)
+ combine (head, tail);
}
- public void Dump ()
+ 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 (left != null)
- left.Dump ();
- if (from > 0)
- Console.Write (" ");
- DumpOne (true, false);
- if (right != null)
- right.Dump ();
+ if (! Stack.IsEmpty)
+ {
+ if (start > From)
+ divide_left (start);
+ if (end < To)
+ divide_right (end);
+ Stack.Pop ();
+ }
+ }
+
+ public void PopSensitive (int start, int end)
+ {
+ update_from_to ();
+ MInterval head = find_head (start);
+ MInterval tail = find_tail (end);
+ while (! head.Stack.IsEmpty && head.From > 0)
+ {
+ MInterval prev = head.Prev;
+
+ if (prev.Stack.IsEmpty || head.Stack.Val != prev.Stack.Val)
+ break;
+ head = head.Prev;
+ }
+ while (! tail.Stack.IsEmpty && tail.To < mtext.Length)
+ {
+ MInterval next = tail.Next;
+
+ if (next.Stack.IsEmpty || tail.Stack.Val != next.Stack.Val)
+ break;
+ tail = tail.Next;
+ }
+ Pop (head.From, tail.To);
+ }
+
+ 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 (Key.ToString () + ":", 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);
+ }
+ Console.Write (indent);
+ if (indent_type == 0)
+ Console.Write (".-");
+ else if (indent_type == 2)
+ Console.Write ("`-");
+ DumpOne (true, true, true);
+ if (Right != null)
+ {
+ if (indent_type >= 1)
+ Right.DumpNested (indent + " ", force);
+ else
+ Right.DumpNested (indent + "| ", force);
+ }
+ }
}
}
projects / m17n / m17n-lib-cs.git / blobdiff