int_evaluator.h

Go to the documentation of this file.

// Interval Evaluator implementation -*- C++ -*-

// $Id: int_evaluator.h 924 2009-11-12 17:09:13Z mihaly $
// 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 _INTERVAL_EVALUATOR_H_
#define _INTERVAL_EVALUATOR_H_

#include <coconut_config.h>
#include <evaluator.h>
#include <expression.h>
#include <model.h>
#include <eval_main.h>
#include <linalg.h>
#include <math.h>
#include <api_exception.h>

using namespace vgtl;

namespace coco {

typedef interval (*interval_evaluator)(const std::vector<interval>* __x,
                                 const variable_indicator& __v);


struct interval_eval_type
{
  const std::vector<interval>* x;       
  std::vector<interval>* cache;         
  const model* mod;                     
  union { void *p; interval_st d; int info; } u; 
  interval r;                           
  unsigned int n;                       
  bool do_intersect;    
};


class interval_eval : public
  cached_forward_evaluator_base<interval_eval_type,expression_node,interval,
                                expression_const_walker>
{
private:
  typedef cached_forward_evaluator_base<interval_eval_type,expression_node,
                                        interval,expression_const_walker> _Base;

protected:
  bool is_cached(const node_data_type& __data)
  {
    if(__data.operator_type == EXPRINFO_LIN ||
       __data.operator_type == EXPRINFO_QUAD)
      return true;
    else
      return false;
#if 0
    if(eval_data.cache && __data.n_parents > 1 && __data.n_children > 0)
      return true;
    else
      return false;
#endif
  }

private:
  interval __power(double __coeff, const interval &__x, int __exp)
  {
    if(__exp == 0)
      return 1.;
    else
    {
      interval k = __coeff*__x;
      switch(__exp)
      {
        case 1:
          return k;
          break;
        case 2:
          return sqr(k);
          break;
        case -1:
          return 1./k;
          break;
        case -2:
          return 1./sqr(k);
          break;
        default:
          return ipow(k, __exp);
          break;
      }
    }
    return 0;           // we never come here!
  }

public:
  interval_eval(const std::vector<interval>& __x, const variable_indicator& __v,
                const model& __m, std::vector<interval>* __c, bool do_i = true)
                : _Base()
  {
    eval_data.x = &__x;
    eval_data.cache = __c;
    eval_data.mod = &__m;
    eval_data.u.d = 0.;
    v_ind = &__v;
    eval_data.n = 0;
    eval_data.do_intersect = do_i;
  }

  interval_eval(const interval_eval& __v) : _Base(__v) {}
  
  ~interval_eval() {}

  expression_const_walker short_cut_to(const expression_node& __data)
  { return eval_data.mod->node(0); }    // return anything

  void new_box(const std::vector<interval>& __x, const variable_indicator& __v)
  {
    eval_data.x = &__x;
    v_ind = &__v;
  }


  void initialize() { return; }
  
  int initialize(const expression_node& __data)
  {
    eval_data.n = 0;
    if(__data.ev && (*__data.ev)[FUNC_RANGE])
    // is there a short-cut evaluator defined?
    {
      eval_data.r =
        (*(interval_evaluator)(*__data.ev)[FUNC_RANGE])(eval_data.x,
                                                                 *v_ind);
      return 0;     // don't perform the remaining graph walk
    }
    else
    {
      switch(__data.operator_type)
      {
        case EXPRINFO_SUM:
        case EXPRINFO_PROD:
        case EXPRINFO_MAX:
        case EXPRINFO_MIN:
        case EXPRINFO_INVERT:
        case EXPRINFO_DIV:
          eval_data.r = __data.params.nd();
          break;
        case EXPRINFO_MONOME:
        case EXPRINFO_IN:
        case EXPRINFO_AND:
        case EXPRINFO_NOGOOD:
          eval_data.r = 1.;
          break;
        case EXPRINFO_ALLDIFF:
          eval_data.u.p = (void*) new std::vector<interval>;
          ((std::vector<interval>*)eval_data.u.p)->reserve(__data.n_children);
          // no break!
        case EXPRINFO_MEAN:
        case EXPRINFO_IF:
        case EXPRINFO_OR:
        case EXPRINFO_NOT:
        case EXPRINFO_COUNT:
        case EXPRINFO_SCPROD:
        case EXPRINFO_NORM:
        case EXPRINFO_LEVEL:
          eval_data.r = 0.;
          break;
        case EXPRINFO_DET:
        case EXPRINFO_PSD:
          // here construct square interval matrix
          break;
        case EXPRINFO_COND:
        case EXPRINFO_FEM:
        case EXPRINFO_MPROD:
          // here construct rectangular interval matrix
          break;
      }
      return 1;
    }
  }

  void calculate(const expression_node& __data)
  {
    if(__data.operator_type > 0)
    {
      eval_data.r = __data.i_evaluate(-1, __data.params.nn(), *eval_data.x,
                                      *v_ind, eval_data.r, interval(0,0), NULL);
    }
    if(eval_data.do_intersect)
      eval_data.r.intersectwith(__data.f_bounds);
  }

  void retrieve_from_cache(const expression_node& __data)
  {
    if(__data.operator_type == EXPRINFO_LIN)
    {
      const linalg::matrix<double>::Row& lrw(eval_data.mod->lin[__data.params.nn()]);
      linalg::matrix<double>::Row::const_iterator _x, _e;

      eval_data.r = interval(0.);
      for(_x = lrw.begin(); _x != _e; ++_x)
        eval_data.r += (*eval_data.x)[_x.index()] * *_x;
    }
    else if(__data.operator_type == EXPRINFO_QUAD)
    {
      throw nyi_exception("int_evaluator: QUAD");
    }
    else
      eval_data.r = (*eval_data.cache)[__data.node_num];
  }

  int update(const interval& __rval)
  {
    eval_data.r = __rval;
    return 0;
  }

  int update(const expression_node& __data, const interval& __rval)
  {
    interval __x;
    int ret = 0;
    if(__data.operator_type < 0)
    {
      switch(__data.operator_type)
      {
        case EXPRINFO_CONSTANT:
          eval_data.r = __data.params.nd();
          break;
        case EXPRINFO_VARIABLE:
          eval_data.r = (*eval_data.x)[__data.params.nn()];
          break;
        case EXPRINFO_SUM:
        case EXPRINFO_MEAN:
          eval_data.r += __data.coeffs[eval_data.n++]*__rval;
          break;
        case EXPRINFO_PROD:
          // the coefficients MUST be collected in __data.params.nd()
          eval_data.r *= __rval;
          if(eval_data.r == 0.) ret = -1;
          break;
        case EXPRINFO_MONOME:
          // the coefficients MUST be collected in __data.params.nd()
          eval_data.r *= __power(__data.coeffs[eval_data.n], __rval,
                                 __data.params.n()[eval_data.n]);
          if(eval_data.r == 0.) ret = -1;
          eval_data.n++;
          break;
        case EXPRINFO_MAX:
          { interval h = __rval * __data.coeffs[eval_data.n++];
            eval_data.r = imax(eval_data.r, h);
          }
          break;
        case EXPRINFO_MIN:
          { interval h = __rval * __data.coeffs[eval_data.n++];
            eval_data.r = imin(eval_data.r, h);
          }
          break;
        case EXPRINFO_SCPROD:
          { interval h = __data.coeffs[eval_data.n]*__rval;
            // if the number of children is odd, the list is implicitly
            // lengthened by one null element (i.e. implicitly shortened)
            if(eval_data.n & 1) // y_n
              eval_data.r += interval(eval_data.u.d)*h;
            else // x_n
              eval_data.u.d = h;
          }
          eval_data.n++;
          break;
        case EXPRINFO_NORM:
          if(__data.params.nd() == COCO_INF)
          {
            interval h = abs(__rval * __data.coeffs[eval_data.n]);
            eval_data.r = imax(eval_data.r, h);
          }
          else
          {
            interval h = abs(__data.coeffs[eval_data.n]*__rval);
            eval_data.r += pow(h, interval(__data.params.nd()));
          }
          ++eval_data.n;
          if(eval_data.n == __data.n_children)
            eval_data.r = pow(eval_data.r, interval(1.)/__data.params.nd());
          break;
        case EXPRINFO_INVERT:
          eval_data.r /= __rval;
          break;
        case EXPRINFO_DIV:
          // this evaluator requires, that the second coefficient
          // is put into the first.
          if(eval_data.n == 0)
            eval_data.r *= __rval;
          else
            eval_data.r /= __rval;
          ++eval_data.n;
          break;
        case EXPRINFO_SQUARE:
          { interval h = __data.coeffs[0]*__rval+__data.params.nd();
            eval_data.r = sqr(h);
          }
          break;
        case EXPRINFO_INTPOWER:
          eval_data.r = __power(__data.coeffs[0], __rval, __data.params.nn());
          break;
        case EXPRINFO_SQROOT:
          eval_data.r = sqrt(__data.coeffs[0]*__rval+__data.params.nd());
          break;
        case EXPRINFO_ABS:
          eval_data.r = abs(__data.coeffs[0]*__rval+__data.params.nd());
          break;
        case EXPRINFO_POW:
          { interval h = __rval * __data.coeffs[eval_data.n];
            if(eval_data.n == 0)
              eval_data.r = h+__data.params.nd();
            else
              eval_data.r = pow(eval_data.r, h);
          }
          ++eval_data.n;
          break;
        case EXPRINFO_EXP:
          eval_data.r = exp(__rval*__data.coeffs[0]+__data.params.nd());
          break;
        case EXPRINFO_LOG:
          eval_data.r = log(__rval*__data.coeffs[0]+__data.params.nd());
          break;
        case EXPRINFO_SIN:
          eval_data.r = sin(__rval*__data.coeffs[0]+__data.params.nd());
          break;
        case EXPRINFO_COS:
          eval_data.r = cos(__rval*__data.coeffs[0]+__data.params.nd());
          break;
        case EXPRINFO_ATAN2:
          { interval h = __rval * __data.coeffs[eval_data.n];
            if(eval_data.n == 0)
              eval_data.r = h;
            else
              eval_data.r = atan2(eval_data.r, h);
            ++eval_data.n;
          }
          break;
        case EXPRINFO_GAUSS:
          { interval h = (__data.coeffs[0]*__rval-__data.params.d()[0])/
                                __data.params.d()[1];
            eval_data.r = gauss(h);
          }
          break;
        case EXPRINFO_POLY:
          throw nyi_exception("int_evaluator: POLY");
          break;
        case EXPRINFO_LIN:
        case EXPRINFO_QUAD:
          // we will never be here
          break;
        case EXPRINFO_IN:
          {
            __x = __data.coeffs[eval_data.n]*__rval;
            const interval& i(__data.params.i()[eval_data.n]);
            if(i.disjoint(__x))     // it is not in
            {
              eval_data.r = -1.;
              ret = -1;
            }
            else if(eval_data.r != interval(-1.))
            {
              if(!i.superset(__x))  // in and out are possible
              {
                if(i.sup() == __x.inf() || i.inf() == __x.sup())
                // intersection is only on the border
                  eval_data.r = interval(-1.,0.);
                else if(eval_data.r.sup() > 0)
                  eval_data.r = interval(-1.,1.);
              }
              else if(i.inf() == __x.inf() || i.sup() == __x.sup())
              // they are not disjoint, and i is a superset of __x
              // but a border is possible
              {
                if(eval_data.r.inf() == 1.)
                {
                  if(__x.is_thin())       // only border
                    eval_data.r = 0.;
                  else                    // interior and border possible
                    eval_data.r = interval(0.,1.);
                }
                else if(__x.is_thin() && eval_data.r.inf() == 0.)
                  eval_data.r = 0.;
              }
              // if __x is in the interior of i eval_data.r does not change
            }
          }
          eval_data.n++;
          break;
        case EXPRINFO_IF:
          __x = __rval * __data.coeffs[eval_data.n];
          if(eval_data.n == 0) // this is the condition
          {
            const interval& i(__data.params.ni());
            if(i.superset(__x))      // always true
              eval_data.u.info = 0;
            else if(i.disjoint(__x)) // never true
            {
              eval_data.u.info = 1;
              ret = 1;               // skip if part
            }
            else                     // both is possible
              eval_data.u.info = 2;
          }
          else if(eval_data.n == 1)  // this is the if part
          {
            eval_data.r = __x;
            if(eval_data.u.info == 0)  // it was always true
              ret = -1;              // don't continue walking
          }
          else // this is the else part
          {
            if(eval_data.u.info == 1) // only the else part
              eval_data.r = __x;
            else                      // both parts
              eval_data.r.hullwith(__x);
          }
          eval_data.n += ret+1;
          break;
        case EXPRINFO_AND:
          { __x = __data.coeffs[eval_data.n]*__rval;
            const interval& i(__data.params.i()[eval_data.n]);
            if(eval_data.r != 0.)
            {
              if(i.disjoint(__x))
              {
                eval_data.r = 0;
                ret = -1;         // result cannot become more false
              }
              else if(!i.superset(__x))
                eval_data.r = interval(0.,1.);
              // else this does not change the value
            }
          }
          eval_data.n++;
          break;
        case EXPRINFO_OR:
          { __x = __data.coeffs[eval_data.n]*__rval;
            const interval& i(__data.params.i()[eval_data.n]);
            if(eval_data.r != 1.)
            {
              if(i.superset(__x))
              {
                eval_data.r = 1;
                ret = -1;         // result cannot become more true
              }
              else if(!i.disjoint(__x))
                eval_data.r = interval(0.,1.);
            }
          }
          eval_data.n++;
          break;
        case EXPRINFO_NOT:
          { __x = __data.coeffs[0]*__rval;
            const interval& i(__data.params.ni());
            if(i.superset(__x))
              eval_data.r = 0;
            else if(i.disjoint(__x))
              eval_data.r = 1;
            else
              eval_data.r = interval(0.,1.);
          }
          break;
        case EXPRINFO_IMPLIES:
          { const interval& i(__data.params.i()[eval_data.n]);
            __x = __rval * __data.coeffs[eval_data.n];
            if(eval_data.n == 0)
            {
              if(i.disjoint(__x))
              {
                eval_data.r = 1.;
                ret = -1;        // ex falso quodlibet
              }
              else if(!i.superset(__x))
                eval_data.r = interval(0.,1.);
              else
                eval_data.r = interval(0.);
            }
            else // we only get here if first clause might be true
            {
              if(i.superset(__x))
                eval_data.r = 1.;
              else if(!i.disjoint(__x))
                eval_data.r = interval(0.,1.);
              // else the value does not change
            }
            ++eval_data.n;
          }
          break;
        case EXPRINFO_COUNT:
          { __x = __data.coeffs[eval_data.n]*__rval;
            const interval& i(__data.params.i()[eval_data.n]);
            if(i.superset(__x))
              eval_data.r += 1;
            else if(!i.disjoint(__x))
              eval_data.r += interval(0.,1.);
          }
          eval_data.n++;
          break;
        case EXPRINFO_ALLDIFF:
          { __x = __data.coeffs[eval_data.n]*__rval;
            for(std::vector<interval>::const_iterator _b =
                        ((std::vector<interval>*)eval_data.u.p)->begin();
                _b != ((std::vector<interval>*)eval_data.u.p)->end(); ++_b)
            {
              interval __h = abs(__x-*_b);
              if(__h.sup() <= __data.params.nd())  // they are always equal
              {
                eval_data.r = 0;
                ret = -1;               // don't continue
                break;
              }
              else if(__h.inf() <= __data.params.nd()) // they are not always different
                eval_data.r = interval(0.,1.);
            }
            if(ret != -1)
              ((std::vector<interval>*) eval_data.u.p)->push_back(__x);
          }
          eval_data.n++;
          if(eval_data.n == __data.n_children || ret == -1)
            delete (std::vector<interval>*) eval_data.u.p;
          break;
        case EXPRINFO_HISTOGRAM:
          throw nyi_exception("int_evaluator: HISTOGRAM");
          break;
        case EXPRINFO_LEVEL:
          { int lo = (int)eval_data.r.inf();
            int hi = (int)eval_data.r.sup();
            __x = __data.coeffs[eval_data.n]*__rval;
            interval _h;

            // first adjust upper bound
            if(hi != INT_MAX)
            {
              while(hi < __data.params.im().nrows())
              { 
                _h = __data.params.im()[hi][eval_data.n];
                if(_h.superset(__x))
                  break;
                hi++;
              }
              if(hi == __data.params.im().nrows())
                hi = INT_MAX;
            }
            // then adjust lower bound
            if(lo != INT_MAX)
            {
              while(lo < __data.params.im().nrows())
              { 
                _h = __data.params.im()[lo][eval_data.n];
                if(!_h.disjoint(__x))
                  break;
                lo++;
              }
              if(lo == __data.params.im().nrows())
                lo = INT_MAX;
            }
            if(hi == INT_MAX && lo == INT_MAX)
            {
              eval_data.r = INT_MAX;
              ret = -1;
            }
            else
              eval_data.r = interval(lo+0.,hi+0.);
          }
          eval_data.n++;
          break;
        case EXPRINFO_NEIGHBOR:
          // this is suboptimal. It does not take into account
          // all the possibilities to proove that the result actually
          // EQUALS 1
          if(eval_data.n == 0)
            eval_data.r = __data.coeffs[0]*__rval;
          else
          {
            interval h = eval_data.r;
            eval_data.r = 0;
            __x = __data.coeffs[1]*__rval;
            for(unsigned int i = 0; i < __data.params.n().size(); i+=2)
            {
              if(h == __data.params.n()[i]+0. &&
                 __x == __data.params.n()[i+1]+0.)
              {
                eval_data.r = 1;
                break;
              }
              else if(h.contains(__data.params.n()[i]+0.) &&
                      __x.contains(__data.params.n()[i+1]+0.))
              {
                eval_data.r = interval(0.,1.);
                break;
              }
            }
          }
          eval_data.n++;
          break;
        case EXPRINFO_NOGOOD:
          __x = __data.coeffs[eval_data.n]*__rval;
          if(eval_data.r != 0.)
          { 
            if(!__x.contains(__data.params.n()[eval_data.n]+0.))
            {
              eval_data.r = 0.;
              ret = -1;
            }
            else if(__x != __data.params.n()[eval_data.n]+0.)
              eval_data.r = interval(0.,1.);
          }
          eval_data.n++;
          break;
        case EXPRINFO_EXPECTATION:
          throw nyi_exception("int_evaluator: EXPECTATION");
          break;
        case EXPRINFO_INTEGRAL:
          throw nyi_exception("int_evaluator: INTEGRAL");
          break;
        case EXPRINFO_LOOKUP:
        case EXPRINFO_PWLIN:
        case EXPRINFO_SPLINE:
        case EXPRINFO_PWCONSTLC:
        case EXPRINFO_PWCONSTRC:
          throw nyi_exception("int_evaluator: Table Operations");
          break;
        case EXPRINFO_DET:
        case EXPRINFO_COND:
        case EXPRINFO_PSD:
        case EXPRINFO_MPROD:
        case EXPRINFO_FEM:
          throw nyi_exception("int_evaluator: Matrix Operations");
          break;
        case EXPRINFO_RE:
        case EXPRINFO_IM:
        case EXPRINFO_ARG:
        case EXPRINFO_CPLXCONJ:
          throw nyi_exception("int_evaluator: Complex Operations");
          break;
        case EXPRINFO_CMPROD:
        case EXPRINFO_CGFEM:
          throw nyi_exception("int_evaluator: Const Matrix Operations");
          break;
        default:
          throw api_exception(apiee_evaluator,
              std::string("int_evaluator: unknown function type ")+
              convert_to_str(__data.operator_type));
          break;
      }
    }
    else if(__data.operator_type > 0)
      // update the function arguments
      eval_data.r = __data.i_evaluate(eval_data.n++, __data.params.nn(),
                        *eval_data.x, *v_ind, eval_data.r, __rval, NULL);
    // use the cache only if it is worthwhile
    //    if(eval_data.cache && __data.n_parents > 1 && __data.n_children > 0)
    if(eval_data.cache)
      (*eval_data.cache)[__data.node_num] = eval_data.r;
    return ret;
  }

  interval calculate_value(bool eval_all)
  {
    return eval_data.r;
  }
};

} // namespace coco

#endif /* _INTERVAL_EVALUATOR_H_ */

---