expressions.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c)
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_EXPRESSIONS_HPP
#define PAAL_EXPRESSIONS_HPP

#include "paal/lp/ids.hpp"
#include "paal/utils/floating.hpp"
#include "paal/utils/functors.hpp"
#include "paal/utils/print_collection.hpp"
#include "paal/utils/pretty_stream.hpp"

#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/algorithm/count_if.hpp>

#include <functional>
#include <unordered_map>

namespace paal {
namespace lp {

namespace {
struct linear_expression_traits {
    static const utils::compare<double> CMP;
};

const utils::compare<double> linear_expression_traits::CMP = utils::compare<double>();
}

class linear_expression {
    typedef std::unordered_map<col_id, double> Elements;
    typedef Elements::const_iterator ExprIter;

  public:
    linear_expression() {}

    linear_expression(col_id col, double coef = 1.) {
        m_coefs.emplace(col, coef);
    }

    linear_expression &operator+=(const linear_expression &expr) {
        join_expression(expr, utils::plus{});
        return *this;
    }

    linear_expression &operator-=(const linear_expression &expr) {
        join_expression(expr, utils::minus{});
        return *this;
    }

    linear_expression &operator*=(double val) {
        for (auto &elem : m_coefs) {
            elem.second *= val;
        }
        return *this;
    }

    linear_expression &operator/=(double val) { return operator*=(1. / val); }

    double get_coefficient(col_id col) const {
        auto elem = m_coefs.find(col);
        if (elem != m_coefs.end()) {
            return elem->second;
        } else {
            return 0.;
        }
    }

    const Elements &get_elements() const { return m_coefs; }

    int non_zeros() const {
        return boost::count_if(m_coefs, [](std::pair<col_id, double> x) {
            return !linear_expression_traits::CMP.e(x.second, 0);
        });
    }

  private:
    template <typename Operation>
    void join_expression(const linear_expression &expr, Operation op) {
        for (auto new_elem : expr.m_coefs) {
            auto elem = m_coefs.find(new_elem.first);
            if (elem == m_coefs.end()) {
                new_elem.second = op(0., new_elem.second);
                m_coefs.insert(new_elem);
            } else {
                elem->second = op(elem->second, new_elem.second);
            }
        }
    }

    Elements m_coefs;
};

namespace detail {
inline std::string col_id_to_string(col_id col) {
    return " x_" + std::to_string(col.get());
}

template <typename Stream, typename PrintCol>
void print_expression(Stream &o, const linear_expression &expr,
                      PrintCol print_col) {
    print_collection(o, expr.get_elements() |
                            boost::adaptors::transformed(
                                [&](std::pair<col_id, double> col_and_val) {
        return pretty_to_string(col_and_val.second) +
               print_col(col_and_val.first);
    }),
                     " + ");
}
};

template <typename Stream>
Stream &operator<<(Stream &o, const linear_expression &expr) {
    detail::print_expression(o, expr, detail::col_id_to_string);
    return o;
}

inline linear_expression operator+(linear_expression expr_left,
                                   const linear_expression &expr_right) {
    expr_left += expr_right;
    return expr_left;
}

inline linear_expression operator-(linear_expression expr_left,
                                   const linear_expression &expr_right) {
    expr_left -= expr_right;
    return expr_left;
}

inline linear_expression operator*(linear_expression expr, double val) {
    expr *= val;
    return expr;
}

inline linear_expression operator*(double val, const linear_expression &expr) {
    return expr * val;
}

inline linear_expression operator/(linear_expression expr, double val) {
    expr /= val;
    return expr;
}

inline linear_expression operator-(const linear_expression &expr) {
    return expr * (-1.);
}

} // lp
} // paal

#endif // PAAL_EXPRESSIONS_HPP