algorithm.h

#pragma once
 
#include <algorithm>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
 
namespace cgv {
namespace utils {
 
template <class T1 = void, class T2 = void>
struct get_first {
    constexpr T1 operator()(const std::pair<T1, T2>& pair) const {
        return pair.first;
    }
};
 
template <>
struct get_first<void, void> {
    template <class T1, class T2>
    constexpr auto operator()(const std::pair<T1, T2>& pair) const
        -> decltype(static_cast<const T1&>(pair.first)) {
        return static_cast<const T1&>(pair.first);
    }
};
 
template <class T1 = void, class T2 = void>
struct get_second {
    constexpr T2 operator()(const std::pair<T1, T2>& pair) const {
        return pair.second;
    }
};
 
template <>
struct get_second<void, void> {
    template <class T1, class T2>
    constexpr auto operator()(const std::pair<T1, T2>& pair) const
        -> decltype(static_cast<const T2&>(pair.second)) {
        return static_cast<const T2&>(pair.second);
    }
};
 
template<typename ForwardIt, typename T>
T min_value(ForwardIt first, ForwardIt last, T fallback) {
    auto it = std::min_element(first, last);
    return it != last ? static_cast<T>(*it) : fallback;
}
 
template<typename ForwardIt, typename UnaryOp, typename T>
T min_value(ForwardIt first, ForwardIt last, UnaryOp operation, T fallback) {
    auto it = std::min_element(first, last, [&operation](const auto& left, const auto& right) {
        return operation(left) < operation(right);
    });
    return it != last ? static_cast<T>(operation(*it)) : fallback;
}
 
template<typename ForwardIt, typename T>
T max_value(ForwardIt first, ForwardIt last, T fallback) {
    auto it = std::max_element(first, last);
    return it != last ? static_cast<T>(*it) : fallback;
}
 
template<typename ForwardIt, typename UnaryOp, typename T>
T max_value(ForwardIt first, ForwardIt last, UnaryOp operation, T fallback) {
    auto it = std::max_element(first, last, [&operation](const auto& left, const auto& right) {
        return operation(left) < operation(right);
    });
    return it != last ? static_cast<T>(operation(*it)) : fallback;
}
 
template <class InputIt, class UnaryOp>
std::string transform_join(const InputIt first, const InputIt last, UnaryOp operation, const std::string& separator, bool trailing_separator = false) {
    std::string res = "";
    if(last > first) {
        for(auto curr = first; curr != last; ++curr) {
            res += operation(*curr);
            if(last - curr > 1 || trailing_separator)
                res += separator;
        }
    }
    return res;
}
 
template <class InputIt>
std::string join(const InputIt first, const InputIt last, const std::string& separator, bool trailing_separator = false) {
    return transform_join(first, last, [](const auto& val) { return to_string(val); }, separator, trailing_separator);
}
 
template<class InputIt, class OutputIt>
OutputIt pair_adjacent(const InputIt first, const InputIt last, OutputIt d_first) {
    if(std::distance(first, last) > 1) {
        return std::transform(first, std::prev(last), std::next(first), d_first, [](const auto& a, const auto& b) {
            return std::make_pair(a, b);
        });
    }
    return d_first;
}
 
template<class InputIt>
std::vector<std::pair<typename InputIt::value_type, typename InputIt::value_type>> pair_adjacent(const InputIt first, const InputIt last) {
    std::vector<std::pair<typename InputIt::value_type, typename InputIt::value_type>> res;
    pair_adjacent(first, last, std::back_inserter(res));
    return res;
}
 
template<typename InputIt1, typename InputIt2, typename OutputIt>
OutputIt zip(const InputIt1 first1, const InputIt1 last1, const InputIt2 first2, OutputIt d_first) {
    return std::transform(first1, last1, first2, d_first, [](const auto& a, const auto& b) {
        return std::make_pair(a, b);
    });
}
 
template<typename InputIt1, typename InputIt2>
std::vector<std::pair<typename InputIt1::value_type, typename InputIt2::value_type>> zip(const InputIt1 first1, const InputIt1 last1, const InputIt2 first2) {
    std::vector<std::pair<typename InputIt1::value_type, typename InputIt2::value_type>> res;
    zip(first1, last1, first2, std::back_inserter(res));
    return res;
}
 
template<typename ParamT = float, typename OutputIt>
void subdivision_sequence(OutputIt output_first, ParamT start, ParamT stop, size_t n) {
    if(n == 1) {
        *output_first = ParamT(0.5) * (start + stop);
        ++output_first;
    } else if(n > 1) {
        const ParamT size = stop - start;
        const ParamT step = size / static_cast<ParamT>(n - 1);
        for(size_t i = 0; i < n; ++i) {
            ParamT t = start + step * static_cast<ParamT>(i);
            *output_first = t;
            ++output_first;
        }
    }
}
 
template<typename ParamT>
std::vector<ParamT> subdivision_sequence(ParamT start, ParamT stop, size_t n) {
    std::vector<ParamT> out;
    out.reserve(n);
    cgv::utils::subdivision_sequence(std::back_inserter(out), start, stop, n);
    return out;
}
 
template<class InputIt>
std::vector<size_t> generate_index_sequence(const InputIt first, const InputIt last) {
    std::vector<size_t> indices(static_cast<size_t>(std::distance(first, last)));
    std::iota(indices.begin(), indices.end(), 0);
    return indices;
}
 
template<class RandomIt>
std::vector<size_t> sort_indices(const RandomIt first, const RandomIt last) {
    std::vector<size_t> indices = generate_index_sequence(first, last);
    std::sort(indices.begin(), indices.end(), [first](size_t i1, size_t i2) {
        return first[i1] < first[i2];
    });
    return indices;
}
 
template<class RandomIt>
std::vector<size_t> stable_sort_indices(const RandomIt first, const RandomIt last) {
    std::vector<size_t> indices = generate_index_sequence(first, last);
    std::stable_sort(indices.begin(), indices.end(), [first](size_t i1, size_t i2) {
        return first[i1] < first[i2];
    });
    return indices;
}
 
template<class RandomIt, class Compare>
std::vector<size_t> sort_indices(const RandomIt first, const RandomIt last, Compare comp) {
    std::vector<size_t> indices = generate_index_sequence(first, last);
    std::sort(indices.begin(), indices.end(), [first, &comp](size_t i1, size_t i2) {
        return comp(first[i1], first[i2]);
    });
    return indices;
}
 
template<class RandomIt, class Compare>
std::vector<size_t> stable_sort_indices(const RandomIt first, const RandomIt last, Compare comp) {
    std::vector<size_t> indices = generate_index_sequence(first, last);
    std::stable_sort(indices.begin(), indices.end(), [first, &comp](size_t i1, size_t i2) {
        return comp(first[i1], first[i2]);
    });
    return indices;
}
 
} // namespace utils
} // namespace cgv