This documentation is automatically generated by online-judge-tools/verification-helper
#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
*/