test/unittest/operate-aggregations.test.cpp

• View this file on GitHub
• Last update: 2026-08-04 11:55:02+00:00

Depends on

• Deque Operate Aggregation (structure/others/deque-operate-aggregation.hpp)
• Queue Operate Aggregation (structure/others/queue-operate-aggregation.hpp)

Code

// competitive-verifier: STANDALONE

#include <cassert>
#include <deque>
#include <random>
#include <string>

#include "../../structure/others/deque-operate-aggregation.hpp"
#include "../../structure/others/queue-operate-aggregation.hpp"

std::string naive_product(const std::deque<std::string>& values) {
  std::string result;
  for (const auto& value : values) result += value;
  return result;
}

int main() {
  const auto concatenate = [](const std::string& a, const std::string& b) {
    return a + b;
  };
  {
    auto queue = get_queue_operate_aggregation<std::string>(concatenate);
    assert(queue.empty());
    queue.push("a");
    queue.push("bc");
    assert(queue.size() == 2);
    assert(queue.all_prod() == "abc");
    queue.pop();
    assert(queue.all_prod() == "bc");
    queue.pop();
    assert(queue.empty());
  }

  auto deque = get_deque_operate_aggregation<std::string>(concatenate);
  std::deque<std::string> expected;
  std::mt19937 rng(123456789);
  for (int iteration = 0; iteration < 5000; iteration++) {
    int operation = expected.empty() ? rng() % 2 : rng() % 4;
    if (operation == 0) {
      std::string value(1, (char)('a' + rng() % 26));
      deque.push_front(value);
      expected.push_front(value);
    } else if (operation == 1) {
      std::string value(1, (char)('a' + rng() % 26));
      deque.push_back(value);
      expected.push_back(value);
    } else if (operation == 2) {
      deque.pop_front();
      expected.pop_front();
    } else {
      deque.pop_back();
      expected.pop_back();
    }

    assert(deque.empty() == expected.empty());
    assert(deque.size() == expected.size());
    if (!expected.empty()) assert(deque.all_prod() == naive_product(expected));
  }
}

#line 1 "test/unittest/operate-aggregations.test.cpp"
// competitive-verifier: STANDALONE

#include <cassert>
#include <deque>
#include <random>
#include <string>

#line 2 "structure/others/deque-operate-aggregation.hpp"

#line 4 "structure/others/deque-operate-aggregation.hpp"
#include <cstddef>
#include <vector>

template <typename T, typename F>
struct DequeOperateAggregation {
 private:
  struct Node {
    T val, sum;

    Node(const T& val, const T& sum) : val(val), sum(sum) {}
  };
  const F f;
  std::vector<Node> st[2];

  void rebuild() {
    if (not st[0].empty()) {
      st[0][0].sum = st[0][0].val;
      for (int i = 1; i < (int)st[0].size(); i++) {
        st[0][i].sum = f(st[0][i].val, st[0][i - 1].sum);
      }
    }
    if (not st[1].empty()) {
      st[1][0].sum = st[1][0].val;
      for (int i = 1; i < (int)st[1].size(); i++) {
        st[1][i].sum = f(st[1][i - 1].sum, st[1][i].val);
      }
    }
  }

 public:
  DequeOperateAggregation() = default;

  explicit DequeOperateAggregation(F f) : f(f) {}

  bool empty() const { return st[0].empty() and st[1].empty(); }

  std::size_t size() const { return st[0].size() + st[1].size(); }

  T all_prod() const {
    assert(not empty());
    if (st[0].empty()) {
      return st[1].back().sum;
    } else if (st[1].empty()) {
      return st[0].back().sum;
    } else {
      return f(st[0].back().sum, st[1].back().sum);
    }
  }

  void push_front(const T& x) {
    if (st[0].empty()) {
      st[0].emplace_back(x, x);
    } else {
      st[0].emplace_back(x, f(x, st[0].back().sum));
    }
  }

  void push_back(const T& x) {
    if (st[1].empty()) {
      st[1].emplace_back(x, x);
    } else {
      st[1].emplace_back(x, f(st[1].back().sum, x));
    }
  }

  void pop_front() {
    assert(not empty());
    if (st[0].empty()) {
      auto m = st[1].size() / 2;
      st[0] = {st[1].rbegin() + m, st[1].rend()};
      st[1] = {st[1].end() - m, st[1].end()};
      rebuild();
    }
    st[0].pop_back();
  }

  void pop_back() {
    assert(not empty());
    if (st[1].empty()) {
      auto m = st[0].size() / 2;
      st[1] = {st[0].rbegin() + m, st[0].rend()};
      st[0] = {st[0].end() - m, st[0].end()};
      rebuild();
    }
    st[1].pop_back();
  }
};

template <typename T, typename F>
DequeOperateAggregation<T, F> get_deque_operate_aggregation(const F& f) {
  return DequeOperateAggregation<T, F>{f};
}
#line 2 "structure/others/queue-operate-aggregation.hpp"

#line 6 "structure/others/queue-operate-aggregation.hpp"

template <typename T, typename F>
struct QueueOperateAggregation {
 private:
  struct Node {
    T val, sum;

    Node(const T& val, const T& sum) : val(val), sum(sum) {}
  };
  const F f;
  std::vector<Node> st[2];

 public:
  QueueOperateAggregation() = default;

  explicit QueueOperateAggregation(F f) : f(f) {}

  bool empty() const { return st[0].empty() and st[1].empty(); }

  std::size_t size() const { return st[0].size() + st[1].size(); }

  T all_prod() const {
    assert(not empty());
    if (st[0].empty()) {
      return st[1].back().sum;
    } else if (st[1].empty()) {
      return st[0].back().sum;
    } else {
      return f(st[0].back().sum, st[1].back().sum);
    }
  }

  void push(const T& x) {
    if (st[1].empty()) {
      st[1].emplace_back(x, x);
    } else {
      st[1].emplace_back(x, f(st[1].back().sum, x));
    }
  }

  void pop() {
    assert(not empty());
    if (st[0].empty()) {
      st[0].emplace_back(st[1].back().val, st[1].back().val);
      st[1].pop_back();
      while (not st[1].empty()) {
        st[0].emplace_back(st[1].back().val,
                           f(st[1].back().val, st[0].back().sum));
        st[1].pop_back();
      }
    }
    st[0].pop_back();
  }
};

template <typename T, typename F>
QueueOperateAggregation<T, F> get_queue_operate_aggregation(const F& f) {
  return QueueOperateAggregation<T, F>{f};
}
#line 10 "test/unittest/operate-aggregations.test.cpp"

std::string naive_product(const std::deque<std::string>& values) {
  std::string result;
  for (const auto& value : values) result += value;
  return result;
}

int main() {
  const auto concatenate = [](const std::string& a, const std::string& b) {
    return a + b;
  };
  {
    auto queue = get_queue_operate_aggregation<std::string>(concatenate);
    assert(queue.empty());
    queue.push("a");
    queue.push("bc");
    assert(queue.size() == 2);
    assert(queue.all_prod() == "abc");
    queue.pop();
    assert(queue.all_prod() == "bc");
    queue.pop();
    assert(queue.empty());
  }

  auto deque = get_deque_operate_aggregation<std::string>(concatenate);
  std::deque<std::string> expected;
  std::mt19937 rng(123456789);
  for (int iteration = 0; iteration < 5000; iteration++) {
    int operation = expected.empty() ? rng() % 2 : rng() % 4;
    if (operation == 0) {
      std::string value(1, (char)('a' + rng() % 26));
      deque.push_front(value);
      expected.push_front(value);
    } else if (operation == 1) {
      std::string value(1, (char)('a' + rng() % 26));
      deque.push_back(value);
      expected.push_back(value);
    } else if (operation == 2) {
      deque.pop_front();
      expected.pop_front();
    } else {
      deque.pop_back();
      expected.pop_back();
    }

    assert(deque.empty() == expected.empty());
    assert(deque.size() == expected.size());
    if (!expected.empty()) assert(deque.all_prod() == naive_product(expected));
  }
}

Back to top page