2 /******************************************************************************
4 * DESCRIPTION: Commutation of modifications
5 * COPYRIGHT : (C) 2009 Joris van der Hoeven
6 *******************************************************************************
7 * This software falls under the GNU general public license version 3 or later.
8 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
9 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
10 ******************************************************************************/
14 /******************************************************************************
16 ******************************************************************************/
19 insert_length (tree t
) {
20 if (is_atomic (t
)) return N(t
->label
);
25 insert_range (tree t
, int i
, int len
) {
26 if (is_atomic (t
)) return t
->label (i
, i
+len
);
27 else return t (i
, i
+len
);
31 dup (modification m
) {
32 return modification (m
->k
, copy (m
->p
), m
->t
);
35 /******************************************************************************
36 * Inversion of modifications
37 ******************************************************************************/
40 invert (modification m
, tree t
) {
41 ASSERT (is_applicable (t
, m
), "modification not applicable");
45 return mod_assign (rp
, subtree (t
, rp
));
47 return mod_remove (rp
, index (m
), insert_length (m
->t
));
52 return mod_insert (rp
, i
, insert_range (subtree (t
, rp
), i
, n
));
55 return mod_join (rp
, index (m
));
59 return mod_split (rp
, i
, insert_length (subtree (t
, rp
* i
)));
62 return mod_assign_node (rp
, L (subtree (t
, rp
)));
64 return mod_remove_node (rp
, argument (m
));
67 tree u
= subtree (t
, rp
);
69 return mod_insert_node (rp
, i
, u (0, i
) * u (i
+1, N(u
)));
72 FAILED ("unexpected situation");
76 /******************************************************************************
77 * Commutation of modifications
78 ******************************************************************************/
81 swap1 (modification
& m1
, modification
& m2
, int i
, int d
) {
82 modification r1
= dup (m2
);
83 modification r2
= dup (m1
);
85 if (m2
->p
->item
!= i
|| !is_nil (root (m2
)) || m2
->k
!= MOD_INSERT
)
87 if (is_nil (root (m2
)))
92 int e2
= b2
+ insert_length (m2
->t
);
93 if (b2
<= i
) r2
->p
->item
+= (e2
-b2
);
99 int e2
= b2
+ m2
->p
->next
->item
;
100 if (b2
<= i
&& i
< e2
)
101 if (b2
!= i
|| m1
->k
!= MOD_REMOVE
)
103 if (b2
< i
) r2
->p
->item
-= (e2
-b2
);
107 if (m2
->p
->item
< i
) r2
->p
->item
++;
110 if (m2
->p
->item
== i
-1) return false;
111 if (m2
->p
->item
< i
) r2
->p
->item
--;
113 case MOD_INSERT_NODE
:
115 modification aux
= m2
;
116 m2
= modification (m1
->k
, path (m2
->p
->item
, m1
->p
), m1
->t
);
120 case MOD_REMOVE_NODE
:
129 swap2 (modification
& m1
, modification
& m2
, int i
, int d
) {
130 modification r1
= dup (m2
);
131 modification r2
= dup (m1
);
132 if (m1
->p
->item
>= i
) r2
->p
->item
+= d
;
139 swap_basic (modification
& m1
, modification
& m2
) {
140 modification aux
= m1
;
147 swap (modification
& m1
, modification
& m2
) {
154 if (m1
== m2
) return true;
155 if (!is_nil (rp2
) || m2
->k
!= MOD_INSERT_NODE
) return false;
156 modification aux
= m2
;
157 m2
= modification (m1
->k
, path (m2
->p
->item
, m1
->p
), m1
->t
);
163 if (is_nil (m2
->p
)) return false;
165 int e
= b
+ insert_length (m1
->t
);
166 if (m2
->p
->item
>= b
&& m2
->p
->item
< e
)
167 if (!is_nil (root (m2
)) || m2
->p
->item
!= b
|| m2
->k
!= MOD_INSERT
)
168 if (!is_nil (root (m2
)) || m2
->k
!= MOD_INSERT_NODE
)
170 return swap1 (m1
, m2
, b
, e
-b
);
174 if (is_nil (m2
->p
)) return false;
176 int d
= m1
->p
->next
->item
;
177 return swap1 (m1
, m2
, i
, -d
);
181 if (is_nil (m2
->p
)) return false;
183 if (m2
->p
->item
== i
|| m2
->p
->item
== i
+1)
184 if (!is_nil (root (m2
)) || m2
->p
->item
!= i
|| m2
->k
!= MOD_INSERT
)
185 if (!is_nil (root (m2
)) || m2
->k
!= MOD_INSERT_NODE
)
187 return swap1 (m1
, m2
, i
, 1);
191 if (is_nil (m2
->p
)) return false;
193 if (m2
->p
->item
== i
)
194 if (!is_nil (root (m2
)) || m2
->k
!= MOD_INSERT
)
196 return swap1 (m1
, m2
, i
, -1);
198 case MOD_ASSIGN_NODE
:
200 if (!is_nil (root (m2
))) return swap_basic (m1
, m2
);
201 if (m1
== m2
) return true;
202 if (!is_nil (rp2
) || m2
->k
!= MOD_INSERT_NODE
) return false;
203 modification aux
= m2
;
204 m2
= modification (m1
->k
, path (m2
->p
->item
, m1
->p
), m1
->t
);
208 case MOD_INSERT_NODE
:
210 if (is_nil (root (m2
))) return false;
211 if (m2
->p
->item
!= m1
->p
->item
) return false;
212 modification aux
= m1
;
213 m1
= modification (m2
->k
, m2
->p
->next
, m2
->t
);
214 if (m2
->k
!= MOD_INSERT_NODE
|| !is_nil (root (m1
))) m2
= aux
;
215 else m2
= modification (aux
->k
, path (m1
->p
->item
, aux
->p
), aux
->t
);
218 case MOD_REMOVE_NODE
:
220 modification aux
= m1
;
221 m1
= modification (m2
->k
, path (m1
->p
->item
, m2
->p
), m2
->t
);
226 else if (is_nil (rp2
))
233 int e
= b
+ insert_length (m2
->t
);
234 return swap2 (m1
, m2
, b
, e
-b
);
239 int e
= b
+ m2
->p
->next
->item
;
240 if (m1
->p
->item
>= b
&& m1
->p
->item
< e
) return false;
241 return swap2 (m1
, m2
, b
, b
-e
);
246 if (m1
->p
->item
== i
) return false;
247 return swap2 (m1
, m2
, i
, 1);
252 if (m1
->p
->item
== i
|| m1
->p
->item
== i
+1) return false;
253 return swap2 (m1
, m2
, i
, -1);
255 case MOD_ASSIGN_NODE
:
256 return swap_basic (m1
, m2
);
257 case MOD_INSERT_NODE
:
259 modification aux
= m2
;
260 m2
= modification (m1
->k
, path (m2
->p
->item
, m1
->p
), m1
->t
);
264 case MOD_REMOVE_NODE
:
266 if (m1
->p
->item
!= m2
->p
->item
) return false;
267 modification aux
= m2
;
268 m2
= modification (m1
->k
, m1
->p
->next
, m1
->t
);
273 else if (rp1
->item
== rp2
->item
) {
275 modification s1
= m1
/ h
;
276 modification s2
= m2
/ h
;
277 bool r
= swap (s1
, s2
);
282 else return swap_basic (m1
, m2
);
286 commute (modification m1
, modification m2
) {
289 return swap (s1
, s2
);
292 /******************************************************************************
293 * Joining simple modifications when possible
294 ******************************************************************************/
297 join (modification
& m1
, modification m2
, tree t
) {
298 if (m1
->k
== MOD_INSERT
&&
299 m2
->k
== MOD_INSERT
&&
301 root (m1
) == root (m2
) &&
302 (index (m2
) == index (m1
) ||
303 index (m2
) == index (m1
) + N (m1
->t
->label
)))
305 string s
= m1
->t
->label
* m2
->t
->label
;
306 if (index (m2
) == index (m1
))
307 s
= m2
->t
->label
* m1
->t
->label
;
308 m1
= mod_insert (root (m1
), index (m1
), tree (s
));
311 if (m1
->k
== MOD_REMOVE
&&
312 m2
->k
== MOD_REMOVE
&&
313 is_atomic (subtree (t
, root (m1
))) &&
314 root (m1
) == root (m2
) &&
315 (index (m1
) == index (m2
) ||
316 index (m1
) == index (m2
) + argument (m2
)))
318 m1
= mod_remove (root (m2
), index (m2
),
319 argument (m1
) + argument (m2
));
325 /******************************************************************************
327 ******************************************************************************/
332 test_modification (int i
) {
334 case 0: return mod_assign (path (), "Hi");
335 case 1: return mod_insert (path (), 0, tree (TUPLE
, "a", "b"));
336 case 2: return mod_remove (path (), 0, 2);
337 case 3: return mod_split (path (), 0, 1);
338 case 4: return mod_join (path (), 0);
339 case 5: return mod_assign_node (path (), TUPLE
);
340 case 6: return mod_insert_node (path (), 1, tree (TUPLE
, "a", "b"));
341 case 7: return mod_remove_node (path (), 0);
343 case 8: return mod_insert (path (), 1, tree (TUPLE
, "a", "b"));
344 case 9: return mod_insert (path (), 2, tree (TUPLE
, "a", "b"));
345 case 10: return mod_remove (path (), 1, 2);
346 case 11: return mod_remove (path (), 2, 2);
347 case 12: return mod_split (path (), 1, 2);
348 case 13: return mod_split (path (), 2, 1);
349 case 14: return mod_join (path (), 1);
350 case 15: return mod_join (path (), 2);
351 case 16: return mod_remove_node (path (), 1);
352 case 17: return mod_remove_node (path (), 2);
354 case 18: case 19: case 20: case 21: case 22: case 23: case 24: case 25:
355 return path (0) * test_modification (i
-18);
356 case 26: case 27: case 28: case 29: case 30: case 31: case 32: case 33:
357 return path (1) * test_modification (i
-26);
358 case 34: case 35: case 36: case 37: case 38: case 39: case 40: case 41:
359 return path (2) * test_modification (i
-34);
361 FAILED ("not implemented");
362 return mod_assign (path (), "");
367 test_tree (int i
= 0, int d
= 3) {
368 // cout << "i= " << i << ", d= " << d << "\n";
369 if (d
== 0) return tree (as_string (i
));
371 int n
= 6 + ((int) (2 * sin (1.0 * i
* d
)));
373 for (int j
=0; j
<n
; i
++, j
++)
374 t
[j
]= test_tree (i
, d
-1);
381 tree tt
= test_tree ();
382 for (int i
=0; i
<42; i
++)
383 for (int j
=0; j
<42; j
++) {
384 modification m1
= test_modification (i
);
385 modification m2
= test_modification (j
);
388 cout
<< "m1 = " << m1
<< "\n";
389 cout
<< "m2 = " << m2
<< "\n";
390 bool r
= swap (m1
, m2
);
393 if (!r
) cout
<< " Modifications do not commute\n\n";
395 cout
<< "m1' = " << m1
<< "\n";
396 cout
<< "m2' = " << m2
<< "\n";
397 if (clean_apply (clean_apply (tt
, t1
), t2
) !=
398 clean_apply (clean_apply (tt
, m1
), m2
)) {
399 cout
<< "t1 = " << clean_apply (clean_apply (tt
, t1
), t2
) << "\n";
400 cout
<< "t2 = " << clean_apply (clean_apply (tt
, m1
), m2
) << "\n";
401 FAILED ("inconsistency");
404 if (!r
) cout
<< "r = " << r
<< "\n";
405 else if (m1
!= t1
|| m2
!= t2
) {
406 cout
<< "m1''= " << m1
<< "\n";
407 cout
<< "m2''= " << m2
<< "\n";
409 if (!r
) cout
<< "r = " << r
<< "\n";
410 else if (m1
!= u1
|| m2
!= u2
) {
411 cout
<< "m1* = " << m1
<< "\n";
412 cout
<< "m2* = " << m2
<< "\n";
416 if (r
) cout
<< " Consistency check succeeded\n\n";
418 cout
<< " Consistency check failed\n\n";
419 FAILED ("inconsistency");
427 tree t1
= test_tree ();
428 for (int i
=0; i
<42; i
++) {
429 modification m1
= test_modification (i
);
430 tree t2
= clean_apply (t1
, m1
);
431 modification m2
= invert (m1
, t1
);
432 tree t3
= clean_apply (t2
, m2
);
433 modification m3
= invert (m2
, t2
);
434 if (m1
!= m3
|| t1
!= t3
) {
435 cout
<< "t1= " << t1
<< "\n";
436 cout
<< "m1= " << m1
<< "\n";
437 cout
<< "t2= " << t2
<< "\n";
438 cout
<< "m2= " << m2
<< "\n";
439 cout
<< "t3= " << t3
<< "\n";
440 FAILED ("inconsistency");