expression_tree
3.2
|
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