functions.hpp

#ifndef INFRARED_FUNCTIONS_HPP
#define INFRARED_FUNCTIONS_HPP
 
/*
 * InfraRed ---  A generic engine for Boltzmann sampling over constraint networks
 * (C) Sebastian Will, 2018
 *
 * This file is part of the InfraRed source code.
 *
 * InfraRed provides a generic framework for tree decomposition-based
 * Boltzmann sampling over constraint networks
 */
 
#include <vector>
#include <unordered_map>
#include <memory>
#include <string>
#include <iterator>
#include <cassert>
#include <numeric>
 
#include "assignment.hpp"
#include "simple_map.hpp"
 
namespace ired {
 
    template<class FunValue, class EP>
    class FeatureNetwork;
 
    class Dependency {
    public:
        using var_idx_t = int;
 
        explicit
        Dependency(const std::vector<var_idx_t> &vars) : vars_(vars) {}
 
        const std::vector<var_idx_t> &
        vars() const {return vars_;}
 
        virtual
        ~Dependency() {}
 
    private:
        const std::vector<var_idx_t> vars_;
    };
 
    template<class FunValue=double>
    class Function : public Dependency {
    public:
        using self_t = Function<FunValue>;
        using base_t = self_t;
        using assignment_t = Assignment;
        using fun_value_t = FunValue;
 
        explicit
        Function(const std::vector<var_idx_t> &vars) : Dependency(vars) {}
 
        virtual
        fun_value_t
        operator () (const assignment_t &) const = 0;
 
        virtual
        bool
        guaranteed_zero(const assignment_t &a) const { return false; }
 
        virtual
        bool
        auto_materialize() const { return true; }
 
        virtual
        std::string
        name() const { return "Function"; }
 
        virtual
        ~Function() {}
    };
 
    template <class T>
    inline
    std::ostream & operator << (std::ostream &out, const Function<T> &f) {
        out << f.name() << "(";
        for (auto i : f.vars()) { out << i << ", "; }
        out << ") <"<<&f<<">";
        return out;
    }
 
    struct mapS {};
 
    struct simple_mapS {};
 
    struct vecS {};
 
    template<class FunValue, class T>
    struct container_selector {
        using type = T;
    };
 
    template<class FunValue>
    struct container_selector<FunValue,vecS> {
        //using type = std::vector<FunValue>;
        using type = typename vector_nbv_sel<FunValue>::type;
        static void init(type &x, size_t size, const FunValue &zero) {
            x.resize(size);
            std::fill(x.begin(),x.end(),zero);
        }
        static bool guaranteed_zero(const type &x, size_t i) {
            return false;
        }
        static FunValue get(const type &x, size_t i, const FunValue &zero) {
            assert(i<x.size());
            return x[i];
        }
        static void set(type &x,size_t i, const FunValue &v, const FunValue &zero) {x[i]=v;}
    };
 
    template<class FunValue>
    struct container_selector<FunValue,mapS> {
        using type = std::unordered_map<int,FunValue>;
        static void init(type &x, size_t size, const FunValue &zero) {
        }
        static const FunValue& get(const type &x, size_t i, const FunValue &zero) {
            auto it = x.find(i);
            if (it != x.end()) return it->second; else return zero;
        }
        static bool guaranteed_zero(const type &x, size_t i) {
            return x.find(i) == x.end();
        }
        static void set(type &x,size_t i, const FunValue &v, const FunValue &zero) {
            if (v!=zero) {
                x[i]=v;
            } else {
                x.erase(i); //erases key i if it exists
            }
        }
    };
 
    template<class FunValue>
    struct container_selector<FunValue,simple_mapS> {
        using type = SimpleMap<int,FunValue>;
        static void init(type &x, size_t size, const FunValue &zero) {
        }
        static const FunValue& get(const type &x, size_t i, const FunValue &zero) {
            auto it = x.find(i);
            if (it != x.end()) return it->second; else return zero;
        }
        static bool guaranteed_zero(const type &x, size_t i) {
            return x.find(i) == x.end();
        }
        static void set( type &x, size_t i, const FunValue &v, const FunValue &zero ) {
            if (v!=zero) {
                x.push_ascending(i,v);
            } else {
                // x.erase(i); //erases key i if it exists
            }
        }
    };
 
 
 
    template< class FunValue, class ContainerS = simple_mapS >
    class MaterializedFunction : public Function<FunValue> {
    public:
        using self_t = MaterializedFunction<FunValue,ContainerS>;
        using parent_t = Function<FunValue>;
        using base_t = typename parent_t::base_t;
 
        using var_idx_t = typename parent_t::var_idx_t;
        using assignment_t = typename parent_t::assignment_t;
        using fun_value_t = FunValue;
        using function_t = Function<fun_value_t>;
 
        using data_t = typename container_selector<FunValue,ContainerS>::type;
 
        template<class FeatureNetwork>
        MaterializedFunction(const std::vector<var_idx_t> &vars,
                             const FeatureNetwork &cn
                             )
            :
            parent_t(vars),
            domains_(extract_domains(cn.domains())),
            zero_(FeatureNetwork::evaluation_policy_t::zero()),
            name_("Message")
        {
            container_selector<FunValue,ContainerS>::init(data_, calc_size(), zero_);
        }
 
        template<class FeatureNetwork>
        MaterializedFunction(const function_t *function,
                             const FeatureNetwork &cn
                             )
            :
            parent_t(unique(function->vars())),
            domains_(extract_domains(cn.domains())),
            zero_(FeatureNetwork::evaluation_policy_t::zero()),
            name_(function->name())
        {
            using feature_network_t = FeatureNetwork;
 
            using ep = typename feature_network_t::evaluation_policy_t;
 
            container_selector<FunValue,ContainerS>::init(data_, calc_size(), zero_);
 
            auto a = Assignment(cn.domains());
 
            auto constraints = std::vector<const typename feature_network_t::constraint_t *>();
            auto functions = std::vector<const typename feature_network_t::function_t *> {function};
 
            auto initial_value = a.eval_determined(functions, ep()); //evaluate 0-ary functions
 
            auto it = a.make_iterator(this->vars(),
                                      cn,
                                      constraints,
                                      functions,
                                      initial_value
                                      );
 
            for(; ! it.finished() ; ++it ) {
                set( a, it.value() );
            }
        }
 
        fun_value_t
        operator () ( const assignment_t & a ) const override {
            return container_selector<FunValue,ContainerS>::get(data_, index(a), zero_);
        }
 
        void
        set( const assignment_t & a, const fun_value_t &val) {
            return container_selector<FunValue,ContainerS>::set(data_, index(a), val, zero_);
        }
 
        bool guaranteed_zero(const assignment_t &a) const override {
            return container_selector<FunValue,ContainerS>::guaranteed_zero(data_, index(a));
        }
 
        virtual
        bool
        auto_materialize() const override { return false; }
 
        virtual
        std::string
        name() const override { return "Materialized"+name_; }
 
        auto
        datasize() const {return data_.size();}
 
    private:
        FiniteDomainVector domains_;
        data_t data_;
        fun_value_t zero_;
        std::string name_;
 
        template<class T>
        auto unique( const std::vector<T> &xs ) {
            auto vec = xs;
            std::sort( vec.begin(), vec.end() );
            vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() );
            return vec;
        }
 
        auto
        extract_domains(const FiniteDomainVector &v) {
            auto ds = FiniteDomainVector();
            for ( auto x: this->vars() ) {
                ds.push_back(v[x]);
            }
            return ds;
        }
 
 
        auto
        index( const assignment_t & a ) const {
            size_t x = 0;
            size_t i = 0;
            auto vars = this->vars();
            for ( size_t i=0; i < domains_.size(); i++) {
                x *= domains_[i].size();
                x += a[vars[i]] - domains_[i].lb();
            }
            return x;
        }
 
        auto
        calc_size() const {
            return std::accumulate( domains_.begin(), domains_.end(), 1,
                       [](int acc, const FiniteDomain &x) { return x.size()*acc; } );
        }
    };
 
    using Constraint = Function<bool>;
}
 
#endif