DESWAG
(lib/data_structure/deswag.hpp)

• View this file on GitHub
• Last update: 2024-11-01 15:41:30+09:00
• Include: #include "lib/data_structure/deswag.hpp"

DESWAG

使い方

• DESWAG<T>(op): 両端 SWAG を構築します。
• fold(): 要素全てに op を適用させた値を計算します。
• push_front(x): x を先頭に追加します。
• push_back(x): x を末尾に追加します。
• pop_front(): 先頭の要素を削除します。
• pop_back(): 末尾の要素を削除します。

計算量

• fold(): $\mathrm{O}(1)$
• push_front(x): $\mathrm{O}(1)$
• push_back(x): $\mathrm{O}(1)$
• pop_front(): 償却 $\mathrm{O}(1)$
• pop_back(): 償却 $\mathrm{O}(1)$

Verified with

• test/library_checker/data_structure/deque_operate_all_composite.test.cpp

Code

#pragma once

/**
 * @brief DESWAG
 * @docs docs/data_structure/deswag.md
 */

#include <stack>
#include <cassert>

template <typename T, T (*op)(T, T)>
struct DESWAG{
private:
    struct node{
    public:
        T val, sum;
        node(const T &val, const T &sum) : val(val), sum(sum) {}
    };

    std::stack<node> front_stack, back_stack, temp_stack;

public:
    DESWAG() : front_stack(), back_stack(), temp_stack() {}

    bool empty(){
        return front_stack.empty() && back_stack.empty();
    }

    size_t size(){
        return front_stack.size() + back_stack.size();
    }

    T fold(){
        if(front_stack.empty()){
            return back_stack.top().sum;
        } else if(back_stack.empty()){
            return front_stack.top().sum;
        } else{
            return op(front_stack.top().sum, back_stack.top().sum);
        }
    }

    void push_front(const T &x){
        if(front_stack.empty()){
            front_stack.emplace(x, x);
        } else{
            T s = op(x, front_stack.top().sum);
            front_stack.emplace(x, s);
        }
    }

    void push_back(const T &x){
        if(back_stack.empty()){
            back_stack.emplace(x, x);
        } else{
            T s = op(back_stack.top().sum, x);
            back_stack.emplace(x, s);
        }
    }

    void pop_front(){
        if(front_stack.empty()){
            size_t half = (back_stack.size() + 1) / 2;
            while(!back_stack.empty()){
                if(back_stack.size() == half){
                    front_stack.emplace(back_stack.top().val, back_stack.top().val);
                } else if(back_stack.size() < half){
                    T s = op(back_stack.top().val, front_stack.top().sum);
                    front_stack.emplace(back_stack.top().val, s);
                } else{
                    temp_stack.emplace(back_stack.top().val, back_stack.top().val);
                }
                back_stack.pop();
            }
            if(!temp_stack.empty()){
                back_stack.emplace(temp_stack.top().val, temp_stack.top().val);
                temp_stack.pop();
                while(!temp_stack.empty()){
                    T s = op(back_stack.top().sum, temp_stack.top().val);
                    back_stack.emplace(temp_stack.top().val, s);
                    temp_stack.pop();
                }
            }
        }
        front_stack.pop();
    }

    void pop_back(){
        if(back_stack.empty()){
            size_t half = (front_stack.size() + 1) / 2;
            while(!front_stack.empty()){
                if(front_stack.size() == half){
                    back_stack.emplace(front_stack.top().val, front_stack.top().val);
                } else if(front_stack.size() < half){
                    T s = op(back_stack.top().sum, front_stack.top().val);
                    back_stack.emplace(front_stack.top().val, s);
                } else{
                    temp_stack.emplace(front_stack.top().val, front_stack.top().val);
                }
                front_stack.pop();
            }
            if(!temp_stack.empty()){
                front_stack.emplace(temp_stack.top().val, temp_stack.top().val);
                temp_stack.pop();
                while(!temp_stack.empty()){
                    T s = op(temp_stack.top().val, front_stack.top().sum);
                    front_stack.emplace(temp_stack.top().val, s);
                    temp_stack.pop();
                }
            }
        }
        back_stack.pop();
    }
};

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

/**
 * @brief DESWAG
 * @docs docs/data_structure/deswag.md
 */

#include <stack>
#include <cassert>

template <typename T, T (*op)(T, T)>
struct DESWAG{
private:
    struct node{
    public:
        T val, sum;
        node(const T &val, const T &sum) : val(val), sum(sum) {}
    };

    std::stack<node> front_stack, back_stack, temp_stack;

public:
    DESWAG() : front_stack(), back_stack(), temp_stack() {}

    bool empty(){
        return front_stack.empty() && back_stack.empty();
    }

    size_t size(){
        return front_stack.size() + back_stack.size();
    }

    T fold(){
        if(front_stack.empty()){
            return back_stack.top().sum;
        } else if(back_stack.empty()){
            return front_stack.top().sum;
        } else{
            return op(front_stack.top().sum, back_stack.top().sum);
        }
    }

    void push_front(const T &x){
        if(front_stack.empty()){
            front_stack.emplace(x, x);
        } else{
            T s = op(x, front_stack.top().sum);
            front_stack.emplace(x, s);
        }
    }

    void push_back(const T &x){
        if(back_stack.empty()){
            back_stack.emplace(x, x);
        } else{
            T s = op(back_stack.top().sum, x);
            back_stack.emplace(x, s);
        }
    }

    void pop_front(){
        if(front_stack.empty()){
            size_t half = (back_stack.size() + 1) / 2;
            while(!back_stack.empty()){
                if(back_stack.size() == half){
                    front_stack.emplace(back_stack.top().val, back_stack.top().val);
                } else if(back_stack.size() < half){
                    T s = op(back_stack.top().val, front_stack.top().sum);
                    front_stack.emplace(back_stack.top().val, s);
                } else{
                    temp_stack.emplace(back_stack.top().val, back_stack.top().val);
                }
                back_stack.pop();
            }
            if(!temp_stack.empty()){
                back_stack.emplace(temp_stack.top().val, temp_stack.top().val);
                temp_stack.pop();
                while(!temp_stack.empty()){
                    T s = op(back_stack.top().sum, temp_stack.top().val);
                    back_stack.emplace(temp_stack.top().val, s);
                    temp_stack.pop();
                }
            }
        }
        front_stack.pop();
    }

    void pop_back(){
        if(back_stack.empty()){
            size_t half = (front_stack.size() + 1) / 2;
            while(!front_stack.empty()){
                if(front_stack.size() == half){
                    back_stack.emplace(front_stack.top().val, front_stack.top().val);
                } else if(front_stack.size() < half){
                    T s = op(back_stack.top().sum, front_stack.top().val);
                    back_stack.emplace(front_stack.top().val, s);
                } else{
                    temp_stack.emplace(front_stack.top().val, front_stack.top().val);
                }
                front_stack.pop();
            }
            if(!temp_stack.empty()){
                front_stack.emplace(temp_stack.top().val, temp_stack.top().val);
                temp_stack.pop();
                while(!temp_stack.empty()){
                    T s = op(temp_stack.top().val, front_stack.top().sum);
                    front_stack.emplace(temp_stack.top().val, s);
                    temp_stack.pop();
                }
            }
        }
        back_stack.pop();
    }
};

Back to top page