00001 /************************************************************************ 00002 ************************************************************************ 00003 FAUST compiler 00004 Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale 00005 --------------------------------------------------------------------- 00006 This program is free software; you can redistribute it and/or modify 00007 it under the terms of the GNU General Public License as published by 00008 the Free Software Foundation; either version 2 of the License, or 00009 (at your option) any later version. 00010 00011 This program is distributed in the hope that it will be useful, 00012 but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 GNU General Public License for more details. 00015 00016 You should have received a copy of the GNU General Public License 00017 along with this program; if not, write to the Free Software 00018 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00019 ************************************************************************ 00020 ************************************************************************/ 00021 00022 00023 00024 /***************************************************************************** 00025 ****************************************************************************** 00026 LIST 00027 Y. Orlarey, (c) Grame 2002 00028 ------------------------------------------------------------------------------ 00029 This file contains several extensions to the tree library : 00030 - lists : based on a operations like cons, hd , tl, ... 00031 - environments : list of associations (key value) 00032 - property list : used to annotate trees 00033 00034 00035 API: 00036 ---- 00037 00038 List : 00039 ----- 00040 00041 nil = predefined empty list 00042 cons (x,l) = create a nex list of head x and tail l 00043 hd(cons(x,l)) = x, 00044 tl (cons(x,l)) = l 00045 nth(l,i) = ith element of l (or nil) 00046 replace(l,i,e) = a copy of l where the ith element is e 00047 len(l) = number of elements of l 00048 isNil(nil) = true (false otherwise) 00049 isList(cons(x,l)) = true (false otherwise) 00050 list(a,b,..) = cons(a, list(b,...)) 00051 00052 lmap(f, cons(x,l)) = cons(f(x), lmap(f,l)) 00053 reverse([a,b,..,z]) = [z,..,b,a] 00054 reverseall([a,b,..,z]) = [ra(z),..,ra(b),ra(a)] where ra is reverseall 00055 00056 Set : 00057 ----- 00058 (Sets are implemented as ordered lists of elements without duplication) 00059 00060 isElement(e,s) = true if e is an element of set s, false otherwise 00061 addElement(e,s) = s U {e} 00062 remElement(e,s) = s - {e} 00063 singleton(e) = {e} 00064 list2set(l) = convert a list into a set 00065 setUnion(s1,s2) = s1 U s2 00066 setIntersection(s1,s2) = s1 intersection s2 00067 setDifference(s1,s2) = s1 - s2 00068 00069 Environment : 00070 ------------- 00071 00072 An 'environment' is a stack of pairs (key x value) used to keep track of lexical bindings 00073 00074 pushEnv (key, val, env) -> env' create a new environment 00075 searchEnv (key,&v,env) -> bool search for key in env and set v accordingly 00076 00077 search(k1,&v, push(k2,x,env)) = true and v is set to x if k1==k2 00078 = search(k1,&v,env) if k1 != k2 00079 Property list : 00080 --------------- 00081 00082 Every tree can be annotated with an 'attribut' field. This attribute field 00083 can be used to manage a property list (pl). A property list is a list of pairs 00084 key x value, with three basic operations : 00085 00086 setProperty (t, key, val) -> t add the association (key x val) to the pl of t 00087 getProperty (t, key, &val) -> bool search the pp of t for the value associated to key 00088 remProperty (t, key) -> t remove any association (key x ?) from the pl of t 00089 00090 Warning : 00091 --------- 00092 Since reference counters are used for garbage collecting, one must be careful not to 00093 create cycles in trees. The only possible source of cycles is by setting the attribut 00094 of a tree t to a tree t' that contains t as a subtree. 00095 00096 History : 00097 --------- 00098 2002-02-08 : First version 00099 2002-02-20 : New description of the API, non recursive lmap and reverse 00100 2002-03-29 : Added function remElement(e,set), corrected comment error 00101 00102 ****************************************************************************** 00103 *****************************************************************************/ 00104 00105 #ifndef __LIST__ 00106 #define __LIST__ 00107 00108 #include "symbol.hh" 00109 #include "tree.hh" 00110 #include <stdio.h> 00111 00112 // Basic List Operations implemented on trees 00113 00114 extern Sym CONS; 00115 extern Sym NIL; 00116 extern Tree nil; 00117 00118 typedef Tree (*tfun)(Tree); 00119 00120 void print (Tree t, FILE* out=stdout); 00121 //bool printlist (const CTree* lc); 00122 00123 // to create new lists 00124 inline Tree cons (Tree a, Tree b) { return tree (CONS, a, b); } 00125 00126 inline Tree list0 () { return nil; } 00127 inline Tree list1 (Tree a) { return cons (a, list0()); } 00128 inline Tree list2 (Tree a, Tree b) { return cons (a, list1(b)); } 00129 inline Tree list3 (Tree a, Tree b, Tree c) { return cons (a, list2(b, c)); } 00130 inline Tree list4 (Tree a, Tree b, Tree c, Tree d) { return cons (a, list3(b, c, d)); } 00131 00132 // to access the head and the tail of a list 00133 inline Tree hd (Tree l) { return l->branch(0); } 00134 inline Tree tl (Tree l) { return l->branch(1); } 00135 00136 // predicates 00137 inline bool isNil (Tree l) { return (l->node() == Node(NIL)) && (l->arity() == 0) ; } 00138 inline bool isList (Tree l) { return (l->node() == Node(CONS)) && (l->arity() == 2) ; } 00139 00140 // predicates 00141 Tree nth(Tree l, int i); 00142 Tree replace(Tree l, int i, Tree e); 00143 int len(Tree l); 00144 00145 // reversing 00146 Tree reverse (Tree l); 00147 Tree reverseall (Tree l); 00148 00149 // operations 00150 Tree rconcat(Tree l1, Tree l2); 00151 Tree concat(Tree l1, Tree l2); 00152 Tree lrange(Tree l, int i, int j); // de i a j exclu 00153 00154 // mapping 00155 Tree lmap (tfun f, Tree l); 00156 00157 // Sets 00158 bool isElement (Tree e, Tree l); 00159 Tree addElement (Tree e, Tree l1); 00160 Tree remElement (Tree e, Tree l1); 00161 Tree singleton (Tree l); 00162 Tree list2set (Tree l); 00163 Tree setUnion (Tree l1, Tree l2); 00164 Tree setIntersection (Tree l1, Tree l2); 00165 Tree setDifference (Tree l1, Tree l2); 00166 00167 // Pairs 00168 00169 //inline Tree pair (Tree t1, Tree t2) { return cons(t1,t2); } 00170 inline Tree left (Tree t) { return t->branch(0); } 00171 inline Tree right (Tree t) { return t->branch(1); } 00172 00173 00174 // Environment : stack of pairs key value) 00175 Tree pushEnv (Tree key, Tree val, Tree env=nil); 00176 bool searchEnv (Tree key, Tree& v, Tree env); 00177 00178 // Operations on the property list of a tree t 00179 void setProperty (Tree t, Tree key, Tree val); 00180 bool getProperty (Tree t, Tree key, Tree& val); 00181 void remProperty (Tree t, Tree key); 00182 00183 // Mapping sur les arbres 00184 Tree tmap (Tree k, tfun f, Tree t); 00185 00186 // remplacement 00187 Tree substitute (Tree t, Tree id, Tree val); 00188 00189 00190 #endif