Expression.cpp

Go to the documentation of this file.

//==============================================================================
//
//  This file is part of GNSSTk, the ARL:UT GNSS Toolkit.
//
//  The GNSSTk is free software; you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published
//  by the Free Software Foundation; either version 3.0 of the License, or
//  any later version.
//
//  The GNSSTk 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 Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public
//  License along with GNSSTk; if not, write to the Free Software Foundation,
//  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110, USA
//
//  This software was developed by Applied Research Laboratories at the
//  University of Texas at Austin.
//  Copyright 2004-2022, The Board of Regents of The University of Texas System
//
//==============================================================================
 
//==============================================================================
//
//  This software was developed by Applied Research Laboratories at the
//  University of Texas at Austin, under contract to an agency or agencies
//  within the U.S. Department of Defense. The U.S. Government retains all
//  rights to use, duplicate, distribute, disclose, or release this software.
//
//  Pursuant to DoD Directive 523024
//
//  DISTRIBUTION STATEMENT A: This software has been approved for public
//                            release, distribution is unlimited.
//
//==============================================================================
 
#include <sstream>
#include <map>
#include <list>
#include <vector>
#include <string>
#include <ctype.h>
#include <math.h>
 
#include "GNSSconstants.hpp"
#include "StringUtils.hpp"
#include "Expression.hpp"
 
namespace gnsstk
{
 
   double Expression::BinOpNode::getValue()
   {
 
      // To get the value, compute the value of the left and
      // right operands, and combine them with the operator.
      double leftVal = left->getValue();
      double rightVal = right->getValue();
 
      if (op=="+") return leftVal + rightVal;
      if (op=="-") return leftVal - rightVal;
      if (op=="*") return leftVal * rightVal;
      if (op=="/") return leftVal / rightVal;
 
      // else THROW exception
      GNSSTK_THROW(ExpressionException());
 
   }
 
   double Expression::FuncOpNode::getValue()
   {
      // To get the value, compute the value of the right first
      double rightVal = right->getValue();
 
      if (op=="cos") return ::cos(rightVal);
      if (op=="sin") return ::sin(rightVal);
      if (op=="tan") return ::tan(rightVal);
      if (op=="acos") return ::acos(rightVal);
      if (op=="asin") return ::asin(rightVal);
      if (op=="atan") return ::atan(rightVal);
      if (op=="exp") return ::exp(rightVal);
      if (op=="abs") return ::fabs(rightVal);
      if (op=="sqrt") return ::sqrt(rightVal);
      if (op=="log") return ::log(rightVal);
      if (op=="log10") return ::log10(rightVal);
 
      // else THROW exception
      GNSSTK_THROW(ExpressionException());
   }
 
   std::ostream& Expression::FuncOpNode::print(std::ostream& ostr) {
      ostr << op;
      right->print(ostr);
 
      return ostr;
   }
 
   std::ostream& Expression::BinOpNode::print(std::ostream& ostr) {
      ostr << "(";
      left->print(ostr);
      ostr << op;
      right->print(ostr);
      ostr << ")";
 
      return ostr;
   }
 
   void Expression::VarNode::setValue(double newValue)
   {
      value=newValue;
      hasValue=true;
   };
 
   double Expression::VarNode::getValue(void)
   {
      if (!hasValue)
      {
         ExpressionException ee("Variable " + name + " undefined.");
         GNSSTK_THROW(ee);
      }
 
      return value;
   }
   Expression::Token::Token(std::string iValue, int iPriority,
                            bool isOp=false)
         :
         value(iValue), isOperator(isOp), resolved(false), priority(iPriority),
         expNode(0), used(false)
   { }
   void Expression::Token::print(std::ostream& ostr)
   {
      ostr <<" Value '" << value;
      ostr << "', operation priority " << priority << ", ";
 
      if (isOperator) ostr << "operator";
      else ostr << "not operator";
 
      ostr << ", ";
 
      if (used) ostr << "used,";
      else ostr << "not used,";
 
      if (resolved) ostr << "resolved";
      else ostr << "not resolved ";
 
      return;
   }
 
   bool Expression::operatorsDefined = false;
   std::map<std::string,int> Expression::operatorMap;
   std::map<std::string,std::string> Expression::argumentPatternMap;
 
   Expression::Expression(const std::string& istr)
         : root(0)
   {
      defineOperators();
      setExpression(istr);
   }
 
   void Expression::setExpression(const std::string& istr)
   {
      dumpLists();
      tokenize(istr);
      buildExpressionTree();
   }
 
   Expression::Expression(void)
         : root(0)
   {
      defineOperators();
      setExpression("0");
   }
 
   Expression::Expression(const Expression& rhs)
   {
      defineOperators();
      std::ostringstream ostr;
      rhs.print(ostr);
      setExpression(ostr.str());
   }
 
   Expression& Expression::operator=(const Expression& rhs)
   {
      std::ostringstream ostr;
      rhs.print(ostr);
      setExpression(ostr.str());
      return (*this);
   }
 
   void Expression::dumpLists(void)
   {
      // first release the points tracked by this Expression
      std::list<ExpNode *>::iterator i= eList.begin(), itemp;
      while (i!= eList.end())
      {
         itemp=i;
         itemp++;
         delete(*i);
         i=itemp;
      }
      std::list<ExpNode *> emptyENodeList;
      eList = emptyENodeList;
      std::list<Token> emptyTokenList;
      tList = emptyTokenList;
      root =0;
   }
 
 
   void Expression::defineOperators(void)
   {
      if (!operatorsDefined)
      {
         operatorMap["+"]=1;
         operatorMap["-"]=1;
         operatorMap["*"]=2;
         operatorMap["/"]=2;
         operatorMap["^"]=3;
         operatorMap["cos"]=4;
         operatorMap["sin"]=4;
         operatorMap["tan"]=4;
         operatorMap["acos"]=4;
         operatorMap["asin"]=4;
         operatorMap["atan"]=4;
         operatorMap["exp"]=4;
         operatorMap["abs"]=4;
         operatorMap["sqrt"]=4;
         operatorMap["log"]=4;
         operatorMap["log10"]=4;
 
         argumentPatternMap["+"]="RL";
         argumentPatternMap["-"]="RL";
         argumentPatternMap["*"]="RL";
         argumentPatternMap["/"]="RL";
         argumentPatternMap["^"]="RL";
         argumentPatternMap["cos"]="R";
         argumentPatternMap["sin"]="R";
         argumentPatternMap["tan"]="R";
         argumentPatternMap["acos"]="R";
         argumentPatternMap["asin"]="R";
         argumentPatternMap["atan"]="R";
         argumentPatternMap["exp"]="R";
         argumentPatternMap["abs"]="R";
         argumentPatternMap["sqrt"]="R";
         argumentPatternMap["log"]="R";
         argumentPatternMap["log10"]="R";
 
         operatorsDefined = true;
      }
   }
 
   Expression::~Expression(void)
   {
      std::list<ExpNode *>::iterator i;
      for (i=eList.begin(); i!=eList.end(); i++)
         delete (*i);
   }
 
   void Expression::tokenize(const std::string& istr)
   {
      using namespace std;
 
      // Remove spaces and parenthesis from the input string
      // Must store informatin from parenthesis in another list
      stringstream ss(istr);
      string str;
      char tempc;
      vector<int> baseOrder;
      int currentOrder = 0;
 
      while (ss >> skipws >> tempc)
      {
         bool strip=false;
 
         if (tempc == '(')
         {
            currentOrder+=10;
            strip=true;
         }
 
         if (tempc == ')')
         {
            currentOrder-=10;
            strip=true;
         }
 
         if (!strip)
         {
            baseOrder.push_back(currentOrder);
            str.append(&tempc,1);
         }
      }
 
      map<string, int>::iterator it;
      list<int> breaks;
      breaks.push_back(0);
 
      // Break the expression into candidates for tokens. First known
      // operators and functions
      // are found and marked with as a "break" in the the string.
      // Note the location and compute the order of operation of each.
      // key is location in string. value is ord. of op.
      map<int,int> breakPriority;
 
      // Note when the breaks are due to an operator or to an operand.
      // Each break can become a token but not all othem do.
      // Key is location in the string, value is boolean, true for operators and functions.
      map<int, bool> breakType;
 
      for (it=operatorMap.begin(); it!=operatorMap.end(); it++)
      {
         std::string::size_type position = 0;
         while ((position=str.find(it->first,position+1))!=string::npos)
         {
            // Account for scientific notation
            bool sciNotation=false;
            if ((it->first=="+") || (it->first=="-"))
            {
               sciNotation =
                  ( ( (str.substr(position-1,1)=="E") ||
                      (str.substr(position-1,1)=="e")    )         &&
                    (isdigit(str.substr(position-2,1).c_str()[0])) &&
                    (isdigit(str.substr(position+1,1).c_str()[0]))      );
            }
 
            if (!sciNotation)
            {
               breaks.push_back(position);
               breakPriority[position] = it->second + baseOrder[position];
               breakType[position] = true;
 
               int operandPos = position+(it->first.size());
               breaks.push_back(operandPos);
               breakPriority[operandPos] = baseOrder[operandPos];
               breakType[operandPos] = false;
            }
         }
 
      }
      breaks.push_back(str.size());
 
      // Sort the breaks into a list
      // Please note that sorting a linked list is expensive compared to
      // sorting a vector or map, as the search cost is high (lists are not sorted).
      // This should be revisited IF large expressions are handled by the GNSSTk.
      breaks.sort();
 
      list<string> tokens;
      list<int>::iterator ls = breaks.begin(), rs = ls; // used to identify token string
 
      for (rs++ ;rs!=breaks.end(); rs++, ls++)
      {
         if (*rs!=*ls) // If not two operators in a row
         {
            string thisToken = str.substr(*ls,(*rs)-(*ls));
            int thisOop = breakPriority[*ls];
            bool isOp = breakType[*ls];
 
               // Create the token
            Token tok(thisToken,thisOop, isOp);
 
            if ( tok.getOperator() )
               tok.setArgumentPattern( argumentPatternMap[thisToken] );
 
            // Create an expression node, save it, and link it to the token
            ExpNode *expNode;
 
 
            if (!isOp)
            {
               char testChar = thisToken.c_str()[0];
               if (isalpha(testChar))
                  expNode = new VarNode(thisToken);
               else
                  expNode = new ConstNode(StringUtils::asDouble(thisToken));
               eList.push_back(expNode);
               tok.setNode(expNode);
               tok.setResolved(true);
            }
 
            // Now that the token has the best possible state, save it
            tList.push_back(tok);
         }
      }
   } // end tokenize function
 
 
   int Expression::countResolvedTokens(void)
   {
      using namespace std;
 
      list<Token>::iterator itt;
 
      // How many have already been processed? Are we done yet?
      int totalResolved=0;
      for (itt = tList.begin(); itt!=tList.end(); itt++)
      {
         if (itt->getResolved()) totalResolved++;
      }
      return totalResolved;
   }
 
 
   void Expression::buildExpressionTree(void)
   {
      using namespace std;
 
      list<Token>::iterator itt, targetToken;
 
      if ((tList.size()==1)&&(tList.begin()->getResolved()))
      {
         root = tList.begin()->getNode();
         return;
      }
 
      size_t totalResolved = countResolvedTokens();
 
      while (totalResolved<tList.size())
      {
 
         //
         // Step through tokens to find the value for the highest priority
         // that doesn not yet have an expression node ExpNode assigned to it.
         // A subtle but important sideeffect of this traversal is taht
         // operators with the same priority get evaluated from right to
         // left.
         itt=tList.begin();
         int highestP = -1;
 
         for (itt = tList.begin(); itt !=tList.end(); itt++)
         {
            if ( itt->getOperator() && !itt->getResolved() )
            {
               if (itt->getPriority()>highestP)
               {
                  targetToken = itt;
                  highestP=itt->getPriority();
               }
            }
         }
 
         if ( targetToken->getOperator() )
         {
            // Find the arg(s) for this operator.
            list<Token>::iterator leftArg=targetToken, rightArg=leftArg;
 
            stringstream argstr(targetToken->getArgumentPattern());
            char thisArg;
            bool searching;
 
            while (argstr >> thisArg)
            {
               switch (thisArg) {
                  case 'R':
                     searching = true;
 
                     while (searching)
                     {
                        if (rightArg==tList.end())// TODO throw exception
                           cout << "Mistake, no right arg for " << targetToken->getValue() << endl;
                        else
                        rightArg++;
 
                        searching = (rightArg->getUsed());
                     }
 
                     break;
 
                  case 'L':
 
                        // Resolve left arg
                     searching=true;
 
                     while (searching)
                     {
                        if (leftArg == tList.begin()) // TODO throw
                           cout << "Mistake - no right argument for operator?!" << endl;
                        else
                           leftArg--;
 
                        searching = (leftArg->getUsed());
                     }
 
                     break;
               } // end of argumentPattern cases
            } // done processing argument list
 
 
           if (targetToken->getArgumentPattern()=="RL")
           {
              ExpNode *opNode =
              new BinOpNode(targetToken->getValue(),leftArg->getNode(), rightArg->getNode());
              targetToken->setNode(opNode);
              eList.push_back(opNode);
 
              targetToken->setResolved(true);
              root = targetToken->getNode();
 
              leftArg->setUsed();
              rightArg->setUsed();
           }
 
           if (targetToken->getArgumentPattern()=="R")
           {
              ExpNode *opNode =
              new FuncOpNode(targetToken->getValue(),rightArg->getNode());
              targetToken->setNode(opNode);
 
              eList.push_back(opNode);
 
              targetToken->setResolved(true);
              root = targetToken->getNode();
 
              rightArg->setUsed();
           }
 
         } // If this is an operator
 
         // Are we done yet?
         totalResolved = countResolvedTokens();
      }
 
   } // end buildExpressionTree
 
 
   bool Expression::set(const std::string name, double value)
   {
      using namespace std;
 
      bool gotSet;
 
      std::list<ExpNode *>::iterator i;
      int t;
 
      for (t=0, i=eList.begin(); i!=eList.end(); t++, i++)
      {
         VarNode *vnode = dynamic_cast<VarNode *> (*i);
         if (vnode!=0)
         {
            if (StringUtils::upperCase(vnode->name) ==
                StringUtils::upperCase(name))
            {
               vnode->setValue(value);
               gotSet = true;
            }
         }
      }
 
      return gotSet;
   }
 
 
   bool Expression::canEvaluate(void)
   {
      using namespace std;
 
      bool areSet=true;
 
      std::list<ExpNode *>::iterator i;
      int t;
 
      for (t=0, i=eList.begin(); i!=eList.end(); t++, i++)
      {
         VarNode *vnode = dynamic_cast<VarNode *> (*i);
         if (vnode!=0)
         {
            areSet &= vnode->hasValue;
         }
      }
 
      return areSet;
   }
 
   bool Expression::setGPSConstants(void)
   {
      bool gotSet = false;
 
      gotSet |= set("gamma",(L1_FREQ_GPS / L2_FREQ_GPS)*(L1_FREQ_GPS / L2_FREQ_GPS));
      gotSet |= set("pi",PI);
      gotSet |= set("c",C_MPS);
      gotSet |= set("c_gps_m",C_MPS);
      gotSet |= set("l0",OSC_FREQ_GPS);
      gotSet |= set("f1",L1_MULT_GPS);
      gotSet |= set("f2",L2_MULT_GPS);
      gotSet |= set("l1",L1_FREQ_GPS);
      gotSet |= set("l2",L2_FREQ_GPS);
      gotSet |= set("wl1",C_MPS/L1_FREQ_GPS);
      gotSet |= set("wl2",C_MPS/L2_FREQ_GPS);
      return gotSet;
   }
 
   bool Expression::setRinexObs(const RinexObsData::RinexObsTypeMap& rotm)
   {
      bool gotSet = false;
 
      RinexObsData::RinexObsTypeMap::const_iterator i;
      for (i=rotm.begin(); i!=rotm.end(); i++)
         gotSet |= set(i->first.type, i->second.data);
 
      return gotSet;
   }
 
   // We use the rinex 3 type identifiers for this since the rinex 2 will leave
   // things ambigous. This is in contrast to the setRinexObs() method which
   // uses the rinex 2 type identifiers.
   bool Expression::setSvObsEpoch(const SvObsEpoch& soe)
   {
      bool gotSet = false;
      for (SvObsEpoch::const_iterator i=soe.begin(); i != soe.end(); i++)
      {
 
         // Note that there are some combinations of the following that are not
         // 'valid'. Well, they aren't defined in the RINEX 3 spec
         // Also, this needs to be moved to another file once we have
         // rinex 3 support in the src directory.
         std::string type, band, attribute;
         bool ignore=false;
         switch (i->first.type)
         {
            case ObservationType::Range:    type = "C"; break;
            case ObservationType::Phase:    type = "L"; break;
            case ObservationType::Doppler:  type = "D"; break;
            case ObservationType::SNR:      type = "S"; break;
            case ObservationType::SSI:      ignore = true; break;
            case ObservationType::LLI:      ignore = true; break;
            case ObservationType::TrackLen: ignore = true; break;
                        default: break; //NB Determine if additional enumeration values need to be handled
         }
 
         switch (i->first.band)
         {
            case CarrierBand::L1:   band = "1"; break;
            case CarrierBand::L2:   band = "2"; break;
            case CarrierBand::L5:   band = "5"; break;
            case CarrierBand::E6:   band = "6"; break;
            case CarrierBand::E5b:  band = "7"; break;
            case CarrierBand::E5ab: band = "8"; break;
                        default: break; //NB Determine if additional enumeration values need to be handled
         }
 
         switch (i->first.code)
         {
            case TrackingCode::CA:   attribute = "C"; break;
            case TrackingCode::P:    attribute = "P"; break;
            case TrackingCode::Y:    attribute = "Y"; break;
            case TrackingCode::Ztracking:    attribute = "W"; break;
            case TrackingCode::YCodeless:    attribute = "N"; break;
            case TrackingCode::MDP:    attribute = "M"; break;
            case TrackingCode::L2CM:  attribute = "S"; break;
            case TrackingCode::L2CL:  attribute = "L"; break;
            case TrackingCode::L2CML: attribute = "X"; break;
            case TrackingCode::L5I:   attribute = "I"; break;
            case TrackingCode::L5Q:   attribute = "Q"; break;
            case TrackingCode::L5IQ:  attribute = "X"; break;
            case TrackingCode::E1A:    attribute = "A"; break;
            case TrackingCode::E1B:    attribute = "B"; break;
            case TrackingCode::E1C:    attribute = "C"; break;
            case TrackingCode::E1BC:   attribute = "X"; break;
            case TrackingCode::E1ABC:  attribute = "Z"; break;
                        default: break; //NB Determine if additional enumeration values need to be handled
         }
         if (ignore)
            continue;
 
         std::string id = type + band + attribute;
 
         if (id.length() != 3)
               std::cout << "Unimplimented ObsID:" << i->first << std::endl;
 
         gotSet |= set(id, i->second);
      }
      return gotSet;
   }
 
} // end namespace gnsstk