+++ /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