expression_tree  3.2
 All Classes Files Functions Variables Typedefs
include/expression_tree.h
Go to the documentation of this file.
00001 /*
00002         (C) Copyright Thierry Seegers 2010-2011. Distributed under the following license:
00003 
00004         Boost Software License - Version 1.0 - August 17th, 2003
00005 
00006         Permission is hereby granted, free of charge, to any person or organization
00007         obtaining a copy of the software and accompanying documentation covered by
00008         this license (the "Software") to use, reproduce, display, distribute,
00009         execute, and transmit the Software, and to prepare derivative works of the
00010         Software, and to permit third-parties to whom the Software is furnished to
00011         do so, all subject to the following:
00012 
00013         The copyright notices in the Software and this entire statement, including
00014         the above license grant, this restriction and the following disclaimer,
00015         must be included in all copies of the Software, in whole or in part, and
00016         all derivative works of the Software, unless such copies or derivative
00017         works are solely in the form of machine-executable object code generated by
00018         a source language processor.
00019 
00020         THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00021         IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00022         FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
00023         SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
00024         FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
00025         ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
00026         DEALINGS IN THE SOFTWARE.
00027 */
00028 
00029 #if !defined(EXPRESSION_TREE_H)
00030      #define EXPRESSION_TREE_H
00031 
00033 #define GCC_VERSION (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
00034 
00035 
00036 #include <functional>   // Eventually, that's all we'll need for all compilers.
00037 
00038 #if (defined(__GNUG__) && (GCC_VERSION < 40500))
00039 #include <tr1/functional>       // Needed for g++ up to 4.4.x.
00040 #endif
00041 
00042 #if (defined(__GNUG__) && (GCC_VERSION >= 40500)) || (defined(_MSC_VER) && (_MSC_VER >= 1700))
00043 #define EXPRESSION_TREE_HAS_FUTURE
00044 #include <future>
00045 #endif
00046 
00048 
00049 // Here we define a tr1_ macro that will map to the right namespace depending on the compiler.
00050 #if (defined(__GNUG__) && (GCC_VERSION < 40500)) || (defined(_MSC_VER) && (_MSC_VER < 1600))
00051 #define tr1_ std::tr1   // For g++ up to 4.4.x or for VS 2008, the function class is in the std::tr1 namespace.
00052 #else
00053 #define tr1_ std                // For g++ 4.5.x and VS 2010, the function class is in the std namespace.
00054 #endif
00055 
00057 
00058 namespace expression_tree
00059 {
00060 
00061 template<typename T, template<typename, typename> class CachingPolicy, class ThreadingPolicy>
00062 class node;
00063 
00064 namespace detail
00065 {
00066 
00070 template<typename T>
00071 struct operation
00072 {
00073         typedef typename tr1_::function<T (const T&, const T&)> t;      
00074 };
00075 
00076 }
00077 
00078 #if defined(EXPRESSION_TREE_HAS_FUTURE)
00079 
00084 struct parallel
00085 {
00087         template<typename T, template<typename, typename> class C, class E>
00088         static T evaluate(const typename detail::operation<T>::t& o, const node<T, C, E>& l, const node<T, C, E>& r)
00089         {
00090                 std::future<T> f = std::async(&node<T, C, E>::evaluate, &l);
00091 
00092                 // Let's not rely on any assumption of parameter evaluation order...
00093                 T t = r.evaluate();
00094 
00095                 f.wait(); // Workaround GCC bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52988
00096 
00097                 return o(f.get(), t);
00098         }
00099 };
00100 
00101 #endif
00102 
00104 struct sequential
00105 {
00107         template<typename T, template<typename, typename> class C, class E>
00108         static T evaluate(const typename detail::operation<T>::t& o, const node<T, C, E>& l, const node<T, C, E>& r)
00109         {
00110                 return o(l.evaluate(), r.evaluate());
00111         }
00112 };
00113 
00114 namespace detail
00115 {
00116 
00118 template<typename T>
00119 class node_impl
00120 {
00121 public:
00122         virtual ~node_impl() {}
00123 
00127         virtual node_impl<T>* clone() const = 0;
00128 
00133         virtual bool constant() const = 0;
00134 
00139         virtual T evaluate() const = 0;
00140 };
00141 
00145 template<typename T>
00146 class leaf : public node_impl<T>
00147 {
00148         const T value; 
00149 
00150 public:
00154         leaf(const T& value) : value(value) {}
00155 
00157         leaf(const leaf<T>& other) : value(other.value) {}
00158 
00159         virtual ~leaf() {}
00160 
00162         virtual leaf<T>* clone() const
00163         {
00164                 return new leaf<T>(*this);
00165         }
00166 
00168         virtual bool constant() const
00169         {
00170                 return true;
00171         }
00172 
00174         virtual T evaluate() const
00175         {
00176                 return value;
00177         }
00178 };
00179 
00183 template<typename T>
00184 class leaf<T*> : public node_impl<T>
00185 {
00186         const T *p;     
00187 
00188 public:
00192         leaf(const T* p) : p(p) {}
00193 
00195         leaf(const leaf<T*>& other) : p(other.p) {}
00196 
00197         virtual ~leaf() {}
00198 
00200         virtual leaf<T*>* clone() const
00201         {
00202                 return new leaf<T*>(*this);
00203         }
00204 
00206         virtual bool constant() const
00207         {
00208                 return false;
00209         }
00210 
00212         virtual T evaluate() const
00213         {
00214                 return *p;
00215         }
00216 };
00217 
00222 template<typename T, template<typename, typename> class CachingPolicy, class ThreadingPolicy>
00223 class default_branch : public node_impl<T>
00224 {
00225 public:
00226         node<T, CachingPolicy, ThreadingPolicy> l;      
00227         node<T, CachingPolicy, ThreadingPolicy> r;      
00228         typename operation<T>::t f;     
00229         
00235         default_branch(const typename operation<T>::t& f, const node<T, CachingPolicy, ThreadingPolicy>& l, const node<T, CachingPolicy, ThreadingPolicy>& r) : f(f), l(l), r(r) {}
00236 
00238         default_branch(const default_branch<T, CachingPolicy, ThreadingPolicy>& other) : f(other.f), l(other.l), r(other.r) {}
00239         
00240         virtual ~default_branch() {}
00241 
00243         virtual default_branch<T, CachingPolicy, ThreadingPolicy>* clone() const
00244         {
00245                 return new default_branch<T, CachingPolicy, ThreadingPolicy>(*this);
00246         }
00247 
00249         virtual bool constant() const
00250         {
00251                 return l.constant() && r.constant();
00252         }
00253 
00255         virtual T evaluate() const
00256         {
00257                 return ThreadingPolicy::evaluate(f, l, r);
00258         }
00259 
00261         virtual node<T, CachingPolicy, ThreadingPolicy>& left()
00262         {
00263                 return l;
00264         }
00265 
00267         virtual node<T, CachingPolicy, ThreadingPolicy>& right()
00268         {
00269                 return r;
00270         }
00271 
00274         virtual void grow()
00275         {
00276                 return;
00277         }
00278 };
00279 
00280 }
00281 
00282 template<typename T, class ThreadingPolicy>
00283 struct no_caching;
00284 
00289 template<typename T, template<typename, typename> class CachingPolicy = no_caching, class ThreadingPolicy = sequential>
00290 class node
00291 {
00292         detail::node_impl<T> *impl;             
00293         node<T, CachingPolicy, ThreadingPolicy> *parent; 
00294 
00295 public:
00299         node(node<T, CachingPolicy, ThreadingPolicy> *parent = 0) : impl(0), parent(parent) {}
00300 
00302         node(const node<T, CachingPolicy, ThreadingPolicy>& other) : impl(other.impl ? other.impl->clone() : 0), parent(other.parent) {}
00303 
00305         node<T, CachingPolicy, ThreadingPolicy>& operator=(const node<T, CachingPolicy, ThreadingPolicy>& other)
00306         {
00307                 if(this != &other)
00308                 {
00309                         detail::node_impl<T>* c = other.impl->clone();
00310 
00311                         if(impl)
00312                         {
00313                                 delete impl;
00314                         }
00315 
00316                         impl = c;
00317                         parent = other.parent;
00318 
00319                         if(parent)
00320                         {
00321                                 parent->grow();
00322                         }
00323                 }
00324 
00325                 return *this;
00326         }
00327 
00328         virtual ~node()
00329         {
00330                 if(impl)
00331                 {
00332                         delete impl;
00333                 }
00334         }
00335 
00340         node<T, CachingPolicy, ThreadingPolicy>& operator=(const T& t)
00341         {
00342                 if(impl)
00343                 {
00344                         delete impl;
00345                 }
00346 
00347                 impl = new detail::leaf<T>(t);
00348 
00349                 if(parent)
00350                 {
00351                         parent->grow();
00352                 }
00353 
00354                 return *this;
00355         }
00356 
00361         node<T, CachingPolicy, ThreadingPolicy>& operator=(const T* t)
00362         {
00363                 if(impl)
00364                 {
00365                         delete impl;
00366                 }
00367 
00368                 impl = new detail::leaf<T*>(t);
00369 
00370                 if(parent)
00371                 {
00372                         parent->grow();
00373                 }
00374 
00375                 return *this;
00376         }
00377 
00382         node<T, CachingPolicy, ThreadingPolicy>& operator=(const typename detail::operation<T>::t& f)
00383         {
00384                 if(impl)
00385                 {
00386                         delete impl;
00387                 }
00388 
00389                 // Create a new branch with the passed operation and two nodes with this node as their parent.
00390                 impl = new typename CachingPolicy<T, ThreadingPolicy>::branch(f, node<T, CachingPolicy, ThreadingPolicy>(this), node<T, CachingPolicy, ThreadingPolicy>(this));
00391 
00392                 if(parent)
00393                 {
00394                         parent->grow();
00395                 }
00396 
00397                 return *this;
00398         }
00399 
00403         node<T, CachingPolicy, ThreadingPolicy>& left()
00404         {
00405                 return dynamic_cast<typename CachingPolicy<T, ThreadingPolicy>::branch*>(impl)->left();
00406         }
00407 
00411         node<T, CachingPolicy, ThreadingPolicy>& right()
00412         {
00413                 return dynamic_cast<typename CachingPolicy<T, ThreadingPolicy>::branch*>(impl)->right();
00414         }
00415 
00417         bool constant() const
00418         {
00419                 return impl ? impl->constant() : false;
00420         }
00421 
00423         T evaluate() const
00424         {
00425                 return impl->evaluate();
00426         }
00427 
00431         void grow()
00432         {
00433                 dynamic_cast<typename CachingPolicy<T, ThreadingPolicy>::branch*>(impl)->grow();
00434 
00435                 if(parent)
00436                 {
00437                         parent->grow();
00438                 }
00439         }
00440 };
00441 
00443 template<typename T, class ThreadingPolicy>
00444 struct no_caching
00445 {
00450         class branch : public detail::default_branch<T, expression_tree::no_caching, ThreadingPolicy>
00451         {
00452         public:
00454                 branch(const typename detail::operation<T>::t& f, const node<T, expression_tree::no_caching, ThreadingPolicy>& l, const node<T, expression_tree::no_caching, ThreadingPolicy>& r)
00455                         : detail::default_branch<T, expression_tree::no_caching, ThreadingPolicy>(f, l, r) {}
00456 
00458                 branch(const branch& o) : detail::default_branch<T, expression_tree::no_caching, ThreadingPolicy>(o) {}
00459 
00460                 virtual ~branch() {}
00461         };
00462 };
00463 
00465 template<typename T, class ThreadingPolicy>
00466 struct cache_on_evaluation
00467 {
00472         class branch : public detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>
00473         {
00474                 mutable bool cached;    
00475                 mutable T value;                
00476 
00477                 using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::f;
00478                 using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::l;
00479                 using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::r;
00480                 using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::constant;
00481 
00482         public:
00484                 branch(const typename detail::operation<T>::t& f, const node<T, expression_tree::cache_on_evaluation, ThreadingPolicy>& l, const node<T, expression_tree::cache_on_evaluation, ThreadingPolicy>& r)
00485                         : detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>(f, l, r), cached(false) {}
00486 
00488                 branch(const branch& o) : detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>(o), cached(o.cached), value(o.value) {}
00489 
00490                 virtual ~branch() {}
00491 
00495                 virtual T evaluate() const
00496                 {
00497                         if(cached) return value;
00498 
00499                         value = ThreadingPolicy::evaluate(f, l, r);
00500 
00501                         if(constant())
00502                         {
00503                                 cached = true;
00504                         }
00505 
00506                         return value;
00507                 }
00508 
00510                 virtual void grow()
00511                 {
00512                         cached = false;
00513                 }
00514         };
00515 };
00516 
00518 template<typename T, class ThreadingPolicy>
00519 struct cache_on_assignment
00520 {
00525         class branch : public detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>
00526         {
00527                 mutable bool cached;    
00528                 mutable T value;                
00529 
00530                 using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::f;
00531                 using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::l;
00532                 using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::r;
00533                 using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::constant;
00534 
00535         public:
00537                 branch(const typename detail::operation<T>::t& f, const node<T, expression_tree::cache_on_assignment, ThreadingPolicy>& l, const node<T, expression_tree::cache_on_assignment, ThreadingPolicy>& r)
00538                         : detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>(f, l, r), cached(false) {}
00539 
00541                 branch(const branch& o) : detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>(o), cached(o.cached), value(o.value) {}
00542 
00543                 virtual ~branch() {}
00544 
00546                 virtual T evaluate() const
00547                 {
00548                         if(cached) return value;
00549 
00550                         return value = ThreadingPolicy::evaluate(f, l, r);
00551                 }
00552                 
00555                 virtual void grow()
00556                 {
00557                         if(constant())
00558                         {
00559                                 // If this node is constant, cache its value now.
00560                                 cached = true;
00561                                 value = ThreadingPolicy::evaluate(f, l, r);
00562                         }
00563                         else
00564                         {
00565                                 // One or both children are not constant. This node is then not constant.
00566                                 cached = false;
00567                         }
00568                 }
00569         };
00570 };
00571 
00582 template<typename T, template<typename, typename> class CachingPolicy = no_caching, class ThreadingPolicy = sequential>
00583 class tree : public node<T, CachingPolicy, ThreadingPolicy>
00584 {
00585 public:
00586         virtual ~tree() {}
00587 
00589         node<T, CachingPolicy, ThreadingPolicy>& root()
00590         {
00591                 return *this;
00592         }
00593 };
00594 
00595 }
00596 
00597 #endif
00598