Container Utils
(library/util/container_utils.hpp)

View this file on GitHub
Last update: 2023-09-15 20:02:25+09:00
Include: #include "library/util/container_utils.hpp"

Container Utils

Depends on

Code

#ifndef SUISEN_CONTAINER_UTILS
#define SUISEN_CONTAINER_UTILS

#include <vector>
#include <optional>
#include <sstream>

#include "library/io/input_stream.hpp"
#include "library/io/output_stream.hpp"
#include "library/type_traits/type_traits.hpp"

namespace suisen {
template <typename T>
int count_leq(const std::vector<T> &v, const T &key) { return std::upper_bound(v.begin(), v.end(), key) - v.begin();  }
template <typename T>
int count_lt(const std::vector<T> &v, const T &key) { return std::lower_bound(v.begin(), v.end(), key) - v.begin();  }
template <typename T>
int count_geq(const std::vector<T> &v, const T &key) { return v.size() - count_lt(v, key); }
template <typename T>
int count_gt(const std::vector<T> &v, const T &key) { return v.size() - count_leq(v, key); }

template <typename Container, typename Key>
auto min_geq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) {
    if (auto it = container.lower_bound(key); it == container.end()) return std::nullopt;
    else return std::make_optional(*it);
}
template <typename Container, typename Key>
auto min_gt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) {
    if (auto it = container.upper_bound(key); it == container.end()) return std::nullopt;
    else return std::make_optional(*it);
}
template <typename Container, typename Key>
auto max_leq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) {
    if (auto it = container.upper_bound(key); it == container.begin()) return std::nullopt;
    else return std::make_optional(*--it);
}
template <typename Container, typename Key>
auto max_lt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) {
    if (auto it = container.lower_bound(key); it == container.begin()) return std::nullopt;
    else return std::make_optional(*--it);
}
template <typename T>
std::optional<T> min_geq(const std::vector<T> &v, const T &key) {
    auto it = std::lower_bound(v.begin(), v.end(), key);
    return it == v.end() ? std::nullopt : std::make_optional(*it);
}
template <typename T>
std::optional<T> min_gt(const std::vector<T> &v, const T &key) {
    auto it = std::upper_bound(v.begin(), v.end(), key);
    return it == v.end() ? std::nullopt : std::make_optional(*it);
}
template <typename T>
std::optional<T> max_leq(const std::vector<T> &v, const T &key) {
    auto it = std::upper_bound(v.begin(), v.end(), key);
    return it == v.begin() ? std::nullopt : std::make_optional(*--it);
}
template <typename T>
std::optional<T> max_lt(const std::vector<T> &v, const T &key) {
    auto it = std::lower_bound(v.begin(), v.end(), key);
    return it == v.begin() ? std::nullopt : std::make_optional(*--it);
}

__int128_t stoi128(const std::string& s) {
    __int128_t res;
    io::InputStream{std::istringstream{s}} >> res;
    return res;
}
__uint128_t stou128(const std::string& s) {
    __uint128_t res;
    io::InputStream{std::istringstream{s}} >> res;
    return res;
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
std::string join(const Iterable& v, const std::string& sep, const std::string& end) {
    io::OutputStream os{ std::ostringstream{} };
    os.print_all(v, sep, end);
    return os.get_stream().str();
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
std::vector<Iterable> split(const Iterable &s, const typename Iterable::value_type &delim) {
    std::vector<Iterable> res;
    for (auto itl = s.begin(), itr = itl;; itl = ++itr) {
        while (itr != s.end() and *itr != delim) ++itr;
        res.emplace_back(itl, itr);
        if (itr == s.end()) return res;
    }
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
void concat(Iterable& s, const Iterable& t) {
    s.reserve(std::size(s) + std::size(t));
    std::copy(std::begin(t), std::end(t), std::back_inserter(s));
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
Iterable concatenated(Iterable s, const Iterable& t) { concat(s, t); return s; }

template <typename Func, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
auto mapped_vec(const Func& f, const Iterable& s) {
    std::vector<std::invoke_result_t<Func, typename Iterable::value_type>> v;
    v.reserve(std::size(s)), std::transform(s.begin(), s.end(), std::back_inserter(v), f);
    return v;
}
template <typename T, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
auto copied_vec(const Iterable& s) {
    std::vector<T> v;
    v.reserve(std::size(s)), std::copy(s.begin(), s.end(), std::back_inserter(v));
    return v;
}

namespace charmap {
    int fd(char c) { return c - '0'; }
    int fa(char c) { return c - 'a'; }
    int fA(char c) { return c - 'A'; }
    int faA(char c) { return c <= 'Z' ? c - 'A' : 26 + (c - 'a'); }
}

// val = Sum_i res[i] * base^i
template <int base = 2, typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::string digits_str(T val, size_t width = 0) {
    static_assert(2 <= base and base <= 10);
    std::string res;
    for (; val or res.size() < width; val /= base) res += '0' + (val % base);
    return res;
}
// val = Sum_i res[i] * base^i
template <typename T, typename U = int, std::enable_if_t<std::conjunction_v<std::is_integral<T>, std::is_integral<U>>, std::nullptr_t> = nullptr>
std::vector<U> digits(T val, U base = 10) {
    std::vector<U> res;
    for (; val; val /= base) res.push_back(val % base);
    if (res.empty()) res.push_back(T{ 0 });
    return res;
}
} // namespace suisen

#endif // SUISEN_CONTAINER_UTILS

#line 1 "library/util/container_utils.hpp"



#include <vector>
#include <optional>
#include <sstream>

#line 1 "library/io/input_stream.hpp"



#include <iostream>
#line 1 "library/type_traits/type_traits.hpp"



#include <limits>
#line 6 "library/type_traits/type_traits.hpp"
#include <type_traits>

namespace suisen {
    template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;

    template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
    template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
    template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
    template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
    template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;

    template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
    template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;

    template <typename T, typename = void> struct rec_value_type { using type = T; };
    template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
        using type = typename rec_value_type<typename T::value_type>::type;
    };
    template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;

    template <typename T> class is_iterable {
        template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
    template <typename T> class is_writable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
    template <typename T> class is_readable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen

#line 6 "library/io/input_stream.hpp"
namespace suisen::io {
    template <typename IStream, std::enable_if_t<std::conjunction_v<std::is_base_of<std::istream, std::remove_reference_t<IStream>>, std::negation<std::is_const<std::remove_reference_t<IStream>>>>, std::nullptr_t> = nullptr>
    struct InputStream {
    private:
        using istream_type = std::remove_reference_t<IStream>;
        IStream is;
        struct { InputStream* is; template <typename T> operator T() { T e; *is >> e; return e; } } _reader{ this };
    public:
        template <typename IStream_> InputStream(IStream_ &&is) : is(std::move(is)) {}
        template <typename IStream_> InputStream(IStream_ &is) : is(is) {}
        template <typename T> InputStream& operator>>(T& e) {
            if constexpr (suisen::is_readable_v<T>) is >> e; else _read(e);
            return *this;
        }
        auto read() { return _reader; }
        template <typename Head, typename... Tail>
        void read(Head& head, Tail &...tails) { ((*this >> head) >> ... >> tails); }
        istream_type& get_stream() { return is; }
    private:
        static __uint128_t _stou128(const std::string& s) {
            __uint128_t ret = 0;
            for (char c : s) if ('0' <= c and c <= '9') ret = 10 * ret + c - '0';
            return ret;
        }
        static __int128_t _stoi128(const std::string& s) { return (s[0] == '-' ? -1 : +1) * _stou128(s); }

        void _read(__uint128_t& v) { v = _stou128(std::string(_reader)); }
        void _read(__int128_t& v) { v = _stoi128(std::string(_reader)); }
        template <typename T, typename U>
        void _read(std::pair<T, U>& a) { *this >> a.first >> a.second; }
        template <size_t N = 0, typename ...Args>
        void _read(std::tuple<Args...>& a) { if constexpr (N < sizeof...(Args)) *this >> std::get<N>(a), _read<N + 1>(a); }
        template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
        void _read(Iterable& a) { for (auto& e : a) *this >> e; }
    };
    template <typename IStream>
    InputStream(IStream &&) -> InputStream<IStream>;
    template <typename IStream>
    InputStream(IStream &) -> InputStream<IStream&>;

    InputStream cin{ std::cin };

    auto read() { return cin.read(); }
    template <typename Head, typename... Tail>
    void read(Head& head, Tail &...tails) { cin.read(head, tails...); }
} // namespace suisen::io
namespace suisen { using io::read; } // namespace suisen

#line 1 "library/io/output_stream.hpp"



#line 6 "library/io/output_stream.hpp"
namespace suisen::io {
    template <typename OStream, std::enable_if_t<std::conjunction_v<std::is_base_of<std::ostream, std::remove_reference_t<OStream>>, std::negation<std::is_const<std::remove_reference_t<OStream>>>>, std::nullptr_t> = nullptr>
    struct OutputStream {
    private:
        using ostream_type = std::remove_reference_t<OStream>;
        OStream os;
    public:
        template <typename OStream_> OutputStream(OStream_ &&os) : os(std::move(os)) {}
        template <typename OStream_> OutputStream(OStream_ &os) : os(os) {}
        template <typename T> OutputStream& operator<<(const T& e) {
            if constexpr (suisen::is_writable_v<T>) os << e; else _print(e);
            return *this;
        }
        void print() { *this << '\n'; }
        template <typename Head, typename... Tail>
        void print(const Head& head, const Tail &...tails) { *this << head, ((*this << ' ' << tails), ...), *this << '\n'; }
        template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
        void print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") {
            for (auto it = v.begin(); it != v.end();) if (*this << *it; ++it != v.end()) *this << sep;
            *this << end;
        }
        ostream_type& get_stream() { return os; }
    private:
        void _print(__uint128_t value) {
            char buffer[41], *d = std::end(buffer);
            do *--d = '0' + (value % 10), value /= 10; while (value);
            os.rdbuf()->sputn(d, std::end(buffer) - d);
        }
        void _print(__int128_t value) {
            if (value < 0) *this << '-';
            _print(__uint128_t(value < 0 ? -value : value));
        }
        template <typename T, typename U>
        void _print(const std::pair<T, U>& a) { *this << a.first << ' ' << a.second; }
        template <size_t N = 0, typename ...Args>
        void _print(const std::tuple<Args...>& a) {
            if constexpr (N < std::tuple_size_v<std::tuple<Args...>>) {
                if constexpr (N) *this << ' ';
                *this << std::get<N>(a), _print<N + 1>(a);
            }
        }
        template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
        void _print(const Iterable& a) { print_all(a, " ", ""); }
    };
    template <typename OStream_>
    OutputStream(OStream_ &&) -> OutputStream<OStream_>;
    template <typename OStream_>
    OutputStream(OStream_ &) -> OutputStream<OStream_&>;

    OutputStream cout{ std::cout }, cerr{ std::cerr };

    template <typename... Args>
    void print(const Args &... args) { cout.print(args...); }
    template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
    void print_all(const Iterable& v, const std::string& sep = " ", const std::string& end = "\n") { cout.print_all(v, sep, end); }
} // namespace suisen::io
namespace suisen { using io::print, io::print_all; } // namespace suisen

#line 11 "library/util/container_utils.hpp"

namespace suisen {
template <typename T>
int count_leq(const std::vector<T> &v, const T &key) { return std::upper_bound(v.begin(), v.end(), key) - v.begin();  }
template <typename T>
int count_lt(const std::vector<T> &v, const T &key) { return std::lower_bound(v.begin(), v.end(), key) - v.begin();  }
template <typename T>
int count_geq(const std::vector<T> &v, const T &key) { return v.size() - count_lt(v, key); }
template <typename T>
int count_gt(const std::vector<T> &v, const T &key) { return v.size() - count_leq(v, key); }

template <typename Container, typename Key>
auto min_geq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) {
    if (auto it = container.lower_bound(key); it == container.end()) return std::nullopt;
    else return std::make_optional(*it);
}
template <typename Container, typename Key>
auto min_gt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) {
    if (auto it = container.upper_bound(key); it == container.end()) return std::nullopt;
    else return std::make_optional(*it);
}
template <typename Container, typename Key>
auto max_leq(const Container &container, const Key &key) -> decltype(std::make_optional(*container.upper_bound(key))) {
    if (auto it = container.upper_bound(key); it == container.begin()) return std::nullopt;
    else return std::make_optional(*--it);
}
template <typename Container, typename Key>
auto max_lt(const Container &container, const Key &key) -> decltype(std::make_optional(*container.lower_bound(key))) {
    if (auto it = container.lower_bound(key); it == container.begin()) return std::nullopt;
    else return std::make_optional(*--it);
}
template <typename T>
std::optional<T> min_geq(const std::vector<T> &v, const T &key) {
    auto it = std::lower_bound(v.begin(), v.end(), key);
    return it == v.end() ? std::nullopt : std::make_optional(*it);
}
template <typename T>
std::optional<T> min_gt(const std::vector<T> &v, const T &key) {
    auto it = std::upper_bound(v.begin(), v.end(), key);
    return it == v.end() ? std::nullopt : std::make_optional(*it);
}
template <typename T>
std::optional<T> max_leq(const std::vector<T> &v, const T &key) {
    auto it = std::upper_bound(v.begin(), v.end(), key);
    return it == v.begin() ? std::nullopt : std::make_optional(*--it);
}
template <typename T>
std::optional<T> max_lt(const std::vector<T> &v, const T &key) {
    auto it = std::lower_bound(v.begin(), v.end(), key);
    return it == v.begin() ? std::nullopt : std::make_optional(*--it);
}

__int128_t stoi128(const std::string& s) {
    __int128_t res;
    io::InputStream{std::istringstream{s}} >> res;
    return res;
}
__uint128_t stou128(const std::string& s) {
    __uint128_t res;
    io::InputStream{std::istringstream{s}} >> res;
    return res;
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
std::string join(const Iterable& v, const std::string& sep, const std::string& end) {
    io::OutputStream os{ std::ostringstream{} };
    os.print_all(v, sep, end);
    return os.get_stream().str();
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
std::vector<Iterable> split(const Iterable &s, const typename Iterable::value_type &delim) {
    std::vector<Iterable> res;
    for (auto itl = s.begin(), itr = itl;; itl = ++itr) {
        while (itr != s.end() and *itr != delim) ++itr;
        res.emplace_back(itl, itr);
        if (itr == s.end()) return res;
    }
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
void concat(Iterable& s, const Iterable& t) {
    s.reserve(std::size(s) + std::size(t));
    std::copy(std::begin(t), std::end(t), std::back_inserter(s));
}
template <typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
Iterable concatenated(Iterable s, const Iterable& t) { concat(s, t); return s; }

template <typename Func, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
auto mapped_vec(const Func& f, const Iterable& s) {
    std::vector<std::invoke_result_t<Func, typename Iterable::value_type>> v;
    v.reserve(std::size(s)), std::transform(s.begin(), s.end(), std::back_inserter(v), f);
    return v;
}
template <typename T, typename Iterable, std::enable_if_t<suisen::is_iterable_v<Iterable>, std::nullptr_t> = nullptr>
auto copied_vec(const Iterable& s) {
    std::vector<T> v;
    v.reserve(std::size(s)), std::copy(s.begin(), s.end(), std::back_inserter(v));
    return v;
}

namespace charmap {
    int fd(char c) { return c - '0'; }
    int fa(char c) { return c - 'a'; }
    int fA(char c) { return c - 'A'; }
    int faA(char c) { return c <= 'Z' ? c - 'A' : 26 + (c - 'a'); }
}

// val = Sum_i res[i] * base^i
template <int base = 2, typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::string digits_str(T val, size_t width = 0) {
    static_assert(2 <= base and base <= 10);
    std::string res;
    for (; val or res.size() < width; val /= base) res += '0' + (val % base);
    return res;
}
// val = Sum_i res[i] * base^i
template <typename T, typename U = int, std::enable_if_t<std::conjunction_v<std::is_integral<T>, std::is_integral<U>>, std::nullptr_t> = nullptr>
std::vector<U> digits(T val, U base = 10) {
    std::vector<U> res;
    for (; val; val /= base) res.push_back(val % base);
    if (res.empty()) res.push_back(T{ 0 });
    return res;
}
} // namespace suisen

Container Utils (library/util/container_utils.hpp)

Container Utils

Depends on

Code

Container Utils
(library/util/container_utils.hpp)