Sliding window aggregation (tools/swag.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-11-05 13:33:02+09:00
• Include: #include "tools/swag.hpp"

It is a data structure which supports the following operations.

• Create an empty sequence of elements on a given monoid in $O(1)$.
• Add an element to the sequence as the first element in $O(1)$.
• Add an element to the sequence as the last element in $O(1)$.
• Remove the first element from the sequence in $O(1)$ amortized.
• Remove the last element from the sequence in $O(1)$ amortized.
• Calculate the production on the monoid of all elements in the sequence, in $O(1)$.

License

• CC0

Author

• anqooqie

Constructor

template <typename M>
swag<M> swag();

It creates an empty sequence of elements on a given monoid $M$.

Constraints

• For all $a$ in typename M::T, $b$ in typename M::T and $c$ in typename M::T, M::op(M::op(a, b), c) $=$ M::op(a, M::op(b, c)).
• For all $a$ in typename M::T, M::op(M::e(), a) $=$ M::op(a, M::e()) $=$ a.

Time Complexity

• $O(1)$

empty

bool swag.empty();

It returns whether the sequence is empty or not.

Constraints

• None

Time Complexity

• $O(1)$

push_front

void swag.push_front(typename M::T x);

It adds an element $x$ to the sequence as the first element.

Constraints

• None

Time Complexity

• $O(1)$

emplace_front

template <typename... Args>
void swag.emplace_front(Args&&... args);

It adds an element typename M::T(args...) to the sequence as the first element.

Constraints

• None

Time Complexity

• $O(1)$

push_back

void swag.push_back(typename M::T x);

It adds an element $x$ to the sequence as the last element.

Constraints

• None

Time Complexity

• $O(1)$

emplace_back

template <typename... Args>
void swag.emplace_back(Args&&... args);

It adds an element typename M::T(args...) to the sequence as the last element.

Constraints

• None

Time Complexity

• $O(1)$

pop_front

void swag.pop_front();

It removes the first element from the sequence.

Constraints

• The sequence is not empty.

Time Complexity

• $O(1)$ amortized

pop_back

void swag.pop_back();

It removes the last element from the sequence.

Constraints

• The sequence is not empty.

Time Complexity

• $O(1)$ amortized

prod

typename M::T swag.prod();

It returns the production on the monoid of all elements in the sequence.

Constraints

• None

Time Complexity

• $O(1)$

Verified with

• tests/swag.test.cpp

Code

#ifndef TOOLS_SWAG_HPP
#define TOOLS_SWAG_HPP

#include <stack>
#include <utility>
#include <cassert>

namespace tools {
  template <typename M>
  class swag {
  private:
    using T = typename M::T;
    ::std::stack<::std::pair<T, T>> m_head;
    ::std::stack<::std::pair<T, T>> m_tail;

    T head_prod() const {
      return this->m_head.empty() ? M::e() : this->m_head.top().second;
    }
    T tail_prod() const {
      return this->m_tail.empty() ? M::e() : this->m_tail.top().second;
    }

  public:
    swag() = default;
    swag(const ::tools::swag<M>&) = default;
    swag(::tools::swag<M>&&) = default;
    ~swag() = default;
    ::tools::swag<M>& operator=(const ::tools::swag<M>&) = default;
    ::tools::swag<M>& operator=(::tools::swag<M>&&) = default;

    bool empty() const {
      return this->m_head.empty() && this->m_tail.empty();
    }

    void push_back(const T& x) {
      this->m_tail.emplace(x, M::op(this->tail_prod(), x));
    }

    template <typename... Args>
    void emplace_back(Args&&... args) {
      this->push_back(T(::std::forward<Args>(args)...));
    }

    void pop_back() {
      assert(!this->empty());
      if (this->m_tail.empty()) {
        ::std::stack<T> tmp;
        while (tmp.size() + 1 < this->m_head.size()) {
          tmp.push(this->m_head.top().first);
          this->m_head.pop();
        }
        while (!this->m_head.empty()) {
          this->m_tail.emplace(this->m_head.top().first, M::op(this->tail_prod(), this->m_head.top().first));
          this->m_head.pop();
        }
        while (!tmp.empty()) {
          this->m_head.emplace(tmp.top(), M::op(tmp.top(), this->head_prod()));
          tmp.pop();
        }
      }
      this->m_tail.pop();
    }

    void push_front(const T& x) {
      this->m_head.emplace(x, M::op(x, this->head_prod()));
    }

    template <typename... Args>
    void emplace_front(Args&&... args) {
      this->push_front(T(::std::forward<Args>(args)...));
    }

    void pop_front() {
      assert(!this->empty());
      if (this->m_head.empty()) {
        ::std::stack<T> tmp;
        while (this->m_tail.size() > tmp.size() + 1) {
          tmp.push(this->m_tail.top().first);
          this->m_tail.pop();
        }
        while (!this->m_tail.empty()) {
          this->m_head.emplace(this->m_tail.top().first, M::op(this->m_tail.top().first, this->head_prod()));
          this->m_tail.pop();
        }
        while (!tmp.empty()) {
          this->m_tail.emplace(tmp.top(), M::op(this->tail_prod(), tmp.top()));
          tmp.pop();
        }
      }
      this->m_head.pop();
    }

    T prod() const {
      return M::op(this->head_prod(), this->tail_prod());
    }
  };
}

#endif

#line 1 "tools/swag.hpp"



#include <stack>
#include <utility>
#include <cassert>

namespace tools {
  template <typename M>
  class swag {
  private:
    using T = typename M::T;
    ::std::stack<::std::pair<T, T>> m_head;
    ::std::stack<::std::pair<T, T>> m_tail;

    T head_prod() const {
      return this->m_head.empty() ? M::e() : this->m_head.top().second;
    }
    T tail_prod() const {
      return this->m_tail.empty() ? M::e() : this->m_tail.top().second;
    }

  public:
    swag() = default;
    swag(const ::tools::swag<M>&) = default;
    swag(::tools::swag<M>&&) = default;
    ~swag() = default;
    ::tools::swag<M>& operator=(const ::tools::swag<M>&) = default;
    ::tools::swag<M>& operator=(::tools::swag<M>&&) = default;

    bool empty() const {
      return this->m_head.empty() && this->m_tail.empty();
    }

    void push_back(const T& x) {
      this->m_tail.emplace(x, M::op(this->tail_prod(), x));
    }

    template <typename... Args>
    void emplace_back(Args&&... args) {
      this->push_back(T(::std::forward<Args>(args)...));
    }

    void pop_back() {
      assert(!this->empty());
      if (this->m_tail.empty()) {
        ::std::stack<T> tmp;
        while (tmp.size() + 1 < this->m_head.size()) {
          tmp.push(this->m_head.top().first);
          this->m_head.pop();
        }
        while (!this->m_head.empty()) {
          this->m_tail.emplace(this->m_head.top().first, M::op(this->tail_prod(), this->m_head.top().first));
          this->m_head.pop();
        }
        while (!tmp.empty()) {
          this->m_head.emplace(tmp.top(), M::op(tmp.top(), this->head_prod()));
          tmp.pop();
        }
      }
      this->m_tail.pop();
    }

    void push_front(const T& x) {
      this->m_head.emplace(x, M::op(x, this->head_prod()));
    }

    template <typename... Args>
    void emplace_front(Args&&... args) {
      this->push_front(T(::std::forward<Args>(args)...));
    }

    void pop_front() {
      assert(!this->empty());
      if (this->m_head.empty()) {
        ::std::stack<T> tmp;
        while (this->m_tail.size() > tmp.size() + 1) {
          tmp.push(this->m_tail.top().first);
          this->m_tail.pop();
        }
        while (!this->m_tail.empty()) {
          this->m_head.emplace(this->m_tail.top().first, M::op(this->m_tail.top().first, this->head_prod()));
          this->m_tail.pop();
        }
        while (!tmp.empty()) {
          this->m_tail.emplace(tmp.top(), M::op(this->tail_prod(), tmp.top()));
          tmp.pop();
        }
      }
      this->m_head.pop();
    }

    T prod() const {
      return M::op(this->head_prod(), this->tail_prod());
    }
  };
}

Back to top page