From 0c7b5eaf4412e608bb5ef6685f4ae66c5c1ca51c Mon Sep 17 00:00:00 2001 From: handa Date: Wed, 25 Mar 2009 12:15:45 +0000 Subject: [PATCH] *** empty log message *** --- MPlist.cs | 54 ++++++- MText.cs | 483 +++++++++++++++++++++++++++++++------------------------------ 2 files changed, 296 insertions(+), 241 deletions(-) diff --git a/MPlist.cs b/MPlist.cs index 0295da9..f54b47f 100644 --- a/MPlist.cs +++ b/MPlist.cs @@ -1,4 +1,5 @@ using System; +using System.Collections; using M17N.Core; namespace M17N.Core @@ -18,7 +19,7 @@ namespace M17N.Core } } - public class MPlist + public class MPlist : IEnumerable { private MProperty prop; private MPlist next; @@ -117,5 +118,56 @@ namespace M17N.Core } return val; } + + public MPlist find (MSymbol key) + { + for (MPlist p = this; ! p.tailp; p = p.next) + if (p.prop.key == key) + return p; + return null; + } + + // Implement IEnumerable interface. + + public virtual IEnumerator GetEnumerator () + { + return new Enumerator (this); + } + + private class Enumerator : IEnumerator + { + private MPlist plist; + private MPlist current; + + internal Enumerator (MPlist plist) + { + this.plist = plist; + } + + public object Current + { + get { + if (current == null || current.tailp) + throw new InvalidOperationException (); + return current; + } + } + + public void Reset () + { + current = null; + } + + public bool MoveNext () + { + if (current == null) + current = plist; + else if (current.tailp) + return false; + else + current = current.next; + return true; + } + } } } diff --git a/MText.cs b/MText.cs index a610507..4561609 100644 --- a/MText.cs +++ b/MText.cs @@ -20,47 +20,21 @@ namespace M17N.Core public class MTextProperty { - private enum MTextPropertyFlagMask - { - FRONT_STICKY = 1, - REAR_STICKY = 2 - }; - - internal MProperty prop; - internal byte flags; - internal MText mtext; - internal from; - internal to; + private MProperty prop; + private bool front_sticky; + private bool rear_sticky; + private MText mtext; - public MProperty Prop - { - get { return prop; } - } - public bool FrontSticky - { - get { return (flags & MTextPropertyFlagMask.FRONT_STICKY) != 0; } - } - public bool RearSticky - { - get { return (flags & MTextPropertyFlagMask.REAR_STICKY) != 0; } - } - public MText mtext - { - get { return mtext; } - } - public int from - { - get { return from; } - } - public int to - { - get { return to; } - } + public MProperty Prop { get { return prop; } } + public bool FrontSticky { get { return front_sticky; } } + public bool RearSticky { get { return rear_sticky; } } + public MText Mtext { get { return mtext; } } - public MTextProperty (bool front_sticky, bool rear_sticky) + public MTextProperty (MProperty prop, bool front_sticky, bool rear_sticky) { - this.flags = ((front_sticky ? MTextPropertyFlagMask.FRONT_STICKY : 0) - | (rear_sticky ? MTextPropertyFlagMask.REAR_STICKY : 0)); + this.prop = prop; + this.front_sticky = front_sticky; + this.rear_sticky = rear_sticky; } } @@ -69,18 +43,11 @@ namespace M17N.Core #if false public enum MTextFormat format; #endif - - private struct KeyIntervalPair - { - object key; - MInterval interval; - }; - private StringBuilder sb; private int nchars; private int cache_pos; private int cache_idx; - private stack root_intervals; + private MPlist intervals; private MProperty default_property; private bool read_only; @@ -234,12 +201,33 @@ namespace M17N.Core sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx)); nchars += to - from; - if (root_interval != null) + + if (mt2.intervals != null + && ! mt2.intervals.tailp) { - MInterval interval = (mt2.root_interval == null - ? null - : mt2.root_interval.CopyTree (from, to)); - root_interval.Insert (pos, interval); + if (intervals == null) + intervals = new MPlist (); + foreach (MInterval interval in mt2.intervals) + if (intervals.find (interval.key) == null) + intervals.push (interval.key, new MInterval (interval.key, mt)); + } + + if (intervals != null) + { + foreach (MInterval root in intervals) + { + MInterval interval; + + if (mt2.intervals != null + && ! mt2.intervals.tailp) + { + interval = mt2.intervals.find (root.key); + if (interval != null) + interval = interval.CopyTree (from, to); + } + if (interval == null) + interval = new MInterval (root.key, to - from); + root.Insert (pos, interval); } } @@ -298,8 +286,12 @@ namespace M17N.Core public void PushProp (int from, int to, MTextProperty prop) { - if (root_interval == null) - root_interval = new MInterval (this); + MInterval root; + + if (intervals == null + || (root = intervals.find (prop.key)) ) + intervals = new MPlist (prop.key, new MInterval (prop.key, this)); + root_interval.Push (from, to, prop); } @@ -313,12 +305,12 @@ namespace M17N.Core // [1 (0 1)] [1 (2 3)] private int total_length; private int from, to; - private object key; + private MSymbol key; private Stack stack; private MInterval left, right, parent; private MText mtext; - public MInterval (object key, int length) + public MInterval (MSymbol key, int length) { if (length <= 0) throw new Exception ("Invalid interval length"); @@ -327,7 +319,7 @@ namespace M17N.Core stack = new Stack (); } - private MInterval (object key, int length, Stack stack) + private MInterval (MSymbol key, int length, Stack stack) { this.key = key; total_length = length; @@ -336,7 +328,7 @@ namespace M17N.Core stack = new Stack (stack); } - public MInterval (object key, MText mt) + public MInterval (MSymbol key, MText mt) { this.key = key; mtext = mt; @@ -346,17 +338,62 @@ namespace M17N.Core stack = new Stack (); } - private MInterval find (int pos) + private void update_from_to () { if (parent != null) { - from = parent.from - total_length; - if (left != null) - from += left.total_length; - to = parent.from; - if (right != null) - to -= right.total_length; + from = parent.from - total_length + LeftLength; + to = parent.from - RightLength; } + } + + private int LeftLength + { + get { return (left == null ? 0 : left.total_length); } + } + + private int RightLength + { + get { return (right == null ? 0 : right.total_length); } + } + + private MInterval LeftMostNode + { + get { return (left == null ? this : left.LeftMostNode); } + } + + private MInterval RightMostNode + { + get { return (right == null ? this : right.RightMostNode); } + } + + private MInterval LeftNode { + get { + MInterval i; + + if (left != null) + for (i = left; i.right != null; i = i.right); + else + for (i = parent; i != null && i.left == null; i = i.parent); + return i; + } + } + + private MInterval RightNode { + get { + MInterval i; + + if (right != null) + for (i = right; i.left != null; i = i.left); + else + for (i = parent; i != null && i.right == null; i = i.parent); + return i; + } + } + + private MInterval find (int pos) + { + update_from_to (); if (pos < from) return left.find (pos); if (pos >= to) @@ -374,7 +411,7 @@ namespace M17N.Core MInterval c1; if (parent == null) - mtext.update_root_interval (key, right); + mtext.root_intervals.put (key, right); else if (parent.left == this) parent.left = right; else @@ -430,33 +467,33 @@ namespace M17N.Core private MInterval balance () { - MInterval interval = this; + MInteval i = this; while (true) { // .-this-. // .-left-. .-right-. - int left_length = (left == null ? 0 : left.total_length); - int right_length = (right == null ? 0 : right.total_length); - int length = total_length - left_length - right_length; - int diff = ((left_length + length) - - - (interval.total_end - this_end)); - int abs = Math.Abs (diff); - - if (left == null) - diff = - - if (abs < this_end - this_start) - break; - if (diff < 0) + // c1 c2 c3 c4 + int diff = i.LeftLength - i.RightLength; + int new_diff; + + if (diff > 0) { - interval = interval.promote_right (); - interval.left.balance (); + new_diff = (i.total_length - i.LeftLength + + i.left.RightLength - i.left.LeftLength); + if (Math.Abs (new_diff) >= diff) + break; + i = i.promote_left (); + i.right.balance (); } - else + else if (diff < 0) { - interval = interval.promote_left (); - interval.right.balance (); + new_diff = (i.total_length - i.RightLength + + i.right.LeftLength - i.right.RightLength); + if (Math.Abs (new_diff) >= diff) + break; + i = i.promote_right (); + i.left.balance (); } } return interval; @@ -464,158 +501,52 @@ namespace M17N.Core public MInterval CopyTree (int start, int end) { - MInterval interval_start, interval_end, interval; - int offset_start, offset_end; - - start <<= 2; - end <<= 2; - interval_start = find (start, out offset_start); - interval_end = find (end, out offset_end); - - interval = new MInterval (); - interval.total_start = 0; - interval.total_end = end - start; - interval.stack = new Stack (interval_start.stack); - interval = interval.divide_right (offset_start); - while (interval_start != interval_end) + MInterval this_copy, left_copy, right_copy; + + update_from_to (); + if (start < from) { - interval_start = interval_start.Right; - interval = interval.divide_right (interval_start.End - - interval_start.Start); + if (end <= from) + return left.CopyTree (start, end); + left_copy = left.CopyTree (start, from); } - return interval; - } - - private MInterval CopyNode () - { - return new MInterval (total_start, total_end, stack); - } - - private int Start { - get { - return (left == null ? total_start : total_start + left.total_end); - } - } - - private int End { - get { - return (right == null ? total_end : total_end + right.total_start); - } - } - - private MInterval Left { - get { - MInterval i; - if (left != null) - for (i = left; i.right != null; i = i.right); - else - for (i = parent; i != null && i.total_start == 0; i = i.parent); - return i; - } - } - - private MInterval Right { - get { - MInterval i; - if (right != null) - for (i = right; i.left != null; i = i.left); - else - for (i = parent; i != null && i.total_start < 0; i = i.parent); - return i; - } - } - - public void Push (int start, int end, MTextProperty prop) - { - start <<= 2; - if (prop.FrontSticky) - start--; - else - start++; - end <<= 2; - if (prop.RearSticky) - end++; - else - end--; - if (start >= end) - throw new Exception ("Invalid Text Property Range"); - - push (start, end, prop); - } - - public void Insert (int pos, MInterval interval) - { - if (pos < Start) - Left.Insert (pos - total_start, interval); - else if (pos > End) - Right.Insert (pos - total_end, interval); - else + else if (end > to) { - // position: 0 1 2 3 - // index: -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 - // this |-----------<-----a----->-----| - // |-----b-----| |--c--| - // - // interval <--A-->-----------> - // <--B-->-----> - // <--C--> - // - // new |-----------<-a-A->-----------------------| - // |-----b-----| |-----------<--a-->-----| - // |-a-B->-----| |--c--| - // |-a-C-| - int len = interval.total_end - interval.total_start; - MInterval temp; - - total_end += len; - for (temp = this; temp.parent != null; - temp = temp.parent) - temp.parent.total_end += len; - temp = new MInterval (); - temp.stack = new Stack (stack); - - temp = divide_right (Start + 2); - temp.left = interval; - right = interval; - } - + if (start >= to) + return right.CopyTree (start, end); + right_copy = right.CopyTree (to, end); + } + this_copy = MInteval (key, end - start, stack); + this_copy.left = left_copy; + this_copy.right = right_copy; + return this_copy; } + // this-. ==> this-. + // right newright-. + // right private MInterval divide_right (int pos) { - MInterval interval = CopyNode (); - int this_start = Start; - int this_end = End; + MInterval interval; - if (left == null - || (right != null && left.total_end < - right.total_start)) - { - interval.left = this; - interval.right = right; - interval.parent = parent; - if (parent != null) - { - if (total_start == 0) - parent.left = interval; - else - parent.right = interval; - } - total_start = 0; - total_end = pos - this_start; - } - else + update_from_to (); + interval = new MInterval (key, to - pos, stack); + + total_length -= to - pos; + if (right != null) { - interval.total_start = pos - this_end; - interval.total_end = 0; - if (right != null) - right.parent = interval; - right = interval; + right->parent = interval; + interval.total_length += right->total_length; } - + interval->parent = this; + right = interval; return interval; } + // .-this ==> .-this + // left .-newleft + // left private MInterval divide_left (int pos) { MInterval interval = CopyNode (); @@ -650,36 +581,108 @@ namespace M17N.Core return interval; } - private void push (int start, int end, MTextProperty prop) + public void Insert (int pos, MInterval interval) { - int this_start = Start; - int this_end = End; + update_from_to (); + if (pos < from) + { + LeftNode.Insert (pos, interval); + return; + } + if (pos >= to) + { + RightNode.Insert (pos, interval); + return; + } + if (pos > from) + { + divide_right (pos).Insert (pos, interval); + return; + } - if (start < this_start) + // POS == FROM + if (left != null && LeftNode.stack.Count > 0) { - if (end <= this_start) + Stack s = new Stack (); + + foreach (MTextProperty p in LeftNode.stack) + if (p.RearSticky) + s.Push (p); + if (s.Count > 0) { - Left.push (start, end, prop); - return; + for (MInterval i = interval.LeftMost; + i != null && i.stack.Count == 0; + i = i.LeftNode) + foreach (MTextProperty p in s) + i.stack.Push (p); } - Left.push (start, this_start, prop); - start = this_start; } - if (this_end < end) + if (stack.Count > 0) { - if (this_end < start) + Stack s = new Stack (); + + foreach (MTextProperty p in stack) + if (p.FrontSticky) + s.Push (p); + if (s.Count > 0) { - Right.push (start, end, prop); - return; + for (MInterval i = interval.RightMostNode; + i != null && i.stack.Count == 0; + i = i.RightNode) + foreach (MTextProperty p in s) + i.stack.Push (p); } - Right.push (this_end, end, prop); - end = this_end; } - if (this_start < start) - divide_left (start); - if (end < this_end) + + // INTERVAL is ready to insert. + // + // .-this-. ==> .-this-. + // left-. left-. + // child interval + // child + + if (left) + { + MInterval i = left.RightMostNode; + + i.left = interval; + interval->parent = i; + for (; i != null; i = i.parent) + i.total_length += interval.total_length; + } + else + { + left = interval; + + for (MInterval i = this; i != null; i = i.parent) + i.total_length += interval.total_length; + } + } + + public MTextProperty Push (int start, int end, MTextProperty prop) + { + update_from_to (); + if (start < from) + { + left.Push (start, end, prop); + if (end <= from) + return prop; + start = from; + } + else if (end > to) + { + right.Push (start, end, prop); + if (start >= to) + return prop; + end = to; + } + + if (start > from) + divide_left (from); + if (end < to) divide_right (end); stack.Push (prop); + return prop; } } -- 1.7.10.4