Back to index

texmacs  1.0.7.15
path.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : path.cpp
00004 * DESCRIPTION: paths are integer lists,
00005 *              which are for instance useful to select subtrees in trees
00006 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00007 *******************************************************************************
00008 * This software falls under the GNU general public license version 3 or later.
00009 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00010 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00011 ******************************************************************************/
00012 
00013 #include "path.hpp"
00014 #include "analyze.hpp"
00015 
00016 /******************************************************************************
00017 * General routines on paths
00018 ******************************************************************************/
00019 
00020 bool
00021 zero_path (path p) {
00022   if (is_nil (p)) return true;
00023   return (p->item == 0) && zero_path (p->next);
00024 }
00025 
00026 int
00027 hash (path p) {
00028   if (is_nil (p)) return 0;
00029   else {
00030     int h= hash (p->next);
00031     return p->item ^ ((h<<7) + (h>>25));
00032   }
00033 }
00034 
00035 string
00036 as_string (path p) {
00037   if (is_nil (p)) return "";
00038   if (is_atom (p)) return as_string (p->item);
00039   return as_string (p->item) * "." * as_string (p->next);
00040 }
00041 
00042 path
00043 as_path (string s) {
00044   int i, j, n= N(s);
00045   for (i=0; i<n; i++)
00046     if (is_digit (s[i])) break;
00047   if (i==n) return path ();
00048   for (j=i; j<n; j++)
00049     if (!is_digit (s[j])) break;
00050   return path (as_int (s (i, j)), as_path (s (j, n)));
00051 }
00052 
00053 bool
00054 version_inf_eq (string v1, string v2) {
00055   if (starts (v2, v1)) return true;
00056   return path_inf_eq (as_path (v1), as_path (v2));
00057 }
00058 
00059 bool
00060 version_inf (string v1, string v2) {
00061   if (v1 == v2) return false;
00062   return version_inf_eq (v1, v2);
00063 }
00064 
00065 /******************************************************************************
00066 * Operations on paths
00067 ******************************************************************************/
00068 
00069 path
00070 path_add (path p, int plus) {
00071   if (is_atom (p)) return path (p->item+plus);
00072   return path (p->item, path_add (p->next, plus));
00073 }
00074 
00075 path
00076 path_add (path p, int plus, int pos) {
00077   p= copy (p);
00078   p[pos]+=plus;
00079   return p;
00080 }
00081 
00082 path
00083 path_up (path p) {
00084   ASSERT (!is_nil (p), "path is too short");
00085   if (is_nil (p->next)) return path ();
00086   return path (p->item, path_up (p->next));
00087 }
00088 
00089 path
00090 path_up (path p, int times) {
00091   return head (p, N(p)-times);
00092 }
00093 
00094 bool
00095 path_inf (path p1, path p2) {
00096   if (is_nil (p1) || is_nil (p2)) return false;
00097   if (p1->item<p2->item) return true;
00098   if (p1->item>p2->item) return false;
00099   return path_inf (p1->next, p2->next);
00100 }
00101 
00102 bool
00103 path_inf_eq (path p1, path p2) {
00104   if (is_nil (p1) || is_nil (p2)) return (p1 == p2);
00105   if (p1->item<p2->item) return true;
00106   if (p1->item>p2->item) return false;
00107   return path_inf_eq (p1->next, p2->next);
00108 }
00109 
00110 bool
00111 path_less (path p1, path p2) {
00112   return path_less_eq (p1, p2) && (p1 != p2);
00113 }
00114 
00115 bool
00116 path_less_eq (path p1, path p2) {
00117   if (is_nil (p1) || is_nil (p2)) return p1 == p2;
00118   if (is_atom (p1) || is_atom (p2)) {
00119     if (is_atom (p1) && is_atom (p2)) return p1->item <= p2->item;
00120     if ((p1->item == 0) && is_nil (p1->next)) return true;
00121     if ((p2->item == 1) && is_nil (p2->next)) return true;
00122     return false;
00123   }
00124   if (p1->item<p2->item) return true;
00125   if (p1->item>p2->item) return false;
00126   return path_less_eq (p1->next, p2->next);
00127 }
00128 
00129 path
00130 operator / (path p, path q) {
00131   if (is_nil (q)) return p;
00132   else if (is_nil (p) || (p->item != q->item)) {
00133     FAILED ("path did not start with required path"); }
00134   else return p->next / q->next;
00135   return path (); // NOT REACHED
00136 }
00137 
00138 path
00139 common (path start, path end) {
00140   if (is_nil (start) || is_nil (end)) return path ();
00141   if (start->item != end->item) return path ();
00142   return path (start->item, common (start->next, end->next));
00143 }
00144 
00145 /******************************************************************************
00146 * Main modification routines
00147 ******************************************************************************/
00148 
00149 bool
00150 has_subtree (tree t, path p) {
00151   if (is_nil (p)) return true;
00152   int i= p->item;
00153   return is_compound (t) && i >= 0 && i < N(t) && has_subtree (t[i], p->next);
00154 }
00155 
00156 tree&
00157 subtree (tree& t, path p) {
00158   if (is_nil (p)) return t;
00159   else return subtree (t[p->item], p->next);
00160 }
00161 
00162 tree&
00163 parent_subtree (tree& t, path p) {
00164   ASSERT (!is_nil (p), "path too short");
00165   if (is_nil (p->next)) return t;
00166   else return parent_subtree (t[p->item], p->next);
00167 }