data_structure/bankers_queue.hpp

• View this file on GitHub
• Last update: 2023-05-08 16:51:58+09:00
• Include: #include "data_structure/bankers_queue.hpp"
• Link: http://www.kmonos.net/pub/Presen/PFDS.pdf
• Link: https://37zigen.com/bankers-queue/

Depends on

• data_structure/Stream.hpp
• data_structure/Suspension.hpp

Verified with

• test/data_structure/Persistent_Queue.test.cpp

Code

#pragma once

#include "../data_structure/Stream.hpp"


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

#include <cassert>


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 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

Back to top page