X-Git-Url: http://git.chise.org/gitweb/?a=blobdiff_plain;f=MText.cs;h=52d19437b7b941f1489ab44b3ce6ddf7c759e6c0;hb=4419a829ffcf2280a03ba5f407679595ae7e5788;hp=45d711bbd8d1e13a3138bb5ac2d522858230bbd0;hpb=9b29b6e5a76d7aa307e5e07664d19f1ba271deae;p=m17n%2Fm17n-lib-cs.git diff --git a/MText.cs b/MText.cs index 45d711b..52d1943 100644 --- a/MText.cs +++ b/MText.cs @@ -19,54 +19,59 @@ namespace M17N.Core } #endif - public class MTextProperty + public class MProperty { + [FlagsAttribute] + public enum Flags + { + None = 0x00, + /// A text inserted before a character that has this property + /// inherits this property. If the text already has properties + /// of the same key, they are deleted. + FrontSticky = 0x01, + /// A text inserted after a character that has this property + /// inherits this property. If the text already has properties + /// of the same key, they are deleted. + RearSticky = 0x02, + /// This property is deleted from a span of text if the span is + /// modified (i.e. a character is changed, a text is inserted, + /// some part is deleted). This propery is also deleted if a + /// property of the same key is added, which means that this + /// property is not stackable. + Sensitive = 0x04, + /// Like Sensitive but also this property is deleted from a span + /// of text if a text just before the span is modified, + /// inserted, or deleted. + FrontSensitive = 0x08, + /// Like Sensitive but also this property is deleted from a span + /// of text if a text just after the span is modified, inserted, + /// or deleted. + RearSensitive = 0x10 + }; + 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.None); } public override string ToString () @@ -137,14 +142,30 @@ namespace M17N.Core intervals = new MPlist (); } - public static MText operator+ (MText mt1, MText mt2) + public static MText operator+ (object obj, MText mt) + { + if (obj is string) + { + MText mtnew = new MText ((string) obj); + return mtnew.Ins (mtnew.Length, mt); + } + throw new Exception ("Unknown object type: " + obj.GetType()); + } + + public static MText operator+ (MText mt, object obj) { - MText mt = new MText (); + 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()); + } - mt.sb.Append (mt1.sb); - mt.sb.Append (mt2.sb); - mt.nchars = mt1.nchars + mt2.nchars; - return mt; + public static MText operator+ (MText mt1, MText mt2) + { + return mt1.Dup ().Ins (mt1.Length, mt2); } // Public properties @@ -165,7 +186,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) { @@ -252,27 +273,42 @@ namespace M17N.Core { 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) @@ -295,8 +331,7 @@ namespace M17N.Core } 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] @@ -333,7 +368,20 @@ namespace M17N.Core 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; } @@ -371,9 +419,16 @@ namespace M17N.Core 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; } @@ -385,11 +440,11 @@ namespace M17N.Core 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); @@ -400,24 +455,24 @@ namespace M17N.Core 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) { @@ -441,7 +496,11 @@ namespace M17N.Core else root = (MInterval) p.Val; + if (root.isSensitive) + root.PopSensitive (from, to); root.Push (from, to, prop); + root.MergeAfterChange (from, to); + root.Balance (); } } @@ -464,7 +523,18 @@ namespace M17N.Core MPlist p = intervals.Find (key); if (p != null) - ((MInterval) p.Val).Pop (from, to); + { + MInterval root = (MInterval) p.Val; + if (root.isSensitive) + root.PopSensitive (from, to); + else + root.Pop (from, to); + root = (MInterval) p.Val; + if (M17n.debug) + DumpPropNested (); + root.MergeAfterChange (from, to); + root.Balance (); + } } } @@ -478,6 +548,7 @@ namespace M17N.Core public void DumpPropNested () { + Console.WriteLine ("total length = {0}", Length); foreach (MPlist p in intervals) ((MInterval) p.Val).DumpNested (true); } @@ -525,29 +596,33 @@ namespace M17N.Core 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; - return array[idx - 1]; + array[idx] = (MProperty) p.Val; + return array[0]; } private MInterval (MSymbol key, MText mt, int length, MPlist stack) @@ -557,10 +632,45 @@ namespace M17N.Core 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) ; } + } + + public bool isAnySensitive + { + get { return MProperty.HasFlags (Key, + (MProperty.Flags.Sensitive + | MProperty.Flags.RearSensitive + | MProperty.Flags.FrontSensitive)) ; } + } + private void update_from_to () { if (Parent == null) @@ -592,12 +702,22 @@ namespace M17N.Core 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 { @@ -605,7 +725,11 @@ namespace M17N.Core 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; @@ -621,7 +745,11 @@ namespace M17N.Core 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; @@ -632,13 +760,23 @@ namespace M17N.Core } } - 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; } @@ -659,29 +797,31 @@ namespace M17N.Core // 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; } @@ -691,36 +831,39 @@ namespace M17N.Core // 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-. @@ -735,8 +878,10 @@ namespace M17N.Core + 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) { @@ -744,14 +889,17 @@ namespace M17N.Core + 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; @@ -760,18 +908,20 @@ namespace M17N.Core 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; @@ -785,6 +935,30 @@ namespace M17N.Core 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); + + if (! head.Stack.IsEmpty + && (isAnySensitive && head.From < start + || isFrontSensitive && ! first)) + { + head = copy.find_head (0); + head.Stack.Clear (); + } + if (! tail.Stack.IsEmpty + && (isAnySensitive && end < head.To + || isRearSensitive && ! last)) + { + tail = copy.find_tail (copy.Length); + tail.Stack.Clear (); + } + return copy; + } + // this-. ==> this-. // right newright-. // right @@ -792,7 +966,7 @@ namespace M17N.Core { 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) { @@ -812,7 +986,7 @@ namespace M17N.Core { 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) { @@ -825,279 +999,311 @@ namespace M17N.Core 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; - - if ((prop.flags & MTextProperty.Flag.FrontSticky) - == MTextProperty.Flag.FrontSticky) - i.Stack.Add (prop.key, prop); - } - } - } + int len; - 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 || isRearSensitive) && i.From < start))) + { + M17n.DebugPrint (" 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 (" 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; + int len; - 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) + 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; - } - - 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; + MInterval i = interval.find_tail (end); - len = 0; - if (forward) - { - i = interval.LeftMost; - while (i != null) + len = 0; + if (Stack.IsEmpty + && (isRearSensitive + || ((isSensitive || isFrontSensitive) && end < i.To))) { - if (! mergeable (i)) - break; - len += i.Length - i.RightLength; - i = i.delete_node_forward (); + M17n.DebugPrint (" 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 (" 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) { - if (Left == null) - { - prev.Insert (pos, interval); - return; - } - prev.remove_properties - (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky); - interval.inherit_front_properties (prev.Stack); + prev.enlarge (end - start); + return; } - 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 (isFrontSticky && ! Stack.IsEmpty) { - MInterval i; - - if (Left != null) - { - // .-this-. ==> .-this-. - // left-. .-left-. - // child child-. - // interval - i = Left.RightMost; - i.Right = interval; - } - else - { - Left = interval; - i = this; - } - interval.Parent = i; - for (; i != null; i = i.Parent) - i.Length += interval.Length; + enlarge (end - start); + 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) + return; + front_grafted = true; + } + if ((grafted = graft_backward (interval, start, end)) > 0) + { + end -= grafted; + if (start == end) + return; + 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, + rear_grafted); + else + interval = new MInterval (Key, mtext, end - start, null); + + MInterval i; + if (Left != null) { - divide_right (pos); - Right.Left = interval; - interval.Parent = Right; - for (MInterval i = Right; i != null; i = i.Parent) - i.Length += interval.Length; + // .-this-. ==> .-this-. + // left-. .-left-. + // child child-. + // interval + i = Left.RightMost; + i.Right = interval; } + else + { + Left = interval; + i = this; + } + interval.Parent = i; + for (; i != null; i = i.Parent) + i.Length += interval.Length; } - else if (pos == To) + else if (pos < To) { - MInterval next = Next; - - if (next != null) + if (! Stack.IsEmpty) { - if (Right == null) + if (isSensitive || isFrontSensitive || isRearSensitive) + 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); + bool front_grafted = false, rear_grafted = false; + int grafted; + if ((grafted = graft_forward (interval, start, end)) > 0) + { + start += grafted; + if (start == end) + return; + front_grafted = true; + pos += grafted; + } + if ((grafted = graft_backward (interval, start, end)) > 0) + { + end -= grafted; + if (start == end) + 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; + + if (isRearSensitive) + Stack.Clear (); + if (next != null && isFrontSensitive) + next.Stack.Clear (); + if (isRearSticky && ! Stack.IsEmpty) { - MInterval i; + enlarge (end - start); + return; + } + if (next != null && isFrontSticky && ! next.Stack.IsEmpty) + { + next.enlarge (end - start); + 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) + return; + rear_grafted = true; + } + if ((grafted = graft_forward (interval, start, end)) > 0) + { + start += grafted; + if (start == end) + return; + front_grafted = true; + } + if (interval != null) + interval = interval.Copy (mtext, start, end, + front_grafted, + rear_grafted || next == null); + else + interval = new MInterval (Key, mtext, end - start, null); - if (Right != null) - { - // .-this-. ==> .-this-. - // .-right .-right - // child .-child - // interval + 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; + 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) @@ -1115,7 +1321,7 @@ namespace M17N.Core 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; } } @@ -1123,31 +1329,53 @@ namespace M17N.Core 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 || isFrontSensitive) + 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 || isRearSensitive) + Stack.Clear (); Right.Delete (To, end); end = To; + rear_checked = true; } if (start == From && end == To) { + if (! front_checked + && start > 0 + && isRearSensitive) + Prev.Stack.Clear (); + if (! rear_checked + && end < mtext.Length + && isFrontSensitive) + Next.Stack.Clear (); if (Right == null) { vacate_node (Left); @@ -1171,15 +1399,17 @@ namespace M17N.Core { int len = end - start; + if (isAnySensitive) + 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) @@ -1201,6 +1431,8 @@ namespace M17N.Core end = To; } + if (! Stack.IsEmpty && isAnySensitive) + Stack.Clear (); if (start > From) divide_left (start); if (end < To) @@ -1208,78 +1440,98 @@ namespace M17N.Core Stack.Push (prop.key, prop); } - private bool try_merge_prev () + /// 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) { - MInterval prev = Prev; + M17n.DebugPrint ("combining {0} through {1}", head, tail); - if (! mergeable (prev)) - return false; + head.update_from_to (); + tail.update_from_to (); + int from = head.From; + int to = tail.To; - M17N.DebugPrint ("merging "); DumpOne (false, false); - M17N.DebugPrint (" with prev "); prev.DumpOne (false, true); - int len = prev.Length - prev.LeftLength; + // The nearest common parent of HEAD and TAIL. + MInterval root; + for (root = head; root.To + root.RightLength < to; + root = root.Parent); + + M17n.DebugPrint (" with common root {0}\n", root); - // PREV is Left, Left.Right, ..., or Left....Right. - if (prev != Left) + if (from < root.From) { - if (prev.Left != null) - prev.Left.Parent = prev.Parent; - prev.Parent.Right = prev.Left; - while (prev.Parent != Left) + MInterval prev = root.Prev; + + while (true) { - prev.Length -= len; - prev = prev.Parent; + M17n.DebugPrint ("merging {0}\n", prev); + prev.vacate_node (prev.Left, root); + if (prev == head) + break; + if (prev.Left != null) + prev = prev.Left.RightMost; + else + prev = prev.Parent; } + root.update_from_to (); } - Left.Length -= len; - if (Left.Length == Left.LeftLength) + if (root.To < to) { - if (Left.Left != null) - Left.Left.Parent = this; - Left = Left.Left; + MInterval next = root.Next; + + while (true) + { + M17n.DebugPrint ("merging {0}\n", next); + next.vacate_node (next.Right, root); + if (next == tail) + break; + if (next.Right != null) + next = next.Right.LeftMost; + else + next = next.Parent; + } + root.update_from_to (); } - return true; } - private bool try_merge_next () + public void MergeAfterChange (int start, int end) { - MInterval next = Next; - - if (! mergeable (next)) - return false; + update_from_to (); - M17N.DebugPrint ("merging "); DumpOne (false, false); - M17N.DebugPrint (" with next "); next.DumpOne (false, true); + MInterval head = find_head (start), i = head; + MInterval tail = start < end ? find_tail (end) : head; - int len = next.Length - next.RightLength; + if (tail.To < Length) + tail = tail.Next; - // NEXT is Right, Right.Left, ..., or Right....Left. - if (next != Right) + if (start == head.From && start > 0) { - if (next.Right != null) - next.Right.Parent = next.Parent; - next.Parent.Left = next.Right; - while (next.Parent != Right) - { - next.Length -= len; - next = next.Parent; - } + MInterval prev = head.Prev; + if (head.mergeable (prev)) + head = prev; } - Right.Length -= len; - if (Right.Length == Right.RightLength) + M17n.DebugPrint ("merge between {0} and {1}\n", head, tail); + while (i != tail) { - if (Right.Right != null) - Right.Right.Parent = this; - Right = Right.Right; + MInterval next = i.Next; + + if (! i.mergeable (next)) + { + if (head != i) + combine (head, i); + head = next; + } + i = next; } - return true; + 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) @@ -1303,46 +1555,80 @@ namespace M17N.Core if (! Stack.IsEmpty) { - bool check_prev = start == From && start > 0; - bool check_next = end == To && end < mtext.Length; - - if (! check_prev) - divide_left (start); - if (! check_next) - divide_right (end); - Stack.Pop (); - if (check_prev && Left != null) - check_prev = try_merge_prev () && (Left != null); - if (check_next && Right != null) - check_next = try_merge_next () && (Right != null); - if (check_prev) - { - if (Prev.try_merge_next () && check_next) - Prev.try_merge_next (); - } - else if (check_next) + if (isAnySensitive) + Stack.Clear (); + else { - Next.try_merge_prev (); + 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); + while (! head.Stack.IsEmpty && head.From > 0) + { + MInterval prev = head.Prev; + + if (prev.Stack.IsEmpty || head.Stack.Val != prev.Stack.Val) + break; + head = head.Prev; + } + while (! tail.Stack.IsEmpty && tail.To < mtext.Length) + { + MInterval next = tail.Next; + + if (next.Stack.IsEmpty || tail.Stack.Val != next.Stack.Val) + break; + tail = tail.Next; + } + Pop (head.From, tail.To); + } + + 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 (); + if (Length <= 0) + throw new Exception ("Invalid interval length"); } } @@ -1350,7 +1636,7 @@ namespace M17N.Core public void Dump (bool force) { - if (force || M17N.debug) + if (force || M17n.debug) { update_from_to (); @@ -1370,12 +1656,12 @@ namespace M17N.Core 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); @@ -1388,16 +1674,17 @@ namespace M17N.Core 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 + "`-"); - DumpOne (true, true); + Console.Write ("`-"); + DumpOne (true, true, true); if (Right != null) { if (indent_type >= 1) Right.DumpNested (indent + " ", force); - else if (indent_type == 2) + else Right.DumpNested (indent + "| ", force); } }