Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

evaluator.h

Go to the documentation of this file.
00001 // Evaluator Basics implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2003 Hermann Schichl
00004 //
00005 // This file is part of the COCONUT API.  This library
00006 // is free software; you can redistribute it and/or modify it under the
00007 // terms of the Library GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // Library GNU General Public License for more details.
00015 
00016 // As a special exception, you may use this file as part of a free software
00017 // library without restriction.  Specifically, if other files instantiate
00018 // templates or use macros or inline functions from this file, or you compile
00019 // this file and link it with other files to produce an executable, this
00020 // file does not by itself cause the resulting executable to be covered by
00021 // the Library GNU General Public License.  This exception does not however
00022 // invalidate any other reasons why the executable file might be covered by
00023 // the Library GNU General Public License.
00024 
00027 #ifndef _EVALUATOR_H_
00028 #define _EVALUATOR_H_
00029 
00030 #include <vector>
00031 #include <dag.h>
00032 #include <g_algo.h>
00033 #include <stdint.h>
00034 #include <coconut_config.h>
00035 
00036 using namespace vgtl;
00037 
00038 static unsigned int _sbits[256] = {
00039   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
00040   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00041   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00042   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00043   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00044   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00045   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00046   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00047 
00048   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00049   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00050   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00051   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00052   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00053   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00054   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00055   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
00056 };
00057 
00058 class variable_indicator
00059 {
00060 private:
00061   std::vector<uint32_t> v;
00062 public:
00063   variable_indicator() : v() {}
00064 
00065   variable_indicator(int num_of_vars) : v((num_of_vars+31)/32, 0) {}
00066   
00067   variable_indicator(const std::vector<int>& __v, int num_of_vars)
00068          : v((num_of_vars+31)/32, 0)
00069   {
00070     for(std::vector<int>::const_iterator b = __v.begin(); b != __v.end(); ++b)
00071         v[*b/32] |= (1 << (*b % 32));
00072   }
00073 
00074   variable_indicator(const variable_indicator& __x) : v(__x.v) {}
00075 
00076   void reserve(int num_of_vars)
00077   {
00078     unsigned int nv;
00079     v.reserve(nv = (num_of_vars+31)/32);
00080     if(nv > v.size()) v.insert(v.end(), nv-v.size(), 0);
00081   }
00082 
00083   void set_all(const variable_indicator& _vi)
00084   {
00085     std::vector<uint32_t>::iterator b;
00086     std::vector<uint32_t>::const_iterator d;
00087 
00088     for(b = v.begin(), d = _vi.v.begin(); b != v.end() && d != _vi.v.end();
00089         ++b, ++d)
00090     {
00091       *b |= *d;
00092     }
00093   }
00094 
00095   void set(int __i)
00096   {
00097     v[__i/32] |= (1 << (__i % 32));
00098   }
00099 
00100   void set(std::vector<int> __v)
00101   {
00102     for(std::vector<int>::const_iterator b = __v.begin(); b != __v.end(); ++b)
00103         v[*b/32] |= (1 << (*b % 32));
00104   }
00105 
00106   void set(int start_idx, int end_idx) // ranges
00107   {
00108     uint32_t i = start_idx/32;
00109     uint32_t j = start_idx%32;
00110 
00111     while(end_idx > start_idx)
00112     {
00113       uint32_t k = end_idx - start_idx;
00114       if(k+j > 32) k = 32-j;
00115       if(k == 32)
00116         v[i] = 0xffffffff;
00117       else
00118         v[i] |= ((1 << k) - 1) << j;
00119       ++i;
00120       j=0;
00121       start_idx = 32*i;
00122     }
00123   }
00124 
00125   void clear()
00126   {
00127     for(std::vector<uint32_t>::iterator b = v.begin(); b != v.end(); ++b)
00128       *b = 0;
00129   }
00130 
00131   void unset(int __i)
00132   {
00133     v[__i/32] &= ~(1 << (__i % 32));
00134   }
00135 
00136   void unset(std::vector<int> __v)
00137   {
00138     for(std::vector<int>::const_iterator b = __v.begin(); b != __v.end(); ++b)
00139         v[*b/32] &= ~(1 << (*b % 32));
00140   }
00141 
00142   void unset(int start_idx, int end_idx) // ranges
00143   {
00144     uint32_t i = start_idx/32;
00145     uint32_t j = start_idx%32;
00146 
00147     while(end_idx > start_idx)
00148     {
00149       uint32_t k = end_idx - start_idx;
00150       if(k+j > 32) k = 32-j;
00151       if(k == 32)
00152         v[i] = 0;
00153       else
00154         v[i] &= ~(((1 << k) - 1) << j);
00155       ++i;
00156       j=0;
00157       start_idx = 32*i;
00158     }
00159   }
00160   
00161   unsigned int sum(int start_idx, int end_idx) const
00162   {
00163     uint32_t i = start_idx/32;
00164     uint32_t j = start_idx%32;
00165     uint32_t help;
00166     unsigned int _r = 0;
00167 
00168     while(end_idx > start_idx)
00169     {
00170       uint32_t k = end_idx - start_idx;
00171       if(k+j > 32) k = 32-j;
00172       if(k == 32)
00173       {
00174         help = v[i];
00175       }
00176       else
00177         help = v[i] & (((1 << k) - 1) << j);
00178       for(int ___j = 4; ___j != 0; --___j)
00179       {
00180         _r += _sbits[help & 255];
00181         help >>= 8;
00182       }
00183       ++i;
00184       j=0;
00185       start_idx = 32*i;
00186     }
00187     return _r;
00188   }
00189 
00190   bool test(int __i) const
00191   {
00192     return v[__i/32] & (1 << (__i % 32));
00193   }
00194 
00195   bool match(const variable_indicator& __v) const
00196   {
00197     std::vector<uint32_t>::const_iterator b1, b2;
00198     uint32_t r = 0;
00199 
00200     for(b1 = v.begin(), b2 = __v.v.begin();
00201         b1 != v.end() && b2 != __v.v.end();
00202         ++b1, ++b2)
00203     {
00204       r |= *b1 & *b2;
00205     }
00206     return !r;
00207   }
00208 
00209   variable_indicator& operator=(const variable_indicator& __v)
00210   {
00211     v = __v.v;
00212     return *this;
00213   }
00214 
00215   bool operator==(const variable_indicator& __v)
00216   {
00217     return v == __v.v;
00218   }
00219 
00220   std::vector<int> encode()
00221   {
00222     std::vector<int> __c;
00223 
00224     __c.reserve(v.size());
00225     __c.insert(__c.end(), v.begin(), v.end());
00226     return __c;
00227   }
00228 
00229   void decode(const std::vector<int>& __e)
00230   {
00231     if(!v.empty())
00232       v.erase(v.begin(), v.end());
00233     v.reserve(__e.size());
00234     v.insert(v.end(), __e.begin(), __e.end());
00235   }
00236 };
00237 
00238 template <class _Tp, class _NData, class _Result, class _Walker>
00239 class _evaluator_base
00240 {
00241 private:
00242   typedef _evaluator_base<_Tp,_NData,_Result,_Walker> _Self;
00243 
00244 public:
00245   typedef _Tp data_type;
00246   typedef _NData node_data_type;
00247   
00248   typedef _Result return_value;
00249   typedef _Walker walker;
00250 
00251 protected:
00252   _Tp eval_data;
00253 
00254 public:
00255   _evaluator_base() : eval_data() {}
00256   _evaluator_base(const _Tp& __x) : eval_data(__x) {}
00257   _evaluator_base(const _Self& __x) : eval_data(__x.eval_data) {}
00258 
00259   virtual ~_evaluator_base() {}
00260 
00261   virtual return_value vvalue() { return return_value(); }
00262   virtual return_value value()  { return return_value(); }
00263 
00264   virtual int vcollect(const return_value& __cresult) { return 0; }
00265   virtual int collect(const node_data_type& __data,
00266                        const return_value& __cresult) { return 0; }
00267 
00268   virtual void postorder(const node_data_type& __data) {}
00269   virtual walker short_cut_to(const node_data_type& __data) PURE_VIRTUAL
00270 };
00271 
00272 template <class _Tp, class _NData, class _Result, class _Walker>
00273 class evaluator_base : public _evaluator_base<_Tp,_NData,_Result,_Walker>
00274 {
00275 public:
00276   typedef typename _evaluator_base<_Tp,_NData,_Result,_Walker>::node_data_type
00277                                                                 node_data_type;
00278   typedef typename _evaluator_base<_Tp,_NData,_Result,_Walker>::return_value
00279                                                                 return_value;
00280   typedef typename _evaluator_base<_Tp,_NData,_Result,_Walker>::walker
00281                                                                 walker;
00282 
00283   virtual int preorder(const node_data_type& __data) { return 1; }
00284   virtual walker short_cut_to(const node_data_type& __data) PURE_VIRTUAL
00285 };
00286 
00287 template <class _Tp, class _NData, class _Result, class _Walker>
00288 class cached_evaluator_base : public _evaluator_base<_Tp, _NData, _Result,_Walker>
00289 {
00290 private:
00291   typedef _evaluator_base<_Tp, _NData, _Result,_Walker> _Base;
00292   typedef cached_evaluator_base<_Tp,_NData,_Result,_Walker> _Self;
00293 
00294 protected:
00295   const variable_indicator* v_ind;  
00296 
00297 public:
00298   typedef typename _Base::node_data_type node_data_type;
00299   typedef typename _Base::return_value return_value;
00300   typedef typename _Base::walker walker;
00301 
00302   virtual int preorder(const node_data_type& __data) { return 1; }
00303   virtual walker short_cut_to(const node_data_type& __data) PURE_VIRTUAL
00304 
00305 public:
00306   cached_evaluator_base() : _Base(), v_ind() {}
00307   cached_evaluator_base(const _Tp& __x, const variable_indicator& __v) :
00308         _Base(__x),  v_ind(__v) {}
00309   cached_evaluator_base(const _Self& __x) : _Base(__x), v_ind(__x.v_ind) {}
00310   
00311   virtual ~cached_evaluator_base() {}
00312 };
00313 
00314 template <class _Tp, class _NData, class _Result, class _Walker>
00315 class forward_evaluator_base : public evaluator_base<_Tp, _NData, _Result,_Walker>
00316 {
00317 private:
00318   typedef evaluator_base<_Tp, _NData, _Result,_Walker> _Base;
00319 
00320 public:
00321   // constructors and destructors are inherited
00322   typedef typename _Base::node_data_type node_data_type;
00323   typedef typename _Base::return_value return_value;
00324   typedef typename _Base::walker walker;
00325 
00326 public:
00327   int preorder(const node_data_type& __data)
00328         { return initialize(__data); }
00329   void postorder(const node_data_type& __data)
00330         { calculate(__data); cleanup(__data); }
00331   int collect(const node_data_type& __data, const return_value& __rval)
00332         { return update(__data, __rval); }
00333   int vcollect(const return_value& __rval)
00334         { return update(__rval); }
00335   return_value value() { return calculate_value(false); }
00336   return_value vvalue() { return calculate_value(true); }
00337   void vinit() { initialize(); }
00338 
00339 public:
00340   virtual void initialize() {}
00341   virtual int initialize(const node_data_type& __data) {}
00342   virtual void calculate(const node_data_type& __data) {}
00343   virtual void cleanup(const node_data_type& __data) {}
00344   virtual int update(const return_value& __rval) { return 0; }
00345   virtual int update(const node_data_type& __data, const return_value& __rval)
00346         { return 0; }
00347   virtual return_value calculate_value(bool eval_all) { return return_value(); }
00348 };
00349 
00350 template <class _Tp, class _NData, class _Result, class _Walker>
00351 class backward_evaluator_base : public evaluator_base<_Tp, _NData, _Result,_Walker>
00352 {
00353 private:
00354   typedef evaluator_base<_Tp, _NData, _Result,_Walker> _Base;
00355   typedef backward_evaluator_base<_Tp, _NData, _Result,_Walker> _Self;
00356 
00357 public:
00358   typedef typename _Base::node_data_type node_data_type;
00359   typedef typename _Base::return_value return_value;
00360   typedef typename _Base::walker walker;
00361 
00362   // only virtual constructors and destructors
00363   backward_evaluator_base() : _Base() {}
00364   backward_evaluator_base(const _Tp& __x) : _Base(__x) {}
00365   backward_evaluator_base(const _Self& __x) : _Base(__x) {}
00366   virtual ~backward_evaluator_base() {}
00367 
00368 public:
00369   int preorder(const node_data_type& __data) { initialize(__data);
00370                                                return calculate(__data); }
00371   void postorder(const node_data_type& __data) { cleanup(__data); }
00372   int collect(const node_data_type& __data, const return_value& __rval)
00373         { return update(__data, __rval); }
00374   int vcollect(const return_value& __rval)
00375         { return update(__rval); }
00376   return_value value() { return calculate_value(false); }
00377   return_value vvalue() { return calculate_value(true); }
00378   void vinit() { initialize(); }
00379 
00380 public:
00381   virtual void initialize() {}
00382   virtual void initialize(const node_data_type& __data) {}
00383   virtual int calculate(const node_data_type& __data) {}
00384   virtual void cleanup(const node_data_type& __data) {}
00385   virtual int update(const node_data_type& __data, const return_value& __rval)
00386         { return 0; }
00387   virtual int update(const return_value& __rval) { return 0; }
00388   virtual return_value calculate_value(bool eval_all) { return return_value(); }
00389 };
00390 
00391 template <class _Tp, class _NData, class _Result, class _Walker>
00392 class cached_forward_evaluator_base : public cached_evaluator_base<_Tp, _NData, _Result,_Walker>
00393 {
00394 public:
00395   typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::node_data_type
00396                                                                 node_data_type;
00397   typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::return_value
00398                                                                 return_value;
00399   typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::walker
00400                                                                 walker;
00401 
00402   // constructors and destructors are inherited
00403 
00404 public:
00405   virtual bool is_cached(const node_data_type& __data)
00406         { return v_ind->match(__data.var_indicator()); }
00407 
00408   int preorder(const node_data_type& __data)
00409         { if(!is_cached(__data))
00410             return initialize(__data);
00411           else
00412           {
00413             retrieve_from_cache(__data);
00414             return 0;
00415           }
00416         }
00417   void postorder(const node_data_type& __data)
00418         { calculate(__data); cleanup(__data); }
00419   int collect(const node_data_type& __data, const return_value& __rval)
00420         { return update(__data, __rval); }
00421   int vcollect(const return_value& __rval)
00422         { return update(__rval); }
00423   return_value value() { return calculate_value(false); }
00424   return_value vvalue() { return calculate_value(true); }
00425   void vinit() { initialize(); }
00426 
00427 public:
00428   virtual void initialize() {}
00429   virtual int initialize(const node_data_type& __data) { return 1; }
00430   virtual void calculate(const node_data_type& __data) {}
00431   virtual void retrieve_from_cache(const node_data_type& __data) {}
00432   virtual void cleanup(const node_data_type& __data) {}
00433   virtual int update(const node_data_type& __data, const return_value& __rval)
00434         { return 0; }
00435   virtual int update(const return_value& __rval) { return 0; }
00436   virtual return_value calculate_value(bool eval_all) {return return_value(); }
00437 };
00438 
00439 template <class _Tp, class _NData, class _Result, class _Walker>
00440 class cached_backward_evaluator_base : public cached_evaluator_base<_Tp, _NData, _Result,_Walker>
00441 {
00442 public:
00443   typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::node_data_type
00444                                                                 node_data_type;
00445   typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::return_value
00446                                                                 return_value;
00447   typedef typename cached_evaluator_base<_Tp, _NData, _Result,_Walker>::walker
00448                                                                 walker;
00449 
00450   // constructors and destructors are inherited
00451 
00452 public:
00453   virtual bool is_cached(const node_data_type& __data)
00454         { return (*v_ind).match(__data.var_indicator()); }
00455 
00456   int preorder(const node_data_type& __data)
00457         { if(!is_cached(__data))
00458             return calculate(__data);
00459           else
00460           {
00461             retrieve_from_cache(__data);
00462             return 0;
00463           }
00464         }
00465   void postorder(const node_data_type& __data) { cleanup(__data); }
00466   int collect(const node_data_type& __data, const return_value& __rval)
00467         { return update(__data, __rval); }
00468   int vcollect(const return_value& __rval)
00469         { return update(__rval); }
00470   void vinit() { initialize(); }
00471   return_value value() { return calculate_value(false); }
00472   return_value vvalue() { return calculate_value(true); }
00473 
00474 public:
00475   virtual void initialize() {}
00476   virtual int calculate(const node_data_type& __data) {return 1;}
00477   virtual void cleanup(const node_data_type& __data) {}
00478   virtual void retrieve_from_cache(const node_data_type& __data) {}
00479   virtual int update(const node_data_type& __data, const return_value& __rval)
00480         { return 0; }
00481   virtual int update(const return_value& __rval) { return 0; }
00482   virtual return_value calculate_value(bool eval_all) {return return_value();}
00483 };
00484 
00485 template <class _Walker, class _Visitor>
00486 typename _Visitor::return_value recursive_short_cut_walk(_Walker __w,
00487                                                          _Visitor __f)
00488 {
00489   _Walker __x;
00490   typename _Walker::children_iterator __it, __e;
00491 
00492   if(__w.is_ground())
00493   {
00494     int j = 0;
00495     __e = __w.child_end();
00496     __f.vinit();
00497     for(__it = __w.child_begin(); __it != __e; ++__it)
00498     {
00499       if(!j)
00500       {
00501         j = __f.vcollect(_recursive_short_cut_walk(__w>>__it, __f));
00502         if(j < 0)
00503           break;
00504       }
00505       else
00506         j--;
00507     }
00508     return __f.vvalue();
00509   }
00510   else if(__w.is_sky())
00511     return __f.vvalue();
00512   else
00513   {
00514     int i = __f.preorder(*__w);
00515     if(i < 0)
00516     {
00517       __x = __f.short_cut_to(*__w);
00518       if(__x.is_sky())
00519         return __f.vvalue();
00520     }
00521     else
00522       __x = __w;
00523     int j = i-1;
00524     if(i != 0)
00525     {
00526       __e = __x.child_end();
00527       for(__it = __x.child_begin(); __it != __e; ++__it)
00528       {
00529         if(!j)
00530         {
00531           j = __f.collect(*__w, _recursive_cached_walk(__x>>__it, __f));
00532           if(j<0)
00533             break;
00534         } 
00535         else
00536           j--;
00537       }
00538     }
00539     // else the result is in the cache
00540     __f.postorder(*__w);
00541     return __f.value();
00542   }
00543 }
00544 
00545 template <class _Walker, class _Visitor>
00546 typename _Visitor::return_value _recursive_short_cut_walk(_Walker __w,
00547                                                        _Visitor __f)
00548 {
00549   _Walker __x;
00550   typename _Walker::children_iterator __it, __e;
00551 
00552   if(__w.is_sky())
00553     return __f.vvalue();
00554   else
00555   {
00556     int i = __f.preorder(*__w);
00557     if(i < 0)
00558     {
00559       __x = __f.short_cut_to(*__w);
00560       if(__x.is_sky())
00561         return __f.vvalue();
00562     }
00563     else
00564       __x = __w;
00565     int j = i-1;
00566     if(i != 0)
00567     {
00568       __e = __x.child_end();
00569       for(__it = __x.child_begin(); __it != __e; ++__it)
00570       {
00571         if(!j)
00572         {
00573           j = __f.collect(*__w, _recursive_cached_walk(__x>>__it, __f));
00574           if(j<0)
00575             break;
00576         } 
00577         else
00578           j--;
00579       }
00580     }
00581     // else the result is in the cache
00582     __f.postorder(*__w);
00583     return __f.value();
00584   }
00585 }
00586   
00587 template <class _Visitor, class _Walker>
00588 typename _Visitor::return_value evaluate(_Visitor __v, _Walker __start)
00589 {
00590   return recursive_short_cut_walk(__start, __v);
00591 }
00592 
00593 #endif /* _EVALUATOR_H_ */

Generated on Tue Nov 4 01:57:57 2003 for COCONUT API by doxygen1.2.18