2 using System.Collections.Generic;
9 static MText mt = new MText ("012345678");
10 static MSymbol key = MSymbol.PropertyKey ("se",
11 MProperty.Flags.Sensitive);
12 static MSymbol val0 = MSymbol.Of ("0");
13 static MSymbol val1 = MSymbol.Of ("1");
14 static MSymbol val2 = MSymbol.Of ("2");
15 static MProperty prop0 = new MProperty (key, val0);
16 static MProperty prop1 = new MProperty (key, val1);
17 static MProperty prop2 = new MProperty (key, val2);
19 // Each property is identified by its beginning point.
20 // The character at position i has the property that begins at prop[i].
21 // If the character has no property, prop[i] == -1.
22 static int[] prop = new int[LENGTH];
24 // The property beginning at position i ends at position end[i].
25 // If no property begins at position i, end[i] is undefined.
26 static int[] end = new int[LENGTH];
28 // The property beginning at position i has value value[i].
29 // If no property begings at positoin i, value[i] is undefined.
30 static MSymbol[] value = new MSymbol[LENGTH];
32 static void TestPushProp (int from, int to, MProperty newprop)
34 Console.WriteLine ("from {0}, to {1}, push {2}.\n", from, to, newprop.Val);
38 if (from > 0 && prop[from - 1] == prop[from] && prop[from] != -1)
41 for (i = prop[from]; i < n; i++)
44 if (to < LENGTH && prop[to - 1] == prop[to] && prop[to] != -1)
47 for (i = to; i < n; i++)
50 for (i = from; i < to; i++)
53 value[from] = (MSymbol) newprop.Val;
55 mt.PushProp (from, to, newprop);
58 static void TestPopProp (int from, int to, MSymbol key)
60 Console.WriteLine ("from {0}, to {1}, pop.\n", from, to);
64 if (from > 0 && prop[from - 1] == prop[from] && prop[from] != -1)
65 for (i = prop[from]; i < from; i++)
68 if (to < LENGTH && prop[to - 1] == prop[to] && prop[to] != -1)
71 for (i = to; i < n; i++)
75 for (i = from; i < to; i++)
78 mt.PopProp (from, to, key);
81 static void TestDelIns (int from, int to, int from2)
83 Console.WriteLine ("from {0}, to {1}, moveto {2}.\n", from, to, from2);
85 int i, n, l = to - from;
86 int[] prop2 = new int[LENGTH], end2 = new int[LENGTH];
87 MSymbol[] value2 = new MSymbol[LENGTH];
89 // sensitivity for deletion
90 if (from > 0 && prop[from - 1] == prop[from] && prop[from] != -1)
93 for (i = prop[from]; i < n; i++)
97 if (to < LENGTH && prop[to - 1] == prop[to] && prop[to] != -1)
100 for (i = prop[to]; i < n; i++)
105 for (i = from; i < to; i++)
110 prop2[i - from] = prop[i] - from + from2;
111 end2[prop2[i - from]] = end[prop[i]] - from + from2;
112 value2[prop2[i - from]] = value[prop[i]];
114 prop2[i - from] = prop[i] - from + from2;
115 end2[i - from] = end[i] - from + from2;
116 value2[i - from] = value[i];
119 prop2[i - from] = -1;
123 for (i = to; i < LENGTH; i++)
127 prop[i - l] = prop[i] - l;
128 end[i - l] = end[i] - l;
129 value[i - l] = value[i];
134 prop[LENGTH - l] = -1;
136 // sensitivity for insertion
137 if (from2 > 0 && prop[from2 - 1] == prop[from2] && prop[from2] != -1)
139 n = end[prop[from2]];
140 for (i = prop[from2]; i < n; i++)
145 for (i = LENGTH - 1; i >= from2 + l; i--)
147 if (prop[i - l] != -1)
149 prop[i] = prop[i - l] + l;
150 end[i] = end[i - l] + l;
151 value[i] = value[i - l];
158 for (i = from2; i < from2 + l; i++)
160 if (prop2[i - from2] != -1)
163 prop[i] = prop2[i - from2];
164 end[prop[i]] = end2[prop2[i - from2]];
165 value[prop[i]] = value2[prop2[i - from2]];
167 prop[i] = prop2[i - from2];
168 end[i] = end2[i - from2];
169 value[i] = value2[i - from2];
175 MText mt2 = mt.Dup ();
177 mt.Ins (from2, mt2, from, to);
180 static bool Compare ()
182 for (int i = 0; i < LENGTH; i++)
184 object val = mt.GetProp (i, key);
186 if (prop[i] == -1 && (MSymbol) val != null)
188 Console.WriteLine ("value[{0}] is nil, GetProp returned {1}",
190 val == null ? MSymbol.nil : val);
194 if (prop[i] != -1 && (value[prop[i]] != (MSymbol) val))
196 Console.WriteLine ("value[{0}] is {1}, GetProp returned {2}",
198 value[prop[i]] == null ? MSymbol.nil : value[prop[i]],
199 val == null ? MSymbol.nil : val);
208 for (int i = 0; i <= LENGTH; i++)
209 Console.Write ("{0} ", i);
210 Console.WriteLine ("\n-------------------");
215 Console.Write ("{0} ", value[prop[0]]);
217 for (int i = 1; i < LENGTH; i++)
221 else if (prop[i - 1] == prop[i])
222 Console.Write ("< ");
224 Console.Write ("{0} ", value[prop[i]]);
226 Console.Write ("\n");
230 static void DebugDump (int n)
234 Console.Write ("\n#{0}\n ", n);
235 for (i = 0; i <= LENGTH; i++)
236 Console.Write ("{0} ", i);
237 Console.Write ("\n----------------------\nP ");
238 for (i = 0; i < LENGTH; i++)
241 Console.Write ("{0} ", prop[i]);
245 Console.Write ("\nE ");
247 Console.Write ("{0} ", end[0]);
250 for (i = 1; i < LENGTH; i++)
252 if (prop[i - 1] != prop[i] && prop[i] != -1)
253 Console.Write ("{0} ", end[i]);
257 Console.Write ("\nV ");
259 Console.Write ("{0} ", value[0]);
262 for (i = 1; i < LENGTH; i++)
264 if (prop[i - 1] != prop[i] && prop[i] != -1)
265 Console.Write ("{0} ", value[i]);
269 Console.Write ("\n");
273 public static void Main (string[] args)
275 Random r = new Random (int.Parse (args[0]));
276 int check = (args.Length > 1 ? int.Parse (args[1]) : 0xFFFFFFF);
278 for (int i = 0; i < LENGTH; i++)
281 for (int loop = 0; loop < 1000000; loop++)
285 Console.WriteLine ("--- loop = {0} ---\n", loop);
288 mt.DumpPropNested ();
294 from = r.Next (LENGTH);
295 to = r.Next (LENGTH) + 1;
296 } while (from == to);
321 TestPushProp (from, to, prop);
324 TestPopProp (from, to, key);
327 TestDelIns (from, to, r.Next (LENGTH - (to - from) + 1));
332 mt.DumpPropNested ();
334 if (Compare () == false)
336 Console.WriteLine ("");
338 Console.WriteLine ("Failed.");