#ifndef _VTEST_VMAKE_HPP #define _VTEST_VMAKE_HPP #include #if __cplusplus < 201703L #include "optional.hpp" #endif namespace vmake { using std::size_t; struct require_unique_t {} require_unique; struct sequence_terminated_error : std::exception { virtual const char *what() const noexcept override final { return "iterating on a terminated sequence."; } }; namespace polyfill { #if __cplusplus >= 201703L using std::optional; using std::as_const; using std::apply; #else using nonstd::optional; template constexpr typename std::add_const::type& as_const(T& t) noexcept { return t; } template void as_const(const T&&) = delete; namespace details { template decltype(auto) apply_helper(Func &&f, Tuple &&t, std::index_sequence) { return f(std::get(std::forward(t))...); } } // namespace details template decltype(auto) apply(Func &&f, Tuple &&t) { return details::apply_helper(std::forward(f), std::forward(t) , std::make_index_sequence::type>::value>()); } #endif } // namespace polyfill namespace details { template auto is_sequence_helper(char) -> decltype( std::declval()() , typename std::enable_if::type>().is_terminated()) , bool>::value, int>::type{0} , typename std::enable_if()()) , typename T::result>::value, int>::type{0} , std::true_type{}); template auto is_sequence_helper(int) -> std::false_type; } template using is_sequence_t = decltype(details::is_sequence_helper(' ')); namespace details { template struct iota_sequence { using result = T; T start; iota_sequence(T&& start) : start(std::forward(start)) {} bool is_terminated() const noexcept { return false; } decltype(auto) operator()() { return start++; } }; template struct ranged_sequence { using result = T; T start, end; ranged_sequence(T&& start, T&& end) : start(std::forward(start)), end(std::forward(end)) {} bool is_terminated() const noexcept { return !(start < end); } decltype(auto) operator()() { if (start == end) throw sequence_terminated_error(); return start++; } }; template struct ranged_step_sequence { using result = T; T start, end, step; ranged_step_sequence(T&& start, T&& end, T&& step) : start(std::forward(start)), end(std::forward(end)) , step(std::forward(step)) {} bool is_terminated() const noexcept { return !(start < end); } decltype(auto) operator()() { if (start == end) throw sequence_terminated_error(); T res = start; start += step; return res; } }; } // namespace details template inline auto iota(Val &&start) { return details::iota_sequence::type>(std::forward(start)); } template inline auto range(Val &&start, Val &&end) { return details::ranged_sequence::type>(std::forward(start) , std::forward(end)); } template inline auto range(Val &&start, Val &&end, Val &&step) { return details::ranged_step_sequence::type>( std::forward(start), std::forward(end), std::forward(step)); } namespace details { template struct empty_sequence { using result = T; bool is_terminated() const noexcept { return true; } T operator()() { throw sequence_terminated_error(); } }; } // namespace details template inline auto nothing() { return details::empty_sequence(); } namespace details { template struct ranged_iterator_extractor { using result = typename std::remove_reference())>::type; ContIt cur, end; bool added; ranged_iterator_extractor(const ContIt &begin, const ContIt &end) : cur(begin) , end(end), added(false) {} bool is_terminated() const noexcept { return cur == end; } decltype(auto) operator()() { // WARN: use for strange iterators such as std::istream_iterator // do NOT try to optimize this into *it++ if (cur == end) throw sequence_terminated_error(); if (added) return *++cur; added = true; return *cur; } }; template struct iterator_extractor { using result = typename std::remove_reference())>::type; ContIt it; bool added; iterator_extractor(const ContIt &begin) : it(begin), added(false) {}; constexpr bool is_terminated() const noexcept { return false; } decltype(auto) operator()() { // WARN: use for strange iterators such as std::istream_iterator // do NOT try to optimize this into *it++ if (added) return *++it; added = true; return *it; } }; } // namespace details template inline auto extract(const ContIt &begin, const ContIt &end) { return details::ranged_iterator_extractor(begin, end); } template inline auto extract(const ContIt &begin) { return details::iterator_extractor(begin); } template inline auto extract_n(const ContIt &begin, size_t n) { return take(details::iterator_extractor(begin), n); } namespace details { template struct generator { using result = decltype(std::declval()()); Func g; generator(Func &&g) : g(std::forward(g)) {} generator(const Func &g) : g(g) {} generator(generator &&y) = default; generator(const generator &y) = default; constexpr bool is_terminated() const noexcept { return false; } decltype(auto) operator()() { return g(); } }; } // namespace details template inline auto make_generator(Args&&... args) { return details::generator(std::move(Func(std::forward(args)...))); } template inline constexpr auto generate(Func &&f) { return details::generator::type>(std::forward(f)); } namespace details { template struct limitor { using core = Gen; using result = typename Gen::result; Gen g; size_t lim; limitor(Gen &&g, size_t lim) : g(std::move(g)), lim(lim) {} limitor(limitor &&g) = default; limitor(const limitor &g) = default; bool is_terminated() const noexcept { return lim <= 0 || g.is_terminated(); } decltype(auto) operator()() { if (lim-- > 0) return g(); else throw sequence_terminated_error(); } }; } // namespace details template inline auto take(Gen &&g, size_t lim) { return details::limitor::type>(std::forward(g), lim); }; namespace details { template struct repeater { using result = Tval; Tval x; repeater(Tval &&x) : x(std::forward(x)) {}; repeater(const repeater&) = default; repeater(repeater &&) = default; constexpr bool is_terminated() const noexcept { return false; } Tval operator()() const { return x; } }; } // namespace details template inline auto repeat(Tval &&x) { return details::repeater::type>(std::forward(x)); } template inline decltype(auto) repeat_n(Tval &&x, size_t n) { return take(repeat(std::forward(x)), n); } namespace details { inline constexpr bool concat_terminate_helper() noexcept { return true; } template inline bool concat_terminate_helper(Seq& f, Seqs& ...rest) noexcept { if (!f.is_terminated()) return false; return concat_terminate_helper(rest...); } template inline auto concat_terminate_applier(Tuple &t, std::index_sequence) noexcept { return polyfill::apply(concat_terminate_helper< typename std::tuple_element::type...>, t); } template inline decltype(auto) concat_call_helper(Seq& f, Seqs& ...rest) { if (f.is_terminated()) return concat_call_helper(rest...); return f(); } template inline decltype(auto) concat_call_helper(Seq &f) { return f(); } template inline decltype(auto) concat_call_applier(Tuple &t, std::index_sequence) { return polyfill::apply(concat_call_helper< typename std::tuple_element::type...>, t); } template struct concator { using result = typename Gen1::result; using core = std::tuple; core g; concator(Gen1&& g1, Gen&&... g2) : g(std::forward(g1), std::forward(g2)...) {} concator(concator&&) = default; concator(const concator&) = default; bool is_terminated() const noexcept { return concat_terminate_applier(g, std::make_index_sequence()); } decltype(auto) operator()() { return concat_call_applier(g, std::make_index_sequence()); } }; } // namespace details template inline constexpr auto concat(Gen&&... g) noexcept { return details::concator::type...>(std::forward(g)...); } namespace details { template struct transformer { using result = decltype(std::declval()(std::declval())); using core = Gen; Gen g; Func f; transformer(Gen &&g, Func &&gf) : g(std::move(g)), f(std::move(f)) {} transformer(transformer &&c) = default; transformer(const transformer &c) = default; bool is_terminated() const noexcept { return g.is_terminated(); } decltype(auto) operator()() { return f(g()); } }; } // namespace details template inline auto transform(Gen &&g, Func &&f) { return details::transformer::type , typename std::decay::type>(std::forward(g) , std::forward(f)); } template struct filteror { using result = typename Gen::result; using core = Gen; filteror(filteror &&) = default; filteror(const filteror &) = default; mutable Gen g; Pred p; mutable polyfill::optional preview; filteror(Gen &&g, Pred &&p) : g(std::forward(g)), p(std::forward(p)) { _find_next(); }; bool is_terminated() const noexcept { if (g.is_terminated() && !preview.has_value()) return true; if (!preview.has_value()) _find_next(); return !preview.has_value(); } decltype(auto) operator()() { if (is_terminated()) throw sequence_terminated_error(); result res = std::move(*preview); preview.reset(); return res; } private: void _find_next() const { preview.reset(); do { if (g.is_terminated()) { preview.reset(); return; } preview.emplace(std::move(g())); } while (!p(polyfill::as_const(*preview))); } }; template inline filteror::type , typename std::decay::type> filter(Gen &&g, Pred &&p) { return {std::forward(g), std::forward(p)}; } namespace details { //template //using tuple_cat_t = decltype(std::tuple_cat(std::declval()...)); template auto repeat_tuple_builder(std::index_sequence seq) -> std::tuple::type...>; template struct repeat_tuple_t { using type = decltype(repeat_tuple_builder(std::make_index_sequence())); }; template inline auto group_builder(Gen &g, std::index_sequence seq) { auto val = std::array{ (void(index), g())... }; return std::make_tuple(std::move(std::get(val))...); } template struct grouper { static_assert(n > 0, ""); using result = typename repeat_tuple_t::type; using core = Gen; Gen g; grouper(grouper&& g) = default; grouper(const grouper& g) = default; grouper(Gen &&g) : g(std::forward(g)) {} bool is_terminated() const noexcept { return g.is_terminated(); } result operator()() { return group_builder(g, std::make_index_sequence()); } }; } // namespace details template inline auto group(Gen &&g) { return details::grouper::type, n>(std::forward(g)); } template inline decltype(auto) discard_n(Gen &&g, size_t n) { for (size_t i = 0; i < n; ++i) g(); return std::forward(g); } namespace details { template auto zipper_call_helper(Gen &&g, std::index_sequence) { return std::make_tuple(std::get(g)()...); } inline constexpr bool zip_terminate_helper() noexcept { return false; } template inline bool zip_terminate_helper(Seq& f, Seqs& ...rest) noexcept { if (f.is_terminated()) return true; return zip_terminate_helper(rest...); } template inline auto zip_terminate_applier(Tuple &t, std::index_sequence) noexcept { return polyfill::apply(zip_terminate_helper< typename std::tuple_element::type...>, t); } template struct zipper { private: static constexpr auto _n = std::tuple_size::value; using _make_index = std::make_index_sequence<_n>; public: using result = decltype(zipper_call_helper(std::declval(), _make_index())); using core = Gen; Gen g; zipper(zipper &&) = default; zipper(const zipper &) = default; zipper(Gen &&g) : g(std::forward(g)) {} bool is_terminated() const noexcept { return zip_terminate_applier(g, _make_index()); } decltype(auto) operator()() { return zipper_call_helper(g, _make_index()); } }; } // namespace detail template inline decltype(auto) zip(Gen&&... g) { using Tuple = std::tuple::type...>; return details::zipper(std::make_tuple(std::forward(g)...)); } namespace rng { inline auto make_seed() { // NOTE: MinGW GCC older than 9.2 have a fixed random_device #if defined(__GNUC__) && defined(_WIN32) && __GNUC__ * 100 + __GNUC_MINOR__ <= 902 return std::chrono::steady_clock::now().time_since_epoch().count(); #else return std::random_device{}(); #endif } template inline auto common() { return make_generator(make_seed()); } template inline auto common(Seed seed) { return make_generator(seed); } namespace details { struct cstyle_rng { using result = decltype(std::rand()); bool is_terminated() const noexcept { return false; } auto operator()() { return std::rand(); } }; } inline auto cstyle() { std::srand(time(0)); std::rand(); return details::cstyle_rng(); } inline auto cstyle(unsigned seed) { std::srand(seed); std::rand(); return details::cstyle_rng(); } template inline auto uniform_ints(Tval &&l, Tval &&r) { return generate([rng = Engine(make_seed()) , dis = std::uniform_int_distribution::type>( std::forward(l), std::forward(r))]() mutable { return dis(rng); }); } namespace details { template struct unique_ints_sequence { using result = Tval; unique_ints_sequence(unique_ints_sequence &&) = default; unique_ints_sequence(const unique_ints_sequence &) = default; Tval l, r; Engine rng; std::uniform_int_distribution dis; bool halfed; std::unordered_set used; std::vector rest; unique_ints_sequence(Engine &&e, Tval &&l, Tval &&r) : l(std::forward(l)) , r(std::forward(r)), rng(std::forward(e)) , dis(std::forward(l), std::forward(r)), halfed(false) {} bool is_terminated() const noexcept { return halfed && rest.empty(); } auto operator()() { if (!halfed && (used.size() + 1) * 2 - (r - l + 1) >= 0) { for (Tval i = l; i <= r; ++i) { if (!used.count(i)) rest.push_back(i); } std::shuffle(rest.begin(), rest.end(), rng); halfed = true; } if (halfed) { if (rest.empty()) throw sequence_terminated_error(); auto res = std::move(rest.back()); rest.pop_back(); return res; } while (true) { auto res = dis(rng); if (used.count(res)) continue; used.insert(res); return res; } } }; }; template inline auto uniform_ints(require_unique_t _, Tval &&l, Tval &&r) { return details::unique_ints_sequence::type, Engine>( Engine(make_seed()), std::forward(l), std::forward(r)); } template inline auto uniform_reals(Tval &&l, Tval &&r) { return generate([rng = Engine(make_seed()) , dis = std::uniform_real_distribution::type>( std::forward(l), std::forward(r))]() mutable { return dis(rng); }); } } template inline OutputIt copy(OutputIt it, Gen&& g) { while (!g.is_terminated()) { *it++ = g(); } return it; } template inline OutputIt copy_n(OutputIt it, size_t n, Gen&& g) { for (size_t i = 0; i < n; ++i) { *it++ = g(); } return it; } template inline auto output(std::basic_ostream& out, const char *delim, Gen &&g) { return copy(std::ostream_iterator< typename std::decay::type::result>(out, delim), std::move(g)); } template inline auto output(std::basic_ostream& out, Gen &&g) { return copy(std::ostream_iterator< typename std::decay::type::result>(out), std::move(g)); } template inline auto output_n(std::basic_ostream& out, size_t n, const char *delim, Gen &&g) { return copy_n(std::ostream_iterator< typename std::decay::type::result>(out, delim), n, std::move(g)); } template inline auto output_n(std::basic_ostream& out, size_t n, Gen &&g) { return copy_n(std::ostream_iterator< typename std::decay::type::result>(out), n, std::move(g)); } template)> inline auto outputln(std::basic_ostream& out, const char *delim , Gen &&g, const Endl &endl = std::endl) { auto res = copy(std::ostream_iterator< typename std::decay::type::result>(out, delim), std::forward(g)); out << endl; return res; } template)> inline auto outputln(std::basic_ostream& out , Gen &&g, const Endl &endl = std::endl) { auto res = copy(std::ostream_iterator< typename std::decay::type::result>(out), std::forward(g)); out << endl; return res; } template)> inline auto outputln_n(std::basic_ostream& out, size_t n , const char *delim, Gen &&g, const Endl &endl = std::endl) { auto res = copy_n(std::ostream_iterator< typename std::decay::type::result>(out, delim), n, std::forward(g)); out << endl; return res; } template)> inline auto outputln_n(std::basic_ostream& out, size_t n , Gen &&g, const Endl &endl = std::endl) { auto res = copy_n(std::ostream_iterator< typename std::decay::type::result>(out), n, std::forward(g)); out << endl; return res; } template)> inline void outputln(std::basic_ostream& out , const Endl &endl = std::endl) { out << endl; } namespace _checks { using empty_sequence_int = decltype(nothing()); static_assert(is_sequence_t::value && is_sequence_t::value && is_sequence_t(empty_sequence_int{}))>::value && is_sequence_t::value && !is_sequence_t::value && !is_sequence_t>::value , "compile-time self-checking failed(try upgrading your compiler)."); } // namespace _checks } // namespace vmake #endif