list.cpp File Reference

#include <stdlib.h>
#include "list.hh"
#include <string>
#include <map>
#include "symbol.hh"
#include <iostream>
#include <vector>
#include <assert.h>
#include <stdio.h>
#include <unistd.h>
#include <cstdlib>
Include dependency graph for list.cpp:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

static bool printlist (Tree l, FILE *out)
void print (Tree t, FILE *out)
Tree nth (Tree l, int i)
Tree replace (Tree l, int i, Tree e)
int len (Tree l)
Tree rconcat (Tree l, Tree q)
Tree concat (Tree l, Tree q)
Tree lrange (Tree l, int i, int j)
static Tree rmap (tfun f, Tree l)
Tree reverse (Tree l)
Tree lmap (tfun f, Tree l)
Tree reverseall (Tree l)
bool isElement (Tree e, Tree l)
Tree addElement (Tree e, Tree l)
Tree remElement (Tree e, Tree l)
Tree singleton (Tree e)
Tree list2set (Tree l)
Tree setUnion (Tree A, Tree B)
Tree setIntersection (Tree A, Tree B)
Tree setDifference (Tree A, Tree B)
Tree pushEnv (Tree key, Tree val, Tree env)
bool searchEnv (Tree key, Tree &v, Tree env)
static bool findKey (Tree pl, Tree key, Tree &val)
static Tree updateKey (Tree pl, Tree key, Tree val)
static Tree removeKey (Tree pl, Tree key)
void setProperty (Tree t, Tree key, Tree val)
bool getProperty (Tree t, Tree key, Tree &val)
void remProperty (Tree t, Tree key)
Tree tmap (Tree key, tfun f, Tree t)
static Tree substkey (Tree t, Tree id, Tree val)
static Tree subst (Tree t, Tree propkey, Tree id, Tree val)
Tree substitute (Tree t, Tree id, Tree val)

Variables

Sym CONS = symbol("cons")
Sym NIL = symbol("nil")
Tree nil = tree(NIL)

Function Documentation

Tree addElement ( Tree  e,
Tree  l 
)

Definition at line 272 of file list.cpp.

References addElement(), cons(), hd(), isList(), and tl().

Referenced by addElement(), evalIdDef(), list2set(), and ppsig::printrec().

00273 {
00274     if (isList(l)) {
00275         if (e < hd(l)) {
00276             return cons(e,l);
00277         } else if (e == hd(l)) {
00278             return l;
00279         } else {
00280             return cons(hd(l), addElement(e,tl(l)));
00281         }
00282     } else {
00283         return cons(e,nil);
00284     }
00285 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree concat ( Tree  l,
Tree  q 
)

Definition at line 216 of file list.cpp.

References rconcat(), and reverse().

Referenced by applyList(), and sigCartesianProd().

00217 {
00218     return rconcat(reverse(l), q);
00219 }

Here is the call graph for this function:

Here is the caller graph for this function:

static bool findKey ( Tree  pl,
Tree  key,
Tree val 
) [static]

Definition at line 373 of file list.cpp.

References hd(), isNil(), left(), right(), and tl().

00374 {
00375     if (isNil(pl))              return false;
00376     if (left(hd(pl)) == key)    { val= right(hd(pl)); return true; }
00377     /*  left(hd(pl)) != key */  return findKey (tl(pl), key, val); 
00378 }

Here is the call graph for this function:

bool getProperty ( Tree  t,
Tree  key,
Tree val 
)

Definition at line 423 of file list.cpp.

References CTree::getProperty().

Referenced by addLayerDef(), annotate(), evalIdDef(), getBoxType(), getColorProperty(), Occurrences::getCount(), getDefFileProp(), getDefLineProp(), getDefNameProperty(), getEvalProperty(), getInferredType(), getNumericProperty(), getPMProperty(), getRecursivness(), ScalarCompiler::getSharingCount(), DocCompiler::getSharingCount(), getSigNickname(), getSigOrder(), privatisation(), searchIdDef(), shcount(), sigMap(), subst(), and tmap().

00424 {
00425     CTree* pl = t->getProperty(key);
00426     if (pl) {
00427         val = pl;
00428         return true;
00429     } else {
00430         return false;
00431     }
00432 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool isElement ( Tree  e,
Tree  l 
)

Definition at line 262 of file list.cpp.

References hd(), isList(), and tl().

00263 {
00264     while (isList(l)) {
00265         if (hd(l) == e) return true;
00266         if (hd(l) > e) return false;
00267         l = tl(l);
00268     }
00269     return false;
00270 }

Here is the call graph for this function:

int len ( Tree  l  ) 

Definition at line 198 of file list.cpp.

References isList(), and tl().

Referenced by checkRulelist(), evalCase(), ffarity(), DocCompiler::generateRec(), ScalarCompiler::generateRec(), make_pattern_matcher(), makeDefinition(), and Symbol::Symbol().

00199 {
00200     int     n = 0;
00201     while (isList(l)) { l = tl(l); n++; }
00202     return n;
00203 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree list2set ( Tree  l  ) 

Definition at line 307 of file list.cpp.

References addElement(), hd(), isList(), and tl().

00308 {
00309     Tree s = nil;
00310     while (isList(l)) {
00311         s = addElement(hd(l),s);
00312         l = tl(l);
00313     }
00314     return s;
00315 }

Here is the call graph for this function:

Tree lmap ( tfun  f,
Tree  l 
)

Definition at line 247 of file list.cpp.

References reverse(), and rmap().

00248 {
00249     return reverse(rmap(f,l));
00250 }

Here is the call graph for this function:

Tree lrange ( Tree  l,
int  i,
int  j 
)

Definition at line 221 of file list.cpp.

References cons(), and nth().

00222 {
00223     Tree    r = nil;
00224     int     c = j;
00225     while (c>i) r = cons( nth(l,--c), r);
00226     return r;
00227 }

Here is the call graph for this function:

Tree nth ( Tree  l,
int  i 
)

Definition at line 182 of file list.cpp.

References hd(), isList(), and tl().

Referenced by ffargtype(), ffname(), DocCompiler::generateFFun(), ScalarCompiler::generateFFun(), DocCompiler::generateRec(), ScalarCompiler::generateRec(), isBoxHSlider(), isBoxNumEntry(), isBoxVSlider(), isSigHSlider(), isSigNumEntry(), isSigVSlider(), and lrange().

00183 {
00184     while (isList(l)) {
00185         if (i == 0)  return hd(l);
00186         l = tl(l);
00187         i--;
00188     }
00189     return nil;
00190 }

Here is the call graph for this function:

Here is the caller graph for this function:

void print ( Tree  t,
FILE *  out 
)

Definition at line 154 of file list.cpp.

References CTree::arity(), CTree::branch(), isDouble(), isInt(), isPointer(), isSym(), name(), CTree::node(), print(), and printlist().

Referenced by addLayerDef(), evalerror(), evalremark(), evalwarning(), ScalarCompiler::generateCode(), generateInsideSchema(), infereSigOrder(), infereSigType(), print(), printlist(), printSignal(), and searchEnv().

00155 {
00156     int i; double f; Sym s; void* p;
00157     
00158     if (printlist(t, out))      return;
00159     
00160     Node n = t->node();
00161          if (isInt(n, &i))      fprintf (out, "%d", i);
00162     else if (isDouble(n, &f))   fprintf (out, "%f", f);
00163     else if (isSym(n, &s))      fprintf (out, "%s", name(s));
00164     else if (isPointer(n, &p))  fprintf (out, "#%p", p);
00165     
00166     int k = t->arity();
00167     if (k > 0) {
00168         char sep = '[';
00169         for (int i=0; i<k; i++) {
00170             fputc(sep, out); sep = ',';
00171             print(t->branch(i), out);
00172         }
00173         fputc(']', out);
00174     } 
00175 }

Here is the call graph for this function:

Here is the caller graph for this function:

static bool printlist ( Tree  l,
FILE *  out 
) [static]

Definition at line 123 of file list.cpp.

References hd(), isList(), isNil(), print(), and tl().

Referenced by print().

00124 {
00125     if (isList(l)) {
00126         
00127         char sep = '(';
00128         
00129         do {
00130             fputc(sep, out); sep = ',';
00131             print(hd(l));
00132             l = tl(l);
00133         } while (isList(l));
00134         
00135         if (! isNil(l)) {
00136             fprintf(out, " . ");
00137             print(l, out);
00138         }
00139         
00140         fputc(')', out);
00141         return true;
00142         
00143     } else if (isNil(l)) {
00144         
00145         fprintf(out, "nil");
00146         return true;
00147         
00148     } else {
00149         
00150         return false;
00151     }
00152 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree pushEnv ( Tree  key,
Tree  val,
Tree  env 
)

Definition at line 351 of file list.cpp.

References cons().

Referenced by propagate().

00352 {
00353     return cons (cons(key,val), env);
00354 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree rconcat ( Tree  l,
Tree  q 
)

Definition at line 210 of file list.cpp.

References cons(), hd(), isList(), and tl().

Referenced by concat().

00211 {
00212     while (isList(l)) { q = cons(hd(l),q); l = tl(l); }
00213     return q;
00214 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree remElement ( Tree  e,
Tree  l 
)

Definition at line 287 of file list.cpp.

References cons(), hd(), isList(), remElement(), and tl().

Referenced by remElement().

00288 {
00289     if (isList(l)) {
00290         if (e < hd(l)) {
00291             return l;
00292         } else if (e == hd(l)) {
00293             return tl(l);
00294         } else {
00295             return cons(hd(l), remElement(e,tl(l)));
00296         }
00297     } else {
00298         return nil;
00299     }
00300 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree removeKey ( Tree  pl,
Tree  key 
) [static]

Definition at line 387 of file list.cpp.

References cons(), hd(), isNil(), left(), and tl().

00388 {
00389     if (isNil(pl))              return nil;
00390     if (left(hd(pl)) == key)    return tl(pl);
00391     /*  left(hd(pl)) != key */  return cons (hd(pl), removeKey(tl(pl), key));
00392 }

Here is the call graph for this function:

void remProperty ( Tree  t,
Tree  key 
)

Definition at line 434 of file list.cpp.

00435 {
00436     exit(1); // fonction not implemented
00437 }

Tree replace ( Tree  l,
int  i,
Tree  e 
)

Definition at line 192 of file list.cpp.

References cons(), hd(), replace(), and tl().

Referenced by replace().

00193 {
00194     return (i==0) ? cons(e,tl(l)) : cons( hd(l), replace(tl(l),i-1,e) );
00195 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree reverse ( Tree  l  ) 

Definition at line 240 of file list.cpp.

References cons(), hd(), isList(), and tl().

Referenced by applyList(), collectDocEqns(), concat(), ScalarCompiler::generateButton(), ScalarCompiler::generateCheckbox(), ScalarCompiler::generateHBargraph(), ScalarCompiler::generateHSlider(), ScalarCompiler::generateNumEntry(), ScalarCompiler::generateVBargraph(), ScalarCompiler::generateVSlider(), DocCompiler::getUIDir(), lmap(), make_pattern_matcher(), printdoccontent(), and printPatternError().

00241 {
00242     Tree r = nil;
00243     while (isList(l)) { r = cons(hd(l),r); l = tl(l); }
00244     return r;
00245 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree reverseall ( Tree  l  ) 

Definition at line 252 of file list.cpp.

References isList(), reverseall(), and rmap().

Referenced by reverseall().

00253 {
00254     return isList(l) ? rmap(reverseall, l) : l;
00255 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree rmap ( tfun  f,
Tree  l 
) [static]

Definition at line 233 of file list.cpp.

References cons(), hd(), isList(), and tl().

Referenced by lmap(), and reverseall().

00234 {
00235     Tree r = nil;
00236     while (isList(l)) { r = cons(f(hd(l)),r); l = tl(l); }
00237     return r;
00238 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool searchEnv ( Tree  key,
Tree v,
Tree  env 
)

Definition at line 356 of file list.cpp.

References hd(), isList(), and tl().

00357 {
00358     while (isList(env)) {
00359         if (hd(hd(env)) == key) {
00360             v = tl(hd(env));
00361             return true;
00362         }
00363         env = tl(env);
00364     }
00365     return false;
00366 }

Here is the call graph for this function:

Tree setDifference ( Tree  A,
Tree  B 
)

Definition at line 336 of file list.cpp.

References cons(), hd(), isNil(), setDifference(), and tl().

Referenced by setDifference().

00337 {
00338     if (isNil(A))       return A;
00339     if (isNil(B))       return A;
00340     if (hd(A) == hd(B)) return setDifference(tl(A),tl(B));
00341     if (hd(A) < hd(B))  return cons(hd(A), setDifference(tl(A),B));
00342     /* (hd(A) > hd(B)*/ return setDifference(A,tl(B));
00343 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree setIntersection ( Tree  A,
Tree  B 
)

Definition at line 327 of file list.cpp.

References cons(), hd(), isNil(), setIntersection(), and tl().

Referenced by setIntersection().

00328 {
00329     if (isNil(A))       return A;
00330     if (isNil(B))       return B;
00331     if (hd(A) == hd(B)) return cons(hd(A), setIntersection(tl(A),tl(B)));
00332     if (hd(A) < hd(B))  return setIntersection(tl(A),B);
00333     /* (hd(A) > hd(B)*/ return setIntersection(A,tl(B));
00334 }

Here is the call graph for this function:

Here is the caller graph for this function:

void setProperty ( Tree  t,
Tree  key,
Tree  val 
)
Tree setUnion ( Tree  A,
Tree  B 
)

Definition at line 317 of file list.cpp.

References cons(), hd(), isNil(), setUnion(), and tl().

Referenced by realeval(), and setUnion().

00318 {
00319     if (isNil(A))       return B;
00320     if (isNil(B))       return A;
00321     
00322     if (hd(A) == hd(B)) return cons(hd(A), setUnion(tl(A),tl(B)));
00323     if (hd(A) < hd(B))  return cons(hd(A), setUnion(tl(A),B));
00324     /* hd(A) > hd(B) */ return cons(hd(B), setUnion(A,tl(B)));
00325 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree singleton ( Tree  e  ) 

Definition at line 302 of file list.cpp.

References list1().

00303 {
00304     return list1(e);
00305 }

Here is the call graph for this function:

static Tree subst ( Tree  t,
Tree  propkey,
Tree  id,
Tree  val 
) [static]

Definition at line 506 of file list.cpp.

References CTree::arity(), CTree::branch(), getProperty(), isNil(), CTree::node(), setProperty(), subst(), and tree().

00507 {
00508     Tree p;
00509     
00510     if (t==id) {
00511         return val;
00512         
00513     } else if (t->arity() == 0) {
00514         return t;
00515     } else if (getProperty(t, propkey, p)) {
00516         return (isNil(p)) ?  t : p;
00517     } else {
00518         Tree r=nil;
00519         switch (t->arity()) {
00520             
00521             case 1 : 
00522                 r = tree(t->node(), 
00523                             subst(t->branch(0), propkey, id, val)); 
00524                 break;
00525                 
00526             case 2 : 
00527                 r = tree(t->node(), 
00528                             subst(t->branch(0), propkey, id, val), 
00529                             subst(t->branch(1), propkey, id, val)); 
00530                 break;
00531                 
00532             case 3 : 
00533                 r = tree(t->node(), 
00534                             subst(t->branch(0), propkey, id, val), 
00535                             subst(t->branch(1), propkey, id, val), 
00536                             subst(t->branch(2), propkey, id, val)); 
00537                 break;
00538                 
00539             case 4 : 
00540                 r = tree(t->node(), 
00541                             subst(t->branch(0), propkey, id, val), 
00542                             subst(t->branch(1), propkey, id, val), 
00543                             subst(t->branch(2), propkey, id, val), 
00544                             subst(t->branch(3), propkey, id, val)); 
00545                 break;
00546             
00547         }
00548         if (r == t) {
00549             setProperty(t, propkey, nil);
00550         } else {
00551             setProperty(t, propkey, r);
00552         }
00553         return r;
00554     }
00555         
00556 }

Here is the call graph for this function:

Tree substitute ( Tree  t,
Tree  id,
Tree  val 
)

Definition at line 559 of file list.cpp.

References subst(), and substkey().

Referenced by calcDeBruijn2Sym(), and calcsubstitute().

00560 {
00561     return subst (t, substkey(t,id,val), id, val);
00562 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree substkey ( Tree  t,
Tree  id,
Tree  val 
) [static]

Definition at line 496 of file list.cpp.

References name(), tree(), and unique().

Referenced by substitute().

00497 {
00498     char    name[256];
00499     snprintf(name, 255, "SUBST<%p,%p,%p> : ", (CTree*)t, (CTree*)id, (CTree*)val);
00500     return tree(unique(name));
00501 }   

Here is the call graph for this function:

Here is the caller graph for this function:

Tree tmap ( Tree  key,
tfun  f,
Tree  t 
)

Definition at line 445 of file list.cpp.

References CTree::arity(), CTree::branch(), getProperty(), isNil(), CTree::node(), setProperty(), tmap(), and tree().

Referenced by tmap().

00446 {   
00447     //printf("start tmap\n");
00448     Tree p; 
00449     
00450     if (getProperty(t, key, p)) {
00451         
00452         return (isNil(p)) ? t : p;  // truc pour eviter les boucles
00453         
00454     } else {
00455         
00456         Tree r1=nil;
00457         switch (t->arity()) {
00458             
00459             case 0 : 
00460                 r1 = t; 
00461                 break;
00462             case 1 : 
00463                 r1 = tree(t->node(), tmap(key,f,t->branch(0))); 
00464                 break;
00465             case 2 : 
00466                 r1 = tree(t->node(), tmap(key,f,t->branch(0)), tmap(key,f,t->branch(1))); 
00467                 break;
00468             case 3 : 
00469                 r1 = tree(t->node(), tmap(key,f,t->branch(0)), tmap(key,f,t->branch(1)),
00470                                            tmap(key,f,t->branch(2))); 
00471                 break;
00472             case 4 : 
00473                 r1 = tree(t->node(), tmap(key,f,t->branch(0)), tmap(key,f,t->branch(1)),
00474                                            tmap(key,f,t->branch(2)), tmap(key,f,t->branch(3))); 
00475                 break;
00476         }
00477         Tree r2 = f(r1);
00478         if (r2 == t) {
00479             setProperty(t, key, nil);
00480         } else {
00481             setProperty(t, key, r2);
00482         }
00483         return r2;
00484     }
00485 }

Here is the call graph for this function:

Here is the caller graph for this function:

static Tree updateKey ( Tree  pl,
Tree  key,
Tree  val 
) [static]

Definition at line 380 of file list.cpp.

References cons(), hd(), isNil(), left(), and tl().

00381 {
00382     if (isNil(pl))              return cons ( cons(key,val), nil );
00383     if (left(hd(pl)) == key)    return cons ( cons(key,val), tl(pl) );
00384     /*  left(hd(pl)) != key */  return cons ( hd(pl), updateKey( tl(pl), key, val ));
00385 }

Here is the call graph for this function:


Variable Documentation

Sym CONS = symbol("cons")

Definition at line 112 of file list.cpp.

Tree nil = tree(NIL)
Sym NIL = symbol("nil")

Definition at line 113 of file list.cpp.

Generated on Thu Apr 29 00:00:07 2010 for FAUST compiler by  doxygen 1.6.3