Persistent Queue (永続キュー)
(lib/data_structure/persistent_queue.hpp)

• View this file on GitHub
• Last update: 2024-11-18 03:54:10+09:00
• Include: #include "lib/data_structure/persistent_queue.hpp"

Depends on

• Persistent Array (永続配列) (lib/data_structure/persistent_array.hpp)

Verified with

• test/library_checker/data_structure/persistent_queue.test.cpp

Code

#pragma once

/**
 * @brief Persistent Queue (永続キュー)
 */

#include <vector>

#include "../data_structure/persistent_array.hpp"

template<typename T>
struct PersistentQueue{
    PersistentArray<T> data;
    using node = typename PersistentArray<T>::Node *;
    std::vector<node> nodes;
    std::vector<int> front, back;
    int nxt = 1;

    PersistentQueue(int N) : nodes(N), front(N), back(N){
        nodes[0] = data.get_root();
    }

    int size(const int t) const {
        return back[t] - front[t];
    }

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

    T top(const int t) {
        return data.get(front[t], nodes[t]);
    }

    int pop(const int t){
        nodes[nxt] = nodes[t];
        front[nxt] = front[t] + 1;
        back[nxt] = back[t];
        return nxt++;
    }

    int push(const T &x, const int t){
        nodes[nxt] = data.set(back[t], x, nodes[t]);
        front[nxt] = front[t];
        back[nxt] = back[t] + 1;
        return nxt++;
    }
};

#line 2 "lib/data_structure/persistent_queue.hpp"

/**
 * @brief Persistent Queue (永続キュー)
 */

#include <vector>

#line 2 "lib/data_structure/persistent_array.hpp"

/**
 * @brief Persistent Array (永続配列)
 */

#include <cstring>

template<typename T>
struct PersistentArray{
    struct Node{
        T data;
        Node *ch[20] = {};
    };
    Node *root = nullptr;

    PersistentArray() {}

    Node *get_root(){
        return root;
    }

    void destructive_set(const int i, const T &val, Node *&t){
        if(!t) t = new Node();
        if(i == 0){
            t->data = val;
        } else{
            destructive_set(i / 20, val, t->ch[i % 20]);
        }
    }

    Node *set(const int i, const T &val, Node *&t){
        Node *res = new Node();
        if(t){
            std::memcpy(res->ch, t->ch, sizeof(t->ch));
            res->data = t->data;
        }
        if(i == 0){
            res->data = val;
        } else{
            res->ch[i % 20] = set(i / 20, val, res->ch[i % 20]);
        }
        return res;
    }

    T get(const int i, Node *t){
        if(!t) return T();
        if(i == 0){
            return t->data;
        } else{
            return get(i / 20, t->ch[i % 20]);
        }
    }
};
#line 10 "lib/data_structure/persistent_queue.hpp"

template<typename T>
struct PersistentQueue{
    PersistentArray<T> data;
    using node = typename PersistentArray<T>::Node *;
    std::vector<node> nodes;
    std::vector<int> front, back;
    int nxt = 1;

    PersistentQueue(int N) : nodes(N), front(N), back(N){
        nodes[0] = data.get_root();
    }

    int size(const int t) const {
        return back[t] - front[t];
    }

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

    T top(const int t) {
        return data.get(front[t], nodes[t]);
    }

    int pop(const int t){
        nodes[nxt] = nodes[t];
        front[nxt] = front[t] + 1;
        back[nxt] = back[t];
        return nxt++;
    }

    int push(const T &x, const int t){
        nodes[nxt] = data.set(back[t], x, nodes[t]);
        front[nxt] = front[t];
        back[nxt] = back[t] + 1;
        return nxt++;
    }
};

Back to top page