pastebin - collaborative debugging tool
kpaste.net RSS


C++ Mathematical Expression Toolkit Library
Posted by Anonymous on Thu 19th Jan 2012 11:08
raw | new post

  1. /*
  2.  **************************************************************
  3.  *         C++ Mathematical Expression Toolkit Library        *
  4.  *                                                            *
  5.  * Author: Arash Partow (1999-2012)                           *
  6.  * URL: http://www.partow.net/programming/exprtk/index.html   *
  7.  *                                                            *
  8.  * Copyright notice:                                          *
  9.  * Free use of the Mathematical Expression Toolkit Library is *
  10.  * permitted under the guidelines and in accordance with the  *
  11.  * most current version of the Common Public License.         *
  12.  * http://www.opensource.org/licenses/cpl1.0.php              *
  13.  *                                                            *
  14.  **************************************************************
  15. */
  16.  
  17. #ifndef INCLUDE_EXPRTK_HPP
  18. #define INCLUDE_EXPRTK_HPP
  19.  
  20. #include <cctype>
  21. #include <iostream>
  22. #include <string>
  23. #include <algorithm>
  24. #include <cmath>
  25. #include <limits>
  26. #include <deque>
  27. #include <map>
  28. #include <stack>
  29.  
  30. namespace exprtk
  31. {
  32.    namespace details
  33.    {
  34.       inline bool is_whitespace(const char& c)
  35.       {
  36.          return (' '  == c) ||
  37.                 ('\n' == c) ||
  38.                 ('\r' == c) ||
  39.                 ('\t' == c);
  40.       }
  41.  
  42.       inline bool is_operator_char(const char& c)
  43.       {
  44.          return ('*' == c) || ('/' == c) ||
  45.                 ('+' == c) || ('-' == c) ||
  46.                 ('^' == c) || ('<' == c) ||
  47.                 ('>' == c) || ('=' == c) ||
  48.                 (',' == c) || ('!' == c) ||
  49.                 ('(' == c) || (')' == c) ||
  50.                 ('[' == c) || (']' == c) ||
  51.                 ('{' == c) || ('}' == c) ||
  52.                 ('%' == c) || (':' == c) ;
  53.       }
  54.  
  55.       inline bool is_letter(const char c)
  56.       {
  57.          return (('a' <= c) && (c <= 'z')) || (('A' <= c) && (c <= 'Z'));
  58.       }
  59.  
  60.       inline bool is_digit(const char c)
  61.       {
  62.          return ('0' <= c) && (c <= '9');
  63.       }
  64.  
  65.       inline bool is_left_bracket(const char c)
  66.       {
  67.          return ('(' == c) || ('[' == c) || ('{' == c);
  68.       }
  69.  
  70.       inline bool is_right_bracket(const char c)
  71.       {
  72.          return (')' == c) || (']' == c) || ('}' == c);
  73.       }
  74.  
  75.       inline bool is_sign(const char c)
  76.       {
  77.          return ('+' == c) || ('-' == c);
  78.       }
  79.  
  80.       inline bool is_invalid(const char& c)
  81.       {
  82.          return !is_whitespace(c)    &&
  83.                 !is_operator_char(c) &&
  84.                 !is_letter(c)        &&
  85.                 !is_digit(c)         &&
  86.                 ('.' != c)           &&
  87.                 ('_' != c)           &&
  88.                 ('$' != c);
  89.       }
  90.  
  91.       static const double pow10[] = {
  92.                                        1.0,
  93.                                        10.0,
  94.                                        100.0,
  95.                                        1000.0,
  96.                                        10000.0,
  97.                                        100000.0,
  98.                                        1000000.0,
  99.                                        10000000.0,
  100.                                        100000000.0,
  101.                                        1000000000.0,
  102.                                        10000000000.0,
  103.                                        100000000000.0,
  104.                                        1000000000000.0,
  105.                                        10000000000000.0,
  106.                                        100000000000000.0,
  107.                                        1000000000000000.0,
  108.                                     };
  109.  
  110.       namespace numeric
  111.       {
  112.          namespace constant
  113.          {
  114.             static const double e       =  2.718281828459045235360;
  115.             static const double pi      =  3.141592653589793238462;
  116.             static const double pi_2    =  1.570796326794896619231;
  117.             static const double pi_4    =  0.785398163397448309616;
  118.             static const double pi_180  =  0.017453292519943295769;
  119.             static const double _1_pi   =  0.318309886183790671538;
  120.             static const double _2_pi   =  0.636619772367581343076;
  121.             static const double _180_pi = 57.295779513082320876798;
  122.          }
  123.  
  124.          namespace details
  125.          {
  126.             struct unknown_type_tag {};
  127.             struct real_type_tag    {};
  128.             struct int_type_tag     {};
  129.  
  130.             template<typename T>
  131.             struct number_type { typedef unknown_type_tag type; };
  132.  
  133.             #define exprtk_register_real_type_tag(T)\
  134.             template<> struct number_type<T> { typedef real_type_tag type; };
  135.  
  136.             #define exprtk_register_int_type_tag(T)\
  137.             template<> struct number_type<T> { typedef int_type_tag type; };
  138.  
  139.             exprtk_register_real_type_tag(double)
  140.             exprtk_register_real_type_tag(long double)
  141.             exprtk_register_real_type_tag(float)
  142.             exprtk_register_int_type_tag(short)
  143.             exprtk_register_int_type_tag(int)
  144.             exprtk_register_int_type_tag(long long int)
  145.             exprtk_register_int_type_tag(unsigned short)
  146.             exprtk_register_int_type_tag(unsigned int)
  147.             exprtk_register_int_type_tag(unsigned long long int)
  148.  
  149.             #undef exprtk_register_real_type_tag
  150.             #undef exprtk_register_real_type_tag
  151.  
  152.             template<typename T>
  153.             inline T modulus_impl(const T& v0, const T& v1, real_type_tag)
  154.             {
  155.                return std::fmod(v0,v1);
  156.             }
  157.  
  158.             template<typename T>
  159.             inline T modulus_impl(const T& v0, const T& v1, int_type_tag)
  160.             {
  161.                return v0 % v1;
  162.             }
  163.          }
  164.  
  165.          template<typename T>
  166.          inline T modulus(const T& v0, const T& v1)
  167.          {
  168.             typename details::number_type<T>::type num_type;
  169.             return details::modulus_impl(v0,v1,num_type);
  170.          }
  171.       }
  172.  
  173.       template <typename T>
  174.       struct token
  175.       {
  176.          enum token_type
  177.          {
  178.             none        =   0,
  179.             error       =   1,
  180.             eof         =   2,
  181.             number      =   3,
  182.             symbol      =   4,
  183.             assign      =   5,
  184.             lte         =   6,
  185.             ne          =   7,
  186.             gte         =   8,
  187.             lt          = '<',
  188.             gt          = '>',
  189.             eq          = '=',
  190.             rbracket    = ')',
  191.             lbracket    = '(',
  192.             rsqrbracket = ']',
  193.             lsqrbracket = '[',
  194.             rcrlbracket = '}',
  195.             lcrlbracket = '{',
  196.             comma       = ',',
  197.             add         = '+',
  198.             sub         = '-',
  199.             div         = '/',
  200.             mul         = '*',
  201.             mod         = '%',
  202.             pow         = '^'
  203.          };
  204.  
  205.          token() {}
  206.  
  207.          token(token_type ttype,
  208.                const char* begin, const char* end,
  209.                const T& numeric_value = T(0))
  210.          : type(ttype),
  211.            value(std::string(begin,end)),
  212.            numeric_value(numeric_value)
  213.          {}
  214.  
  215.          token_type type;
  216.          std::string value;
  217.          T numeric_value;
  218.       };
  219.  
  220.       template <typename T>
  221.       class lexer
  222.       {
  223.       public:
  224.  
  225.          typedef token<T> token_t;
  226.  
  227.          inline bool process(const std::string& str)
  228.          {
  229.             error_description_ = "";
  230.             s_itr = str.data();
  231.             s_end = str.data() + str.size();
  232.             eof_token_ = token_t(token_t::eof,s_end,s_end);
  233.             token_list_.clear();
  234.             while (s_end != s_itr)
  235.             {
  236.                scan_token();
  237.                if (!error_description_.empty())
  238.                {
  239.                   return false;
  240.                }
  241.             }
  242.             token_itr_ = token_list_.begin();
  243.             store_token_itr_ = token_list_.begin();
  244.             return true;
  245.          }
  246.  
  247.          inline void store()
  248.          {
  249.             store_token_itr_ = token_itr_;
  250.          }
  251.  
  252.          inline void restore()
  253.          {
  254.             token_itr_ = store_token_itr_;
  255.          }
  256.  
  257.          inline token_t& next_token()
  258.          {
  259.             if (token_list_.end() != token_itr_)
  260.             {
  261.                return *token_itr_++;
  262.             }
  263.             else
  264.                return eof_token_;
  265.          }
  266.  
  267.          inline std::string error() const
  268.          {
  269.             return error_description_;
  270.          }
  271.  
  272.       private:
  273.  
  274.          inline void scan_token()
  275.          {
  276.             while ((s_end != s_itr) && is_whitespace(*s_itr))
  277.             {
  278.                ++s_itr;
  279.             }
  280.  
  281.             if (s_end == s_itr)
  282.             {
  283.                return;
  284.             }
  285.             else if (is_operator_char(*s_itr))
  286.             {
  287.                if ((s_itr + 1) != s_end)
  288.                {
  289.                   typename token_t::token_type ttype = token_t::none;
  290.                    char c0 = s_itr[0];
  291.                    char c1 = s_itr[1];
  292.                        if ((c0 == '<') && (c1 == '=')) ttype = token_t::lte;
  293.                   else if ((c0 == '>') && (c1 == '=')) ttype = token_t::gte;
  294.                   else if ((c0 == '<') && (c1 == '>')) ttype = token_t::ne;
  295.                   else if ((c0 == '!') && (c1 == '=')) ttype = token_t::ne;
  296.                   else if ((c0 == '=') && (c1 == '=')) ttype = token_t::eq;
  297.                   else if ((c0 == ':') && (c1 == '=')) ttype = token_t::assign;
  298.                   if (0 != ttype)
  299.                   {
  300.                      token_list_.push_back(token_t(ttype,s_itr,s_itr + 2));
  301.                      s_itr += 2;
  302.                      return;
  303.                   }
  304.                }
  305.  
  306.                switch (*s_itr)
  307.                {
  308.                   case '<' : token_list_.push_back(token_t(token_t::lt,s_itr,s_itr + 1));
  309.                              ++s_itr;
  310.                              return;
  311.                   case '>' : token_list_.push_back(token_t(token_t::gt,s_itr,s_itr + 1));
  312.                              ++s_itr;
  313.                              return;
  314.                }
  315.  
  316.                token_list_.push_back(token_t(typename token_t::token_type((*s_itr)),s_itr,s_itr + 1));
  317.                ++s_itr;
  318.                return;
  319.             }
  320.             else if (is_letter(*s_itr))
  321.             {
  322.                scan_symbol();
  323.                return;
  324.             }
  325.             else if (is_digit((*s_itr)) || ('.' == (*s_itr)))
  326.             {
  327.                scan_number();
  328.                return;
  329.             }
  330.             if ('$' == (*s_itr))
  331.             {
  332.                scan_special_function();
  333.                return;
  334.             }
  335.             else
  336.             {
  337.                set_error(std::string("scan_token() - error unrecognized token: ") + std::string(s_itr,s_itr + 2));
  338.                token_list_.push_back(error(s_itr,s_itr + 1));
  339.                ++s_itr;
  340.             }
  341.          }
  342.  
  343.          inline void scan_symbol()
  344.          {
  345.             const char* begin = s_itr;
  346.             while ((s_end != s_itr) &&
  347.                    (is_letter((*s_itr)) || is_digit ((*s_itr)) || ((*s_itr) == '_')))
  348.             {
  349.                ++s_itr;
  350.             }
  351.             token_list_.push_back(token_t(token_t::symbol,begin,s_itr));
  352.          }
  353.  
  354.          inline void scan_number()
  355.          {
  356.             const char* begin = s_itr;
  357.             bool dot_found = false;
  358.             bool e_found = false;
  359.             bool post_e_sign_found = false;
  360.             while (s_end != s_itr)
  361.             {
  362.               if ('.' == (*s_itr))
  363.               {
  364.                  if (dot_found)
  365.                  {
  366.                     set_error(std::string("scan_number() - error invalid numeric token[1]: ") + std::string(begin,s_itr));
  367.                     token_list_.push_back(error(begin,s_itr));
  368.                     return;
  369.                  }
  370.                  dot_found = true;
  371.                  ++s_itr;
  372.                  continue;
  373.               }
  374.               else if (('e' == (*s_itr)) || ('E' == (*s_itr)))
  375.               {
  376.                  const char& c = *(s_itr + 1);
  377.                  if (s_end == (s_itr + 1))
  378.                  {
  379.                     set_error(std::string("scan_number() - error invalid numeric token[2]: ") + std::string(begin,s_itr));
  380.                     token_list_.push_back(error(begin,s_itr));
  381.                     return;
  382.                  }
  383.                  else if (('+' != c) && ('-' != c) && !is_digit(c))
  384.                  {
  385.                     set_error(std::string("scan_number() - error invalid numeric token[3]: ") + std::string(begin,s_itr));
  386.                     token_list_.push_back(error(begin,s_itr));
  387.                     return;
  388.                  }
  389.                  e_found = true;
  390.                  ++s_itr;
  391.                  continue;
  392.               }
  393.               else if (e_found && is_sign(*s_itr))
  394.               {
  395.                  if (post_e_sign_found)
  396.                  {
  397.                     set_error(std::string("scan_number() - error invalid numeric token[4]: ") + std::string(begin,s_itr));
  398.                     token_list_.push_back(error(begin,s_itr));
  399.                     return;
  400.                  }
  401.                  post_e_sign_found = true;
  402.                  ++s_itr;
  403.                  continue;
  404.               }
  405.               else if (('.' != (*s_itr)) && !is_digit(*s_itr))
  406.                   break;
  407.                else
  408.                   ++s_itr;
  409.             }
  410.             T nval = T(atof(std::string(begin,s_itr).c_str()));
  411.             token_list_.push_back(token_t(token_t::number,begin,s_itr,nval));
  412.             return;
  413.          }
  414.  
  415.          inline void scan_special_function()
  416.          {
  417.             const char* begin = s_itr;
  418.             //$fdd(x,x,x) = 11 chars
  419.             if (std::distance(s_itr,s_end) < 11)
  420.             {
  421.                set_error(std::string("scan_special_function() - error invalid special function [1]: ") + std::string(begin,s_itr));
  422.                token_list_.push_back(error(begin,s_itr));
  423.                return;
  424.             }
  425.  
  426.             if (!(('$' == *s_itr) &&
  427.                   ('f' == *(s_itr + 1)) &&
  428.                   ('(' == *(s_itr + 4)) &&
  429.                   (is_digit(*(s_itr + 2))) &&
  430.                   (is_digit(*(s_itr + 3)))))
  431.             {
  432.                set_error(std::string("scan_special_function() - error invalid special function [2]: ") + std::string(begin,s_itr));
  433.                token_list_.push_back(error(begin,s_itr));
  434.                return;
  435.             }
  436.             s_itr += 4;
  437.             token_list_.push_back(token_t(token_t::symbol,begin,s_itr));
  438.             return;
  439.          }
  440.  
  441.          inline void set_error(const std::string& s)
  442.          {
  443.             if (error_description_.empty())
  444.             {
  445.                error_description_ = s;
  446.             }
  447.          }
  448.  
  449.          inline token_t error(const char* begin, const char* end)
  450.          {
  451.             return token_t(token_t::error,begin,end);
  452.          }
  453.  
  454.       private:
  455.  
  456.          std::string error_description_;
  457.          std::deque<token_t> token_list_;
  458.          typename std::deque<token_t>::iterator token_itr_;
  459.          typename std::deque<token_t>::iterator store_token_itr_;
  460.          token_t eof_token_;
  461.          const char* s_itr;
  462.          const char* s_end;
  463.       };
  464.  
  465.       enum operator_type
  466.       {
  467.          e_default,
  468.          e_add    ,
  469.          e_sub    ,
  470.          e_mul    ,
  471.          e_div    ,
  472.          e_mod    ,
  473.          e_pow    ,
  474.          e_atan2  ,
  475.          e_min    ,
  476.          e_max    ,
  477.          e_avg    ,
  478.          e_sum    ,
  479.          e_prod   ,
  480.          e_lt     ,
  481.          e_lte    ,
  482.          e_eq     ,
  483.          e_equal  ,
  484.          e_ne     ,
  485.          e_nequal ,
  486.          e_gte    ,
  487.          e_gt     ,
  488.          e_and    ,
  489.          e_nand   ,
  490.          e_or     ,
  491.          e_nor    ,
  492.          e_xor    ,
  493.          e_abs    ,
  494.          e_acos   ,
  495.          e_asin   ,
  496.          e_atan   ,
  497.          e_ceil   ,
  498.          e_cos    ,
  499.          e_cosh   ,
  500.          e_exp    ,
  501.          e_floor  ,
  502.          e_log    ,
  503.          e_log10  ,
  504.          e_logn   ,
  505.          e_neg    ,
  506.          e_pos    ,
  507.          e_round  ,
  508.          e_roundn ,
  509.          e_root   ,
  510.          e_sqrt   ,
  511.          e_sin    ,
  512.          e_sinh   ,
  513.          e_sec    ,
  514.          e_csc    ,
  515.          e_tan    ,
  516.          e_tanh   ,
  517.          e_cot    ,
  518.          e_clamp  ,
  519.          e_inrange,
  520.          e_r2d    ,
  521.          e_d2r    ,
  522.          e_d2g    ,
  523.          e_g2d    ,
  524.          e_hyp    ,
  525.          e_not    ,
  526.  
  527.          // Do not add new functions/operators after this point.
  528.          e_sf00 = 1000,
  529.          e_sf01 = 1001,
  530.          e_sf02 = 1002,
  531.          e_sf03 = 1003,
  532.          e_sf04 = 1004,
  533.          e_sf05 = 1005,
  534.          e_sf06 = 1006,
  535.          e_sf07 = 1007,
  536.          e_sf08 = 1008,
  537.          e_sf09 = 1009,
  538.          e_sf10 = 1010,
  539.          e_sf11 = 1011,
  540.          e_sf12 = 1012,
  541.          e_sf13 = 1013,
  542.          e_sf14 = 1014,
  543.          e_sf15 = 1015,
  544.          e_sf16 = 1016,
  545.          e_sf17 = 1017,
  546.          e_sf18 = 1018,
  547.          e_sf19 = 1019,
  548.          e_sf20 = 1020,
  549.          e_sf21 = 1021,
  550.          e_sf22 = 1022,
  551.          e_sf23 = 1023,
  552.          e_sf24 = 1024,
  553.          e_sf25 = 1025,
  554.          e_sf26 = 1026,
  555.          e_sf27 = 1027,
  556.          e_sf28 = 1028,
  557.          e_sf29 = 1029,
  558.          e_sf30 = 1030,
  559.          e_sf31 = 1031,
  560.          e_sf32 = 1032,
  561.          e_sf33 = 1033,
  562.          e_sf34 = 1034,
  563.          e_sf35 = 1035,
  564.          e_sf36 = 1036,
  565.          e_sf37 = 1037,
  566.          e_sf38 = 1038,
  567.          e_sf39 = 1039,
  568.          e_sf40 = 1040,
  569.          e_sf41 = 1041,
  570.          e_sf42 = 1042
  571.       };
  572.  
  573.       template <typename T>
  574.       class expression_node
  575.       {
  576.       public:
  577.  
  578.          enum node_type
  579.          {
  580.             e_none        ,
  581.             e_constant    ,
  582.             e_unary       ,
  583.             e_binary      ,
  584.             e_trinary     ,
  585.             e_quaternary  ,
  586.             e_quinary     ,
  587.             e_senary      ,
  588.             e_conditional ,
  589.             e_variable
  590.          };
  591.  
  592.          typedef T value_type;
  593.          typedef expression_node<T>* expression_ptr;
  594.  
  595.          virtual ~expression_node()
  596.          {}
  597.  
  598.          virtual inline T value()
  599.          {
  600.             return std::numeric_limits<T>::quiet_NaN();
  601.          }
  602.  
  603.          virtual inline node_type type() const
  604.          {
  605.             return e_none;
  606.          }
  607.       };
  608.  
  609.       template <typename T>
  610.       class literal_node : public expression_node<T>
  611.       {
  612.       public:
  613.  
  614.          explicit literal_node(const T& value)
  615.          : value_(value)
  616.          {}
  617.  
  618.          inline T value()
  619.          {
  620.             return value_;
  621.          }
  622.  
  623.          inline typename expression_node<T>::node_type type() const
  624.          {
  625.             return expression_node<T>::e_constant;
  626.          }
  627.  
  628.       private:
  629.  
  630.          T value_;
  631.       };
  632.  
  633.       template <typename T>
  634.       class unary_node : public expression_node<T>
  635.       {
  636.       public:
  637.  
  638.          typedef expression_node<T>* expression_ptr;
  639.  
  640.         ~unary_node()
  641.          {
  642.             if (branch_ && branch_deletable_)  { delete branch_; branch_ = 0; }
  643.          }
  644.  
  645.          unary_node(const operator_type& operation,
  646.                     expression_ptr branch)
  647.          : operation_(operation),
  648.            branch_(branch),
  649.            branch_deletable_(expression_node<T>::e_variable != branch_->type())
  650.          {}
  651.  
  652.          inline T value()
  653.          {
  654.             const T arg = branch_->value();
  655.             switch ((operator_type) operation_)
  656.             {
  657.                case e_abs   : return std::abs  (arg);
  658.                case e_acos  : return std::acos (arg);
  659.                case e_asin  : return std::asin (arg);
  660.                case e_atan  : return std::atan (arg);
  661.                case e_ceil  : return std::ceil (arg);
  662.                case e_cos   : return std::cos  (arg);
  663.                case e_cosh  : return std::cosh (arg);
  664.                case e_exp   : return std::exp  (arg);
  665.                case e_floor : return std::floor(arg);
  666.                case e_log   : return std::log  (arg);
  667.                case e_log10 : return std::log10(arg);
  668.                case e_neg   : return -arg;
  669.                case e_pos   : return +arg;
  670.                case e_round : return std::floor(arg + T(0.5));
  671.                case e_sin   : return std::sin  (arg);
  672.                case e_sinh  : return std::sinh (arg);
  673.                case e_sqrt  : return std::sqrt (arg);
  674.                case e_tan   : return std::tan  (arg);
  675.                case e_tanh  : return std::tanh (arg);
  676.                case e_cot   : return T(1) / std::tan(arg);
  677.                case e_sec   : return T(1) / std::cos(arg);
  678.                case e_csc   : return T(1) / std::sin(arg);
  679.                case e_r2d   : return (arg * T(numeric::constant::_180_pi));
  680.                case e_d2r   : return (arg * T(numeric::constant::pi_180));
  681.                case e_d2g   : return (arg * T(20.0/9.0));
  682.                case e_g2d   : return (arg * T(9.0/20.0));
  683.                case e_not   : return (arg != T(0) ? T(0) : T(1));
  684.                default      : return std::numeric_limits<T>::infinity();
  685.             }
  686.          }
  687.  
  688.          inline typename expression_node<T>::node_type type() const
  689.          {
  690.             return expression_node<T>::e_unary;
  691.          }
  692.  
  693.       private:
  694.  
  695.          operator_type  operation_;
  696.          expression_ptr branch_;
  697.          bool           branch_deletable_;
  698.       };
  699.  
  700.       template<std::size_t N, typename T>
  701.       inline void init_branches(std::pair< expression_node<T>*,bool> (&branch)[N],
  702.                                  expression_node<T>* b0,
  703.                                  expression_node<T>* b1 = reinterpret_cast<expression_node<T>*>(0),
  704.                                  expression_node<T>* b2 = reinterpret_cast<expression_node<T>*>(0),
  705.                                  expression_node<T>* b3 = reinterpret_cast<expression_node<T>*>(0),
  706.                                  expression_node<T>* b4 = reinterpret_cast<expression_node<T>*>(0),
  707.                                  expression_node<T>* b5 = reinterpret_cast<expression_node<T>*>(0))
  708.       {
  709.          typedef expression_node<T> Node;
  710.          if (b0 && (N > 0)) { branch[0] = std::make_pair(b0,Node::e_variable != b0->type()); }
  711.          if (b1 && (N > 1)) { branch[1] = std::make_pair(b1,Node::e_variable != b1->type()); }
  712.          if (b2 && (N > 2)) { branch[2] = std::make_pair(b2,Node::e_variable != b2->type()); }
  713.          if (b3 && (N > 3)) { branch[3] = std::make_pair(b3,Node::e_variable != b3->type()); }
  714.          if (b4 && (N > 4)) { branch[4] = std::make_pair(b4,Node::e_variable != b4->type()); }
  715.          if (b5 && (N > 5)) { branch[5] = std::make_pair(b5,Node::e_variable != b5->type()); }
  716.       }
  717.  
  718.       template<std::size_t N, typename T>
  719.       inline void cleanup_branches(std::pair<expression_node<T>*,bool> (&branch)[N])
  720.       {
  721.          for (std::size_t i = 0; i < N; ++i)
  722.          {
  723.             if (branch[i].first && branch[i].second)
  724.             {
  725.                delete branch[i].first;
  726.                branch[i].first = 0;
  727.             }
  728.          }
  729.       }
  730.  
  731.       template <typename T>
  732.       class binary_node : public expression_node<T>
  733.       {
  734.       public:
  735.  
  736.          typedef expression_node<T>* expression_ptr;
  737.          typedef std::pair<expression_ptr,bool> branch_t;
  738.  
  739.          binary_node(const operator_type& operation,
  740.                      expression_ptr branch0,
  741.                      expression_ptr branch1)
  742.          : operation_(operation)
  743.          {
  744.             init_branches<2>(branch_,branch0,branch1);
  745.          }
  746.  
  747.         ~binary_node()
  748.          {
  749.             cleanup_branches<2>(branch_);
  750.          }
  751.  
  752.          inline T value()
  753.          {
  754.             const T arg0 = branch_[0].first->value();
  755.             const T arg1 = branch_[1].first->value();
  756.             switch (operation_)
  757.             {
  758.                case e_add    : return (arg0 + arg1);
  759.                case e_sub    : return (arg0 - arg1);
  760.                case e_mul    : return (arg0 * arg1);
  761.                case e_div    : return (arg0 / arg1);
  762.                case e_mod    : return details::numeric::modulus<T>(arg0,arg1);
  763.                case e_pow    : return std::pow(arg0, arg1);
  764.                case e_atan2  : return std::atan2(arg0, arg1);
  765.                case e_min    : return std::min<T>(arg0,arg1);
  766.                case e_max    : return std::max<T>(arg0,arg1);
  767.                case e_logn   : return std::log(arg0) / std::log(arg1);
  768.                case e_lt     : return (arg0 <  arg1) ? T(1) : T(0);
  769.                case e_lte    : return (arg0 <= arg1) ? T(1) : T(0);
  770.                case e_eq     : return (arg0 == arg1) ? T(1) : T(0);
  771.                case e_ne     : return (arg0 != arg1) ? T(1) : T(0);
  772.                case e_gte    : return (arg0 >= arg1) ? T(1) : T(0);
  773.                case e_gt     : return (arg0 >  arg1) ? T(1) : T(0);
  774.                case e_and    : return (arg0 != 0.0) && (arg1 != 0.0) ? T(1) : T(0);
  775.                case e_nand   : return (arg0 != 0.0) && (arg1 != 0.0) ? T(0) : T(1);
  776.                case e_or     : return (arg0 != 0.0) || (arg1 != 0.0) ? T(1) : T(0);
  777.                case e_nor    : return (arg0 != 0.0) || (arg1 != 0.0) ? T(0) : T(1);
  778.                case e_xor    : return (arg0 != arg1) ? T(1) : T(0);
  779.                case e_root   : return std::pow(arg0, T(1) / arg1);
  780.                case e_roundn : return std::floor((arg0 * pow10[(int)std::floor(arg1)]) + T(0.5)) / T(pow10[(int)std::floor(arg1)]);
  781.                case e_equal  : return (std::abs(arg0 - arg1) <= (std::max(T(1),std::max(std::abs(arg0),std::abs(arg1))) * T(0.0000000001))) ? T(1) : T(0);
  782.                case e_nequal : return (std::abs(arg0 - arg1) >  (std::max(T(1),std::max(std::abs(arg0),std::abs(arg1))) * T(0.0000000001))) ? T(1) : T(0);
  783.                case e_hyp    : return std::sqrt((arg0 * arg0) + (arg1 * arg1));
  784.                case e_avg    : return (arg0 + arg1)/T(2.0);
  785.                case e_sum    : return (arg0 + arg1);
  786.                case e_prod   : return (arg0 * arg1);
  787.                default       : return std::numeric_limits<T>::infinity();
  788.             }
  789.          }
  790.  
  791.          inline typename expression_node<T>::node_type type() const
  792.          {
  793.             return expression_node<T>::e_binary;
  794.          }
  795.  
  796.       private:
  797.  
  798.          operator_type  operation_;
  799.          branch_t branch_[2];
  800.       };
  801.  
  802.       template <typename T>
  803.       class trinary_node : public expression_node<T>
  804.       {
  805.       public:
  806.  
  807.          typedef expression_node<T>* expression_ptr;
  808.          typedef std::pair<expression_ptr,bool> branch_t;
  809.  
  810.          trinary_node(const operator_type& operation,
  811.                       expression_ptr branch0,
  812.                       expression_ptr branch1,
  813.                       expression_ptr branch2)
  814.          : operation_(operation)
  815.          {
  816.             init_branches<3>(branch_,branch0,branch1,branch2);
  817.          }
  818.  
  819.         ~trinary_node()
  820.          {
  821.             cleanup_branches<3>(branch_);
  822.          }
  823.  
  824.          inline T value()
  825.          {
  826.             const T arg0 = branch_[0].first->value();
  827.             const T arg1 = branch_[1].first->value();
  828.             const T arg2 = branch_[2].first->value();
  829.             switch (operation_)
  830.             {
  831.                case e_clamp   : return (arg1 < arg0) ? arg0 : (arg1 > arg2 ? arg2 : arg1);
  832.                case e_inrange : return (arg1 < arg0) ? T(0) : ((arg1 > arg2) ? T(0) : T(1));
  833.                case e_min     : return std::min<T>(std::min<T>(arg0,arg1),arg2);
  834.                case e_max     : return std::max<T>(std::max<T>(arg0,arg1),arg2);
  835.                case e_avg     : return (arg0 + arg1 + arg2) / T(3.0);
  836.                case e_sum     : return (arg0 + arg1 + arg2);
  837.                case e_prod    : return (arg0 * arg1 * arg2);
  838.                default        : return std::numeric_limits<T>::infinity();
  839.             }
  840.          }
  841.  
  842.          inline typename expression_node<T>::node_type type() const
  843.          {
  844.             return expression_node<T>::e_trinary;
  845.          }
  846.  
  847.       protected:
  848.  
  849.          operator_type operation_;
  850.          branch_t branch_[3];
  851.       };
  852.  
  853.       template <typename T>
  854.       class quaternary_node : public expression_node<T>
  855.       {
  856.       public:
  857.  
  858.          typedef expression_node<T>* expression_ptr;
  859.          typedef std::pair<expression_ptr,bool> branch_t;
  860.  
  861.          quaternary_node(const operator_type& operation,
  862.                          expression_ptr branch0,
  863.                          expression_ptr branch1,
  864.                          expression_ptr branch2,
  865.                          expression_ptr branch3)
  866.          : operation_(operation)
  867.          {
  868.             init_branches<4>(branch_,branch0,branch1,branch2,branch3);
  869.          }
  870.  
  871.          ~quaternary_node()
  872.          {
  873.             cleanup_branches<4>(branch_);
  874.          }
  875.  
  876.          inline T value()
  877.          {
  878.             const T arg0 = branch_[0].first->value();
  879.             const T arg1 = branch_[1].first->value();
  880.             const T arg2 = branch_[2].first->value();
  881.             const T arg3 = branch_[3].first->value();
  882.             switch (operation_)
  883.             {
  884.                case e_min     : return std::min<T>(std::min<T>(arg0,arg1),std::min<T>(arg2,arg3));
  885.                case e_max     : return std::max<T>(std::max<T>(arg0,arg1),std::max<T>(arg2,arg3));
  886.                case e_avg     : return (arg0 + arg1 + arg2 + arg3) / T(4.0);
  887.                case e_sum     : return (arg0 + arg1 + arg2 + arg3);
  888.                case e_prod    : return (arg0 * arg1 * arg2 * arg3);
  889.                case e_default :
  890.                default        : return std::numeric_limits<T>::infinity();
  891.             }
  892.          }
  893.  
  894.          inline typename expression_node<T>::node_type type() const
  895.          {
  896.             return expression_node<T>::e_quaternary;
  897.          }
  898.  
  899.       protected:
  900.  
  901.          operator_type operation_;
  902.          branch_t branch_[4];
  903.       };
  904.  
  905.       template <typename T>
  906.       class quinary_node : public expression_node<T>
  907.       {
  908.       public:
  909.  
  910.          typedef expression_node<T>* expression_ptr;
  911.          typedef std::pair<expression_ptr,bool> branch_t;
  912.  
  913.          quinary_node(const operator_type& operation,
  914.                       expression_ptr branch0,
  915.                       expression_ptr branch1,
  916.                       expression_ptr branch2,
  917.                       expression_ptr branch3,
  918.                       expression_ptr branch4)
  919.          : operation_(operation)
  920.          {
  921.             init_branches<5>(branch_,branch0,branch1,branch2,branch3,branch4);
  922.          }
  923.  
  924.         ~quinary_node()
  925.          {
  926.             cleanup_branches<5>(branch_);
  927.          }
  928.  
  929.          inline T value()
  930.          {
  931.             const T arg0 = branch_[0].first->value();
  932.             const T arg1 = branch_[1].first->value();
  933.             const T arg2 = branch_[2].first->value();
  934.             const T arg3 = branch_[3].first->value();
  935.             const T arg4 = branch_[4].first->value();
  936.             switch (operation_)
  937.             {
  938.                case e_min     : return std::min<T>(std::min<T>(std::min<T>(arg0,arg1),std::min<T>(arg2,arg3)),arg4);
  939.                case e_max     : return std::max<T>(std::max<T>(std::max<T>(arg0,arg1),std::max<T>(arg2,arg3)),arg4);
  940.                case e_avg     : return (arg0 + arg1 + arg2 + arg3 + arg4) / T(5.0);
  941.                case e_sum     : return (arg0 + arg1 + arg2 + arg3 + arg4);
  942.                case e_prod    : return (arg0 * arg1 * arg2 * arg3 * arg4);
  943.                case e_default :
  944.                default        : return std::numeric_limits<T>::infinity();
  945.             }
  946.          }
  947.  
  948.          inline typename expression_node<T>::node_type type() const
  949.          {
  950.             return expression_node<T>::e_quinary;
  951.          }
  952.  
  953.       private:
  954.  
  955.          operator_type operation_;
  956.          branch_t branch_[5];
  957.       };
  958.  
  959.       template <typename T>
  960.       class senary_node : public expression_node<T>
  961.       {
  962.       public:
  963.  
  964.          typedef expression_node<T>* expression_ptr;
  965.          typedef std::pair<expression_ptr,bool> branch_t;
  966.  
  967.          senary_node(const operator_type& operation,
  968.                       expression_ptr branch0,
  969.                       expression_ptr branch1,
  970.                       expression_ptr branch2,
  971.                       expression_ptr branch3,
  972.                       expression_ptr branch4,
  973.                       expression_ptr branch5)
  974.          : operation_(operation)
  975.          {
  976.             init_branches<6>(branch_,branch0,branch1,branch2,branch3,branch4,branch5);
  977.          }
  978.  
  979.         ~senary_node()
  980.          {
  981.             cleanup_branches<6>(branch_);
  982.          }
  983.  
  984.          inline T value()
  985.          {
  986.             const T arg0 = branch_[0].first->value();
  987.             const T arg1 = branch_[1].first->value();
  988.             const T arg2 = branch_[2].first->value();
  989.             const T arg3 = branch_[3].first->value();
  990.             const T arg4 = branch_[4].first->value();
  991.             const T arg5 = branch_[5].first->value();
  992.             switch (operation_)
  993.             {
  994.                case e_min     : return std::min<T>(std::min<T>(std::min<T>(arg0,arg1),std::min<T>(arg2,arg3)),std::min<T>(arg4,arg5));
  995.                case e_max     : return std::max<T>(std::max<T>(std::max<T>(arg0,arg1),std::max<T>(arg2,arg3)),std::max<T>(arg4,arg5));
  996.                case e_avg     : return (arg0 + arg1 + arg2 + arg3 + arg4 + arg5) / T(6.0);
  997.                case e_sum     : return (arg0 + arg1 + arg2 + arg3 + arg4 + arg5);
  998.                case e_prod    : return (arg0 * arg1 * arg2 * arg3 * arg4 * arg5);
  999.                case e_default :
  1000.                default        : return std::numeric_limits<T>::infinity();
  1001.             }
  1002.          }
  1003.  
  1004.          inline typename expression_node<T>::node_type type() const
  1005.          {
  1006.             return expression_node<T>::e_senary;
  1007.          }
  1008.  
  1009.       private:
  1010.  
  1011.          operator_type operation_;
  1012.          branch_t branch_[6];
  1013.       };
  1014.  
  1015.       template <typename T>
  1016.       class conditional_node : public expression_node<T>
  1017.       {
  1018.       public:
  1019.  
  1020.          typedef expression_node<T>* expression_ptr;
  1021.  
  1022.          conditional_node(expression_ptr test,
  1023.                           expression_ptr consequent,
  1024.                           expression_ptr alternative)
  1025.          : test_(test),
  1026.            consequent_(consequent),
  1027.            alternative_(alternative),
  1028.            test_deletable_(expression_node<T>::e_variable != test_->type()),
  1029.            consequent_deletable_(expression_node<T>::e_variable != consequent_->type()),
  1030.            alternative_deletable_(expression_node<T>::e_variable != alternative_->type())
  1031.          {}
  1032.  
  1033.         ~conditional_node()
  1034.          {
  1035.             if (test_        &&        test_deletable_) delete test_;
  1036.             if (consequent_  &&  consequent_deletable_) delete consequent_;
  1037.             if (alternative_ && alternative_deletable_) delete alternative_;
  1038.          }
  1039.  
  1040.          inline T value()
  1041.          {
  1042.             if (test_->value() != 0)
  1043.                return consequent_->value();
  1044.             else
  1045.                return alternative_->value();
  1046.          }
  1047.  
  1048.          inline typename expression_node<T>::node_type type() const
  1049.          {
  1050.             return expression_node<T>::e_conditional;
  1051.          }
  1052.  
  1053.       private:
  1054.  
  1055.          expression_ptr test_;
  1056.          expression_ptr consequent_;
  1057.          expression_ptr alternative_;
  1058.          bool test_deletable_;
  1059.          bool consequent_deletable_;
  1060.          bool alternative_deletable_;
  1061.       };
  1062.  
  1063.       template <typename T>
  1064.       class variable_node : public expression_node<T>
  1065.       {
  1066.       public:
  1067.  
  1068.          static T null_value;
  1069.  
  1070.          explicit variable_node()
  1071.          : value_(&null_value)
  1072.          {}
  1073.  
  1074.          explicit variable_node(T& value)
  1075.          : value_(&value)
  1076.          {}
  1077.  
  1078.          inline bool operator <(const variable_node<T>& v) const
  1079.          {
  1080.             return this < (&v);
  1081.          }
  1082.  
  1083.          inline T value()
  1084.          {
  1085.             return (*value_);
  1086.          }
  1087.  
  1088.          inline T& ref()
  1089.          {
  1090.             return (*value_);
  1091.          }
  1092.  
  1093.          inline const T& ref() const
  1094.          {
  1095.             return (*value_);
  1096.          }
  1097.  
  1098.          inline typename expression_node<T>::node_type type() const
  1099.          {
  1100.             return expression_node<T>::e_variable;
  1101.          }
  1102.  
  1103.       private:
  1104.  
  1105.          T* value_;
  1106.       };
  1107.  
  1108.       template<typename T>
  1109.       T variable_node<T>::null_value = T(std::numeric_limits<T>::infinity());
  1110.  
  1111.       template <typename T>
  1112.       class sf3_node : public trinary_node<T>
  1113.       {
  1114.       public:
  1115.  
  1116.          typedef expression_node<T>* expression_ptr;
  1117.  
  1118.          sf3_node(const operator_type& operation,
  1119.                   expression_ptr branch0,
  1120.                   expression_ptr branch1,
  1121.                   expression_ptr branch2)
  1122.          : trinary_node<T>(operation,branch0,branch1,branch2)
  1123.          {}
  1124.  
  1125.          inline T value()
  1126.          {
  1127.             const T x = trinary_node<T>::branch_[0].first->value();
  1128.             const T y = trinary_node<T>::branch_[1].first->value();
  1129.             const T z = trinary_node<T>::branch_[2].first->value();
  1130.  
  1131.             switch(trinary_node<T>::operation_)
  1132.             {
  1133.                case e_sf00 : return (x + y) / z;
  1134.                case e_sf01 : return (x + y) * z;
  1135.                case e_sf02 : return (x - y) / z;
  1136.                case e_sf03 : return (x - y) * z;
  1137.                case e_sf04 : return (x * y) + z;
  1138.                case e_sf05 : return (x * y) - z;
  1139.                case e_sf06 : return (x * y) / z;
  1140.                case e_sf07 : return (x * y) * z;
  1141.                case e_sf08 : return (x / y) + z;
  1142.                case e_sf09 : return (x / y) - z;
  1143.                case e_sf10 : return (x / y) / z;
  1144.                case e_sf11 : return (x / y) * z;
  1145.                case e_sf12 : return z / (x + y);
  1146.                case e_sf13 : return z / (x - y);
  1147.                case e_sf14 : return z / (x * y);
  1148.                case e_sf15 : return z / (x / y);
  1149.                case e_sf16 : return z - (x / y);
  1150.                case e_sf17 : return z - (x / y);
  1151.                default     : return std::numeric_limits<T>::infinity();
  1152.             }
  1153.          }
  1154.       };
  1155.  
  1156.       template <typename T>
  1157.       class sf4_node : public quaternary_node<T>
  1158.       {
  1159.       public:
  1160.  
  1161.          typedef expression_node<T>* expression_ptr;
  1162.  
  1163.          sf4_node(const operator_type& operation,
  1164.                   expression_ptr branch0,
  1165.                   expression_ptr branch1,
  1166.                   expression_ptr branch2,
  1167.                   expression_ptr branch3)
  1168.          : quaternary_node<T>(operation,branch0,branch1,branch2,branch3)
  1169.          {}
  1170.  
  1171.          inline T value()
  1172.          {
  1173.             const T x = quaternary_node<T>::branch_[0].first->value();
  1174.             const T y = quaternary_node<T>::branch_[1].first->value();
  1175.             const T z = quaternary_node<T>::branch_[2].first->value();
  1176.             const T w = quaternary_node<T>::branch_[3].first->value();
  1177.  
  1178.             switch(quaternary_node<T>::operation_)
  1179.             {
  1180.                case e_sf18 : return w + ((x + y) / z);
  1181.                case e_sf19 : return w + ((x + y) * z);
  1182.                case e_sf20 : return w + ((x - y) / z);
  1183.                case e_sf21 : return w + ((x - y) * z);
  1184.                case e_sf22 : return w + ((x * y) / z);
  1185.                case e_sf23 : return w + ((x * y) * z);
  1186.                case e_sf24 : return w + ((x / y) + z);
  1187.                case e_sf25 : return w + ((x / y) / z);
  1188.                case e_sf26 : return w + ((x / y) * z);
  1189.                case e_sf27 : return w - ((x + y) / z);
  1190.                case e_sf28 : return w - ((x + y) * z);
  1191.                case e_sf29 : return w - ((x - y) / z);
  1192.                case e_sf30 : return w - ((x - y) * z);
  1193.                case e_sf31 : return w - ((x * y) / z);
  1194.                case e_sf32 : return w - ((x * y) * z);
  1195.                case e_sf33 : return w - ((x / y) / z);
  1196.                case e_sf34 : return w - ((x / y) * z);
  1197.                case e_sf35 : return ((x + y) * z) - w;
  1198.                case e_sf36 : return ((x - y) * z) - w;
  1199.                case e_sf37 : return ((x * y) * z) - w;
  1200.                case e_sf38 : return ((x / y) * z) - w;
  1201.                case e_sf39 : return ((x + y) / z) - w;
  1202.                case e_sf40 : return ((x - y) / z) - w;
  1203.                case e_sf41 : return ((x * y) / z) - w;
  1204.                case e_sf42 : return ((x / y) / z) - w;
  1205.                default     : return std::numeric_limits<T>::infinity();
  1206.             }
  1207.          }
  1208.       };
  1209.  
  1210.       class node_allocator
  1211.       {
  1212.       public:
  1213.  
  1214.          enum { buffer_size = 512 * 1024 };
  1215.  
  1216.          template <typename ResultNode, typename OpType, typename ExprNode>
  1217.          inline expression_node<typename ResultNode::value_type>* allocate(const OpType& operation, ExprNode (&branch)[1])
  1218.          {
  1219.             return allocate<ResultNode>(operation,branch[0]);
  1220.          }
  1221.  
  1222.          template <typename ResultNode, typename OpType, typename ExprNode>
  1223.          inline expression_node<typename ResultNode::value_type>* allocate(const OpType& operation, ExprNode (&branch)[2])
  1224.          {
  1225.             return allocate<ResultNode>(operation,branch[0],branch[1]);
  1226.          }
  1227.  
  1228.          template <typename ResultNode, typename OpType, typename ExprNode>
  1229.          inline expression_node<typename ResultNode::value_type>* allocate(const OpType& operation, ExprNode (&branch)[3])
  1230.          {
  1231.             return allocate<ResultNode>(operation,branch[0],branch[1],branch[2]);
  1232.          }
  1233.  
  1234.          template <typename ResultNode, typename OpType, typename ExprNode>
  1235.          inline expression_node<typename ResultNode::value_type>* allocate(const OpType& operation, ExprNode (&branch)[4])
  1236.          {
  1237.             return allocate<ResultNode>(operation,branch[0],branch[1],branch[2],branch[3]);
  1238.          }
  1239.  
  1240.          template <typename ResultNode, typename OpType, typename ExprNode>
  1241.          inline expression_node<typename ResultNode::value_type>* allocate(const OpType& operation, ExprNode (&branch)[5])
  1242.          {
  1243.             return allocate<ResultNode>(operation,branch[0],branch[1],branch[2],branch[3],branch[4]);
  1244.          }
  1245.  
  1246.          template <typename ResultNode, typename OpType, typename ExprNode>
  1247.          inline expression_node<typename ResultNode::value_type>* allocate(const OpType& operation, ExprNode (&branch)[6])
  1248.          {
  1249.             return allocate<ResultNode>(operation,branch[0],branch[1],branch[2],branch[3],branch[4],branch[5]);
  1250.          }
  1251.  
  1252.          template <typename node_type, typename T1>
  1253.          inline expression_node<typename node_type::value_type>* allocate(const T1& t1) const
  1254.          {
  1255.             return new node_type(t1);
  1256.          }
  1257.  
  1258.          template <typename node_type,
  1259.                    typename T1,
  1260.                    typename T2>
  1261.          inline expression_node<typename node_type::value_type>* allocate(const T1& t1, const T2& t2) const
  1262.          {
  1263.             return new node_type(t1,t2);
  1264.          }
  1265.  
  1266.          template <typename node_type,
  1267.                    typename T1, typename T2,
  1268.                    typename T3>
  1269.          inline expression_node<typename node_type::value_type>* allocate(const T1& t1, const T2& t2,
  1270.                                                                           const T3& t3) const
  1271.          {
  1272.             return new node_type(t1,t2,t3);
  1273.          }
  1274.  
  1275.          template <typename node_type,
  1276.                    typename T1, typename T2,
  1277.                    typename T3, typename T4>
  1278.          inline expression_node<typename node_type::value_type>* allocate(const T1& t1, const T2& t2,
  1279.                                                                           const T3& t3, const T4& t4) const
  1280.          {
  1281.             return new node_type(t1,t2,t3,t4);
  1282.          }
  1283.  
  1284.          template <typename node_type,
  1285.                    typename T1, typename T2,
  1286.                    typename T3, typename T4, typename T5>
  1287.          inline expression_node<typename node_type::value_type>* allocate(const T1& t1, const T2& t2,
  1288.                                                                           const T3& t3, const T4& t4,
  1289.                                                                           const T5& t5) const
  1290.          {
  1291.             return new node_type(t1,t2,t3,t4,t5);
  1292.          }
  1293.  
  1294.          template <typename node_type,
  1295.                    typename T1, typename T2,
  1296.                    typename T3, typename T4, typename T5, typename T6>
  1297.          inline expression_node<typename node_type::value_type>* allocate(const T1& t1, const T2& t2,
  1298.                                                                           const T3& t3, const T4& t4,
  1299.                                                                           const T5& t5, const T6& t6) const
  1300.          {
  1301.             return new node_type(t1,t2,t3,t4,t5,t6);
  1302.          }
  1303.  
  1304.          template <typename node_type,
  1305.                    typename T1, typename T2,
  1306.                    typename T3, typename T4,
  1307.                    typename T5, typename T6, typename T7>
  1308.          inline expression_node<typename node_type::value_type>* allocate(const T1& t1, const T2& t2,
  1309.                                                                           const T3& t3, const T4& t4,
  1310.                                                                           const T5& t5, const T6& t6,
  1311.                                                                           const T7& t7) const
  1312.          {
  1313.             return new node_type(t1,t2,t3,t4,t5,t6,t7);
  1314.          }
  1315.  
  1316.          template <typename T>
  1317.          void inline free(expression_node<T>*& e) const
  1318.          {
  1319.             delete e;
  1320.             e = 0;
  1321.          }
  1322.       };
  1323.  
  1324.       struct operation_t
  1325.       {
  1326.          operation_t(const std::string& n, const operator_type t, const unsigned int& np)
  1327.          : name(n),
  1328.            type(t),
  1329.            num_params(np)
  1330.          {}
  1331.  
  1332.          std::string name;
  1333.          operator_type type;
  1334.          unsigned int num_params;
  1335.       };
  1336.  
  1337.       static const operation_t operation_list[] =
  1338.                                  {
  1339.                                     operation_t(      "abs" , e_abs    , 1),
  1340.                                     operation_t(     "acos" , e_acos   , 1),
  1341.                                     operation_t(     "asin" , e_asin   , 1),
  1342.                                     operation_t(     "atan" , e_atan   , 1),
  1343.                                     operation_t(     "ceil" , e_ceil   , 1),
  1344.                                     operation_t(      "cos" , e_cos    , 1),
  1345.                                     operation_t(     "cosh" , e_cosh   , 1),
  1346.                                     operation_t(      "exp" , e_exp    , 1),
  1347.                                     operation_t(    "floor" , e_floor  , 1),
  1348.                                     operation_t(      "log" , e_log    , 1),
  1349.                                     operation_t(    "log10" , e_log10  , 1),
  1350.                                     operation_t(    "round" , e_round  , 1),
  1351.                                     operation_t(      "sin" , e_sin    , 1),
  1352.                                     operation_t(     "sinh" , e_sinh   , 1),
  1353.                                     operation_t(      "sec" , e_sec    , 1),
  1354.                                     operation_t(      "csc" , e_csc    , 1),
  1355.                                     operation_t(     "sqrt" , e_sqrt   , 1),
  1356.                                     operation_t(      "tan" , e_tan    , 1),
  1357.                                     operation_t(     "tanh" , e_tanh   , 1),
  1358.                                     operation_t(      "cot" , e_cot    , 1),
  1359.                                     operation_t(  "rad2deg" , e_r2d    , 1),
  1360.                                     operation_t(  "deg2rad" , e_d2r    , 1),
  1361.                                     operation_t( "deg2grad" , e_d2g    , 1),
  1362.                                     operation_t( "grad2deg" , e_g2d    , 1),
  1363.                                     operation_t(      "not" , e_not    , 1),
  1364.                                     operation_t(    "atan2", e_atan2   , 2),
  1365.                                     operation_t(      "min", e_min     , 2),
  1366.                                     operation_t(      "max", e_max     , 2),
  1367.                                     operation_t(      "avg", e_avg     , 2),
  1368.                                     operation_t(      "sum", e_sum     , 2),
  1369.                                     operation_t(      "mul", e_prod    , 2),
  1370.                                     operation_t(      "mod", e_mod     , 2),
  1371.                                     operation_t(     "logn", e_logn    , 2),
  1372.                                     operation_t(     "root", e_root    , 2),
  1373.                                     operation_t(   "roundn", e_roundn  , 2),
  1374.                                     operation_t(    "equal", e_equal   , 2),
  1375.                                     operation_t("not_equal", e_nequal  , 2),
  1376.                                     operation_t(      "hyp", e_hyp     , 2),
  1377.                                     operation_t(    "clamp", e_clamp   , 3),
  1378.                                     operation_t(  "inrange", e_inrange , 3),
  1379.                                     operation_t(      "min", e_min     , 3),
  1380.                                     operation_t(      "max", e_max     , 3),
  1381.                                     operation_t(      "avg", e_avg     , 3),
  1382.                                     operation_t(      "sum", e_sum     , 3),
  1383.                                     operation_t(      "mul", e_prod    , 3),
  1384.                                     operation_t(      "min", e_min     , 4),
  1385.                                     operation_t(      "max", e_max     , 4),
  1386.                                     operation_t(      "avg", e_avg     , 4),
  1387.                                     operation_t(      "sum", e_sum     , 4),
  1388.                                     operation_t(      "mul", e_prod    , 4),
  1389.                                     operation_t(      "min", e_min     , 5),
  1390.                                     operation_t(      "max", e_max     , 5),
  1391.                                     operation_t(      "avg", e_avg     , 5),
  1392.                                     operation_t(      "sum", e_sum     , 5),
  1393.                                     operation_t(      "mul", e_prod    , 5),
  1394.                                     operation_t(      "min", e_min     , 6),
  1395.                                     operation_t(      "max", e_max     , 6),
  1396.                                     operation_t(      "avg", e_avg     , 6),
  1397.                                     operation_t(      "sum", e_sum     , 6),
  1398.                                     operation_t(      "mul", e_prod    , 6),
  1399.                                  };
  1400.  
  1401.       static const std::size_t operation_list_size = sizeof(operation_list) / sizeof(operation_t);
  1402.  
  1403.    } // namespace details
  1404.  
  1405.    template <typename T>
  1406.    class symbol_table
  1407.    {
  1408.    private:
  1409.       typedef typename details::variable_node<T> variable_t;
  1410.       typedef std::pair<bool,variable_t> variable_pair_t;
  1411.       typedef variable_t* variable_ptr;
  1412.       typedef std::pair<bool,variable_ptr> vpair_t;
  1413.       typedef std::map<std::string,vpair_t> variable_map_t;
  1414.       typedef typename variable_map_t::iterator vm_itr_t;
  1415.       typedef typename variable_map_t::const_iterator vm_const_itr_t;
  1416.  
  1417.       static const std::size_t lut_size = 256;
  1418.  
  1419.    public:
  1420.  
  1421.       symbol_table()
  1422.       {
  1423.          clear_short_var_lut();
  1424.       }
  1425.  
  1426.      ~symbol_table()
  1427.       {
  1428.          vm_itr_t itr = variable_map_.begin();
  1429.          vm_itr_t end = variable_map_.end();
  1430.          while (end != itr)
  1431.          {
  1432.             delete (*itr).second.second;
  1433.             ++itr;
  1434.          }
  1435.          variable_map_.clear();
  1436.          clear_short_var_lut();
  1437.       }
  1438.  
  1439.       inline variable_ptr get_variable(const std::string& name)
  1440.       {
  1441.          if (name.empty())
  1442.             return reinterpret_cast<variable_ptr>(0);
  1443.          else if (!details::is_letter(name[0]))
  1444.             return reinterpret_cast<variable_ptr>(0);
  1445.          else if (1 == name.size())
  1446.          {
  1447.             variable_pair_t& vp = short_variable_lut_[static_cast<std::size_t>(name[0])];
  1448.             if (vp.first)
  1449.                return &(vp.second);
  1450.             else
  1451.                return reinterpret_cast<variable_ptr>(0);
  1452.          }
  1453.          else
  1454.          {
  1455.             vm_const_itr_t itr = variable_map_.find(name);
  1456.             if (variable_map_.end() == itr)
  1457.                return reinterpret_cast<variable_ptr>(0);
  1458.             else
  1459.                return itr->second.second;
  1460.          }
  1461.       }
  1462.  
  1463.       inline T& variable_ref(const std::string& name)
  1464.       {
  1465.          static T null_var = T(0);
  1466.          if (name.empty())
  1467.             return null_var;
  1468.          else if (!details::is_letter(name[0]))
  1469.             return null_var;
  1470.          else if (1 == name.size())
  1471.          {
  1472.             variable_pair_t& vp = short_variable_lut_[static_cast<std::size_t>(name[0])];
  1473.             if (vp.first)
  1474.                return vp.second.ref();
  1475.             else
  1476.                return null_var;
  1477.          }
  1478.          else
  1479.          {
  1480.             vm_const_itr_t itr = variable_map_.find(name);
  1481.             if (variable_map_.end() == itr)
  1482.                return null_var;
  1483.             else
  1484.                return itr->second.second->ref();
  1485.          }
  1486.       }
  1487.  
  1488.       inline bool is_constant(const std::string& name) const
  1489.       {
  1490.          vm_const_itr_t itr = variable_map_.find(name);
  1491.          if (variable_map_.end() == itr)
  1492.             return false;
  1493.          else
  1494.             return itr->second.first;
  1495.       }
  1496.  
  1497.       inline bool add_variable(const std::string& name, T& t, const bool is_constant = false)
  1498.       {
  1499.          if (name.empty())
  1500.             return false;
  1501.          else if (!details::is_letter(name[0]))
  1502.             return false;
  1503.          else if (1 == name.size())
  1504.          {
  1505.             variable_pair_t& vp = short_variable_lut_[static_cast<std::size_t>(name[0])];
  1506.             vp.first = true;
  1507.             vp.second = variable_t(t);
  1508.          }
  1509.          else
  1510.          {
  1511.             vm_itr_t itr = variable_map_.find(name);
  1512.             if (variable_map_.end() == itr)
  1513.             {
  1514.                variable_map_[name] = std::make_pair(is_constant,new details::variable_node<T>(t));
  1515.             }
  1516.          }
  1517.          return true;
  1518.       }
  1519.  
  1520.       inline bool remove_variable(const std::string& name)
  1521.       {
  1522.          vm_itr_t itr = variable_map_.find(name);
  1523.          if (variable_map_.end() != itr)
  1524.          {
  1525.             variable_map_.erase(itr);
  1526.             return true;
  1527.          }
  1528.          else
  1529.             return false;
  1530.       }
  1531.  
  1532.       inline void add_constants()
  1533.       {
  1534.          add_pi();
  1535.          add_epsilon();
  1536.          add_infinity();
  1537.       }
  1538.  
  1539.       inline void add_pi()
  1540.       {
  1541.          static T pi = T(details::numeric::constant::pi);
  1542.          add_variable("pi",pi,true);
  1543.       }
  1544.  
  1545.       inline void add_epsilon()
  1546.       {
  1547.          static T epsilon = std::numeric_limits<T>::epsilon();
  1548.          add_variable("epsilon",epsilon,true);
  1549.       }
  1550.  
  1551.       inline void add_infinity()
  1552.       {
  1553.          static T infinity = std::numeric_limits<T>::infinity();
  1554.          add_variable("inf",infinity,true);
  1555.       }
  1556.  
  1557.    private:
  1558.  
  1559.       inline void clear_short_var_lut()
  1560.       {
  1561.          for (std::size_t i = 0; i < lut_size; ++i)
  1562.          {
  1563.             short_variable_lut_[i].first = false;
  1564.          }
  1565.       }
  1566.  
  1567.       variable_pair_t short_variable_lut_[lut_size];
  1568.       variable_map_t  variable_map_;
  1569.    };
  1570.  
  1571.    template <typename T> class parser;
  1572.  
  1573.    template <typename T>
  1574.    class expression
  1575.    {
  1576.    private:
  1577.  
  1578.       typedef details::expression_node<T>* expression_ptr;
  1579.  
  1580.       struct expression_holder
  1581.       {
  1582.          expression_holder()
  1583.          : ref_count(0),
  1584.            expr(0)
  1585.          {}
  1586.  
  1587.          expression_holder(expression_ptr e)
  1588.          : ref_count(1),
  1589.            expr(e)
  1590.          {}
  1591.  
  1592.         ~expression_holder()
  1593.          {
  1594.             delete expr;
  1595.          }
  1596.  
  1597.          std::size_t ref_count;
  1598.          expression_ptr expr;
  1599.       };
  1600.  
  1601.    public:
  1602.  
  1603.       expression()
  1604.       : expression_deletable_(true),
  1605.         expression_holder_(0),
  1606.         symbol_table_(0)
  1607.       {}
  1608.  
  1609.       expression(const expression& e)
  1610.       {
  1611.          expression_holder_ = e.expression_holder_;
  1612.          expression_holder_->ref_count++;
  1613.          expression_deletable_ = e.expression_deletable_;
  1614.          symbol_table_ = e.symbol_table_;
  1615.       }
  1616.  
  1617.       expression& operator=(const expression& e)
  1618.       {
  1619.          if (expression_holder_)
  1620.          {
  1621.             if (0 == --expression_holder_->ref_count)
  1622.             {
  1623.                delete expression_holder_;
  1624.             }
  1625.             expression_holder_ = 0;
  1626.          }
  1627.          expression_holder_ = e.expression_holder_;
  1628.          expression_holder_->ref_count++;
  1629.          expression_deletable_ = e.expression_deletable_;
  1630.          symbol_table_ = e.symbol_table_;
  1631.          return *this;
  1632.       }
  1633.  
  1634.       inline bool operator!()
  1635.       {
  1636.          return ((0 == expression_holder_) || (0 == expression_holder_->expr));
  1637.       }
  1638.  
  1639.      ~expression()
  1640.       {
  1641.          if (expression_deletable_)
  1642.          {
  1643.             if (expression_holder_)
  1644.             {
  1645.                if (0 == --expression_holder_->ref_count)
  1646.                {
  1647.                   delete expression_holder_;
  1648.                }
  1649.             }
  1650.          }
  1651.       }
  1652.  
  1653.       inline T operator()()
  1654.       {
  1655.          return value();
  1656.       }
  1657.  
  1658.       inline T value()
  1659.       {
  1660.          if (expression_holder_->expr)
  1661.             return expression_holder_->expr->value();
  1662.          else
  1663.             return std::numeric_limits<T>::quiet_NaN();
  1664.       }
  1665.  
  1666.       inline void register_symbol_table(symbol_table<T>& st)
  1667.       {
  1668.          symbol_table_ = &st;
  1669.       }
  1670.  
  1671.       inline symbol_table<T>* get_symbol_table()
  1672.       {
  1673.          return symbol_table_;
  1674.       }
  1675.  
  1676.    private:
  1677.  
  1678.       inline void set_expression(const expression_ptr expr)
  1679.       {
  1680.          if (expr)
  1681.          {
  1682.             if (expression_holder_)
  1683.             {
  1684.                if (0 == --expression_holder_->ref_count)
  1685.                {
  1686.                   delete expression_holder_;
  1687.                }
  1688.             }
  1689.             expression_holder_ = new expression_holder(expr);
  1690.             expression_deletable_ = (details::expression_node<T>::e_variable != expression_holder_->expr->type());
  1691.          }
  1692.       }
  1693.  
  1694.       bool expression_deletable_;
  1695.       expression_holder* expression_holder_;
  1696.       symbol_table<T>* symbol_table_;
  1697.  
  1698.       friend class parser<T>;
  1699.    };
  1700.  
  1701.    template <typename T>
  1702.    class parser
  1703.    {
  1704.    private:
  1705.  
  1706.       enum precedence_level
  1707.       {
  1708.          e_level00,
  1709.          e_level01,
  1710.          e_level02,
  1711.          e_level03,
  1712.          e_level04,
  1713.          e_level05,
  1714.          e_level06,
  1715.          e_level07,
  1716.          e_level08,
  1717.          e_level09,
  1718.          e_level10,
  1719.          e_level11,
  1720.          e_level12
  1721.       };
  1722.  
  1723.       typedef details::expression_node <T>  expression_node_t;
  1724.       typedef details::literal_node    <T>     literal_node_t;
  1725.       typedef details::unary_node      <T>       unary_node_t;
  1726.       typedef details::binary_node     <T>      binary_node_t;
  1727.       typedef details::trinary_node    <T>     trinary_node_t;
  1728.       typedef details::quaternary_node <T>  quaternary_node_t;
  1729.       typedef details::quinary_node    <T>     quinary_node_t;
  1730.       typedef details::senary_node    <T>       senary_node_t;
  1731.       typedef details::conditional_node<T> conditional_node_t;
  1732.       typedef details::variable_node   <T>    variable_node_t;
  1733.       typedef details::sf3_node        <T>         sf3_node_t;
  1734.       typedef details::sf4_node        <T>         sf4_node_t;
  1735.       typedef details::token           <T>            token_t;
  1736.       typedef expression_node_t*          expression_node_ptr;
  1737.  
  1738.    public:
  1739.  
  1740.       parser()
  1741.       : symbol_table_(0)
  1742.       {}
  1743.  
  1744.       inline bool compile(const std::string& expression_string, expression<T>& expr)
  1745.       {
  1746.          if (!validate_expression(expression_string))
  1747.          {
  1748.             return false;
  1749.          }
  1750.          set_error("");
  1751.          expression_generator_.set_allocator(node_allocator_);
  1752.          if (!lexer_.process(expression_string))
  1753.          {
  1754.             set_error(lexer_.error());
  1755.             return false;
  1756.          }
  1757.          symbol_table_ = expr.get_symbol_table();
  1758.          next_token();
  1759.          expression_node_ptr e = parse_expression();
  1760.          if ((0 != e) && (current_token_.type == token_t::eof))
  1761.          {
  1762.             expr.set_expression(e);
  1763.             return !(!expr);
  1764.          }
  1765.          else
  1766.          {
  1767.             set_error("parser::compile() - Incomplete expression!");
  1768.             if (0 != e) delete e;
  1769.             return false;
  1770.          }
  1771.       }
  1772.  
  1773.       inline std::string error() const
  1774.       {
  1775.          return error_description_;
  1776.       }
  1777.  
  1778.    private:
  1779.  
  1780.       inline void store_token()
  1781.       {
  1782.          lexer_.store();
  1783.          store_current_token_ = current_token_;
  1784.       }
  1785.  
  1786.       inline void restore_token()
  1787.       {
  1788.          lexer_.restore();
  1789.          current_token_ = store_current_token_;
  1790.       }
  1791.  
  1792.       inline void next_token()
  1793.       {
  1794.          current_token_ = lexer_.next_token();
  1795.       }
  1796.  
  1797.       static const precedence_level default_precedence = e_level00;
  1798.  
  1799.       struct state_t
  1800.       {
  1801.          inline void set(const precedence_level& l,
  1802.                          const precedence_level& r,
  1803.                          const details::operator_type& o)
  1804.          {
  1805.             left  = l;
  1806.             right = r;
  1807.             operation = o;
  1808.          }
  1809.  
  1810.          inline void reset()
  1811.          {
  1812.             left  = e_level00;
  1813.             right = e_level00;
  1814.          }
  1815.  
  1816.          precedence_level left;
  1817.          precedence_level right;
  1818.          details::operator_type operation;
  1819.       };
  1820.  
  1821.       inline expression_node_ptr parse_expression(precedence_level precedence = e_level00)
  1822.       {
  1823.          expression_node_ptr expr = parse_branch();
  1824.  
  1825.          if (0 == expr)
  1826.          {
  1827.             return expr;
  1828.          }
  1829.  
  1830.          bool break_loop = false;
  1831.  
  1832.          state_t current_state;
  1833.  
  1834.          for ( ; ; )
  1835.          {
  1836.             current_state.reset();
  1837.             switch (current_token_.type)
  1838.             {
  1839.                case token_t::lt  : current_state.set(e_level05,e_level06,details:: e_lt); break;
  1840.                case token_t::lte : current_state.set(e_level05,e_level06,details::e_lte); break;
  1841.                case token_t::eq  : current_state.set(e_level05,e_level06,details:: e_eq); break;
  1842.                case token_t::ne  : current_state.set(e_level05,e_level06,details:: e_ne); break;
  1843.                case token_t::gte : current_state.set(e_level05,e_level06,details::e_gte); break;
  1844.                case token_t::gt  : current_state.set(e_level05,e_level06,details:: e_gt); break;
  1845.                case token_t::add : current_state.set(e_level07,e_level08,details::e_add); break;
  1846.                case token_t::sub : current_state.set(e_level07,e_level08,details::e_sub); break;
  1847.                case token_t::div : current_state.set(e_level10,e_level11,details::e_div); break;
  1848.                case token_t::mul : current_state.set(e_level10,e_level11,details::e_mul); break;
  1849.                case token_t::mod : current_state.set(e_level10,e_level11,details::e_mod); break;
  1850.                case token_t::pow : current_state.set(e_level12,e_level12,details::e_pow); break;
  1851.                default           : if (current_token_.type == token_t::symbol)
  1852.                                    {
  1853.                                       static const std::string s_and  =  "and";
  1854.                                       static const std::string s_nand = "nand";
  1855.                                       static const std::string s_or   =   "or";
  1856.                                       static const std::string s_nor  =  "nor";
  1857.                                       static const std::string s_xor  =  "xor";
  1858.                                       if (imatch(current_token_.value,s_and))
  1859.                                       {
  1860.                                          current_state.set(e_level01,e_level02,details::e_and);
  1861.                                          break;
  1862.                                       }
  1863.                                       else if (imatch(current_token_.value,s_nand))
  1864.                                       {
  1865.                                          current_state.set(e_level01,e_level02,details::e_nand);
  1866.                                          break;
  1867.                                       }
  1868.                                       else if (imatch(current_token_.value,s_or))
  1869.                                       {
  1870.                                          current_state.set(e_level03,e_level04,details::e_or);
  1871.                                          break;
  1872.                                       }
  1873.                                       else if (imatch(current_token_.value,s_nor))
  1874.                                       {
  1875.                                          current_state.set(e_level03,e_level04,details::e_nor);
  1876.                                          break;
  1877.                                       }
  1878.                                       else if (imatch(current_token_.value,s_xor))
  1879.                                       {
  1880.                                          current_state.set(e_level03,e_level04,details::e_xor);
  1881.                                          break;
  1882.                                       }
  1883.                                    }
  1884.                                    break_loop = true;
  1885.             }
  1886.             if (break_loop)
  1887.                break;
  1888.             else if (current_state.left < precedence)
  1889.                break;
  1890.             next_token();
  1891.             expr = expression_generator_(current_state.operation,expr,parse_expression(current_state.right));
  1892.          }
  1893.          return expr;
  1894.       }
  1895.  
  1896.       template<typename Type, std::size_t N>
  1897.       struct scoped_delete
  1898.       {
  1899.          typedef Type* ptr_t;
  1900.  
  1901.          scoped_delete(parser<T>& pr, ptr_t& p)
  1902.          : delete_ptr(true),
  1903.            parser_(pr),
  1904.            p_(&p)
  1905.          {}
  1906.  
  1907.          scoped_delete(parser<T>& pr, ptr_t p[N])
  1908.          : delete_ptr(true),
  1909.            parser_(pr),
  1910.            p_(p)
  1911.          {}
  1912.  
  1913.         ~scoped_delete()
  1914.          {
  1915.             if (delete_ptr)
  1916.             {
  1917.                for (std::size_t i = 0; i < N; ++i)
  1918.                {
  1919.                   if (p_[i]) parser_.node_allocator_.free(p_[i]);
  1920.                }
  1921.             }
  1922.          }
  1923.          bool delete_ptr;
  1924.          parser<T>& parser_;
  1925.          ptr_t* p_;
  1926.       };
  1927.  
  1928.       template<std::size_t NumberofParameters>
  1929.       inline expression_node_ptr parse_function_call(const details::operator_type& opt_type)
  1930.       {
  1931.          expression_node_ptr branch[NumberofParameters];
  1932.          expression_node_ptr result  = 0;
  1933.          std::fill_n(branch,NumberofParameters,reinterpret_cast<expression_node_ptr>(0));
  1934.          scoped_delete<expression_node_t,NumberofParameters> sd(*this,branch);
  1935.          next_token();
  1936.          if (!token_is(token_t::lbracket))
  1937.          {
  1938.             return reinterpret_cast<expression_node_ptr>(0);
  1939.          }
  1940.          for (int i = 0; i < static_cast<int>(NumberofParameters); ++i)
  1941.          {
  1942.             branch[i] = parse_expression();
  1943.             if (i < static_cast<int>(NumberofParameters - 1))
  1944.             {
  1945.                if (!token_is(token_t::comma))
  1946.                {
  1947.                   return reinterpret_cast<expression_node_ptr>(0);
  1948.                }
  1949.             }
  1950.          }
  1951.          if (!token_is(token_t::rbracket))
  1952.             return reinterpret_cast<expression_node_ptr>(0);
  1953.          else
  1954.             result = expression_generator_(opt_type,branch);
  1955.          sd.delete_ptr = false;
  1956.          return result;
  1957.       }
  1958.  
  1959.       inline expression_node_ptr parse_conditional_statement()
  1960.       {
  1961.          expression_node_ptr condition   = 0;
  1962.          expression_node_ptr consequent  = 0;
  1963.          expression_node_ptr alternative = 0;
  1964.          next_token();
  1965.          if (token_is(token_t::lbracket))
  1966.             condition = parse_expression();
  1967.          else
  1968.             return reinterpret_cast<expression_node_ptr>(0);
  1969.          if (token_is(token_t::comma))
  1970.             consequent = parse_expression();
  1971.          else
  1972.             return reinterpret_cast<expression_node_ptr>(0);
  1973.          if (token_is(token_t::comma))
  1974.             alternative = parse_expression();
  1975.          else
  1976.             return reinterpret_cast<expression_node_ptr>(0);
  1977.          if (token_is(token_t::rbracket))
  1978.             return expression_generator_.conditional(condition,consequent,alternative);
  1979.          else
  1980.             return reinterpret_cast<expression_node_ptr>(0);
  1981.       }
  1982.  
  1983.       inline expression_node_ptr parse_special_function(const unsigned int id)
  1984.       {
  1985.          //Expect: $fDD(expr0,expr1,expr2) or $fDD(expr0,expr1,expr2,expr3)
  1986.          const details::operator_type opt_type = details::operator_type(id + 1000);
  1987.          const std::size_t NumberOfParameters = (id < (details::e_sf18 - 1000)) ? 3 : 4;
  1988.          expression_node_ptr branch3[3];
  1989.          expression_node_ptr branch4[4];
  1990.          expression_node_ptr* branch = (id < (details::e_sf18 - 1000)) ? &branch3[0] : &branch4[0];
  1991.          expression_node_ptr result  = 0;
  1992.          std::fill_n(branch3,3,reinterpret_cast<expression_node_ptr>(0));
  1993.          std::fill_n(branch4,4,reinterpret_cast<expression_node_ptr>(0));
  1994.          scoped_delete<expression_node_t,3> sd3(*this,branch3);
  1995.          scoped_delete<expression_node_t,4> sd4(*this,branch4);
  1996.          next_token();
  1997.          if (!token_is(token_t::lbracket))
  1998.          {
  1999.             return reinterpret_cast<expression_node_ptr>(0);
  2000.          }
  2001.          for (std::size_t i = 0; i < NumberOfParameters; ++i)
  2002.          {
  2003.             branch[i] = parse_expression();
  2004.             if (i < (NumberOfParameters - 1))
  2005.             {
  2006.                if (!token_is(token_t::comma))
  2007.                {
  2008.                   return reinterpret_cast<expression_node_ptr>(0);
  2009.                }
  2010.             }
  2011.          }
  2012.          if (!token_is(token_t::rbracket))
  2013.             return reinterpret_cast<expression_node_ptr>(0);
  2014.          else
  2015.          {
  2016.             switch (NumberOfParameters)
  2017.             {
  2018.                case 3  : result = expression_generator_.special_function(opt_type,branch3); break;
  2019.                case 4  : result = expression_generator_.special_function(opt_type,branch4); break;
  2020.                default : return reinterpret_cast<expression_node_ptr>(0);
  2021.             }
  2022.          }
  2023.  
  2024.          sd3.delete_ptr = false;
  2025.          sd4.delete_ptr = false;
  2026.          return result;
  2027.       }
  2028.  
  2029.       inline expression_node_ptr parse_symbol()
  2030.       {
  2031.          std::pair<bool,std::string> match_found_error(false,"");
  2032.          store_token();
  2033.          for (std::size_t i = 0; i < details::operation_list_size; ++i)
  2034.          {
  2035.             if (imatch(details::operation_list[i].name,current_token_.value))
  2036.             {
  2037.                std::string token_value = current_token_.value;
  2038.                expression_node_ptr branch = reinterpret_cast<expression_node_ptr>(0);
  2039.                switch(details::operation_list[i].num_params)
  2040.                {
  2041.                   case 1 : branch = parse_function_call<1>(details::operation_list[i].type); break;
  2042.                   case 2 : branch = parse_function_call<2>(details::operation_list[i].type); break;
  2043.                   case 3 : branch = parse_function_call<3>(details::operation_list[i].type); break;
  2044.                   case 4 : branch = parse_function_call<4>(details::operation_list[i].type); break;
  2045.                   case 5 : branch = parse_function_call<5>(details::operation_list[i].type); break;
  2046.                   case 6 : branch = parse_function_call<6>(details::operation_list[i].type); break;
  2047.                }
  2048.                if (branch)
  2049.                {
  2050.                   return branch;
  2051.                }
  2052.                else if (!match_found_error.first)
  2053.                {
  2054.                   match_found_error.first = true;
  2055.                   match_found_error.second = token_value;
  2056.                   set_error("");
  2057.                }
  2058.                restore_token();
  2059.             }
  2060.          }
  2061.  
  2062.          if (match_found_error.first)
  2063.          {
  2064.             set_error("parser::parse_branch() - invalid argument count for function: " + match_found_error.second);
  2065.             return reinterpret_cast<expression_node_ptr>(0);
  2066.          }
  2067.  
  2068.          static const std::string s_if = "if";
  2069.          if (imatch(current_token_.value,s_if))
  2070.          {
  2071.             return parse_conditional_statement();
  2072.          }
  2073.          else if ((current_token_.value.size() == 4) && '$' == current_token_.value[0] && 'f' == current_token_.value[1])
  2074.          {
  2075.             unsigned int id = (current_token_.value[2] - '0') * 10 +  (current_token_.value[3] - '0');
  2076.             return parse_special_function(id);
  2077.          }
  2078.          else if (symbol_table_)
  2079.          {
  2080.             expression_node_ptr var = symbol_table_->get_variable(current_token_.value);
  2081.             if (0 == var)
  2082.             {
  2083.                set_error("parser::parse_branch() - unknown variable: " + current_token_.value);
  2084.                return expression_node_ptr(0);
  2085.             }
  2086.  
  2087.             if (symbol_table_->is_constant(current_token_.value))
  2088.             {
  2089.                var = expression_generator_(var->value());
  2090.             }
  2091.  
  2092.             next_token();
  2093.             return var;
  2094.          }
  2095.          else
  2096.          {
  2097.             set_error("parser::parse_branch() - invalid symbol-table and variable found");
  2098.             return expression_node_ptr(0);
  2099.          }
  2100.       }
  2101.  
  2102.       inline expression_node_ptr parse_branch()
  2103.       {
  2104.          switch (current_token_.type)
  2105.          {
  2106.             case token_t::number :
  2107.                                  {
  2108.                                     expression_node_ptr literal_exp = expression_generator_(current_token_.numeric_value);
  2109.                                     next_token();
  2110.                                     return literal_exp;
  2111.                                  }
  2112.  
  2113.             case token_t::symbol : return parse_symbol();
  2114.  
  2115.             case '(' :
  2116.                                  {
  2117.                                     next_token();
  2118.                                     expression_node_ptr branch = parse_expression();
  2119.                                     if (token_is(token_t::rbracket))
  2120.                                        return branch;
  2121.                                     else
  2122.                                        return reinterpret_cast<expression_node_ptr>(0);
  2123.                                  }
  2124.             case '[' :
  2125.                                  {
  2126.                                     next_token();
  2127.                                     expression_node_ptr branch = parse_expression();
  2128.                                     if (token_is(token_t::rsqrbracket))
  2129.                                        return branch;
  2130.                                     else
  2131.                                        return reinterpret_cast<expression_node_ptr>(0);
  2132.                                  }
  2133.             case '{' :
  2134.                                  {
  2135.                                     next_token();
  2136.                                     expression_node_ptr branch = parse_expression();
  2137.                                     if (token_is(token_t::rcrlbracket))
  2138.                                        return branch;
  2139.                                     else
  2140.                                        return reinterpret_cast<expression_node_ptr>(0);
  2141.                                  }
  2142.             case '-' :
  2143.                                  {
  2144.                                     next_token();
  2145.                                     return expression_generator_(details::e_neg,parse_expression(e_level09));
  2146.                                  }
  2147.             case '+' :
  2148.                                  {
  2149.                                     next_token();
  2150.                                     return expression_generator_(details::e_pos,parse_expression(e_level09));
  2151.                                  }
  2152.             case token_t::eof :
  2153.                                  {
  2154.                                     set_error("parser::parse_branch() - expected a valid branch [1]");
  2155.                                     return reinterpret_cast<expression_node_ptr>(0);
  2156.                                  }
  2157.             default :
  2158.                                  {
  2159.                                     set_error("parser::parse_branch() - expected a valid branch [2]");
  2160.                                     return reinterpret_cast<expression_node_ptr>(0);
  2161.                                  }
  2162.          }
  2163.       }
  2164.  
  2165.       inline bool token_is(const typename token_t::token_type& ttype)
  2166.       {
  2167.          if (current_token_.type != ttype)
  2168.          {
  2169.             if (!((current_token_.type == ']') && (token_t::rbracket == ttype)))
  2170.             {
  2171.                set_error(std::string("parser::token_is() - expected: ") + static_cast<char>(ttype));
  2172.                return false;
  2173.             }
  2174.          }
  2175.  
  2176.          next_token();
  2177.          return true;
  2178.       }
  2179.  
  2180.       template<typename Type>
  2181.       class expression_generator
  2182.       {
  2183.       public:
  2184.  
  2185.          typedef details::expression_node<Type>* expression_node_ptr;
  2186.  
  2187.          inline void set_allocator(details::node_allocator& na)
  2188.          {
  2189.             node_allocator_ = &na;
  2190.          }
  2191.  
  2192.          inline expression_node_ptr operator()(const Type& v) const
  2193.          {
  2194.             return node_allocator_->allocate<literal_node_t>(v);
  2195.          }
  2196.  
  2197.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr (&branch)[1])
  2198.          {
  2199.             return synthesize_expression<unary_node_t,1>(operation,branch);
  2200.          }
  2201.  
  2202.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr (&branch)[2])
  2203.          {
  2204.             return synthesize_expression<binary_node_t,2>(operation,branch);
  2205.          }
  2206.  
  2207.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr (&branch)[3])
  2208.          {
  2209.             return synthesize_expression<trinary_node_t,3>(operation,branch);
  2210.          }
  2211.  
  2212.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr (&branch)[4])
  2213.          {
  2214.             return synthesize_expression<quaternary_node_t,4>(operation,branch);
  2215.          }
  2216.  
  2217.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr (&branch)[5])
  2218.          {
  2219.             return synthesize_expression<quinary_node_t,5>(operation,branch);
  2220.          }
  2221.  
  2222.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr (&branch)[6])
  2223.          {
  2224.             return synthesize_expression<senary_node_t,6>(operation,branch);
  2225.          }
  2226.  
  2227.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr b0)
  2228.          {
  2229.             expression_node_ptr branch[1] = { b0 };
  2230.             return synthesize_expression<unary_node_t,1>(operation,branch);
  2231.          }
  2232.  
  2233.          inline expression_node_ptr operator()(const details::operator_type& operation, expression_node_ptr b0, expression_node_ptr b1)
  2234.          {
  2235.             expression_node_ptr branch[2] = { b0, b1 };
  2236.             return synthesize_expression<binary_node_t,2>(operation,branch);
  2237.          }
  2238.  
  2239.          inline expression_node_ptr conditional(expression_node_ptr condition,
  2240.                                                 expression_node_ptr consequent,
  2241.                                                 expression_node_ptr alternative) const
  2242.          {
  2243.             //Can the condition be immediately evaluated, hence optimised out?
  2244.             if (expression_node_t::e_constant == condition->type())
  2245.             {
  2246.                if (condition->value() != Type(0))
  2247.                {
  2248.                   node_allocator_->free(condition);
  2249.                   node_allocator_->free(alternative);
  2250.                   return consequent;
  2251.                }
  2252.                else
  2253.                {
  2254.                   node_allocator_->free(condition);
  2255.                   node_allocator_->free(consequent);
  2256.                   return alternative;
  2257.                }
  2258.             }
  2259.             else
  2260.                return node_allocator_->allocate<conditional_node_t>(condition,consequent,alternative);
  2261.          }
  2262.  
  2263.          inline expression_node_ptr special_function(const details::operator_type& operation, expression_node_ptr (&branch)[3])
  2264.          {
  2265.             return synthesize_expression<sf3_node_t,3>(operation,branch);
  2266.          }
  2267.  
  2268.          inline expression_node_ptr special_function(const details::operator_type& operation, expression_node_ptr (&branch)[4])
  2269.          {
  2270.             return synthesize_expression<sf4_node_t,4>(operation,branch);
  2271.          }
  2272.  
  2273.  
  2274.       private:
  2275.  
  2276.          template<typename NodePtr>
  2277.          inline bool is_contant_node(NodePtr n) const
  2278.          {
  2279.             return (expression_node_t::e_constant != n->type());
  2280.          }
  2281.  
  2282.          template<std::size_t N, typename NodePtr>
  2283.          inline bool is_constant_foldable(NodePtr (&b)[N]) const
  2284.          {
  2285.             for (std::size_t i = 0; i < N; ++i)
  2286.             {
  2287.                if (b[i] && !is_contant_node<NodePtr>(b[i])) return false;
  2288.             }
  2289.             return true;
  2290.          }
  2291.  
  2292.          template<std::size_t N>
  2293.          inline bool all_nodes_valid(expression_node_ptr (&b)[N]) const
  2294.          {
  2295.             for (std::size_t i = 0; i < N; ++i)
  2296.             {
  2297.                if (0 == b[i]) return false;
  2298.             }
  2299.             return true;
  2300.          }
  2301.  
  2302.          template<typename NodeType, std::size_t N>
  2303.          inline expression_node_ptr synthesize_expression(const details::operator_type& operation, expression_node_ptr (&branch)[N])
  2304.          {
  2305.             if ((details::e_default != operation) && all_nodes_valid<N>(branch))
  2306.             {
  2307.                //Attempt simple constant folding optimisation.
  2308.                expression_node_ptr expression_point = node_allocator_->allocate<NodeType>(operation,branch);
  2309.                if (is_constant_foldable<N>(branch))
  2310.                {
  2311.                   Type v = expression_point->value();
  2312.                   node_allocator_->free(expression_point);
  2313.                   return node_allocator_->allocate<literal_node_t>(v);
  2314.                }
  2315.                else
  2316.                   return expression_point;
  2317.             }
  2318.             else
  2319.                return reinterpret_cast<expression_node_ptr>(0);
  2320.          }
  2321.  
  2322.          details::node_allocator* node_allocator_;
  2323.       };
  2324.  
  2325.       inline bool imatch(const std::string& s1, const std::string& s2) const
  2326.       {
  2327.          if (s1.size() == s2.size())
  2328.          {
  2329.             for (std::size_t i = 0; i < s1.size(); ++i)
  2330.             {
  2331.                if (std::tolower(s1[i]) != std::tolower(s2[i]))
  2332.                {
  2333.                   return false;
  2334.                }
  2335.             }
  2336.             return true;
  2337.          }
  2338.          else
  2339.             return false;
  2340.       }
  2341.  
  2342.       inline bool check0(const char c0, const char c1,
  2343.                          const char v0, const char v1,
  2344.                          const char v2)
  2345.       {
  2346.          return ((c0 == v0) && ((c1 == v1) || (c1 == v2)));
  2347.       }
  2348.  
  2349.       inline bool check1(const char c0, const char c1,
  2350.                          const char v0, const char v1)
  2351.       {
  2352.          return ((c0 == v0) && (c1 == v1));
  2353.       }
  2354.  
  2355.       inline bool validate_expression(const std::string& expression_string)
  2356.       {
  2357.          if (expression_string.empty())
  2358.          {
  2359.             set_error("parser::validate_expression() - empty expression");
  2360.             return false;
  2361.          }
  2362.  
  2363.          std::stack<char> bracket_stack;
  2364.  
  2365.          for (std::size_t i = 0; i < (expression_string.size() - 1); ++i)
  2366.          {
  2367.             char c0 = expression_string[i];
  2368.             char c1 = expression_string[i + 1];
  2369.             if (details::is_invalid(c0))
  2370.             {
  2371.                set_error(std::string("parser::validate_expression() - invalid character: ") + c0);
  2372.                return false;
  2373.             }
  2374.             else if (
  2375.                      check0(c0,c1,'*','*','/') ||
  2376.                      check0(c0,c1,'*','%','^') ||
  2377.                      check0(c0,c1,'/','*','/') ||
  2378.                      check0(c0,c1,'/','%','^') ||
  2379.                      check0(c0,c1,'+','*','/') ||
  2380.                      check0(c0,c1,'+','%','^') ||
  2381.                      check0(c0,c1,'-','*','/') ||
  2382.                      check0(c0,c1,'-','%','^') ||
  2383.                      check0(c0,c1,'^','*','/') ||
  2384.                      check0(c0,c1,'^','^','%') ||
  2385.                      check0(c0,c1,'%','*','/') ||
  2386.                      check0(c0,c1,'%','^','%') ||
  2387.                      check0(c0,c1,'.','%','^') ||
  2388.                      check0(c0,c1,'.','*','/') ||
  2389.                      check0(c0,c1,',','%','^') ||
  2390.                      check0(c0,c1,',','*','/') ||
  2391.                      check0(c0,c1,'(','*','/') ||
  2392.                      check0(c0,c1,'(','%','^') ||
  2393.                      check0(c0,c1,'[','*','/') ||
  2394.                      check0(c0,c1,'[','%','^') ||
  2395.                      check0(c0,c1,'{','*','/') ||
  2396.                      check0(c0,c1,'{','%','^') ||
  2397.                      check0(c0,c1,'+',')',']') ||
  2398.                      check0(c0,c1,'-',')',']') ||
  2399.                      check0(c0,c1,'*',')',']') ||
  2400.                      check0(c0,c1,'/',')',']') ||
  2401.                      check0(c0,c1,'^',')',']') ||
  2402.                      check0(c0,c1,'%',')',']') ||
  2403.                      check1(c0,c1,'+','}'    ) ||
  2404.                      check1(c0,c1,'-','}'    ) ||
  2405.                      check1(c0,c1,'*','}'    ) ||
  2406.                      check1(c0,c1,'/','}'    ) ||
  2407.                      check1(c0,c1,'^','}'    ) ||
  2408.                      check1(c0,c1,'%','}'    ) ||
  2409.                      check1(c0,c1,'.','.'    ) ||
  2410.                      check1(c0,c1,'.','+'    ) ||
  2411.                      check1(c0,c1,'.','-'    ) ||
  2412.                      check1(c0,c1,'.','*'    ) ||
  2413.                      check1(c0,c1,'.','/'    ) ||
  2414.                      check1(c0,c1,',',','    )
  2415.                     )
  2416.             {
  2417.                set_error(std::string("parser::validate_expression() - invalid character combination: ") + expression_string.substr(i,2));
  2418.                return false;
  2419.             }
  2420.             else if (c0 == '(')
  2421.                bracket_stack.push(')');
  2422.             else if (c0 == '[')
  2423.                bracket_stack.push(']');
  2424.             else if (c0 == '{')
  2425.                bracket_stack.push('}');
  2426.             else if (details::is_right_bracket(c0))
  2427.             {
  2428.                if (bracket_stack.empty())
  2429.                {
  2430.                   set_error(std::string("parser::validate_expression() - invalid/mismatched bracket(s)[0]: ") + expression_string.substr(0,i));
  2431.                   return false;
  2432.                }
  2433.                else if (c0 != bracket_stack.top())
  2434.                {
  2435.                   set_error(std::string("parser::validate_expression() - invalid/mismatched bracket(s)[1]: ") + expression_string.substr(0,i));
  2436.                   return false;
  2437.                }
  2438.                else
  2439.                   bracket_stack.pop();
  2440.             }
  2441.          }
  2442.  
  2443.          if (!bracket_stack.empty())
  2444.          {
  2445.             if (1 == bracket_stack.size())
  2446.             {
  2447.                char c0 = expression_string[expression_string.size() - 1];
  2448.                if (details::is_right_bracket(c0))
  2449.                {
  2450.                   if (c0 == bracket_stack.top())
  2451.                      return true;
  2452.                   else
  2453.                   {
  2454.                      set_error(std::string("parser::validate_expression() - invalid/mismatched bracket(s)[2]: ") + expression_string);
  2455.                      return false;
  2456.                   }
  2457.                }
  2458.             }
  2459.             set_error(std::string("parser::validate_expression() - invalid/mismatched bracket(s)[3]: ") + expression_string);
  2460.             return false;
  2461.          }
  2462.          return true;
  2463.       }
  2464.  
  2465.       inline void set_error(const std::string& err_str)
  2466.       {
  2467.          //would it be better if this were a stack?
  2468.          if (error_description_.empty())
  2469.          {
  2470.             error_description_ = err_str;
  2471.          }
  2472.       }
  2473.  
  2474.    private:
  2475.  
  2476.       details::lexer<T> lexer_;
  2477.       details::token<T> current_token_;
  2478.       details::token<T> store_current_token_;
  2479.       details::node_allocator node_allocator_;
  2480.       expression_generator<T> expression_generator_;
  2481.       symbol_table<T>* symbol_table_;
  2482.       std::string error_description_;
  2483.    };
  2484.  
  2485.    template<typename T>
  2486.    inline T integrate(expression<T>& e,
  2487.                       T& x,
  2488.                       const T& r0, const T& r1,
  2489.                       const std::size_t number_of_intervals = 1000000)
  2490.    {
  2491.       if (r0 > r1) return T(0);
  2492.       T h = (r1 - r0) / (T(2.0) * number_of_intervals);
  2493.       T total_area = T(0);
  2494.       for (std::size_t i = 0; i < number_of_intervals; ++i)
  2495.       {
  2496.          x = r0 + T(2.0) * i * h;
  2497.          T y0 = e.value(); x += h;
  2498.          T y1 = e.value(); x += h;
  2499.          T y2 = e.value(); x += h;
  2500.          total_area += h * (y0 + T(4.0) * y1 + y2) / T(3.0);
  2501.       }
  2502.       return total_area;
  2503.    }
  2504.  
  2505.    template<typename T>
  2506.    inline T integrate(expression<T>& e,
  2507.                       const std::string& variable_name,
  2508.                       const T& r0, const T& r1,
  2509.                       const std::size_t number_of_intervals = 1000000)
  2510.    {
  2511.       details::variable_node<T>* var = e.get_symbol_table()->get_variable(variable_name);
  2512.       if (var)
  2513.       {
  2514.          T& x = var->ref();
  2515.          return integrate(e,x,r0,r1,number_of_intervals);
  2516.       }
  2517.       else
  2518.          return std::numeric_limits<T>::quiet_NaN();
  2519.    }
  2520.  
  2521.    template<typename T>
  2522.    inline T derivative(expression<T>& e,
  2523.                        T& x,
  2524.                        const double& h = 0.00001)
  2525.    {
  2526.       T x_init = x;
  2527.       x = x_init + T(2.0) * h;
  2528.       T y0 = e.value();
  2529.       x = x_init + h;
  2530.       T y1 = e.value();
  2531.       x = x_init - h;
  2532.       T y2 = e.value();
  2533.       x = x_init - T(2.0) * h;
  2534.       T y3 = e.value();
  2535.       x = x_init;
  2536.       return (-y0 + T(8.0) * (y1 - y2) + y3) / (T(12.0) * h);
  2537.    }
  2538.  
  2539.    template<typename T>
  2540.    inline T derivative(expression<T>& e,
  2541.                        const std::string& variable_name,
  2542.                        const double& h = 0.00001)
  2543.    {
  2544.       details::variable_node<T>* var = e.get_symbol_table()->get_variable(variable_name);
  2545.       if (var)
  2546.       {
  2547.          T& x = var->ref();
  2548.          return derivative(e,x,h);
  2549.       }
  2550.       else
  2551.          return std::numeric_limits<T>::quiet_NaN();
  2552.    }
  2553.  
  2554.    namespace information
  2555.    {
  2556.       static const char* library = "Mathematical Expression Toolkit";
  2557.       static const char* version = "2.718281828";
  2558.       static const char* date    = "20111111";
  2559.  
  2560.       static inline std::string data()
  2561.       {
  2562.          static const std::string info_str = std::string(library) +
  2563.                                              std::string(" v") + std::string(version) +
  2564.                                              std::string(" (") + date + std::string(")");
  2565.          return info_str;
  2566.       }
  2567.  
  2568.    } // namespace information
  2569.  
  2570. } // namespace exprtk
  2571.  
  2572. #endif

Submit a correction or amendment below (click here to make a fresh posting)
After submitting an amendment, you'll be able to view the differences between the old and new posts easily.

Syntax highlighting:

To highlight particular lines, prefix each line with {%HIGHLIGHT}




All content is user-submitted.
The administrators of this site (kpaste.net) are not responsible for their content.
Abuse reports should be emailed to us at