X-Git-Url: http://git.chise.org/gitweb/?a=blobdiff_plain;f=MText.cs;h=b28180898a25d02e4266c77f10df1f3d6c90327d;hb=18f80341e7c3f27769e588819b0ba1673ba4864e;hp=f8d7379428f9df8ff1d15ab2f6e22264d96b5468;hpb=30ca419599b1981f2babfab221d095a38fe77304;p=m17n%2Fm17n-lib-cs.git diff --git a/MText.cs b/MText.cs index f8d7379..b281808 100644 --- a/MText.cs +++ b/MText.cs @@ -25,28 +25,52 @@ namespace M17N.Core 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, + + /// 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. 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, + /// 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 text just before the span is modified, + /// of text if a characeter just before the span is modified, /// inserted, or deleted. - FrontSensitive = 0x0C, + FrontSensitive = 0x30, // 00110000 + /// 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 = 0x14 + /// 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; @@ -100,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; } @@ -110,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; } @@ -128,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); @@ -142,6 +173,14 @@ namespace M17N.Core intervals = new MPlist (); } + 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) { if (obj is string) @@ -186,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) @@ -219,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; @@ -340,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; } @@ -349,20 +388,32 @@ 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 () { MText mt = new MText (sb.ToString ()); @@ -409,14 +460,29 @@ namespace M17N.Core 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) { @@ -494,16 +560,46 @@ namespace M17N.Core intervals.Push (prop.key, root); } else - root = (MInterval) p.Val; - - if (root.isSensitive) - root.PopSensitive (from, to); + { + 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 (); + } + } + } + public void PopProp (int from, int to, MSymbol key) { if (from < 0) @@ -538,6 +634,19 @@ namespace M17N.Core } } + 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 ("("); @@ -776,6 +885,10 @@ namespace M17N.Core { 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) @@ -851,6 +964,21 @@ namespace M17N.Core 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) + { + from = i.From; + to = i.To; + } + return i; + } + public MInterval Balance () { MInterval i = this; @@ -927,6 +1055,35 @@ 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); + + M17n.DebugPrint ("Copying: {0}", copy); + + if (! head.Stack.IsEmpty + && (isSensitive && head.From < start + || (isFrontSensitive && ! first))) + { + M17n.DebugPrint (" clear head"); + head = copy.find_head (0); + head.Stack.Clear (); + } + if (! tail.Stack.IsEmpty + && (isSensitive && end < tail.To + || (isRearSensitive && ! last))) + { + M17n.DebugPrint (" clear tail"); + tail = copy.find_tail (copy.Length); + tail.Stack.Clear (); + } + M17n.DebugPrint ("\n"); + return copy; + } + // this-. ==> this-. // right newright-. // right @@ -934,7 +1091,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) { @@ -954,7 +1111,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) { @@ -1005,9 +1162,19 @@ namespace M17N.Core MInterval i = interval.find_head (start); len = 0; - while (i != null && mergeable (i)) + if (Stack.IsEmpty + && (isFrontSensitive || (isSensitive && i.From < start))) { - M17n.DebugPrint (" grafting "); i.DumpOne (false, false); + 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; @@ -1020,7 +1187,7 @@ namespace M17N.Core } } - M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true); + M17n.DebugPrint (" grafted {0} in {1}\n", len, this); if (len > 0) enlarge (len); return len; @@ -1039,9 +1206,19 @@ namespace M17N.Core MInterval i = interval.find_tail (end); len = 0; - while (i != null && mergeable (i)) + 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 (" grafting "); i.DumpOne (false, false); + M17n.DebugPrint (" backward grafting {0}", i); len += i.To - i.From; if (end < i.To) len -= i.To - end; @@ -1054,7 +1231,7 @@ namespace M17N.Core } } - M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true); + M17n.DebugPrint (" grafted {0} in {1}\n", len, this); if (len > 0) enlarge (len); return len; @@ -1064,8 +1241,8 @@ namespace M17N.Core { update_from_to (); - M17n.DebugPrint ("insert({0} to {1}) at {2} in ", start, end, pos); - DumpOne (false, false); + M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}", + start, end, pos, this); if (pos < From) Left.Insert (pos, interval, start, end); @@ -1080,24 +1257,44 @@ namespace M17N.Core if (prev != null && isRearSticky && ! prev.Stack.IsEmpty) { prev.enlarge (end - start); + M17n.DebugPrint (" done\n"); return; } if (isFrontSticky && ! Stack.IsEmpty) { enlarge (end - start); + M17n.DebugPrint (" done\n"); return; } - if (prev != null) + 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) + { + M17n.DebugPrint (" done\n"); + return; + } + front_grafted = true; + } + if ((grafted = graft_backward (interval, start, end)) > 0) { - start += prev.graft_forward (interval, start, end); + end -= grafted; if (start == end) - return; + { + M17n.DebugPrint (" done\n"); + return; + } + rear_grafted = true; } - if ((end -= graft_backward (interval, start, end)) == start) - return; if (interval != null) - interval = interval.Copy (mtext, start, end); + interval = interval.Copy (mtext, start, end, + (front_grafted + || (prev == null && start == 0)), + rear_grafted); else interval = new MInterval (Key, mtext, end - start, null); @@ -1122,22 +1319,42 @@ namespace M17N.Core } else if (pos < To) { - if (isSensitive) - Stack.Clear (); - else if (! Stack.IsEmpty && (isFrontSticky || isRearSticky)) + if (! Stack.IsEmpty) { - enlarge (end - start); - return; + 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) + { + end -= grafted; + if (start == end) + { + M17n.DebugPrint (" done\n"); + return; + } + rear_grafted = true; } - int len = graft_forward (interval, start, end); - start += len; - if (start == end) - return; - if ((end -= graft_backward (interval, start, end)) == start) - return; - pos += len; if (interval != null) - interval = interval.Copy (mtext, start, end); + interval = interval.Copy (mtext, start, end, + front_grafted, rear_grafted); else interval = new MInterval (Key, mtext, end - start, null); @@ -1158,25 +1375,44 @@ namespace M17N.Core if (isRearSticky && ! Stack.IsEmpty) { enlarge (end - start); + M17n.DebugPrint (" done by enlarging this\n"); + return; + } + if (next != null && isFrontSticky && ! next.Stack.IsEmpty) + { + M17n.DebugPrint (" next is {0}\n", next); + next.enlarge (end - start); + M17n.DebugPrint (" done by enlarging next\n"); return; } - if (next != null) + bool front_grafted = false, rear_grafted = false; + int grafted; + if (next != null + && (grafted = next.graft_backward (interval, start, end)) > 0) { - if (isFrontSticky && ! next.Stack.IsEmpty) + end -= grafted; + if (start == end) { - next.enlarge (end - start); + M17n.DebugPrint (" done\n"); return; } - end -= next.graft_backward (interval, start, end); + rear_grafted = true; + } + if ((grafted = graft_forward (interval, start, end)) > 0) + { + start += grafted; if (start == end) - return; + { + M17n.DebugPrint (" done\n"); + return; + } + front_grafted = true; } - - if ((start += graft_forward (interval, start, end)) == end) - return; - if (interval != null) - interval = interval.Copy (mtext, start, end); + 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); @@ -1241,29 +1477,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) + Stack.Clear (); Left.Delete (start, From); To -= From - start; end -= From - start; From = start; + front_checked = true; } if (end > To) { if (start >= To) { + if (start == To && isRearSensitive) + Stack.Clear (); Right.Delete (start, end); return; } + if (isSensitive) + Stack.Clear (); Right.Delete (To, end); end = To; + rear_checked = true; } + if (start == From + && ! front_checked + && start > 0 + && isRearSensitive) + Prev.Stack.Clear (); + if (end == To + && ! rear_checked + && Next != null + && isFrontSensitive) + Next.Stack.Clear (); if (start == From && end == To) { if (Right == null) @@ -1289,6 +1549,8 @@ namespace M17N.Core { int len = end - start; + if (isSensitive) + Stack.Clear (); for (MInterval i = this; i != null; i = i.Parent) i.Length -= len; } @@ -1297,7 +1559,7 @@ namespace M17N.Core 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) @@ -1319,6 +1581,8 @@ namespace M17N.Core end = To; } + if (! Stack.IsEmpty && isSensitive) + Stack.Clear (); if (start > From) divide_left (start); if (end < To) @@ -1327,21 +1591,23 @@ namespace M17N.Core } /// Combine intervals between HEAD and TAIL (both inclusive) to - /// the common parent of HEAD and TAIL while assuming that the - /// intervals are mergeable. + /// 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 "); head.DumpOne (true, false); - M17n.DebugPrint (" through "); tail.DumpOne (true, false); + 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 (" common root is "); root.DumpOne (false, true); + M17n.DebugPrint (" with common root {0}\n", root); if (from < root.From) { @@ -1349,7 +1615,7 @@ namespace M17N.Core while (true) { - M17n.DebugPrint ("merging "); prev.DumpOne (false, true); + M17n.DebugPrint ("merging {0}\n", prev); prev.vacate_node (prev.Left, root); if (prev == head) break; @@ -1366,7 +1632,7 @@ namespace M17N.Core while (true) { - M17n.DebugPrint ("merging "); next.DumpOne (false, true); + M17n.DebugPrint ("merging {0}\n", next); next.vacate_node (next.Right, root); if (next == tail) break; @@ -1384,19 +1650,23 @@ namespace M17N.Core update_from_to (); MInterval head = find_head (start), i = head; - MInterval tail = find_tail (end).Next; + MInterval tail = start < end ? find_tail (end) : head; + + if (tail.To < Length) + tail = tail.Next; if (start == head.From && start > 0) { - i = head.Prev; - if (! head.mergeable (i)) - i = head; + 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 (next == null || ! i.mergeable (next)) + if (! i.mergeable (next)) { if (head != i) combine (head, i); @@ -1404,12 +1674,14 @@ namespace M17N.Core } i = next; } + 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) @@ -1433,11 +1705,16 @@ namespace M17N.Core 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 (); + } } } @@ -1446,28 +1723,64 @@ namespace M17N.Core update_from_to (); MInterval head = find_head (start); MInterval tail = find_tail (end); - while (! head.Stack.IsEmpty && head.From > 0) - { - MInterval prev = head.Prev; + Pop (head.From, tail.To); + } - if (prev.Stack.IsEmpty || head.Stack.Val != prev.Stack.Val) - break; - head = head.Prev; + 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; } - while (! tail.Stack.IsEmpty && tail.To < mtext.Length) + if (end > To) { - MInterval next = tail.Next; + if (start >= To) + { + Right.PopAll (start, end); + return; + } + Right.PopAll (To, end); + end = To; + } - if (next.Stack.IsEmpty || tail.Stack.Val != next.Stack.Val) - break; - tail = tail.Next; + if (! Stack.IsEmpty) + { + if (isSensitive) + Stack.Clear (); + else + { + if (start > From) + divide_left (start); + if (end < To) + divide_right (end); + Stack.Clear (); + } } - Pop (head.From, tail.To); } - private void DumpOne (bool with_prop, bool newline) + public override string ToString () { - DumpOne (with_prop, newline, false); + 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) @@ -1517,7 +1830,7 @@ namespace M17N.Core public void DumpNested (bool force) { - DumpNested (Key.ToString () + ":", force); + DumpNested (" " + Key.ToString () + ":", force); } public void DumpNested (string indent, bool force)