From dd6002fc07fb3af22932c88854ca676eba122658 Mon Sep 17 00:00:00 2001 From: ntakahas Date: Wed, 1 Jul 2009 09:07:31 +0000 Subject: [PATCH] *** empty log message *** --- frontsensitive.cs | 91 ++++-------------- rearsensitive.cs | 278 ++++++++++++++++++++++++++++++++++++++++------------- sensitive.cs | 18 +++- 3 files changed, 242 insertions(+), 145 deletions(-) diff --git a/frontsensitive.cs b/frontsensitive.cs index 42fe6b1..b9fd103 100644 --- a/frontsensitive.cs +++ b/frontsensitive.cs @@ -29,6 +29,10 @@ public class Test // If no property begings at positoin i, value[i] is undefined. static MSymbol[] value = new MSymbol[LENGTH]; + // Cut buffers + static int[] subprop = new int[LENGTH], subend = new int[LENGTH]; + static MSymbol[] subvalue = new MSymbol[LENGTH]; + static void TestPushProp (int from, int to, MProperty newprop) { Console.WriteLine ("from {0}, to {1}, push {2}.\n", from, to, newprop.Val); @@ -61,7 +65,6 @@ public class Test int i, n; - Console.WriteLine ("prop[from] = {0}", prop[from]); if (from > 0 && prop[from - 1] == prop[from] && prop[from] != -1) for (i = prop[from]; i < from; i++) prop[i] = -1; @@ -84,10 +87,7 @@ public class Test Console.WriteLine ("from {0}, to {1}, moveto {2}.\n", from, to, from2); int i, n, l = to - from; - int[] prop2 = new int[LENGTH], end2 = new int[LENGTH]; - MSymbol[] value2 = new MSymbol[LENGTH]; - DebugDump (0); // sensitivity for deletion if (from > 0 && prop[from] != -1) { @@ -103,36 +103,33 @@ public class Test prop[i] = -1; } - DebugDump (1); // copy for (i = from; i < to; i++) { if (prop[i] != -1) { - prop2[i - from] = prop[i] - from + from2; - end2[prop2[i - from]] = end[prop[i]] - from + from2; - value2[prop2[i - from]] = value[prop[i]]; + subprop[i - from] = prop[i] - from + from2; + subend[i - from] = end[i] - from + from2; + subvalue[i - from] = value[i]; } else - prop2[i - from] = -1; + subprop[i - from] = -1; } - DebugDump (2); // delete for (i = to; i < LENGTH; i++) { if (prop[i] != -1) { prop[i - l] = prop[i] - l; - end[prop[i - l]] = end[prop[i]] - l; - value[prop[i - l]] = value[prop[i]]; + end[i - l] = end[i] - l; + value[i - l] = value[i]; } else prop[i - l] = -1; } prop[LENGTH - l] = -1; - DebugDump (3); // sensitivity for insertion if (prop[from2] != -1) { @@ -144,41 +141,35 @@ public class Test for (; i < n; i++) prop[i] = -1; } - if (from2 > 0 && prop2[0] != -1) - { - n = prop2[0]; - for (i = 0; i < n; i++) - prop2[i] = -1; - } + if (from2 > 0 && subprop[0] != -1) + for (i = 0; i < subend[0] - from2; i++) + subprop[i] = -1; - DebugDump (4); // move for (i = LENGTH - 1; i >= from2 + l; i--) { if (prop[i - l] != -1) { prop[i] = prop[i - l] + l; - end[prop[i]] = end[prop[i - l]] + l; - value[prop[i]] = value[prop[i - l]]; + end[i] = end[i - l] + l; + value[i] = value[i - l]; } else prop[i] = -1; } - DebugDump (5); // insert for (i = from2; i < from2 + l; i++) { - if (prop2[i - from2] != -1) + if (subprop[i - from2] != -1) { - prop[i] = prop2[i - from2]; - end[prop[i]] = end2[prop2[i - from2]]; - value[prop[i]] = value2[prop2[i - from2]]; + prop[i] = subprop[i - from2]; + end[i] = subend[i - from2]; + value[i] = subvalue[i - from2]; } else prop[i] = -1; } - DebugDump (6); MText mt2 = mt.Dup (); mt.Del (from, to); @@ -234,50 +225,6 @@ public class Test Console.Write ("\n"); } - static void DebugDump (int n) - { - /* - int i; - - Console.Write ("\n#{0}\n ", n); - for (i = 0; i <= LENGTH; i++) - Console.Write ("{0} ", i); - Console.Write ("\n----------------------\nP "); - for (i = 0; i < LENGTH; i++) - { - if (prop[i] != -1) - Console.Write ("{0} ", prop[i]); - else - Console.Write (" "); - } - Console.Write ("\nE "); - if (prop[0] != -1) - Console.Write ("{0} ", end[0]); - else - Console.Write (" "); - for (i = 1; i < LENGTH; i++) - { - if (prop[i - 1] != prop[i] && prop[i] != -1) - Console.Write ("{0} ", end[i]); - else - Console.Write (" "); - } - Console.Write ("\nV "); - if (prop[0] != -1) - Console.Write ("{0} ", value[0]); - else - Console.Write (" "); - for (i = 1; i < LENGTH; i++) - { - if (prop[i - 1] != prop[i] && prop[i] != -1) - Console.Write ("{0} ", value[i]); - else - Console.Write (" "); - } - Console.Write ("\n"); - */ - } - public static void Main (string[] args) { Random r = new Random (int.Parse (args[0])); diff --git a/rearsensitive.cs b/rearsensitive.cs index 2848e08..b9554f7 100644 --- a/rearsensitive.cs +++ b/rearsensitive.cs @@ -5,9 +5,8 @@ using M17N.Core; public class Test { - const int LENGTH = 10; - const int DEPTH = 10; - static MText mt = new MText ("0123456789"); + const int LENGTH = 9; + static MText mt = new MText ("012345678"); static MSymbol key = MSymbol.PropertyKey ("rse", MProperty.Flags.RearSensitive); static MSymbol val0 = MSymbol.Of ("0"); @@ -17,111 +16,182 @@ public class Test static MProperty prop1 = new MProperty (key, val1); static MProperty prop2 = new MProperty (key, val2); - static MSymbol[] valtable = new MSymbol[LENGTH]; + // Each property is identified by its beginning point. + // The character at position i has the property that begins at prop[i]. + // If the character has no property, prop[i] == -1. + static int[] prop = new int[LENGTH]; - static void TestPushProp (int from, int to, MProperty prop) + // The property beginning at position i ends at position end[i]. + // If no property begins at position i, end[i] is undefined. + static int[] end = new int[LENGTH]; + + // The property beginning at position i has value value[i]. + // If no property begings at positoin i, value[i] is undefined. + static MSymbol[] value = new MSymbol[LENGTH]; + + static void TestPushProp (int from, int to, MProperty newprop) { - int i; - MSymbol sym; + Console.WriteLine ("from {0}, to {1}, push {2}.\n", from, to, newprop.Val); - if (from > 0 && valtable[from] != null) + int i, n; + + if (from > 0 && prop[from - 1] == prop[from] && prop[from] != -1) { - sym = valtable[from]; - for (i = from - 1; i >= 0 && valtable[i] == sym; i--) - valtable[i] = null; + n = end[prop[from]]; + for (i = prop[from]; i < n; i++) + prop[i] = -1; } - if (to < LENGTH && valtable[to - 1] != null) + if (to < LENGTH && prop[to - 1] == prop[to] && prop[to] != -1) { - sym = valtable[to - 1]; - for (i = to; i < LENGTH && valtable[i] == sym; i++) - valtable[i] = null; + n = end[prop[to]]; + for (i = to; i < n; i++) + prop[i] = -1; } for (i = from; i < to; i++) - valtable[i] = (MSymbol) prop.Val; - Console.WriteLine ("from {0}, to {1}, push {2}.\n", from, to, prop.Val); + prop[i] = from; + end[from] = to; + value[from] = (MSymbol) newprop.Val; - mt.PushProp (from, to, prop); + mt.PushProp (from, to, newprop); } static void TestPopProp (int from, int to, MSymbol key) { - int i; - MSymbol sym; + Console.WriteLine ("from {0}, to {1}, pop.\n", from, to); - if (from > 0 && valtable[from] != null) - { - sym = valtable[from]; - for (i = from - 1; i >= 0 && valtable[i] == sym; i--) - valtable[i] = null; - } - if (to < LENGTH && valtable[to - 1] != null) + int i, n; + + if (from > 0 && prop[from - 1] == prop[from] && prop[from] != -1) + for (i = prop[from]; i < from; i++) + prop[i] = -1; + + if (to < LENGTH && prop[to - 1] == prop[to] && prop[to] != -1) { - sym = valtable[to - 1]; - for (i = to; i < LENGTH && valtable[i] == sym; i++) - valtable[i] = null; + n = end[prop[to]]; + for (i = to; i < n; i++) + prop[i] = -1; } + for (i = from; i < to; i++) - valtable[i] = null; - Console.WriteLine ("from {0}, to {1}, pop.\n", from, to); + prop[i] = -1; mt.PopProp (from, to, key); } static void TestDelIns (int from, int to, int from2) { - int i, l = to - from; - MSymbol[] valtable2 = new MSymbol[LENGTH]; - MSymbol sym; + Console.WriteLine ("from {0}, to {1}, moveto {2}.\n", from, to, from2); + + int i, j, n, l = to - from; + int[] prop2 = new int[LENGTH], end2 = new int[LENGTH]; + MSymbol[] value2 = new MSymbol[LENGTH]; // sensitivity for deletion - if (from > 0 && valtable[from - 1] != null) + if (from > 0 && prop[from - 1] != -1) { - sym = valtable[from - 1]; - for (i = from - 1; i >= 0 && valtable[i] == sym; i--) - valtable[i] = null; - for (i = from; i < LENGTH && valtable[i] == sym; i++) - valtable[i] = null; + n = prop[from - 1] == prop[from] ? end[prop[from]] : from; + for (i = prop[from - 1]; i < n; i++) + prop[i] = -1; } - if (to < LENGTH && valtable[to - 1] != null) + + if (to < LENGTH && prop[to - 1] != -1) { - sym = valtable[to - 1]; - for (i = to - 1; i >= 0 && valtable[i] == sym; i--) - valtable[i] = null; - for (i = to; i < LENGTH && valtable[i] == sym; i++) - valtable[i] = null; + n = prop[to - 1] == prop[to] ? end[prop[to]] : to; + for (i = prop[to - 1]; i < n; i++) + prop[i] = -1; } // copy - for (i = from; i < to; i++) - valtable2[i - from] = valtable[i]; + for (i = from, j = from2; i < to; i++, j++) + { + if (prop[i] != -1) + { + prop2[j] = prop[i] - from + from2; + end2[j] = end[i] - from + from2; + value2[j] = value[i]; + } + else + prop2[j] = -1; + } + + /* + Console.Write ("\n "); + for (j = from2; j < from2 + l; j++) + Console.Write ("{0} ", j); + Console.Write ("\n--------------------\nP "); + for (j = from2; j < from2 + l; j++) + { + if (prop2[j] != -1) + Console.Write ("{0} ", prop2[j]); + else + Console.Write (" "); + } + Console.Write ("\nE "); + for (j = from2; j < from2 + l; j++) + { + if (prop2[j] != -1) + Console.Write ("{0} ", end2[j]); + else + Console.Write (" "); + } + Console.Write ("\nV "); + for (j = from2; j < from2 + l; j++) + { + if (prop2[j] != -1) + Console.Write ("{0} ", value2[j]); + else + Console.Write (" "); + } + Console.Write ("\n"); + */ // delete for (i = to; i < LENGTH; i++) - valtable[i - l] = valtable[i]; - valtable[LENGTH - l] = null; - - // sensitivity for insertion - if (from2 > 0 && valtable[from2 - 1] != null) { - sym = valtable[from2 - 1]; - for (i = from2 - 1; i >= 0 && valtable[i] == sym; i--) - valtable[i] = null; + if (prop[i] != -1) + { + prop[i - l] = prop[i] - l; + end[i - l] = end[i] - l; + value[i - l] = value[i]; + } + else + prop[i - l] = -1; } - if ((to < LENGTH || from2 + l < LENGTH) && valtable2[l - 1] != null) + + // sensitivity for insertion + if (from2 > 0 && prop[from2 - 1] != -1) { - sym = valtable2[l - 1]; - for (i = l - 1; i >= 0; i--) - valtable2[i] = null; + n = prop[from2 - 1] == prop[from2] ? end[prop[from2]] : from2; + for (i = prop[from2 - 1]; i < n; i++) + prop[i] = -1; } + if (from2 + l < LENGTH && prop2[from2 + l - 1] != -1) + for (i = prop2[from2 + l -1]; i < from2 + l; i++) + prop2[i] = -1; // move for (i = LENGTH - 1; i >= from2 + l; i--) - valtable[i] = valtable[i - l]; + { + if (prop[i - l] != -1) + { + prop[i] = prop[i - l] + l; + end[i] = end[i - l] + l; + value[i] = value[i - l]; + } + else + prop[i] = -1; + } // insert for (i = from2; i < from2 + l; i++) - valtable[i] = valtable2[i - from2]; - Console.WriteLine ("from {0}, to {1}, moveto {2}.\n", from, to, from2); + { + prop[i] = prop2[i]; + if (prop2[i] != -1) + { + end[i] = end2[i]; + value[i] = value2[i]; + } + } MText mt2 = mt.Dup (); mt.Del (from, to); @@ -134,11 +204,19 @@ public class Test { object val = mt.GetProp (i, key); - if (valtable[i] != (MSymbol) val) + if (prop[i] == -1 && (MSymbol) val != null) { - Console.WriteLine ("valtable[{0}] is {1}, GetProp returned {2}", + Console.WriteLine ("value[{0}] is nil, GetProp returned {1}", i, - valtable[i] == null ? MSymbol.nil : valtable[i], + val == null ? MSymbol.nil : val); + return false; + } + + if (prop[i] != -1 && (value[prop[i]] != (MSymbol) val)) + { + Console.WriteLine ("value[{0}] is {1}, GetProp returned {2}", + i, + value[prop[i]] == null ? MSymbol.nil : value[prop[i]], val == null ? MSymbol.nil : val); return false; } @@ -148,8 +226,67 @@ public class Test static void Dump () { - for (int i = 0; i < LENGTH; i++) - Console.WriteLine ("{0} {1} :", i, valtable[i]); + for (int i = 0; i <= LENGTH; i++) + Console.Write ("{0} ", i); + Console.WriteLine ("\n-------------------"); + + if (prop[0] == -1) + Console.Write (" "); + else + Console.Write ("{0} ", value[prop[0]]); + + for (int i = 1; i < LENGTH; i++) + { + if (prop[i] == -1) + Console.Write (" "); + else if (prop[i - 1] == prop[i]) + Console.Write ("< "); + else + Console.Write ("{0} ", value[prop[i]]); + } + Console.Write ("\n"); + } + + static void DebugDump (int n) + { + int i; + + Console.Write ("\n#{0}\n ", n); + for (i = 0; i <= LENGTH; i++) + Console.Write ("{0} ", i); + Console.Write ("\n----------------------\nP "); + for (i = 0; i < LENGTH; i++) + { + if (prop[i] != -1) + Console.Write ("{0} ", prop[i]); + else + Console.Write (" "); + } + Console.Write ("\nE "); + if (prop[0] != -1) + Console.Write ("{0} ", end[0]); + else + Console.Write (" "); + for (i = 1; i < LENGTH; i++) + { + if (prop[i - 1] != prop[i] && prop[i] != -1) + Console.Write ("{0} ", end[i]); + else + Console.Write (" "); + } + Console.Write ("\nV "); + if (prop[0] != -1) + Console.Write ("{0} ", value[0]); + else + Console.Write (" "); + for (i = 1; i < LENGTH; i++) + { + if (prop[i - 1] != prop[i] && prop[i] != -1) + Console.Write ("{0} ", value[i]); + else + Console.Write (" "); + } + Console.Write ("\n"); } public static void Main (string[] args) @@ -157,6 +294,9 @@ public class Test Random r = new Random (int.Parse (args[0])); int check = (args.Length > 1 ? int.Parse (args[1]) : 0xFFFFFFF); + for (int i = 0; i < LENGTH; i++) + prop[i] = -1; + for (int loop = 0; loop < 1000000; loop++) { int from, to; diff --git a/sensitive.cs b/sensitive.cs index 55d0d96..28788d0 100644 --- a/sensitive.cs +++ b/sensitive.cs @@ -106,9 +106,14 @@ public class Test { if (prop[i] != -1) { + /* prop2[i - from] = prop[i] - from + from2; end2[prop2[i - from]] = end[prop[i]] - from + from2; value2[prop2[i - from]] = value[prop[i]]; + */ + prop2[i - from] = prop[i] - from + from2; + end2[i - from] = end[i] - from + from2; + value2[i - from] = value[i]; } else prop2[i - from] = -1; @@ -120,8 +125,8 @@ public class Test if (prop[i] != -1) { prop[i - l] = prop[i] - l; - end[prop[i - l]] = end[prop[i]] - l; - value[prop[i - l]] = value[prop[i]]; + end[i - l] = end[i] - l; + value[i - l] = value[i]; } else prop[i - l] = -1; @@ -142,8 +147,8 @@ public class Test if (prop[i - l] != -1) { prop[i] = prop[i - l] + l; - end[prop[i]] = end[prop[i - l]] + l; - value[prop[i]] = value[prop[i - l]]; + end[i] = end[i - l] + l; + value[i] = value[i - l]; } else prop[i] = -1; @@ -154,9 +159,14 @@ public class Test { if (prop2[i - from2] != -1) { + /* prop[i] = prop2[i - from2]; end[prop[i]] = end2[prop2[i - from2]]; value[prop[i]] = value2[prop2[i - from2]]; + */ + prop[i] = prop2[i - from2]; + end[i] = end2[i - from2]; + value[i] = value2[i - from2]; } else prop[i] = -1; -- 1.7.10.4