data_structure/Stream.hpp

• View this file on GitHub
• Last update: 2023-05-08 16:51:58+09:00
• Include: #include "data_structure/Stream.hpp"
• Link: https://noshi91.github.io/Library/data_structure/stream.cpp
• Link: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Depends on

• data_structure/Suspension.hpp

Required by

• data_structure/bankers_queue.hpp

Verified with

• test/data_structure/Persistent_Queue.test.cpp

Code

#pragma once

#include "../data_structure/Suspension.hpp"


/*
    reference: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
               https://noshi91.github.io/Library/data_structure/stream.cpp
*/

#include <cassert>

#include <optional>


namespace ebi {

template <class T>
struct stream : suspension<std::optional<std::pair<T, stream<T>>>> {
  private:
    using Self = stream<T>;
    using cell_type = std::optional<std::pair<T, Self>>;
    using base_type = suspension<cell_type>;
    using base_type::force;

    stream(T x, Self s) : base_type(cell_type(std::in_place, x, s)) {}

  public:
    stream() : base_type(cell_type(std::nullopt)) {}
    stream(std::function<cell_type()> f) : base_type(f) {}
    bool empty() const {
        return !force().has_value();
    }
    T top() const {
        assert(!empty());
        return force()->first;
    }
    Self push(T x) const {
        return stream(x, *this);
    }
    Self pop() const {
        assert(!empty());
        return (*force()).second;
    }
    Self reverse() {
        return Self([x = *this]() mutable {
            Self ret;
            while (!x.empty()) {
                ret = ret.push(x.top());
                x = x.pop();
            }
            return ret.force();
        });
    }

    friend Self operator+(Self lhs, Self rhs) {
        return Self([lhs, rhs]() {
            if (lhs.empty()) {
                return rhs.force();
            } else {
                return cell_type(std::in_place, lhs.top(), lhs.pop() + rhs);
            }
        });
    }
};

}  // namespace ebi

#line 2 "data_structure/Stream.hpp"

#line 2 "data_structure/Suspension.hpp"

/*
    reference: https://noshi91.github.io/Library/other/suspension.cpp
*/

#include <functional>

#include <memory>

#include <utility>

#include <variant>


namespace ebi {

template <class T>
struct suspension : std::shared_ptr<std::variant<T, std::function<T()>>> {
    using value_type = T;
    using func_type = std::function<T()>;
    using node_type = std::variant<T, std::function<T()>>;
    using base_type = std::shared_ptr<node_type>;

  private:
    static T get(node_type &x) {
        if (x.index() != 0) {
            x = std::get<1>(x)();
        }
        return std::get<0>(x);
    }

  public:
    suspension(T x)
        : base_type(std::make_shared<node_type>(std::in_place_index<0>, x)) {}
    suspension(std::function<T()> f)
        : base_type(std::make_shared<node_type>(std::in_place_index<1>, f)) {}

    T force() const {
        return get(**this);
    }
};

}  // namespace ebi

#line 4 "data_structure/Stream.hpp"

/*
    reference: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
               https://noshi91.github.io/Library/data_structure/stream.cpp
*/

#include <cassert>

#include <optional>


namespace ebi {

template <class T>
struct stream : suspension<std::optional<std::pair<T, stream<T>>>> {
  private:
    using Self = stream<T>;
    using cell_type = std::optional<std::pair<T, Self>>;
    using base_type = suspension<cell_type>;
    using base_type::force;

    stream(T x, Self s) : base_type(cell_type(std::in_place, x, s)) {}

  public:
    stream() : base_type(cell_type(std::nullopt)) {}
    stream(std::function<cell_type()> f) : base_type(f) {}
    bool empty() const {
        return !force().has_value();
    }
    T top() const {
        assert(!empty());
        return force()->first;
    }
    Self push(T x) const {
        return stream(x, *this);
    }
    Self pop() const {
        assert(!empty());
        return (*force()).second;
    }
    Self reverse() {
        return Self([x = *this]() mutable {
            Self ret;
            while (!x.empty()) {
                ret = ret.push(x.top());
                x = x.pop();
            }
            return ret.force();
        });
    }

    friend Self operator+(Self lhs, Self rhs) {
        return Self([lhs, rhs]() {
            if (lhs.empty()) {
                return rhs.force();
            } else {
                return cell_type(std::in_place, lhs.top(), lhs.pop() + rhs);
            }
        });
    }
};

}  // namespace ebi

Back to top page