interpreter/preprocessor/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