---

expression.h

Go to the documentation of this file.

// Expression implementation -*- C++ -*-

// Copyright (C) 2001-2003 Hermann Schichl
//
// This file is part of the COCONUT API.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#ifndef _EXPRESSION_H_
#define _EXPRESSION_H_

#include <stdarg.h>
#include <stdio.h>
#include <dag.h>
#include <visitor.h>
#include <interval.h>
#include <coconut_config.h>
#include <semantics.h>
#include <evaluator.h>          // not yet designed
#include <g_algo.h>
#include <fstream>
#include <cerrno>
#include <string>
#include <utility>
#include <values.h>
#include <linalg.h>

using namespace vgtl;

// another very well possible approach would be to use
// a base expression class and derived classes for every
// expression type known. I have, however, no idea which
// method performs better. I would never remove the expression
// type flag, though.

// don't renumber these w/o thinking
#define EXPRINFO_GHOST          0       // number is overlayed params.b
                                        // contains info on edge deletion
#define EXPRINFO_CONSTANT       -1      // contained in params.d or .nd 
#define EXPRINFO_VARIABLE       -2      // index contained in params.nn

// renumbering these should be safe

// these have an arbitrary number of arguments
#define EXPRINFO_SUM            -3      // params.nd contains additive const
#define EXPRINFO_MEAN           -4      // no params
#define EXPRINFO_PROD           -5      // params.nd contains multiplic. const
#define EXPRINFO_MAX            -6      // params.nd contains min value
#define EXPRINFO_MIN            -7      // params.nd contains max value
#define EXPRINFO_MONOME         -8      // params.n contains the exponents
#define EXPRINFO_SCPROD         -9      // no params
#define EXPRINFO_NORM          -10      // params.nd contains the norm-type

// these are one dimensional
#define EXPRINFO_INVERT        -11      // params.nd/x
#define EXPRINFO_SQUARE        -12      // (x+q)^2, q in params.nd
#define EXPRINFO_SQROOT        -13      // sqrt(x+c) c in params.nd
#define EXPRINFO_ABS           -14      // abs(x+c) c in params.nd
#define EXPRINFO_INTPOWER      -15      // x^n (n const. in params.nn)
#define EXPRINFO_EXP           -16      // exp(x+p) p in params.nd
#define EXPRINFO_LOG           -17      // log(x+p) p in params.nd
#define EXPRINFO_SIN           -18      // sin(x + th) th in params.nd
#define EXPRINFO_COS           -19      // cos(x + th) th in params.nd
#define EXPRINFO_GAUSS         -20      // exp(-(x-m)^2/s^2) m, s in params.d
#define EXPRINFO_POLY          -21      // a_0+a_1 x+...+a_n x^n, a in params.d

// two dimensional
#define EXPRINFO_POW           -22      // (x+p)^y, p in params.nd
#define EXPRINFO_DIV           -23      // a*x/y, a in params.nd
#define EXPRINFO_ATAN2         -24      // atan(x,y) no params

// these must have variable nodes as children
#define EXPRINFO_LIN           -25      // number of row in lin in params.nn
#define EXPRINFO_QUAD          -26      // (A|b) cont. in params.m x^T A x+b^T x
                                        // A is assumed symmetric

// the following have complex arguments and real results
#define EXPRINFO_RE            -27      // no params
#define EXPRINFO_IM            -28      // no params
#define EXPRINFO_ARG           -29      // no params

// these have complex arguments and complex results
#define EXPRINFO_CPLXCONJ      -30      // no params

// these are table driven
#define EXPRINFO_LOOKUP        -31      // table in params.m
#define EXPRINFO_PWLIN         -32      // table in params.m
#define EXPRINFO_SPLINE        -33      // table in params.m
#define EXPRINFO_PWCONSTLC     -34      // table in params.m
#define EXPRINFO_PWCONSTRC     -35      // table in params.m

// these have discrete results
#define EXPRINFO_IN            -36      // box in params.i
#define EXPRINFO_IF            -37      // truth-interval in params.ni
#define EXPRINFO_AND           -38      // truth-intervals in params.i
#define EXPRINFO_OR            -39      // truth-intervals in params.i
#define EXPRINFO_NOT           -40      // truth-interval in params.ni
#define EXPRINFO_IMPLIES       -41      // truth-intervals in params.i
#define EXPRINFO_COUNT         -42      // truth-intervals in params.i
#define EXPRINFO_ALLDIFF       -43      // max of abs(x_i-x_j) in params.nd
#define EXPRINFO_HISTOGRAM     -44      // pairs of intervals in params.i
#define EXPRINFO_LEVEL         -45      // boxes in params.mi (multi-in)

// these have discrete arguments and discrete results
#define EXPRINFO_NEIGHBOR      -46      // list of pairs in double long params.n
#define EXPRINFO_NOGOOD        -47      // vector x_0 in params.n

// the following involve integration
#define EXPRINFO_EXPECTATION   -48      // no params
#define EXPRINFO_INTEGRAL      -49      // integration area in params.i

// the following highly complex operations implicitly build matrices
// all use params.nm to hold the parameters. Special is params.nm[0],
// because it contains the noted info. If the matrix is sparse, the remaining
// rows contain column index information
#define EXPRINFO_DET           -50      // [0]=0(sparse),1(dense), [1]=dim
#define EXPRINFO_COND          -51      // [0]=0(sparse),1(dense), [1],[2]=dim
#define EXPRINFO_PSD           -52      // [0]=0(sparse),1(dense), [1]=dim
#define EXPRINFO_MPROD         -53      // [0]=0(sparse),1(dense), [1],[2]=dim
#define EXPRINFO_FEM           -54      // [0]=0(sparse),1(dense), [1],[2]=dim

// these contain constant matrices
#define EXPRINFO_CMPROD        -55      // params.m contains A
#define EXPRINFO_CGFEM         -56      // params.m contains A

// this should be (last entry)-1 
#define EXPRINFO_UNDEFINED     -57
#define EXPRINFO_NUMOFPREDEF   -(EXPRINFO_UNDEFINED)

#define EXPR_LASTARG            NULL

// possible types of the expressions
// ex_bound, ex_linear, ex_quadratic, ex_polynomial, and ex_other are
// mutually exclusive
enum { // type flags
       ex_bound=1, ex_linear=1<<1, ex_quadratic=1<<2, ex_polynomial=1<<3,
       ex_other=1<<4,

       // automatic from Karush-John conditions (for vars. and constr.)
       // ex_kj .... only additional vars, constr. from KJ-conditions
       // ex_org ... original vars, constr. (both set = none set)
       ex_kj=1<<7, ex_org=1<<8,

       // redundant (both set = none set)
       ex_redundant=1<<9, ex_notredundant=1<<10,
      
       // activity 
       // both set = none set = all constraints
       ex_active_lo=1<<11, ex_inactive_lo=1<<12,
       ex_active_hi=1<<13, ex_inactive_hi=1<<14,
       ex_active=ex_active_lo|ex_active_hi,
       ex_inactive=ex_inactive_lo|ex_inactive_hi,

       // integer
       ex_integer=1<<15,

       // forall, exists, stochastic, free
       // none set = select all
       ex_exists = 1<<16,
       ex_forall = 1<<17,
       ex_free = 1<<18,
       ex_stochastic = 1<<19,
       
       // convexity flags (known to be!)
       ex_convex=1<<20, ex_concave=1<<21,
       
       // bound flags
       ex_inequality=1<<28, ex_equality=1<<29,
       ex_leftbound=1<<30, ex_rightbound=1<<31,

       // short cuts
       ex_atmlin=ex_bound|ex_linear,                    // at most linear
       ex_atmquad=ex_atmlin|ex_quadratic,               // at most quadratic
       ex_atmpoly=ex_atmquad|ex_polynomial,             // at most polynomial
       ex_nonlin=ex_quadratic|ex_polynomial|ex_other,   // non linear
       ex_nonbnd=ex_linear|ex_nonlin,                   // not bounds
       ex_any=ex_atmlin|ex_nonlin,                      // any
       ex_bothbound=ex_leftbound|ex_rightbound};

typedef interval rhs_t; // use intervals as right hand sides of constraints.
                        // more general sets could be introduced later
typedef std::vector<void*> evaluator_v;

#include <addinfo.h>

class expression_node
{
public:
  unsigned int node_num;  // node number for indexing

  int operator_type;      // this is a number describing the operation.
                          // negative numbers describe standard operations
                          // as defined above.
                          // the positive numbers describe other operations
                          // like elementary functions (exp, pow, sin,...)
                          // or more complicated functions like linear or
                          // general quadratic terms, user-defined functions,
                          // piecewise linear approximations,...

  unsigned int n_parents, n_children;
                          // number of parents, children

  std::vector<double> coeffs;  // coefficients of the sub_expressions

  additional_info_u params; // additional expression info

  interval f_bounds;      // bounds on this node
  
  unsigned short is_var;  // this node represents is_var variables
  std::vector<unsigned int> var_idx;  // the variable indices corresponding to this node

  semantics sem;          // additional semantics information like
                          // integer (y/n), stochastic (y/n), karush-john (y/n)
                          // convexity,...

  variable_indicator v_i; // this node depends on which variables?

  evaluator_v* ev;        // optional evaluators used instead of tree walks
                          // NULL means no evaluators, map if some or all
                          // are defined. This is for recursive_cached_walk

private:
  void init()
  {
    is_var = 0;
    f_bounds.set(-INFINITY, INFINITY);
  }

public:
  // constructors and destructor
  expression_node() : node_num(), operator_type(0), n_parents(0),
                      n_children(0), coeffs(), params(), var_idx(),
                      sem(), v_i(), ev(NULL)
    { init(); }

  expression_node(int et, int nn) : node_num(nn), operator_type(et),
                                    n_parents(0), n_children(0), coeffs(),
                                    params(), var_idx(), sem(), v_i(),
                                    ev(NULL)
    { init(); }

  expression_node(const expression_node& __x) : node_num(__x.node_num),
        operator_type(__x.operator_type), n_parents(__x.n_parents),
        n_children(__x.n_children), coeffs(__x.coeffs), params(__x.params),
        f_bounds(__x.f_bounds), is_var(__x.is_var), var_idx(__x.var_idx),
        sem(__x.sem), v_i(__x.v_i), ev(__x.ev)
    { }

  ~expression_node()
    {
      if(node_num == 0)
        return;
      if(ev) delete(ev);
    }

  // assignment operator
  expression_node& operator=(const expression_node& __x)
  {
    operator_type = __x.operator_type;
    node_num = __x.node_num;
    v_i = __x.v_i;
    coeffs = __x.coeffs;
    params = __x.params;
    ev = __x.ev;
    sem = __x.sem;
    var_idx = __x.var_idx;
    is_var = __x.is_var;
    f_bounds = __x.f_bounds;
    return *this;
  }

  class parents_compare;
  class children_compare;
  class parents_compare_eq;
  bool operator<(const expression_node& __x) const;

  // other methods

  void merge(const expression_node& __s)
  {
    f_bounds.intersect(__s.f_bounds);
    if(operator_type != EXPRINFO_VARIABLE)
    {
      is_var += __s.is_var;
      var_idx.insert(var_idx.end(), __s.var_idx.begin(), __s.var_idx.end());
    }
    n_parents += __s.n_parents;
    sem.merge(__s.sem);
  }
  
  void set_bounds(interval __i)
  {
    f_bounds = __i;
  }

  void set_bounds(double __d = 0.)
  {
    f_bounds = interval(__d);
  }

  void set_bounds(int __i)
  {
    set_bounds(__i+0.);
  }

  void set_bounds(double lo, double up)
  {
    f_bounds = interval(lo, up);
  }

  void add_is_var(unsigned int idx)
  {
    is_var++;
    var_idx.push_back(idx);
  }

  void rm_is_var(unsigned int idx)
  {
    for(std::vector<unsigned int>::iterator b = var_idx.begin();
        b != var_idx.end(); b++)
      if(*b == idx)
      {
        var_idx.erase(b);
        is_var--;
      }
  }

  bool is(unsigned int __tp) const;
    
  // and others needed
  // print the expression_node
  friend std::ostream& operator<< (std::ostream& o, const expression_node& __x);

  // construct C expression
  friend std::string& print_C_pre(std::string& __s, const expression_node& __x);
  friend std::string& print_C_post(std::string& __s, const expression_node& __x);

  // and others needed
  const variable_indicator& var_indicator() const { return v_i; }

  // extra evaluation routines
  double f_evaluate(int argnum, int idx, const std::vector<double> &x, const variable_indicator& v_i, double fold, double fupd, std::vector<double> *cache_data) const { return 0; }
  interval i_evaluate(int argnum, int idx, const std::vector<interval> &x, const variable_indicator& v_i, interval fold, interval fupd, std::vector<interval> *cache_data) const { return interval(); }
  interval cp_evaluate(int argnum, int idx, const std::vector<interval> &node_range, const variable_indicator& v_i, interval fold, interval fupd, std::vector<interval> *cache_data) const { return interval(); }
public:
};

// include implementation of the huge methods
#include <expr-inline.h>

#endif // _EXPRESSION_H_

---