algorithm.hpp

Go to the documentation of this file.

#pragma once
 
#include <algorithm>
#include <array>
#include <fmt/ostream.h>
#include <functional>
#include <iterator>
#include <set>
#include <type_traits>
#include <utility>
 
namespace precice::utils {

template <class InputIt1, class InputIt2, class OutputIt>
void set_intersection_indices(InputIt1 ref1, InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
  while (first1 != last1 && first2 != last2) {
    if (*first1 < *first2) {
      ++first1;
    } else {
      if (!(*first2 < *first1)) {
        *d_first++ = std::distance(ref1, first1++); // *first1 and *first2 are equivalent.
      }
      ++first2;
    }
  }
}

template <typename... Elements>
auto make_array(Elements &&...elements) -> std::array<typename std::common_type<Elements...>::type, sizeof...(Elements)>
{
  return {std::forward<Elements>(elements)...};
}

template <typename Container, typename BinaryPredicate = std::equal_to<typename Container::value_type>>
bool unique_elements(const Container &c, BinaryPredicate p = {})
{
  // This algorithm runs on small containers, so the O(n^2) does not hurt.
  auto cbegin = c.begin();
  auto cend   = c.end();
  // An empty set has unique elements
  if (cbegin == cend) {
    return true;
  }
  auto cstart = cbegin + 1;
  for (; cstart < cend; ++cbegin, ++cstart) {
    if (std::find_if(cstart, cend,
                     [&p, cbegin](const typename Container::value_type &v) -> bool {
                       return p(*cbegin, v);
                     }) != cend) {
      return false;
    }
  }
  return true;
}

template <class InputIter, class ElementType>
void intersperse(InputIter first, InputIter last, const ElementType &elem, std::ostream &out)
{
  if (first == last)
    return;
 
  out << *first++;
  for (; first != last; ++first) {
    out << elem << *first;
  }
}

template <class InputIt1, class InputIt2>
std::pair<InputIt1, InputIt2>
mismatch(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
{
  while (first1 != last1 && first2 != last2 && *first1 == *first2) {
    ++first1, ++first2;
  }
  return std::make_pair(first1, first2);
}

template <typename InputIter>
struct RangePreview {
  using Size = typename std::iterator_traits<InputIter>::difference_type;
  Size      n;
  InputIter begin;
  InputIter end;
 
  RangePreview(Size n, InputIter begin, InputIter end)
      : n(n), begin(begin), end(end) {}
 
  void print(std::ostream &out) const
  {
    if (begin == end) {
      out << "<Empty Range>";
      return;
    }
 
    out << '[';
 
    if (n == 0) {
      out << " ... ";
    } else {
      auto              dist = std::distance(begin, end);
      const std::string sep{", "};
      if (dist <= n * 2) {
        intersperse(begin, end, sep, out);
      } else {
        auto last1 = begin;
        std::advance(last1, n);
        intersperse(begin, last1, sep, out);
        out << sep << "... " << sep;
        auto first2 = begin;
        std::advance(first2, dist - n);
        intersperse(first2, end, sep, out);
      }
    }
 
    auto mm = std::minmax_element(begin, end);
    out << "] min:" << *mm.first << " max:" << *mm.second;
  }
};

template <typename Iter>
std::ostream &operator<<(std::ostream &out, const RangePreview<Iter> &rp)
{
  rp.print(out);
  return out;
}

template <typename Range, typename Iter = typename Range::const_iterator, typename Size = typename std::iterator_traits<Iter>::difference_type>
const RangePreview<Iter> previewRange(Size n, const Range &range)
{
  return {n, std::begin(range), std::end(range)};
}

template <typename T, typename Index, size_t n>
auto reorder_array(const std::array<Index, n> &order, const std::array<T, n> &elements) -> std::array<T, n>
{
  static_assert(n > 0, "Reordering nothing is pointless");
  std::array<T, n> reordered;
  for (std::size_t i = 0; i < n; ++i) {
    reordered[i] = elements[order[i]];
  }
  return reordered;
}
 
template <class InputIt, class Size, class InOutIt>
void add_n(InputIt first, Size count, InOutIt result)
{
  std::transform(first, std::next(first, count), result, result, std::plus{});
}

template <class InputIt, class Unary>
void for_each_unique(InputIt first, InputIt last, Unary func)
{
  using Inner = std::remove_cv_t<std::remove_reference_t<decltype(*first)>>;
  std::set<Inner> seen;
  std::for_each(first, last, [&seen, &func](const auto &elem) {
    if (seen.count(elem) == 0) {
      seen.insert(elem);
      func(elem);
    }
  });
}

template <class InputIt, class Predicate>
std::pair<InputIt, InputIt> find_first_range(InputIt first, InputIt last, Predicate p)
{
  auto firstMatch = std::find_if(first, last, p);
  if (firstMatch == last) { // nothing found
    return {last, last};
  }
  auto trailing = firstMatch;
  auto next     = std::next(firstMatch);
  while (next != last && p(*next)) {
    ++trailing;
    ++next;
  }
  return {firstMatch, trailing};
}
 
} // namespace precice::utils
 
template <typename Iter>
struct fmt::formatter<precice::utils::RangePreview<Iter>> : ostream_formatter {
};