Realtime Queue
(data_structure/realtime_queue.cpp)

• View this file on GitHub
• Last update: 2020-03-16 22:45:32+09:00
• Link: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Depends on

• Persistent Stack (data_structure/persistent_stack.cpp)
• Stream (data_structure/stream.cpp)
• Suspension (other/suspension.cpp)

Verified with

• test/realtime_queue.test.cpp

Code

#include "data_structure/persistent_stack.cpp"
#include "data_structure/stream.cpp"

#include <cassert>
#include <utility>

template <class T> class realtime_queue {
  using Self = realtime_queue<T>;
  using stream_type = stream<T>;
  using cell_type = typename stream_type::cell_type;
  using stack_type = persistent_stack<T>;

public:
  using value_type = T;

private:
  static stream_type rotate(stream_type f, stack_type b, stream_type t) {
    return stream_type([f, b, t]() {
      if (f.empty())
        return cell_type(std::in_place, b.top(), t);
      else
        return cell_type(std::in_place, f.top(),
                         rotate(f.pop(), b.pop(), t.push(b.top())));
    });
  }

  static Self make_queue(stream_type f, stack_type b, stream_type s) {
    if (not s.empty())
      return Self(f, b, s.pop());
    stream_type temp = rotate(f, b, stream_type());
    return Self(temp, stack_type(), temp);
  }

  stream_type front_;
  stack_type back_;
  stream_type schedule;

  realtime_queue(stream_type f, stack_type b, stream_type s)
      : front_(f), back_(b), schedule(s) {}

public:
  realtime_queue() = default;

  bool empty() const { return front_.empty(); }

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

    return front_.top();
  }

  Self push(T x) const { return make_queue(front_, back_.push(x), schedule); }

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

    return make_queue(front_.pop(), back_, schedule);
  }
};

/**
 * @brief Realtime Queue
 * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
 */

#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 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 2 "data_structure/stream.cpp"

#line 4 "data_structure/stream.cpp"
#include <optional>
#line 6 "data_structure/stream.cpp"

template <class T>
class stream : private suspension<std::optional<std::pair<T, stream<T>>>> {
  using Self = stream<T>;

public:
  using value_type = T;
  using cell_type = std::optional<std::pair<T, Self>>;

private:
  using base_type = suspension<cell_type>;

  stream(T x, Self s)
      : base_type(std::in_place, cell_type(std::in_place, x, s)) {}

public:
  stream() : base_type(std::in_place, cell_type(std::nullopt)) {}

  stream(std::function<cell_type()> f) : base_type(f) {}

  using base_type::force;

  bool empty() const { return not force().has_value(); }

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

    return (*force()).first;
  }

  Self push(T x) const { return Self(x, *this); }

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

    return (*force()).second;
  }

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

  friend Self operator+(Self l, Self r) {
    return Self([l, r]() {
      if (l.empty())
        return r.force();
      else
        return cell_type(std::in_place, l.top(), l.pop() + r);
    });
  }
};

/**
 * @brief Stream
 * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
 */
#line 3 "data_structure/realtime_queue.cpp"

#line 6 "data_structure/realtime_queue.cpp"

template <class T> class realtime_queue {
  using Self = realtime_queue<T>;
  using stream_type = stream<T>;
  using cell_type = typename stream_type::cell_type;
  using stack_type = persistent_stack<T>;

public:
  using value_type = T;

private:
  static stream_type rotate(stream_type f, stack_type b, stream_type t) {
    return stream_type([f, b, t]() {
      if (f.empty())
        return cell_type(std::in_place, b.top(), t);
      else
        return cell_type(std::in_place, f.top(),
                         rotate(f.pop(), b.pop(), t.push(b.top())));
    });
  }

  static Self make_queue(stream_type f, stack_type b, stream_type s) {
    if (not s.empty())
      return Self(f, b, s.pop());
    stream_type temp = rotate(f, b, stream_type());
    return Self(temp, stack_type(), temp);
  }

  stream_type front_;
  stack_type back_;
  stream_type schedule;

  realtime_queue(stream_type f, stack_type b, stream_type s)
      : front_(f), back_(b), schedule(s) {}

public:
  realtime_queue() = default;

  bool empty() const { return front_.empty(); }

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

    return front_.top();
  }

  Self push(T x) const { return make_queue(front_, back_.push(x), schedule); }

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

    return make_queue(front_.pop(), back_, schedule);
  }
};

/**
 * @brief Realtime Queue
 * @see https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
 */

Back to top page