Sliding Window Aggregation (Queue)
(data_structure/queue_aggregation.hpp)

• View this file on GitHub
• Last update: 2023-09-10 00:45:18+09:00
• Include: #include "data_structure/queue_aggregation.hpp"
• Link: https://scrapbox.io/data-structures/Sliding_Window_Aggregation

説明

半群の列$(a_0,a_1, \dots, a_{n-1})$を扱う. 詳しくは https://scrapbox.io/data-structures/Sliding_Window_Aggregation 参照

コンストラクタ

queue_aggregation<Semigroup, op> swag;

• 型Semigroup
• 二項演算Semigroup op(Semigroup, Semigroup)

を定義する必要がある.例としてスライド最小値ならば以下のようになる.

int op(int a, int b) {
    return std::min(a,b);
}
queue_aggregation<int, op> swag;

Operations

• fold_all()
  • $op(a_0, a_1, \dots, a_{n-1})$ を計算する
  • 時間計算量$O(1)$
• front()
  • 　先頭要素を返す
  • 時間計算量 $O(1)$ amortized
• push(Semigroup x)
  • $x$ を末尾に追加する
  • 時間計算量 $O(1)$
• pop()
  • 先頭を削除する
  • 時間計算量 $O(1)$ amortized
• empty()
  • 空であるときtrueを返す
  • 時間計算量 $O(1)$
• size()
  • 要素数を求める
  • 時間計算量 $O(1)$

Verified with

• test/data_structure/Queue_Operate_All_Composite.test.cpp

Code

#pragma once

/*
    reference: https://scrapbox.io/data-structures/Sliding_Window_Aggregation
*/

#include <cassert>

#include <stack>


namespace ebi {

template <class Semigroup, Semigroup (*op)(Semigroup, Semigroup)>
struct queue_aggregation {
  private:
    struct Node {
        Semigroup val;
        Semigroup fold;
    };

    void move() {
        assert(!_back.empty());
        Node p = _back.top();
        _back.pop();
        _front.push({p.val, p.val});
        while (!_back.empty()) {
            Semigroup x = _back.top().val;
            _back.pop();
            _front.push({x, op(x, _front.top().fold)});
        }
    }

  public:
    queue_aggregation() {}

    int size() {
        return _front.size() + _back.size();
    }

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

    void push(Semigroup x) {
        Node node = {x, x};
        if (!_back.empty()) {
            node.fold = op(_back.top().fold, x);
        }
        _back.push(node);
    }

    Semigroup front() {
        assert(!empty());
        if (_front.empty()) {
            move();
        }
        return _front.top().val;
    }

    void pop() {
        assert(!empty());
        if (_front.empty()) {
            move();
        }
        _front.pop();
    }

    void clear() {
        _front = std::stack<Node>();
        _back = std::stack<Node>();
    }

    Semigroup fold_all() {
        assert(!empty());
        if (_front.empty()) {
            return _back.top().fold;
        } else if (_back.empty()) {
            return _front.top().fold;
        } else {
            return op(_front.top().fold, _back.top().fold);
        }
    }

  private:
    std::stack<Node> _front, _back;
};

}  // namespace ebi

#line 2 "data_structure/queue_aggregation.hpp"

/*
    reference: https://scrapbox.io/data-structures/Sliding_Window_Aggregation
*/

#include <cassert>

#include <stack>


namespace ebi {

template <class Semigroup, Semigroup (*op)(Semigroup, Semigroup)>
struct queue_aggregation {
  private:
    struct Node {
        Semigroup val;
        Semigroup fold;
    };

    void move() {
        assert(!_back.empty());
        Node p = _back.top();
        _back.pop();
        _front.push({p.val, p.val});
        while (!_back.empty()) {
            Semigroup x = _back.top().val;
            _back.pop();
            _front.push({x, op(x, _front.top().fold)});
        }
    }

  public:
    queue_aggregation() {}

    int size() {
        return _front.size() + _back.size();
    }

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

    void push(Semigroup x) {
        Node node = {x, x};
        if (!_back.empty()) {
            node.fold = op(_back.top().fold, x);
        }
        _back.push(node);
    }

    Semigroup front() {
        assert(!empty());
        if (_front.empty()) {
            move();
        }
        return _front.top().val;
    }

    void pop() {
        assert(!empty());
        if (_front.empty()) {
            move();
        }
        _front.pop();
    }

    void clear() {
        _front = std::stack<Node>();
        _back = std::stack<Node>();
    }

    Semigroup fold_all() {
        assert(!empty());
        if (_front.empty()) {
            return _back.top().fold;
        } else if (_back.empty()) {
            return _front.top().fold;
        } else {
            return op(_front.top().fold, _back.top().fold);
        }
    }

  private:
    std::stack<Node> _front, _back;
};

}  // namespace ebi

Back to top page