Container utilities

container.hpp

#pragma once
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>

/**
 * @file container.hpp
 * A few helpers to simplify common tasks pertaining to containers
 */

/// Helpers for containers
namespace cont {

/**
 * signed size of a type
 */
template <typename T>
inline constexpr auto ssizeof = static_cast<std::ptrdiff_t>(sizeof(T));

/**
 * The signed size of a container
 * @param c a container-like object
 * @return the size as a signed integer
 */
template <typename C>
constexpr auto ssize(C const &c) noexcept
{
    using std::size;
    using R = std::common_type_t<std::ptrdiff_t, std::make_signed_t<decltype(size(c))>>;
    return static_cast<R>(c.size());
}

/**
 * The signed size of an array
 * @return the size of the array as a signed integer
 */
template <typename T, std::size_t N>
constexpr auto ssize(T const(&)[N]) noexcept
{
    return std::ptrdiff_t(N);
}

/**
 * Test if a container contains a value
 * @param c a container
 * @param v a value
 * @return true if c contains at least one v
 */
template <typename C, typename T>
[[nodiscard]] bool contains(const C &c, T &&v)
{
    auto it = std::find(std::begin(c), std::end(c), v);
    return it != std::end(c);
}

/**
 * Test if a container contains a value
 * @param c a container
 * @param P a predicate
 * @return true if a least one element of c is true
 */
template <typename C, typename P>
[[nodiscard]] bool containsIf(const C &c, P &&p)
{
    auto it = std::find_if(std::begin(c), std::end(c), std::forward<P>(p));
    return it != std::end(c);
}

/**
 * Remove elements from a vector
 * @param c a vector
 * @param v a value
 * @return the number of removed elements
 */
template <typename VectorT,
          typename T,
          std::enable_if_t<std::is_convertible_v<T, typename VectorT::value_type>>* = nullptr>
size_t erase(VectorT &c, T &&v)
{
    const auto end = std::end(c);
    auto it = std::remove(std::begin(c), end, v);
    auto sz = std::distance(it, end);
    c.erase(it, end);
    return static_cast<size_t>(sz);
}

/**
 * Remove elements that satisfact a predicate from a vector
 * @param c a vector
 * @param p a predicate
 */
template <typename VectorT, typename P>
size_t eraseIf(VectorT &c, P &&p)
{
    const auto end = std::end(c);
    auto it = std::remove_if(std::begin(c), end, std::forward<P>(p));
    auto sz = std::distance(it, end);
    c.erase(it, end);
    return static_cast<size_t>(sz);
}

/**
 * For associative containers, returns either the value for a key or a default value
 * @param c an associative container
 * @param key the key to lookup
 * @param d the default value
 * @return either the mapped value for key or d if c does not contain key
 */
template <typename C, typename K, typename T>
[[nodiscard]] typename C::mapped_type valueOr(const C &c, K &&key, T &&d)
{
    auto it = c.find(key);
    return it == c.end() ? std::forward<T>(d) : it->second;
}

/**
 * Create a container of linearly spaced values
 * @pre last >= first && step > 0 || first >= last && step < 0
 * @param first first value
 * @param last last (excluded) value
 * @param step increment step
 * @return a container of values
 */
template <typename T, typename Cont = std::vector<T>>
Cont linspace(T first, T last, T step = 1)
{
    assert((last >= first && step > 0) || (first >= last && step < 0));

    const auto N = static_cast<size_t>((last - first) / step);
    Cont c(N);
    for (size_t i = 0; i < N; ++i) {
        c[i] = first;
        first += step;
    }
    return c;
}

/**
 * Append the data of container C2 to container C1
 */
template <typename C1, typename C2>
void append(C1 && c1, C2 && c2)
{
//    if constexpr (trait::is_resizable_container_v<C1>) {
//        c1.reserve(c1.size() + c2.size());
//    }
    std::copy(std::begin(c2), std::end(c2), std::back_inserter(c1));
}

/**
 * Map application over a container to produce a new container
 */
template <template <typename...> class Container,
          typename Func,
          typename T,
          typename ...Args>
auto map(const Container<T, Args...> &c, Func fun)
{
    using R = std::invoke_result_t<Func, const T&>;
    Container<R> res(std::size(c));
    std::transform(std::begin(c), std::end(c), std::begin(res), fun);
    return res;
}

/**
 * Map application over a container to produce a new container
 */
template <template <typename...> class Container1,
          template <typename...> class Container2,
          typename Func,
          typename T1,
          typename T2,
          typename ...Args1,
          typename ...Args2>
auto map(const Container1<T1, Args1...> &c1, const Container2<T2, Args2...> &c2, Func fun)
{
    const auto len = std::min(std::size(c1), std::size(c2));
    using R = std::invoke_result_t<Func, const T1&, const T2&>;
    Container1<R> res(len);
    std::transform(std::begin(c1), std::begin(c1) + len, std::begin(c2), std::begin(res), fun);
    return res;
}

/**
 * Permute the content of c in place using the permutation vector idx.
 * This is typically useful to sort a container by indices.
 */
template <typename ContainerT, typename ContainerIdx>
void permute(ContainerT &c, ContainerIdx &idx)
{
    using T = typename ContainerT::value_type;
    const auto len = std::size(c);

    for (size_t i = 0; i < len; i++) {
        auto cur = i;
        if (idx[cur] != i) {
            T t{std::move(c[i])};
            while (idx[cur] != i) {
                auto n = idx[cur];
                c[cur] = std::move(c[n]);
                idx[cur] = cur;
                cur = n;
            }
            c[cur] = std::move(t);
            idx[cur] = cur;
        }
    }
}

/**
 * Sort a container
 */
template <typename Container>
void sort(Container &c)
{
    std::sort(std::begin(c), std::end(c));
}

/**
 * Sort a container using a custom Compare function
 */
template <typename Container, typename CompareFunc>
void sort(Container &c, CompareFunc fun)
{
    std::sort(std::begin(c), std::end(c), std::move(fun));
}

/**
 * Sort a container using a key computed from the container elements using make_key.
 * The purpose of this function is to avoid numerous make_key invocations by caching
 * the result in a temporary vector of keys.
 */
template <typename Container, typename KeyFunc, typename CompareFunc>
void sortBy(Container &c, KeyFunc make_key, CompareFunc comp)
{
    using Key = decltype(make_key(std::declval<typename Container::value_type>()));
    std::vector<Key> keys(std::size(c));
    std::vector<size_t> idx(std::size(c));
    std::transform(std::begin(c), std::end(c), std::begin(keys), [&](auto &&e) { return make_key(e); });
    std::iota(idx.begin(), idx.end(), size_t(0));
    cont::sort(idx, [&](size_t a, size_t b) { return comp(keys[a], keys[b]); });
    permute(c, idx);
}

/**
 * Sort a container using a key computed from the container elements using make_key.
 * The purpose of this function is to avoid numerous make_key invocations by caching
 * the result in a temporary vector of keys.
 */
template <typename Container, typename KeyFunc>
void sortBy(Container &c, KeyFunc make_key)
{
    sortBy(c, std::move(make_key), std::less<>());
}

}  // namespace cont