--- /dev/null
+/************************************************************************
+ ************************************************************************
+ FAUST compiler
+ Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
+ ---------------------------------------------------------------------
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ ************************************************************************
+ ************************************************************************/
+
+
+
+/*****************************************************************************
+******************************************************************************
+ LIST
+ Y. Orlarey, (c) Grame 2002
+------------------------------------------------------------------------------
+This file contains several extensions to the tree library :
+ - lists : based on a operations like cons, hd , tl, ...
+ - environments : list of associations (key value)
+ - property list : used to annotate trees
+
+
+ API:
+ ----
+
+ List :
+ -----
+
+ nil = predefined empty list
+ cons (x,l) = create a nex list of head x and tail l
+ hd(cons(x,l)) = x,
+ tl (cons(x,l)) = l
+ nth(l,i) = ith element of l (or nil)
+ replace(l,i,e) = a copy of l where the ith element is e
+ len(l) = number of elements of l
+ isNil(nil) = true (false otherwise)
+ isList(cons(x,l)) = true (false otherwise)
+ list(a,b,..) = cons(a, list(b,...))
+
+ lmap(f, cons(x,l)) = cons(f(x), lmap(f,l))
+ reverse([a,b,..,z]) = [z,..,b,a]
+ reverseall([a,b,..,z]) = [ra(z),..,ra(b),ra(a)] where ra is reverseall
+
+ Set :
+ -----
+ (Sets are implemented as ordered lists of elements without duplication)
+
+ isElement(e,s) = true if e is an element of set s, false otherwise
+ addElement(e,s) = s U {e}
+ remElement(e,s) = s - {e}
+ singleton(e) = {e}
+ list2set(l) = convert a list into a set
+ setUnion(s1,s2) = s1 U s2
+ setIntersection(s1,s2) = s1 intersection s2
+ setDifference(s1,s2) = s1 - s2
+
+ Environment :
+ -------------
+
+ An 'environment' is a stack of pairs (key x value) used to keep track of lexical bindings
+
+ pushEnv (key, val, env) -> env' create a new environment
+ searchEnv (key,&v,env) -> bool search for key in env and set v accordingly
+
+ search(k1,&v, push(k2,x,env)) = true and v is set to x if k1==k2
+ = search(k1,&v,env) if k1 != k2
+ Property list :
+ ---------------
+
+ Every tree can be annotated with an 'attribut' field. This attribute field
+ can be used to manage a property list (pl). A property list is a list of pairs
+ key x value, with three basic operations :
+
+ setProperty (t, key, val) -> t add the association (key x val) to the pl of t
+ getProperty (t, key, &val) -> bool search the pp of t for the value associated to key
+ remProperty (t, key) -> t remove any association (key x ?) from the pl of t
+
+ Warning :
+ ---------
+ Since reference counters are used for garbage collecting, one must be careful not to
+ create cycles in trees. The only possible source of cycles is by setting the attribut
+ of a tree t to a tree t' that contains t as a subtree.
+
+ History :
+ ---------
+ 2002-02-08 : First version
+ 2002-02-20 : New description of the API, non recursive lmap and reverse
+ 2002-03-29 : Added function remElement(e,set), corrected comment error
+
+******************************************************************************
+*****************************************************************************/
+
+#ifndef __LIST__
+#define __LIST__
+
+#include "symbol.hh"
+#include "tree.hh"
+#include <stdio.h>
+
+// Basic List Operations implemented on trees
+
+extern Sym CONS;
+extern Sym NIL;
+extern Tree nil;
+
+typedef Tree (*tfun)(Tree);
+
+void print (Tree t, FILE* out=stdout);
+//bool printlist (const CTree* lc);
+
+// to create new lists
+inline Tree cons (Tree a, Tree b) { return tree (CONS, a, b); }
+
+inline Tree list0 () { return nil; }
+inline Tree list1 (Tree a) { return cons (a, list0()); }
+inline Tree list2 (Tree a, Tree b) { return cons (a, list1(b)); }
+inline Tree list3 (Tree a, Tree b, Tree c) { return cons (a, list2(b, c)); }
+inline Tree list4 (Tree a, Tree b, Tree c, Tree d) { return cons (a, list3(b, c, d)); }
+
+// to access the head and the tail of a list
+inline Tree hd (Tree l) { return l->branch(0); }
+inline Tree tl (Tree l) { return l->branch(1); }
+
+// predicates
+inline bool isNil (Tree l) { return (l->node() == Node(NIL)) && (l->arity() == 0) ; }
+inline bool isList (Tree l) { return (l->node() == Node(CONS)) && (l->arity() == 2) ; }
+
+// predicates
+Tree nth(Tree l, int i);
+Tree replace(Tree l, int i, Tree e);
+int len(Tree l);
+
+// reversing
+Tree reverse (Tree l);
+Tree reverseall (Tree l);
+
+// operations
+Tree rconcat(Tree l1, Tree l2);
+Tree concat(Tree l1, Tree l2);
+Tree lrange(Tree l, int i, int j); // de i a j exclu
+
+// mapping
+Tree lmap (tfun f, Tree l);
+
+// Sets
+bool isElement (Tree e, Tree l);
+Tree addElement (Tree e, Tree l1);
+Tree remElement (Tree e, Tree l1);
+Tree singleton (Tree l);
+Tree list2set (Tree l);
+Tree setUnion (Tree l1, Tree l2);
+Tree setIntersection (Tree l1, Tree l2);
+Tree setDifference (Tree l1, Tree l2);
+
+// functions as set of pairs key x value
+Tree addFun(Tree k, Tree v, Tree l);
+bool getFun(Tree k, Tree& v, Tree l);
+
+// Pairs
+
+//inline Tree pair (Tree t1, Tree t2) { return cons(t1,t2); }
+inline Tree left (Tree t) { return t->branch(0); }
+inline Tree right (Tree t) { return t->branch(1); }
+
+
+// Environment : stack of pairs key value)
+Tree pushEnv (Tree key, Tree val, Tree env=nil);
+bool searchEnv (Tree key, Tree& v, Tree env);
+
+// Operations on the property list of a tree t
+void setProperty (Tree t, Tree key, Tree val);
+bool getProperty (Tree t, Tree key, Tree& val);
+void remProperty (Tree t, Tree key);
+
+// Mapping sur les arbres
+Tree tmap (Tree k, tfun f, Tree t);
+
+// remplacement
+Tree substitute (Tree t, Tree id, Tree val);
+
+
+#endif
projects / Faustine.git / blobdiff