m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Sliding Window Aggregation Deque
(ds/range_query/sliding_window_aggregation_deque.hpp)

Overview

SlidingWindowAggregationDeque<Monoid> maintains a deque and the monoid product of all its elements. It is the double-ended version of sliding window aggregation (SWAG): elements can be inserted or removed at either end.

The deque is stored in two aggregate stacks. When one stack is empty, the elements are split approximately in half between the stacks. This gives amortized constant-time updates while keeping the total product available in constant time.

SwagDeque<Monoid> is a shorter alias.

Template Requirements

Monoid must satisfy m1une::monoid::IsMonoid. Its value_type must be copy-constructible, and Monoid::op(a, b) must be associative with identity Monoid::id().

The product follows deque order:

\[a_0 \mathbin{\mathrm{op}} a_1 \mathbin{\mathrm{op}} \cdots \mathbin{\mathrm{op}} a_{n-1}.\]

The monoid does not need to be commutative.

Methods

Method Description Complexity
SlidingWindowAggregationDeque() Constructs an empty deque. $O(1)$
SlidingWindowAggregationDeque(const std::vector<T>& values) Constructs a deque containing values in order. $O(N)$
SlidingWindowAggregationDeque(std::vector<T>&& values) Constructs a deque containing values in order, moving the values. $O(N)$
void push_front(T value) Inserts value at the front. Amortized $O(1)$
void push_back(T value) Inserts value at the back. Amortized $O(1)$
void pop_front() Removes the front element. Amortized $O(1)$
void pop_back() Removes the back element. Amortized $O(1)$
const T& front() Returns the front element. Amortized $O(1)$
const T& back() Returns the back element. Amortized $O(1)$
T prod() const, T all_prod() const Returns the ordered product, or the identity when empty. $O(1)$
std::size_t size() const Returns the number of elements. $O(1)$
bool empty() const Returns whether the deque is empty. $O(1)$
void clear() Removes every element. $O(N)$
void reserve(std::size_t capacity) Reserves both internal stacks. $O(N)$

pop_front, pop_back, front, and back require a nonempty deque.

Example

This maintains a string under updates at both ends:

#include "ds/range_query/sliding_window_aggregation_deque.hpp"

#include <iostream>
#include <string>

struct Concat {
    using value_type = std::string;

    static value_type id() {
        return "";
    }

    static value_type op(const value_type& left, const value_type& right) {
        return left + right;
    }
};

int main() {
    m1une::ds::SwagDeque<Concat> deque;
    deque.push_back("b");
    deque.push_front("a");
    deque.push_back("c");
    std::cout << deque.prod() << "\n";  // abc

    deque.pop_front();
    std::cout << deque.prod() << "\n";  // bc
}

Depends on

Verified with

Code

#ifndef M1UNE_DS_RANGE_QUERY_SLIDING_WINDOW_AGGREGATION_DEQUE_HPP
#define M1UNE_DS_RANGE_QUERY_SLIDING_WINDOW_AGGREGATION_DEQUE_HPP 1

#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

#include "../../monoid/concept.hpp"

namespace m1une {
namespace ds {

// A deque supporting the ordered product of all elements in amortized O(1).
template <m1une::monoid::IsMonoid Monoid>
struct SlidingWindowAggregationDeque {
    using T = typename Monoid::value_type;

   private:
    struct Entry {
        T value;
        T product;
    };

    // The back of _front is the front of the deque. _back is in deque order.
    std::vector<Entry> _front;
    std::vector<Entry> _back;

    void rebalance(bool need_front) {
        assert(empty() == false);

        std::vector<T> values;
        values.reserve(size());
        for (auto iter = _front.rbegin(); iter != _front.rend(); ++iter) {
            values.push_back(std::move(iter->value));
        }
        for (Entry& entry : _back) values.push_back(std::move(entry.value));

        _front.clear();
        _back.clear();

        const std::size_t front_size = need_front ? (values.size() + 1) / 2 : values.size() / 2;
        for (std::size_t index = front_size; index > 0; --index) {
            push_front(std::move(values[index - 1]));
        }
        for (std::size_t index = front_size; index < values.size(); ++index) {
            push_back(std::move(values[index]));
        }
    }

    void ensure_front() {
        if (_front.empty()) rebalance(true);
    }

    void ensure_back() {
        if (_back.empty()) rebalance(false);
    }

   public:
    SlidingWindowAggregationDeque() = default;

    explicit SlidingWindowAggregationDeque(const std::vector<T>& values) {
        reserve(values.size());
        for (const T& value : values) push_back(value);
    }

    explicit SlidingWindowAggregationDeque(std::vector<T>&& values) {
        reserve(values.size());
        for (T& value : values) push_back(std::move(value));
    }

    std::size_t size() const {
        return _front.size() + _back.size();
    }

    bool empty() const {
        return _front.empty() && _back.empty();
    }

    void reserve(std::size_t capacity) {
        _front.reserve(capacity);
        _back.reserve(capacity);
    }

    void clear() {
        _front.clear();
        _back.clear();
    }

    void push_front(T value) {
        T product = _front.empty() ? value : Monoid::op(value, _front.back().product);
        _front.push_back(Entry{
            std::move(value),
            std::move(product),
        });
    }

    void push_back(T value) {
        T product = _back.empty() ? value : Monoid::op(_back.back().product, value);
        _back.push_back(Entry{
            std::move(value),
            std::move(product),
        });
    }

    void pop_front() {
        assert(!empty());
        ensure_front();
        _front.pop_back();
    }

    void pop_back() {
        assert(!empty());
        ensure_back();
        _back.pop_back();
    }

    const T& front() {
        assert(!empty());
        ensure_front();
        return _front.back().value;
    }

    const T& back() {
        assert(!empty());
        ensure_back();
        return _back.back().value;
    }

    // Returns the product in deque order, or the identity when empty.
    T prod() const {
        if (_front.empty()) {
            return _back.empty() ? Monoid::id() : _back.back().product;
        }
        if (_back.empty()) return _front.back().product;
        return Monoid::op(_front.back().product, _back.back().product);
    }

    T all_prod() const {
        return prod();
    }
};

template <m1une::monoid::IsMonoid Monoid>
using SwagDeque = SlidingWindowAggregationDeque<Monoid>;

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_RANGE_QUERY_SLIDING_WINDOW_AGGREGATION_DEQUE_HPP
#line 1 "ds/range_query/sliding_window_aggregation_deque.hpp"



#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

#line 1 "monoid/concept.hpp"



#include <concepts>

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 10 "ds/range_query/sliding_window_aggregation_deque.hpp"

namespace m1une {
namespace ds {

// A deque supporting the ordered product of all elements in amortized O(1).
template <m1une::monoid::IsMonoid Monoid>
struct SlidingWindowAggregationDeque {
    using T = typename Monoid::value_type;

   private:
    struct Entry {
        T value;
        T product;
    };

    // The back of _front is the front of the deque. _back is in deque order.
    std::vector<Entry> _front;
    std::vector<Entry> _back;

    void rebalance(bool need_front) {
        assert(empty() == false);

        std::vector<T> values;
        values.reserve(size());
        for (auto iter = _front.rbegin(); iter != _front.rend(); ++iter) {
            values.push_back(std::move(iter->value));
        }
        for (Entry& entry : _back) values.push_back(std::move(entry.value));

        _front.clear();
        _back.clear();

        const std::size_t front_size = need_front ? (values.size() + 1) / 2 : values.size() / 2;
        for (std::size_t index = front_size; index > 0; --index) {
            push_front(std::move(values[index - 1]));
        }
        for (std::size_t index = front_size; index < values.size(); ++index) {
            push_back(std::move(values[index]));
        }
    }

    void ensure_front() {
        if (_front.empty()) rebalance(true);
    }

    void ensure_back() {
        if (_back.empty()) rebalance(false);
    }

   public:
    SlidingWindowAggregationDeque() = default;

    explicit SlidingWindowAggregationDeque(const std::vector<T>& values) {
        reserve(values.size());
        for (const T& value : values) push_back(value);
    }

    explicit SlidingWindowAggregationDeque(std::vector<T>&& values) {
        reserve(values.size());
        for (T& value : values) push_back(std::move(value));
    }

    std::size_t size() const {
        return _front.size() + _back.size();
    }

    bool empty() const {
        return _front.empty() && _back.empty();
    }

    void reserve(std::size_t capacity) {
        _front.reserve(capacity);
        _back.reserve(capacity);
    }

    void clear() {
        _front.clear();
        _back.clear();
    }

    void push_front(T value) {
        T product = _front.empty() ? value : Monoid::op(value, _front.back().product);
        _front.push_back(Entry{
            std::move(value),
            std::move(product),
        });
    }

    void push_back(T value) {
        T product = _back.empty() ? value : Monoid::op(_back.back().product, value);
        _back.push_back(Entry{
            std::move(value),
            std::move(product),
        });
    }

    void pop_front() {
        assert(!empty());
        ensure_front();
        _front.pop_back();
    }

    void pop_back() {
        assert(!empty());
        ensure_back();
        _back.pop_back();
    }

    const T& front() {
        assert(!empty());
        ensure_front();
        return _front.back().value;
    }

    const T& back() {
        assert(!empty());
        ensure_back();
        return _back.back().value;
    }

    // Returns the product in deque order, or the identity when empty.
    T prod() const {
        if (_front.empty()) {
            return _back.empty() ? Monoid::id() : _back.back().product;
        }
        if (_back.empty()) return _front.back().product;
        return Monoid::op(_front.back().product, _back.back().product);
    }

    T all_prod() const {
        return prod();
    }
};

template <m1une::monoid::IsMonoid Monoid>
using SwagDeque = SlidingWindowAggregationDeque<Monoid>;

}  // namespace ds
}  // namespace m1une
Back to top page