test/data_structure/Persistent_Queue.test.cpp

View this file on GitHub
Last update: 2023-07-17 14:12:40+09:00
Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include <iomanip>

#include <iostream>

#include <limits>

#include <vector>


#include "../../data_structure/bankers_queue.hpp"


int main() {
    std::cout << std::fixed << std::setprecision(15);
    int q;
    std::cin >> q;
    std::vector<ebi::bankers_queue<int>> que(1);
    while (q--) {
        int flag;
        std::cin >> flag;
        if (flag == 0) {
            int t, x;
            std::cin >> t >> x;
            t++;
            que.emplace_back(que[t].push(x));
        } else {
            int t;
            std::cin >> t;
            t++;
            std::cout << que[t].top() << '\n';
            que.emplace_back(que[t].pop());
        }
    }
}

#line 1 "test/data_structure/Persistent_Queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include <iomanip>

#include <iostream>

#include <limits>

#include <vector>


#line 2 "data_structure/bankers_queue.hpp"

#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
#line 4 "data_structure/bankers_queue.hpp"

/*
    reference: https://37zigen.com/bankers-queue/
               http://www.kmonos.net/pub/Presen/PFDS.pdf
*/

#line 11 "data_structure/bankers_queue.hpp"

namespace ebi {

template <class T> struct bankers_queue {
  private:
    using size_t = std::size_t;
    using Self = bankers_queue<T>;
    stream<T> f;
    size_t fsize;
    stream<T> r;
    size_t rsize;

    bankers_queue(stream<T> _f, size_t _fsize, stream<T> _r, size_t _rsize)
        : f(_f), fsize(_fsize), r(_r), rsize(_rsize) {}

    Self normalize() {
        if (fsize >= rsize)
            return *this;
        else {
            return Self(f + r.reverse(), fsize + rsize, stream<T>(), 0);
        }
    }

  public:
    bankers_queue() : f(), fsize(0), r(), rsize(0) {}

    bool empty() {
        return f.empty();
    }

    T top() {
        assert(!empty());
        return f.top();
    }

    T front() {
        return top();
    }

    Self push(T x) {
        return Self(f, fsize, r.push(x), rsize + 1).normalize();
    }

    Self pop() {
        assert(!empty());
        return Self(f.pop(), fsize - 1, r, rsize).normalize();
    }
};

}  // namespace ebi
#line 9 "test/data_structure/Persistent_Queue.test.cpp"

int main() {
    std::cout << std::fixed << std::setprecision(15);
    int q;
    std::cin >> q;
    std::vector<ebi::bankers_queue<int>> que(1);
    while (q--) {
        int flag;
        std::cin >> flag;
        if (flag == 0) {
            int t, x;
            std::cin >> t >> x;
            t++;
            que.emplace_back(que[t].push(x));
        } else {
            int t;
            std::cin >> t;
            t++;
            std::cout << que[t].top() << '\n';
            que.emplace_back(que[t].pop());
        }
    }
}