ider_evaluator.h

Go to the documentation of this file.

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

// $Id: ider_evaluator.h 923 2009-11-12 17:08:15Z 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 _IDER_EVALUATOR_H_
#define _IDER_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 bool (*prep_id_evaluator)();
typedef interval (*func_id_evaluator)(
              const std::vector<interval>* __x, const variable_indicator& __v,
              std::vector<interval>& __id_data);
typedef std::vector<interval>& (*ider_evaluator)(
              const std::vector<interval>& __d_dat,
              const variable_indicator& __v);


class prep_id_eval : public
  cached_forward_evaluator_base<std::vector<std::vector<interval> >*,
                                expression_node, bool, expression_const_walker>
{
private:
  typedef cached_forward_evaluator_base<std::vector<std::vector<interval> >*,
                                   expression_node,bool,expression_const_walker> _Base;

public:
  prep_id_eval(std::vector<std::vector<interval> >& __d,
              unsigned int _num_of_nodes)
  {
    eval_data = &__d;
    if((*eval_data).size() < _num_of_nodes)
      (*eval_data).insert((*eval_data).end(),
                          _num_of_nodes-(*eval_data).size(), std::vector<interval>());
  }

  prep_id_eval(const prep_id_eval& __x) { eval_data = __x.eval_data; }

  ~prep_id_eval() {}

  bool is_cached(const expression_node& __data)
  {
    return (*eval_data)[__data.node_num].size() > 0;
  }

  int initialize(const expression_node& __data)
  {
    (*eval_data)[__data.node_num].insert((*eval_data)[__data.node_num].end(),
        __data.n_children, interval(0.));
    return 1;
  }


  void retrieve_from_cache(const expression_node& __data) { return; }

  void initialize() { return; }

  void calculate(const expression_node& __data) { return; }

  int update(bool __rval) { return 0; }

  int update(const expression_node& __data, bool __rval)
        { return 0; }

  bool calculate_value(bool eval_all) { return true; }
};

// function evaluation at interval argument + preparation of derivative data
// for later backwards evaluation


struct func_id_eval_type
{
  const std::vector<interval>* x;       
  const std::vector<interval>* range;   
  std::vector<interval>* f;             
  std::vector<std::vector<interval> >* id_data;
  const model* mod;                     
  union { void *p; interval_st d; unsigned int info; } u; 
  interval r;                           
  unsigned int n;                       
};


class func_id_eval : public
  cached_forward_evaluator_base<func_id_eval_type, expression_node,
                                interval, expression_const_walker>
{
private:
  typedef cached_forward_evaluator_base<func_id_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;
    if(eval_data.f && __data.n_parents > 1 && __data.n_children > 0 &&
       v_ind->match(__data.var_indicator()))
      return true;
    else
      return false;
  }

private:
  interval __power(double __coeff, 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!
  }

  void __calc_max(const interval& h, const expression_node& __data)
  { 
    if(h.inf() > eval_data.r.sup())
    {
      for(unsigned int i = 0; i < eval_data.n; ++i)
        (*eval_data.id_data)[__data.node_num][i] = 0;
      (*eval_data.id_data)[__data.node_num][eval_data.n] =
                          __data.coeffs[eval_data.n];
      eval_data.r = h;
      eval_data.u.info = eval_data.n;
    }
    else if(h.sup() < eval_data.r.inf())
      (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
    else
    {
      (*eval_data.id_data)[__data.node_num][eval_data.n] =
                __data.coeffs[eval_data.n] >= 0 ?
                      interval(0.,__data.coeffs[eval_data.n]):
                      interval(__data.coeffs[eval_data.n],0.);
      (*eval_data.id_data)[__data.node_num][eval_data.u.info] =
                __data.coeffs[eval_data.u.info] >= 0 ?
                      interval(0.,__data.coeffs[eval_data.u.info]):
                      interval(__data.coeffs[eval_data.u.info],0.);
    }
  }

public:
  func_id_eval(const std::vector<interval>& __x,
                  const std::vector<interval>& __rg,
                  const variable_indicator& __v,
                  const model& __m,
                  std::vector<std::vector<interval> >& __d,
                  std::vector<interval>* __c) : _Base()
  {
    eval_data.x = &__x;
    eval_data.f = __c;
    eval_data.range = &__rg;
    eval_data.mod = &__m;
    eval_data.id_data = &__d;
    eval_data.n = 0;
    eval_data.r = interval(0.);
    eval_data.u.d = 0;
    v_ind = &__v;
  }

  func_id_eval(const func_id_eval& __x) : _Base(__x) {}

  ~func_id_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 new_range(const std::vector<interval>& __rg, const variable_indicator& __v)
  {
    eval_data.range = &__rg;
    v_ind = &__v;
  }


  void initialize() { return; }

  int initialize(const expression_node& __data)
  {
    eval_data.n = 0;
    if(__data.ev != NULL && (*__data.ev)[FUNC_ID_EVALUATOR] != NULL)
    // is there a short-cut evaluator defined?
    {
      eval_data.r =
          (*(func_id_evaluator)(*__data.ev)[FUNC_ID_EVALUATOR])(eval_data.range,
                               *v_ind, (*eval_data.id_data)[__data.node_num]);
      return 0;     // don't perform the remaining graph walk
    }
    else
    {
      switch(__data.operator_type)
      {
        case EXPRINFO_MAX:
        case EXPRINFO_MIN:
          eval_data.u.info = 0;
          // no break == continue
        case EXPRINFO_SUM:
        case EXPRINFO_INVERT:
        case EXPRINFO_PROD:
        case EXPRINFO_DIV:
          eval_data.r = __data.params.nd();
          break;
        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:
          eval_data.r = 0.;
          break;
        case EXPRINFO_NORM:
          eval_data.u.info = 0;
          eval_data.r = 0.;
          break;
        case EXPRINFO_LEVEL:
          eval_data.u.p = (void*) new std::vector<interval>;
          ((std::vector<interval>*)eval_data.u.p)->reserve(__data.n_children);
          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)
    {
#if 0
      //***** THINK ABOUT THIS LATER !
      eval_data.r = __data.f_evaluate(-1, __data.params.nn(), *eval_data.x,
                                      *v_ind, eval_data.r, 0,
                                      &((*eval_data.id_data)[__data.node_num]));
#endif
    }
  }

  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 = 0.;
      _e = lrw.end();
      for(_x = lrw.begin(); _x != _e; ++_x)
      {
        interval _h = (*eval_data.x)[_x.index()];
        eval_data.r += *_x * _h;
      }
      eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
    }
    else if(__data.operator_type == EXPRINFO_QUAD)
    {
      throw nyi_exception("func_id_evaluator: QUAD");
    }
    else
    {
    // the parallel ider_cache MUST be initialized, too
      eval_data.r = (*eval_data.f)[__data.node_num];
      eval_data.r.intersectwith((*eval_data.range)[__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();
          // don't care about id_data, CONSTANTS are ALWAYS leafs
          break;
        case EXPRINFO_VARIABLE:
          eval_data.r = (*eval_data.x)[__data.params.nn()];
          eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          // don't care about id_data, VARIABLES are ALWAYS leafs
          break;
        case EXPRINFO_SUM:
        case EXPRINFO_MEAN:
          { double h = __data.coeffs[eval_data.n];
            eval_data.r += h*__rval;
            (*eval_data.id_data)[__data.node_num][eval_data.n++] = h;
          }
          // intersect with the known range
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_PROD:
          if(eval_data.n == 0)
          {
            eval_data.r *= __rval;
            (*eval_data.id_data)[__data.node_num][0] = __data.params.nd();
          }
          else
          {
            (*eval_data.id_data)[__data.node_num][eval_data.n] = eval_data.r;
            eval_data.r *= __rval;
            for(int i = eval_data.n-1; i >= 0; i--)
              (*eval_data.id_data)[__data.node_num][i] *= __rval;
          }
          ++eval_data.n;
          // intersect with the known range
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_MONOME:
          if(eval_data.n == 0)
          {
            int n = __data.params.n()[0];
            if(n != 0)
            {
              eval_data.r = __power(__data.coeffs[0], __rval, n);
              (*eval_data.id_data)[__data.node_num][0] =
                 (n*__data.coeffs[0])*__power(__data.coeffs[0], __rval, n-1);
            }
            else
            {
              eval_data.r = 1;
              (*eval_data.id_data)[__data.node_num][0] = 0;
            }
          }
          else
          {
            int n = __data.params.n()[eval_data.n];
            if(n != 0)
            {
              __x = __power(__data.coeffs[eval_data.n], __rval, n-1)*
                                __data.coeffs[eval_data.n];
              (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                                        eval_data.r*(n+0.)*__x;
              __x = __power(__data.coeffs[eval_data.n], __rval, n);
              eval_data.r *= __x;
              for(int i = eval_data.n-1; i >= 0; i--)
                (*eval_data.id_data)[__data.node_num][i] *= __x;
            }
            else
              (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
          }
          ++eval_data.n;
          // intersect with the known range
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_MAX:
          __calc_max(__rval * __data.coeffs[eval_data.n], __data);
          ++eval_data.n;
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_MIN:
          { interval h = __rval * __data.coeffs[eval_data.n];
            if(h.sup() < eval_data.r.inf())
            {
              for(unsigned int i = 0; i < eval_data.n; ++i)
                (*eval_data.id_data)[__data.node_num][i] = 0;
              (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                  __data.coeffs[eval_data.n];
              eval_data.r = h;
              eval_data.u.info = eval_data.n;
            }
            else if(h.inf() > eval_data.r.sup())
              (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
            else
            {
              (*eval_data.id_data)[__data.node_num][eval_data.n] =
                        __data.coeffs[eval_data.n] >= 0 ?
                              interval(0.,__data.coeffs[eval_data.n]):
                              interval(__data.coeffs[eval_data.n],0.);
              (*eval_data.id_data)[__data.node_num][eval_data.u.info] =
                        __data.coeffs[eval_data.u.info] >= 0 ?
                              interval(0.,__data.coeffs[eval_data.u.info]):
                              interval(__data.coeffs[eval_data.u.info],0.);
            }
          }
          ++eval_data.n;
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          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;
              (*eval_data.id_data)[__data.node_num][eval_data.n] =
                          interval(eval_data.u.d)*__data.coeffs[eval_data.n-1];
              (*eval_data.id_data)[__data.node_num][eval_data.n-1] =
                                                  h*__data.coeffs[eval_data.n];
            }
            else // x_n
              eval_data.u.d = h;
          }
          eval_data.n++;
          // intersect with the known range
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_NORM:
          if(__data.params.nd() == COCO_INF)
            __calc_max(abs(__rval*__data.coeffs[eval_data.n]), __data);
          else
          { interval h = abs(__data.coeffs[eval_data.n]*__rval);
            eval_data.r += pow(h, interval(__data.params.nd()));
            (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                pow(h, interval(__data.params.nd())-1.);
          }
          eval_data.n++;
          // intersect with the known range
          if(eval_data.n == __data.n_children)
          {
            if(__data.params.nd() != COCO_INF)
            {
              interval h = pow(eval_data.r, interval(1.)/__data.params.nd()-1.);
              for(unsigned int i = 0; i < eval_data.n; ++i)
                (*eval_data.id_data)[__data.node_num][eval_data.n] *= h;
              eval_data.r = pow(eval_data.r, interval(1.)/__data.params.nd());
            }
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          }
          break;
        case EXPRINFO_INVERT:
          { interval h = 1./__rval;
            eval_data.r *= h;
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            (*eval_data.id_data)[__data.node_num][0] =
                                -eval_data.r*eval_data.r/__data.params.nd();
          }
          break;
        case EXPRINFO_DIV:  // has two children
          if(eval_data.n++ == 0)
            eval_data.r = __rval;
          else
          {
            interval h = 1./__rval;
            eval_data.r *=
                (*eval_data.id_data)[__data.node_num][0] = __data.params.nd()*h;
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            (*eval_data.id_data)[__data.node_num][1] = -eval_data.r*h;
          }
          break;
        case EXPRINFO_SQUARE:
          { interval h = __data.coeffs[0]*__rval+__data.params.nd();
            eval_data.r = sqr(h);
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            (*eval_data.id_data)[__data.node_num][0] = 2.*h*__data.coeffs[0];
          }
          break;
        case EXPRINFO_INTPOWER:
          { int hl = __data.params.nn();
            if(hl == 0)
            {
              eval_data.r = 1;
              (*eval_data.id_data)[__data.node_num][0] = 0;
            }
            else
            {
              interval kl = __data.coeffs[0]*__rval;
              switch(hl)
              {
                case 1:
                  eval_data.r = kl;
                  (*eval_data.id_data)[__data.node_num][0] = __data.coeffs[0];
                  break;
                case 2:
                  eval_data.r = sqr(kl);
                  (*eval_data.id_data)[__data.node_num][0] =
                        2.*kl*__data.coeffs[0];
                  break;
                case -1:
                  { interval h = 1./kl;
                    eval_data.r = h;
                    h = eval_data.r.
                          intersectwith((*eval_data.range)[__data.node_num]);
                    (*eval_data.id_data)[__data.node_num][0] =
                                -h*h/__data.coeffs[0];
                  }
                  break;
                case -2:
                  { interval h = 1./kl;
                    interval k = sqr(h);
                    k.intersectwith((*eval_data.range)[__data.node_num]);
                    eval_data.r = k;
                    (*eval_data.id_data)[__data.node_num][0] =
                                                -2.*h*k*__data.coeffs[0];
                  }
                  break;
                default:
                  { interval h;
                    if(hl < 0)
                    {
                      h = ipow(kl, hl);
                      h.intersectwith((*eval_data.range)[__data.node_num]);
                      eval_data.r = h;
                      (*eval_data.id_data)[__data.node_num][0] =
                                        (hl+0.)*h*__data.coeffs[0];
                    }
                    else // hl > 0
                    {
                      h = ipow(kl, hl-1);
                      eval_data.r = ipow(kl, hl);
                      (*eval_data.id_data)[__data.node_num][0] =
                                        (hl+0.)*h*__data.coeffs[0];
                    }
                  }
                  break;
              }
            }
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          }
          break;
        case EXPRINFO_SQROOT:
          { interval h = sqrt(__data.coeffs[0]*__rval+__data.params.nd());
            h.intersectwith((*eval_data.range)[__data.node_num]);
            eval_data.r = h;
            (*eval_data.id_data)[__data.node_num][0] = 0.5*__data.coeffs[0]/h;
          }
          break;
        case EXPRINFO_ABS:
          { interval h = __data.coeffs[0]*__rval+__data.params.nd();
            eval_data.r = abs(h);
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            if(h.contains(0))
              h = interval(-1.,1.);
            else if(h.inf() > 0)
              h = 1.;
            else
              h = -1.;
            (*eval_data.id_data)[__data.node_num][0] = h*__data.coeffs[0];
          }
          break;
        case EXPRINFO_POW:
          { interval hh = __rval * __data.coeffs[eval_data.n];
            if(eval_data.n++ == 0)
              eval_data.r = hh+__data.params.nd();
            else
            { 
              if(hh == interval(0.))
              {
                (*eval_data.id_data)[__data.node_num][0] = 0;
                (*eval_data.id_data)[__data.node_num][1] =
                                  log(eval_data.r)*__data.coeffs[1];
                eval_data.r = 1;
              }
              else
              {
                interval h = pow(eval_data.r, hh);
                h.intersectwith((*eval_data.range)[__data.node_num]);

                (*eval_data.id_data)[__data.node_num][0] =
                         hh*pow(eval_data.r, hh-1.)*__data.coeffs[0];
                (*eval_data.id_data)[__data.node_num][1] =
                                       log(eval_data.r)*h*__data.coeffs[1];
                eval_data.r = h;
              }
            }
          }
          break;
        case EXPRINFO_EXP:
          { interval h = exp(__rval*__data.coeffs[0]+__data.params.nd());
            h.intersectwith((*eval_data.range)[__data.node_num]);
            eval_data.r = h;
            (*eval_data.id_data)[__data.node_num][0] = h*__data.coeffs[0];
          }
          break;
        case EXPRINFO_LOG:
          { interval h = __rval*__data.coeffs[0]+__data.params.nd();
            eval_data.r = log(h);
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            (*eval_data.id_data)[__data.node_num][0] = __data.coeffs[0]/h;
          }
          break;
        case EXPRINFO_SIN:
          { interval h = __rval*__data.coeffs[0]+__data.params.nd();
            eval_data.r = sin(h);
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            (*eval_data.id_data)[__data.node_num][0] = __data.coeffs[0]*cos(h);
          }
          break;
        case EXPRINFO_COS:
          { interval h = __rval*__data.coeffs[0]+__data.params.nd();
            eval_data.r = cos(h);
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            (*eval_data.id_data)[__data.node_num][0] = -__data.coeffs[0]*sin(h);
          }
          break;
        case EXPRINFO_ATAN2:
          { interval hh = __rval * __data.coeffs[eval_data.n];
            if(eval_data.n++ == 0)
              eval_data.r = hh;
            else
            { interval h = eval_data.r;
              h *= h;
              h += hh*hh;
              (*eval_data.id_data)[__data.node_num][0] = __data.coeffs[0]*hh/h;
              (*eval_data.id_data)[__data.node_num][1] =
                                                  -__data.coeffs[1]*eval_data.r/h;
              eval_data.r = atan2(eval_data.r,hh);
              eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            }
          }
          break;
        case EXPRINFO_GAUSS:
          { interval h = (__data.coeffs[0]*__rval-__data.params.d()[0])/
                                __data.params.d()[1];
            interval k = exp(-h*h);
            k.intersectwith((*eval_data.range)[__data.node_num]);
            eval_data.r = k;
            (*eval_data.id_data)[__data.node_num][0] =
                                 -2*__data.coeffs[0]*k*h/__data.params.d()[1];
          }
          break;
        case EXPRINFO_POLY:
          throw nyi_exception("func_id_evaluator: POLY");
          break;
        case EXPRINFO_QUAD:
        case EXPRINFO_LIN:
          // 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;
              std::vector<interval>& r((*eval_data.id_data)[__data.node_num]);
              r.erase(r.begin(),r.end());
              r.insert(r.end(),__data.n_children,interval(0.));
            }
            else
            {
              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.);
                  if(i.sup() == __x.inf())
                    (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                interval(-COCO_INF,0.);
                  else
                    (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                interval(0.,COCO_INF);
                }
                else
                {
                  // intersection is big
                  if(eval_data.r.sup() > 0)
                    eval_data.r = interval(-1.,1.);

                  if(i.subset(__x))
                    (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                interval(-COCO_INF,COCO_INF);
                  else if(__x.contains(i.inf()))
                    (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                interval(0.,COCO_INF);
                  else
                    (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                interval(-COCO_INF,0.);
                }
              }
              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.inf() == __x.sup())
                  (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
                else if(i.inf() == __x.inf() && i.sup() == __x.sup())
                  (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                  interval(-COCO_INF,COCO_INF);
                else if(i.inf() == __x.inf())
                  (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                  interval(0.,COCO_INF);
                else
                  (*eval_data.id_data)[__data.node_num][eval_data.n] = 
                                                  interval(-COCO_INF,0.);
              }
              else
              // if __x is in the interior of i eval_data.r does not change
                (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
            }
          }
          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;
              (*eval_data.id_data)[__data.node_num][0] = 0;
              (*eval_data.id_data)[__data.node_num][2] = 0;
            }
            else if(i.disjoint(__x)) // never true
            {
              eval_data.u.info = 1;
              (*eval_data.id_data)[__data.node_num][0] = 0;
              (*eval_data.id_data)[__data.node_num][1] = 0;
              ret = 1;               // skip if part
            }
            else                     // both is possible
              eval_data.u.info = 1;
          }
          else if(eval_data.n == 1)  // this is either the if or the else part
          {
            eval_data.r = __x;
            (*eval_data.id_data)[__data.node_num][1] = __data.coeffs[1];
            if(eval_data.u.info == 0)  // it was always true
              ret = -1;                // don't continue walking
          }
          else // this is the else part if both possibilities could be true
          {
            if(eval_data.u.info == 1)
              eval_data.r = __x;
            else
            {
              eval_data.r.hullwith(__x);
              (*eval_data.id_data)[__data.node_num][0] =
                                                interval(-COCO_INF,COCO_INF);
            }
            (*eval_data.id_data)[__data.node_num][2] = __data.coeffs[2];
          }
          if(eval_data.n == 2 || ret == -1)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          else
            eval_data.n += 1+ret;
          break;
        case EXPRINFO_AND:
          { __x = __data.coeffs[eval_data.n]*__rval;
            const interval& i(__data.params.i()[eval_data.n]);
            if(i.disjoint(__x))
            {
              eval_data.r = 0;
              std::vector<interval>& r((*eval_data.id_data)[__data.node_num]);
              r.erase(r.begin(),r.end());
              r.insert(r.end(),__data.n_children,interval(0.));
              ret = -1;
            }
            else if(!i.superset(__x))
            {
              double lo = 0, hi = 0;
              if(eval_data.r != 0)
                eval_data.r = interval(0.,1.);
              if(__x.inf() < i.inf())
                hi = COCO_INF;
              if(__x.sup() > i.sup())
                lo = -COCO_INF;
              (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                                               interval(lo,hi);
            }
            else
              (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
          }
          eval_data.n++;
          // intersect with the known range
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_OR:
          { __x = __data.coeffs[eval_data.n]*__rval;
            const interval& i(__data.params.i()[eval_data.n]);
            if(i.superset(__x))
            {
              eval_data.r = 1;
              std::vector<interval>& r((*eval_data.id_data)[__data.node_num]);
              r.erase(r.begin(),r.end());
              r.insert(r.end(),__data.n_children,interval(0.));
              ret = -1;
            }
            else if(!i.disjoint(__x))
            {
              if(eval_data.r != 0)
                eval_data.r = interval(0.,1.);
              double lo = 0, hi = 0;
              if(__x.inf() < i.inf())
                hi = COCO_INF;
              if(__x.sup() > i.sup())
                lo = -COCO_INF;
              (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                                               interval(lo,hi);
            }
            else
              (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
          }
          eval_data.n++;
          // intersect with the known range
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_NOT:
          { __x = __data.coeffs[0]*__rval;
            const interval& i(__data.params.ni());
            if(i.superset(__x))
            {
              eval_data.r = 0;
              (*eval_data.id_data)[__data.node_num][0] = 0;
            }
            else if(i.disjoint(__x))
            {
              eval_data.r = 1;
              (*eval_data.id_data)[__data.node_num][0] = 0;
            }
            else
            {
              eval_data.r = interval(0.,1.);
              double lo = 0, hi = 0;
              if(__x.inf() < i.inf())
                lo = -COCO_INF;
              if(__x.sup() > i.sup())
                hi = COCO_INF;
              (*eval_data.id_data)[__data.node_num][0] = interval(lo,hi);
            }
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          }
          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.;
                (*eval_data.id_data)[__data.node_num][0] = 0;
                (*eval_data.id_data)[__data.node_num][1] = 0;
                ret = -1;        // ex falso quodlibet
              }
              else if(!i.superset(__x))
              {
                eval_data.r = interval(0.,1.);
                double lo = 0, hi = 0;
                if(__x.inf() < i.inf())
                  lo = -COCO_INF;
                if(__x.sup() > i.sup())
                  hi = COCO_INF;
                (*eval_data.id_data)[__data.node_num][0] = interval(lo,hi);
              }
              else
              {
                eval_data.r = interval(0.);
                (*eval_data.id_data)[__data.node_num][0] = 0;
              }
            }
            else // we only get here if first clause might be true
            {
              if(i.superset(__x)) // true result is always true
              {
                eval_data.r = 1.;
                (*eval_data.id_data)[__data.node_num][0] = 0;
                (*eval_data.id_data)[__data.node_num][1] = 0;
              }
              else if(!i.disjoint(__x))
              {
                eval_data.r = interval(0.,1.);
                double lo = 0, hi = 0;
                if(__x.inf() < i.inf())
                  hi = COCO_INF;
                if(__x.sup() > i.sup())
                  lo = -COCO_INF;
                (*eval_data.id_data)[__data.node_num][0] = interval(lo,hi);
              }
              else
                (*eval_data.id_data)[__data.node_num][1] = 0;
              eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
            }
            ++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;
              (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
            }
            else if(!i.disjoint(__x))
            {
              eval_data.r += interval(0.,1.);
              double lo = 0, hi = 0;
              if(__x.inf() < i.inf())
                hi = COCO_INF;
              if(__x.sup() > i.sup())
                lo = -COCO_INF;
              (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                                               interval(lo,hi);
            }
            else
              (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
          }
          eval_data.n++;
          // intersect with the known range
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_ALLDIFF:
          { int i; 
            std::vector<interval>::const_iterator _b;
            __x = __data.coeffs[eval_data.n]*__rval;
            (*eval_data.id_data)[__data.node_num][eval_data.n] = 0;
            for(_b = ((std::vector<interval>*)eval_data.u.p)->begin(), i = 0;
                _b != ((std::vector<interval>*)eval_data.u.p)->end(); ++_b, ++i)
            {
              interval __h = abs(__x-*_b);
              if(__h.sup() <= __data.params.nd())  // they are always equal
              {
                eval_data.r = 0;
                std::vector<interval>& r((*eval_data.id_data)[__data.node_num]);
                r.erase(r.begin(),r.end());
                r.insert(r.end(),__data.n_children,interval(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.);
                (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                                interval(-COCO_INF,COCO_INF);
                (*eval_data.id_data)[__data.node_num][i] =
                                                interval(-COCO_INF,COCO_INF);
              }
            }
            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)
          {
            if(eval_data.r == 1.)       // all are always different
            {
              std::vector<interval>& r((*eval_data.id_data)[__data.node_num]);
              r.erase(r.begin(),r.end());
              r.insert(r.end(),__data.n_children,interval(0.));
            }
            delete (std::vector<interval>*) eval_data.u.p;
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          }
          break;
        case EXPRINFO_HISTOGRAM:
          throw nyi_exception("func_id_evaluator: HISTOGRAM");
          break;
        case EXPRINFO_LEVEL:
          { // we have to make this one more complicated than
            // in the interval evaluation. For deciding the final
            // outcome, we (seemingly) need to know the results
            // for all before determining the derivatives
            int lo = 0;
            int hi = 0;
            __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;
            }
            ((std::vector<interval>*)eval_data.u.p)->
                                        push_back(interval(lo+0.,hi+0.));
            eval_data.r = interval(std::min(eval_data.r.inf(),lo+0.),
                                   std::max(eval_data.r.sup(),hi+0.));
          }
          eval_data.n++;
          if(eval_data.n == __data.n_children)
          {
            std::vector<interval>& v(*((std::vector<interval>*)eval_data.u.p));
            for(unsigned int i = 0; i < __data.n_children; ++i)
            {
              if(v[i].is_thin() || v[i].sup() < eval_data.r.inf())
                (*eval_data.id_data)[__data.node_num][i] = 0;
              else
                (*eval_data.id_data)[__data.node_num][i] =
                                                interval(0.,COCO_INF);
            }
            delete (std::vector<interval>*)eval_data.u.p;
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          }
          break;
        case EXPRINFO_NEIGHBOR:
          // this is suboptimal. It does not take into account
          // all the possibilities to proove that the result actually
          // EQUALS 1
          // furthermore, it sets all derivatives to [-I,I] because
          // computing derivatives is nonsense, anyway
          (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                                interval(-COCO_INF,COCO_INF);
          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++;
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_NOGOOD:
          // derivatives are nonsense here, so set them to [-I,I]
          (*eval_data.id_data)[__data.node_num][eval_data.n] =
                                                interval(-COCO_INF,COCO_INF);
          __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++;
          if(eval_data.n == __data.n_children)
            eval_data.r.intersectwith((*eval_data.range)[__data.node_num]);
          break;
        case EXPRINFO_EXPECTATION:
          throw nyi_exception("func_id_evaluator: EXPECTATION");
          break;
        case EXPRINFO_INTEGRAL:
          throw nyi_exception("func_id_evaluator: INTEGRAL");
          break;
        case EXPRINFO_LOOKUP:
        case EXPRINFO_PWLIN:
        case EXPRINFO_SPLINE:
        case EXPRINFO_PWCONSTLC:
        case EXPRINFO_PWCONSTRC:
          throw nyi_exception("func_id_evaluator: Table Operations");
          break;
        case EXPRINFO_DET:
        case EXPRINFO_COND:
        case EXPRINFO_PSD:
        case EXPRINFO_MPROD:
        case EXPRINFO_FEM:
          throw nyi_exception("func_id_evaluator: Matrix Operations");
          break;
        case EXPRINFO_RE:
        case EXPRINFO_IM:
        case EXPRINFO_ARG:
        case EXPRINFO_CPLXCONJ:
          throw nyi_exception("func_id_evaluator: Complex Operations");
          break;
        case EXPRINFO_CMPROD:
        case EXPRINFO_CGFEM:
          throw nyi_exception("func_id_evaluator: Const Matrix Operations");
          break;
        default:
          throw api_exception(apiee_evaluator,
              std::string("func_id_evaluator: unknown function type ")+
              convert_to_str(__data.operator_type));
          break;
      }
    }
    else if(__data.operator_type > 0)
    {
#if 0
      // think about this later
      // update the function arguments
      eval_data.r = __data.f_evaluate(eval_data.n++, __data.params.nn(),
                        *eval_data.x, *v_ind, eval_data.r, __rval,
                            &(*eval_data.id_data)[__data.node_num]);
#endif
    }
    // use the cache only if it is worthwhile
    if(eval_data.f && __data.n_parents > 1 && __data.n_children > 0)
      (*eval_data.f)[__data.node_num] = eval_data.r;
    return ret;
  }

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


struct ider_eval_type
{
  std::vector<std::vector<interval> >* id_data; 
  std::vector<std::vector<interval> >* d_cache; 
  std::vector<interval>* grad_vec;  
  const std::vector<interval>* x;   
  const model* mod;                 
  interval mult;                    
  interval mult_trans;              
  unsigned int child_n;             
};


class ider_eval : public
  cached_backward_evaluator_base<ider_eval_type,expression_node,bool,
                                 expression_const_walker>
{
private:
  typedef cached_backward_evaluator_base<ider_eval_type,expression_node,
                                         bool,expression_const_walker> _Base;

protected:
  bool is_cached(const node_data_type& __data)
     { 
       if(eval_data.d_cache && __data.n_parents > 1 && __data.n_children > 0
          && (*eval_data.d_cache)[__data.node_num].size() > 0 &&
          v_ind->match(__data.var_indicator()))
       {
         return true;
       }
       else
         return false;
     }
                                        
public:
  ider_eval(const std::vector<interval>& __x,
      std::vector<std::vector<interval> >& __ider_data, variable_indicator& __v,
      const model& __m, std::vector<std::vector<interval > >* __d, 
      std::vector<interval>& __grad)
  { // __grad MUST BE INITIALIZED WITH 0 AND THE CORRECT LENGTH
    eval_data.id_data = &__ider_data;
    eval_data.d_cache = __d;
    eval_data.mod = &__m;
    eval_data.grad_vec = &__grad;
    eval_data.mult_trans = 1;
    eval_data.mult = 0;
    eval_data.x = &__x;
    v_ind = &__v;
  }

  ider_eval(const ider_eval& __d) { eval_data = __d.eval_data; }

  ~ider_eval() {}

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

  void new_result(std::vector<interval>& __grad)
  {
    eval_data.grad_vec = &__grad;
  }

  void set_mult(const interval& scal)
  {
    eval_data.mult_trans = scal;
  }
public:

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


  // at virtual nodes (ground, sky)
  void initialize()
  {
    eval_data.child_n = 0;
  }

  // before the children are visited
  int calculate(const expression_node& __data)
  {
    if(__data.operator_type == EXPRINFO_CONSTANT)
      return 0;
    else if(__data.operator_type == EXPRINFO_VARIABLE)
    {
      // update the gradient
      (*eval_data.grad_vec)[__data.params.nn()] += eval_data.mult_trans;
      return 0;
    }
    else if(__data.operator_type == EXPRINFO_LIN)
    { // update the gradient
      const linalg::matrix<double>::Row& lrw(eval_data.mod->lin[__data.params.nn()]);
      linalg::matrix<double>::Row::const_iterator _x, _e;
      _e = lrw.end();
      for(_x = lrw.begin(); _x != _e; ++_x)
        (*eval_data.grad_vec)[_x.index()] += *_x * eval_data.mult_trans;
      return 0;     // don't perform the remaining graph walk
    }
    else if(__data.operator_type == EXPRINFO_QUAD)
    { // update the gradient
      throw nyi_exception("ider_evaluator: QUAD");
      return 0;
    }
    else if(__data.ev && (*__data.ev)[IDER_EVALUATOR])
    // is there a short-cut evaluator defined?
    {
#if 0
      // think about this later
      linalg::linalg_ssum(*eval_data.grad_vec, eval_data.mult, 
          (*(ider_evaluator)(*__data.ev)[IDER_EVALUATOR])(
                              (*eval_data.id_data)[__data.node_num], *v_ind));
#endif 
      return 0;     // don't perform the remaining graph walk
    }
    else if(eval_data.mult_trans == interval(0.))
    // does not contribute to grad
      return 0;
    else
    {
      eval_data.child_n = 1;
      eval_data.mult = eval_data.mult_trans;
      if(__data.n_parents > 1 && __data.n_children > 0 && eval_data.d_cache)
      { 
        eval_data.mult_trans = (*eval_data.id_data)[__data.node_num][0];
      }
      else // set multiplier for first child
        eval_data.mult_trans *= (*eval_data.id_data)[__data.node_num][0];
      return 1;
    }
  }

  // after all children have finished
  void cleanup(const expression_node& __data)
  {
    // use the cache only if it is worthwhile
    if(__data.n_parents > 1 && __data.n_children > 0 && eval_data.d_cache
       && (*eval_data.d_cache)[__data.node_num].size() == 0)
    {
      (*eval_data.d_cache)[__data.node_num] = *eval_data.grad_vec;
      linalg::linalg_smult(*eval_data.grad_vec, interval(eval_data.mult));
    }
  }

  void retrieve_from_cache(const expression_node& __data)
  {
    // the parallel f_cache MUST be initialized, too
    linalg::linalg_ssum(*eval_data.grad_vec, interval(eval_data.mult_trans), 
          (*eval_data.d_cache)[__data.node_num]);
  }

  int update(const bool& __rval)
  {
    eval_data.child_n++;
    return 0;
  }

  // after the current child is processed
  int update(const expression_node& __data, const bool& __rval)
  {
    if(__data.n_children == 0)
      return 0;
    if(__data.n_parents > 1 && __data.n_children > 0 && eval_data.d_cache)
    { 
      if(eval_data.child_n < __data.n_children)
        eval_data.mult_trans =
                (*eval_data.id_data)[__data.node_num][eval_data.child_n];
    }
    else if(eval_data.child_n < __data.n_children)
    { // prepare multiplier for the next child
      eval_data.mult_trans = eval_data.mult *
                (*eval_data.id_data)[__data.node_num][eval_data.child_n];
    }
    eval_data.child_n++;
    return 0;
  }

  bool calculate_value(bool eval_all)
  {
    return true;
  }
};

} // namespace coco

#endif /* _IDER_EVALUATOR_H_ */

---