---

evaluator.h

Go to the documentation of this file.

// Evaluator Basics 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 _EVALUATOR_H_
#define _EVALUATOR_H_

#include <vector>
#include <dag.h>
#include <g_algo.h>
#include <stdint.h>
#include <coconut_config.h>

using namespace vgtl;

static unsigned int _sbits[256] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

class variable_indicator
{
private:
  std::vector<uint32_t> v;
public:
  variable_indicator() : v() {}

  variable_indicator(int num_of_vars) : v((num_of_vars+31)/32, 0) {}
  
  variable_indicator(const std::vector<int>& __v, int num_of_vars)
         : v((num_of_vars+31)/32, 0)
  {
    for(std::vector<int>::const_iterator b = __v.begin(); b != __v.end(); ++b)
        v[*b/32] |= (1 << (*b % 32));
  }

  variable_indicator(const variable_indicator& __x) : v(__x.v) {}

  void reserve(int num_of_vars)
  {
    unsigned int nv;
    v.reserve(nv = (num_of_vars+31)/32);
    if(nv > v.size()) v.insert(v.end(), nv-v.size(), 0);
  }

  void set_all(const variable_indicator& _vi)
  {
    std::vector<uint32_t>::iterator b;
    std::vector<uint32_t>::const_iterator d;

    for(b = v.begin(), d = _vi.v.begin(); b != v.end() && d != _vi.v.end();
        ++b, ++d)
    {
      *b |= *d;
    }
  }

  void set(int __i)
  {
    v[__i/32] |= (1 << (__i % 32));
  }

  void set(std::vector<int> __v)
  {
    for(std::vector<int>::const_iterator b = __v.begin(); b != __v.end(); ++b)
        v[*b/32] |= (1 << (*b % 32));
  }

  void set(int start_idx, int end_idx) // ranges
  {
    uint32_t i = start_idx/32;
    uint32_t j = start_idx%32;

    while(end_idx > start_idx)
    {
      uint32_t k = end_idx - start_idx;
      if(k+j > 32) k = 32-j;
      if(k == 32)
        v[i] = 0xffffffff;
      else
        v[i] |= ((1 << k) - 1) << j;
      ++i;
      j=0;
      start_idx = 32*i;
    }
  }

  void clear()
  {
    for(std::vector<uint32_t>::iterator b = v.begin(); b != v.end(); ++b)
      *b = 0;
  }

  void unset(int __i)
  {
    v[__i/32] &= ~(1 << (__i % 32));
  }

  void unset(std::vector<int> __v)
  {
    for(std::vector<int>::const_iterator b = __v.begin(); b != __v.end(); ++b)
        v[*b/32] &= ~(1 << (*b % 32));
  }

  void unset(int start_idx, int end_idx) // ranges
  {
    uint32_t i = start_idx/32;
    uint32_t j = start_idx%32;

    while(end_idx > start_idx)
    {
      uint32_t k = end_idx - start_idx;
      if(k+j > 32) k = 32-j;
      if(k == 32)
        v[i] = 0;
      else
        v[i] &= ~(((1 << k) - 1) << j);
      ++i;
      j=0;
      start_idx = 32*i;
    }
  }
  
  unsigned int sum(int start_idx, int end_idx) const
  {
    uint32_t i = start_idx/32;
    uint32_t j = start_idx%32;
    uint32_t help;
    unsigned int _r = 0;

    while(end_idx > start_idx)
    {
      uint32_t k = end_idx - start_idx;
      if(k+j > 32) k = 32-j;
      if(k == 32)
      {
        help = v[i];
      }
      else
        help = v[i] & (((1 << k) - 1) << j);
      for(int ___j = 4; ___j != 0; --___j)
      {
        _r += _sbits[help & 255];
        help >>= 8;
      }
      ++i;
      j=0;
      start_idx = 32*i;
    }
    return _r;
  }

  bool test(int __i) const
  {
    return v[__i/32] & (1 << (__i % 32));
  }

  bool match(const variable_indicator& __v) const
  {
    std::vector<uint32_t>::const_iterator b1, b2;
    uint32_t r = 0;

    for(b1 = v.begin(), b2 = __v.v.begin();
        b1 != v.end() && b2 != __v.v.end();
        ++b1, ++b2)
    {
      r |= *b1 & *b2;
    }
    return !r;
  }

  variable_indicator& operator=(const variable_indicator& __v)
  {
    v = __v.v;
    return *this;
  }

  bool operator==(const variable_indicator& __v)
  {
    return v == __v.v;
  }

  std::vector<int> encode()
  {
    std::vector<int> __c;

    __c.reserve(v.size());
    __c.insert(__c.end(), v.begin(), v.end());
    return __c;
  }

  void decode(const std::vector<int>& __e)
  {
    if(!v.empty())
      v.erase(v.begin(), v.end());
    v.reserve(__e.size());
    v.insert(v.end(), __e.begin(), __e.end());
  }
};

template <class _Tp, class _NData, class _Result, class _Walker>
class _evaluator_base
{
private:
  typedef _evaluator_base<_Tp,_NData,_Result,_Walker> _Self;

public:
  typedef _Tp data_type;
  typedef _NData node_data_type;
  
  typedef _Result return_value;
  typedef _Walker walker;

protected:
  _Tp eval_data;

public:
  _evaluator_base() : eval_data() {}
  _evaluator_base(const _Tp& __x) : eval_data(__x) {}
  _evaluator_base(const _Self& __x) : eval_data(__x.eval_data) {}

  virtual ~_evaluator_base() {}

  virtual return_value vvalue() { return return_value(); }
  virtual return_value value()  { return return_value(); }

  virtual int vcollect(const return_value& __cresult) { return 0; }
  virtual int collect(const node_data_type& __data,
                       const return_value& __cresult) { return 0; }

  virtual void postorder(const node_data_type& __data) {}
  virtual walker short_cut_to(const node_data_type& __data) PURE_VIRTUAL
};

template <class _Tp, class _NData, class _Result, class _Walker>
class evaluator_base : public _evaluator_base<_Tp,_NData,_Result,_Walker>
{
public:
  typedef typename _evaluator_base<_Tp,_NData,_Result,_Walker>::node_data_type
                                                                node_data_type;
  typedef typename _evaluator_base<_Tp,_NData,_Result,_Walker>::return_value
                                                                return_value;
  typedef typename _evaluator_base<_Tp,_NData,_Result,_Walker>::walker
                                                                walker;

  virtual int preorder(const node_data_type& __data) { return 1; }
  virtual walker short_cut_to(const node_data_type& __data) PURE_VIRTUAL
};

template <class _Tp, class _NData, class _Result, class _Walker>
class cached_evaluator_base : public _evaluator_base<_Tp, _NData, _Result,_Walker>
{
private:
  typedef _evaluator_base<_Tp, _NData, _Result,_Walker> _Base;
  typedef cached_evaluator_base<_Tp,_NData,_Result,_Walker> _Self;

protected:
  const variable_indicator* v_ind;  

public:
  typedef typename _Base::node_data_type node_data_type;
  typedef typename _Base::return_value return_value;
  typedef typename _Base::walker walker;

  virtual int preorder(const node_data_type& __data) { return 1; }
  virtual walker short_cut_to(const node_data_type& __data) PURE_VIRTUAL

public:
  cached_evaluator_base() : _Base(), v_ind() {}
  cached_evaluator_base(const _Tp& __x, const variable_indicator& __v) :
        _Base(__x),  v_ind(__v) {}
  cached_evaluator_base(const _Self& __x) : _Base(__x), v_ind(__x.v_ind) {}
  
  virtual ~cached_evaluator_base() {}
};

template <class _Tp, class _NData, class _Result, class _Walker>
class forward_evaluator_base : public evaluator_base<_Tp, _NData, _Result,_Walker>
{
private:
  typedef evaluator_base<_Tp, _NData, _Result,_Walker> _Base;

public:
  // constructors and destructors are inherited
  typedef typename _Base::node_data_type node_data_type;
  typedef typename _Base::return_value return_value;
  typedef typename _Base::walker walker;

public:
  int preorder(const node_data_type& __data)
        { return initialize(__data); }
  void postorder(const node_data_type& __data)
        { calculate(__data); cleanup(__data); }
  int collect(const node_data_type& __data, const return_value& __rval)
        { return update(__data, __rval); }
  int vcollect(const return_value& __rval)
        { return update(__rval); }
  return_value value() { return calculate_value(false); }
  return_value vvalue() { return calculate_value(true); }
  void vinit() { initialize(); }

public:
  virtual void initialize() {}
  virtual int initialize(const node_data_type& __data) {}
  virtual void calculate(const node_data_type& __data) {}
  virtual void cleanup(const node_data_type& __data) {}
  virtual int update(const return_value& __rval) { return 0; }
  virtual int update(const node_data_type& __data, const return_value& __rval)
        { return 0; }
  virtual return_value calculate_value(bool eval_all) { return return_value(); }
};

template <class _Tp, class _NData, class _Result, class _Walker>
class backward_evaluator_base : public evaluator_base<_Tp, _NData, _Result,_Walker>
{
private:
  typedef evaluator_base<_Tp, _NData, _Result,_Walker> _Base;
  typedef backward_evaluator_base<_Tp, _NData, _Result,_Walker> _Self;

public:
  typedef typename _Base::node_data_type node_data_type;
  typedef typename _Base::return_value return_value;
  typedef typename _Base::walker walker;

  // only virtual constructors and destructors
  backward_evaluator_base() : _Base() {}
  backward_evaluator_base(const _Tp& __x) : _Base(__x) {}
  backward_evaluator_base(const _Self& __x) : _Base(__x) {}
  virtual ~backward_evaluator_base() {}

public:
  int preorder(const node_data_type& __data) { initialize(__data);
                                               return calculate(__data); }
  void postorder(const node_data_type& __data) { cleanup(__data); }
  int collect(const node_data_type& __data, const return_value& __rval)
        { return update(__data, __rval); }
  int vcollect(const return_value& __rval)
        { return update(__rval); }
  return_value value() { return calculate_value(false); }
  return_value vvalue() { return calculate_value(true); }
  void vinit() { initialize(); }

public:
  virtual void initialize() {}
  virtual void initialize(const node_data_type& __data) {}
  virtual int calculate(const node_data_type& __data) {}
  virtual void cleanup(const node_data_type& __data) {}
  virtual int update(const node_data_type& __data, const return_value& __rval)
        { return 0; }
  virtual int update(const return_value& __rval) { return 0; }
  virtual return_value calculate_value(bool eval_all) { return return_value(); }
};

template <class _Tp, class _NData, class _Result, class _Walker>
class cached_forward_evaluator_base : public cached_evaluator_base<_Tp, _NData, _Result,_Walker>
{
public:
  typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::node_data_type
                                                                node_data_type;
  typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::return_value
                                                                return_value;
  typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::walker
                                                                walker;

  // constructors and destructors are inherited

public:
  virtual bool is_cached(const node_data_type& __data)
        { return v_ind->match(__data.var_indicator()); }

  int preorder(const node_data_type& __data)
        { if(!is_cached(__data))
            return initialize(__data);
          else
          {
            retrieve_from_cache(__data);
            return 0;
          }
        }
  void postorder(const node_data_type& __data)
        { calculate(__data); cleanup(__data); }
  int collect(const node_data_type& __data, const return_value& __rval)
        { return update(__data, __rval); }
  int vcollect(const return_value& __rval)
        { return update(__rval); }
  return_value value() { return calculate_value(false); }
  return_value vvalue() { return calculate_value(true); }
  void vinit() { initialize(); }

public:
  virtual void initialize() {}
  virtual int initialize(const node_data_type& __data) { return 1; }
  virtual void calculate(const node_data_type& __data) {}
  virtual void retrieve_from_cache(const node_data_type& __data) {}
  virtual void cleanup(const node_data_type& __data) {}
  virtual int update(const node_data_type& __data, const return_value& __rval)
        { return 0; }
  virtual int update(const return_value& __rval) { return 0; }
  virtual return_value calculate_value(bool eval_all) {return return_value(); }
};

template <class _Tp, class _NData, class _Result, class _Walker>
class cached_backward_evaluator_base : public cached_evaluator_base<_Tp, _NData, _Result,_Walker>
{
public:
  typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::node_data_type
                                                                node_data_type;
  typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::return_value
                                                                return_value;
  typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::walker
                                                                walker;

  // constructors and destructors are inherited

public:
  virtual bool is_cached(const node_data_type& __data)
        { return (*v_ind).match(__data.var_indicator()); }

  int preorder(const node_data_type& __data)
        { if(!is_cached(__data))
            return calculate(__data);
          else
          {
            retrieve_from_cache(__data);
            return 0;
          }
        }
  void postorder(const node_data_type& __data) { cleanup(__data); }
  int collect(const node_data_type& __data, const return_value& __rval)
        { return update(__data, __rval); }
  int vcollect(const return_value& __rval)
        { return update(__rval); }
  void vinit() { initialize(); }
  return_value value() { return calculate_value(false); }
  return_value vvalue() { return calculate_value(true); }

public:
  virtual void initialize() {}
  virtual int calculate(const node_data_type& __data) {return 1;}
  virtual void cleanup(const node_data_type& __data) {}
  virtual void retrieve_from_cache(const node_data_type& __data) {}
  virtual int update(const node_data_type& __data, const return_value& __rval)
        { return 0; }
  virtual int update(const return_value& __rval) { return 0; }
  virtual return_value calculate_value(bool eval_all) {return return_value();}
};

template <class _Walker, class _Visitor>
typename _Visitor::return_value recursive_short_cut_walk(_Walker __w,
                                                         _Visitor __f)
{
  _Walker __x;
  typename _Walker::children_iterator __it, __e;

  if(__w.is_ground())
  {
    int j = 0;
    __e = __w.child_end();
    __f.vinit();
    for(__it = __w.child_begin(); __it != __e; ++__it)
    {
      if(!j)
      {
        j = __f.vcollect(_recursive_short_cut_walk(__w>>__it, __f));
        if(j < 0)
          break;
      }
      else
        j--;
    }
    return __f.vvalue();
  }
  else if(__w.is_sky())
    return __f.vvalue();
  else
  {
    int i = __f.preorder(*__w);
    if(i < 0)
    {
      __x = __f.short_cut_to(*__w);
      if(__x.is_sky())
        return __f.vvalue();
    }
    else
      __x = __w;
    int j = i-1;
    if(i != 0)
    {
      __e = __x.child_end();
      for(__it = __x.child_begin(); __it != __e; ++__it)
      {
        if(!j)
        {
          j = __f.collect(*__w, _recursive_cached_walk(__x>>__it, __f));
          if(j<0)
            break;
        } 
        else
          j--;
      }
    }
    // else the result is in the cache
    __f.postorder(*__w);
    return __f.value();
  }
}

template <class _Walker, class _Visitor>
typename _Visitor::return_value _recursive_short_cut_walk(_Walker __w,
                                                       _Visitor __f)
{
  _Walker __x;
  typename _Walker::children_iterator __it, __e;

  if(__w.is_sky())
    return __f.vvalue();
  else
  {
    int i = __f.preorder(*__w);
    if(i < 0)
    {
      __x = __f.short_cut_to(*__w);
      if(__x.is_sky())
        return __f.vvalue();
    }
    else
      __x = __w;
    int j = i-1;
    if(i != 0)
    {
      __e = __x.child_end();
      for(__it = __x.child_begin(); __it != __e; ++__it)
      {
        if(!j)
        {
          j = __f.collect(*__w, _recursive_cached_walk(__x>>__it, __f));
          if(j<0)
            break;
        } 
        else
          j--;
      }
    }
    // else the result is in the cache
    __f.postorder(*__w);
    return __f.value();
  }
}
  
template <class _Visitor, class _Walker>
typename _Visitor::return_value evaluate(_Visitor __v, _Walker __start)
{
  return recursive_short_cut_walk(__start, __v);
}

#endif /* _EVALUATOR_H_ */

---