Program Listing for File hugenholtz.hpp

↰ Return to documentation for file (SeQuant/core/hugenholtz.hpp)

//
// Created by Eduard Valeyev on 2019-02-14.
//

#ifndef SEQUANT_HUGENHOLTZ_HPP
#define SEQUANT_HUGENHOLTZ_HPP

namespace sequant {

template <typename Edge, typename EdgeEquality>
class HugenholtzVertex {
  using Group = std::pair<Edge, container::set<size_t>>;

 public:
  HugenholtzVertex() = default;
  HugenholtzVertex(const HugenholtzVertex&) = default;
  HugenholtzVertex(HugenholtzVertex&&) = default;

  template <typename EdgeRange, typename = std::enable_if_t<!std::is_same_v<
                                    HugenholtzVertex, std::decay_t<EdgeRange>>>>
  HugenholtzVertex(EdgeRange&& edge_range, EdgeEquality equals = EdgeEquality{})
      : equals_(std::move(equals)) {
    const auto num_edges = ranges::size(edge_range);
    edge_to_group_.reserve(num_edges);

    // compute the groups
    size_t edge_idx = 0;
    ranges::for_each(edge_range, [this, &edge_idx](const Edge& edge) {
      const auto grp_it = std::find_if(
          begin(groups_), end(groups_),
          [&edge, this](const Group& grp) { return equals_(grp.first, edge); });
      if (grp_it == end(groups_)) {  // no group yet? create
        groups_.emplace_back(
            std::make_pair(edge, typename Group::second_type{edge_idx}));
        edge_to_group_.push_back(groups_.size() - 1);
      } else {
        auto result = grp_it->second.insert(edge_idx);
        assert(result.second);
        edge_to_group_.push_back(grp_it - begin(groups_));
      }
      ++edge_idx;
    });
  }

  auto num_edges() const { return edge_to_group_.size(); }

  auto num_groups() const { return groups_.size(); }

  auto num_nonempty_groups() const {
    return std::accumulate(begin(groups_), end(groups_), size_t(0),
                           [](const size_t& left, const Group& right) {
                             return left + (right.second.empty() ? 0 : 1);
                           });
  }

  const auto& group(size_t edge_idx) const {
    const auto grp_idx = edge_to_group_.at(edge_idx);
    return groups_.at(grp_idx);
  }

  const auto& group_at(size_t grp_idx) const { return groups_.at(grp_idx); }

  const size_t group_size(size_t edge_idx) const {
    const auto result = group(edge_idx).second.size();
    assert(result > 0);
    return result;
  }

  void erase(size_t edge_idx, const Edge& edge) {
    // preconditions
    const auto grp_idx = edge_to_group_.at(edge_idx);
    Group& grp = groups_.at(grp_idx);
    assert(std::find_if(begin(groups_), end(groups_),
                        [this, &edge](const Group& grp) {
                          return equals_(grp.first, edge);
                        }) != end(groups_));
    assert(grp.second.find(edge_idx) != end(grp.second));
    assert(equals_(grp.first, edge));

    // remove the edge from the map and update the groups
    edge_to_group_.erase(edge_to_group_.begin() + edge_idx);
    grp.second.erase(edge_idx);
    for (auto&& g : groups_) {
      ranges::for_each(g.second, [&edge_idx](size_t& e) {
        if (e >= edge_idx) {
          assert(e > 0);
          --e;
        }
      });
    }
    // groups are never erased!
  }

  void insert(const size_t edge_idx, const Edge& edge) {
    // preconditions
    if (edge_idx > edge_to_group_.size()) {
      throw std::out_of_range(
          "HugenholtzVertex::insert : can only insert or append");
    }

    auto grp_it = std::find_if(
        begin(groups_), end(groups_),
        [this, &edge](const Group& grp) { return equals_(grp.first, edge); });

    // update existing edge indices if inserting in the middle
    if (edge_idx < edge_to_group_.size()) {
      for (auto&& g : groups_) {
        ranges::for_each(g.second, [&edge_idx](size_t& e) {
          if (e >= edge_idx) {
            ++e;
          }
        });
      }
    }

    // now update the group with the new index and update the edge->grp map
    if (grp_it == end(groups_)) {  // no group yet? create
      groups_.emplace_back(
          std::make_pair(edge, typename Group::second_type{edge_idx}));
      edge_to_group_.insert(edge_to_group_.begin() + edge_idx,
                            groups_.size() - 1);
    } else {  // just insert but keep the group indices sorted
      auto result = grp_it->second.insert(edge_idx);
      assert(result.second);
      edge_to_group_.insert(edge_to_group_.begin() + edge_idx,
                            grp_it - groups_.begin());
    }
  }

 private:
  container::svector<size_t> edge_to_group_;  // maps edge index to group idx
  container::svector<Group>
      groups_;  // group = Edge + (sorted) indices of the equivalent edges
  EdgeEquality equals_;
};

}  // namespace sequant

#endif  // SEQUANT_HUGENHOLTZ_HPP