public class MTextProperty
{
- internal MProperty prop;
- internal bool front_sticky;
- internal bool rear_sticky;
- internal bool merginable;
- public MProperty Prop { get { return prop; } }
- public bool FrontSticky { get { return front_sticky; } }
- public bool RearSticky { get { return rear_sticky; } }
- public bool Merginable { get { return merginable; } }
+ internal MSymbol key;
+ internal object val;
- public MTextProperty (bool front_sticky, bool rear_sticky)
+ [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
{
- this.front_sticky = front_sticky;
- this.rear_sticky = rear_sticky;
+ get { return (flags & Flag.Sensitive) != Flag.None; }
}
- public MTextProperty (bool front_sticky, bool rear_sticky, bool merginable)
+
+ 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.front_sticky = front_sticky;
- this.rear_sticky = rear_sticky;
- this.merginable = merginable;
+ 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;
}
}
#if false
public enum MTextFormat format;
#endif
-
private StringBuilder sb;
private int nchars;
private int cache_pos;
private int cache_idx;
- private MInterval root_interval;
+ private MPlist intervals;
+ private MPlist default_property;
private bool read_only;
private static UTF8Encoding utf8 = new UTF8Encoding ();
public MText ()
{
sb = new StringBuilder ();
+ intervals = new MPlist ();
}
public MText (byte[] str)
{
sb = new StringBuilder (utf8.GetString (str));
nchars = count_chars (sb);
+ intervals = new MPlist ();
}
public MText (String str)
{
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)
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)
{
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;
- if (root_interval != null)
+
+ 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)
{
- MInterval interval = (mt2.root_interval == null
- ? null
- : mt2.root_interval.CopyTree (from, to));
- root_interval.Insert (pos, interval);
+ MPlist p = mt2.intervals.Find (plist.Key);
+ MInterval interval;
+
+ if (p == null)
+ interval = new MInterval (plist.Key, to - from);
+ else
+ interval = ((MInterval) p.Val).copy (from, to);
+ ((MInterval) plist.Val).Insert (pos, interval);
}
}
}
}
- public MText dup ()
+ public MText Dup ()
{
return (new MText (sb.ToString ()));
}
- public MText ins (int pos, MText mt)
+ 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)
+ public MText Ins (int pos, MText mt, int from, int to)
{
insert (pos, mt, from, to);
return this;
}
- public MText del (int from, int to)
+ 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.Find (key).Val;
+
+ 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.Find (key).Val;
+
+ 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.Find (key).Val;
+
+ 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 (root_interval == null)
- root_interval = new MInterval (this);
- root_interval.Push (from, to, 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) p.Val).Pop (from, to);
+ }
+ }
+
+ public void DumpProp ()
+ {
+ Console.Write ("(");
+ foreach (MPlist p in intervals)
+ ((MInterval) p.Val).Dump ();
+ Console.WriteLine (")");
}
private class MInterval
{
- // position: 0 1 2 3
- // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
- // | | A | | B | | C | |
- // interval |<--------->|<--->|<--------------->|<----|
+ // position: 0 1 2 3 4 5 6 7
+ // | A | B | C | D | E F | G |
+ // interval |---|---|---|<->|-------|---|
+ // |---|<->|---| |<----->|---|
+ // |<->| |<->| |<->|
//
- // [-1 99 (9 89)]
- // [0 10 (-1 9)] [-10 0 (89 99)]
- // [0 4 (-1 3)] [-4 0 (5 9)] [0 4 (89 93)] [-2 0 (97 99)]
+ // [7 (3 4)]
+ // [3 (1 2)] [3 (4 6)]
+ // [1 (0 1)] [2 (2 3)] [1 (6 7)]
//
- // Start and end positions of this interval and its children.
- // If this is the left node, the values are relative to the
- // parent's total_start. Otherwise, the values are relative to
- // the parent's total_end. So:
- // total_start total_end
- // left-side interval 0 positive even
- // right-side interval negative even 0
- // top-most interval -1 positive odd
- private int total_start, total_end;
- // Stack of MTextProperty
- private Stack<MTextProperty> stack;
+ 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 MText mt;
+ private MText mtext;
- private static int adjust_position (int pos, bool front_inclusive)
+ public MInterval (MSymbol key, int length)
{
- return (pos << 2) + (front_inclusive ? -1 : 1);
+ if (length <= 0)
+ throw new Exception ("Invalid interval length");
+ this.key = key;
+ total_length = length;
+ stack = new MPlist ();
+ id = count++;
}
- private static bool before_point_p (int pos)
+ public MInterval (MSymbol key, MText mt)
{
- return ((pos + 1) % 4) == 0;
+ this.key = key;
+ mtext = mt;
+ total_length = mt.sb.Length;
+ from = 0;
+ to = total_length;
+ stack = new MPlist ();
+ id = count++;
}
- public MInterval (int start, bool front_inclusive,
- int end, bool rear_inclusive)
+ public MTextProperty Get (int pos)
{
- if (start > end)
- throw new Exception ("Invalid Interval Range");
- this.total_start = (start << 2) + (front_inclusive ? -1 : 1);
- this.total_end = (end << 2) + (rear_inclusive ? 1 : -1);
- this.stack = new Stack<MTextProperty> ();
+ MInterval i = find (pos);
+
+ return (i.stack.IsEmpty ? null : (MTextProperty) i.stack.Val);
}
- public MInterval (MText mt)
+ public MTextProperty Get (int pos, out MTextProperty[] array)
{
- this.mt = mt;
- this.total_start = -1;
- this.total_end = (mt.sb.Length << 2) + 1;
- this.stack = new Stack<MTextProperty> ();
- }
+ MInterval i = find (pos);
- private MInterval () { }
+ 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[idx - 1];
+ }
- private MInterval (int start, int end, Stack<MTextProperty> stack)
+ private MInterval (MSymbol key, int length, MPlist stack)
{
- this.total_start = start;
- this.total_end = end;
- this.stack = new Stack<MTextProperty> (stack);
+ this.key = key;
+ total_length = length;
+ from = 0;
+ to = total_length;
+ this.stack = stack.Clone ();
+ id = count++;
}
- private MInterval find (int pos, out int offset)
+ private void update_from_to ()
{
- if (pos < total_start || total_end < pos)
+ if (parent == null)
{
- offset = 0;
- return null;
+ from = LeftLength;
+ to = total_length - RightLength;
+ }
+ else if (parent.left == this)
+ {
+ from = parent.from - total_length + LeftLength;
+ to = parent.from - RightLength;
+ }
+ else
+ {
+ from = parent.to + LeftLength;
+ to = parent.to + total_length - RightLength;
}
- if (pos < Start)
- return left.find (pos, out offset);
- if (End < pos)
- return right.find (pos - total_end, out offset);
- offset = pos - Start;
+ }
+
+ private int LeftLength
+ {
+ get { return (left == null ? 0 : left.total_length); }
+ }
+
+ private int RightLength
+ {
+ get { return (right == null ? 0 : right.total_length); }
+ }
+
+ private MInterval left_most_node
+ {
+ get { return (left == null ? this : left.left_most_node); }
+ }
+
+ private MInterval right_most_node
+ {
+ get { return (right == null ? this : right.right_most_node); }
+ }
+
+ private MInterval prev {
+ get {
+ MInterval i;
+
+ if (left != null)
+ for (i = left; i.right != null; i = i.right);
+ else
+ for (i = parent; i != null && i.left == null; i = i.parent);
+ return i;
+ }
+ }
+
+ private MInterval next {
+ get {
+ MInterval i;
+
+ if (right != null)
+ for (i = right; i.left != null; i = i.left);
+ else
+ for (i = parent; i != null && i.right == null; 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;
}
// c1 c2 left c1
private MInterval promote_right ()
{
- int right_length = - right.total_start;
+ int right_length = right.total_length;
MInterval c1;
if (parent == null)
- mt.root_interval = right;
- else if (total_start == 0)
+ mtext.intervals.Put (key, right);
+ else if (parent.left == this)
parent.left = right;
else
parent.right = right;
parent = right;
right = c1;
- if (c1 != null)
- c1.parent = this;
-
- parent.total_start = total_start;
- parent.total_end = total_end;
- total_start = 0;
- total_end -= right_length - (c1 == null ? 0 : c1.total_end);
-
+ parent.total_length += total_length;
+ total_length -= right_length;
if (c1 != null)
{
- c1.total_end = - c1.total_start;
- c1.total_start = 0;
+ c1.parent = this;
+ parent.total_length -= c1.total_length;
+ total_length += c1.total_length;
}
return parent;
}
// c1 c2 c2 right
private MInterval promote_left ()
{
- int left_length = left.total_end;
- MInterval c2;
+ int left_length = left.total_length;
+ MInterval c1;
if (parent == null)
- mt.root_interval = left;
- else if (total_start == 0)
+ mtext.intervals.Put (key, left);
+ else if (parent.left == this)
parent.left = left;
else
parent.right = left;
left.parent = parent;
- c2 = left.right;
+ c1 = left.left;
left.right = this;
parent = left;
- left = c2;
- if (c2 != null)
- c2.parent = this;
-
- parent.total_start = total_start;
- parent.total_end = total_end;
- total_start -= left_length + (c2 == null ? 0 : c2.total_end);;
- total_end = 0;
-
- if (c2 != null)
+ left = c1;
+ parent.total_length += total_length;
+ total_length -= left_length;
+ if (c1 != null)
{
- c2.total_start = - c2.total_end;
- c2.total_end = 0;
+ c1.parent = this;
+ parent.total_length -= c1.total_length;
+ total_length += c1.total_length;
}
return parent;
}
private MInterval balance ()
{
- MInterval interval = this;
+ MInterval i = this;
while (true)
{
- int this_start = interval.Start;
- int this_end = interval.End;
- int diff = ((this_start - interval.total_start)
- - (interval.total_end - this_end));
- int abs = Math.Abs (diff);
+ // .-this-.
+ // .-left-. .-right-.
+ // c1 c2 c3 c4
+ int diff = i.LeftLength - i.RightLength;
+ int new_diff;
- if (abs < this_end - this_start)
- break;
- if (diff < 0)
+ if (diff > 0)
{
- interval = interval.promote_right ();
- interval.left.balance ();
+ new_diff = (i.total_length - i.LeftLength
+ + i.left.RightLength - i.left.LeftLength);
+ if (Math.Abs (new_diff) >= diff)
+ break;
+ i = i.promote_left ();
+ i.right.balance ();
}
- else
+ else if (diff < 0)
{
- interval = interval.promote_left ();
- interval.right.balance ();
+ new_diff = (i.total_length - i.RightLength
+ + i.right.LeftLength - i.right.RightLength);
+ if (Math.Abs (new_diff) >= diff)
+ break;
+ i = i.promote_right ();
+ i.left.balance ();
}
}
- return interval;
+ return i;
}
- public MInterval CopyTree (int start, int end)
+ public MInterval copy (int start, int end)
{
- MInterval interval_start, interval_end, interval;
- int offset_start, offset_end;
+ MInterval this_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);
+ }
+ else if (end > to)
+ {
+ if (start >= to)
+ return right.copy (start, end);
+ right_copy = right.copy (to, end);
+ }
+ this_copy = new MInterval (key, end - start, stack);
+ this_copy.left = left_copy;
+ this_copy.right = right_copy;
+
+ return this_copy;
+ }
- start <<= 2;
- end <<= 2;
- interval_start = find (start, out offset_start);
- interval_end = find (end, out offset_end);
+ // this-. ==> this-.
+ // right newright-.
+ // right
+ private MInterval divide_right (int pos)
+ {
+ MInterval interval = new MInterval (key, to - pos, stack);
- interval = new MInterval ();
- interval.total_start = 0;
- interval.total_end = end - start;
- interval.stack = new Stack<MTextProperty> (interval_start.stack);
- interval = interval.divide_right (offset_start);
- while (interval_start != interval_end)
+ Console.Write ("divide-right({0}) at ", pos); DumpOne (false, true);
+ to = pos;
+ if (right != null)
{
- interval_start = interval_start.Right;
- interval = interval.divide_right (interval_start.End
- - interval_start.Start);
+ interval.right = right;
+ right.parent = interval;
+ interval.total_length += right.total_length;
}
+ interval.parent = this;
+ right = interval;
return interval;
}
- private MInterval CopyNode ()
+ // .-this ==> .-this
+ // left .-newleft
+ // left
+ private MInterval divide_left (int pos)
{
- return new MInterval (total_start, total_end, stack);
- }
+ MInterval interval = new MInterval (key, pos - from, stack);
- private int Start {
- get {
- return (left == null ? total_start : total_start + left.total_end);
- }
+ Console.Write ("divide-reft({0}) at ", pos); DumpOne (false, true);
+ from = pos;
+ if (left != null)
+ {
+ interval.left = left;
+ left.parent = interval;
+ interval.total_length += left.total_length;
+ }
+ interval.parent = this;
+ left = interval;
+ return interval;
}
- private int End {
- get {
- return (right == null ? total_end : total_end + right.total_start);
- }
- }
+ private void remove_properties (MTextProperty.Flag flags)
+ {
+ for (MPlist p = stack; ! p.IsEmpty;)
+ {
+ MTextProperty prop = (MTextProperty) p.Val;
- private MInterval Left {
- get {
- MInterval i;
- if (left != null)
- for (i = left; i.right != null; i = i.right);
- else
- for (i = parent; i != null && i.total_start == 0; i = i.parent);
- return i;
- }
+ if ((prop.flags & flags) == flags)
+ p.Pop ();
+ else
+ p = p.Next;
+ }
}
- private MInterval Right {
- get {
- MInterval i;
- if (right != null)
- for (i = right; i.left != null; i = i.left);
- else
- for (i = parent; i != null && i.total_start < 0; i = i.parent);
- return i;
- }
+ private void merge_front_properties (MPlist plist)
+ {
+ for (MInterval i = left_most_node; 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);
+ }
+ }
}
- public void Push (int start, int end, MTextProperty prop)
+ private void merge_rear_properties (MPlist plist)
{
- start <<= 2;
- if (prop.FrontSticky)
- start--;
- else
- start++;
- end <<= 2;
- if (prop.RearSticky)
- end++;
- else
- end--;
- if (start >= end)
- throw new Exception ("Invalid Text Property Range");
+ for (MInterval i = right_most_node; i != null; i = i.prev)
+ {
+ if (! stack.IsEmpty)
+ break;
+ for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
+ {
+ MTextProperty prop = (MTextProperty) p.Val;
- push (start, end, prop);
+ if ((prop.flags & MTextProperty.Flag.FrontSticky)
+ == MTextProperty.Flag.FrontSticky)
+ i.stack.Add (prop.key, prop);
+ }
+ }
}
public void Insert (int pos, MInterval interval)
{
- if (pos < Start)
- Left.Insert (pos - total_start, interval);
- else if (pos > End)
- Right.Insert (pos - total_end, interval);
- else
+ update_from_to ();
+ Console.Write ("insert({0}) at ", pos); DumpOne (false, true);
+ if (pos < from || (pos == from && left == null && pos > 0))
{
- // position: 0 1 2 3
- // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
- // this |-----------<-----a----->-----|
- // |-----b-----| |--c--|
- //
- // interval <--A-->----------->
- // <--B-->----->
- // <--C-->
- //
- // new |-----------<-a-A->-----------------------|
- // |-----b-----| |-----------<--a-->-----|
- // |-a-B->-----| |--c--|
- // |-a-C-|
- int len = interval.total_end - interval.total_start;
- MInterval temp;
-
- total_end += len;
- for (temp = this; temp.parent != null;
- temp = temp.parent)
- temp.parent.total_end += len;
- temp = new MInterval ();
- temp.stack = new Stack<MTextProperty> (stack);
-
- temp = divide_right (Start + 2);
- temp.left = interval;
- right = interval;
+ 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)
+ {
+ if (pos > 0)
+ {
+ 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;
+ }
+ else
+ {
+ left = interval;
+
+ for (MInterval i = this; i != null; i = i.parent)
+ i.total_length += interval.total_length;
+ }
+ }
+ else // pos == to
+ {
+ if (right != null)
+ {
+ MInterval left_most = right.left_most_node;
+
+ left_most.remove_properties
+ (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
+ interval.merge_rear_properties (left_most.stack);
+ }
+ 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)
+ {
+ MInterval i = right.left_most_node;
+
+ i.left = interval;
+ interval.parent = i;
+ for (; i != null; i = i.parent)
+ i.total_length += interval.total_length;
+ }
+ else
+ {
+ right = interval;
+
+ for (MInterval i = this; i != null; i = i.parent)
+ i.total_length += interval.total_length;
+ }
+ }
}
- private MInterval divide_right (int pos)
+ private void vacate_node (MInterval interval)
{
- MInterval interval = CopyNode ();
- int this_start = Start;
- int this_end = End;
+ Console.WriteLine ("vacate #{0} to #{1}", id, interval.id);
+ if (interval != null)
+ interval.parent = parent;
+ if (parent == null)
+ {
+ mtext.intervals.Put (key, interval);
+ }
+ else
+ {
+ if (this == parent.right)
+ parent.right = interval;
+ else
+ parent.left = interval;
- if (left == null
- || (right != null && left.total_end < - right.total_start))
+ int diff = total_length;
+ if (interval != null)
+ diff -= interval.total_length;
+ for (MInterval i = parent; i != null; i = i.parent)
+ i.total_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)
{
- interval.left = this;
- interval.right = right;
- interval.parent = parent;
- if (parent != null)
+ if (end <= from)
{
- if (total_start == 0)
- parent.left = interval;
- else
- parent.right = interval;
+ left.Delete (start, end);
+ return;
}
- total_start = 0;
- total_end = pos - this_start;
+ left.Delete (start, from);
+ to -= from - start;
+ end -= from - start;
+ from = start;
}
- else
+ if (end > to)
{
- interval.total_start = pos - this_end;
- interval.total_end = 0;
- if (right != null)
- right.parent = interval;
- right = interval;
+ 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.total_length += left.total_length;
+ i.total_length += left.total_length;
+ i.left = left;
+ left.parent = i;
+ }
+ vacate_node (right);
+ }
+ }
+ else
+ {
+ int len = end - start;
- return interval;
+ for (MInterval i = this; i != null; i = i.parent)
+ i.total_length -= len;
+ }
}
- private MInterval divide_left (int pos)
+ public void Push (int start, int end, MTextProperty prop)
{
- MInterval interval = CopyNode ();
- int this_start = Start;
- int this_end = End;
-
- if (left == null
- || (right != null && left.total_end < - right.total_start))
+ update_from_to ();
+ Console.Write ("push({0} {1}) at ", start, end); DumpOne (false, true);
+ if (start < from)
{
- interval.total_start = 0;
- interval.total_end = pos - this_start;
- if (left != null)
- left.parent = interval;
- left = interval;
+ if (end <= from)
+ {
+ left.Push (start, end, prop);
+ return;
+ }
+ left.Push (start, from, prop);
+ start = from;
}
- else
+ if (end > to)
{
- interval.right = this;
- interval.left = left;
- interval.parent = parent;
- if (parent != null)
+ if (start >= to)
{
- if (total_start == 0)
- parent.left = interval;
- else
- parent.right = interval;
+ right.Push (start, end, prop);
+ return;
}
- total_start = pos - this_end;
- total_end = 0;
+ right.Push (to, end, prop);
+ end = to;
}
- return interval;
+ if (start > from)
+ divide_left (start);
+ if (end < to)
+ divide_right (end);
+ stack.Push (prop.key, prop);
}
- private void push (int start, int end, MTextProperty prop)
+ public void Pop (int start, int end)
{
- int this_start = Start;
- int this_end = End;
-
- if (start < this_start)
+ update_from_to ();
+ Console.Write ("pop({0} {1}) at ", start, end); DumpOne (false, true);
+ if (start < from)
{
- if (end <= this_start)
+ if (end <= from)
{
- Left.push (start, end, prop);
+ left.Pop (start, end);
return;
}
- Left.push (start, this_start, prop);
- start = this_start;
+ left.Pop (start, from);
+ start = from;
}
- if (this_end < end)
+ if (end > to)
{
- if (this_end < start)
+ if (start >= to)
{
- Right.push (start, end, prop);
+ right.Pop (start, end);
return;
}
- Right.push (this_end, end, prop);
- end = this_end;
+ right.Pop (to, end);
+ end = to;
}
- if (this_start < start)
- divide_left (start);
- if (end < this_end)
- divide_right (end);
- stack.Push (prop);
+
+ 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)
+ {
+ 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 ();
+ }
+
+ public void Dump ()
+ {
+ update_from_to ();
+
+ if (left != null)
+ left.Dump ();
+ if (from > 0)
+ Console.Write (" ");
+ DumpOne (true, false);
+ if (right != null)
+ right.Dump ();
}
}
projects / m17n / m17n-lib-cs.git / blobdiff