expression_tree.h

Go to the documentation of this file.

/*
        (C) Copyright Thierry Seegers 2010-2011. Distributed under the following license:

        Boost Software License - Version 1.0 - August 17th, 2003

        Permission is hereby granted, free of charge, to any person or organization
        obtaining a copy of the software and accompanying documentation covered by
        this license (the "Software") to use, reproduce, display, distribute,
        execute, and transmit the Software, and to prepare derivative works of the
        Software, and to permit third-parties to whom the Software is furnished to
        do so, all subject to the following:

        The copyright notices in the Software and this entire statement, including
        the above license grant, this restriction and the following disclaimer,
        must be included in all copies of the Software, in whole or in part, and
        all derivative works of the Software, unless such copies or derivative
        works are solely in the form of machine-executable object code generated by
        a source language processor.

        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
        SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
        FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
        ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
        DEALINGS IN THE SOFTWARE.
*/

#if !defined(EXPRESSION_TREE_H)
     #define EXPRESSION_TREE_H

#include <functional>
#include <future>
#include <memory>

namespace expression_tree
{

template<typename T, template<typename, typename> class CachingPolicy, class ThreadingPolicy>
class node;

namespace detail
{

template<typename T>
struct operation
{
        typedef typename std::function<T (const T&, const T&)> t;       
};

}

struct parallel
{
        template<typename T, template<typename, typename> class C, class E>
        static T evaluate(const typename detail::operation<T>::t& o, const node<T, C, E>& l, const node<T, C, E>& r)
        {
                std::future<T> f = std::async(&node<T, C, E>::evaluate, &l);

                // Let's not rely on any assumption of parameter evaluation order...
                T t = r.evaluate();

                f.wait(); // Workaround GCC bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52988

                return o(f.get(), t);
        }
};

struct sequential
{
        template<typename T, template<typename, typename> class C, class E>
        static T evaluate(const typename detail::operation<T>::t& o, const node<T, C, E>& l, const node<T, C, E>& r)
        {
                return o(l.evaluate(), r.evaluate());
        }
};

namespace detail
{

template<typename T>
class node_impl
{
public:
        virtual ~node_impl() {}

        virtual std::unique_ptr<node_impl<T>> clone() const = 0;

        virtual bool constant() const = 0;

        virtual T evaluate() const = 0;
};

template<typename T>
class leaf : public node_impl<T>
{
        const T value; 

public:
        leaf(const T& value) : value(value) {}

        leaf(const leaf<T>& other) : value(other.value) {}

        virtual ~leaf() {}

        virtual std::unique_ptr<node_impl<T>> clone() const
        {
                return std::unique_ptr<leaf<T>>(new leaf<T>(*this));
        }

        virtual bool constant() const
        {
                return true;
        }

        virtual T evaluate() const
        {
                return value;
        }
};

template<typename T>
class leaf<T*> : public node_impl<T>
{
        const T *p;     

public:
        leaf(const T* p) : p(p) {}

        leaf(const leaf<T*>& other) : p(other.p) {}

        virtual ~leaf() {}

        virtual std::unique_ptr<node_impl<T>> clone() const
        {
                return std::unique_ptr<leaf<T*>>(new leaf<T*>(*this));
        }

        virtual bool constant() const
        {
                return false;
        }

        virtual T evaluate() const
        {
                return *p;
        }
};

template<typename T, template<typename, typename> class CachingPolicy, class ThreadingPolicy>
class default_branch : public node_impl<T>
{
public:
        node<T, CachingPolicy, ThreadingPolicy> l;      
        node<T, CachingPolicy, ThreadingPolicy> r;      
        typename operation<T>::t f;     
        
        default_branch(const typename operation<T>::t& f, const node<T, CachingPolicy, ThreadingPolicy>& l, const node<T, CachingPolicy, ThreadingPolicy>& r) : l(l), r(r), f(f) {}

        default_branch(const default_branch<T, CachingPolicy, ThreadingPolicy>& other) : l(other.l), r(other.r) , f(other.f) {}
        
        virtual ~default_branch() {}

        virtual std::unique_ptr<node_impl<T>> clone() const
        {
                return std::unique_ptr<default_branch<T, CachingPolicy, ThreadingPolicy>>(new default_branch<T, CachingPolicy, ThreadingPolicy>(*this));
        }

        virtual bool constant() const
        {
                return l.constant() && r.constant();
        }

        virtual T evaluate() const
        {
                return ThreadingPolicy::evaluate(f, l, r);
        }

        virtual node<T, CachingPolicy, ThreadingPolicy>& left()
        {
                return l;
        }

        virtual node<T, CachingPolicy, ThreadingPolicy>& right()
        {
                return r;
        }

        virtual void grow()
        {
                return;
        }
};

}

template<typename T, class ThreadingPolicy>
struct no_caching;

template<typename T, template<typename, typename> class CachingPolicy = no_caching, class ThreadingPolicy = sequential>
class node
{
        std::unique_ptr<detail::node_impl<T>> impl;             
        node<T, CachingPolicy, ThreadingPolicy> *parent; 

public:
        node(node<T, CachingPolicy, ThreadingPolicy> *parent = 0) : impl(nullptr), parent(parent) {}

        node(const node<T, CachingPolicy, ThreadingPolicy>& other) : impl(other.impl ? other.impl->clone() : nullptr), parent(other.parent) {}

        node<T, CachingPolicy, ThreadingPolicy>& operator=(const node<T, CachingPolicy, ThreadingPolicy>& other)
        {
                if(this != &other)
                {
                        impl = other.impl->clone();
                        parent = other.parent;

                        if(parent)
                        {
                                parent->grow();
                        }
                }

                return *this;
        }

        virtual ~node()
        {}

        node<T, CachingPolicy, ThreadingPolicy>& operator=(const T& t)
        {
                impl.reset(new detail::leaf<T>(t));

                if(parent)
                {
                        parent->grow();
                }

                return *this;
        }

        node<T, CachingPolicy, ThreadingPolicy>& operator=(const T* t)
        {
                impl.reset(new detail::leaf<T*>(t));

                if(parent)
                {
                        parent->grow();
                }

                return *this;
        }

        node<T, CachingPolicy, ThreadingPolicy>& operator=(const typename detail::operation<T>::t& f)
        {
                // Create a new branch with the passed operation and two nodes with this node as their parent.
                impl.reset(new typename CachingPolicy<T, ThreadingPolicy>::branch(f, node<T, CachingPolicy, ThreadingPolicy>(this), node<T, CachingPolicy, ThreadingPolicy>(this)));

                if(parent)
                {
                        parent->grow();
                }

                return *this;
        }

        node<T, CachingPolicy, ThreadingPolicy>& left()
        {
                return dynamic_cast<typename CachingPolicy<T, ThreadingPolicy>::branch*>(impl.get())->left();
        }

        node<T, CachingPolicy, ThreadingPolicy>& right()
        {
                return dynamic_cast<typename CachingPolicy<T, ThreadingPolicy>::branch*>(impl.get())->right();
        }

        bool constant() const
        {
                return impl ? impl->constant() : false;
        }

        T evaluate() const
        {
                return impl->evaluate();
        }

        void grow()
        {
                dynamic_cast<typename CachingPolicy<T, ThreadingPolicy>::branch*>(impl.get())->grow();

                if(parent)
                {
                        parent->grow();
                }
        }
};

template<typename T, class ThreadingPolicy>
struct no_caching
{
        class branch : public detail::default_branch<T, expression_tree::no_caching, ThreadingPolicy>
        {
        public:
                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)
                        : detail::default_branch<T, expression_tree::no_caching, ThreadingPolicy>(f, l, r) {}

                branch(const branch& o) : detail::default_branch<T, expression_tree::no_caching, ThreadingPolicy>(o) {}

                virtual ~branch() {}
        };
};

template<typename T, class ThreadingPolicy>
struct cache_on_evaluation
{
        class branch : public detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>
        {
                mutable bool cached;    
                mutable T value;                

                using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::f;
                using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::l;
                using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::r;
                using detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>::constant;

        public:
                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)
                        : detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>(f, l, r), cached(false) {}

                branch(const branch& o) : detail::default_branch<T, expression_tree::cache_on_evaluation, ThreadingPolicy>(o), cached(o.cached), value(o.value) {}

                virtual ~branch() {}

                virtual T evaluate() const
                {
                        if(cached) return value;

                        value = ThreadingPolicy::evaluate(f, l, r);

                        if(constant())
                        {
                                cached = true;
                        }

                        return value;
                }

                virtual void grow()
                {
                        cached = false;
                }
        };
};

template<typename T, class ThreadingPolicy>
struct cache_on_assignment
{
        class branch : public detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>
        {
                mutable bool cached;    
                mutable T value;                

                using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::f;
                using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::l;
                using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::r;
                using detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>::constant;

        public:
                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)
                        : detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>(f, l, r), cached(false) {}

                branch(const branch& o) : detail::default_branch<T, expression_tree::cache_on_assignment, ThreadingPolicy>(o), cached(o.cached), value(o.value) {}

                virtual ~branch() {}

                virtual T evaluate() const
                {
                        if(cached) return value;

                        return value = ThreadingPolicy::evaluate(f, l, r);
                }
                
                virtual void grow()
                {
                        if(constant())
                        {
                                // If this node is constant, cache its value now.
                                cached = true;
                                value = ThreadingPolicy::evaluate(f, l, r);
                        }
                        else
                        {
                                // One or both children are not constant. This node is then not constant.
                                cached = false;
                        }
                }
        };
};

template<typename T, template<typename, typename> class CachingPolicy = no_caching, class ThreadingPolicy = sequential>
class tree : public node<T, CachingPolicy, ThreadingPolicy>
{
public:
        virtual ~tree() {}

        node<T, CachingPolicy, ThreadingPolicy>& root()
        {
                return *this;
        }
};

}

#endif