X-Git-Url: http://git.chise.org/gitweb/?a=blobdiff_plain;f=MText.cs;h=cdb6ad328403facac438e786dbc1eb2a4cb83141;hb=df8fc52d293cac1452df4ccd7bfaa4f5d745e86a;hp=ecc1689dcea58dcda9ba241a34967727d727494f;hpb=9361876fc803e02e7f23c9193a74f960b25a9784;p=m17n%2Fm17n-lib-cs.git diff --git a/MText.cs b/MText.cs index ecc1689..cdb6ad3 100644 --- a/MText.cs +++ b/MText.cs @@ -2,6 +2,7 @@ using System; using System.Text; using System.Collections; using System.Collections.Generic; +using M17N; using M17N.Core; namespace M17N.Core @@ -20,25 +21,57 @@ namespace M17N.Core 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 + { + get { return (flags & Flag.Sensitive) != Flag.None; } + } + + public MTextProperty (MSymbol key, object val) + { + this.key = key; + this.val = val; + flags |= Flag.RearSticky; + } + + public MTextProperty (MSymbol key, object val, + bool front_sticky, bool rear_sticky, bool sensitive) { - this.front_sticky = front_sticky; - this.rear_sticky = rear_sticky; + this.key = key; + this.val = val; + if (front_sticky) + flags |= Flag.FrontSticky; + if (rear_sticky) + flags |= Flag.RearSticky; + if (sensitive) + flags |= Flag.Sensitive; } - public MTextProperty (bool front_sticky, bool rear_sticky, bool merginable) + + public override string ToString () { - this.front_sticky = front_sticky; - this.rear_sticky = rear_sticky; - this.merginable = merginable; + return key.ToString () + ":" + val; } } @@ -47,12 +80,12 @@ namespace M17N.Core #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 (); @@ -80,24 +113,28 @@ namespace M17N.Core 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) @@ -128,7 +165,7 @@ namespace M17N.Core 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) { @@ -197,23 +234,71 @@ namespace M17N.Core 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 - ? new MInterval (0, false, to - from, false) - : 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, this, to - from); + else + interval = ((MInterval) p.Val).Copy (from, to); + ((MInterval) plist.Val).Insert (pos, interval); } } + private void insert (int pos, int c) + { + check_pos (pos, true); + + int pos_idx = pos_to_idx (this, pos); + + if (c < 0x10000) + { + char ch = (char) c; + sb.Insert (pos_idx, ch); + } + else + { + char high = (char) (0xD800 + ((c - 0x10000) >> 10)); + char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF)); + sb.Insert (pos_idx, low); + sb.Insert (pos_idx, high); + } + nchars++; + foreach (MPlist plist in intervals) + ((MInterval) plist.Val).Insert (pos, + new MInterval (plist.Key, this, 1)); + } + public int this[int i] { set { @@ -243,149 +328,365 @@ namespace M17N.Core } } - public MText dup () + 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 (0, Length)); + return mt; } - public MText ins (int pos, MText mt) + public MText Ins (int pos, int c) + { + insert (pos, c); + return this; + } + + public MText Ins (int pos, MText mt) { insert (pos, mt, 0, mt.nchars); return this; } - public MText ins (int pos, MText mt, int from, int to) + 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 Cat (int c) { + insert (nchars, c); + return this; + } + + public MText Del (int from, int to) + { + if (check_range (from, to, true)) + return this; + sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from)); nchars -= to - from; + + if (nchars > 0) + foreach (MPlist plist in intervals) + ((MInterval) plist.Val).Delete (from, to); + else + intervals = new MPlist (); return this; } + public object GetProp (int pos, MSymbol key) + { + check_pos (pos, false); + + MInterval i = (MInterval) intervals.Get (key); + if (i == null) + return null; + + MTextProperty prop = i.Get (pos); + return (prop != null ? prop.Val : null); + } + + public object GetProp (int pos, MSymbol key, out MTextProperty prop) + { + check_pos (pos, false); + + MInterval i = (MInterval) intervals.Get (key); + if (i == null) + return (prop = null); + prop = i.Get (pos); + return (prop != null ? prop.Val : null); + } + + public object GetProp (int pos, MSymbol key, out MTextProperty[] array) + { + check_pos (pos, false); + + MInterval i = (MInterval) intervals.Get (key); + if (i == null) + return (array = null); + MTextProperty prop = i.Get (pos, out array); + return (prop != null ? prop.Val : null); + } + + public void PushProp (int from, int to, MSymbol key, object val) + { + if (! check_range (from, to, true)) + PushProp (from, to, new MTextProperty (key, val)); + } + public void PushProp (int from, int to, MTextProperty prop) { - if (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 root = (MInterval) p.Val; + root.Pop (from, to); + root.MergeAfterChange (from, to); + } + } + } + + public void DumpProp () + { + Console.Write ("("); + foreach (MPlist p in intervals) + ((MInterval) p.Val).Dump (true); + Console.WriteLine (")"); + } + + public void DumpPropNested () + { + foreach (MPlist p in intervals) + ((MInterval) p.Val).DumpNested (true); } private class MInterval { - // position: 0 1 2 3 - // 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 stack; - private MInterval left, right, parent; - private MText mt; - - private static int adjust_position (int pos, bool front_inclusive) + private static int count = 0; + private int ID; + private int Length; + private int From, To; + private MSymbol Key; + private MPlist Stack; + private MInterval Left, Right, Parent; + private MText mtext; + + public MInterval (MSymbol key, MText mt, int length) { - return (pos << 2) + (front_inclusive ? -1 : 1); + if (length <= 0) + throw new Exception ("Invalid interval length"); + Key = key; + mtext = mt; + 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; + Key = key; + mtext = mt; + Length = mt.sb.Length; + From = 0; + To = 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 (); + 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 (); - } + MInterval i = find (pos); + + if (i.Stack.IsEmpty) + { + array = null; + return null; + } + array = new MTextProperty[i.Stack.Count]; - private MInterval () { } + int idx; + MPlist p; + for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next) + array[idx] = (MTextProperty) p.Val; + return array[0]; + } - private MInterval (int start, int end, Stack stack) + private MInterval (MSymbol key, MText mt, int length, MPlist stack) { - this.total_start = start; - this.total_end = end; - this.stack = new Stack (stack); + Key = key; + mtext = mt; + Length = length; + From = 0; + To = Length; + 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 = Length - RightLength; + } + else if (Parent.Left == this) + { + From = Parent.From - Length + LeftLength; + To = Parent.From - RightLength; + } + else + { + From = Parent.To + LeftLength; + To = Parent.To + Length - RightLength; } - 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.Length); } + } + + private int RightLength + { + get { return (Right == null ? 0 : Right.Length); } + } + + private MInterval LeftMost + { + get { return (Left == null ? this : Left.LeftMost); } + } + + private MInterval RightMost + { + get { return (Right == null ? this : Right.RightMost); } + } + + private MInterval Prev { + get { + MInterval i; + + if (Left != null) + for (i = Left; i.Right != null; i = i.Right); + else + { + MInterval child = this; + for (i = Parent; i != null && i.Left == child; + child = i, i = i.Parent); + } + return i; + } + } + + private MInterval Next { + get { + MInterval i; + + if (Right != null) + for (i = Right; i.Left != null; i = i.Left); + else + { + MInterval child = this; + for (i = Parent; i != null && i.Right == child; + child = i, i = i.Parent); + } + return i; + } + } + + private MInterval find (int pos) + { + update_from_to (); + if (pos < From) + return Left.find (pos); + if (pos >= To) + return Right.find (pos); return this; } + private bool mergeable (MInterval i) + { + MPlist p1, p2; + + for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty; + p1 = p1.Next, p2 = p2.Next) + if (p1.Val != p2.Val) + return false; + return (p1.IsEmpty && p2.IsEmpty); + } + // p-. or .-p p-. or .-p // .-this-. .-right-. // left .-right-. -> .-this-. c2 // c1 c2 left c1 private MInterval promote_right () { - int right_length = - right.total_start; + int right_length = Right.Length; MInterval c1; - if (parent == null) - mt.root_interval = right; - else if (total_start == 0) - parent.left = right; + 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; - 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.Right = Right; + Right.Parent = Parent; + c1 = Right.Left; + Right.Left = this; + + Parent = Right; + Right = c1; + Parent.Length += Length; + Length -= right_length; if (c1 != null) { - c1.total_end = - c1.total_start; - c1.total_start = 0; + c1.Parent = this; + Parent.Length -= c1.Length; + Length += c1.Length; } - return parent; + return Parent; } // p-. or .-p p-. or .-p @@ -394,286 +695,755 @@ namespace M17N.Core // c1 c2 c2 right private MInterval promote_left () { - int left_length = left.total_end; - MInterval c2; + int left_length = Left.Length; + MInterval c1; - if (parent == null) - mt.root_interval = left; - else if (total_start == 0) - parent.left = left; + if (Parent == null) + mtext.intervals.Put (Key, Left); + else if (Parent.Left == this) + Parent.Left = Left; else - parent.right = left; - left.parent = parent; - c2 = left.right; - left.right = this; - - parent = left; - left = c2; - if (c2 != null) - c2.parent = this; - - parent.total_start = total_start; - parent.total_end = total_end; - total_start -= left_length + (c2 == null ? 0 : c2.total_end);; - total_end = 0; - - if (c2 != null) + Parent.Right = Left; + Left.Parent = Parent; + c1 = Left.Left; + Left.Right = this; + + Parent = Left; + Left = c1; + Parent.Length += Length; + Length -= left_length; + if (c1 != null) { - c2.total_start = - c2.total_end; - c2.total_end = 0; + c1.Parent = this; + Parent.Length -= c1.Length; + Length += c1.Length; } - return parent; + 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.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.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 copy, left_copy = null, right_copy = null; + + update_from_to (); + + if (start < From) + { + if (end <= From) + return Left.Copy (start, end); + left_copy = Left.Copy (start, From); + } + if (end > To) + { + if (start >= To) + return Right.Copy (start, end); + right_copy = Right.Copy (To, end); + } + + copy = new MInterval (Key, null, end - start, Stack); + remove_properties (MTextProperty.Flag.Sensitive); + if (left_copy != null) + { + copy.Left = left_copy; + left_copy.Parent = copy; + } + if (right_copy != null) + { + copy.Right = right_copy; + right_copy.Parent = copy; + } + return copy; + } - 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, mtext, To - pos, Stack); - interval = new MInterval (); - interval.total_start = 0; - interval.total_end = end - start; - interval.stack = new Stack (interval_start.stack); - interval = interval.divide_right (offset_start); - while (interval_start != interval_end) + M17N.DebugPrint ("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.Length += Right.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, mtext, pos - From, Stack); + + M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true); + From = pos; + if (Left != null) + { + interval.Left = Left; + Left.Parent = interval; + interval.Length += Left.Length; + } + interval.Parent = this; + Left = interval; + return interval; } - private int Start { - get { - return (left == null ? total_start : total_start + left.total_end); - } + private void remove_properties (MTextProperty.Flag flags) + { + for (MPlist p = Stack; ! p.IsEmpty;) + { + MTextProperty prop = (MTextProperty) p.Val; + + if ((prop.flags & flags) == flags) + p.Pop (); + else + p = p.Next; + } } - private int End { - get { - return (right == null ? total_end : total_end + right.total_start); - } + private void inherit_front_properties (MPlist plist) + { + for (MInterval i = LeftMost; i != null; i = i.Next) + { + if (! Stack.IsEmpty) + break; + for (MPlist p = plist; ! p.IsEmpty; p = p.Next) + { + MTextProperty prop = (MTextProperty) p.Val; + + if ((prop.flags & MTextProperty.Flag.RearSticky) + == MTextProperty.Flag.RearSticky) + i.Stack.Add (prop.key, prop); + } + } } - private 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; - } + private void inherit_rear_properties (MPlist plist) + { + for (MInterval i = RightMost; i != null; i = i.Prev) + { + if (! Stack.IsEmpty) + break; + for (MPlist p = plist; ! p.IsEmpty; p = p.Next) + { + MTextProperty prop = (MTextProperty) p.Val; + + if ((prop.flags & MTextProperty.Flag.FrontSticky) + == MTextProperty.Flag.FrontSticky) + i.Stack.Add (prop.key, prop); + } + } } - private MInterval 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 MInterval delete_node_forward () + { + if (Parent != null) + { + int len = Length - RightLength; + + for (MInterval i = Parent; i != null; i = i.Parent) + i.Length -= len; + if (Parent.Left == this) + Parent.Left = Right; + else + Parent.Right = Right; + } + + if (Right != null) + { + Right.Parent = Parent; + return Right.LeftMost; + } + return Parent; } - public void Push (int start, int end, MTextProperty prop) + private MInterval delete_node_backward () { - 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"); + if (Parent != null) + { + int len = Length - RightLength; - push (start, end, prop); + for (MInterval i = Parent; i != null; i = i.Parent) + i.Length -= len; + if (Parent.Left == this) + Parent.Left = Left; + else + Parent.Right = Left; + } + + if (Left != null) + { + Left.Parent = Parent; + return Left.RightMost; + } + return Parent; } - public void Insert (int pos, MInterval interval) + private void set_mtext (MText mt) { - if (pos < Start) - Left.Insert (pos - total_start, interval); - else if (pos > End) - Right.Insert (pos - total_end, interval); + mtext = mt; + if (Left != null) + Left.set_mtext (mt); + if (Right != null) + Right.set_mtext (mt); + } + + private MInterval graft (MInterval interval, bool forward, out int len) + { + MInterval i; + + len = 0; + if (forward) + { + i = interval.LeftMost; + while (i != null) + { + if (! mergeable (i)) + break; + len += i.Length - i.RightLength; + i = i.delete_node_forward (); + } + } else { - // position: 0 1 2 3 - // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 - // this |<----------<----------->---->| - // |<--------->| |<--->| - // - // BBBBB - // AAAAA - // interval |<--->| - // - // new |<----------<----->----->-->------------>->| - // |<--------->| |<---->-->------------>->| - // |<----------->->| - // |<>| - int len = interval.total_end - interval.total_start; - MInterval temp; - - total_end += len; - for (temp = this; temp.parent != null; - temp = temp.parent) - temp.parent.total_end += len; - if (End - pos < interval.End) + i = interval.RightMost; + while (i != null) { - - + if (! mergeable (i)) + break; + len += i.Length - i.LeftLength; + i = i.delete_node_backward (); } + } - temp = divide_right (Start + 2); - temp.left = interval; - right = interval; - } - - + 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; } - private MInterval divide_right (int pos) + public void Insert (int pos, MInterval interval) { - MInterval interval = CopyNode (); - int this_start = Start; - int this_end = End; + update_from_to (); + M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos); + DumpOne (false, true); + + interval.set_mtext (mtext); - if (left == null - || (right != null && left.total_end < - right.total_start)) + if (pos < From) + Prev.Insert (pos, interval); + else if (pos == From) { - interval.left = this; - interval.right = right; - interval.parent = parent; - if (parent != null) + MInterval prev = Prev; + + if (prev != null) { - if (total_start == 0) - parent.left = interval; + if (Left == null) + { + prev.Insert (pos, interval); + return; + } + prev.remove_properties + (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky); + interval.inherit_front_properties (prev.Stack); + } + remove_properties + (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky); + interval.inherit_rear_properties (Stack); + + int len; + interval = graft (interval, false, out len); + if (interval != null && prev != null) + interval = prev.graft (interval, true, out len); + if (interval != null) + { + MInterval i; + + if (Left != null) + { + // .-this-. ==> .-this-. + // left-. .-left-. + // child child-. + // interval + i = Left.RightMost; + i.Right = interval; + } else - parent.right = interval; + { + Left = interval; + i = this; + } + interval.Parent = i; + for (; i != null; i = i.Parent) + i.Length += interval.Length; } - total_start = 0; - total_end = pos - this_start; } - else + else if (pos < To) { - interval.total_start = pos - this_end; - interval.total_end = 0; - if (right != null) - right.parent = interval; - right = interval; + remove_properties (MTextProperty.Flag.Sensitive); + + int len; + interval = graft (interval, true, out len); + pos += len; + if (interval != null) + interval = graft (interval, false, out len); + if (interval != null) + { + divide_right (pos); + Right.Left = interval; + interval.Parent = Right; + for (MInterval i = Right; i != null; i = i.Parent) + i.Length += interval.Length; + } } + else if (pos == To) + { + MInterval next = Next; - return interval; + if (next != null) + { + if (Right == null) + { + next.Insert (pos, interval); + return; + } + next.remove_properties + (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky); + interval.inherit_rear_properties (next.Stack); + } + remove_properties + (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky); + interval.inherit_front_properties (Stack); + + int len; + interval = graft (interval, true, out len); + if (interval != null && next != null) + interval = next.graft (interval, false, out len); + if (interval != null) + { + MInterval i; + + if (Right != null) + { + // .-this-. ==> .-this-. + // .-right .-right + // child .-child + // interval + + i = Right.LeftMost; + i.Left = interval; + } + else + { + Right = interval; + i = this; + } + interval.Parent = i; + for (; i != null; i = i.Parent) + i.Length += interval.Length; + } + } + else // (pos > To) + Next.Insert (pos, interval); } - private MInterval divide_left (int pos) + private void vacate_node (MInterval interval) { - MInterval interval = CopyNode (); - int this_start = Start; - int this_end = End; + M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID); + if (interval != null) + interval.Parent = Parent; + if (Parent == null) + { + if (mtext != null) + mtext.intervals.Put (Key, interval); + } + else + { + if (this == Parent.Right) + Parent.Right = interval; + else + Parent.Left = interval; - if (left == null - || (right != null && left.total_end < - right.total_start)) + int diff = Length; + if (interval != null) + diff -= interval.Length; + for (MInterval i = Parent; i != null; i = i.Parent) + i.Length -= diff; + } + } + + public void Delete (int start, int end) + { + update_from_to (); + M17N.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true); + if (start < From) + { + if (end <= From) + { + Left.Delete (start, end); + return; + } + Left.Delete (start, From); + To -= From - start; + end -= From - start; + From = start; + } + if (end > To) + { + if (start >= To) + { + Right.Delete (start, end); + return; + } + Right.Delete (To, end); + end = To; + } + if (start == From && end == To) { - interval.total_start = 0; - interval.total_end = pos - this_start; - if (left != null) - left.parent = interval; - left = interval; + if (Right == null) + { + vacate_node (Left); + } + else + { + if (Left != null) + { + MInterval i; + + for (i = Right; i.Left != null; i = i.Left) + i.Length += Left.Length; + i.Length += Left.Length; + i.Left = Left; + Left.Parent = i; + } + vacate_node (Right); + } } else { - interval.right = this; - interval.left = left; - interval.parent = parent; - if (parent != null) + int len = end - start; + + for (MInterval i = this; i != null; i = i.Parent) + i.Length -= len; + } + } + + public void Push (int start, int end, MTextProperty prop) + { + update_from_to (); + M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true); + if (start < From) + { + if (end <= From) + { + Left.Push (start, end, prop); + return; + } + Left.Push (start, From, prop); + start = From; + } + if (end > To) + { + if (start >= To) { - if (total_start == 0) - parent.left = interval; + Right.Push (start, end, prop); + return; + } + Right.Push (To, end, prop); + end = To; + } + + if (start > From) + divide_left (start); + if (end < To) + divide_right (end); + Stack.Push (prop.key, prop); + } + + private static void merge_nodes (MInterval head, MInterval tail) + { + M17N.DebugPrint ("merging "); head.DumpOne (true, false); + M17N.DebugPrint (" through "); tail.DumpOne (true, true); + + int from = head.From; + int to = tail.To; + MInterval root; + + for (root = head; root.To + head.RightLength < to; + root = root.Parent); + + M17N.DebugPrint ("common root is "); root.DumpOne (false, true); + + if (from < root.From) + { + MInterval prev = root.Prev; + + while (true) + { + int len = prev.Length - prev.LeftLength; + + M17N.DebugPrint ("merging "); prev.DumpOne (false, true); + if (prev.Left != null) + { + prev.Left.Parent = prev.Parent; + if (prev.Parent.Right == prev) + prev.Parent.Right = prev.Left; + else + prev.Parent.Left = prev.Left; + for (MInterval i = prev.Parent; i != root; i = i.Parent) + i.Length -= len; + if (prev == head) + break; + prev = prev.Left.RightMost; + } else - parent.right = interval; + { + prev.Parent.Right = null; + for (MInterval i = prev.Parent; i != root; i = i.Parent) + i.Length -= len; + if (prev == head) + break; + prev = prev.Parent; + } } - total_start = pos - this_end; - total_end = 0; } + if (root.To < to) + { + MInterval next = root.Next; - return interval; + while (true) + { + int len = next.Length - next.RightLength; + + M17N.DebugPrint ("merging "); next.DumpOne (false, true); + if (next.Right != null) + { + next.Right.Parent = next.Parent; + if (next.Parent.Left == next) + next.Parent.Left = next.Right; + else + next.Parent.Right = next.Right; + for (MInterval i = next.Parent; i != root; i = i.Parent) + i.Length -= len; + if (next == tail) + break; + next = next.Right.LeftMost; + } + else + { + next.Parent.Left = null; + for (MInterval i = next.Parent; i != root; i = i.Parent) + i.Length -= len; + if (next == tail) + break; + next = next.Parent; + } + } + } } - private void push (int start, int end, MTextProperty prop) + public void MergeAfterChange (int start, int end) { - int this_start = Start; - int this_end = End; + update_from_to (); + if (start < From) + { + Prev.MergeAfterChange (start, end); + return; + } + + MInterval head = this, tail = this, i; - if (start < this_start) + if (start == From && start > 0) { - if (end <= this_start) + i = Prev; + if (mergeable (i)) + head = i; + } + while (tail.To < end) + { + i = tail.Next; + if (! tail.mergeable (i)) { - Left.push (start, end, prop); + if (head != tail) + merge_nodes (head, tail); + head = i; + } + tail = i; + } + while (true) + { + i = tail.Next; + if (i == null || ! tail.mergeable (i)) + break; + tail = i; + } + if (head != tail) + merge_nodes (head, tail); + } + + public void Pop (int start, int end) + { + update_from_to (); + M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true); + if (start < From) + { + if (end <= From) + { + Left.Pop (start, end); return; } - Left.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 (! Stack.IsEmpty) + { + if (start > From) + divide_left (start); + if (end < To) + divide_right (end); + Stack.Pop (); + } + } + + private void DumpOne (bool with_prop, bool newline) + { + DumpOne (with_prop, newline, false); + } + + private void DumpOne (bool with_prop, bool newline, bool force) + { + if (force || M17N.debug) + { + Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To); + if (with_prop) + foreach (MPlist p in Stack) + Console.Write (" " + p.Val); + Console.Write (")"); + if (newline) + Console.WriteLine (); + if (Length <= 0) + throw new Exception ("Invalid interval length"); + } + } + + public void Dump () { Dump (false); } + + public void Dump (bool force) + { + if (force || M17N.debug) + { + update_from_to (); + + if (Left != null) + Left.Dump (force); + if (From > 0) + Console.Write (" "); + DumpOne (true, false, force); + if (Right != null) + Right.Dump (force); + } + } + + private int Depth { + get { return (Parent == null ? 0 : Parent.Depth + 1); } + } + + public void DumpNested (bool force) + { + DumpNested ("", force); + } + + public void DumpNested (string indent, bool force) + { + if (force || M17N.debug) + { + int indent_type = (Parent == null ? 1 + : Parent.Left == this ? 0 : 2); + + update_from_to (); + if (Left != null) + { + if (indent_type <= 1) + Left.DumpNested (indent + " ", force); + else + Left.DumpNested (indent + "| ", force); + } + if (indent_type == 0) + Console.Write (indent + ".-"); + else if (indent_type == 2) + Console.Write (indent + "`-"); + DumpOne (true, true, true); + if (Right != null) + { + if (indent_type >= 1) + Right.DumpNested (indent + " ", force); + else + Right.DumpNested (indent + "| ", force); + } } - if (this_start < start) - divide_left (start); - if (end < this_end) - divide_right (end); - stack.Push (prop); } }