Back to index

texmacs  1.0.7.15
modification.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : modification.hpp
00004 * DESCRIPTION: elementary tree modifications
00005 * COPYRIGHT  : (C) 2008  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #include "modification.hpp"
00013 
00014 /******************************************************************************
00015 * Equality and Output
00016 ******************************************************************************/
00017 
00018 bool
00019 operator == (modification m1, modification m2) {
00020   return m1->k == m2->k && m1->p == m2->p && m1->t == m2->t;
00021 }
00022 
00023 bool
00024 operator != (modification m1, modification m2) {
00025   return m1->k != m2->k || m1->p != m2->p || m1->t != m2->t;
00026 }
00027 
00028 tm_ostream&
00029 operator << (tm_ostream& out, modification mod) {
00030   switch (mod->k) {
00031   case MOD_ASSIGN:
00032     return out << "assign (" << root (mod)
00033               << ", " << mod->t << ")";
00034   case MOD_INSERT:
00035     return out << "insert (" << root (mod)
00036               << ", " << index (mod) << ", " << mod->t << ")";
00037   case MOD_REMOVE:
00038     return out << "remove (" << root (mod)
00039               << ", " << index (mod) << ", " << argument (mod) << ")";
00040   case MOD_SPLIT:
00041     return out << "split (" << root (mod)
00042               << ", " << index (mod) << ", " << argument (mod) << ")";
00043   case MOD_JOIN:
00044     return out << "join (" << root (mod)
00045               << ", " << index (mod) << ")";
00046   case MOD_ASSIGN_NODE:
00047     return out << "assign_node (" << root (mod)
00048               << ", " << mod->t << ")";
00049   case MOD_INSERT_NODE:
00050     return out << "insert_node (" << root (mod)
00051               << ", " << argument (mod) << ", " << mod->t << ")";
00052   case MOD_REMOVE_NODE:
00053     return out << "remove_node (" << root (mod)
00054               << ", " << index (mod) << ")";
00055   case MOD_SET_CURSOR:
00056     return out << "set_cursor (" << root (mod)
00057               << ", " << index (mod) << ", " << mod->t << ")";
00058   default: FAILED ("invalid modification type");
00059     return out;
00060   }
00061 }
00062 
00063 /******************************************************************************
00064 * Accessors
00065 ******************************************************************************/
00066 
00067 path
00068 root (modification mod) {
00069   switch (mod->k) {
00070   case MOD_ASSIGN: return mod->p;
00071   case MOD_INSERT: return path_up (mod->p);
00072   case MOD_REMOVE: return path_up (path_up (mod->p));
00073   case MOD_SPLIT: return path_up (path_up (mod->p));
00074   case MOD_JOIN: return path_up (mod->p);
00075   case MOD_ASSIGN_NODE: return mod->p;
00076   case MOD_INSERT_NODE: return path_up (mod->p);
00077   case MOD_REMOVE_NODE: return path_up (mod->p);
00078   case MOD_SET_CURSOR: return path_up (mod->p);
00079   default: FAILED ("invalid modification type");
00080   }
00081 }
00082 
00083 int
00084 index (modification mod) {
00085   switch (mod->k) {
00086   case MOD_INSERT: return last_item (mod->p);
00087   case MOD_REMOVE: return last_item (path_up (mod->p));
00088   case MOD_SPLIT: return last_item (path_up (mod->p));
00089   case MOD_JOIN: return last_item (mod->p);
00090   case MOD_REMOVE_NODE: return last_item (mod->p);
00091   case MOD_SET_CURSOR: return last_item (mod->p);
00092   default: FAILED ("invalid modification type");
00093   }
00094 }
00095 
00096 int
00097 argument (modification mod) {
00098   switch (mod->k) {
00099   case MOD_REMOVE: return last_item (mod->p);
00100   case MOD_SPLIT: return last_item (mod->p);
00101   case MOD_INSERT_NODE: return last_item (mod->p);
00102   default: FAILED ("invalid modification type");
00103   }
00104 }
00105 
00106 tree_label
00107 L (modification mod) {
00108   ASSERT (mod->k == MOD_ASSIGN_NODE, "assign_node modification expected");
00109   return L (mod->t);
00110 }
00111 
00112 /******************************************************************************
00113 * Test applicability of modifications
00114 ******************************************************************************/
00115 
00116 bool
00117 can_assign (tree t, path p, tree u) {
00118   (void) u;
00119   return has_subtree (t, p);
00120 }
00121 
00122 bool
00123 can_insert (tree t, path p, int pos, tree u) {
00124   if (!has_subtree (t, p)) return false;
00125   tree st= subtree (t, p);
00126   if (is_atomic (st)) return pos >= 0 && pos <= N(st->label) && is_atomic (u);
00127   else return pos >= 0 && pos <= N(st) && is_compound (u);
00128 }
00129 
00130 bool
00131 can_remove (tree t, path p, int pos, int nr) {
00132   if (!has_subtree (t, p)) return false;
00133   tree st= subtree (t, p);
00134   if (is_atomic (st)) return pos >= 0 && pos+nr <= N(st->label);
00135   else return pos >= 0 && pos+nr <= N(st);
00136 }
00137 
00138 bool
00139 can_split (tree t, path p, int pos, int at) {
00140   if (!has_subtree (t, p * pos)) return false;
00141   tree st= subtree (t, p * pos);
00142   if (is_atomic (st)) return at >= 0 && at <= N(st->label);
00143   else return at >= 0 && at <= N(st);
00144 }
00145 
00146 bool
00147 can_join (tree t, path p, int pos) {
00148   if (!has_subtree (t, p)) return false;
00149   tree st= subtree (t, p);
00150   if (pos < 0 || pos+1 >= N(st)) return false;
00151   if (is_atomic (st[pos]) && is_atomic (st[pos+1])) return true;
00152   if (is_compound (st[pos]) && is_compound (st[pos+1])) return true;
00153   return false;
00154 }
00155 
00156 bool
00157 can_assign_node (tree t, path p, tree_label op) {
00158   (void) op;
00159   return has_subtree (t, p) && is_compound (subtree (t, p));
00160 }
00161 
00162 bool
00163 can_insert_node (tree t, path p, int pos, tree u) {
00164   return has_subtree (t, p) && is_compound (u) && pos >= 0 && pos <= N(u);
00165 }
00166 
00167 bool
00168 can_remove_node (tree t, path p, int pos) {
00169   return has_subtree (t, p * pos);
00170 }
00171 
00172 bool
00173 can_set_cursor (tree t, path p, int pos, tree data) {
00174   (void) data;
00175   if (!has_subtree (t, p)) return false;
00176   return pos >= 0 && pos <= right_index (subtree (t, p));
00177 }
00178 
00179 bool
00180 is_applicable (tree t, modification mod) {
00181   switch (mod->k) {
00182   case MOD_ASSIGN:
00183     return can_assign (t, root (mod), mod->t);
00184   case MOD_INSERT:
00185     return can_insert (t, root (mod), index (mod), mod->t);
00186   case MOD_REMOVE:
00187     return can_remove (t, root (mod), index (mod), argument (mod));
00188   case MOD_SPLIT:
00189     return can_split (t, root (mod), index (mod), argument (mod));
00190   case MOD_JOIN:
00191     return can_join (t, root (mod), index (mod));
00192   case MOD_ASSIGN_NODE:
00193     return can_assign_node (t, root (mod), L (mod));
00194   case MOD_INSERT_NODE:
00195     return can_insert_node (t, root (mod), argument (mod), mod->t);
00196   case MOD_REMOVE_NODE:
00197     return can_remove_node (t, root (mod), index (mod));
00198   case MOD_SET_CURSOR:
00199     return can_set_cursor (t, root (mod), index (mod), mod->t);
00200   default:
00201     return false;
00202   }
00203 }
00204 
00205 /******************************************************************************
00206 * Functional application of modifications
00207 ******************************************************************************/
00208 
00209 tree
00210 clean_assign (tree t, path p, tree u) {
00211   if (is_nil (p)) return copy (u);
00212   else {
00213     int i, j= p->item, n= N(t);
00214     if (j >= n) FAILED("clean_remove(): Invalid path."); //return copy(u);  // FIXME? check whether this is the right return value.
00215     tree r (t, n);
00216     for (i=0; i<j; i++) r[i]= t[i];
00217     r[j]= clean_assign (t[j], p->next, u);
00218     for (i++; i<n; i++) r[i]= t[i];
00219     return r;
00220   }
00221 }
00222 
00223 tree
00224 clean_insert (tree t, path p, tree u) {
00225   if (is_nil (p->next) && is_atomic (t)) {
00226     string s= t->label;
00227     return s (0, p->item) * u->label * s (p->item, N(s));
00228   }
00229   else if (is_nil (p->next)) {
00230     int i, j= p->item, n= N(t), nr= N(u);
00231     tree r (t, n+nr);
00232     for (i=0; i<j; i++) r[i]= t[i];
00233     for (; i<n; i++) r[i+nr]= t[i];
00234     for (i=0; i<nr; i++) r[j+i]= copy (u[i]);
00235     return r;
00236   }
00237   else {
00238     int i, j= p->item, n= N(t);
00239     tree r (t, n);
00240     for (i=0; i<j; i++) r[i]= t[i];
00241     r[j]= clean_insert (t[j], p->next, u);
00242     for (i++; i<n; i++) r[i]= t[i];
00243     return r;
00244   }  
00245 }
00246 
00247 tree
00248 clean_remove (tree t, path p, int nr) {
00249   if (is_nil (p->next) && is_atomic (t)) {
00250     string s= t->label;
00251     return s (0, p->item) * s (p->item+nr, N(s));
00252   }
00253   else if (is_nil (p->next)) {
00254     int i, j= p->item, n= N(t);
00255     tree r (t, n-nr);
00256     for (i=0; i<j; i++) r[i]= t[i];
00257     for (i+=nr; i<n; i++) r[i-nr]= t[i];
00258     return r;
00259   }
00260   else {
00261     int i, j= p->item, n= N(t);
00262     if (j >= n) FAILED("clean_remove(): Invalid path."); //return t;  // FIXME? check whether this is the right return value.
00263     tree r (t, n);
00264     for (i=0; i<j; i++) r[i]= t[i];
00265     r[j]= clean_remove (t[j], p->next, nr);
00266     for (i++; i<n; i++) r[i]= t[i];
00267     return r;
00268   }  
00269 }
00270 
00271 tree
00272 clean_split (tree t, path p) {
00273   if (is_nil (p->next->next)) {
00274     tree u= t[p->item];
00275     int i, n1= p->next->item, n2= N(u)-n1;
00276     tree s1, s2;
00277     if (is_atomic (u)) {
00278       s1= u->label (0, n1);
00279       s2= u->label (n1, N(u->label));
00280     }
00281     else {
00282       s1= tree (u, n1);
00283       s2= tree (u, n2);
00284       for (i=0; i<n1; i++) s1[i]= u[i];
00285       for (i=0; i<n2; i++) s2[i]= u[n1+i];
00286     }
00287 
00288     int j= p->item, n= N(t);
00289     tree r (t, n+1);
00290     for (i=0; i<j; i++) r[i]= t[i];
00291     r[j]= s1; r[j+1]= s2;
00292     for (i++; i<n; i++) r[i+1]= t[i];
00293     return r;
00294   }
00295   else {
00296     int i, j= p->item, n= N(t);
00297     tree r (t, n);
00298     for (i=0; i<j; i++) r[i]= t[i];
00299     r[j]= clean_split (t[j], p->next);
00300     for (i++; i<n; i++) r[i]= t[i];
00301     return r;
00302   }  
00303 }
00304 
00305 tree
00306 clean_join (tree t, path p) {
00307   if (is_nil (p->next)) {
00308     int i, j= p->item;
00309     tree s1= t[j], s2= t[j+1], u;
00310     if (is_atomic (s1))
00311       u= tree (s1->label * s2->label);
00312     else {
00313       int n1= N(s1), n2= N(s2);
00314       u= tree (s1, n1+n2);
00315       for (i=0; i<n1; i++) u[i]= s1[i];
00316       for (i=0; i<n2; i++) u[n1+i]= s2[i];
00317     }
00318 
00319     int n= N(t);
00320     tree r (t, n-1);
00321     for (i=0; i<j; i++) r[i]= t[i];
00322     r[j]= u;
00323     for (i+=2; i<n; i++) r[i-1]= t[i];
00324     return r;
00325   }
00326   else {
00327     int i, j= p->item, n= N(t);
00328     tree r (t, n);
00329     for (i=0; i<j; i++) r[i]= t[i];
00330     r[j]= clean_join (t[j], p->next);
00331     for (i++; i<n; i++) r[i]= t[i];
00332     return r;
00333   }  
00334 }
00335 
00336 tree
00337 clean_assign_node (tree t, path p, tree_label op) {
00338   if (is_nil (p)) {
00339     int i, n= N(t);
00340     tree r (op, n);
00341     for (i=0; i<n; i++) r[i]= t[i];
00342     return r;
00343   }
00344   else {
00345     int i, j= p->item, n= N(t);
00346     tree r (t, n);
00347     for (i=0; i<j; i++) r[i]= t[i];
00348     r[j]= clean_assign_node (t[j], p->next, op);
00349     for (i++; i<n; i++) r[i]= t[i];
00350     return r;
00351   }  
00352 }
00353 
00354 tree
00355 clean_insert_node (tree t, path p, tree u) {
00356   if (is_nil (p->next)) {
00357     int i, j= p->item, n= N(u);
00358     tree r (u, n+1);
00359     for (i=0; i<j; i++) r[i]= u[i];
00360     r[j]= t;
00361     for (; i<n; i++) r[i+1]= u[i];
00362     return r;
00363   }
00364   else {
00365     int i, j= p->item, n= N(t);
00366     tree r (t, n);
00367     for (i=0; i<j; i++) r[i]= t[i];
00368     r[j]= clean_insert_node (t[j], p->next, u);
00369     for (i++; i<n; i++) r[i]= t[i];
00370     return r;
00371   }  
00372 }
00373 
00374 tree
00375 clean_remove_node (tree t, path p) {
00376   if (is_nil (p->next)) return t[p->item];
00377   else {
00378     int i, j= p->item, n= N(t);
00379     tree r (t, n);
00380     for (i=0; i<j; i++) r[i]= t[i];
00381     r[j]= clean_remove_node (t[j], p->next);
00382     for (i++; i<n; i++) r[i]= t[i];
00383     return r;
00384   }  
00385 }
00386 
00387 tree
00388 clean_set_cursor (tree t, path p, tree data) {
00389   (void) p; (void) data;
00390   return t;
00391 }
00392 
00393 tree
00394 clean_apply (tree t, modification mod) {
00395   switch (mod->k) {
00396   case MOD_ASSIGN:
00397     return clean_assign (t, mod->p, mod->t);
00398   case MOD_INSERT:
00399     return clean_insert (t, mod->p, mod->t);
00400   case MOD_REMOVE:
00401     return clean_remove (t, path_up (mod->p), last_item (mod->p));
00402   case MOD_SPLIT:
00403     return clean_split (t, mod->p);
00404   case MOD_JOIN:
00405     return clean_join (t, mod->p);
00406   case MOD_ASSIGN_NODE:
00407     return clean_assign_node (t, mod->p, L(mod));
00408   case MOD_INSERT_NODE:
00409     return clean_insert_node (t, mod->p, mod->t);
00410   case MOD_REMOVE_NODE:
00411     return clean_remove_node (t, mod->p);
00412   case MOD_SET_CURSOR:
00413     return clean_set_cursor (t, mod->p, mod->t);
00414   default:
00415     FAILED ("invalid modification type");
00416     return "";
00417   }
00418 }