Expression.cpp

Go to the documentation of this file.

#pragma ident "$Id: Expression.cpp 2944 2011-10-27 08:04:41Z yanweignss $"

//============================================================================
//
//  This file is part of GPSTk, the GPS Toolkit.
//
//  The GPSTk 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 2.1 of the License, or
//  any later version.
//
//  The GPSTk 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 GPSTk; if not, write to the Free Software Foundation,
//  Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//  
//  Copyright 2004, The University of Texas at Austin
//
//============================================================================


#include <sstream>
#include <map>
#include <list>
#include <vector>
#include <string>
#include <ctype.h>
#include <math.h>

#include "icd_200_constants.hpp"
#include "StringUtils.hpp"
#include "Expression.hpp"

namespace gpstk 
{
   
   double Expression::BinOpNode::getValue() 
      throw (ExpressionException) 
   {

      // 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
      GPSTK_THROW(ExpressionException());

   }

   double Expression::FuncOpNode::getValue()
      throw (ExpressionException) 
   {
      // 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
      GPSTK_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) 
      throw (ExpressionException)
   {
      if (!hasValue) 
      { 
         ExpressionException ee("Variable " + name + " undefined."); 
         GPSTK_THROW(ee);
      }
      
      return value;
   }
   
   Expression::Token::Token(std::string iValue, int iPriority, 
                            bool isOp=false)
         :
         value(iValue), priority(iPriority), used(false), resolved(false),
         expNode(0), isOperator(isOp)
   {
   }

   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++)
      {
         int 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 GPSTk.
      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;
      }
      
      int 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 / L2_FREQ)*(L1_FREQ / L2_FREQ));
      gotSet |= set("pi",PI);
      gotSet |= set("c",C_GPS_M);
      gotSet |= set("c_gps_m",C_GPS_M);
      gotSet |= set("l0",OSC_FREQ);
      gotSet |= set("f1",L1_MULT);
      gotSet |= set("f2",L2_MULT);
      gotSet |= set("l1",L1_FREQ);
      gotSet |= set("l2",L2_FREQ);
      gotSet |= set("wl1",C_GPS_M/L1_FREQ);
      gotSet |= set("wl2",C_GPS_M/L2_FREQ);
      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 ObsID::otRange:    type = "C"; break;
            case ObsID::otPhase:    type = "L"; break;
            case ObsID::otDoppler:  type = "D"; break;
            case ObsID::otSNR:      type = "S"; break;
            case ObsID::otSSI:      ignore = true; break;
            case ObsID::otLLI:      ignore = true; break;
            case ObsID::otTrackLen: ignore = true; break;
         }

         switch (i->first.band)
         {
            case ObsID::cbL1:   band = "1"; break;
            case ObsID::cbL2:   band = "2"; break;
            case ObsID::cbL5:   band = "5"; break;
            case ObsID::cbE6:   band = "6"; break;
            case ObsID::cbE5b:  band = "7"; break;
            case ObsID::cbE5ab: band = "8"; break;
         }

         switch (i->first.code)
         {
            case ObsID::tcCA:   attribute = "C"; break;
            case ObsID::tcP:    attribute = "P"; break;
            case ObsID::tcY:    attribute = "Y"; break;
            case ObsID::tcW:    attribute = "W"; break;
            case ObsID::tcN:    attribute = "N"; break;
            case ObsID::tcM:    attribute = "M"; break;
            case ObsID::tcC2M:  attribute = "S"; break;
            case ObsID::tcC2L:  attribute = "L"; break;
            case ObsID::tcC2LM: attribute = "X"; break;
            case ObsID::tcI5:   attribute = "I"; break;
            case ObsID::tcQ5:   attribute = "Q"; break;
            case ObsID::tcIQ5:  attribute = "X"; break;
            case ObsID::tcA:    attribute = "A"; break;
            case ObsID::tcB:    attribute = "B"; break;
            case ObsID::tcC:    attribute = "C"; break;
            case ObsID::tcBC:   attribute = "X"; break;
            case ObsID::tcABC:  attribute = "Z"; break;
         }
         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 gpstk

---