From 7c46edd97138e0860a5b620f410e59f7a40a68ea Mon Sep 17 00:00:00 2001 From: handa Date: Thu, 26 Mar 2009 07:15:24 +0000 Subject: [PATCH] *** empty log message *** --- .cvsignore | 1 + MPlist.cs | 131 ++++++++++-------------- MSymbol.cs | 6 +- MText.cs | 324 +++++++++++++++++++++++++++++++++++++++++------------------- Makefile | 2 +- temp.cs | 10 +- 6 files changed, 286 insertions(+), 188 deletions(-) diff --git a/.cvsignore b/.cvsignore index b883f1f..c138f01 100644 --- a/.cvsignore +++ b/.cvsignore @@ -1 +1,2 @@ *.exe +*.dll diff --git a/MPlist.cs b/MPlist.cs index f54b47f..7c81701 100644 --- a/MPlist.cs +++ b/MPlist.cs @@ -4,127 +4,96 @@ using M17N.Core; namespace M17N.Core { - public struct MProperty - { - internal MSymbol key; - internal object val; - - public MSymbol Key { get { return this.key;} } - public object Val { get { return this.val; } } - - public MProperty (MSymbol key, object val) - { - this.key = key; - this.val = val; - } - } - public class MPlist : IEnumerable { - private MProperty prop; + public MSymbol Key; + public object Val; private MPlist next; public MPlist () { - prop = new MProperty (MSymbol.nil, null); + Key = MSymbol.nil; + Val = null; } - public bool tailp { get { return prop.key == MSymbol.nil; } } + private MPlist (MSymbol key, object val) + { + Key = key; + Val = val; + } + + public bool IsEmpty { get { return next == null; } } public new string ToString () { string str = ""; - for (MPlist p = this; ! p.tailp; p = p.next) + for (MPlist p = this; ! p.IsEmpty; p = p.next) { - str += (p == this ? "(" : " ") + p.prop.key.ToString () + ":"; - if (p.prop.val is MSymbol) - str += ((MSymbol) p.prop.val).ToString (); - else if (p.prop.val is MPlist) - str += ((MPlist) p.prop.val).ToString (); + str += (p == this ? "(" : " ") + p.Key.ToString () + ":"; + if (p.Val is MSymbol) + str += ((MSymbol) p.Val).ToString (); + else if (p.Val is MPlist) + str += ((MPlist) p.Val).ToString (); } return str + ")"; } + public MPlist find (MSymbol key) + { + MPlist p; + + for (p = this; ! p.IsEmpty; p = p.next) + if (p.Key == key) + break; + return p; + } + public object get (MSymbol key) { - if ((object) key == null) - return null; - for (MPlist p = this; ! p.tailp; p = p.next) - if (p.prop.key == key) - return p.prop.val; - return null; + return find (key).Val; } - public object put (MSymbol key, object val) + public MPlist put (MSymbol key, object val) { - MPlist p; + MPlist p = find (key); - for (p = this; ! p.tailp; p = p.next) - if (p.prop.key == key) - { - if (val != null) - p.prop.val = val; - else - p.pop (); - return val; - } - if (val != null) - { - p.prop.key = key; - p.prop.val = val; - p.next = new MPlist (); - } - return val; + if (p.IsEmpty) + return p.push (key, val); + p.Val = val; + return p; } - public object push (MSymbol key, object val) + public MPlist push (MSymbol key, object val) { - MPlist p = new MPlist (); + MPlist p = new MPlist (Key, Val); - p.prop.key = this.prop.key; - p.prop.val = this.prop.val; p.next = this.next; - this.prop.key = key; - this.prop.val = val; - this.next = p; - - return val; + Key = key; + Val = val; + next = p; + return this; } public object pop () { - if (tailp) + if (IsEmpty) return null; - object val = this.prop.val; + object val = Val; - this.prop.key = this.next.prop.key; - this.prop.val = this.next.prop.val; - this.next = this.next.next; + Key = next.Key; + Val = next.Val; + next = next.next; return val; } - public object add (MSymbol key, object val) + public MPlist add (MSymbol key, object val) { MPlist p; - for (p = this; ! p.tailp; p = p.next); - if (val != null) - { - p.prop.key = key; - p.prop.val = val; - p.next = new MPlist (); - } - 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; + for (p = this; ! p.IsEmpty; p = p.next); + return p.push (key, val); } // Implement IEnumerable interface. @@ -147,7 +116,7 @@ namespace M17N.Core public object Current { get { - if (current == null || current.tailp) + if (current == null || current.IsEmpty) throw new InvalidOperationException (); return current; } @@ -162,7 +131,7 @@ namespace M17N.Core { if (current == null) current = plist; - else if (current.tailp) + else if (current.IsEmpty) return false; else current = current.next; diff --git a/MSymbol.cs b/MSymbol.cs index bc67b1b..67fa7e9 100644 --- a/MSymbol.cs +++ b/MSymbol.cs @@ -8,7 +8,7 @@ namespace M17N.Core { static private Hashtable pool = new Hashtable (); - internal class MSymbolData + private class MSymbolData { public string name; public Object value; @@ -20,11 +20,11 @@ namespace M17N.Core } } + private MSymbolData data; + static public MSymbol nil = new MSymbol ("nil"); static public MSymbol t = new MSymbol ("t"); - private MSymbolData data; - public MSymbol (string name) { if (! pool.ContainsKey (name)) diff --git a/MText.cs b/MText.cs index 4561609..ff29503 100644 --- a/MText.cs +++ b/MText.cs @@ -20,19 +20,27 @@ namespace M17N.Core public class MTextProperty { - private MProperty prop; + internal MSymbol key; + internal object val; private bool front_sticky; private bool rear_sticky; - private MText mtext; - public MProperty Prop { get { return prop; } } + public MSymbol Key { get { return key; } } + public object Val { get { return val; } } public bool FrontSticky { get { return front_sticky; } } public bool RearSticky { get { return rear_sticky; } } - public MText Mtext { get { return mtext; } } - public MTextProperty (MProperty prop, bool front_sticky, bool rear_sticky) + public MTextProperty (MSymbol key, object val) { - this.prop = prop; + this.key = key; + this.val = val; + } + + public MTextProperty (MSymbol key, object val, + bool front_sticky, bool rear_sticky) + { + this.key = key; + this.val = val; this.front_sticky = front_sticky; this.rear_sticky = rear_sticky; } @@ -48,7 +56,7 @@ namespace M17N.Core private int cache_pos; private int cache_idx; private MPlist intervals; - private MProperty default_property; + private MPlist default_property; private bool read_only; private static UTF8Encoding utf8 = new UTF8Encoding (); @@ -76,24 +84,28 @@ namespace M17N.Core public MText () { sb = new StringBuilder (); + intervals = new MPlist (); } public MText (byte[] str) { sb = new StringBuilder (utf8.GetString (str)); nchars = count_chars (sb); + intervals = new MPlist (); } public MText (String str) { sb = new StringBuilder (str); nchars = count_chars (str); + intervals = new MPlist (); } public MText (StringBuilder str) { sb = str; nchars = count_chars (str); + intervals = new MPlist (); } public static MText operator+ (MText mt1, MText mt2) @@ -202,32 +214,19 @@ namespace M17N.Core sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx)); nchars += to - from; - if (mt2.intervals != null - && ! mt2.intervals.tailp) + 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) { - 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)); - } + MPlist p = mt2.intervals.find (plist.Key); + MInterval interval; - 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); + if (p.IsEmpty) + interval = new MInterval (plist.Key, to - from); + else + interval = ((MInterval) p.Val).copy (from, to); + ((MInterval) plist.Val).insert (pos, interval); } } @@ -281,28 +280,80 @@ namespace M17N.Core { sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from)); nchars -= to - from; + + foreach (MPlist plist in intervals) + ((MInterval) plist.Val).delete (from, to); return this; } - public void PushProp (int from, int to, MTextProperty prop) + public object get_prop (int pos, MSymbol key) { - MInterval root; + MInterval i = (MInterval) intervals.find (key).Val; + + if (i == null) + return null; + + MTextProperty prop = i.get (pos); + return (prop != null ? prop.Val : null); + } - if (intervals == null - || (root = intervals.find (prop.key)) ) - intervals = new MPlist (prop.key, new MInterval (prop.key, this)); + public object get_prop (int pos, MSymbol key, out MTextProperty prop) + { + MInterval i = (MInterval) intervals.find (key).Val; + + if (i == null) + return (prop = null); + prop = i.get (pos); + return (prop != null ? prop.Val : null); + } + + public object get_prop (int pos, MSymbol key, out MTextProperty[] array) + { + MInterval i = (MInterval) intervals.find (key).Val; + + if (i == null) + return (array = null); + MTextProperty prop = i.get (pos, out array); + return (prop != null ? prop.Val : null); + } + + public void push_prop (int from, int to, MSymbol key, object val) + { + push_prop (from, to, new MTextProperty (key, val)); + } + + public void push_prop (int from, int to, MTextProperty prop) + { + if (from < 0) + { + if (default_property == null) + default_property = new MPlist (); + default_property.push (prop.key, prop.val); + } + else + { + MInterval root = (MInterval) intervals.find (prop.key).Val; - root_interval.Push (from, to, prop); + if (root == null) + { + root = new MInterval (prop.key, this); + intervals.push (prop.key, root); + } + root.Push (from, to, prop); + } } private class MInterval { - // position: 0 1 2 3 - // | A | B | C | - // interval |<--------->|<--------->|<--------->| + // position: 0 1 2 3 4 5 6 7 + // | A | B | C | D | E F | G | + // interval |---|---|---|<->|-------|---| + // |---|<->|---| |<----->|---| + // |<->| |<->| |<->| // - // [3 (1 2)] - // [1 (0 1)] [1 (2 3)] + // [7 (3 4)] + // [3 (1 2)] [3 (4 6)] + // [1 (0 1)] [2 (2 3)] [1 (6 7)] private int total_length; private int from, to; private MSymbol key; @@ -319,25 +370,46 @@ namespace M17N.Core stack = new Stack (); } - private MInterval (MSymbol key, int length, Stack stack) + public MInterval (MSymbol key, MText mt) { this.key = key; - total_length = length; + mtext = mt; + total_length = mt.sb.Length; from = 0; to = total_length; - stack = new Stack (stack); + stack = new Stack (); } - public MInterval (MSymbol key, MText mt) + public MTextProperty get (int pos) + { + MInterval i = find (pos); + + return (i.stack.Count > 0 ? i.stack.Peek () : null); + } + + public MTextProperty get (int pos, out MTextProperty[] array) + { + MInterval i = find (pos); + + if (i.stack.Count == 0) + { + array = null; + return null; + } + array = i.stack.ToArray (); + return i.stack.Peek (); + } + + private MInterval (MSymbol key, int length, Stack stack) { this.key = key; - mtext = mt; - total_length = mt.sb.Length; + total_length = length; from = 0; to = total_length; - stack = new Stack (); + stack = new Stack (stack); } + private void update_from_to () { if (parent != null) @@ -411,7 +483,7 @@ namespace M17N.Core MInterval c1; if (parent == null) - mtext.root_intervals.put (key, right); + mtext.intervals.put (key, right); else if (parent.left == this) parent.left = right; else @@ -443,7 +515,7 @@ namespace M17N.Core MInterval c1; if (parent == null) - mtext.update_root_interval (key, left); + mtext.intervals.put (key, left); else if (parent.left == this) parent.left = left; else @@ -467,7 +539,7 @@ namespace M17N.Core private MInterval balance () { - MInteval i = this; + MInterval i = this; while (true) { @@ -496,27 +568,27 @@ namespace M17N.Core i.left.balance (); } } - return interval; + return i; } - public MInterval CopyTree (int start, int end) + public MInterval copy (int start, int end) { - MInterval this_copy, left_copy, right_copy; + MInterval this_copy, left_copy = null, right_copy = null; update_from_to (); if (start < from) { if (end <= from) - return left.CopyTree (start, end); - left_copy = left.CopyTree (start, from); + return left.copy (start, end); + left_copy = left.copy (start, from); } else if (end > to) { if (start >= to) - return right.CopyTree (start, end); - right_copy = right.CopyTree (to, end); + return right.copy (start, end); + right_copy = right.copy (to, end); } - this_copy = MInteval (key, end - start, stack); + this_copy = new MInterval (key, end - start, stack); this_copy.left = left_copy; this_copy.right = right_copy; @@ -528,18 +600,17 @@ namespace M17N.Core // right private MInterval divide_right (int pos) { - MInterval interval; - update_from_to (); - interval = new MInterval (key, to - pos, stack); + + MInterval interval = new MInterval (key, to - pos, stack); total_length -= to - pos; if (right != null) { - right->parent = interval; - interval.total_length += right->total_length; + right.parent = interval; + interval.total_length += right.total_length; } - interval->parent = this; + interval.parent = this; right = interval; return interval; } @@ -549,54 +620,37 @@ namespace M17N.Core // left private MInterval divide_left (int pos) { - MInterval interval = CopyNode (); - int this_start = Start; - int this_end = End; + update_from_to (); - if (left == null - || (right != null && left.total_end < - right.total_start)) - { - interval.total_start = 0; - interval.total_end = pos - this_start; - if (left != null) - left.parent = interval; - left = interval; - } - else + MInterval interval = new MInterval (key, to - pos, stack); + + total_length -= to - pos; + if (left != null) { - interval.right = this; - interval.left = left; - interval.parent = parent; - if (parent != null) - { - if (total_start == 0) - parent.left = interval; - else - parent.right = interval; - } - total_start = pos - this_end; - total_end = 0; + left.parent = interval; + interval.total_length += left.total_length; } - + interval.parent = this; + left = interval; return interval; } - public void Insert (int pos, MInterval interval) + public void insert (int pos, MInterval interval) { update_from_to (); if (pos < from) { - LeftNode.Insert (pos, interval); + LeftNode.insert (pos, interval); return; } if (pos >= to) { - RightNode.Insert (pos, interval); + RightNode.insert (pos, interval); return; } if (pos > from) { - divide_right (pos).Insert (pos, interval); + divide_right (pos).insert (pos, interval); return; } @@ -610,7 +664,7 @@ namespace M17N.Core s.Push (p); if (s.Count > 0) { - for (MInterval i = interval.LeftMost; + for (MInterval i = interval.LeftMostNode; i != null && i.stack.Count == 0; i = i.LeftNode) foreach (MTextProperty p in s) @@ -641,12 +695,12 @@ namespace M17N.Core // child interval // child - if (left) + if (left != null) { MInterval i = left.RightMostNode; i.left = interval; - interval->parent = i; + interval.parent = i; for (; i != null; i = i.parent) i.total_length += interval.total_length; } @@ -659,6 +713,78 @@ namespace M17N.Core } } + private void update_parent (MInterval i) + { + if (parent == null) + mtext.intervals.put (key, i); + else + { + int diff; + + if (parent.right == i) + { + diff = parent.right.total_length - i.total_length; + parent.right = i; + } + else + { + diff = parent.left.total_length - i.total_length; + parent.left = i; + } + for (i = parent; i != null; i = i.parent) + i.total_length += diff; + } + } + + public void delete (int start, int end) + { + update_from_to (); + if (start < from) + { + if (end <= from) + { + left.delete (start, end); + return; + } + left.delete (start, from); + start = from; + } + else if (end > to) + { + if (start >= to) + { + right.delete (start, end); + return; + } + right.delete (to, end); + end = to; + } + if (start == from && end == to) + { + if (left == null) + update_parent (right); + else if (right == null) + update_parent (left); + else + { + 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; + update_parent (right); + } + } + else + { + int len = end - start; + + for (MInterval i = this; i != null; i = i.parent) + i.total_length -= len; + } + } + public MTextProperty Push (int start, int end, MTextProperty prop) { update_from_to (); diff --git a/Makefile b/Makefile index 5a66d8a..93cc1ff 100644 --- a/Makefile +++ b/Makefile @@ -10,7 +10,7 @@ M17N.exe: M17N.cs M17NCore.dll $(CS) /r:M17NCore M17N.cs temp.exe: temp.cs M17NCore.dll - $(CS) /r:M17NCore temp.cs + $(CS) -codepage:65001 /r:M17NCore temp.cs clean: rm -f *.dll *.exe diff --git a/temp.cs b/temp.cs index 2dc7619..e212bf7 100644 --- a/temp.cs +++ b/temp.cs @@ -6,15 +6,17 @@ public class Test { public static void Main() { - MText mt = new MText ("a𝄀あc"); - MText mt2; + String str = "a𝄀あc"; + MText mt = new MText (str); - Console.WriteLine ("Length={0}", mt.Length); + Console.WriteLine ("{0}, Length={1}", mt, mt.Length); foreach (int c in mt) Console.WriteLine ("U+{0:X4}", c); Console.WriteLine (mt + new MText ("漢字")); - mt2 = mt.dup (); + + MText mt2 = mt.dup (); mt[1] = 'b'; + Console.WriteLine (mt); Console.WriteLine (mt2); } } -- 1.7.10.4