}
#endif
- public class MTextProperty
+ public class MProperty
{
+ [FlagsAttribute]
+ public enum Flags
+ {
+ None = 0x00,
+
+ /// On inserting a text in between two characters, if the
+ /// preceding and following characters have Sticky properties of
+ /// the same key with same values, the inserted text inherits
+ /// those properties. In that case, properties of the inserted
+ /// text are overriden.
+ Sticky = 0x01, // 00000001
+
+ /// On inserting a text before a character, if the character has
+ /// FrontSticky properties, the inserted text inherits those
+ /// properties.
+ FrontSticky = 0x03, // 00000011
+
+ /// On inserting a text after a character, if the character has
+ /// RearSticky properties, the inserted text inherits those
+ /// properties.
+ RearSticky = 0x05, // 00000101
+
+ /// Like RearSticky, but if the inserted text inherits no
+ /// properties from the preceding character, it inherits
+ /// BothSticky properties from the following character if any.
+ BothSticky = 0x07, // 00000111
+
+ /// This property is deleted from a span of text if the span is
+ /// modified (i.e. one of a character is changed, a text is
+ /// inserted, some part is deleted). Here, "span" means a
+ /// sequence of characters that has this property with the same
+ /// value. This property is also deleted if a property of the
+ /// same key is added, which means that this property is not
+ /// stackable. In addition this property is never merged with
+ /// the same value of preceding or following property. At last,
+ /// this property can't be sticky in any way.
+ Sensitive = 0x10, // 00010000
+
+ /// Like Sensitive but also this property is deleted from a span
+ /// of text if a characeter just before the span is modified,
+ /// inserted, or deleted.
+ FrontSensitive = 0x30, // 00110000
+
+ /// Like Sensitive but also this property is deleted from a span
+ /// of text if a character just after the span is modified,
+ /// inserted, or deleted.
+ RearSensitive = 0x50, // 01010000
+
+ /// Same as (FrontSensitive | RearSensitive).
+ BothSensitive = 0x70, // 01110000
+ };
+
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 = 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 static bool HasFlags (MSymbol key, Flags flags)
+ {
+ return ((key.flags & flags) == flags);
}
public override string ToString ()
intervals = new MPlist ();
}
+ public MText (byte[] str, int offset, int length)
+ {
+ sb = new StringBuilder (utf8.GetString (str, offset, length));
+ nchars = count_chars (sb);
+ intervals = new MPlist ();
+ }
+
public MText (String str)
{
sb = new StringBuilder (str);
intervals = new MPlist ();
}
- public static MText operator+ (MText mt1, MText mt2)
+ public static MText operator+ (object obj, MText mt)
{
- MText mt = new MText ();
+ if (obj is string)
+ {
+ MText mtnew = new MText ((string) obj);
+ return mtnew.Ins (mtnew.Length, mt);
+ }
+ throw new Exception ("Unknown object type: " + obj.GetType());
+ }
- mt.sb.Append (mt1.sb);
- mt.sb.Append (mt2.sb);
- mt.nchars = mt1.nchars + mt2.nchars;
- return mt;
+ public static MText operator+ (MText mt, object obj)
+ {
+ if (obj is string)
+ return mt + new MText ((string) obj);
+ if (obj is int)
+ return mt.Dup ().Ins (mt.Length, (int) obj);
+ if (obj is char)
+ return mt.Dup ().Ins (mt.Length, (int) ((char) obj));
+ throw new Exception ("Unknown object type: " + obj.GetType());
+ }
+
+ public static MText operator+ (MText mt1, MText mt2)
+ {
+ return mt1.Dup ().Ins (mt1.Length, mt2);
}
// Public properties
return this.sb.ToString ().CompareTo (other.sb.ToString ());
}
- public override String ToString () { return "\"" + sb.ToString () + "\""; }
+ public override string ToString () { return sb.ToString (); }
private static bool surrogate_high_p (char c)
{
{
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;
-
- 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)
}
nchars++;
foreach (MPlist plist in intervals)
- ((MInterval) plist.Val).Insert (pos,
- new MInterval (plist.Key, this, 1));
+ ((MInterval) plist.Val).Insert (pos, null, 0, 1);
}
public int this[int i]
MText mt = new MText (sb.ToString ());
foreach (MPlist p in intervals)
- mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (0, Length));
+ 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;
}
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;
}
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);
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.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)
{
if (! check_range (from, to, true))
- PushProp (from, to, new MTextProperty (key, val));
+ 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)
{
intervals.Push (prop.key, root);
}
else
- root = (MInterval) p.Val;
-
+ {
+ root = (MInterval) p.Val;
+ if (root.isSensitive)
+ {
+ root.PopSensitive (from, to);
+ root.MergeAfterChange (from, to);
+ root = (MInterval) p.Val;
+ if (M17n.debug)
+ DumpPropNested ();
+ }
+ }
root.Push (from, to, prop);
+ root.MergeAfterChange (from, to);
+ root.Balance ();
}
}
if (p != null)
{
MInterval root = (MInterval) p.Val;
- root.Pop (from, to);
+ 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 ();
}
}
}
public void DumpPropNested ()
{
+ Console.WriteLine ("total length = {0}", Length);
foreach (MPlist p in intervals)
((MInterval) p.Val).DumpNested (true);
}
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.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;
+ array[idx] = (MProperty) p.Val;
return array[0];
}
Length = length;
From = 0;
To = Length;
- Stack = stack.Clone ();
+ Stack = stack == null ? new MPlist () : stack.Clone ();
ID = count++;
}
+ private bool isRearSticky
+ {
+ get { return MProperty.HasFlags (Key, MProperty.Flags.RearSticky) ; }
+ }
+
+ private bool isFrontSticky
+ {
+ get { return MProperty.HasFlags (Key, MProperty.Flags.FrontSticky) ; }
+ }
+
+ public bool isSensitive
+ {
+ get { return MProperty.HasFlags (Key, MProperty.Flags.Sensitive) ; }
+ }
+
+ public bool isFrontSensitive
+ {
+ get { return MProperty.HasFlags (Key,
+ MProperty.Flags.FrontSensitive) ; }
+ }
+
+ public bool isRearSensitive
+ {
+ get { return MProperty.HasFlags (Key,
+ MProperty.Flags.RearSensitive) ; }
+ }
+
private void update_from_to ()
{
if (Parent == null)
private MInterval LeftMost
{
- get { return (Left == null ? this : Left.LeftMost); }
+ get {
+ update_from_to ();
+ if (Left == null)
+ return this;
+ return Left.LeftMost;
+ }
}
private MInterval RightMost
{
- get { return (Right == null ? this : Right.RightMost); }
+ get {
+ update_from_to ();
+ if (Right == null)
+ return this;
+ return Right.RightMost;
+ }
}
private MInterval Prev {
MInterval i;
if (Left != null)
- for (i = Left; i.Right != null; i = i.Right);
+ {
+ for (i = Left; i.Right != null; i = i.Right)
+ i.update_from_to ();
+ i.update_from_to ();
+ }
else
{
MInterval child = this;
MInterval i;
if (Right != null)
- for (i = Right; i.Left != null; i = i.Left);
+ {
+ for (i = Right; i.Left != null; i = i.Left)
+ i.update_from_to ();
+ i.update_from_to ();
+ }
else
{
MInterval child = this;
}
}
- private MInterval find (int pos)
+ private MInterval find_head (int pos)
{
update_from_to ();
if (pos < From)
- return Left.find (pos);
+ return Left.find_head (pos);
if (pos >= To)
- return Right.find (pos);
+ 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;
}
{
MPlist p1, p2;
+ if (Stack.IsEmpty && i.Stack.IsEmpty)
+ return true;
+ if (isSensitive)
+ return false;
for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
p1 = p1.Next, p2 = p2.Next)
if (p1.Val != p2.Val)
// c1 c2 left c1
private MInterval promote_right ()
{
- int right_length = Right.Length;
- MInterval c1;
+ MInterval c1 = Right.Left;
+ // Update Parent.
if (Parent == null)
mtext.intervals.Put (Key, Right);
else if (Parent.Left == this)
Parent.Left = Right;
else
Parent.Right = Right;
+
+ // Update Right.
Right.Parent = Parent;
- c1 = Right.Left;
Right.Left = this;
+ Right.Length += LeftLength + (To - From);
+ // Update this.
Parent = Right;
Right = c1;
- Parent.Length += Length;
- Length -= right_length;
+ Length = LeftLength + (To - From) + RightLength;
+
+ // Update C1 if necessary.
if (c1 != null)
- {
- c1.Parent = this;
- Parent.Length -= c1.Length;
- Length += c1.Length;
- }
+ c1.Parent = this;
+
+ Parent.update_from_to ();
return Parent;
}
// c1 c2 c2 right
private MInterval promote_left ()
{
- int left_length = Left.Length;
- MInterval c1;
+ MInterval c2 = Left.Right;
+ // Update Parent.
if (Parent == null)
mtext.intervals.Put (Key, Left);
else if (Parent.Left == this)
Parent.Left = Left;
else
Parent.Right = Left;
+
+ // Update Left.
Left.Parent = Parent;
- c1 = Left.Left;
Left.Right = this;
+ Left.Length += (To - From) + RightLength;
+ // Update this.
Parent = Left;
- Left = c1;
- Parent.Length += Length;
- Length -= left_length;
- if (c1 != null)
- {
- c1.Parent = this;
- Parent.Length -= c1.Length;
- Length += c1.Length;
- }
+ 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-.
+ 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)
{
+ 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 copy, left_copy = null, right_copy = null;
if (start < From)
{
if (end <= From)
- return Left.Copy (start, end);
- left_copy = Left.Copy (start, From);
+ return Left.Copy (mt, start, end);
+ left_copy = Left.Copy (mt, start, From);
}
if (end > To)
{
if (start >= To)
- return Right.Copy (start, end);
- right_copy = Right.Copy (To, end);
+ return Right.Copy (mt, start, end);
+ right_copy = Right.Copy (mt, To, end);
}
copy = new MInterval (Key, null, end - start, Stack);
- remove_properties (MTextProperty.Flag.Sensitive);
+ copy.mtext = mt;
+ if (isSensitive && (From < start || end < To))
+ copy.Stack.Clear ();
if (left_copy != null)
{
copy.Left = left_copy;
return copy;
}
+ public MInterval Copy (MText mt, int start, int end,
+ bool first, bool last)
+ {
+ MInterval copy = Copy (mt, start, end);
+ MInterval head = find_head (start);
+ MInterval tail = find_tail (end);
+
+ M17n.DebugPrint ("Copying: {0}", copy);
+
+ if (! head.Stack.IsEmpty
+ && (isSensitive && head.From < start
+ || (isFrontSensitive && ! first)))
+ {
+ M17n.DebugPrint (" clear head");
+ head = copy.find_head (0);
+ head.Stack.Clear ();
+ }
+ if (! tail.Stack.IsEmpty
+ && (isSensitive && end < tail.To
+ || (isRearSensitive && ! last)))
+ {
+ M17n.DebugPrint (" clear tail");
+ tail = copy.find_tail (copy.Length);
+ tail.Stack.Clear ();
+ }
+ M17n.DebugPrint ("\n");
+ return copy;
+ }
+
// this-. ==> this-.
// right newright-.
// right
{
MInterval interval = new MInterval (Key, mtext, To - pos, Stack);
- M17N.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
+ M17n.DebugPrint ("divide-right({0}) at {1}\n", pos, this);
To = pos;
if (Right != null)
{
{
MInterval interval = new MInterval (Key, mtext, pos - From, Stack);
- M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
+ M17n.DebugPrint ("divide-left({0}) at {1}\n", pos, this);
From = pos;
if (Left != null)
{
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;
-
- if ((prop.flags & flags) == flags)
- p.Pop ();
- else
- p = p.Next;
- }
+ mtext = mt;
+ if (Left != null)
+ Left.set_mtext (mt);
+ if (Right != null)
+ Right.set_mtext (mt);
}
- private void inherit_front_properties (MPlist plist)
+ private void enlarge (int len)
{
- for (MInterval i = LeftMost; i != null; i = i.Next)
+ Length += len;
+ To += len;
+ for (MInterval prev = this, i = this.Parent; i != null;
+ prev = i, i = i.Parent)
{
- if (! Stack.IsEmpty)
- break;
- for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
+ i.Length += len;
+ if (prev == i.Left)
{
- MTextProperty prop = (MTextProperty) p.Val;
-
- if ((prop.flags & MTextProperty.Flag.RearSticky)
- == MTextProperty.Flag.RearSticky)
- i.Stack.Add (prop.key, prop);
+ i.From += len;
+ i.To += len;;
}
}
}
- private void inherit_rear_properties (MPlist plist)
+ private int graft_forward (MInterval interval, int start, int end)
{
- 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;
+ int len;
- if ((prop.flags & MTextProperty.Flag.FrontSticky)
- == MTextProperty.Flag.FrontSticky)
- i.Stack.Add (prop.key, prop);
- }
- }
- }
-
- private MInterval delete_node_forward ()
- {
- if (Parent != null)
+ if (! Stack.IsEmpty && isRearSticky)
+ len = end - start;
+ else if (interval == null)
+ len = Stack.IsEmpty ? end - start : 0;
+ else
{
- int len = Length - RightLength;
+ MInterval i = interval.find_head (start);
- for (MInterval i = Parent; i != null; i = i.Parent)
- i.Length -= len;
- if (Parent.Left == this)
- Parent.Left = Right;
- else
- Parent.Right = Right;
+ len = 0;
+ if (Stack.IsEmpty
+ && (isFrontSensitive || (isSensitive && i.From < start)))
+ {
+ M17n.DebugPrint (" forward grafting {0}", i);
+ if (i.To < end)
+ len = i.To - start;
+ else
+ len = end - start;
+ i = i.Next;
+ }
+ while (i != null && i.From < end && mergeable (i))
+ {
+ M17n.DebugPrint (" forward grafting {0}", i);
+ 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;
+ }
}
- if (Right != null)
- {
- Right.Parent = Parent;
- return Right.LeftMost;
- }
- return Parent;
+ M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
+ if (len > 0)
+ enlarge (len);
+ return len;
}
- private MInterval delete_node_backward ()
+ private int graft_backward (MInterval interval, int start, int end)
{
- 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;
- }
+ int len;
- if (Left != null)
+ if (! Stack.IsEmpty && isFrontSticky)
+ len = end - start;
+ else if (interval == null)
+ len = Stack.IsEmpty ? end - start : 0;
+ else
{
- Left.Parent = Parent;
- return Left.RightMost;
- }
- return Parent;
- }
+ MInterval i = interval.find_tail (end);
- 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)
+ len = 0;
+ if (Stack.IsEmpty
+ && (isRearSensitive || (isSensitive && end < i.To)))
{
- if (! mergeable (i))
- break;
- len += i.Length - i.RightLength;
- i = i.delete_node_forward ();
+ M17n.DebugPrint (" backward grafting {0}", i);
+ if (i.From <= start)
+ len = end - start;
+ else
+ len = end - i.From;
+ i = i.Prev;
}
- }
- else
- {
- i = interval.RightMost;
- while (i != null)
+ while (i != null && i.To <= start && mergeable (i))
{
- if (! mergeable (i))
- break;
- len += i.Length - i.LeftLength;
- i = i.delete_node_backward ();
+ M17n.DebugPrint (" backward grafting {0}", i);
+ 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;
}
}
- 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;
+ M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
+ 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 ();
- M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos);
- DumpOne (false, true);
- interval.set_mtext (mtext);
+ M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}",
+ start, end, pos, this);
if (pos < From)
- Prev.Insert (pos, interval);
+ Left.Insert (pos, interval, start, end);
else if (pos == From)
{
- MInterval prev = Prev;
+ MInterval prev = Left != null ? Prev : null;
- if (prev != null)
+ if (isFrontSensitive)
+ Stack.Clear ();
+ if (prev != null && isRearSensitive)
+ prev.Stack.Clear ();
+ if (prev != null && isRearSticky && ! prev.Stack.IsEmpty)
+ {
+ prev.enlarge (end - start);
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ if (isFrontSticky && ! Stack.IsEmpty)
{
- if (Left == null)
+ enlarge (end - start);
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ bool front_grafted = false, rear_grafted = false;
+ int grafted;
+ if (prev != null
+ && (grafted = prev.graft_forward (interval, start, end)) > 0)
+ {
+ start += grafted;
+ if (start == end)
{
- prev.Insert (pos, interval);
+ M17n.DebugPrint (" done\n");
return;
}
- prev.remove_properties
- (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
- interval.inherit_front_properties (prev.Stack);
+ front_grafted = true;
}
- 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)
+ if ((grafted = graft_backward (interval, start, end)) > 0)
{
- MInterval i;
-
- if (Left != null)
- {
- // .-this-. ==> .-this-.
- // left-. .-left-.
- // child child-.
- // interval
- i = Left.RightMost;
- i.Right = interval;
- }
- else
+ end -= grafted;
+ if (start == end)
{
- Left = interval;
- i = this;
+ M17n.DebugPrint (" done\n");
+ return;
}
- interval.Parent = i;
- for (; i != null; i = i.Parent)
- i.Length += interval.Length;
+ rear_grafted = true;
}
- }
- 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)
+ interval = interval.Copy (mtext, start, end,
+ (front_grafted
+ || (prev == null && start == 0)),
+ rear_grafted);
+ else
+ interval = new MInterval (Key, mtext, end - start, null);
+
+ MInterval i;
+ if (Left != null)
+ {
+ // .-this-. ==> .-this-.
+ // left-. .-left-.
+ // child child-.
+ // interval
+ i = Left.RightMost;
+ i.Right = interval;
+ }
+ else
{
- divide_right (pos);
- Right.Left = interval;
- interval.Parent = Right;
- for (MInterval i = Right; i != null; i = i.Parent)
- i.Length += interval.Length;
+ Left = interval;
+ i = this;
}
+ interval.Parent = i;
+ for (; i != null; i = i.Parent)
+ i.Length += interval.Length;
}
- else if (pos == To)
+ else if (pos < To)
{
- MInterval next = Next;
-
- if (next != null)
+ if (! Stack.IsEmpty)
{
- if (Right == null)
+ if (isSensitive)
+ Stack.Clear ();
+ else if (isFrontSticky || isRearSticky)
{
- next.Insert (pos, interval);
+ enlarge (end - start);
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)
+ bool front_grafted = false, rear_grafted = false;
+ int grafted;
+ if ((grafted = graft_forward (interval, start, end)) > 0)
{
- MInterval i;
-
- if (Right != null)
+ start += grafted;
+ if (start == end)
{
- // .-this-. ==> .-this-.
- // .-right .-right
- // child .-child
- // interval
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ front_grafted = true;
+ pos += grafted;
+ }
+ if ((grafted = graft_backward (interval, start, end)) > 0)
+ {
+ end -= grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
+ }
+ rear_grafted = true;
+ }
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end,
+ front_grafted, rear_grafted);
+ 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;
+ }
+ else if (pos == To)
+ {
+ MInterval next = Right != null ? Next : null;
- i = Right.LeftMost;
- i.Left = interval;
+ if (isRearSensitive)
+ Stack.Clear ();
+ if (next != null && isFrontSensitive)
+ next.Stack.Clear ();
+ if (isRearSticky && ! Stack.IsEmpty)
+ {
+ enlarge (end - start);
+ M17n.DebugPrint (" done by enlarging this\n");
+ return;
+ }
+ if (next != null && isFrontSticky && ! next.Stack.IsEmpty)
+ {
+ M17n.DebugPrint (" next is {0}\n", next);
+ next.enlarge (end - start);
+ M17n.DebugPrint (" done by enlarging next\n");
+ return;
+ }
+ bool front_grafted = false, rear_grafted = false;
+ int grafted;
+ if (next != null
+ && (grafted = next.graft_backward (interval, start, end)) > 0)
+ {
+ end -= grafted;
+ if (start == end)
+ {
+ M17n.DebugPrint (" done\n");
+ return;
}
- else
+ rear_grafted = true;
+ }
+ if ((grafted = graft_forward (interval, start, end)) > 0)
+ {
+ start += grafted;
+ if (start == end)
{
- Right = interval;
- i = this;
+ M17n.DebugPrint (" done\n");
+ return;
}
- interval.Parent = i;
- for (; i != null; i = i.Parent)
- i.Length += interval.Length;
+ front_grafted = true;
}
+ if (interval != null)
+ interval = interval.Copy (mtext, start, end,
+ front_grafted,
+ (rear_grafted
+ || (next == null && end == interval.mtext.Length)));
+ else
+ interval = new MInterval (Key, mtext, end - start, 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);
+ Right.Insert (pos, interval, start, end);
+ M17n.DebugPrint (" done\n");
}
private void vacate_node (MInterval interval)
{
- M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID);
+ vacate_node (interval, null);
+ }
+
+ private void vacate_node (MInterval interval, MInterval stop)
+ {
+ if (interval != 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)
int diff = Length;
if (interval != null)
diff -= interval.Length;
- for (MInterval i = Parent; i != null; i = i.Parent)
+ for (MInterval i = Parent; i != stop; 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);
+ M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this);
+
+ bool front_checked = false;
+ bool rear_checked = false;
+
if (start < From)
{
if (end <= From)
{
+ if (end == From && isFrontSensitive)
+ Stack.Clear ();
Left.Delete (start, end);
return;
}
+ if (isSensitive)
+ Stack.Clear ();
Left.Delete (start, From);
To -= From - start;
end -= From - start;
From = start;
+ front_checked = true;
}
if (end > To)
{
if (start >= To)
{
+ if (start == To && isRearSensitive)
+ Stack.Clear ();
Right.Delete (start, end);
return;
}
+ if (isSensitive)
+ Stack.Clear ();
Right.Delete (To, end);
end = To;
+ rear_checked = true;
}
+ if (start == From
+ && ! front_checked
+ && start > 0
+ && isRearSensitive)
+ Prev.Stack.Clear ();
+ if (end == To
+ && ! rear_checked
+ && Next != null
+ && isFrontSensitive)
+ Next.Stack.Clear ();
if (start == From && end == To)
{
if (Right == null)
{
int len = end - start;
+ if (isSensitive)
+ Stack.Clear ();
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 ();
- M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
+ M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this);
if (start < From)
{
if (end <= From)
end = To;
}
+ if (! Stack.IsEmpty && isSensitive)
+ Stack.Clear ();
if (start > From)
divide_left (start);
if (end < To)
Stack.Push (prop.key, prop);
}
- private static void merge_nodes (MInterval head, MInterval tail)
+ /// Combine intervals between HEAD and TAIL (both inclusive) to
+ /// the common parent of HEAD and TAIL. Callers should assure
+ /// that the intervals are mergeable in advance.
+ private static void combine (MInterval head, MInterval tail)
{
- M17N.DebugPrint ("merging "); head.DumpOne (true, false);
- M17N.DebugPrint (" through "); tail.DumpOne (true, true);
+ M17n.DebugPrint ("combining {0} through {1}", head, tail);
+ head.update_from_to ();
+ tail.update_from_to ();
int from = head.From;
int to = tail.To;
- MInterval root;
- for (root = head; root.To + head.RightLength < 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);
+ M17n.DebugPrint (" with common root {0}\n", root);
if (from < root.From)
{
while (true)
{
- int len = prev.Length - prev.LeftLength;
-
- M17N.DebugPrint ("merging "); prev.DumpOne (false, true);
+ M17n.DebugPrint ("merging {0}\n", prev);
+ prev.vacate_node (prev.Left, root);
+ if (prev == head)
+ break;
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;
- }
+ 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;
- }
+ prev = prev.Parent;
}
+ root.update_from_to ();
}
if (root.To < to)
{
while (true)
{
- int len = next.Length - next.RightLength;
-
- M17N.DebugPrint ("merging "); next.DumpOne (false, true);
+ M17n.DebugPrint ("merging {0}\n", next);
+ next.vacate_node (next.Right, root);
+ if (next == tail)
+ break;
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;
- }
+ 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;
- }
+ next = next.Parent;
}
+ root.update_from_to ();
}
}
public void MergeAfterChange (int start, int end)
{
update_from_to ();
- if (start < From)
- {
- Prev.MergeAfterChange (start, end);
- return;
- }
- MInterval head = this, tail = this, i;
+ MInterval head = find_head (start), i = head;
+ MInterval tail = start < end ? find_tail (end) : head;
+
+ if (tail.To < Length)
+ tail = tail.Next;
- if (start == From && start > 0)
+ if (start == head.From && start > 0)
{
- i = Prev;
- if (mergeable (i))
- head = i;
+ MInterval prev = head.Prev;
+ if (head.mergeable (prev))
+ head = prev;
}
- while (tail.To < end)
+ M17n.DebugPrint ("merge between {0} and {1}\n", head, tail);
+ while (i != tail)
{
- i = tail.Next;
- if (! tail.mergeable (i))
+ MInterval next = i.Next;
+
+ if (! i.mergeable (next))
{
- if (head != tail)
- merge_nodes (head, tail);
- head = i;
+ if (head != i)
+ combine (head, i);
+ head = next;
}
- tail = i;
- }
- while (true)
- {
- i = tail.Next;
- if (i == null || ! tail.mergeable (i))
- break;
- tail = i;
+ i = next;
}
- if (head != tail)
- merge_nodes (head, tail);
+ if (head != i)
+ combine (head, i);
}
public void Pop (int start, int end)
{
update_from_to ();
- M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
+ M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this);
if (start < From)
{
if (end <= From)
if (! Stack.IsEmpty)
{
- if (start > From)
- divide_left (start);
- if (end < To)
- divide_right (end);
- Stack.Pop ();
+ if (isSensitive)
+ Stack.Clear ();
+ else
+ {
+ if (start > From)
+ divide_left (start);
+ if (end < To)
+ divide_right (end);
+ Stack.Pop ();
+ }
}
}
- private void DumpOne (bool with_prop, bool newline)
+ public void PopSensitive (int start, int end)
{
- DumpOne (with_prop, newline, false);
+ update_from_to ();
+ MInterval head = find_head (start);
+ MInterval tail = find_tail (end);
+ Pop (head.From, tail.To);
+ }
+
+ public override string ToString ()
+ {
+ string str = String.Format ("#{0}({1} {2} {3} [", ID, Length, From, To);
+ bool first = true;
+ foreach (MPlist p in Stack)
+ {
+ if (first)
+ {
+ str += ((MProperty) p.Val).Val;
+ first = false;
+ }
+ else
+ str += " " + ((MProperty) p.Val).Val;
+ }
+ return (str + "])");
}
private void DumpOne (bool with_prop, bool newline, bool force)
{
- if (force || M17N.debug)
+ 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);
+ if (with_prop && ! Stack.IsEmpty)
+ {
+ string prepend = " [";
+ foreach (MPlist p in Stack)
+ {
+ Console.Write (prepend + ((MProperty) p.Val).Val);
+ prepend = " ";
+ }
+ Console.Write ("]");
+ }
Console.Write (")");
if (newline)
Console.WriteLine ();
public void Dump (bool force)
{
- if (force || M17N.debug)
+ if (force || M17n.debug)
{
update_from_to ();
public void DumpNested (bool force)
{
- DumpNested ("", force);
+ DumpNested (" " + Key.ToString () + ":", force);
}
public void DumpNested (string indent, bool force)
{
- if (force || M17N.debug)
+ if (force || M17n.debug)
{
int indent_type = (Parent == null ? 1
: Parent.Left == this ? 0 : 2);
else
Left.DumpNested (indent + "| ", force);
}
+ Console.Write (indent);
if (indent_type == 0)
- Console.Write (indent + ".-");
+ Console.Write (".-");
else if (indent_type == 2)
- Console.Write (indent + "`-");
+ Console.Write ("`-");
DumpOne (true, true, true);
if (Right != null)
{