This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub noshi91/Library
#include "other/suspension.cpp" #include <cassert> #include <optional> #include <utility> template <class T> class stream : private suspension<std::optional<std::pair<T, stream<T>>>> { using Self = stream<T>; public: using value_type = T; using cell_type = std::optional<std::pair<T, Self>>; private: using base_type = suspension<cell_type>; stream(T x, Self s) : base_type(std::in_place, cell_type(std::in_place, x, s)) {} public: stream() : base_type(std::in_place, cell_type(std::nullopt)) {} stream(std::function<cell_type()> f) : base_type(f) {} using base_type::force; bool empty() const { return not force().has_value(); } T top() const { assert(not empty()); return (*force()).first; } Self push(T x) const { return Self(x, *this); } Self pop() const { assert(not empty()); return (*force()).second; } Self reverse() const { return Self([x = *this]() mutable { Self ret; while (not x.empty()) { ret = ret.push(x.top()); x = x.pop(); } return ret.force(); }); } friend Self operator+(Self l, Self r) { return Self([l, r]() { if (l.empty()) return r.force(); else return cell_type(std::in_place, l.top(), l.pop() + r); }); } }; /** * @brief Stream * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf */
#line 1 "other/suspension.cpp" #include <functional> #include <memory> #include <utility> #include <variant> template <class T> class suspension : private std::shared_ptr<std::variant<T, std::function<T()>>> { public: using value_type = T; using func_type = std::function<T()>; using node_type = std::variant<T, func_type>; private: using base_type = std::shared_ptr<node_type>; static T get(node_type &x) { if (x.index() != 0) x = std::get<1>(x)(); return std::get<0>(x); } template <class... Args> static base_type make_node(Args &&... args) { return std::make_shared<node_type>(std::forward<Args>(args)...); } public: suspension(std::in_place_t, T x) : base_type(make_node(std::in_place_index<0>, x)) {} suspension(func_type f) : base_type(make_node(std::in_place_index<1>, f)) {} T force() const { return get(**this); } }; /** * @brief Suspension * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf */ #line 2 "data_structure/stream.cpp" #include <cassert> #include <optional> #line 6 "data_structure/stream.cpp" template <class T> class stream : private suspension<std::optional<std::pair<T, stream<T>>>> { using Self = stream<T>; public: using value_type = T; using cell_type = std::optional<std::pair<T, Self>>; private: using base_type = suspension<cell_type>; stream(T x, Self s) : base_type(std::in_place, cell_type(std::in_place, x, s)) {} public: stream() : base_type(std::in_place, cell_type(std::nullopt)) {} stream(std::function<cell_type()> f) : base_type(f) {} using base_type::force; bool empty() const { return not force().has_value(); } T top() const { assert(not empty()); return (*force()).first; } Self push(T x) const { return Self(x, *this); } Self pop() const { assert(not empty()); return (*force()).second; } Self reverse() const { return Self([x = *this]() mutable { Self ret; while (not x.empty()) { ret = ret.push(x.top()); x = x.pop(); } return ret.force(); }); } friend Self operator+(Self l, Self r) { return Self([l, r]() { if (l.empty()) return r.force(); else return cell_type(std::in_place, l.top(), l.pop() + r); }); } }; /** * @brief Stream * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf */