home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Examples / AppKit / Graph / Expression.m < prev    next >
Encoding:
Text File  |  1993-01-07  |  25.1 KB  |  836 lines
  1. /*
  2.     Expression.m
  3.  
  4.     The Expression class is implemented using a grammar generated by the Unix
  5.     program yacc, and a lexical scanner generated by the Unix program lex.
  6.     The only interface between these parsing modules and this class is the
  7.     function _EXPParseExpression, which actually performs the parse.  The
  8.     results of the parse are returned in two data structures: a parse tree
  9.     representing the expression and a hashtable which holds that variables
  10.     found in the expression.
  11.  
  12.     The parse tree's nodes are Term structs (declared in exprDefs.h).  There
  13.     is a node for each piece of the expression.  For example, when the
  14.     expression "A+5" is parsed, three nodes result.  The top node of the tree
  15.     represents the binary operator "+".  This top node has two subnodes.  The
  16.     first subnode represents the variable "A".  The second represents the
  17.     integer constant "5".  Since variables can appear more than once in an
  18.     expression, their nodes may occur more than once in the parse tree.
  19.     
  20.     A parse tree is evaluated by doing a depth first traversal of the tree,
  21.     bubbling up the results of each sub-tree until the final value rises
  22.     to the top.
  23.  
  24.     You may freely copy, distribute, and reuse the code in this example.
  25.     NeXT disclaims any warranty of any kind, expressed or implied, as to its
  26.     fitness for any particular use.
  27. */
  28.  
  29. #import "Graph.h"
  30.  
  31. /* declaration of methods static to this class */
  32. @interface Expression(ExpressionPrivate)
  33. - (int)_updateResults;
  34. - (EXPTermPtr)_addVarTerm:(const char *)name;
  35. @end
  36.  
  37. @implementation Expression
  38.  
  39. /* function which can be applied to parse tree nodes with applyToTerms() */
  40. typedef void ParseTreeFunc(void *info, Term *term);
  41.  
  42. static void freeContents(Expression *self);
  43. static void applyToTerms(Term *t, ParseTreeFunc *func, void *data, int mask);
  44. static void updateTerm(void *data, Term *t);
  45. static float evalTerm(Term *t, int *indices);
  46. static Term *termOfVar(Expression *self, const char *varName);
  47. static NXHashTable *makeBuiltInFuncTable(NXZone *zone);
  48. static NXHashTable *getBuiltInFuncs(void);
  49. static Function *addFuncTerm(NXHashTable *table, const char *name, int min, int max, EXPTermEvalFunc *func);
  50. static void safeFree(void **data);
  51. static EXPTermEvalFunc sinStub, cosStub, tanStub;
  52. static EXPTermEvalFunc asinStub, acosStub, atanStub;
  53. static EXPTermEvalFunc expStub, lnStub, sqrtStub, sumStub;
  54. static char *termName(const Term *t);
  55. static void FunctionFree(const void *info, void *data);
  56. static unsigned    VarTermHash(const void *info, const void *data);
  57. static int VarTermCompare(const void *info, const void *data1, const void *data2);
  58.  
  59. /*
  60.  * Shared table of built in functions.  All Expressions which haven't had
  61.  * any application functions added to them shared this table, which contains
  62.  * just the built in functions.
  63.  */
  64. static NXHashTable *BuiltInFuncTable = NULL;
  65.  
  66. /* data for a built in function */
  67. typedef struct _BuiltInFunc {
  68.     const char *name;        /* name of the function */
  69.     EXPTermEvalFunc *func;    /* proc to call for evaluation */
  70.     int minArgs;
  71.     int maxArgs;
  72. } BuiltInFunc;
  73.  
  74. /* table of built in functions */
  75. static const BuiltInFunc FuncList[] = {
  76.     {"sin", &sinStub, 1, 1},
  77.     {"cos", &cosStub, 1, 1},
  78.     {"tan", &tanStub, 1, 1},
  79.     {"asin", &asinStub, 1, 1},
  80.     {"acos", &acosStub, 1, 1},
  81.     {"atan", &atanStub, 1, 1},
  82.     {"exp", &expStub, 1, 1},
  83.     {"ln", &lnStub, 1, 1},
  84.     {"sqrt", &sqrtStub, 1, 1},
  85.     {"sum", &sumStub, 1, -1}
  86. };
  87.  
  88. #define NUM_BUILTIN_FUNCS    (sizeof(FuncList)/sizeof(BuiltInFunc))
  89.  
  90. /* prototype used to create hashtables of variable terms */
  91. static NXHashTablePrototype VarTermProto = {&VarTermHash, &VarTermCompare, (void (*)(const void *info, void *data))&_EXPFreeTerm, 0};
  92.  
  93. - init {
  94.     [super init];
  95.     resolution = 1;
  96.     dimensions = 1;
  97.     varTerms = NXCreateHashTableFromZone(VarTermProto, 0, NULL, [self zone]);
  98.     return self;
  99. }
  100.  
  101. - free {
  102.     freeContents(self);
  103.   /* if we have a function table and its not the shared one */
  104.     if (validFuncs && validFuncs != BuiltInFuncTable)
  105.     NXFreeHashTable(validFuncs);
  106.     return [super free];
  107. }
  108.  
  109. - (BOOL)parse:(const char *)expressionString {
  110.     NXZone *zone;
  111.  
  112.     zone = [self zone];
  113.   /* clear away any results from a previous parse */
  114.     freeContents(self);
  115.     varTerms = NXCreateHashTableFromZone(VarTermProto, 0, NULL, zone);
  116.     resultsValid = NO;
  117.     text = NXCopyStringBufferFromZone(expressionString, zone);
  118.     if (!validFuncs)
  119.     validFuncs = getBuiltInFuncs();
  120.     return _EXPParseExpression(text, validFuncs, &parseTree, varTerms, zone);
  121. }
  122.  
  123. - (const char *)text {
  124.     return text;
  125. }
  126.  
  127. - setResolution:(int)count {
  128.     if (resolution != count) {
  129.       /*
  130.        * Changing the resolution means we have to recalculate next time
  131.        * we're asked for results
  132.        */
  133.     resultsValid = NO;
  134.     resolution = count;
  135.     }
  136.     return self;
  137. }
  138.  
  139. - (int)resolution {
  140.     return resolution;
  141. }
  142.  
  143. - setVar:(const char *)varName value:(float)val {
  144.     Term *t;
  145.  
  146.     t = termOfVar(self, varName);
  147.     if (!t)
  148.     t = [self _addVarTerm:varName];
  149.   /*
  150.    * If the term was previously a vector term, we change it to a variable
  151.    * term (one that has a single value).
  152.    */
  153.     if (t->tag == vectorTerm) {
  154.     t->tag = varTerm;
  155.     safeFree((void **)&t->data.vector.vals);
  156.     t->data.var.name = t->data.vector.name;
  157.     resultsValid = NO;
  158.     }
  159.     NX_ASSERT(t->tag == varTerm, "Invalid term type in setVar:value:");
  160.     if (t->data.var.val != val) {
  161.     t->data.var.val = val;
  162.     resultsValid = NO;        /* must recalc after a var is set */
  163.     }
  164.     return self;
  165. }
  166.  
  167. - (float)varValue:(const char *)varName {
  168.     Term *t;
  169.  
  170.     t = termOfVar(self, varName);
  171.     if (t) {
  172.     if (t->tag == varTerm)
  173.         return t->data.var.val;
  174.     else
  175.         NX_RAISE(expErrInvalidVarType, self, (void *)varName);
  176.     } else
  177.     NX_RAISE(expErrInvalidVarName, self, (void *)varName);
  178. }
  179.  
  180. - setVar:(const char *)varName vector:(float *)vals numVals:(int)count {
  181.     Term *t;
  182.  
  183.     resultsValid = NO;
  184.     t = termOfVar(self, varName);
  185.     if (!t)
  186.     t = [self _addVarTerm:varName];
  187.   /*
  188.    * If the term was previously a non-vector variable, we change it to a
  189.    * vector variable term.
  190.    */
  191.     if (t->tag == varTerm) {
  192.     t->tag = vectorTerm;
  193.     t->data.vector.name = t->data.var.name;
  194.     t->data.vector.hasRange = NO;
  195.     t->data.vector.vals = NULL;
  196.     t->data.vector.resolution = 0;
  197.     t->data.vector.dimension = 0;
  198.     }
  199.     NX_ASSERT(t->tag == vectorTerm, "Invalid term type in setVar:vector:");
  200.     safeFree((void **)&t->data.vector.vals);
  201.     t->data.vector.resolution = count;
  202.     t->data.vector.vals = vals;
  203.     t->data.vector.changed = YES;
  204.     resolution = count;
  205.     return self;
  206. }
  207.  
  208. - varVector:(const char *)varName vector:(float **)vals numVals:(int *)count {
  209.     Term *t;
  210.  
  211.     t = termOfVar(self, varName);
  212.     if (t) {
  213.     if (t->tag == vectorTerm) {
  214.         updateTerm(self, t);
  215.         *count = t->data.vector.resolution;
  216.         *vals = t->data.vector.vals;
  217.     } else
  218.         NX_RAISE(expErrInvalidVarType, self, (void *)varName);
  219.     } else
  220.         NX_RAISE(expErrInvalidVarName, self, (void *)varName);
  221.     return self;
  222. }
  223.  
  224. - setVar:(const char *)varName min:(float)minVal max:(float)maxVal {
  225.     Term *t;
  226.  
  227.     if (minVal > maxVal)
  228.     NX_RAISE(expErrMinMax, self, NULL);
  229.     t = termOfVar(self, varName);
  230.     if (!t)
  231.     t = [self _addVarTerm:varName];
  232.   /*
  233.    * If the term was previously a non-vector variable, we change it to a
  234.    * vector variable term.
  235.    */
  236.     if (t->tag == varTerm) {
  237.     t->tag = vectorTerm;
  238.     t->data.vector.name = t->data.var.name;
  239.     t->data.vector.hasRange = YES;
  240.     t->data.vector.vals = NULL;
  241.     t->data.vector.changed = YES;
  242.     t->data.vector.dimension = 0;
  243.     }
  244.     NX_ASSERT(t->tag == vectorTerm, "Invalid term type in setVar:min:max:");
  245.  
  246.   /*
  247.    * We optimize and do nothing if the passed values are the same as our
  248.    * current values.
  249.    */
  250.     if (t->data.vector.changed || t->data.vector.min != minVal || t->data.vector.max != maxVal) {
  251.     safeFree((void **)&t->data.vector.vals);
  252.     t->data.vector.resolution = 0;
  253.     t->data.vector.min = minVal;
  254.     t->data.vector.max = maxVal;
  255.     t->data.vector.changed = YES;
  256.     resultsValid = NO;
  257.     }    
  258.     return self;
  259. }
  260.  
  261. - var:(const char *)varName min:(float *)minVal max:(float *)maxVal {
  262.     Term *t;
  263.  
  264.     t = termOfVar(self, varName);
  265.     if (t) {
  266.     if (t->tag == vectorTerm) {
  267.         updateTerm(self, t);
  268.         *minVal = t->data.vector.min;
  269.         *maxVal = t->data.vector.max;
  270.     } else
  271.         NX_RAISE(expErrInvalidVarType, self, (void *)varName);
  272.     } else
  273.         NX_RAISE(expErrInvalidVarName, self, (void *)varName);
  274.     return self;
  275. }
  276.  
  277. - setVar:(const char *)varName dimension:(short)dimensionNum {
  278.     Term *t;
  279.  
  280.     if (dimensionNum < 0 || dimensionNum >= dimensions)
  281.     NX_RAISE(expInvalidDimension, self, (void *)varName);
  282.     resultsValid = NO;
  283.     t = termOfVar(self, varName);
  284.     if (!t)
  285.     t = [self _addVarTerm:varName];
  286.   /*
  287.    * If the term was previously a non-vector variable, we change it to a
  288.    * vector variable term.
  289.    */
  290.     if (t->tag == varTerm) {
  291.     t->tag = vectorTerm;
  292.     t->data.vector.name = t->data.var.name;
  293.     t->data.vector.hasRange = YES;
  294.     t->data.vector.vals = NULL;
  295.     t->data.vector.changed = YES;
  296.     t->data.vector.dimension = 0;
  297.     }
  298.     NX_ASSERT(t->tag == vectorTerm, "Invalid term type in setVar:dimension:");
  299.     t->data.vector.dimension = dimensionNum;
  300.     return self;
  301. }
  302.  
  303. - var:(const char *)varName dimension:(short *)dimensionNum {
  304.     Term *t;
  305.  
  306.     t = termOfVar(self, varName);
  307.     if (t) {
  308.     if (t->tag == vectorTerm)
  309.         *dimensionNum = t->data.vector.dimension;
  310.     else
  311.         NX_RAISE(expErrInvalidVarType, self, (void *)varName);
  312.     } else
  313.         NX_RAISE(expErrInvalidVarName, self, (void *)varName);
  314.     return self;
  315. }
  316.  
  317. - (float)resultValue {
  318.     [self _updateResults];
  319.     return *results;
  320. }
  321.  
  322. - resultsVector:(float **)vals numVals:(int *)count {
  323.     *count = [self _updateResults];
  324.     *vals = results;
  325.     return self;
  326. }
  327.  
  328. - resultsMin:(float *)minVal max:(float *)maxVal {
  329.     [self _updateResults];
  330.     *minVal = resultsMin;
  331.     *maxVal = resultsMax;
  332.     return self;
  333. }
  334.  
  335. - setDimensions:(short)count {
  336.     if (dimensions != count)
  337.     resultsValid = NO;
  338.     dimensions = count;
  339.     return self;
  340. }
  341.  
  342. - (short)dimensions {
  343.     return dimensions;
  344. }
  345.  
  346. /*
  347.  * Since the varables are all in a NXHashTable, we just use the NXHashTable
  348.  * functions to enumerate through the names of the variables.
  349.  */
  350.  
  351. - (EXPEnumState)beginVariableEnumeration {
  352.     NXHashState *state;
  353.  
  354.     state = NXZoneMalloc([self zone], sizeof(NXHashState));
  355.     *state = NXInitHashState(varTerms);
  356.     return state;
  357. }
  358.  
  359. - (const char *)nextVariable:(EXPEnumState)state {
  360.     const Term *t;
  361.  
  362.     if (NXNextHashState(varTerms, (NXHashState *)state, (void **)&t))
  363.     return termName(t);
  364.     else
  365.     return NULL;
  366. }
  367.  
  368. - (void)endVariableEnumeration:(EXPEnumState)state {
  369.     free(state);
  370. }
  371.  
  372. - addFuncTerm:(const char *)name minArgs:(int)min maxArgs:(int)max
  373.                     evalFunc:(EXPTermEvalFunc *)func {
  374.     Function *existingType;
  375.  
  376.   /*
  377.    * If we dont have a function table yet, get one.  If we do have one, but
  378.    * its the shared built in table, get a new one that we can safely modify.
  379.    */
  380.     if (!validFuncs || validFuncs == BuiltInFuncTable)
  381.     validFuncs = makeBuiltInFuncTable([self zone]);
  382.     existingType = addFuncTerm(validFuncs, name, min, max, func);
  383.     if (existingType)
  384.     NX_RAISE(expFuncTypeInUse, self, existingType);
  385.     return self;
  386. }
  387.  
  388. - removeFuncTerm:(const char *)name {
  389.     Function *realFunc;
  390.     Function key;
  391.  
  392.     if (validFuncs) {
  393.       /* look up the func term by name in our table of functions */
  394.     key.name = (char *)name;
  395.     if (realFunc = NXHashGet(validFuncs, &key)) {
  396.       /*
  397.        * If we are using the shared table of built ins, get a new table
  398.        * that we can safely modify (this covers the case of someone
  399.        * wishing to remove a built in function, possibly to redefine it).
  400.        */
  401.         if (validFuncs == BuiltInFuncTable) {
  402.         validFuncs = makeBuiltInFuncTable([self zone]);
  403.         realFunc = NXHashGet(validFuncs, &key);
  404.         }
  405.         NXHashRemove(validFuncs, realFunc);
  406.         free(realFunc);
  407.         return self;
  408.     }
  409.     }
  410.     return self;
  411. }
  412.  
  413. /*
  414.  * This is a utililty routine that recursively applies a function to all
  415.  * terms of a parse tree. data is a blind pointer that is simply passed
  416.  * along through the function call.  The function is only called on terms
  417.  * whose type match the given mask.
  418.  */
  419. static void applyToTerms(Term *t, ParseTreeFunc *func, void *data, int mask) {
  420.     int i;
  421.     Term **tPtr;
  422.  
  423.     for (i = t->numSubterms, tPtr = t->subterms; i--; tPtr++)
  424.     applyToTerms(*tPtr, func, data, mask);
  425.     if (t->tag & mask)
  426.     (*func)(data, t);
  427. }
  428.  
  429. /*
  430.  * Empties the contents of the Expression.  Since the variable terms can
  431.  * exist multiple times in the tree, we first run through the tree and
  432.  * free all the nodes except that variable nodes.  Then we free the hash
  433.  * table of variable terms, including the terms themselves. 
  434.  */
  435. static void freeContents(Expression *self) {
  436.     safeFree((void **)&self->text);
  437.   /* free the non-variable terms */
  438.     if (self->parseTree)
  439.     applyToTerms(self->parseTree, _EXPFreeTerm, NULL, ~(varTerm|vectorTerm));
  440.   /* free the shared variable terms */
  441.     NXFreeHashTable(self->varTerms);
  442.     safeFree((void **)&self->results);
  443. }
  444.  
  445. /*
  446.  * Allocates a new term of the given type, with room for subterms.  The
  447.  * subterms themselves follow as a variable number of arguments.  The are
  448.  * copied into the subterms list of the new term.
  449.  */
  450. Term *_EXPAllocTerm(NXZone *zone, TermTag tag, int numSubterms, ...) {
  451.     Term *t;
  452.     int i;
  453.     va_list args;
  454.  
  455.     t = NXZoneCalloc(zone, sizeof(Term) + (numSubterms-1) * sizeof(Term *), 1);
  456.     t->tag = tag;
  457.     t->numSubterms = numSubterms;
  458.     va_start(args, numSubterms);
  459.     for (i = 0; i < numSubterms; i++)
  460.     t->subterms[i] = va_arg(args, Term *);
  461.     va_end(args);
  462.     return t;
  463. }
  464.  
  465. /*
  466.  * Frees a term and any associated data.  This routine can be used as the
  467.  * free function of a NXHashTable prototype, or as a proc passed to
  468.  * applyToTerms().
  469.  */
  470. void _EXPFreeTerm(void *info, Term *data) {
  471.     Term *t = (Term *)data;
  472.  
  473.     if (t->tag == vectorTerm) {
  474.     free(t->data.vector.vals);
  475.     free(t->data.vector.name);
  476.     } else if (t->tag == varTerm)
  477.     free(t->data.var.name);
  478.     free(t);
  479. }
  480.  
  481. /*
  482.  * Makes sure a term is up to date.  Since terms recalculate any internal
  483.  * state lazily, this must be called before making use of a term's value.
  484.  * We apply this function recursively to all terms before evaluating an
  485.  * Expression, and apply to any term if we are asked to return the values
  486.  * held within the term (for example, from -varVector:vector:numVals:).
  487.  */
  488. static void updateTerm(void *data, Term *t) {
  489.     Expression *self = data;
  490.  
  491.     if (t->tag != vectorTerm)
  492.     return;        /* only vector terms require work to stay up to date */
  493.  
  494.   /* Ensure this term has the same resolution as the rest of the Expression. */ 
  495.     if (self->resolution != t->data.vector.resolution) {
  496.       /*
  497.        * We can change its resolution if we interpolate values for this term
  498.        * within a range.  Else if we were passed a list of values for this
  499.        * term, its an exception if the resolution is no longer in sync.
  500.        */
  501.     if (t->data.vector.hasRange) {
  502.         safeFree((void **)&t->data.vector.vals);
  503.         t->data.vector.vals = NXZoneMalloc([self zone],
  504.                     self->resolution * sizeof(float));
  505.         t->data.vector.resolution = self->resolution;
  506.         t->data.vector.changed = YES;    /* remember to re-interpolate */
  507.     } else
  508.         NX_RAISE(expErrResolutionMismatch, self,
  509.                     (void *)t->data.vector.name);
  510.     }
  511.  
  512.     if (t->data.vector.changed) {
  513.     if (t->data.vector.hasRange) {
  514.       /* interpolate a list of values between min and max */
  515.         int i;
  516.         float delta;
  517.         float *val, *prevVal;
  518.  
  519.         i = self->resolution - 1;
  520.         if (i) {
  521.         delta = (t->data.vector.max - t->data.vector.min) / i;
  522.         prevVal = t->data.vector.vals;
  523.         *prevVal = t->data.vector.min;
  524.         val = prevVal + 1;
  525.         while (i--)
  526.             *val++ = *prevVal++ + delta;
  527.         *(val-1) = t->data.vector.max;    /* to be sure we hit max */
  528.         } else
  529.         *t->data.vector.vals = t->data.vector.min;
  530.     } else {
  531.       /* scan the list of values passed in to find the min and max */
  532.         int i;
  533.         float newMin, newMax;
  534.         float *val;
  535.  
  536.         val = t->data.vector.vals;
  537.         newMin = newMax = *val++;
  538.         for (i = t->data.vector.resolution; i--; val++) {
  539.         if (*val > newMax)
  540.             newMax = *val;
  541.         else if (*val < newMin)
  542.             newMin = *val;
  543.         }
  544.         t->data.vector.min = newMin;
  545.         t->data.vector.max = newMax;
  546.     }
  547.     t->data.vector.changed = NO;    /* we're now up to date */
  548.     }
  549. }
  550.  
  551. /*
  552.  * Ensures that the results calculated for this Expression are up to date.
  553.  * We first make sure all the terms in the parse tree are up to date by
  554.  * applying updateTerm() to all of them.  We then evaluate the Expression
  555.  * for every n times, depending on the resolution, storing all the results
  556.  * and calculating their min and max. 
  557.  */
  558. - (int)_updateResults {
  559. #define MAX_INDICES 10
  560.     int i, j;
  561.     float *f;
  562.     int indicesBuffer[MAX_INDICES];
  563.     int *indices = indicesBuffer;
  564.     int totalVals;
  565.     NXZone *zone = [self zone];
  566.  
  567.     totalVals = resolution;
  568.     for (i = 1; i < dimensions; i++)
  569.     totalVals *= resolution;
  570.     if (!resultsValid) {
  571.     if (parseTree) {
  572.         applyToTerms(self->parseTree, updateTerm, self, -1);
  573.         safeFree((void **)&results);
  574.         results = NXZoneMalloc(zone, sizeof(float) * totalVals);
  575.         if (dimensions > MAX_INDICES)
  576.         indices = NXZoneMalloc(zone, sizeof(int) * dimensions);
  577.         bzero(indices, sizeof(int) * dimensions);
  578.         *results = evalTerm(parseTree, indices);
  579.         resultsMin = *results;
  580.         resultsMax = *results;
  581.         for (i = 1, f = results + 1; i < totalVals; i++, f++) {
  582.  
  583.           /*
  584.            * Increment the indices.  The first one always changes.  The
  585.            * others change only when the previous one wraps around (like
  586.            * an odometer with base = resolution).
  587.            */
  588.         for (j = 0; j < dimensions; j++) {
  589.             indices[j] = (indices[j] + 1) % resolution;
  590.             if (indices[j])
  591.             break;
  592.         }
  593.  
  594.           /*
  595.            * We pass the loop indices down through the evaluation recursion
  596.            * so vector terms can know which element of their vectors they
  597.            * should use for this evaluation.
  598.            */
  599.         *f = evalTerm(parseTree, indices);
  600.         if (*f > resultsMax)
  601.             resultsMax = *f;
  602.         else if (*f < resultsMin)
  603.             resultsMin = *f;
  604.         }
  605.         if (dimensions > MAX_INDICES)
  606.         NXZoneFree(zone, indices);
  607.     } else
  608.         NX_RAISE(expErrNoText, self, NULL);
  609.     resultsValid = YES;
  610.     }
  611.     return totalVals;
  612. }
  613.  
  614. #define MAX_ARGS    50
  615.  
  616. /*
  617.  * Evaluates a particular term.  In order to evaluate itself, any term with
  618.  * subterms must recursively evaluate those first.
  619.  */
  620. static float evalTerm(Term *t, int *indices) {
  621.     float result = 0.0;        /* initted to quiet -Wall */
  622.     float base;
  623.     float argsBuffer[MAX_ARGS];
  624.     float *args;
  625.     int i;
  626.  
  627.     switch (t->tag) {
  628.     case constantTerm:
  629.         NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
  630.         result = t->data.constant.val;
  631.         break;
  632.     case varTerm:
  633.         NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
  634.         result = t->data.var.val;
  635.         break;
  636.     case vectorTerm:
  637.         NX_ASSERT(t->numSubterms == 0, "Wrong #subterms in evalTerm");
  638.         result = t->data.vector.vals[indices[t->data.vector.dimension]];
  639.         break;
  640.     case binOpTerm:
  641.         NX_ASSERT(t->numSubterms == 2 ||
  642.             (t->data.binOp.op == '-' && t->numSubterms == 1),
  643.                     "Wrong #subterms in evalTerm");
  644.         switch (t->data.binOp.op) {
  645.         case '+':
  646.             result = evalTerm(t->subterms[0], indices) +
  647.                 evalTerm(t->subterms[1], indices);
  648.             break;
  649.         case '-':
  650.             if (t->numSubterms == 2)
  651.             result = evalTerm(t->subterms[0], indices) -
  652.                     evalTerm(t->subterms[1], indices);
  653.             else
  654.             result = - evalTerm(t->subterms[0], indices);
  655.             break;
  656.         case '*':
  657.             result = evalTerm(t->subterms[0], indices) *
  658.                 evalTerm(t->subterms[1], indices);
  659.             break;
  660.         case '/':
  661.             result = evalTerm(t->subterms[0], indices) /
  662.                 evalTerm(t->subterms[1], indices);
  663.             break;
  664.         case '%':
  665.             result = (int)rint(evalTerm(t->subterms[0], indices)) %
  666.                 (int)rint(evalTerm(t->subterms[1], indices));
  667.             break;
  668.         case '^':
  669.           /* optimize for raising to an integral power */
  670.             if (t->subterms[1]->tag == constantTerm &&
  671.                 t->subterms[1]->data.constant.isInt &&
  672.                 t->subterms[1]->data.constant.val >= 1) {
  673.             result = base = evalTerm(t->subterms[0], indices);
  674.             for (i = t->subterms[1]->data.constant.val; --i; )
  675.                 result *= base;
  676.             } else
  677.             result = pow(evalTerm(t->subterms[0], indices),
  678.                     evalTerm(t->subterms[1], indices));
  679.             break;
  680.         default:
  681.             NX_ASSERT(FALSE, "Unknown binary op type in evalTerm");
  682.         }
  683.         break;
  684.     case funcTerm:
  685.       /*
  686.        * For functions, we first ensure we have a large enough buffer
  687.        * for the values of all the arguments.  If there are few enough
  688.        * arguments, we use a buffer on the stack instead of thrashing
  689.        * the heap.  We then buffer up all the results of evaluating
  690.        * the arguments, and then pass this array of argument values
  691.        * to the proc that we use to evaluate this type of function.
  692.        */
  693.         if (t->numSubterms > MAX_ARGS)
  694.         args = NXZoneMalloc(NXDefaultMallocZone(),
  695.                     sizeof(float) * t->numSubterms);
  696.         else
  697.         args = argsBuffer;
  698.         for (i = 0; i < t->numSubterms; i++)
  699.         args[i] = evalTerm(t->subterms[i], indices);
  700.         result = t->data.func.type->evalFunc(t->numSubterms, args);
  701.             if (t->numSubterms > MAX_ARGS)
  702.         NXZoneFree(NXDefaultMallocZone(), args);
  703.         break;
  704.     default:
  705.         NX_ASSERT(FALSE, "Invalid term type in evalTerm");
  706.     }
  707.     return result;
  708. }
  709.  
  710. /* Utility routine to look up a variable by name in the variable hashtable. */
  711. static Term *termOfVar(Expression *self, const char *varName) {
  712.     Term key;
  713.  
  714.     if (self->parseTree) {
  715.     key.tag = varTerm;
  716.     key.data.var.name = (char *)varName;
  717.     return NXHashGet(self->varTerms, &key);
  718.     } else
  719.     NX_RAISE(expErrNoText, self, NULL);
  720. }
  721.  
  722. /* adds a variable term to the Expressions hashtable of them */
  723. - (Term *)_addVarTerm:(const char *)name {
  724.     Term *newTerm;
  725.     Term *existingTerm;
  726.  
  727.     newTerm = _EXPAllocTerm([self zone], varTerm, 0);
  728.     newTerm->data.var.name = NXCopyStringBufferFromZone(name, [self zone]);
  729.     existingTerm = NXHashInsertIfAbsent(varTerms, newTerm);
  730.     NX_ASSERT(existingTerm == newTerm, "_addVarTerm: called with existing term");
  731.     return newTerm;
  732. }
  733.  
  734. /* frees some storage, NULL'ing out the pointer */
  735. static void safeFree(void **data) {
  736.     free(*data);
  737.     *data = NULL;
  738. }
  739.  
  740. /* free function used in the NXHashTable prototype for functions */
  741. static void FunctionFree(const void *info, void *data) {
  742.     free(((Function *)data)->name);
  743.     free(data);
  744. }
  745.  
  746. /*
  747.  * Adds a func term to a HashTable of them.  Returns any existing entry
  748.  * with the same name, else NULL.
  749.  */
  750. static Function *addFuncTerm(NXHashTable *table, const char *name, int min, int max, EXPTermEvalFunc *func) {
  751.     Function *newFunc;
  752.     Function *existingType;
  753.  
  754.     newFunc = NXZoneMalloc(NXZoneFromPtr(table), sizeof(Function));
  755.     newFunc->name = NXCopyStringBufferFromZone(name, NXZoneFromPtr(table));
  756.     newFunc->minArgs = min;
  757.     newFunc->maxArgs = max;
  758.     newFunc->evalFunc = func;
  759.     existingType = NXHashInsertIfAbsent(table, newFunc);
  760.     if (existingType != newFunc)
  761.     return existingType;
  762.     else
  763.     return NULL;
  764. }
  765.  
  766. /*
  767.  * Returns a global table of all built in functions.  This table is shared
  768.  * by expressions that dont have application functions added to them.
  769.  */
  770. static NXHashTable *getBuiltInFuncs(void) {
  771.     if (!BuiltInFuncTable)
  772.     BuiltInFuncTable = makeBuiltInFuncTable(NXDefaultMallocZone());
  773.     return BuiltInFuncTable;
  774. }
  775.  
  776. /* Returns a new hashtable of all built in functions. */
  777. static NXHashTable *makeBuiltInFuncTable(NXZone *zone) {
  778.     NXHashTable *table;
  779.     NXHashTablePrototype FuncTermProto;
  780.     const BuiltInFunc *bif;
  781.     int i;
  782.  
  783.     FuncTermProto = NXStrStructKeyPrototype;
  784.     FuncTermProto.free = FunctionFree;
  785.     table = NXCreateHashTableFromZone(FuncTermProto, NUM_BUILTIN_FUNCS,
  786.                                 NULL, zone);
  787.     for (i = NUM_BUILTIN_FUNCS, bif = FuncList; i--; bif++)
  788.     (void)addFuncTerm(table, bif->name, bif->minArgs, bif->maxArgs, bif->func);
  789.     return table;
  790. }
  791.  
  792. /* Returns the name of a term. */
  793. static char *termName(const Term *t) {
  794.     switch (t->tag) {
  795.     case varTerm:
  796.         return t->data.var.name;
  797.     case vectorTerm:
  798.         return t->data.vector.name;
  799.     default:
  800.         NX_ASSERT(FALSE, "Bogus term type in VarTermHash");
  801.         return NULL;
  802.     }
  803. }
  804.  
  805. /* hashing function for variable terms.  Used in hashtable prototypes. */
  806. static unsigned    VarTermHash(const void *info, const void *data) {
  807.     return NXStrHash(info, termName(data));
  808. }
  809.  
  810. /* comparison function for variable terms.  Used in hashtable prototypes. */
  811. static int VarTermCompare(const void *info, const void *data1, const void *data2) {
  812.     return NXStrIsEqual(info, termName(data1), termName(data2));
  813. }
  814.  
  815. @end
  816.  
  817. /* These procs implement the built in functions */
  818.  
  819. static float sinStub(int numArgs, float *arg)    { return sin(*arg); }
  820. static float cosStub(int numArgs, float *arg)    { return cos(*arg); }
  821. static float tanStub(int numArgs, float *arg)    { return tan(*arg); }
  822. static float asinStub(int numArgs, float *arg)    { return asin(*arg); }
  823. static float acosStub(int numArgs, float *arg)    { return acos(*arg); }
  824. static float atanStub(int numArgs, float *arg)    { return atan(*arg); }
  825. static float expStub(int numArgs, float *arg)    { return exp(*arg); }
  826. static float lnStub(int numArgs, float *arg)    { return log(*arg); }
  827. static float sqrtStub(int numArgs, float *arg)    { return sqrt(*arg); }
  828.  
  829. static float sumStub(int numArgs, float *arg) {
  830.     float sum = 0.0;
  831.  
  832.     while (numArgs--)
  833.     sum += *arg++;
  834.     return sum;
  835. }
  836.