From f3bc451dc0679e6e83e508a13a9bdfe4b503b51c Mon Sep 17 00:00:00 2001 From: handa Date: Tue, 28 Apr 2009 06:19:52 +0000 Subject: [PATCH] *** empty log message *** --- MText.cs | 478 ++++++++++++++++++++++++++++++-------------------------------- 1 file changed, 235 insertions(+), 243 deletions(-) diff --git a/MText.cs b/MText.cs index 9d98c4e..c861720 100644 --- a/MText.cs +++ b/MText.cs @@ -123,6 +123,13 @@ namespace M17N.Core intervals = new MPlist (); } + public static MText operator+ (object obj, MText mt) + { + if (obj is string) + return new MText ((string) obj) + mt; + throw new Exception ("Unknown object type: " + obj.GetType()); + } + public static MText operator+ (MText mt1, MText mt2) { MText mt = new MText (); @@ -133,6 +140,15 @@ namespace M17N.Core return mt; } + public static MText operator+ (string str, MText mt) + { + MText mtnew = new MText (str); + + mtnew.sb.Append (mt.sb); + mtnew.nchars += mt.nchars; + return mtnew; + } + // Public properties public bool ReadOnly { get { return read_only; } } public int Length { get { return nchars; } } @@ -238,32 +254,41 @@ 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; - 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 intervals) { MPlist p = mt2.intervals.Find (plist.Key); - MInterval i; + MInterval i = p == null ? null : (MInterval) p.Val; - if (p == null) - i = new MInterval (plist.Key, this, to - from); - else - i = ((MInterval) p.Val).Copy (this, from, to); - ((MInterval) plist.Val).Insert (pos, i); + ((MInterval) plist.Val).Insert (pos, i, from, to); } foreach (MPlist plist in mt2.intervals) if (intervals.Find (plist.Key) == null) { - MInterval i = (((MInterval) plist.Val).Copy (this, from, to)); - intervals.Push (plist.Key, i); + 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; } private void insert (int pos, int c) @@ -286,8 +311,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] @@ -332,9 +356,10 @@ namespace M17N.Core { 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)); - MText mt = new MText (sb.ToString ().Substring (pos_to_idx (this, from), - pos_to_idx (this, to))); foreach (MPlist p in intervals) mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, from, to)); return mt; @@ -376,7 +401,7 @@ namespace M17N.Core foreach (MPlist plist in intervals) ((MInterval) plist.Val).Delete (from, to); else - intervals = new MPlist (); + intervals.Clear (); if (M17n.debug) DumpPropNested (); return this; @@ -535,17 +560,23 @@ namespace M17N.Core ID = count++; } + /// POS must be smaller than Length; public MTextProperty Get (int pos) { MInterval i = find (pos); + if (i.To == pos) + i = i.Next; return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val); } + /// POS must be smaller than Length; public MTextProperty Get (int pos, out MTextProperty[] array) { MInterval i = find (pos); + if (i.To == pos) + i = i.Next; if (i.Stack.IsEmpty) { array = null; @@ -567,7 +598,7 @@ namespace M17N.Core Length = length; From = 0; To = Length; - Stack = stack.Clone (); + Stack = stack == null ? new MPlist () : stack.Clone (); ID = count++; } @@ -643,8 +674,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; @@ -660,8 +694,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; @@ -677,7 +714,7 @@ namespace M17N.Core update_from_to (); if (pos < From) return Left.find (pos); - if (pos >= To) + if (pos > To) return Right.find (pos); return this; } @@ -812,14 +849,8 @@ namespace M17N.Core copy = new MInterval (Key, null, end - start, Stack); copy.mtext = mt; - - if (isSensitive) - { - if (isRearSticky && start < From && ! Left.Stack.IsEmpty) - Stack.Clear (); - else if (isFrontSticky && end > To && ! Right.Stack.IsEmpty) - Stack.Clear (); - } + if (isSensitive && (From < start || end < To)) + copy.Stack.Clear (); if (left_copy != null) { copy.Left = left_copy; @@ -873,271 +904,227 @@ namespace M17N.Core return interval; } - private void remove_properties (MTextProperty.Flags flags) - { - if (! Stack.IsEmpty - && (Key.TextPropertyFlags & flags) == flags) - Stack.Clear (); - } - - private void inherit_front_properties (MPlist plist) + private void set_mtext (MText mt) { - for (MInterval i = LeftMost; i != null; i = i.Next) - { - if (! Stack.IsEmpty) - break; - for (MPlist p = plist; ! p.IsEmpty; p = p.Next) - { - MTextProperty prop = (MTextProperty) p.Val; - - if ((p.Key.TextPropertyFlags & MTextProperty.Flags.RearSticky) - == MTextProperty.Flags.RearSticky) - i.Stack.Add (prop.key, prop); - } - } + mtext = mt; + if (Left != null) + Left.set_mtext (mt); + if (Right != null) + Right.set_mtext (mt); } - private void inherit_rear_properties (MPlist plist) + private void enlarge (int len) { - for (MInterval i = RightMost; i != null; i = i.Prev) + 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 ((p.Key.TextPropertyFlags & MTextProperty.Flags.FrontSticky) - == MTextProperty.Flags.FrontSticky) - i.Stack.Add (prop.key, prop); + i.From += len; + i.To += len;; } } } - private MInterval delete_node_forward () + private int graft_forward (MInterval interval, int start, int end) { - if (Parent != null) - { - int len = Length - RightLength; - - for (MInterval i = Parent; i != null; i = i.Parent) - i.Length -= len; - if (Parent.Left == this) - Parent.Left = Right; - else - Parent.Right = Right; - } - - if (Right != null) - { - Right.Parent = Parent; - return Right.LeftMost; - } - return Parent; - } + int len; - private MInterval delete_node_backward () - { - if (Parent != null) + if (! Stack.IsEmpty && isRearSticky) + len = end - start; + else if (interval == null) + len = Stack.IsEmpty ? end - start : 0; + else { - int len = Length - LeftLength; + MInterval i = interval.find (start); - for (MInterval i = Parent; i != null; i = i.Parent) - i.Length -= len; - if (Parent.Left == this) - Parent.Left = Left; - else - Parent.Right = Left; + if (i.To == start && i.Right != null) + i = i.Next; + len = 0; + while (i != null && mergeable (i)) + { + M17n.DebugPrint (" grafting "); i.DumpOne (false, false); + 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 (Left != null) - { - Left.Parent = Parent; - return Left.RightMost; - } - return Parent; + M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true); + if (len > 0) + enlarge (len); + return len; } - private void set_mtext (MText mt) + private int graft_backward (MInterval interval, int start, int end) { - 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; + int len; - len = 0; - if (forward) - { - i = interval.LeftMost; - while (i != null) - { - if (! mergeable (i)) - break; - len += i.Length - i.RightLength; - i = i.delete_node_forward (); - } - } + if (! Stack.IsEmpty && isFrontSticky) + len = end - start; + else if (interval == null) + len = Stack.IsEmpty ? end - start : 0; else { - i = interval.RightMost; - while (i != null) - { - if (! mergeable (i)) - break; - len += i.Length - i.LeftLength; - i = i.delete_node_backward (); - } - } + MInterval i = interval.find (end); - if (len == 0) - return interval; - Length += len; - To += len; - M17n.DebugPrint ("grafted {0} in ", len); DumpOne (false, true); - for (MInterval prev = this, ii = this.Parent; ii != null; - prev = ii, ii = ii.Parent) - { - ii.Length += len; - if (prev == ii.Left) + if (i.From == end && i.Left != null) + i = i.Prev; + len = 0; + while (i != null && mergeable (i)) { - ii.From += len; - ii.To += len;; + M17n.DebugPrint (" grafting "); i.DumpOne (false, false); + 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; } } - if (i != null) - while (i.Parent != null) i = i.Parent; - return i; + + M17n.DebugPrint (" grafted {0} in ", len); DumpOne (false, true); + 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, false); - interval.set_mtext (mtext); + M17n.DebugPrint ("insert({0} to {1}) at {2} in ", start, end, pos); + DumpOne (false, false); if (pos < From) - Prev.Insert (pos, interval); + Left.Insert (pos, interval, start, end); else if (pos == From) { - MInterval prev = Prev; - - if (prev != null) + if (Left != null) { - if (Left == null) - { - prev.Insert (pos, interval); - return; - } - prev.remove_properties - (MTextProperty.Flags.Sensitive|MTextProperty.Flags.RearSticky); - interval.inherit_front_properties (prev.Stack); + MInterval prev = Prev; + + if (prev.isSensitive && prev.isRearSticky) + prev.Stack.Clear (); + start += prev.graft_forward (interval, start, end); } - remove_properties - (MTextProperty.Flags.Sensitive|MTextProperty.Flags.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 (isSensitive && isFrontSticky) + Stack.Clear (); + if (start < end) { - MInterval i; - - if (Left != null) + end -= graft_backward (interval, start, end); + if (start < end) { - // .-this-. ==> .-this-. - // left-. .-left-. - // child child-. - // interval - i = Left.RightMost; - i.Right = interval; - } - else - { - Left = interval; - i = this; + if (interval != null) + interval = interval.Copy (mtext, start, end); + else + interval = new MInterval (Key, mtext, end - start, null); + + 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; } - interval.Parent = i; - for (; i != null; i = i.Parent) - i.Length += interval.Length; } } else if (pos < To) { - remove_properties (MTextProperty.Flags.Sensitive); + if (isSensitive) + Stack.Clear (); - int len; - interval = graft (interval, true, out len); + int len = graft_forward (interval, start, end); + start += len; pos += len; - if (interval != null) - interval = graft (interval, false, out len); - if (interval != null) + if (start < end) { - divide_right (pos); - Right.Left = interval; - interval.Parent = Right; - for (MInterval i = Right; i != null; i = i.Parent) - i.Length += interval.Length; + end -= graft_backward (interval, start, end); + if (start < end) + { + if (interval != null) + interval = interval.Copy (mtext, start, end); + 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 = Next; - - if (next != null) + if (Right != null) { - if (Right == null) - { - next.Insert (pos, interval); - return; - } - next.remove_properties - (MTextProperty.Flags.Sensitive|MTextProperty.Flags.FrontSticky); - interval.inherit_rear_properties (next.Stack); + MInterval next = Next; + + if (next.isSensitive && next.isFrontSticky) + next.Stack.Clear (); + end -= next.graft_backward (interval, start, end); } - remove_properties - (MTextProperty.Flags.Sensitive|MTextProperty.Flags.RearSticky); - interval.inherit_front_properties (Stack); - - int len; - interval = graft (interval, true, out len); - if (interval != null && next != null) - interval = next.graft (interval, false, out len); - if (interval != null) + if (isSensitive && isRearSticky) + Stack.Clear (); + if (start < end) { - MInterval i; - - if (Right != null) + start += graft_forward (interval, start, end); + if (start < end) { - // .-this-. ==> .-this-. - // .-right .-right - // child .-child - // interval + if (interval != null) + interval = interval.Copy (mtext, start, end); + else + interval = new MInterval (Key, mtext, end - start, null); - i = Right.LeftMost; - i.Left = interval; - } - else - { - Right = interval; - i = this; + 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; } - interval.Parent = i; - for (; i != null; i = i.Parent) - i.Length += interval.Length; } } else // (pos > To) - Next.Insert (pos, interval); + Next.Insert (pos, interval, start, end); M17n.DebugPrint (" done\n"); } @@ -1262,13 +1249,17 @@ namespace M17N.Core Stack.Push (prop.key, prop); } - private static void merge_nodes (MInterval head, MInterval tail) + /// Combine intervals between HEAD and TAIL (both inclusive) to + /// the common parent of HEAD and TAIL while assuming that the + /// intervals are mergeable. + private static void combine (MInterval head, MInterval tail) { M17n.DebugPrint ("merging "); head.DumpOne (true, false); M17n.DebugPrint (" through "); tail.DumpOne (true, false); 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; @@ -1333,7 +1324,7 @@ namespace M17N.Core if (! tail.mergeable (i)) { if (head != tail) - merge_nodes (head, tail); + combine (head, tail); head = i; } tail = i; @@ -1346,7 +1337,7 @@ namespace M17N.Core tail = i; } if (head != tail) - merge_nodes (head, tail); + combine (head, tail); } public void Pop (int start, int end) @@ -1429,7 +1420,7 @@ namespace M17N.Core public void DumpNested (bool force) { - DumpNested ("", force); + DumpNested (Key.ToString () + ":", force); } public void DumpNested (string indent, bool force) @@ -1447,10 +1438,11 @@ 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 + "`-"); + Console.Write ("`-"); DumpOne (true, true, true); if (Right != null) { -- 1.7.10.4