Persistent Queue
(data-structure/persistent_queue.hpp)

• View this file on GitHub
• Last update: 2024-01-07 20:49:49+09:00
• Include: #include "data-structure/persistent_queue.hpp"

Description

永続キューは，過去のバージョンを保持するキューである．この実装では内部で永続配列を用いている．

空間計算量: $O(m \log n)$, $m$ は変更の数

Operations

• int size()
  • キューの要素数を返す
  • 時間計算量: $O(1)$
• bool empty()
  • 時間計算量: $O(1)$
• T front()
  • 先頭の要素を返す
  • 時間計算量: $O(1)$
• T back()
  • 末尾の要素を返す
  • 時間計算量: $O(1)$
• PersistentQueue push(T val)
  • val をキューの末尾に追加する
  • 時間計算量: $O(\log n)$
• PersistentQueue pop()
  • キューの先頭要素を削除する
  • 時間計算量: $O(1)$

Depends on

• Persistent Array (data-structure/persistent_array.hpp)

Verified with

• test/yosupo/persistent_queue.test.cpp

Code

#pragma once
#include <cassert>

#include "persistent_array.hpp"

template <typename T>
class PersistentQueue {
   public:
    PersistentQueue() : first(0), last(0) {}

    int size() const { return last - first; }

    bool empty() const { return size() == 0; }

    T front() const {
        assert(!empty());
        return pa.get(first);
    }

    T back() const {
        assert(!empty());
        return pa.get(last - 1);
    }

    PersistentQueue push(const T& val) const {
        return PersistentQueue(pa.set(last, val), first, last + 1);
    }

    PersistentQueue pop() const {
        assert(!empty());
        return PersistentQueue(pa, first + 1, last);
    }

   private:
    PersistentArray<T> pa;
    int first, last;

    PersistentQueue(const PersistentArray<T>& pa, int first, int last)
        : pa(pa), first(first), last(last) {}
};

#line 2 "data-structure/persistent_queue.hpp"
#include <cassert>

#line 2 "data-structure/persistent_array.hpp"
#include <memory>
#include <vector>

template <typename T, int B = 2>
class PersistentArray {
   public:
    PersistentArray() = default;
    explicit PersistentArray(const std::vector<T>& v) {
        for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]);
    }

    T get(int k) const { return get(root, k); }

    PersistentArray set(int k, const T& x) const {
        return PersistentArray(set(root, k, x));
    }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr ch[B];
    };

    node_ptr root = nullptr;

    explicit PersistentArray(const node_ptr& root) : root(root) {}

    T get(const node_ptr& t, int k) const {
        if (k == 0) return t->val;
        return get(t->ch[k % B], k / B);
    }

    node_ptr set(const node_ptr& t, int k, const T& x) const {
        node_ptr res =
            t ? std::make_shared<Node>(*t) : std::make_shared<Node>();
        if (k == 0) {
            res->val = x;
        } else {
            res->ch[k % B] = set(res->ch[k % B], k / B, x);
        }
        return res;
    }
};
#line 5 "data-structure/persistent_queue.hpp"

template <typename T>
class PersistentQueue {
   public:
    PersistentQueue() : first(0), last(0) {}

    int size() const { return last - first; }

    bool empty() const { return size() == 0; }

    T front() const {
        assert(!empty());
        return pa.get(first);
    }

    T back() const {
        assert(!empty());
        return pa.get(last - 1);
    }

    PersistentQueue push(const T& val) const {
        return PersistentQueue(pa.set(last, val), first, last + 1);
    }

    PersistentQueue pop() const {
        assert(!empty());
        return PersistentQueue(pa, first + 1, last);
    }

   private:
    PersistentArray<T> pa;
    int first, last;

    PersistentQueue(const PersistentArray<T>& pa, int first, int last)
        : pa(pa), first(first), last(last) {}
};

Back to top page