X-Git-Url: http://git.chise.org/gitweb/?a=blobdiff_plain;f=MText.cs;h=b28180898a25d02e4266c77f10df1f3d6c90327d;hb=3d9937566424ad30834dbf9090721ed8c95c47a5;hp=cbf5c8a0b7cd98e92bea5903a0a1f4eecd9b3808;hpb=7dc73cfdf3e4a0359fcd41b1f1ae541ac01797e4;p=m17n%2Fm17n-lib-cs.git diff --git a/MText.cs b/MText.cs index cbf5c8a..b281808 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 @@ -18,54 +19,83 @@ namespace M17N.Core } #endif - public class MTextProperty + public class MProperty { + [FlagsAttribute] + public enum Flags + { + None = 0x00, + + /// On inserting a text in between two characters, if the + /// preceding and following characters have Sticky properties of + /// the same key with same values, the inserted text inherits + /// those properties. In that case, properties of the inserted + /// text are overriden. + Sticky = 0x01, // 00000001 + + /// On inserting a text before a character, if the character has + /// FrontSticky properties, the inserted text inherits those + /// properties. + FrontSticky = 0x03, // 00000011 + + /// On inserting a text after a character, if the character has + /// RearSticky properties, the inserted text inherits those + /// properties. + RearSticky = 0x05, // 00000101 + + /// Like RearSticky, but if the inserted text inherits no + /// properties from the preceding character, it inherits + /// BothSticky properties from the following character if any. + BothSticky = 0x07, // 00000111 + + /// This property is deleted from a span of text if the span is + /// modified (i.e. one of a character is changed, a text is + /// inserted, some part is deleted). Here, "span" means a + /// sequence of characters that has this property with the same + /// value. This property is also deleted if a property of the + /// same key is added, which means that this property is not + /// stackable. In addition this property is never merged with + /// the same value of preceding or following property. At last, + /// this property can't be sticky in any way. + Sensitive = 0x10, // 00010000 + + /// Like Sensitive but also this property is deleted from a span + /// of text if a characeter just before the span is modified, + /// inserted, or deleted. + FrontSensitive = 0x30, // 00110000 + + /// Like Sensitive but also this property is deleted from a span + /// of text if a character just after the span is modified, + /// inserted, or deleted. + RearSensitive = 0x50, // 01010000 + + /// Same as (FrontSensitive | RearSensitive). + BothSensitive = 0x70, // 01110000 + }; + internal MSymbol key; internal object val; - [FlagsAttribute] - internal enum Flag : byte - { - None = 0, - FrontSticky = 1, - RearSticky = 2, - Sensitive = 4 - }; - internal Flag flags; - public MSymbol Key { get { return key; } } public object Val { get { return val; } } - public bool FrontSticky - { - get { return (flags & Flag.FrontSticky) != Flag.None; } - } - public bool RearSticky - { - get { return (flags & Flag.RearSticky) != Flag.None; } - } - public bool Sensitive - { - get { return (flags & Flag.Sensitive) != Flag.None; } - } - public MTextProperty (MSymbol key, object val) + public MProperty (MSymbol key, object val) { + if (key.flags == null) + key.flags = Flags.None; this.key = key; this.val = val; - flags |= Flag.RearSticky; } - public MTextProperty (MSymbol key, object val, - bool front_sticky, bool rear_sticky, bool sensitive) + public MProperty (string name, object val) { - this.key = key; + key = MSymbol.PropertyKey (name); this.val = val; - if (front_sticky) - flags |= Flag.FrontSticky; - if (rear_sticky) - flags |= Flag.RearSticky; - if (sensitive) - flags |= Flag.Sensitive; + } + + public static bool HasFlags (MSymbol key, Flags flags) + { + return ((key.flags & flags) == flags); } public override string ToString () @@ -94,7 +124,7 @@ namespace M17N.Core int len = str.Length, n = 0; for (int i = 0; i < len; i++, n++) - if (surrogate_high_p (str[i])) + if (Char.IsHighSurrogate (str[i])) i++; return n; } @@ -104,7 +134,7 @@ namespace M17N.Core int len = str.Length, n = 0; for (int i = 0; i < len; i++, n++) - if (surrogate_high_p (str[i])) + if (Char.IsHighSurrogate (str[i])) i++; return n; } @@ -122,6 +152,13 @@ namespace M17N.Core intervals = new MPlist (); } + public MText (byte[] str, int offset, int length) + { + sb = new StringBuilder (utf8.GetString (str, offset, length)); + nchars = count_chars (sb); + intervals = new MPlist (); + } + public MText (String str) { sb = new StringBuilder (str); @@ -136,14 +173,38 @@ namespace M17N.Core intervals = new MPlist (); } - public static MText operator+ (MText mt1, MText mt2) + public MText (int c, int len) : this () + { + while (len-- > 0) + this.Cat (c); + } + + public MText (int c) : this (c, 1) { } + + public static MText operator+ (object obj, MText mt) { - MText mt = new MText (); + if (obj is string) + { + MText mtnew = new MText ((string) obj); + return mtnew.Ins (mtnew.Length, mt); + } + throw new Exception ("Unknown object type: " + obj.GetType()); + } - mt.sb.Append (mt1.sb); - mt.sb.Append (mt2.sb); - mt.nchars = mt1.nchars + mt2.nchars; - return mt; + public static MText operator+ (MText mt, object obj) + { + if (obj is string) + return mt + new MText ((string) obj); + if (obj is int) + return mt.Dup ().Ins (mt.Length, (int) obj); + if (obj is char) + return mt.Dup ().Ins (mt.Length, (int) ((char) obj)); + throw new Exception ("Unknown object type: " + obj.GetType()); + } + + public static MText operator+ (MText mt1, MText mt2) + { + return mt1.Dup ().Ins (mt1.Length, mt2); } // Public properties @@ -164,26 +225,26 @@ 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) + public static implicit operator MText (string str) { - return (c >= 0xD800 && c < 0xDC00); + return new MText (str); } - private static bool surrogate_low_p (char c) + public static explicit operator string (MText mt) { - return (c >= 0xDC00 && c < 0xE000); + return mt.ToString (); } private static int inc_idx (StringBuilder sb, int i) { - return (i + (surrogate_high_p (sb[i]) ? 2 : 1)); + return (i + (Char.IsHighSurrogate (sb[i]) ? 2 : 1)); } private static int dec_idx (StringBuilder sb, int i) { - return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1)); + return (i - (Char.IsLowSurrogate (sb[i - 1]) ? 2 : 1)); } private static int pos_to_idx (MText mt, int pos) @@ -197,7 +258,7 @@ namespace M17N.Core if (pos < mt.cache_pos) { if (mt.cache_pos == mt.cache_idx) - return mt.cache_idx; + return pos; if (pos < mt.cache_pos - pos) { p = i = 0; @@ -251,27 +312,65 @@ 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; + private void insert (int pos, int c) + { + check_pos (pos, true); - if (p == null) - interval = new MInterval (plist.Key, to - from); - else - interval = ((MInterval) p.Val).copy (from, to); - ((MInterval) plist.Val).Insert (pos, interval); + int pos_idx = pos_to_idx (this, pos); + + if (c < 0x10000) + { + char ch = (char) c; + sb.Insert (pos_idx, ch); + } + else + { + char high = (char) (0xD800 + ((c - 0x10000) >> 10)); + char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF)); + sb.Insert (pos_idx, low); + sb.Insert (pos_idx, high); } + nchars++; + foreach (MPlist plist in intervals) + ((MInterval) plist.Val).Insert (pos, null, 0, 1); } public int this[int i] @@ -280,7 +379,7 @@ namespace M17N.Core i = pos_to_idx (this, i); if (value < 0x10000) { - if (surrogate_high_p (sb[i])) + if (Char.IsHighSurrogate (sb[i])) sb.Remove (i, 1); sb[i] = (char) value; } @@ -289,23 +388,58 @@ namespace M17N.Core char high = (char) (0xD800 + ((value - 0x10000) >> 10)); char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF)); - if (! surrogate_high_p (sb[i])) + if (! Char.IsHighSurrogate (sb[i])) sb.Insert (i, 0); sb[i] = high; sb[i + 1] = low; } + PopProp (i, i + 1); } get { i = pos_to_idx (this, i); - return (surrogate_high_p (sb[i]) + return (Char.IsHighSurrogate (sb[i]) ? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000 : sb[i]); } } + public MText this[int from, int to] + { + set { + if (from < to) + Del (from, to); + if (value != null) + Ins (from, value); + } + get { return Dup (from, to); } + } + public MText Dup () { - return (new MText (sb.ToString ())); + MText mt = new MText (sb.ToString ()); + + foreach (MPlist p in intervals) + mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, 0, Length)); + return mt; + } + + public MText Dup (int from, int to) + { + if (check_range (from, to, true)) + return new MText (); + int from_idx = pos_to_idx (this, from); + int len = pos_to_idx (this, to) - from_idx; + MText mt = new MText (sb.ToString ().Substring (from_idx, len)); + + foreach (MPlist p in intervals) + mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, from, to)); + return mt; + } + + public MText Ins (int pos, int c) + { + insert (pos, c); + return this; } public MText Ins (int pos, MText mt) @@ -320,19 +454,47 @@ namespace M17N.Core return this; } + public MText Cat (int c) + { + insert (nchars, c); + return this; + } + + public MText Cat (MText mt) + { + insert (nchars, mt, 0, mt.Length); + return this; + } + + public MText Cat (MText mt, int from, int to) + { + insert (nchars, mt, from, to); + return this; + } + + public MText Del () + { + return Del (0, Length); + } + 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); + { + 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; } @@ -340,46 +502,43 @@ namespace M17N.Core { check_pos (pos, false); - MInterval i = (MInterval) intervals.Find (key).Val; - + MInterval i = (MInterval) intervals.Get (key); if (i == null) return null; - MTextProperty prop = i.Get (pos); + MProperty prop = i.Get (pos); return (prop != null ? prop.Val : null); } - public object GetProp (int pos, MSymbol key, out MTextProperty prop) + public object GetProp (int pos, MSymbol key, out MProperty prop) { check_pos (pos, false); - MInterval i = (MInterval) intervals.Find (key).Val; - + MInterval i = (MInterval) intervals.Get (key); if (i == null) return (prop = null); prop = i.Get (pos); return (prop != null ? prop.Val : null); } - public object GetProp (int pos, MSymbol key, out MTextProperty[] array) + public object GetProp (int pos, MSymbol key, out MProperty[] array) { check_pos (pos, false); - MInterval i = (MInterval) intervals.Find (key).Val; - + MInterval i = (MInterval) intervals.Get (key); if (i == null) return (array = null); - MTextProperty prop = i.Get (pos, out array); + MProperty prop = i.Get (pos, out array); return (prop != null ? prop.Val : null); } public void PushProp (int from, int to, MSymbol key, object val) { 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) { @@ -401,9 +560,43 @@ namespace M17N.Core intervals.Push (prop.key, root); } else - root = (MInterval) p.Val; - + { + root = (MInterval) p.Val; + if (root.isSensitive) + { + root.PopSensitive (from, to); + root.MergeAfterChange (from, to); + root = (MInterval) p.Val; + if (M17n.debug) + DumpPropNested (); + } + } root.Push (from, to, prop); + root.MergeAfterChange (from, to); + root.Balance (); + } + } + + public void PopProp (int from, int to) + { + if (from < 0) + { + default_property = null; + } + else + { + if (check_range (from, to, true)) + return; + for (MPlist p = intervals; ! p.IsEmpty; p = p.next) + { + MInterval root = (MInterval) p.Val; + root.PopAll (from, to); + root = (MInterval) p.Val; + if (M17n.debug) + DumpPropNested (); + root.MergeAfterChange (from, to); + root.Balance (); + } } } @@ -426,18 +619,49 @@ 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 (); + } } } + public object FindProp (MSymbol key, int pos, out int from, out int to) + { + from = 0; + to = Length; + check_pos (pos, false); + + MInterval i = (MInterval) intervals.Get (key); + if (i != null + && (i = i.Find (pos, out from, out to)) != null) + return GetProp (from, key); + return null; + } + public void DumpProp () { Console.Write ("("); foreach (MPlist p in intervals) - ((MInterval) p.Val).Dump (); + ((MInterval) p.Val).Dump (true); Console.WriteLine (")"); } + public void DumpPropNested () + { + Console.WriteLine ("total length = {0}", Length); + foreach (MPlist p in intervals) + ((MInterval) p.Val).DumpNested (true); + } + private class MInterval { // position: 0 1 2 3 4 5 6 7 @@ -451,173 +675,259 @@ namespace M17N.Core // [1 (0 1)] [2 (2 3)] [1 (6 7)] // private static int count = 0; - private int id; - private int total_length; - private int from, to; - private MSymbol key; - private MPlist stack; - private MInterval left, right, parent; + private int ID; + private int Length; + private int From, To; + private MSymbol Key; + private MPlist Stack; + private MInterval Left, Right, Parent; private MText mtext; - public MInterval (MSymbol key, int length) + public MInterval (MSymbol key, MText mt, int length) { if (length <= 0) throw new Exception ("Invalid interval length"); - this.key = key; - total_length = length; - stack = new MPlist (); - id = count++; + Key = key; + mtext = mt; + Length = length; + Stack = new MPlist (); + ID = count++; } public MInterval (MSymbol key, MText mt) { - this.key = key; + Key = key; mtext = mt; - total_length = mt.sb.Length; - from = 0; - to = total_length; - stack = new MPlist (); - id = count++; + Length = mt.sb.Length; + From = 0; + To = Length; + Stack = new MPlist (); + ID = count++; } - public MTextProperty Get (int pos) + /// POS must be smaller than Length; + public MProperty Get (int pos) { - MInterval i = find (pos); + MInterval i = find_head (pos); - return (i.stack.IsEmpty ? null : (MTextProperty) i.stack.Val); + return (i.Stack.IsEmpty ? null : (MProperty) i.Stack.Val); } - public MTextProperty Get (int pos, out MTextProperty[] array) + /// POS must be smaller than Length; + public MProperty Get (int pos, out MProperty[] array) { - MInterval i = find (pos); + MInterval i = find_head (pos); - if (i.stack.IsEmpty) + if (i.To == pos) + i = i.Next; + if (i.Stack.IsEmpty) { array = null; return null; } - array = new MTextProperty[i.stack.Count]; + array = new MProperty[i.Stack.Count]; int idx; MPlist p; - for (idx = 0, p = i.stack; ! p.IsEmpty; idx++, p = p.Next) - array[idx] = (MTextProperty) p.Val; - return array[idx - 1]; + for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next) + array[idx] = (MProperty) p.Val; + return array[0]; + } + + private MInterval (MSymbol key, MText mt, int length, MPlist stack) + { + Key = key; + mtext = mt; + Length = length; + From = 0; + To = Length; + 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) ; } } - private MInterval (MSymbol key, int length, MPlist stack) + public bool isFrontSensitive { - this.key = key; - total_length = length; - from = 0; - to = total_length; - this.stack = stack.Clone (); - id = count++; + get { return MProperty.HasFlags (Key, + MProperty.Flags.FrontSensitive) ; } + } + + public bool isRearSensitive + { + get { return MProperty.HasFlags (Key, + MProperty.Flags.RearSensitive) ; } } private void update_from_to () { - if (parent == null) + if (Parent == null) { - from = LeftLength; - to = total_length - RightLength; + From = LeftLength; + To = Length - RightLength; } - else if (parent.left == this) + else if (Parent.Left == this) { - from = parent.from - total_length + LeftLength; - to = parent.from - RightLength; + From = Parent.From - Length + LeftLength; + To = Parent.From - RightLength; } else { - from = parent.to + LeftLength; - to = parent.to + total_length - RightLength; + From = Parent.To + LeftLength; + To = Parent.To + Length - RightLength; } } private int LeftLength { - get { return (left == null ? 0 : left.total_length); } + get { return (Left == null ? 0 : Left.Length); } } private int RightLength { - get { return (right == null ? 0 : right.total_length); } + get { return (Right == null ? 0 : Right.Length); } } - private MInterval left_most_node + private MInterval LeftMost { - get { return (left == null ? this : left.left_most_node); } + get { + update_from_to (); + if (Left == null) + return this; + return Left.LeftMost; + } } - private MInterval right_most_node + private MInterval RightMost { - get { return (right == null ? this : right.right_most_node); } + get { + update_from_to (); + if (Right == null) + return this; + return Right.RightMost; + } } - private MInterval prev { + private MInterval Prev { get { MInterval i; - if (left != null) - for (i = left; i.right != null; i = i.right); + if (Left != null) + { + for (i = Left; i.Right != null; i = i.Right) + i.update_from_to (); + i.update_from_to (); + } else - for (i = parent; i != null && i.left == null; i = i.parent); + { + MInterval child = this; + for (i = Parent; i != null && i.Left == child; + child = i, i = i.Parent); + } return i; } } - private MInterval next { + private MInterval Next { get { MInterval i; - if (right != null) - for (i = right; i.left != null; i = i.left); + if (Right != null) + { + for (i = Right; i.Left != null; i = i.Left) + i.update_from_to (); + i.update_from_to (); + } else - for (i = parent; i != null && i.right == null; i = i.parent); + { + MInterval child = this; + for (i = Parent; i != null && i.Right == child; + child = i, i = i.Parent); + } return i; } } - private MInterval find (int pos) + private MInterval find_head (int pos) + { + update_from_to (); + if (pos < From) + return Left.find_head (pos); + if (pos >= To) + return Right.find_head (pos); + return this; + } + + private MInterval find_tail (int pos) { update_from_to (); - if (pos < from) - return left.find (pos); - if (pos >= to) - return right.find (pos); + if (pos <= From) + return Left.find_tail (pos); + if (pos > To) + return Right.find_tail (pos); return this; } + private bool mergeable (MInterval i) + { + MPlist p1, p2; + + if (Stack.IsEmpty && i.Stack.IsEmpty) + return true; + if (isSensitive) + return false; + for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty; + p1 = p1.Next, p2 = p2.Next) + if (p1.Val != p2.Val) + return false; + return (p1.IsEmpty && p2.IsEmpty); + } + // p-. or .-p p-. or .-p // .-this-. .-right-. // left .-right-. -> .-this-. c2 // c1 c2 left c1 private MInterval promote_right () { - int right_length = right.total_length; - MInterval c1; + MInterval c1 = Right.Left; - if (parent == null) - mtext.intervals.Put (key, right); - else if (parent.left == this) - parent.left = right; + // Update Parent. + if (Parent == null) + mtext.intervals.Put (Key, Right); + else if (Parent.Left == this) + Parent.Left = Right; else - parent.right = right; - right.parent = parent; - c1 = right.left; - right.left = this; - - parent = right; - right = c1; - parent.total_length += total_length; - total_length -= right_length; + Parent.Right = Right; + + // Update Right. + Right.Parent = Parent; + Right.Left = this; + Right.Length += LeftLength + (To - From); + + // Update this. + Parent = Right; + Right = c1; + Length = LeftLength + (To - From) + RightLength; + + // Update C1 if necessary. if (c1 != null) - { - c1.parent = this; - parent.total_length -= c1.total_length; - total_length += c1.total_length; - } - return parent; + c1.Parent = this; + + Parent.update_from_to (); + return Parent; } // p-. or .-p p-. or .-p @@ -626,36 +936,54 @@ namespace M17N.Core // c1 c2 c2 right private MInterval promote_left () { - int left_length = left.total_length; - MInterval c1; + MInterval c2 = Left.Right; - if (parent == null) - mtext.intervals.Put (key, left); - else if (parent.left == this) - parent.left = left; + // Update Parent. + if (Parent == null) + mtext.intervals.Put (Key, Left); + else if (Parent.Left == this) + Parent.Left = Left; else - parent.right = left; - left.parent = parent; - c1 = left.left; - left.right = this; - - parent = left; - left = c1; - parent.total_length += total_length; - total_length -= left_length; - if (c1 != null) + Parent.Right = Left; + + // Update Left. + Left.Parent = Parent; + Left.Right = this; + Left.Length += (To - From) + RightLength; + + // Update this. + Parent = Left; + Left = c2; + Length = LeftLength + (To - From) + RightLength; + + // Update C2 if necessary. + if (c2 != null) + c2.Parent = this; + + Parent.update_from_to (); + return Parent; + } + + public MInterval Find (int pos, out int from, out int to) + { + MInterval i = find_head (pos); + + from = to = pos; + if (i.Stack.IsEmpty) + i = i.Next; + if (i != null) { - c1.parent = this; - parent.total_length -= c1.total_length; - total_length += c1.total_length; + from = i.From; + to = i.To; } - return parent; + return i; } - private MInterval balance () + public MInterval Balance () { MInterval i = this; + update_from_to (); while (true) { // .-this-. @@ -666,48 +994,94 @@ namespace M17N.Core if (diff > 0) { - new_diff = (i.total_length - i.LeftLength - + i.left.RightLength - i.left.LeftLength); + new_diff = (i.Length - i.LeftLength + + i.Left.RightLength - i.Left.LeftLength); if (Math.Abs (new_diff) >= diff) break; + M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID); i = i.promote_left (); - i.right.balance (); + M17n.DebugPrint ("done\n"); + i.Right.Balance (); } else if (diff < 0) { - new_diff = (i.total_length - i.RightLength - + i.right.LeftLength - i.right.RightLength); + new_diff = (i.Length - i.RightLength + + i.Right.LeftLength - i.Right.RightLength); if (Math.Abs (new_diff) >= diff) break; + M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID); i = i.promote_right (); - i.left.balance (); + i.Left.Balance (); } + else + break; } return i; } - public MInterval copy (int start, int end) + public MInterval Copy (MText mt, int start, int end) { - MInterval this_copy, left_copy = null, right_copy = null; + MInterval copy, left_copy = null, right_copy = null; update_from_to (); - if (start < from) + + if (start < From) { - if (end <= from) - return left.copy (start, end); - left_copy = left.copy (start, from); + if (end <= From) + return Left.Copy (mt, start, end); + left_copy = Left.Copy (mt, start, From); } - else if (end > to) + if (end > To) { - if (start >= to) - return right.copy (start, end); - right_copy = right.copy (to, end); + if (start >= To) + return Right.Copy (mt, start, end); + right_copy = Right.Copy (mt, To, end); } - this_copy = new MInterval (key, end - start, stack); - this_copy.left = left_copy; - this_copy.right = right_copy; - return this_copy; + copy = new MInterval (Key, null, end - start, Stack); + copy.mtext = mt; + if (isSensitive && (From < start || end < To)) + copy.Stack.Clear (); + if (left_copy != null) + { + copy.Left = left_copy; + left_copy.Parent = copy; + } + if (right_copy != null) + { + copy.Right = right_copy; + right_copy.Parent = copy; + } + return copy; + } + + public MInterval Copy (MText mt, int start, int end, + bool first, bool last) + { + MInterval copy = Copy (mt, start, end); + MInterval head = find_head (start); + MInterval tail = find_tail (end); + + M17n.DebugPrint ("Copying: {0}", copy); + + if (! head.Stack.IsEmpty + && (isSensitive && head.From < start + || (isFrontSensitive && ! first))) + { + M17n.DebugPrint (" clear head"); + head = copy.find_head (0); + head.Stack.Clear (); + } + if (! tail.Stack.IsEmpty + && (isSensitive && end < tail.To + || (isRearSensitive && ! last))) + { + M17n.DebugPrint (" clear tail"); + tail = copy.find_tail (copy.Length); + tail.Stack.Clear (); + } + M17n.DebugPrint ("\n"); + return copy; } // this-. ==> this-. @@ -715,18 +1089,18 @@ namespace M17N.Core // right private MInterval divide_right (int pos) { - MInterval interval = new MInterval (key, to - pos, stack); + MInterval interval = new MInterval (Key, mtext, To - pos, Stack); - Console.Write ("divide-right({0}) at ", pos); DumpOne (false, true); - to = pos; - if (right != null) + M17n.DebugPrint ("divide-right({0}) at {1}\n", pos, this); + To = pos; + if (Right != null) { - interval.right = right; - right.parent = interval; - interval.total_length += right.total_length; + interval.Right = Right; + Right.Parent = interval; + interval.Length += Right.Length; } - interval.parent = this; - right = interval; + interval.Parent = this; + Right = interval; return interval; } @@ -735,333 +1109,759 @@ namespace M17N.Core // left private MInterval divide_left (int pos) { - MInterval interval = new MInterval (key, pos - from, stack); + MInterval interval = new MInterval (Key, mtext, pos - From, Stack); - Console.Write ("divide-reft({0}) at ", pos); DumpOne (false, true); - from = pos; - if (left != null) + M17n.DebugPrint ("divide-left({0}) at {1}\n", pos, this); + From = pos; + if (Left != null) { - interval.left = left; - left.parent = interval; - interval.total_length += left.total_length; + interval.Left = Left; + Left.Parent = interval; + interval.Length += Left.Length; } - interval.parent = this; - left = interval; + interval.Parent = this; + Left = interval; return interval; } - private void remove_properties (MTextProperty.Flag flags) + private void set_mtext (MText mt) { - for (MPlist p = stack; ! p.IsEmpty;) - { - MTextProperty prop = (MTextProperty) p.Val; + mtext = mt; + if (Left != null) + Left.set_mtext (mt); + if (Right != null) + Right.set_mtext (mt); + } - if ((prop.flags & flags) == flags) - p.Pop (); - else - p = p.Next; + private void enlarge (int len) + { + Length += len; + To += len; + for (MInterval prev = this, i = this.Parent; i != null; + prev = i, i = i.Parent) + { + i.Length += len; + if (prev == i.Left) + { + i.From += len; + i.To += len;; + } } } - private void merge_front_properties (MPlist plist) + private int graft_forward (MInterval interval, int start, int end) { - for (MInterval i = left_most_node; i != null; i = i.next) + int len; + + if (! Stack.IsEmpty && isRearSticky) + len = end - start; + else if (interval == null) + len = Stack.IsEmpty ? end - start : 0; + else { - if (! stack.IsEmpty) - break; - for (MPlist p = plist; ! p.IsEmpty; p = p.Next) - { - MTextProperty prop = (MTextProperty) p.Val; + MInterval i = interval.find_head (start); - if ((prop.flags & MTextProperty.Flag.RearSticky) - == MTextProperty.Flag.RearSticky) - i.stack.Add (prop.key, prop); + len = 0; + if (Stack.IsEmpty + && (isFrontSensitive || (isSensitive && i.From < start))) + { + M17n.DebugPrint (" forward grafting {0}", i); + if (i.To < end) + len = i.To - start; + else + len = end - start; + i = i.Next; + } + while (i != null && i.From < end && mergeable (i)) + { + M17n.DebugPrint (" forward grafting {0}", i); + len += i.To - i.From; + if (i.From < start) + len -= start - i.From; + if (i.To >= end) + { + len -= i.To - end; + break; + } + i = i.Next; } } + + M17n.DebugPrint (" grafted {0} in {1}\n", len, this); + if (len > 0) + enlarge (len); + return len; } - private void merge_rear_properties (MPlist plist) + private int graft_backward (MInterval interval, int start, int end) { - for (MInterval i = right_most_node; i != null; i = i.prev) + int len; + + if (! Stack.IsEmpty && isFrontSticky) + len = end - start; + else if (interval == null) + len = Stack.IsEmpty ? end - start : 0; + else { - if (! stack.IsEmpty) - break; - for (MPlist p = plist; ! p.IsEmpty; p = p.Next) - { - MTextProperty prop = (MTextProperty) p.Val; + MInterval i = interval.find_tail (end); - if ((prop.flags & MTextProperty.Flag.FrontSticky) - == MTextProperty.Flag.FrontSticky) - i.stack.Add (prop.key, prop); + len = 0; + if (Stack.IsEmpty + && (isRearSensitive || (isSensitive && end < i.To))) + { + M17n.DebugPrint (" backward grafting {0}", i); + if (i.From <= start) + len = end - start; + else + len = end - i.From; + i = i.Prev; + } + while (i != null && i.To <= start && mergeable (i)) + { + M17n.DebugPrint (" backward grafting {0}", i); + len += i.To - i.From; + if (end < i.To) + len -= i.To - end; + if (i.From <= start) + { + len -= start - i.From; + break; + } + i = i.Prev; } } + + 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 (); - Console.Write ("insert({0}) at ", pos); DumpOne (false, true); - if (pos < from || (pos == from && left == null && pos > 0)) - { - prev.Insert (pos, interval); - return; - } - if (pos > to || (pos == to && right == null && next != null)) - { - next.Insert (pos, interval); - return; - } - if (pos > from && pos < to) - { - remove_properties (MTextProperty.Flag.Sensitive); - divide_right (pos).Insert (pos, interval); - return; - } - if (pos == from) + + M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}", + start, end, pos, this); + + if (pos < From) + Left.Insert (pos, interval, start, end); + else if (pos == From) { - if (pos > 0) + MInterval prev = Left != null ? Prev : null; + + if (isFrontSensitive) + Stack.Clear (); + if (prev != null && isRearSensitive) + prev.Stack.Clear (); + if (prev != null && isRearSticky && ! prev.Stack.IsEmpty) + { + prev.enlarge (end - start); + M17n.DebugPrint (" done\n"); + return; + } + if (isFrontSticky && ! Stack.IsEmpty) { - prev.remove_properties - (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky); - interval.merge_front_properties (prev.stack); + enlarge (end - start); + M17n.DebugPrint (" done\n"); + return; } - 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) + bool front_grafted = false, rear_grafted = false; + int grafted; + if (prev != null + && (grafted = prev.graft_forward (interval, start, end)) > 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; + start += grafted; + if (start == end) + { + M17n.DebugPrint (" done\n"); + return; + } + front_grafted = true; } - else + if ((grafted = graft_backward (interval, start, end)) > 0) { - left = interval; + end -= grafted; + if (start == end) + { + M17n.DebugPrint (" done\n"); + return; + } + rear_grafted = true; + } + + if (interval != null) + interval = interval.Copy (mtext, start, end, + (front_grafted + || (prev == null && start == 0)), + rear_grafted); + else + interval = new MInterval (Key, mtext, end - start, null); - for (MInterval i = this; i != null; i = i.parent) - i.total_length += interval.total_length; + MInterval i; + if (Left != null) + { + // .-this-. ==> .-this-. + // left-. .-left-. + // child child-. + // interval + i = Left.RightMost; + i.Right = interval; + } + else + { + Left = interval; + i = this; } + interval.Parent = i; + for (; i != null; i = i.Parent) + i.Length += interval.Length; } - else // pos == to + else if (pos < To) { - if (right != null) + if (! Stack.IsEmpty) + { + if (isSensitive) + Stack.Clear (); + else if (isFrontSticky || isRearSticky) + { + enlarge (end - start); + return; + } + } + bool front_grafted = false, rear_grafted = false; + int grafted; + if ((grafted = graft_forward (interval, start, end)) > 0) + { + start += grafted; + if (start == end) + { + M17n.DebugPrint (" done\n"); + return; + } + front_grafted = true; + pos += grafted; + } + if ((grafted = graft_backward (interval, start, end)) > 0) { - MInterval left_most = right.left_most_node; + end -= grafted; + if (start == end) + { + M17n.DebugPrint (" done\n"); + return; + } + rear_grafted = true; + } + if (interval != null) + interval = interval.Copy (mtext, start, end, + front_grafted, rear_grafted); + else + interval = new MInterval (Key, mtext, end - start, null); + + divide_right (pos); + Right.Left = interval; + interval.Parent = Right; + for (MInterval i = Right; i != null; i = i.Parent) + i.Length += interval.Length; + } + else if (pos == To) + { + MInterval next = Right != null ? Next : null; - left_most.remove_properties - (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky); - interval.merge_rear_properties (left_most.stack); + if (isRearSensitive) + Stack.Clear (); + if (next != null && isFrontSensitive) + next.Stack.Clear (); + if (isRearSticky && ! Stack.IsEmpty) + { + enlarge (end - start); + M17n.DebugPrint (" done by enlarging this\n"); + return; } - 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) + if (next != null && isFrontSticky && ! next.Stack.IsEmpty) { - MInterval i = right.left_most_node; - - i.left = interval; - interval.parent = i; - for (; i != null; i = i.parent) - i.total_length += interval.total_length; + M17n.DebugPrint (" next is {0}\n", next); + next.enlarge (end - start); + M17n.DebugPrint (" done by enlarging next\n"); + return; } + bool front_grafted = false, rear_grafted = false; + int grafted; + if (next != null + && (grafted = next.graft_backward (interval, start, end)) > 0) + { + end -= grafted; + if (start == end) + { + M17n.DebugPrint (" done\n"); + return; + } + rear_grafted = true; + } + if ((grafted = graft_forward (interval, start, end)) > 0) + { + start += grafted; + if (start == end) + { + M17n.DebugPrint (" done\n"); + return; + } + front_grafted = true; + } + if (interval != null) + interval = interval.Copy (mtext, start, end, + front_grafted, + (rear_grafted + || (next == null && end == interval.mtext.Length))); else + interval = new MInterval (Key, mtext, end - start, null); + + MInterval i; + if (Right != null) { - right = interval; + // .-this-. ==> .-this-. + // .-right .-right + // child .-child + // interval - for (MInterval i = this; i != null; i = i.parent) - i.total_length += interval.total_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) + Right.Insert (pos, interval, start, end); + M17n.DebugPrint (" done\n"); } private void vacate_node (MInterval interval) { - Console.WriteLine ("vacate #{0} to #{1}", id, interval.id); + vacate_node (interval, null); + } + + private void vacate_node (MInterval interval, MInterval stop) + { if (interval != null) - interval.parent = parent; - if (parent == null) + M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID); + else + M17n.DebugPrint ("vacate #{0} to null\n", ID); + if (interval != null) + interval.Parent = Parent; + if (Parent == null) { - mtext.intervals.Put (key, interval); + if (mtext != null) + mtext.intervals.Put (Key, interval); } else { - if (this == parent.right) - parent.right = interval; + if (this == Parent.Right) + Parent.Right = interval; else - parent.left = interval; + Parent.Left = interval; - int diff = total_length; + int diff = Length; if (interval != null) - diff -= interval.total_length; - for (MInterval i = parent; i != null; i = i.parent) - i.total_length -= diff; + diff -= interval.Length; + for (MInterval i = Parent; i != stop; i = i.Parent) + i.Length -= diff; } } public void Delete (int start, int end) { update_from_to (); - Console.Write ("delete({0} {1}) at ", start, end); DumpOne (false, true); - if (start < from) + M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this); + + bool front_checked = false; + bool rear_checked = false; + + if (start < From) { - if (end <= from) + if (end <= From) { - left.Delete (start, end); + if (end == From && isFrontSensitive) + Stack.Clear (); + Left.Delete (start, end); return; } - left.Delete (start, from); - to -= from - start; - end -= from - start; - from = start; + if (isSensitive) + Stack.Clear (); + Left.Delete (start, From); + To -= From - start; + end -= From - start; + From = start; + front_checked = true; } - if (end > to) + if (end > To) { - if (start >= to) + if (start >= To) { - right.Delete (start, end); + if (start == To && isRearSensitive) + Stack.Clear (); + Right.Delete (start, end); return; } - right.Delete (to, end); - end = to; + if (isSensitive) + Stack.Clear (); + Right.Delete (To, end); + end = To; + rear_checked = true; } - if (start == from && end == to) + if (start == From + && ! front_checked + && start > 0 + && isRearSensitive) + Prev.Stack.Clear (); + if (end == To + && ! rear_checked + && Next != null + && isFrontSensitive) + Next.Stack.Clear (); + if (start == From && end == To) { - if (right == null) + if (Right == null) { - vacate_node (left); + vacate_node (Left); } else { - if (left != null) + if (Left != null) { MInterval i; - for (i = right; i.left != null; i = i.left) - i.total_length += left.total_length; - i.total_length += left.total_length; - i.left = left; - left.parent = i; + for (i = Right; i.Left != null; i = i.Left) + i.Length += Left.Length; + i.Length += Left.Length; + i.Left = Left; + Left.Parent = i; } - vacate_node (right); + vacate_node (Right); } } else { int len = end - start; - for (MInterval i = this; i != null; i = i.parent) - i.total_length -= len; + if (isSensitive) + Stack.Clear (); + for (MInterval i = this; i != null; i = i.Parent) + i.Length -= len; } } - public void Push (int start, int end, MTextProperty prop) + public void Push (int start, int end, MProperty prop) { update_from_to (); - Console.Write ("push({0} {1}) at ", start, end); DumpOne (false, true); - if (start < from) + M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this); + if (start < From) { - if (end <= from) + if (end <= From) { - left.Push (start, end, prop); + Left.Push (start, end, prop); return; } - left.Push (start, from, prop); - start = from; + Left.Push (start, From, prop); + start = From; } - if (end > to) + if (end > To) { - if (start >= to) + if (start >= To) { - right.Push (start, end, prop); + Right.Push (start, end, prop); return; } - right.Push (to, end, prop); - end = to; + Right.Push (To, end, prop); + end = To; } - if (start > from) + if (! Stack.IsEmpty && isSensitive) + Stack.Clear (); + if (start > From) divide_left (start); - if (end < to) + if (end < To) divide_right (end); - stack.Push (prop.key, prop); + Stack.Push (prop.key, prop); + } + + /// Combine intervals between HEAD and TAIL (both inclusive) to + /// the common parent of HEAD and TAIL. Callers should assure + /// that the intervals are mergeable in advance. + private static void combine (MInterval head, MInterval tail) + { + M17n.DebugPrint ("combining {0} through {1}", head, tail); + + head.update_from_to (); + tail.update_from_to (); + int from = head.From; + int to = tail.To; + + // The nearest common parent of HEAD and TAIL. + MInterval root; + for (root = head; root.To + root.RightLength < to; + root = root.Parent); + + M17n.DebugPrint (" with common root {0}\n", root); + + if (from < root.From) + { + MInterval prev = root.Prev; + + while (true) + { + 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 (); + } + if (root.To < to) + { + 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 (); + } + } + + public void MergeAfterChange (int start, int end) + { + update_from_to (); + + MInterval head = find_head (start), i = head; + MInterval tail = start < end ? find_tail (end) : head; + + if (tail.To < Length) + tail = tail.Next; + + if (start == head.From && start > 0) + { + MInterval prev = head.Prev; + if (head.mergeable (prev)) + head = prev; + } + M17n.DebugPrint ("merge between {0} and {1}\n", head, tail); + while (i != tail) + { + MInterval next = i.Next; + + if (! i.mergeable (next)) + { + if (head != i) + combine (head, i); + head = next; + } + i = next; + } + if (head != i) + combine (head, i); } public void Pop (int start, int end) { update_from_to (); - Console.Write ("pop({0} {1}) at ", start, end); DumpOne (false, true); - if (start < from) + M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this); + if (start < From) { - if (end <= from) + if (end <= From) { - left.Pop (start, end); + Left.Pop (start, end); return; } - left.Pop (start, from); - start = from; + Left.Pop (start, From); + start = From; } - if (end > to) + if (end > To) { - if (start >= to) + if (start >= To) { - right.Pop (start, end); + Right.Pop (start, end); return; } - right.Pop (to, end); - end = to; + Right.Pop (To, end); + end = To; } - if (! stack.IsEmpty) + if (! Stack.IsEmpty) { - if (start > from) - divide_left (start); - if (end < to) - divide_right (end); - stack.Pop (); + if (isSensitive) + Stack.Clear (); + else + { + if (start > From) + divide_left (start); + if (end < To) + divide_right (end); + Stack.Pop (); + } } } - private void DumpOne (bool with_prop, bool newline) + public void PopSensitive (int start, int end) { - Console.Write ("#{0}({1} {2} {3}", id, total_length, from, to); - if (with_prop) - foreach (MPlist p in stack) - Console.Write (" " + p.Val); - Console.Write (")"); - if (newline) - Console.WriteLine (); + update_from_to (); + MInterval head = find_head (start); + MInterval tail = find_tail (end); + Pop (head.From, tail.To); } - public void Dump () + public void PopAll (int start, int end) { update_from_to (); + M17n.DebugPrint ("popall({0} {1}) at {2}\n", start, end, this); + if (start < From) + { + if (end <= From) + { + Left.PopAll (start, end); + return; + } + Left.PopAll (start, From); + start = From; + } + if (end > To) + { + if (start >= To) + { + Right.PopAll (start, end); + return; + } + Right.PopAll (To, end); + end = To; + } + + if (! Stack.IsEmpty) + { + if (isSensitive) + Stack.Clear (); + else + { + if (start > From) + divide_left (start); + if (end < To) + divide_right (end); + Stack.Clear (); + } + } + } - if (left != null) - left.Dump (); - if (from > 0) - Console.Write (" "); - DumpOne (true, false); - if (right != null) - right.Dump (); + 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) + { + Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To); + 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"); + } + } + + public void Dump () { Dump (false); } + + public void Dump (bool force) + { + if (force || M17n.debug) + { + update_from_to (); + + if (Left != null) + Left.Dump (force); + if (From > 0) + Console.Write (" "); + DumpOne (true, false, force); + if (Right != null) + Right.Dump (force); + } + } + + private int Depth { + get { return (Parent == null ? 0 : Parent.Depth + 1); } + } + + public void DumpNested (bool force) + { + DumpNested (" " + Key.ToString () + ":", force); + } + + public void DumpNested (string indent, bool force) + { + if (force || M17n.debug) + { + int indent_type = (Parent == null ? 1 + : Parent.Left == this ? 0 : 2); + + update_from_to (); + if (Left != null) + { + if (indent_type <= 1) + Left.DumpNested (indent + " ", force); + else + Left.DumpNested (indent + "| ", force); + } + Console.Write (indent); + if (indent_type == 0) + Console.Write (".-"); + else if (indent_type == 2) + Console.Write ("`-"); + DumpOne (true, true, true); + if (Right != null) + { + if (indent_type >= 1) + Right.DumpNested (indent + " ", force); + else + Right.DumpNested (indent + "| ", force); + } + } } }