DataFunc.cpp

Go to the documentation of this file.

//DataFunc.cpp

/*************************************************************/
//
// CDataFunc
//
// Function parser and evaluator
//
//-------------------------------------------------------------
//
// v 1.7 - 2007/03/27 - Top hat
// v 1.6 - 2007/02/07 - More trig and log functions
// v 1.5 - 2007/02/01 - Heavyside functions
// v 1.4 - 2007/01/13 - Added comma to end of variable list
// v 1.3 - 2006/11/17 - Fixed '-' presidence and ',' argument separator
// v 1.2 - 2006/08/21 - Rewrote Infix -> RPN converter
// v 1.1 - 2006/08/18 - Added plane equation
// v 1.0 - 2006/04/19 - Initial release
//
// See LICENSE.txt for distribution and usage restrictions
// Copyright (c) 2005-2007 Simon Chorley
// www.mylaboratory.co.uk - greylab@mylaboratory.co.uk
//
/*************************************************************/


///Function parser and evaluator (Implementation)
/**
 * Provides implementation of CDataFunc function parser and evaluator to process the data.
 * @file DataFunc.cpp
 * @version 1.7 - 2007/03/27
 */


#include "DataFunc.h"

#include <string>
#include <cmath>
#include <iostream>


CDataFunc::op *(CDataFunc::ops) = NULL;         ///<List of operators.
int CDataFunc::nOps = 0;                                        ///<Number of operators.
int CDataFunc::instances = 0;                           ///<Number of instances of this class.


#define BUILDOP(str, pres, lass, arg) ops[i].tag = new char[strlen(str)+1]; \
        strcpy(ops[i].tag, str); \
        ops[i].tag[strlen(str)] = '\0'; \
        ops[i].precedence = pres; \
        ops[i].lassociative = lass; \
        ops[i].args = arg; \
        ++i;

///Initialise CDataFunc
/**
 * If there are no instances of the class then the array of available operators is built.
 */
CDataFunc::CDataFunc()
{
        valid = true;
        nValues = 0;
        nQueue = 0;
        values = NULL;
        queue = NULL;
        if (instances == 0)
        {
                int i = 0;
                ops = new op[100];
//Build list of acceptable tokens
//=================================================================
//       String         Prese.  LAsso.  Args.   Name
//=================================================================
BUILDOP("r",            -1,             true,   0)      //Result
BUILDOP("(",            12,             false,  0)      //Parentheses
BUILDOP(")",            11,             true,   0)      //Parentheses
//BUILDOP(",",          10,             true,   0)      //Argument separator
BUILDOP("v",            -1,             true,   0)      //Value (a number)
BUILDOP("-",            1,              true,   2)      //Subtract
BUILDOP("+",            1,              true,   2)      //Add
BUILDOP("*",            3,              true,   2)      //Multiply
BUILDOP("/",            3,              true,   2)      //Divide
BUILDOP("^",            4,              false,  2)      //Power
BUILDOP("exp",          5,              false,  1)      //Exponential
BUILDOP("cos",          6,              false,  1)      //Cosine
BUILDOP("sin",          6,              false,  1)      //Sine
BUILDOP("tan",          6,              false,  1)      //Tangent
BUILDOP("pi",           -1,             true,   0)      //Pi
BUILDOP("x",            -1,             true,   0)      //x channel value
BUILDOP("y",            -1,             true,   0)      //Sweep variable value
BUILDOP("z",            -1,             true,   0)      //Data point
BUILDOP("abs",          6,              false,  1)      //Absolute
BUILDOP("blend",        6,              false,  3)      //Blend (a,b,x) - blend a*(1-x)+bx
BUILDOP("clamp",        6,              false,  3)      //Clamp (x,a,b) - clamp x to range a->b
BUILDOP("large",        6,              false,  2)      //Large (x,y) - larger of x and y
BUILDOP("small",        6,              false,  2)      //Small (x,y) - smaller of x and y
BUILDOP("select",       6,              false,  4)      //Select (x,y,z,a) - select x if z <= a else y
BUILDOP("int",          6,              false,  1)      //Integer
BUILDOP("col",          9,              false,  1)      //Column data point
BUILDOP("plane",        6,              false,  4)      //Z height on plane given by ax+by+cz+d=0
BUILDOP("NEGATE",       0,              false,  1)      //Negative of argument
BUILDOP("hsl",          6,              false,  1)      //Left heavyside
BUILDOP("hsr",          6,              false,  1)      //Right heavyside
BUILDOP("acos",         6,              false,  1)      //Arccosine
BUILDOP("asin",         6,              false,  1)      //Arcsine
BUILDOP("atan",         6,              false,  1)      //Arctangent
BUILDOP("cosh",         6,              false,  1)      //Hyperbolic cosine
BUILDOP("sinh",         6,              false,  1)      //Hyperbolic sine
BUILDOP("tanh",         6,              false,  1)      //Hyperbolic tangent
BUILDOP("log",          6,              false,  1)      //Base 10 log
BUILDOP("ln",           6,              false,  1)      //Base e (natural) log
BUILDOP("th",           6,              false,  2)      //Top hat (left side, right side)
//=================================================================
                nOps = i;
        }
        ++instances;
}


///Destruct CDataFunc
/**
 * If this is the last instances of the class then delete the array of available operators.
 */
CDataFunc::~CDataFunc()
{
        --instances;
        if (instances == 0)
        {
                int i;
                for (i = 0; i < nOps; ++i)
                        delete[] ops[i].tag;
                delete[] ops;
        }
//      if (nQueue != 0) delete[] queue;
//      if (nValues != 0) delete[] values;
        if (queue != NULL) delete[] queue;
        if (values != NULL) delete[] values;
}


///Searches the list of tokens for a particular tag
/**
 * @param string Name of the operator to search for.
 * @return ID of the found tag or -1 if not found.
 */
int CDataFunc::FindTagID(char *string)
{
        int i;
        for (i = 0; i < nOps; ++i)
                if (strcmp(string, ops[i].tag) == 0)
                        return(i);
        return(-1);
}


///List of non-number characters.
#define NONNUMBER " \n,abcdefghijklmnopqrstuvwxyz_ABCDEFGHIJKLMNOPQRSTUVWXYZ!\"£$%^&*()-=+:;\'@#~<>/?\\|`¬[]{}"
///Converts a infix string into RPN stack
/**
 * @param input Input equation.
 * @remark The resulting RPN stack is in the array CDataFunc::queue.
 * @return Error code of the parsing as a CDataFunc::status.
 */
CDataFunc::status CDataFunc::InfixToRPN(char *input)
{
        nQueue = 0;
        nValues = 0;
        valid = false;
        char prevNonSpace = 0;

        token *stack;
        stack = new token;
        token *top = stack;
        top->tagid = -1;
        top->prev = NULL;
        top->next = NULL;

        token *opstack = new token;
        token *topop = opstack;
        topop->tagid = -1;
        topop->next = NULL;
        topop->prev = NULL;

        char *strptr = input;
//std::cerr << "Start: \'" << strptr << "\'\n";
        while (strptr[0] != '\0')
        {
                if (strptr[0] == '$')   //Variable
                {
                        int eov = strcspn(&strptr[1], "+-/* ()^,");     //end of variable
                        char *readtag = new char[eov+1];
                        strncpy(readtag, &strptr[1], eov);
                        readtag[eov] = '\0';
//std::cerr << '\'' << readtag << "\' var-> \'" << strptr << "\'\n";
                        top->next = new token;
                        top->next->next = NULL;
                        top->next->prev = top;
                        top = top->next;
                        top->value = 0.0;
                        top->tagid = FindTagID(readtag);
                        delete[] readtag;
                        if (top->tagid == -1) return(UNKNOWN_TAG);
                        prevNonSpace = strptr[eov];
                        strptr = &strptr[eov+1];
                        ++nValues;
                        ++nQueue;
                }
                else if (((strptr[0] >= '0') && (strptr[0] <= '9')) || (strptr[0] == '.'))      //Number
                {
                        int eov = strcspn(&strptr[0], NONNUMBER);
                        if ((strptr[eov] == 'e') || (strptr[eov] == 'E'))
                        {
                                if (strptr[eov+1] == '-')
                                        eov += 2+strcspn(&strptr[eov+2], NONNUMBER);    //negative exponential
                                else if (strptr[eov+1] == '+')
                                        eov += 2+strcspn(&strptr[eov+2], NONNUMBER);    //positive exponential
                                else if ((strptr[eov+1] >= '0') && (strptr[eov+1] <= '9'))
                                        eov += 1+strcspn(&strptr[eov+1], NONNUMBER);    //exponential
                        }
                        char *readtag = new char[eov+1];
                        strncpy(readtag, &strptr[0], eov);
                        readtag[eov] = '\0';
//std::cerr << '\'' << readtag << "\' num-> \'" << strptr << "\'\n";
                        top->next = new token;
                        top->next->next = NULL;
                        top->next->prev = top;
                        top = top->next;
                        top->tagid = FindTagID("v\0");
                        top->value = atof(readtag);
                        delete[] readtag;
                        if (top->tagid == -1) return(UNKNOWN_TAG);
                        prevNonSpace = strptr[eov-1];
                        strptr = &strptr[eov];
                        ++nValues;
                        ++nQueue;
                }
                else if (strptr[0] == '(')      //(
                {
                        topop->next = new token;
                        topop->next->next = NULL;
                        topop->next->prev = topop;
                        topop = topop->next;
                        topop->tagid = 1;
                        prevNonSpace = strptr[0];
                        strptr = &strptr[1];
                }
                else if (strptr[0] == ')')      //)
                {
                        while (topop->tagid != 1)
                        {
                                if (topop->tagid == -1) return(UNMATCHED_PARENTHESES);
                                top->next = new token;
                                top->next->next = NULL;
                                top->next->prev = top;
                                top = top->next;
                                top->value = 0.0;
                                top->tagid = topop->tagid;
                                topop = topop->prev;
                                delete topop->next;
                                topop->next = NULL;
                        }
                        topop = topop->prev;
                        delete topop->next;
                        topop->next = NULL;
                        prevNonSpace = strptr[0];
                        strptr = &strptr[1];
                }
                else if (strcspn(&strptr[0], "+-*/^") == 0)     //operator
                {
                        char *readtag = new char[2];
                        readtag[0] = strptr[0];
                        readtag[1] = '\0';

                        //detect negative numbers
                        if (readtag[0] == '-')
                        {
                                if ((prevNonSpace == '(') || (prevNonSpace == ',') || (prevNonSpace == '*') || (prevNonSpace == '/') || (prevNonSpace == '^') || (prevNonSpace == 0))
                                {
                                        delete[] readtag;
                                        readtag = new char[7];
                                        strcpy(readtag, "NEGATE");
/*                                      delete[] readtag;
                                        int eov = 1+strcspn(&strptr[1], NONNUMBER);
                                        if ((strptr[eov+1] == 'e') || (strptr[eov+1] == 'E'))
                                                if ((strptr[eov+2] >= '0') && (strptr[eov+2] <= '9'))
                                                        eov += 1+strcspn(&strptr[eov+2], NONNUMBER);    //exponential
                                        readtag = new char[eov+1];
                                        strncpy(readtag, &strptr[0], eov);
                                        readtag[eov] = '\0';
std::cerr << '\'' << readtag << "\' num-> \'" << strptr << "\'\n";
                                        top->next = new token;
                                        top->next->next = NULL;
                                        top->next->prev = top;
                                        top = top->next;
                                        top->tagid = FindTagID("v\0");
                                        top->value = atof(readtag);
                                        delete[] readtag;
                                        if (top->tagid == -1) return(UNKNOWN_TAG);
                                        prevNonSpace = strptr[eov];
                                        strptr = &strptr[eov+1];
                                        ++nValues;
                                        ++nQueue;
                                        continue;*/
                                }
                        }
                        
//std::cerr << '\'' << readtag << "\' op-> \'" << strptr << "\'\n";
                        int tagid = FindTagID(readtag);
                        delete[] readtag;
                        if (tagid == -1) return(UNKNOWN_TAG);

                        while (((topop->tagid != -1) && (topop->tagid != 1) && (topop->tagid != 3)) &&
                                (((ops[tagid].lassociative == true) && (ops[tagid].precedence <= ops[topop->tagid].precedence)) ||
                                        ((ops[tagid].lassociative == false) && (ops[tagid].precedence < ops[topop->tagid].precedence))))
                        {
                                top->next = new token;
                                top->next->next = NULL;
                                top->next->prev = top;
                                top = top->next;
                                top->tagid = topop->tagid;
                                top->value = topop->value;
                                topop = topop->prev;
                                delete topop->next;
                                topop->next = NULL;
                        }
                        topop->next = new token;
                        topop->next->next = NULL;
                        topop->next->prev = topop;
                        topop = topop->next;
                        topop->value = 0.0;
                        topop->tagid = tagid;
                        prevNonSpace = strptr[0];
                        strptr = &strptr[1];
                        ++nQueue;
                }
                else if (strptr[0] == ',')                      //argument separator
                {
                        while (topop->tagid != 1)
                        {
                                if (topop->tagid == -1) return(INVALID_SEPARATOR);
                                top->next = new token;
                                top->next->next = NULL;
                                top->next->prev = top;
                                top = top->next;
                                top->value = 0.0;
                                top->tagid = topop->tagid;
                                topop = topop->prev;
                                delete topop->next;
                                topop->next = NULL;
                        }
//std::cerr << '\'' << strptr[0] << "\' sep-> \'" << strptr << "\'\n";
                        prevNonSpace = strptr[0];
                        strptr = &strptr[1];
                }
                else if ((strptr[0] != ' ') && (strptr[0] != '\t') && (strptr[0] != '\n'))                      //function
                {
                        int eov = strcspn(&strptr[0], "0123456789. ()");
                        char *readtag = new char[eov+1];
                        strncpy(readtag, strptr, eov);
                        readtag[eov] = '\0';
//std::cerr << '\'' << readtag << "\' func-> \'" << strptr << "\'\n";
                        int tagid = FindTagID(readtag);
                        delete[] readtag;
                        if (tagid == -1) return(UNKNOWN_TAG);

                        while (((topop->tagid != -1) && (topop->tagid != 1) && (topop->tagid != 3)) &&
                                (((ops[tagid].lassociative == true) && (ops[tagid].precedence <= ops[topop->tagid].precedence)) ||
                                        ((ops[tagid].lassociative == false) && (ops[tagid].precedence < ops[topop->tagid].precedence))))
                        {
                                top->next = new token;
                                top->next->next = NULL;
                                top->next->prev = top;
                                top = top->next;
                                top->tagid = topop->tagid;
                                top->value = topop->value;
                                topop = topop->prev;
                                delete topop->next;
                                topop->next = NULL;
                        }
                        topop->next = new token;
                        topop->next->next = NULL;
                        topop->next->prev = topop;
                        topop = topop->next;
                        topop->value = 0.0;
                        topop->tagid = tagid;
                        prevNonSpace = strptr[eov-1];
                        strptr = &strptr[eov];
                        ++nQueue;
                }
                else
                        strptr = &strptr[1];
        }
        while (topop->tagid != -1)
        {
                if (topop->tagid == 1) return(UNMATCHED_PARENTHESES);
                top->next = new token;
                top->next->next = NULL;
                top->next->prev = top;
                top = top->next;
                top->tagid = topop->tagid;
                top->value = 0.0;
                topop = topop->prev;
                delete topop->next;
                topop->next = NULL;
        }
        delete topop;
//std::cerr << '\n';

        if (queue != NULL) delete[] queue;
        if (values != NULL) delete[] values;
        queue = NULL;
        values = NULL;
        if (nQueue != 0)
                queue = new token[nQueue];
        if (nValues != 0)
        {
                values = new real[nValues];
        }
        top = stack->next;
        int i;
        for (i = 0; i < nQueue; ++i)
        {
                queue[i].tagid = top->tagid;
                queue[i].value = top->value;
//std::cerr << ops[top->tagid].tag << top->value << ' ';
                top = top->next;
        }
        top = stack;
        while (top->next != NULL)
        {
                top = top->next;
                delete top->prev;
        }
        delete top;
        
        return(TestEvaluate());
}


///Evaluates an RPN stack
/**
 * Evaluates the RPN stack in CDataFunc::queue.
 * @param x X coordinate of the datapoint.
 * @param y Y coordinate of the datapoint.
 * @param z Z value of the datapoint.
 * @param cols Number of columns in coldata.
 * @param coldata Values in the other columns of the datapoint.
 * @return Evaluated value.
 */
double CDataFunc::Evaluate(double x, double y, double z, int cols, double coldata[])
{
        int val = 0, i;
        for (i = 0; i < nQueue; ++i)    //for all tokens
        {
                switch (queue[i].tagid) //identify and adjust stack as required
                {
                                        //"r"           Result
                                        //"("           Parentheses
                                        //")"           Parentheses
                case 3:         //"v"           Value (a number)
                        {
                                values[val] = queue[i].value;
                                ++val;
                        }
                        break;
                case 4:         //"-"           Subtract
                        {
                                --val;
                                values[val-1] = values[val-1]-values[val];
                        }
                        break;
                case 5:         //"+"           Add
                        {
                                --val;
                                values[val-1] = values[val-1]+values[val];
                        }
                        break;
                case 6:         //"*"           Multiply
                        {
                                --val;
                                values[val-1] = values[val-1]*values[val];
                        }
                        break;
                case 7:         //"/"           Divide
                        {
                                --val;
                                values[val-1] = values[val-1]/values[val];
                        }
                        break;
                case 8:         //"^"           Power
                        {
                                --val;
                                values[val-1] = pow(values[val-1], values[val]);
                        }
                        break;
                case 9:         //"exp"         Exponential
                        {
                                values[val-1] = exp(values[val-1]);
                        }
                        break;
                case 10:        //"cos"         Cosine
                        {
                                values[val-1] = cos(values[val-1]);
                        }
                        break;
                case 11:        //"sin"         Sine
                        {
                                values[val-1] = sin(values[val-1]);
                        }
                        break;
                case 12:        //"tan"         Tangent
                        {
                                values[val-1] = tan(values[val-1]);
                        }
                        break;
                case 13:        //"pi"          Pi
                        {
                                values[val] = PI;
                                ++val;
                        }
                        break;
                case 14:        //"x"           x channel value
                        {
                                values[val] = x;
                                ++val;
                        }
                        break;
                case 15:        //"y"           y sd value
                        {
                                values[val] = y;
                                ++val;
                        }
                        break;
                case 16:        //"z"           the data point
                        {
                                values[val] = z;
                                ++val;
                        }
                        break;
                case 17:        //"abs"         Absolute
                        {
                                values[val-1] = fabs(values[val-1]);
                        }
                        break;
                case 18:        //"blend"       Blend (a,b,x) - blend a*(1-x)+bx
                        {
                                val -= 2;
                                values[val-1] = values[val-1]*(1-values[val+1])+values[val]*values[val+1];
                        }
                        break;
                case 19:        //"clamp"       Clamp (x,a,b) - clamp x to range a->b
                        {
                                val -= 2;
                                if (values[val-1] < values[val])
                                        values[val-1] = values[val];
                                else if (values[val-1] > values[val+1])
                                        values[val-1] = values[val+1];
//                              else leave as is
                        }
                        break;
                case 20:        //"large"       Large (x,y) - larger of x and y
                        {
                                --val;
                                if (values[val-1] < values[val])
                                        values[val-1] = values[val];
                        }
                        break;
                case 21:        //"small"       Small (x,y) - smaller of x and y
                        {
                                --val;
                                if (values[val-1] > values[val])
                                        values[val-1] = values[val];
                        }
                        break;
                case 22:        //"select"      Select (x,y,z,a) - select x if z <= a else y
                        {
                                val -= 3;
                                if (values[val+1] > values[val+2])
                                        values[val-1] = values[val];
                        }
                        break;
                case 23:        //"int"         Integer
                        {
                                values[val-1] = (real)((int)(values[val-1]));
                        }
                        break;
                case 24:        //"col"         Column data point
                        {
                                if (values[val-1] > (cols-1))
                                        return(1e-100);
                                values[val-1] = coldata[(int)(values[val-1])];
                        }
                        break;
                case 25:        //"plane"               Z of plane ax+by+cz+d=0
                        {
                                val -= 3;
                                values[val-1] = (0.0-values[val+2]-values[val-1]*x-values[val]*y)/values[val+1];
                        }
                        break;
                case 26:        //"NEGATE"              Negative of argument
                        {
                                values[val-1] = -values[val-1];
                        }
                        break;
                case 27:        //"hsl"         Left heavyside
                        {
                                if (values[val-1] <= 0.0)
                                        values[val-1] = 1.0;
                                else
                                        values[val-1] = 0.0;
                        }
                        break;
                case 28:        //"hsr"         Negative of argument
                        {
                                if (values[val-1] >= 0.0)
                                        values[val-1] = 1.0;
                                else
                                        values[val-1] = 0.0;
                        }
                        break;
                case 29:        //"acos"        Arccossine
                        {
                                values[val-1] = acos(values[val-1]);
                        }
                        break;
                case 30:        //"asin"        Arcsine
                        {
                                values[val-1] = asin(values[val-1]);
                        }
                        break;
                case 31:        //"atan"        Arctangent
                        {
                                values[val-1] = atan(values[val-1]);
                        }
                        break;
                case 32:        //"cosh"        Hyperbolic cosine
                        {
                                values[val-1] = cosh(values[val-1]);
                        }
                        break;
                case 33:        //"sinh"        Hyperbolic sine
                        {
                                values[val-1] = sinh(values[val-1]);
                        }
                        break;
                case 34:        //"tanh"        Hyperbolic tangent
                        {
                                values[val-1] = tanh(values[val-1]);
                        }
                        break;
                case 35:        //"log" Base 10 log
                        {
                                values[val-1] = log10(values[val-1]);
                        }
                        break;
                case 36:        //"ln"  Base e (natural) log
                        {
                                values[val-1] = log(values[val-1]);
                        }
                        break;
                case 37:        //"th"  Top hat (x,y) - 1 if x > 0 and y < 0
                        {
                                --val;
                                if ((values[val-1] >= 0.0) && (values[val] <= 0))
                                        values[val-1] = 1.0;
                                else
                                        values[val-1] = 0.0;
                        }
                        break;
                }
        }
        return(values[val-1]);
}


///Simple evaluation check
/**
 * Checks that after evaluation we are just left with the answer on the stack.
 * @return Status of the test evaluation as a CDataFunc::status.
 */
CDataFunc::status CDataFunc::TestEvaluate(void)
{
        int val = 0, i;
        for (i = 0; i < nQueue; ++i)
        {
                val -= ops[queue[i].tagid].args;
                if (val < 0)
                        return(TOO_FEW_VARS);
                ++val;
        }
        if (val < 1)
                return(TOO_FEW_VARS);
        valid = true;
        return(OK);
}

---