c0b58af4d7e2417f001561b6d7a972eb4684697f
[Faustine.git] / interpretor / faust-0.9.47mr3 / compiler / tlib / list.hh
1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
5 ---------------------------------------------------------------------
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 ************************************************************************
20 ************************************************************************/
21
22
23
24 /*****************************************************************************
25 ******************************************************************************
26 LIST
27 Y. Orlarey, (c) Grame 2002
28 ------------------------------------------------------------------------------
29 This file contains several extensions to the tree library :
30 - lists : based on a operations like cons, hd , tl, ...
31 - environments : list of associations (key value)
32 - property list : used to annotate trees
33
34
35 API:
36 ----
37
38 List :
39 -----
40
41 nil = predefined empty list
42 cons (x,l) = create a nex list of head x and tail l
43 hd(cons(x,l)) = x,
44 tl (cons(x,l)) = l
45 nth(l,i) = ith element of l (or nil)
46 replace(l,i,e) = a copy of l where the ith element is e
47 len(l) = number of elements of l
48 isNil(nil) = true (false otherwise)
49 isList(cons(x,l)) = true (false otherwise)
50 list(a,b,..) = cons(a, list(b,...))
51
52 lmap(f, cons(x,l)) = cons(f(x), lmap(f,l))
53 reverse([a,b,..,z]) = [z,..,b,a]
54 reverseall([a,b,..,z]) = [ra(z),..,ra(b),ra(a)] where ra is reverseall
55
56 Set :
57 -----
58 (Sets are implemented as ordered lists of elements without duplication)
59
60 isElement(e,s) = true if e is an element of set s, false otherwise
61 addElement(e,s) = s U {e}
62 remElement(e,s) = s - {e}
63 singleton(e) = {e}
64 list2set(l) = convert a list into a set
65 setUnion(s1,s2) = s1 U s2
66 setIntersection(s1,s2) = s1 intersection s2
67 setDifference(s1,s2) = s1 - s2
68
69 Environment :
70 -------------
71
72 An 'environment' is a stack of pairs (key x value) used to keep track of lexical bindings
73
74 pushEnv (key, val, env) -> env' create a new environment
75 searchEnv (key,&v,env) -> bool search for key in env and set v accordingly
76
77 search(k1,&v, push(k2,x,env)) = true and v is set to x if k1==k2
78 = search(k1,&v,env) if k1 != k2
79 Property list :
80 ---------------
81
82 Every tree can be annotated with an 'attribut' field. This attribute field
83 can be used to manage a property list (pl). A property list is a list of pairs
84 key x value, with three basic operations :
85
86 setProperty (t, key, val) -> t add the association (key x val) to the pl of t
87 getProperty (t, key, &val) -> bool search the pp of t for the value associated to key
88 remProperty (t, key) -> t remove any association (key x ?) from the pl of t
89
90 Warning :
91 ---------
92 Since reference counters are used for garbage collecting, one must be careful not to
93 create cycles in trees. The only possible source of cycles is by setting the attribut
94 of a tree t to a tree t' that contains t as a subtree.
95
96 History :
97 ---------
98 2002-02-08 : First version
99 2002-02-20 : New description of the API, non recursive lmap and reverse
100 2002-03-29 : Added function remElement(e,set), corrected comment error
101
102 ******************************************************************************
103 *****************************************************************************/
104
105 #ifndef __LIST__
106 #define __LIST__
107
108 #include "symbol.hh"
109 #include "tree.hh"
110 #include <stdio.h>
111
112 // Basic List Operations implemented on trees
113
114 extern Sym CONS;
115 extern Sym NIL;
116 extern Tree nil;
117
118 typedef Tree (*tfun)(Tree);
119
120 void print (Tree t, FILE* out=stdout);
121 //bool printlist (const CTree* lc);
122
123 // to create new lists
124 inline Tree cons (Tree a, Tree b) { return tree (CONS, a, b); }
125
126 inline Tree list0 () { return nil; }
127 inline Tree list1 (Tree a) { return cons (a, list0()); }
128 inline Tree list2 (Tree a, Tree b) { return cons (a, list1(b)); }
129 inline Tree list3 (Tree a, Tree b, Tree c) { return cons (a, list2(b, c)); }
130 inline Tree list4 (Tree a, Tree b, Tree c, Tree d) { return cons (a, list3(b, c, d)); }
131
132 // to access the head and the tail of a list
133 inline Tree hd (Tree l) { return l->branch(0); }
134 inline Tree tl (Tree l) { return l->branch(1); }
135
136 // predicates
137 inline bool isNil (Tree l) { return (l->node() == Node(NIL)) && (l->arity() == 0) ; }
138 inline bool isList (Tree l) { return (l->node() == Node(CONS)) && (l->arity() == 2) ; }
139
140 // predicates
141 Tree nth(Tree l, int i);
142 Tree replace(Tree l, int i, Tree e);
143 int len(Tree l);
144
145 // reversing
146 Tree reverse (Tree l);
147 Tree reverseall (Tree l);
148
149 // operations
150 Tree rconcat(Tree l1, Tree l2);
151 Tree concat(Tree l1, Tree l2);
152 Tree lrange(Tree l, int i, int j); // de i a j exclu
153
154 // mapping
155 Tree lmap (tfun f, Tree l);
156
157 // Sets
158 bool isElement (Tree e, Tree l);
159 Tree addElement (Tree e, Tree l1);
160 Tree remElement (Tree e, Tree l1);
161 Tree singleton (Tree l);
162 Tree list2set (Tree l);
163 Tree setUnion (Tree l1, Tree l2);
164 Tree setIntersection (Tree l1, Tree l2);
165 Tree setDifference (Tree l1, Tree l2);
166
167 // functions as set of pairs key x value
168 Tree addFun(Tree k, Tree v, Tree l);
169 bool getFun(Tree k, Tree& v, Tree l);
170
171 // Pairs
172
173 //inline Tree pair (Tree t1, Tree t2) { return cons(t1,t2); }
174 inline Tree left (Tree t) { return t->branch(0); }
175 inline Tree right (Tree t) { return t->branch(1); }
176
177
178 // Environment : stack of pairs key value)
179 Tree pushEnv (Tree key, Tree val, Tree env=nil);
180 bool searchEnv (Tree key, Tree& v, Tree env);
181
182 // Operations on the property list of a tree t
183 void setProperty (Tree t, Tree key, Tree val);
184 bool getProperty (Tree t, Tree key, Tree& val);
185 void remProperty (Tree t, Tree key);
186
187 // Mapping sur les arbres
188 Tree tmap (Tree k, tfun f, Tree t);
189
190 // remplacement
191 Tree substitute (Tree t, Tree id, Tree val);
192
193
194 #endif