Neighbourhood.h

Go to the documentation of this file.

#ifndef COMMA_PROJECT_FIRST_ORDER_NEIGHBOURHOOD_H
#define COMMA_PROJECT_FIRST_ORDER_NEIGHBOURHOOD_H
 
/*
 * CoMMA
 *
 * Copyright © 2024 ONERA
 *
 * Authors: Nicolas Lantos, Alberto Remigi, and Riccardo Milani
 * Contributors: Karim Anemiche
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */
 
#include <algorithm>
#include <cassert>
#include <deque>
#include <memory>
#include <queue>
#include <set>
#include <unordered_set>
#include <vector>
 
#include "CoMMA/Util.h"
 
namespace comma {
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class Neighbourhood {
#if 0
Some remarks about the implementation. All the work is done in the function "update",
hence that is where we have to focus on. There are only two constraints for the
returned object: it should be an iterable, and the content (the indices of the neighbours)
must be ordered using their weights. An ordered set of pair of (index, weight) with
CustomPairGreaterFunctor as comparator would not work as because we want unique indices
and that would have been quite hard to achieve even if defining a custom operator==,
have a look here, https://stackoverflow.com/a/1114862
We still use sets, but we have an extra check before inserting whether there already is
a pair with the same index.
#endif
 
public:
  using CoMMAPairType = std::pair<CoMMAIndexType, CoMMAWeightType>;
  using CoMMASetOfPairType =
    std::set<CoMMAPairType, CustomPairGreaterFunctor<CoMMAPairType>>;
  using CoMMAPairFindFirstBasedType = PairFindFirstBasedFunctor<CoMMAPairType>;
  using CandidatesContainerType = std::deque<CoMMAIndexType>;
  using ContainerIndexType = std::vector<CoMMAIndexType>;
  using ContainerIndexConstIt = typename ContainerIndexType::const_iterator;
 
  Neighbourhood(
    const std::unordered_set<CoMMAIndexType> &s_neighbours_of_seed,
    const std::vector<CoMMAWeightType> &weights
  ) :
    _s_neighbours_of_seed(std::move(s_neighbours_of_seed)),
    _weights(weights),
    _s_fc(),
    _candidates() {}
 
  Neighbourhood(
    const Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType> &other
  ) = default;
 
  virtual ~Neighbourhood() = default;
 
  inline void update(
    const CoMMAIndexType new_fc, const ContainerIndexType &new_neighbours
  ) {
    update_it(new_fc, new_neighbours.cbegin(), new_neighbours.cend());
  }
 
  virtual void update_it(
    const CoMMAIndexType new_fc,
    ContainerIndexConstIt neighs_begin,
    ContainerIndexConstIt neighs_end
  ) = 0;
 
  inline const CandidatesContainerType &get_candidates() const {
    return this->_candidates;
  }
 
protected:
  const std::unordered_set<CoMMAIndexType> _s_neighbours_of_seed;
 
  const std::vector<CoMMAWeightType> &_weights;
 
  std::unordered_set<CoMMAIndexType> _s_fc;
 
  CandidatesContainerType _candidates;
 
  inline void extract_and_update_candidates(
    const CoMMASetOfPairType &candidates_w_weights
  ) {
    for (const auto &[idx, w] : candidates_w_weights)
      this->_candidates.push_back(idx);
  }
};
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class Neighbourhood_Extended :
  public Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType> {
public:
  using NeighbourhoodBaseType =
    Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
  using typename NeighbourhoodBaseType::CoMMAPairType;
  using typename NeighbourhoodBaseType::CoMMASetOfPairType;
  using typename NeighbourhoodBaseType::CoMMAPairFindFirstBasedType;
  using typename NeighbourhoodBaseType::ContainerIndexType;
  using typename NeighbourhoodBaseType::ContainerIndexConstIt;
 
  Neighbourhood_Extended(
    const std::unordered_set<CoMMAIndexType> &s_neighbours_of_seed,
    const std::vector<CoMMAWeightType> &weights
  ) :
    Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>(
      s_neighbours_of_seed, weights
    ) {}
 
  Neighbourhood_Extended(
    const Neighbourhood_Extended<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>
      &other
  ) = default;
 
  ~Neighbourhood_Extended() override = default;
 
  void update_it(
    const CoMMAIndexType new_fc,
    ContainerIndexConstIt neighs_begin,
    ContainerIndexConstIt neighs_end
  ) override {
    // Add new_fc to current CC and remove it from previous neighbourhoods
    this->_s_fc.insert(new_fc);
    auto new_fc_ptr =
      std::find(this->_candidates.begin(), this->_candidates.end(), new_fc);
    if (new_fc_ptr != this->_candidates.end())
      this->_candidates.erase(new_fc_ptr);
 
    // Compute the set of direct neighbours allowed by original
    // neighbourhood-order
    CoMMASetOfPairType neighs;
    for (auto it_fc = neighs_begin; it_fc != neighs_end; ++it_fc) {
      if ((std::find(this->_candidates.begin(), this->_candidates.end(), *it_fc)
           == this->_candidates.end())
          && (this->_s_fc.count(*it_fc) == 0)
          && (this->_s_neighbours_of_seed.count(*it_fc) > 0)) {
        // If not yet in the FON, not yet in the coarse cell and among the
        // allowed neighbours, insert
        neighs.emplace(*it_fc, this->_weights[*it_fc]);
      }
    }
    // Just add new candidates at the back. This will leave candidates closer to
    // the original seed at the top, hence giving them a slightly higher
    // priority
    this->extract_and_update_candidates(neighs);
  }
};
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class Neighbourhood_Pure_Front :
  public Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType> {
public:
  using NeighbourhoodBaseType =
    Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
  using typename NeighbourhoodBaseType::CoMMAPairType;
  using typename NeighbourhoodBaseType::CoMMASetOfPairType;
  using typename NeighbourhoodBaseType::CoMMAPairFindFirstBasedType;
  using typename NeighbourhoodBaseType::ContainerIndexType;
  using typename NeighbourhoodBaseType::ContainerIndexConstIt;
 
  Neighbourhood_Pure_Front(
    const std::unordered_set<CoMMAIndexType> &s_neighbours_of_seed,
    const std::vector<CoMMAWeightType> &weights,
    CoMMAIntType dimension
  ) :
    Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>(
      s_neighbours_of_seed, weights
    ),
    _q_neighs_w_weights(),
    _dimension(dimension) {}
 
  Neighbourhood_Pure_Front(const Neighbourhood_Pure_Front<
                           CoMMAIndexType,
                           CoMMAWeightType,
                           CoMMAIntType> &other) = default;
 
  ~Neighbourhood_Pure_Front() override = default;
 
  void update_it(
    const CoMMAIndexType new_fc,
    ContainerIndexConstIt neighs_begin,
    ContainerIndexConstIt neighs_end
  ) override {
    this->_candidates.clear();
    // Add new_fc to current CC and remove it from previous neighbourhoods
    this->_s_fc.insert(new_fc);
    for (auto &queue : this->_q_neighs_w_weights) {
      // There is erase_if for sets in C++20
      // erase_if(queue, [&new_fc](const CoMMAPairType &p){return p.first ==
      // new_fc;});
      auto it = std::find_if(
        queue.begin(), queue.end(), CoMMAPairFindFirstBasedType(new_fc)
      );
      //[&new_fc](const CoMMAPairType &p){return p.first == new_fc;});
      if (it != queue.end()) queue.erase(it);
    }
 
    // Compute the set of direct neighbours allowed by original
    // neighbourhood-order
    CoMMASetOfPairType curr_set = CoMMASetOfPairType();
    for (auto it_fc = neighs_begin; it_fc != neighs_end; ++it_fc) {
      if ((this->_s_fc.count(*it_fc) == 0)
          && (this->_s_neighbours_of_seed.count(*it_fc) > 0)) {
        // If not yet in coarse cell and among the allowed neighbours, insert
        curr_set.emplace(*it_fc, this->_weights[*it_fc]);
      }
    }
 
    this->_q_neighs_w_weights.push_front(curr_set);
 
    // Now, see which neighbours to return. Here is the strategy:
    // If most recent list is not empty, return it. If not, check the oldest
    // list: if not empty return it, otherwise check the previous list. If
    // empty, check the second oldest, and so on... We grant ourselves one
    // exception...
    if (this->_q_neighs_w_weights.size()
        <= static_cast<decltype(this->_q_neighs_w_weights.size())>(
          this->_dimension
        )) {
      // If at the (very) beginning of the agglomeration, still consider every
      // possible neighbour. This will allow to obtain nice quads from quads
      // TODO[RM]: I think this workaround is needed because we are not able to
      // compute exactly the AR; if we ever we will be able we should try to
      // remove it
      for (auto prev_q = this->_q_neighs_w_weights.begin() + 1;
           prev_q != this->_q_neighs_w_weights.end();
           ++prev_q)
        curr_set.insert(prev_q->begin(), prev_q->end());
      this->extract_and_update_candidates(curr_set);
    } else {
      auto cur_front = decltype(this->_q_neighs_w_weights.size()){0};
      auto cur_back = decltype(this->_q_neighs_w_weights.size()
      ){this->_q_neighs_w_weights.size() - 1};
      while (cur_front <= cur_back) {
        // typename decltype(this->_q_neighs_w_weights)::iterator it =
        auto it = this->_q_neighs_w_weights.begin() + (cur_front++);
        if (!it->empty()) {
          this->extract_and_update_candidates(*it);
          break;
        }
        it = this->_q_neighs_w_weights.begin() + (cur_back--);
        if (!it->empty()) {
          this->extract_and_update_candidates(*it);
          break;
        }
      }
    }
  }
 
  inline const CoMMASetOfPairType &get_neighbours_by_level(
    const CoMMAIntType lvl
  ) const {
    assert(
      lvl >= 0
      && lvl < static_cast<CoMMAIntType>(this->_q_neighs_w_weights.size())
    );
    return this->_q_neighs_w_weights[lvl];
  }
 
protected:
  std::deque<CoMMASetOfPairType> _q_neighs_w_weights;
 
  CoMMAIntType _dimension;
};
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class NeighbourhoodCreator {
public:
  using NeighbourhoodBaseType =
    Neighbourhood<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
 
  NeighbourhoodCreator() = default;
 
  virtual ~NeighbourhoodCreator() = default;
 
  virtual std::shared_ptr<NeighbourhoodBaseType> create(
    const std::unordered_set<CoMMAIndexType> &s_neighbours_of_seed,
    const std::vector<CoMMAWeightType> &priority_weights,
    const CoMMAIntType dimension
  ) const = 0;
 
  virtual std::shared_ptr<NeighbourhoodBaseType> clone(
    std::shared_ptr<NeighbourhoodBaseType> other
  ) const = 0;
};
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class NeighbourhoodExtendedCreator :
  public NeighbourhoodCreator<CoMMAIndexType, CoMMAWeightType, CoMMAIntType> {
public:
  using CreatorBaseType =
    NeighbourhoodCreator<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
  using typename CreatorBaseType::NeighbourhoodBaseType;
  using NeighbourhoodDerivedType =
    Neighbourhood_Extended<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
 
  NeighbourhoodExtendedCreator() :
    CreatorBaseType() {}
 
  ~NeighbourhoodExtendedCreator() override = default;
 
  inline std::shared_ptr<NeighbourhoodBaseType> create(
    const std::unordered_set<CoMMAIndexType> &s_neighbours_of_seed,
    const std::vector<CoMMAWeightType> &priority_weights,
    const CoMMAIntType dimension
  ) const override {
    CoMMAUnused(dimension);
    return std::make_shared<NeighbourhoodDerivedType>(
      s_neighbours_of_seed, priority_weights
    );
  }
 
  inline std::shared_ptr<NeighbourhoodBaseType> clone(
    std::shared_ptr<NeighbourhoodBaseType> other
  ) const override {
    // Using copy-constructor
    return std::make_shared<NeighbourhoodDerivedType>(
      *std::dynamic_pointer_cast<NeighbourhoodDerivedType>(other)
    );
  }
};
 
template<
  typename CoMMAIndexType,
  typename CoMMAWeightType,
  typename CoMMAIntType>
class NeighbourhoodPureFrontCreator :
  public NeighbourhoodCreator<CoMMAIndexType, CoMMAWeightType, CoMMAIntType> {
public:
  using CreatorBaseType =
    NeighbourhoodCreator<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
  using typename CreatorBaseType::NeighbourhoodBaseType;
  using NeighbourhoodDerivedType =
    Neighbourhood_Pure_Front<CoMMAIndexType, CoMMAWeightType, CoMMAIntType>;
 
  NeighbourhoodPureFrontCreator() :
    CreatorBaseType() {}
 
  ~NeighbourhoodPureFrontCreator() override = default;
 
  inline std::shared_ptr<NeighbourhoodBaseType> create(
    const std::unordered_set<CoMMAIndexType> &s_neighbours_of_seed,
    const std::vector<CoMMAWeightType> &priority_weights,
    const CoMMAIntType dimension
  ) const override {
    return std::make_shared<NeighbourhoodDerivedType>(
      s_neighbours_of_seed, priority_weights, dimension
    );
  }
 
  inline std::shared_ptr<NeighbourhoodBaseType> clone(
    std::shared_ptr<NeighbourhoodBaseType> other
  ) const override {
    // Using copy-constructor
    return std::make_shared<NeighbourhoodDerivedType>(
      *std::dynamic_pointer_cast<NeighbourhoodDerivedType>(other)
    );
  }
};
 
}  // end namespace comma
 
#endif  // COMMA_PROJECT_FIRST_ORDER_NEIGHBOURHOOD_H