<commit_before>#ifndef _SDD_HOM_SUM_HH_
#define _SDD_HOM_SUM_HH_

#include <algorithm>  // all_of, equal
#include <initializer_list>

#include <boost/container/flat_set.hpp>

#include "sdd/dd/definition.hh"
#include "sdd/hom/context_fwd.hh"
#include "sdd/hom/definition_fwd.hh"
#include "sdd/hom/identity.hh"

namespace sdd { namespace hom {

/*-------------------------------------------------------------------------------------------*/

/// @cond INTERNAL_DOC

/// @brief Sum homomorphism.
template <typename C>
class sum
{
public:

  /// @brief The set of homomorphism operands
  typedef boost::container::flat_set<homomorphism<C>> operands_type;

private:

  const operands_type operands_;

public:

  /// @brief Constructor.
  sum(operands_type&& operands)
    : operands_(std::move(operands))
  {
  }

  /// @brief Evaluation.
  SDD<C>
  operator()(context<C>& cxt, const SDD<C>& x)
  const
  {
    sum_builder<C, SDD<C>> sum_operands(operands_.size());
    for (const auto& op : operands_)
    {
      sum_operands.add(op(cxt, x));
    }
    return sdd::sum(cxt.sdd_context(), std::move(sum_operands));
  }

  /// @brief Skip variable predicate.
  bool
  skip(const typename C::Variable& v)
  const noexcept
  {
    return std::all_of( operands_.begin(), operands_.end()
                      , [&](const homomorphism<C>& h){return h.skip(v);});
  }

  const operands_type&
  operands()
  const noexcept
  {
    return operands_;
  }
};

/*-------------------------------------------------------------------------------------------*/

/// @brief Equality of two Sum homomorphisms.
/// @related Sum
template <typename C>
inline
bool
operator==(const sum<C>& lhs, const sum<C>& rhs)
noexcept
{
  return lhs.operands().size() == rhs.operands().size()
     and std::equal(lhs.operands().begin(), lhs.operands().end(), rhs.operands().begin());
}

/// @endcond

/*-------------------------------------------------------------------------------------------*/

/// @brief Create the Sum homomorphism.
/// @related homomorphism
template <typename C, typename InputIterator>
homomorphism<C>
Sum(InputIterator begin, InputIterator end)
{
  const std::size_t size = std::distance(begin, end);

  if (size == 0)
  {
    return Id<C>();
  }

  typename sum<C>::operands_type operands;
  operands.reserve(size);

  for (; begin != end; ++begin)
  {
    operands.insert(*begin);
  }

  if (operands.size() == 1)
  {
    return *operands.begin();
  }
  else
  {
    return homomorphism<C>::create(internal::mem::construct<sum<C>>(), std::move(operands));
  }
}

/*-------------------------------------------------------------------------------------------*/

/// @brief Create the Sum homomorphism.
/// @related homomorphism
template <typename C>
homomorphism<C>
Sum(std::initializer_list<homomorphism<C>> operands)
{
  return Sum<C>(operands.begin(), operands.end());
}

/*-------------------------------------------------------------------------------------------*/

}} // namespace sdd::hom

namespace std {

/*-------------------------------------------------------------------------------------------*/

/// @cond INTERNAL_DOC

/// @brief Hash specialization for sdd::hom::sum.
template <typename C>
struct hash<sdd::hom::sum<C>>
{
  std::size_t
  operator()(const sdd::hom::sum<C>& s)<commit_msg>Optimize sum at creation.<commit_after>#ifndef _SDD_HOM_SUM_HH_
#define _SDD_HOM_SUM_HH_

#include <algorithm>  // all_of, copy, equal
#include <initializer_list>
#include <iosfwd>
#include <unordered_map>
#include <vector>

#include <boost/container/flat_set.hpp>

#include "sdd/dd/definition.hh"
#include "sdd/hom/context_fwd.hh"
#include "sdd/hom/definition_fwd.hh"
#include "sdd/hom/identity.hh"
#include "sdd/hom/local.hh"

namespace sdd { namespace hom {

/*-------------------------------------------------------------------------------------------*/

/// @cond INTERNAL_DOC

/// @brief Sum homomorphism.
template <typename C>
class sum
{
public:

  /// @brief The set of homomorphism operands
  typedef boost::container::flat_set<homomorphism<C>> operands_type;

private:

  const operands_type operands_;

public:

  /// @brief Constructor.
  sum(operands_type&& operands)
    : operands_(std::move(operands))
  {
  }

  /// @brief Evaluation.
  SDD<C>
  operator()(context<C>& cxt, const SDD<C>& x)
  const
  {
    sum_builder<C, SDD<C>> sum_operands(operands_.size());
    for (const auto& op : operands_)
    {
      sum_operands.add(op(cxt, x));
    }
    return sdd::sum(cxt.sdd_context(), std::move(sum_operands));
  }

  /// @brief Skip variable predicate.
  bool
  skip(const typename C::Variable& v)
  const noexcept
  {
    return std::all_of( operands_.begin(), operands_.end()
                      , [&](const homomorphism<C>& h){return h.skip(v);});
  }

  const operands_type&
  operands()
  const noexcept
  {
    return operands_;
  }
};

/*-------------------------------------------------------------------------------------------*/

/// @brief Equality of two sum.
/// @related sum
template <typename C>
inline
bool
operator==(const sum<C>& lhs, const sum<C>& rhs)
noexcept
{
  return lhs.operands().size() == rhs.operands().size()
     and std::equal(lhs.operands().begin(), lhs.operands().end(), rhs.operands().begin());
}

/// @related sum
template <typename C>
std::ostream&
operator<<(std::ostream& os, const sum<C>& s)
{
  os << "(";
  std::copy( s.operands().begin(), std::prev(s.operands().end())
           , std::ostream_iterator<homomorphism<C>>(os, " + "));
  return os << *std::prev(s.operands().end()) << ")";
}

/*-------------------------------------------------------------------------------------------*/

/// @brief Help optimize an union's operands.
template <typename C>
struct sum_builder_helper
{
  typedef void result_type;
  typedef typename sum<C>::operands_type operands_type;
  typedef std::vector<homomorphism<C>> hom_list_type;
  typedef std::unordered_map<typename C::Variable, hom_list_type> locals_type;

  /// @brief Flatten nested sums.
  void
  operator()( const sum<C>& s
            , const homomorphism<C>& h, operands_type& operands, locals_type& locals)
  const
  {
    for (const auto& op : s.operands())
    {
      apply_visitor(*this, op->data(), op, operands, locals);
    }
  }

  /// @brief Regroup locals.
  void
  operator()( const local<C>& l
            , const homomorphism<C>& h, operands_type& operands, locals_type& locals)
  const
  {
    auto insertion = locals.emplace(l.variable(), hom_list_type());
    insertion.first->second.emplace_back(l.hom());
  }

  /// @brief Insert normally all other operands.
  template <typename T>
  void
  operator()(const T&, const homomorphism<C>& h, operands_type& operands, locals_type&)
  const
  {
    operands.insert(h);
  }

};

/// @endcond

/*-------------------------------------------------------------------------------------------*/

/// @brief Create the Sum homomorphism.
/// @related homomorphism
template <typename C, typename InputIterator>
homomorphism<C>
Sum(InputIterator begin, InputIterator end)
{
  const std::size_t size = std::distance(begin, end);

  if (size == 0)
  {
    return Id<C>();
  }

  typename sum<C>::operands_type operands;
  operands.reserve(size);

  sum_builder_helper<C> sbv;
  typename sum_builder_helper<C>::locals_type locals;
  for (; begin != end; ++begin)
  {
    apply_visitor(sbv, (*begin)->data(), *begin, operands, locals);
  }

  // insert remaining locals
  for (const auto& l : locals)
  {
    operands.insert(Local<C>(l.first, Sum<C>(l.second.begin(), l.second.end())));
  }

  if (operands.size() == 1)
  {
    return *operands.begin();
  }
  else
  {
    operands.shrink_to_fit();
    return homomorphism<C>::create(internal::mem::construct<sum<C>>(), std::move(operands));
  }
}

/*-------------------------------------------------------------------------------------------*/

/// @brief Create the Sum homomorphism.
/// @related homomorphism
template <typename C>
homomorphism<C>
Sum(std::initializer_list<homomorphism<C>> operands)
{
  return Sum<C>(operands.begin(), operands.end());
}

/*-------------------------------------------------------------------------------------------*/

}} // namespace sdd::hom

namespace std {

/*-------------------------------------------------------------------------------------------*/

/// @cond INTERNAL_DOC

/// @brief Hash specialization for sdd::hom::sum.
template <typename C>
struct hash<sdd::hom::sum<C>>
{
  std::size_t
  operator()(const sdd::hom::sum<C>& s)
{'fraction_non_alphanumeric': 0.28509133765468475, 'fraction_numerical': 0.0004714201532115498, 'mean_word_length': 2.1244477172312224, 'pattern_counts': {'":': 0, '<': 95, '<?xml version=': 0, '>': 90, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1493804', 'n_tokens_mistral': 2668, 'n_tokens_neox': 2582, 'n_words': 566}