From f35666d3149c6a16b0c6473475d3ce792b3a62de Mon Sep 17 00:00:00 2001 From: handa Date: Mon, 6 Apr 2009 07:10:19 +0000 Subject: [PATCH] *** empty log message *** --- MText.cs | 589 ++++++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 339 insertions(+), 250 deletions(-) diff --git a/MText.cs b/MText.cs index 0ae3003..21d0bc9 100644 --- a/MText.cs +++ b/MText.cs @@ -267,9 +267,9 @@ namespace M17N.Core MInterval interval; if (p == null) - interval = new MInterval (plist.Key, to - from); + interval = new MInterval (plist.Key, this, to - from); else - interval = ((MInterval) p.Val).copy (from, to); + interval = ((MInterval) p.Val).Copy (from, to); ((MInterval) plist.Val).Insert (pos, interval); } } @@ -451,129 +451,131 @@ 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) { MInterval i = find (pos); - return (i.stack.IsEmpty ? null : (MTextProperty) i.stack.Val); + return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val); } public MTextProperty Get (int pos, out MTextProperty[] array) { MInterval i = find (pos); - if (i.stack.IsEmpty) + if (i.Stack.IsEmpty) { array = null; return null; } - array = new MTextProperty[i.stack.Count]; + array = new MTextProperty[i.Stack.Count]; int idx; MPlist p; - for (idx = 0, p = i.stack; ! p.IsEmpty; idx++, p = p.Next) + for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next) array[idx] = (MTextProperty) p.Val; return array[idx - 1]; } - private MInterval (MSymbol key, int length, MPlist stack) + private MInterval (MSymbol key, MText mt, int length, MPlist stack) { - this.key = key; - total_length = length; - from = 0; - to = total_length; - this.stack = stack.Clone (); - id = count++; + Key = key; + mtext = mt; + Length = length; + From = 0; + To = Length; + Stack = stack.Clone (); + ID = count++; } 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 { return (Left == null ? this : Left.LeftMost); } } - private MInterval right_most_node + private MInterval RightMost { - get { return (right == null ? this : right.right_most_node); } + get { return (Right == null ? this : 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); else - for (i = parent; i != null && i.left == null; i = i.parent); + for (i = Parent; i != null && i.Left == null; 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); else - for (i = parent; i != null && i.right == null; i = i.parent); + for (i = Parent; i != null && i.Right == null; i = i.Parent); return i; } } @@ -581,43 +583,54 @@ namespace M17N.Core private MInterval find (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 (pos); + if (pos >= To) + return Right.find (pos); return this; } + private bool mergeable (MInterval i) + { + MPlist p1, p2; + + for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty; + p1 = p1.Next, p2 = p2.Next) + if (p1.Val != p2.Val) + return false; + return (p1.IsEmpty && p2.IsEmpty); + } + // p-. or .-p p-. or .-p // .-this-. .-right-. // left .-right-. -> .-this-. c2 // c1 c2 left c1 private MInterval promote_right () { - int right_length = right.total_length; + int right_length = Right.Length; MInterval c1; - if (parent == null) - mtext.intervals.Put (key, right); - else if (parent.left == this) - parent.left = right; + if (Parent == null) + mtext.intervals.Put (Key, Right); + else if (Parent.Left == this) + Parent.Left = Right; else - parent.right = right; - right.parent = parent; - c1 = right.left; - right.left = this; - - parent = right; - right = c1; - parent.total_length += total_length; - total_length -= right_length; + Parent.Right = Right; + Right.Parent = Parent; + c1 = Right.Left; + Right.Left = this; + + Parent = Right; + Right = c1; + Parent.Length += Length; + Length -= right_length; if (c1 != null) { - c1.parent = this; - parent.total_length -= c1.total_length; - total_length += c1.total_length; + c1.Parent = this; + Parent.Length -= c1.Length; + Length += c1.Length; } - return parent; + return Parent; } // p-. or .-p p-. or .-p @@ -626,30 +639,30 @@ namespace M17N.Core // c1 c2 c2 right private MInterval promote_left () { - int left_length = left.total_length; + int left_length = Left.Length; MInterval c1; - if (parent == null) - mtext.intervals.Put (key, left); - else if (parent.left == this) - parent.left = left; + if (Parent == null) + mtext.intervals.Put (Key, Left); + else if (Parent.Left == this) + Parent.Left = Left; else - parent.right = left; - left.parent = parent; - c1 = left.left; - left.right = this; - - parent = left; - left = c1; - parent.total_length += total_length; - total_length -= left_length; + Parent.Right = Left; + Left.Parent = Parent; + c1 = Left.Left; + Left.Right = this; + + Parent = Left; + Left = c1; + Parent.Length += Length; + Length -= left_length; if (c1 != null) { - c1.parent = this; - parent.total_length -= c1.total_length; - total_length += c1.total_length; + c1.Parent = this; + Parent.Length -= c1.Length; + Length += c1.Length; } - return parent; + return Parent; } private MInterval balance () @@ -666,48 +679,50 @@ 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; i = i.promote_left (); - i.right.balance (); + 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; i = i.promote_right (); - i.left.balance (); + i.Left.balance (); } } return i; } - public MInterval copy (int start, int end) + public MInterval Copy (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 (start, end); + left_copy = Left.Copy (start, From); } - else if (end > to) + else if (end > To) { - if (start >= to) - return right.copy (start, end); - right_copy = right.copy (to, end); + if (start >= To) + return Right.Copy (start, end); + right_copy = Right.Copy (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, mtext, end - start, Stack); + remove_properties (MTextProperty.Flag.Sensitive); + copy.Left = left_copy; + copy.Right = right_copy; + + return copy; } // this-. ==> this-. @@ -715,18 +730,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) + 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,24 +750,24 @@ 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-left({0}) at ", pos); DumpOne (false, true); - from = pos; - if (left != null) + 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) { - for (MPlist p = stack; ! p.IsEmpty;) + for (MPlist p = Stack; ! p.IsEmpty;) { MTextProperty prop = (MTextProperty) p.Val; @@ -763,11 +778,11 @@ namespace M17N.Core } } - private void merge_front_properties (MPlist plist) + private void inherit_front_properties (MPlist plist) { - for (MInterval i = left_most_node; i != null; i = i.next) + for (MInterval i = LeftMost; i != null; i = i.Next) { - if (! stack.IsEmpty) + if (! Stack.IsEmpty) break; for (MPlist p = plist; ! p.IsEmpty; p = p.Next) { @@ -775,16 +790,16 @@ namespace M17N.Core if ((prop.flags & MTextProperty.Flag.RearSticky) == MTextProperty.Flag.RearSticky) - i.stack.Add (prop.key, prop); + i.Stack.Add (prop.key, prop); } } } - private void merge_rear_properties (MPlist plist) + private void inherit_rear_properties (MPlist plist) { - for (MInterval i = right_most_node; i != null; i = i.prev) + for (MInterval i = RightMost; i != null; i = i.Prev) { - if (! stack.IsEmpty) + if (! Stack.IsEmpty) break; for (MPlist p = plist; ! p.IsEmpty; p = p.Next) { @@ -792,7 +807,7 @@ namespace M17N.Core if ((prop.flags & MTextProperty.Flag.FrontSticky) == MTextProperty.Flag.FrontSticky) - i.stack.Add (prop.key, prop); + i.Stack.Add (prop.key, prop); } } } @@ -800,34 +815,28 @@ namespace M17N.Core public void Insert (int pos, MInterval interval) { 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) + Console.Write ("insert({0}) in ", pos); DumpOne (false, true); + + if (pos < From) + Prev.Insert (pos, interval); + else if (pos == From) { if (pos > 0) { + MInterval prev = Prev; + + if (Left == null) + { + prev.Insert (pos, interval); + return; + } prev.remove_properties (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky); - interval.merge_front_properties (prev.stack); + interval.inherit_front_properties (prev.Stack); } remove_properties (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky); - interval.merge_rear_properties (stack); + interval.inherit_rear_properties (Stack); // INTERVAL is ready to insert. // @@ -838,34 +847,44 @@ namespace M17N.Core if (pos > 0) { - MInterval i = left.right_most_node; + MInterval i = Left.RightMost; - i.left = interval; - interval.parent = i; - for (; i != null; i = i.parent) - i.total_length += interval.total_length; + i.Left = interval; + interval.Parent = i; + for (; i != null; i = i.Parent) + i.Length += interval.Length; } else { - left = interval; + Left = interval; - for (MInterval i = this; i != null; i = i.parent) - i.total_length += interval.total_length; + for (MInterval i = this; i != null; i = i.Parent) + i.Length += interval.Length; } } - else // pos == to + else if (pos < To) { - if (right != null) + remove_properties (MTextProperty.Flag.Sensitive); + divide_right (pos).Insert (pos, interval); + } + else if (pos == To) + { + if (pos < mtext.Length) { - MInterval left_most = right.left_most_node; + MInterval next = Next; - left_most.remove_properties + if (Right == null) + { + next.Insert (pos, interval); + return; + } + next.remove_properties (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky); - interval.merge_rear_properties (left_most.stack); + interval.inherit_rear_properties (next.Stack); } remove_properties (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky); - interval.merge_front_properties (stack); + interval.inherit_front_properties (Stack); // INTERVAL is ready to insert. // @@ -874,102 +893,104 @@ namespace M17N.Core // child interval-. // child - if (right != null) + if (Right != null) { - MInterval i = right.left_most_node; + MInterval i = Right.LeftMost; - i.left = interval; - interval.parent = i; - for (; i != null; i = i.parent) - i.total_length += interval.total_length; + i.Left = interval; + interval.Parent = i; + for (; i != null; i = i.Parent) + i.Length += interval.Length; } else { - right = interval; + Right = interval; - for (MInterval i = this; i != null; i = i.parent) - i.total_length += interval.total_length; + for (MInterval i = this; i != null; i = i.Parent) + i.Length += interval.Length; } } + else // (pos > To) + Next.Insert (pos, interval); } private void vacate_node (MInterval interval) { - Console.WriteLine ("vacate #{0} to #{1}", id, interval.id); + Console.WriteLine ("vacate #{0} to #{1}", ID, interval.ID); if (interval != null) - interval.parent = parent; - if (parent == null) + interval.Parent = Parent; + if (Parent == null) { - mtext.intervals.Put (key, interval); + 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 != null; 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) + Console.Write ("delete({0} {1}) from ", start, end); DumpOne (false, true); + if (start < From) { - if (end <= from) + if (end <= From) { - left.Delete (start, end); + Left.Delete (start, end); return; } - left.Delete (start, from); - to -= from - start; - end -= from - start; - from = start; + Left.Delete (start, From); + To -= From - start; + end -= From - start; + From = start; } - if (end > to) + if (end > To) { - if (start >= to) + if (start >= To) { - right.Delete (start, end); + Right.Delete (start, end); return; } - right.Delete (to, end); - end = to; + Right.Delete (To, end); + end = To; } - if (start == from && end == to) + 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; + for (MInterval i = this; i != null; i = i.Parent) + i.Length -= len; } } @@ -977,74 +998,142 @@ namespace M17N.Core { update_from_to (); Console.Write ("push({0} {1}) at ", start, end); DumpOne (false, true); - if (start < from) + 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 (start > From) divide_left (start); - if (end < to) + if (end < To) divide_right (end); - stack.Push (prop.key, prop); + Stack.Push (prop.key, prop); } + private bool try_merge_prev () + { + MInterval prev = Prev; + + if (! mergeable (prev)) + return false; + + int len = prev.Length - prev.LeftLength; + + // PREV is Left, Left.Right, ..., or Left....Right. + if (prev != Left) + { + prev.Parent.Right = prev.Left; + while (prev.Parent != Left) + { + prev.Length -= len; + prev = prev.Parent; + } + } + Left.Length -= len; + if (Left.Length == Left.LeftLength) + Left = Left.Left; + return true; + } + + private bool try_merge_next () + { + MInterval next = Next; + + if (! mergeable (next)) + return false; + + int len = next.Length - next.LeftLength; + + // NEXT is Right, Right.Left, ..., or Right....Left. + if (next != Right) + { + next.Parent.Left = next.Right; + while (next.Parent != Right) + { + next.Length -= len; + next = next.Parent; + } + } + Right.Length -= len; + if (Right.Length == Right.LeftLength) + Right = Right.Left; + + return true; + } + + public void Pop (int start, int end) { update_from_to (); Console.Write ("pop({0} {1}) at ", start, end); DumpOne (false, true); - if (start < from) + 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) + bool check_prev = start == From && start > 0; + bool check_next = end == To && end < mtext.Length; + + if (! check_prev) divide_left (start); - if (end < to) + if (! check_next) divide_right (end); - stack.Pop (); + 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) + { + Next.try_merge_prev (); + } } } private void DumpOne (bool with_prop, bool newline) { - Console.Write ("#{0}({1} {2} {3}", id, total_length, from, to); + Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To); if (with_prop) - foreach (MPlist p in stack) + foreach (MPlist p in Stack) Console.Write (" " + p.Val); Console.Write (")"); if (newline) @@ -1055,13 +1144,13 @@ namespace M17N.Core { update_from_to (); - if (left != null) - left.Dump (); - if (from > 0) + if (Left != null) + Left.Dump (); + if (From > 0) Console.Write (" "); DumpOne (true, false); - if (right != null) - right.Dump (); + if (Right != null) + Right.Dump (); } } -- 1.7.10.4