00001 #ifndef __TLIB__ 00002 #define __TLIB__ 00003 00004 /************************************************************************ 00005 ************************************************************************ 00006 FAUST compiler 00007 Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale 00008 --------------------------------------------------------------------- 00009 This program is free software; you can redistribute it and/or modify 00010 it under the terms of the GNU General Public License as published by 00011 the Free Software Foundation; either version 2 of the License, or 00012 (at your option) any later version. 00013 00014 This program is distributed in the hope that it will be useful, 00015 but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 GNU General Public License for more details. 00018 00019 You should have received a copy of the GNU General Public License 00020 along with this program; if not, write to the Free Software 00021 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00022 ************************************************************************ 00023 ************************************************************************/ 00024 00025 00026 00027 /***************************************************************************** 00028 ****************************************************************************** 00029 TLIB : tree library 00030 Y. Orlarey, (c) Grame 2002 00031 ------------------------------------------------------------------------------ 00032 Tlib is a simple tree library inspired by the ATerm library. It is made of 00033 five elements : symbols, nodes, smartpointers, trees and lists : 00034 00035 +------------------------+ 00036 | shlysis | 00037 +------------------------+ 00038 | rec | 00039 |------------------------| 00040 | list | 00041 |------------------------| 00042 | tree | 00043 |------------------------| 00044 | nodes | | 00045 |---------| smartpointer | 00046 | symbol | | 00047 +---------+--------------+ 00048 00049 API: 00050 ---- 00051 1) Symbols : 00052 ------------ 00053 Sym q = symbol("abcd"); : returns a symbol q of name "abcd" 00054 const char* s = name(q); : returns the name of symbol q 00055 00056 2) Nodes : 00057 ---------- 00058 Node(symbol("abcd")); : node with symbol content 00059 Node(10); : node with int content 00060 Node(3.14159); : node with float content 00061 00062 n->type(); : kIntNode or kFloatNode or kSymNode 00063 00064 n->getInt(); : int content of n 00065 n->getFloat(); : float content of n 00066 n->getSym(); : symbol content of n 00067 00068 - Pattern matching : 00069 00070 if (isInt(n, &i)) ... : int i = int content of n 00071 if (isFloat(n, &f)) ... : float f = float content of n 00072 if (isSym(n, &s)) ... : Sym s = Sym content of n 00073 00074 3) Trees : 00075 ---------- 00076 tree (n) : tree of node n with no branch 00077 tree (n, t1) : tree of node n with a branch t 00078 tree (n, t1,...,tm) : tree of node n with m branches t1,...,tm 00079 00080 - Pattern matching : 00081 00082 if (isTree (t, n)) ... : t has node n and no branches; 00083 if (isTree (t, n, &t1) ... : t has node n and 1 branch, t1 is set accordingly; 00084 if (isTree (t, n, &t1...&tm)...: t has node n and m branches, ti's are set accordingly; 00085 00086 - Accessors : 00087 00088 t->node() : the node of t 00089 t->arity() : the number of branches of t 00090 t->branch(i) : the ith branch of t 00091 00092 4) List : 00093 --------- 00094 00095 nil = predefined empty list 00096 cons (x,l) = create a new list of head x and tail l 00097 list(a,b,..) = cons(a, list(b,...)) 00098 00099 hd(cons(x,l)) = x, 00100 tl (cons(x,l)) = l 00101 nth(l,i) = ith element of l (or nil) 00102 len(l) = number of elements of l 00103 00104 isNil(nil) = true (false otherwise) 00105 isList(cons(x,l)) = true (false otherwise) 00106 00107 lmap(f, cons(x,l)) = cons(f(x), lmap(f,l)) 00108 reverse([a,b,..,z]) = [z,..,b,a] 00109 reverseall([a,b,..,z]) = [ra(z),..,ra(b),ra(a)] where ra is reverseall 00110 00111 - Set : 00112 (Sets are implemented as ordered lists of elements without duplication) 00113 00114 isElement(e,s) = true if e is an element of set s, false otherwise 00115 addElement(e,s) = s U {e} 00116 singleton(e) = {e} 00117 list2set(l) = convert a list into a set 00118 setUnion(s1,s2) = s1 U s2 00119 setIntersection(s1,s2) = s1 intersection s2 00120 setIntersection(s1,s2) = s1 - s2 00121 00122 - Environment : 00123 00124 pushEnv (key, val, env) -> env' create a new environment 00125 searchEnv (key,&v,env) -> bool search for key in env and set v accordingly 00126 00127 - Property list : 00128 00129 setProperty (t, key, val) -> t add the association (key x val) to the pl of t 00130 getProperty (t, key, &val) -> bool search the pp of t for the value associated to key 00131 remProperty (t, key) -> t remove any association (key x ?) from the pl of t 00132 00133 5) Recursive trees 00134 ------------------ 00135 00136 rid() = a unique ID (a tree) used to identify recursive trees 00137 rec(id, t) = a tree containing recursive references 'ref(id)' 00138 ref(id) = a reference to a surrounding 'rec(id,t)' 00139 isRec(t, id, t') = true if t = rec(id,t') 00140 isRef(t, id) = true if t = ref(id) 00141 00142 areEquiv(t,t') = alpha equivalence of trees 00143 shmax(t) = maximize the sharing of recursive subtrees 00144 00145 00146 6) Sharing Analysis : 00147 --------------------- 00148 00149 shprkey(t) -> k = unique sharing property key of t 00150 shcount(k,t') -> n = returns the number of occurences of t' in t (where k = shprkey(t)) 00151 shlysis(t) -> k = annotated the subtrees of t with prop (key sharing-count) 00152 (0 if t' is not a subtree of t) 00153 00154 00155 History : 00156 --------- 00157 2002-02-08 : First version 00158 2002-02-20 : New description of the API 00159 2002-04-07 : Added Sharing Analysis 'shlysis.h' 00160 00161 ****************************************************************************** 00162 *****************************************************************************/ 00163 00164 #include "symbol.hh" 00165 #include "node.hh" 00166 #include "tree.hh" 00167 #include "num.hh" 00168 #include "list.hh" 00169 #include "shlysis.hh" 00170 //#include "recness.hh" 00171 00172 #endif