test/physicists_queue.test.cpp

• View this file on GitHub
• Last update: 2020-03-18 22:48:14+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

• Persistent Stack (data_structure/persistent_stack.cpp)
• Physicist's Queue (data_structure/physicists_queue.cpp)
• other/fast_ios.cpp
• other/int_alias.cpp
• Suspension (other/suspension.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include "data_structure/physicists_queue.cpp"

#include <iostream>
#include <vector>

int main() {
#include "other/fast_ios.cpp"

  int q;
  std::cin >> q;

  std::vector<physicists_queue<int>> s_(q + 1);
  const auto s = s_.begin() + 1;

  for (int i = 0; i != q; i += 1) {
    int c;
    std::cin >> c;
    switch (c) {
    case 0: {
      int t, x;
      std::cin >> t >> x;
      s[i] = s[t].push(x);
    } break;
    case 1: {
      int t;
      std::cin >> t;
      std::cout << s[t].front() << "\n";
      s[i] = s[t].pop();
    }
    }
  }
}

#line 1 "test/physicists_queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#line 1 "data_structure/persistent_stack.cpp"
#include <cassert>
#include <memory>
#include <utility>

template <class T> class persistent_stack {
  using Self = persistent_stack<T>;
  class node_type;
  using node_ptr = std::shared_ptr<const node_type>;

  class node_type {
  public:
    T value;
    node_ptr next;

    node_type(T value, node_ptr next) : value(value), next(next) {}
  };

  node_ptr root;

  persistent_stack(node_ptr root) : root(root) {}

public:
  persistent_stack() = default;

  bool empty() const { return not root; }

  T top() const {
    assert(not empty());

    return root->value;
  }

  Self push(T x) const {
    return Self(std::make_shared<const node_type>(x, root));
  }

  Self pop() const {
    assert(not empty());

    return Self(root->next);
  }

  Self reverse() const {
    Self ret;
    Self x = *this;
    while (not x.empty()) {
      ret = ret.push(x.top());
      x = x.pop();
    }
    return ret;
  }
};

/**
 * @brief Persistent Stack
 */
#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 1 "other/suspension.cpp"
#include <functional>
#line 4 "other/suspension.cpp"
#include <variant>

template <class T>
class suspension
    : private std::shared_ptr<std::variant<T, std::function<T()>>> {
public:
  using value_type = T;
  using func_type = std::function<T()>;
  using node_type = std::variant<T, func_type>;

private:
  using base_type = std::shared_ptr<node_type>;

  static T get(node_type &x) {
    if (x.index() != 0)
      x = std::get<1>(x)();
    return std::get<0>(x);
  }

  template <class... Args> static base_type make_node(Args &&... args) {
    return std::make_shared<node_type>(std::forward<Args>(args)...);
  }

public:
  suspension(std::in_place_t, T x)
      : base_type(make_node(std::in_place_index<0>, x)) {}

  suspension(func_type f) : base_type(make_node(std::in_place_index<1>, f)) {}

  T force() const { return get(**this); }
};

/**
 * @brief Suspension
 * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
 */
#line 4 "data_structure/physicists_queue.cpp"

#line 7 "data_structure/physicists_queue.cpp"

template <class T> class physicists_queue {
  using Self = physicists_queue<T>;
  using stack_type = persistent_stack<T>;
  using susp_stack = suspension<stack_type>;

  stack_type working;
  susp_stack front_;
  usize f_size;
  stack_type back_;
  usize b_size;

  physicists_queue(stack_type working, susp_stack front_, usize f_size,
                   stack_type back_, usize b_size)
      : working(working), front_(front_), f_size(f_size), back_(back_),
        b_size(b_size) {}

  Self check_r() const {
    if (f_size >= b_size)
      return *this;
    stack_type temp = front_.force();
    auto f = [l = temp, r = back_]() mutable {
      r = r.reverse();
      l = l.reverse();
      while (not l.empty()) {
        r = r.push(l.top());
        l = l.pop();
      }
      return r;
    };
    return Self(temp, susp_stack(f), f_size + b_size, stack_type(), 0);
  }

  Self check_w() const {
    if (working.empty())
      return Self(front_.force(), front_, f_size, back_, b_size);
    else
      return *this;
  }

  Self check() const { return check_r().check_w(); }

public:
  physicists_queue()
      : working(), front_(std::in_place, stack_type()), f_size(0), back_(),
        b_size(0) {}

  bool empty() const { return f_size == 0; }

  T front() const {
    assert(not empty());

    return working.top();
  }

  Self push(T x) const {
    return Self(working, front_, f_size, back_.push(x), b_size + 1).check();
  }

  Self pop() const {
    assert(not empty());

    return Self(working.pop(),
                susp_stack([f = front_]() { return f.force().pop(); }),
                f_size - 1, back_, b_size)
        .check();
  }
};

/**
 * @brief Physicist's Queue
 * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
 */
#line 4 "test/physicists_queue.test.cpp"

#include <iostream>
#include <vector>

int main() {
#line 1 "other/fast_ios.cpp"
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#line 10 "test/physicists_queue.test.cpp"

  int q;
  std::cin >> q;

  std::vector<physicists_queue<int>> s_(q + 1);
  const auto s = s_.begin() + 1;

  for (int i = 0; i != q; i += 1) {
    int c;
    std::cin >> c;
    switch (c) {
    case 0: {
      int t, x;
      std::cin >> t >> x;
      s[i] = s[t].push(x);
    } break;
    case 1: {
      int t;
      std::cin >> t;
      std::cout << s[t].front() << "\n";
      s[i] = s[t].pop();
    }
    }
  }
}

Back to top page