Back to index

texmacs  1.0.7.15
tree.hpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : tree.hpp
00004 * DESCRIPTION: fixed size trees with reference counting
00005 * COPYRIGHT  : (C) 1999  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 #ifndef TREE_H
00013 #define TREE_H
00014 #include "tree_label.hpp"
00015 #include "observer.hpp"
00016 #include "array.hpp"
00017 
00018 /******************************************************************************
00019 * The tree class 'tree'
00020 ******************************************************************************/
00021 
00022 class tree;
00023 class tree_rep;
00024 class atomic_rep;
00025 class compound_rep;
00026 class generic_rep;
00027 class blackbox;
00028 tree copy (tree t);
00029 
00030 class tree {
00031   tree_rep* rep; // can be atomic or compound or generic
00032   inline tree (tree_rep* rep2);
00033 
00034 public:
00035   inline tree (const tree& x);
00036   inline ~tree ();
00037   inline atomic_rep* operator -> ();
00038   inline tree& operator = (tree x);
00039 
00040   inline tree ();
00041   inline tree (string l);
00042   inline tree (const char* l);
00043   inline tree (tree_label l, int n=0);
00044   inline tree (tree_label l, array<tree> a);
00045   inline tree (tree t, int n);
00046   tree (tree_label l, tree t1);
00047   tree (tree_label l, tree t1, tree t2);
00048   tree (tree_label l, tree t1, tree t2, tree t3);
00049   tree (tree_label l, tree t1, tree t2, tree t3, tree t4);
00050   tree (tree_label l, tree t1, tree t2, tree t3, tree t4, tree t5);
00051   tree (tree_label l, tree t1, tree t2, tree t3, tree t4, tree t5, tree t6);
00052   tree (tree_label l, tree t1, tree t2, tree t3, tree t4,
00053                      tree t5, tree t6, tree t7);
00054   tree (tree_label l, tree t1, tree t2, tree t3, tree t4,
00055                      tree t5, tree t6, tree t7, tree t8);
00056   inline tree& operator [] (int i);
00057   tree operator () (int start, int end);
00058 
00059   friend inline int N (tree t);
00060   friend inline int arity (tree t);
00061   friend inline tree_label L (tree t);
00062   friend inline tree_label& LR (tree t);
00063   friend inline array<tree> A (tree t);
00064   friend inline array<tree>& AR (tree t);
00065   friend inline bool is_atomic (tree t);
00066   friend inline bool is_compound (tree t);
00067   friend inline bool is_generic (tree t);
00068   friend inline bool operator == (tree t, tree_label lab);
00069   friend inline bool operator != (tree t, tree_label lab);
00070   friend inline bool operator == (tree t, string s);
00071   friend inline bool operator != (tree t, string s);
00072   friend inline bool operator == (tree t, const char* s);
00073   friend inline bool operator != (tree t, const char* s);
00074   friend inline tree_rep* inside (tree t);
00075   friend inline bool strong_equal (tree t, tree u);
00076   friend inline bool is_func (tree t, tree_label l);
00077   friend inline bool is_func (tree t, tree_label l, int i);
00078 
00079   friend tree copy (tree t);
00080   friend tree freeze (tree t);
00081   friend bool operator == (tree t, tree u);
00082   friend bool operator != (tree t, tree u);
00083   friend tree& operator << (tree& t, tree t2);
00084   friend tree& operator << (tree& t, array<tree> a);
00085   friend tm_ostream& operator << (tm_ostream& out, tree t);
00086   friend tree operator * (tree t1, tree t2);
00087   friend void print_tree (tree t, int tab=0);
00088   friend list<tree> as_trees (list<pointer> l);
00089   friend class tree_pointer_rep;
00090   friend class tree_position_rep;
00091   friend class tree_addendum_rep;
00092   friend class edit_observer_rep;
00093   friend class undo_observer_rep;
00094   friend class tree_links_rep;
00095   friend class link_repository_rep;
00096   friend blackbox as_blackbox (const tree& t);
00097 };
00098 
00099 class tree_rep: concrete_struct {
00100 public:
00101   tree_label op;
00102   observer obs;
00103   inline tree_rep (tree_label op2): op (op2) {}
00104   friend class tree;
00105 };
00106 
00107 class atomic_rep: public tree_rep {
00108 public:
00109   string label;
00110   inline atomic_rep (string l): tree_rep (STRING), label (l) {}
00111   friend class tree;
00112 };
00113 
00114 class compound_rep: public tree_rep {
00115 public:
00116   array<tree> a;
00117   inline compound_rep (tree_label l, array<tree> a2): tree_rep (l), a (a2) {}
00118   friend class tree;
00119 };
00120 
00121 // generic_rep in generic_tree.hpp
00122 
00123 template<> struct type_helper<tree> { static int id; static tree init; };
00124 
00125 typedef tree scheme_tree;
00126 
00127 /******************************************************************************
00128 * Routines for trees
00129 ******************************************************************************/
00130 
00131 #ifdef debug_trees
00132 #define CHECK_ATOMIC(t) \
00133   if (((t).rep)->op != STRING) { \
00134     cerr << "\nThe tree : " << (t) << "\n"; \
00135     FAILED ("atomic tree expected"); \
00136   }
00137 #define CHECK_COMPOUND(t) \
00138   if (((t).rep)->op == STRING) { \
00139     cerr << "\nThe tree : " << (t) << "\n"; \
00140     FAILED ("compound tree expected"); \
00141   }
00142 #else
00143 #define CHECK_ATOMIC(t)
00144 #define CHECK_COMPOUND(t)
00145 #endif
00146 
00147 void destroy_tree_rep (tree_rep* rep);
00148 inline tree::tree (tree_rep* rep2): rep (rep2) { rep->ref_count++; }
00149 inline tree::tree (const tree& x): rep (x.rep) { rep->ref_count++; }
00150 inline tree::~tree () {
00151   if ((--rep->ref_count)==0) { destroy_tree_rep (rep); rep= NULL; } }
00152 inline atomic_rep* tree::operator -> () {
00153   CHECK_ATOMIC (*this);
00154   return static_cast<atomic_rep*> (rep); }
00155 inline tree& tree::operator = (tree x) {
00156   x.rep->ref_count++;
00157   if ((--rep->ref_count)==0) destroy_tree_rep (rep);
00158   rep= x.rep;
00159   return *this; }
00160 
00161 inline tree::tree ():
00162   rep (tm_new<atomic_rep> (string ())) {}
00163 inline tree::tree (const char *s):
00164   rep (tm_new<atomic_rep> (s)) {}
00165 inline tree::tree (string s):
00166   rep (tm_new<atomic_rep> (s)) {}
00167 inline tree::tree (tree_label l, int n):
00168   rep (tm_new<compound_rep> (l, array<tree> (n))) {}
00169 inline tree::tree (tree_label l, array<tree> a):
00170   rep (tm_new<compound_rep> (l, a)) {}
00171 inline tree::tree (tree t, int n):
00172   rep (tm_new<compound_rep> (t.rep->op, array<tree> (n))) {
00173     CHECK_COMPOUND (t); }
00174 
00175 inline tree& tree::operator [] (int i) {
00176   CHECK_COMPOUND (*this);
00177   return (static_cast<compound_rep*> (rep))->a[i]; }
00178 inline int N (tree t) {
00179   CHECK_COMPOUND (t);
00180   return N ((static_cast<compound_rep*> (t.rep))->a); }
00181 inline int arity (tree t) {
00182   if (t.rep->op == STRING) return 0;
00183   else return N ((static_cast<compound_rep*> (t.rep))->a); }
00184 inline int right_index (tree t) {
00185   return is_atomic (t)? N(t->label): 1; }
00186 inline tree_label L (tree t) {
00187   return t.rep->op; }
00188 inline tree_label& LR (tree t) {
00189   return t.rep->op; }
00190 inline array<tree> A (tree t) {
00191   CHECK_COMPOUND (t);
00192   return (static_cast<compound_rep*> (t.rep))->a; }
00193 inline array<tree>& AR (tree t) {
00194   CHECK_COMPOUND (t);
00195   return (static_cast<compound_rep*> (t.rep))->a; }
00196 
00197 inline bool is_atomic (tree t) { return (((int) t.rep->op) == 0); }
00198 inline bool is_compound (tree t) { return (((int) t.rep->op) > STRING); }
00199 inline bool is_generic (tree t) { return ((int) t.rep->op) < 0; }
00200 inline string get_label (tree t) {
00201   return is_atomic (t)? t->label: copy (as_string (L(t))); }
00202 inline bool operator == (tree t, tree_label lab) {
00203   return (t.rep->op == lab) && (N(t)==0); }
00204 inline bool operator != (tree t, tree_label lab) {
00205   return (t.rep->op != lab) || (N(t)!=0); }
00206 inline bool operator == (tree t, string s) {
00207   return (t.rep->op == STRING) && (t->label == s); }
00208 inline bool operator != (tree t, string s) {
00209   return (t.rep->op != STRING) || (t->label != s); }
00210 inline bool operator == (tree t, const char* s) {
00211   return (t.rep->op == STRING) && (t->label == s); }
00212 inline bool operator != (tree t, const char* s) {
00213   return (t.rep->op != STRING) || (t->label != s); }
00214 inline tree_rep* inside (tree t) {
00215   return t.rep; }
00216 inline bool strong_equal (tree t, tree u) {
00217   return t.rep == u.rep; }
00218 
00219 inline bool is_func (tree t, tree_label l) {
00220   return (t.rep->op==l) && (N(t)!=0); }
00221 inline bool is_func (tree t, tree_label l, int i) {
00222   return (t.rep->op==l) && (N(t)==i); }
00223 
00224 inline bool is_bool (tree t) { return is_atomic (t) && is_bool (t->label); }
00225 inline bool is_int (tree t) { return is_atomic (t) && is_int (t->label); }
00226 inline bool is_double (tree t) { return is_atomic (t) && is_double(t->label); }
00227 inline bool is_string (tree t) { return is_atomic (t); }
00228 inline bool as_bool (tree t) {
00229   if (is_atomic (t)) return as_bool (t->label);
00230   else return false; }
00231 inline int as_int (tree t) {
00232   if (is_atomic (t)) return as_int (t->label);
00233   else return 0; }
00234 inline double as_double (tree t) {
00235   if (is_atomic (t)) return as_double (t->label);
00236   else return 0.0; }
00237 inline string as_string (tree t) {
00238   if (is_atomic (t)) return t->label;
00239   else return ""; }
00240 string tree_as_string (tree t);
00241 template<class T> inline tree as_tree(T x) { return (tree) x; }
00242 template<> inline tree as_tree(int x) { return as_string (x); }
00243 template<> inline tree as_tree(double x) { return as_string (x); }
00244 template<> inline tree as_tree(pointer x) { (void) x; return "pointer"; }
00245 inline tree bool_as_tree (bool f) {
00246   return (f? tree ("true"): tree ("false")); }
00247 
00248 /******************************************************************************
00249 * Data
00250 ******************************************************************************/
00251 
00252 bool is_document (tree t);
00253 bool is_concat (tree t);
00254 bool is_format (tree t);
00255 bool is_formatting (tree t);
00256 bool is_table (tree t);
00257 bool is_table_format (tree t);
00258 bool is_multi_paragraph (tree t);
00259 bool is_around (tree t);
00260 bool is_script (tree t);
00261 bool is_script (tree t, bool& right);
00262 bool is_prime (tree t);
00263 bool is_right_script_prime (tree t);
00264 bool is_mod_active (tree t);
00265 bool is_mod_active_once (tree t);
00266 bool is_graphical_text (tree t);
00267 bool is_empty (tree t);
00268 
00269 inline bool
00270 is_applicable (tree t) {
00271   return is_compound (t) && (N(t) >= 1) &&
00272     ((L(t) == MACRO) || (L(t) == FUNC) || (L(t) == XMACRO));
00273 }
00274 
00275 tree simplify_concat (tree t);
00276 tree simplify_correct (tree t);
00277 
00278 /******************************************************************************
00279 * Compound trees
00280 ******************************************************************************/
00281 
00282 tree compound (string s);
00283 tree compound (string s, tree t1);
00284 tree compound (string s, tree t1, tree t2);
00285 tree compound (string s, tree t1, tree t2, tree t3);
00286 tree compound (string s, tree t1, tree t2, tree t3, tree t4);
00287 tree compound (string s, array<tree> a);
00288 bool is_extension (tree t);
00289 bool is_extension (tree t, int n);
00290 bool is_compound (tree t, string s);
00291 bool is_compound (tree t, string s, int n);
00292 
00293 /******************************************************************************
00294 * Tuples
00295 ******************************************************************************/
00296 
00297 inline tree tuple () {
00298   return tree (TUPLE); }
00299 inline tree tuple (tree t1) {
00300   return tree (TUPLE, t1); }
00301 inline tree tuple (tree t1, tree t2) {
00302   return tree (TUPLE, t1, t2); }
00303 inline tree tuple (tree t1, tree t2, tree t3) {
00304   return tree (TUPLE, t1, t2, t3); }
00305 inline tree tuple (tree t1, tree t2, tree t3, tree t4) {
00306   return tree (TUPLE, t1, t2, t3, t4); }
00307 
00308 inline bool is_tuple (tree t) {
00309   return (L(t) == TUPLE); }
00310 inline bool is_tuple (tree t, string s) {
00311   return (L(t) == TUPLE) && (N(t) >= 1) && (t[0] == s); }
00312 inline bool is_tuple (tree t, const char* s) {
00313   return (L(t) == TUPLE) && (N(t) >= 1) && (t[0] == s); }
00314 inline bool is_tuple (tree t, string s, int n) {
00315   return (L(t) == TUPLE) && (N(t) == (n+1)) && (t[0] == s); }
00316 inline bool is_tuple (tree t, const char* s, int n) {
00317   return (L(t) == TUPLE) && (N(t) == (n+1)) && (t[0] == s); }
00318 
00319 /******************************************************************************
00320 * Other frequent markup
00321 ******************************************************************************/
00322 
00323 inline tree concat () {
00324   return tree (CONCAT); }
00325 inline tree concat (tree t1) {
00326   return tree (CONCAT, t1); }
00327 inline tree concat (tree t1, tree t2) {
00328   return tree (CONCAT, t1, t2); }
00329 inline tree concat (tree t1, tree t2, tree t3) {
00330   return tree (CONCAT, t1, t2, t3); }
00331 inline tree concat (tree t1, tree t2, tree t3, tree t4) {
00332   return tree (CONCAT, t1, t2, t3, t4); }
00333 inline tree concat (tree t1, tree t2, tree t3, tree t4, tree t5) {
00334   return tree (CONCAT, t1, t2, t3, t4, t5); }
00335 
00336 inline tree document () {
00337   return tree (DOCUMENT); }
00338 inline tree document (tree t1) {
00339   return tree (DOCUMENT, t1); }
00340 inline tree document (tree t1, tree t2) {
00341   return tree (DOCUMENT, t1, t2); }
00342 inline tree document (tree t1, tree t2, tree t3) {
00343   return tree (DOCUMENT, t1, t2, t3); }
00344 inline tree document (tree t1, tree t2, tree t3, tree t4) {
00345   return tree (DOCUMENT, t1, t2, t3, t4); }
00346 inline tree document (tree t1, tree t2, tree t3, tree t4, tree t5) {
00347   return tree (DOCUMENT, t1, t2, t3, t4, t5); }
00348 
00349 inline tree verbatim (tree t1) {
00350   return compound ("verbatim", t1); }
00351 
00352 /******************************************************************************
00353 * Miscellaneous
00354 ******************************************************************************/
00355 
00356 tree   correct (tree t);
00357 int    hash (tree t);
00358 
00359 template<class T>
00360 array<T>::operator tree () {
00361   int i, n=rep->n;
00362   tree t (TUPLE, n);
00363   for (i=0; i<n; i++)
00364     t[i]= as_tree(rep->a[i]);
00365   return t;
00366 }
00367 
00368 #endif // defined TREE_H