text: #pragma ident "$Id$"
  
  //============================================================================
  //
  //  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., 51 Franklin Street, Fifth Floor, Boston, MA 02110, USA
  //
  //  Copyright 2004, The University of Texas at Austin
  //
  //============================================================================
  
  
  /**
   * @file Expression.hpp
   * Provides ability to resolve mathematical functions at runtime.
   * Class declarations.
   */
  
  #ifndef EXPRESSION__HPP
  #define EXPRESSION__HPP
  
  #include <iostream>
  #include <string>
  #include <list>
  #include <map>
  
  #include "RinexObsHeader.hpp"
  #include "RinexObsData.hpp"
  #include "ObsEpochMap.hpp"
  #include "Exception.hpp"
  
  namespace gpstk
  {
  /** @addtogroup math */
  //@{
  
  /**
   * This class provides the ability to resolve general mathematical
   * expressions at run time. The goal is to allow the end user the
   * ability to specify arbitrary observation transformations.
   *
   * The expression is input as a string in the constructor of the class.
   * The expression is first broken up into tokens. Those tokens are
   * prioritized according to operator precedence and the number of
   * parentheses surrounding them. This list of prioritized combinations
   * is then converted into a 'classic" binary expression tree. All this
   * happens during construction, hidden to the user.
   *
   * The design of the expression node classes is based on
   * material by David Eck and Scotty Orr found at
   *
   *     http://math.hws.edu/orr/s04/cpsc225/btrees/index.html
   *
   * After the expression is instantiated, it can be evaluated. If the
   * expression contains variables, those must be set using the set
   * operation for the expression to successfully evaluate.
   *
   */
  
  NEW_EXCEPTION_CLASS(ExpressionException, Exception);
  
  class Expression
  {
  public:
  
      /**
       * Empty constructor
       */
      Expression(void);
  
      /**
       * Constructor.
       * @param str Expression to be evaluated.
       */
      Expression(const std::string& str);
  
      /**
       * Copy constructor.
       * @param expr Expression to be copied. Note that variable values are not copied.
       */
      Expression(const Expression& rhs);
  
      /// Destructor
      ~Expression(void);
  
      /// Assignment operator.
      Expression& operator=(const Expression& rhs);
  
  
      /**
       * Sets a variable in the expression to the input value.
       * All instances of the variable are set to this value.
       * This is required before an expression can be evaluated, if
       * the expression contains variables.
       * @param name Name of the variable to set
       * @param value Value to set the variable to.
       * @return True if the variable was found.
       */
      bool set(const std::string name, double value);
  
      /**
       * Sets a variable in the expression to the input value.
       * All instances of the variable are set to this value.
       * This is required before an expression can be evaluated, if
       * the expression contains variables. In the search, case
       * is not important (e.g., "c" and "C" would be a match).
       * @param name Name of the variable to set
       * @param value Value to set the variable to.
       * @return True if the variable was found.
       */
      bool set(const char* name, double value)
      {
          return set (std::string(name),value);
      }
  
      /**
       * Sets multiple variables in the expression to constants associated
       * with GPS. Predefined variables include: PI; C (meters per
       * second); L1 and L2, carrier frequencies in cycles per second;
       * WL1 and WL2, carrier
       * wavelengths. As with other variables, the case is insensitive.
       * @return True if any GPS related constants were found
       */
      bool setGPSConstants(void);
  
      /**
       * Sets multiple variables in the expression using values stored
       * in a RinexObsType stucture. This structure is nested within the
       * RinexObsData class.
       * @param rotm Map of RinexObsType to RinexObsDatum
       * @return True if an obs variable was found.
       */
      bool setRinexObs(const RinexObsData::RinexObsTypeMap& rotm);
  
      /**
       * Sets multiple variables in the expression using values stored
       * in a RinexObsType stucture. This structure is nested within the
       * RinexObsData class.
       * @param rotm Map of RinexObsType to RinexObsDatum
       * @return True if an obs variable was found.
       */
      bool setSvObsEpoch(const SvObsEpoch& soe);
  
      /**
       * Checks in advance if all variables have been set.
       * @return True if all variables are set.
       */
      bool canEvaluate(void);
  
      /**
       * Returns the numerical value of the expression. Note that
       * if the expression contains variables, those variables must
       * be set.
       */
      double evaluate(void)  throw (ExpressionException)
      {
          return root->getValue();
      }
  
      /**
       * Writes the expression out to a stream.
       */
      void print(std::ostream& ostr) const
      {
          root->print(ostr);
      }
  
  private:
      // Represents a node of any type in an expression tree.
      class ExpNode
      {
      public:
  
          virtual ~ExpNode() {}
  
          // Compute and return the numerical value of this node
          virtual double getValue()
          throw (ExpressionException) =0;
  
  
          // Write out this node to a stream
          virtual std::ostream& print(std::ostream& ostr) =0;
  
      }; // end class ExpNode
  
  
      // Represents a node that holds a number.
      class ConstNode : public ExpNode
      {
      public:
          // Constructor.  Create a node to hold val.
          ConstNode( double theNum ): number(theNum) {}
  
          double getValue()  throw (ExpressionException)
          {
              return number;
          }
  
          std::ostream& print(std::ostream& ostr)
          {
              ostr << number;
              return ostr;
          }
  
          double number;  // The number in the node.
      }; // end class ConstNode
  
      // Represents a node that holds a variable
      class VarNode : public ExpNode
      {
      public:
          // Constructor.
  
          VarNode(std::string theName ): name(theName), hasValue(false)
          {}
  
          double getValue()  throw (ExpressionException);
  
          std::ostream& print(std::ostream& ostr)
          {
              ostr << name;
              return ostr;
          }
  
          std::string name;  // The name of the varaible
          bool hasValue;
  
          void setValue(double newValue);
  
      private:
          double value;
  
  
      }; // end class VarNode
  
      // Represents a node that holds an operator.
      class BinOpNode : public ExpNode
      {
      public:
  
          // Constructor.  Create a node to hold the given data.
          BinOpNode( const std::string& theOp, ExpNode *theLeft, ExpNode *theRight ):
              op(theOp), left(theLeft), right(theRight) {}
  
          double getValue()
          throw (ExpressionException);
  
          std::ostream& print(std::ostream& ostr);
  
          std::string op;        // The operator.
          ExpNode *left;   // The left operand.
          ExpNode *right;  // The right operand.
  
      }; // end class BinOpNode
  
      // Represents a node that holds a function of a signle variable
      class FuncOpNode : public ExpNode
      {
      public:
  
          // Constructor.  Create a node to hold the given data.
          FuncOpNode( const std::string& theOp, ExpNode *theRight ):
              op(theOp), right(theRight) {}
  
          double getValue()
          throw (ExpressionException);
  
          std::ostream& print(std::ostream& ostr);
  
          std::string op;        // The operator.
          ExpNode *right;  // The right operand.
  
      }; // end class FuncOpNode
  
      // This class is used internally, during construction of an Expression,
      // to generate ExpNodes.
      class Token
      {
      public:
  
          Token(std::string value, int relPriority,
                bool isOperator);
  
          std::string getValue(void)
          {
              return value;
          }
  
          int getPriority(void)
          {
              return priority;
          }
  
          void setUsed(void)
          {
              used=true;
          }
          bool getUsed(void)
          {
              return used;
          }
  
          ExpNode * getNode(void)
          {
              return expNode;
          }
          void setNode(ExpNode *newNode)
          {
              expNode = newNode;
          }
  
          void setResolved(bool value)
          {
              resolved=value;
          }
          bool getResolved(void)
          {
              return resolved;
          }
  
          bool getOperator(void)
          {
              return isOperator;
          }
          void setOperator(bool value)
          {
              isOperator = value;
          }
  
          std::string getArgumentPattern(void)
          {
              return argumentPattern;
          }
          void setArgumentPattern(std::string value)
          {
              argumentPattern = value;
          }
  
          void print(std::ostream& ostr);
  
      private:
  
          std::string value;
          bool isOperator;
          bool resolved;
  
          int priority;
          ExpNode *expNode;
          bool used; // has the node of this token been used (linked to?)
  
          std::string argumentPattern;
      };
  
      void setExpression(const std::string& newExpression);
      void dumpLists(void);
  
      void defineOperators(void);
      void tokenize(const std::string& str);
      void buildExpressionTree(void);
  
      int countResolvedTokens(void);
  
      static std::map<std::string,int> operatorMap;
      static std::map<std::string,std::string> argumentPatternMap;
      static bool operatorsDefined;
  
      std::list<Token> tList;
      std::list<ExpNode *> eList;
      ExpNode *root;
  }; // End class expression
  
  
  } // End namespace gpstk
  
  #endif // EXPRESSION_HPP
  