persistent_queue.hpp

SECTIONData Structure INCLUDEnoya/persistent_queue.hpp

维护可持久化队列，每次入队或出队都生成新版本；适合查询分叉历史中的队首与队列状态。

Complexity: Time: O(1) worst-case per push/pop. Space: O(1) new nodes per operation, excluding shared ownership metadata.

AC 记录：persistent_queue。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(1) worst-case per push/pop.  Space: O(1) new nodes per
/// operation, excluding shared ownership metadata.

#include <cassert>
#include <memory>
#include <utility>

namespace noya {

/// @brief Fully persistent FIFO queue using an incrementally evaluated list
/// rotation.  Each new version performs one step of reversing the rear list;
/// the memoized stream node is shared by every branch that reaches it, so no
/// operation has to finish an entire reversal at once.
template <class T> class persistent_queue {
  using self = persistent_queue<T>;
  struct node;
  using node_pointer = std::shared_ptr<node>;
  struct stream;
  using stream_pointer = std::shared_ptr<stream>;

  struct node {
    T val;
    node_pointer nxt;

    template <class Pointer>
    node(T v0, Pointer &&n0)
        : val(std::move(v0)), nxt(std::forward<Pointer>(n0)) {}
  };

  template <class... Arguments>
  static node_pointer make_node(Arguments &&...xs) {
    return std::make_shared<node>(std::forward<Arguments>(xs)...);
  }

  struct stream {
    node_pointer it;
    node_pointer rot;

    template <class Pointer>
    stream(const node_pointer &s0, Pointer &&r0)
        : it(s0), rot(std::forward<Pointer>(r0)) {}

    node_pointer next() {
      node_pointer res;
      if (it) {
        res = make_node(it->val, nullptr);
        it = it->nxt;
      } else {
        while (rot) {
          res = make_node(rot->val, std::move(res));
          rot = rot->nxt;
        }
      }
      return res;
    }
  };

  template <class... Arguments>
  static stream_pointer make_stream(Arguments &&...xs) {
    return std::make_shared<stream>(std::forward<Arguments>(xs)...);
  }

  node_pointer fq;
  node *ptr = nullptr;
  stream_pointer ro0;
  node_pointer bq;

  explicit persistent_queue(stream_pointer r00)
      : fq(r00->next()), ptr(fq.get()), ro0(std::move(r00)) {}

  template <class Pointer>
  persistent_queue(const node_pointer &f0, node *p0, const stream_pointer &r00,
                   Pointer &&b0)
      : fq(f0), ptr(p0), ro0(r00), bq(std::forward<Pointer>(b0)) {}

public:
  persistent_queue() = default;

  bool empty() const { return !fq; }

  const T &front() const {
    assert(!empty());
    return fq->val;
  }

  self push(T val) const {
    if (!ptr) {
      return self(make_stream(fq, make_node(std::move(val), bq)));
    }
    if (!ptr->nxt) {
      ptr->nxt = ro0->next();
    }
    return self(fq, ptr->nxt.get(), ro0, make_node(std::move(val), bq));
  }

  self pop() const {
    assert(!empty());
    if (!ptr) {
      return self(make_stream(fq->nxt, bq));
    }
    if (!ptr->nxt) {
      ptr->nxt = ro0->next();
    }
    return self(fq->nxt, ptr->nxt.get(), ro0, bq);
  }
};

} // namespace noya

#ifndef NOYA_PERSISTENT_QUEUE_HPP
#define NOYA_PERSISTENT_QUEUE_HPP 1

/// @complexity Time: O(1) worst-case per push/pop.  Space: O(1) new nodes per
/// operation, excluding shared ownership metadata.

#include <cassert>
#include <memory>
#include <utility>

namespace noya {

/// @brief Fully persistent FIFO queue using an incrementally evaluated list
/// rotation.  Each new version performs one step of reversing the rear list;
/// the memoized stream node is shared by every branch that reaches it, so no
/// operation has to finish an entire reversal at once.
template <class T> class persistent_queue {
  using self = persistent_queue<T>;
  struct node;
  using node_pointer = std::shared_ptr<node>;
  struct stream;
  using stream_pointer = std::shared_ptr<stream>;

  struct node {
    T val;
    node_pointer nxt;

    template <class Pointer>
    node(T v0, Pointer &&n0)
        : val(std::move(v0)), nxt(std::forward<Pointer>(n0)) {}
  };

  template <class... Arguments>
  static node_pointer make_node(Arguments &&...xs) {
    return std::make_shared<node>(std::forward<Arguments>(xs)...);
  }

  struct stream {
    node_pointer it;
    node_pointer rot;

    template <class Pointer>
    stream(const node_pointer &s0, Pointer &&r0)
        : it(s0), rot(std::forward<Pointer>(r0)) {}

    node_pointer next() {
      node_pointer res;
      if (it) {
        res = make_node(it->val, nullptr);
        it = it->nxt;
      } else {
        while (rot) {
          res = make_node(rot->val, std::move(res));
          rot = rot->nxt;
        }
      }
      return res;
    }
  };

  template <class... Arguments>
  static stream_pointer make_stream(Arguments &&...xs) {
    return std::make_shared<stream>(std::forward<Arguments>(xs)...);
  }

  node_pointer fq;
  node *ptr = nullptr;
  stream_pointer ro0;
  node_pointer bq;

  explicit persistent_queue(stream_pointer r00)
      : fq(r00->next()), ptr(fq.get()), ro0(std::move(r00)) {}

  template <class Pointer>
  persistent_queue(const node_pointer &f0, node *p0, const stream_pointer &r00,
                   Pointer &&b0)
      : fq(f0), ptr(p0), ro0(r00), bq(std::forward<Pointer>(b0)) {}

public:
  persistent_queue() = default;

  bool empty() const { return !fq; }

  const T &front() const {
    assert(!empty());
    return fq->val;
  }

  self push(T val) const {
    if (!ptr) {
      return self(make_stream(fq, make_node(std::move(val), bq)));
    }
    if (!ptr->nxt) {
      ptr->nxt = ro0->next();
    }
    return self(fq, ptr->nxt.get(), ro0, make_node(std::move(val), bq));
  }

  self pop() const {
    assert(!empty());
    if (!ptr) {
      return self(make_stream(fq->nxt, bq));
    }
    if (!ptr->nxt) {
      ptr->nxt = ro0->next();
    }
    return self(fq->nxt, ptr->nxt.get(), ro0, bq);
  }
};

} // namespace noya

#endif // NOYA_PERSISTENT_QUEUE_HPP

#include <cassert>
#include <memory>
#include <utility>

/// @complexity Time: O(1) worst-case per push/pop.  Space: O(1) new nodes per
/// operation, excluding shared ownership metadata.

namespace noya {

/// @brief Fully persistent FIFO queue using an incrementally evaluated list
/// rotation.  Each new version performs one step of reversing the rear list;
/// the memoized stream node is shared by every branch that reaches it, so no
/// operation has to finish an entire reversal at once.
template <class T> class persistent_queue {
  using self = persistent_queue<T>;
  struct node;
  using node_pointer = std::shared_ptr<node>;
  struct stream;
  using stream_pointer = std::shared_ptr<stream>;

  struct node {
    T val;
    node_pointer nxt;

    template <class Pointer>
    node(T v0, Pointer &&n0)
        : val(std::move(v0)), nxt(std::forward<Pointer>(n0)) {}
  };

  template <class... Arguments>
  static node_pointer make_node(Arguments &&...xs) {
    return std::make_shared<node>(std::forward<Arguments>(xs)...);
  }

  struct stream {
    node_pointer it;
    node_pointer rot;

    template <class Pointer>
    stream(const node_pointer &s0, Pointer &&r0)
        : it(s0), rot(std::forward<Pointer>(r0)) {}

    node_pointer next() {
      node_pointer res;
      if (it) {
        res = make_node(it->val, nullptr);
        it = it->nxt;
      } else {
        while (rot) {
          res = make_node(rot->val, std::move(res));
          rot = rot->nxt;
        }
      }
      return res;
    }
  };

  template <class... Arguments>
  static stream_pointer make_stream(Arguments &&...xs) {
    return std::make_shared<stream>(std::forward<Arguments>(xs)...);
  }

  node_pointer fq;
  node *ptr = nullptr;
  stream_pointer ro0;
  node_pointer bq;

  explicit persistent_queue(stream_pointer r00)
      : fq(r00->next()), ptr(fq.get()), ro0(std::move(r00)) {}

  template <class Pointer>
  persistent_queue(const node_pointer &f0, node *p0, const stream_pointer &r00,
                   Pointer &&b0)
      : fq(f0), ptr(p0), ro0(r00), bq(std::forward<Pointer>(b0)) {}

public:
  persistent_queue() = default;

  bool empty() const { return !fq; }

  const T &front() const {
    assert(!empty());
    return fq->val;
  }

  self push(T val) const {
    if (!ptr) {
      return self(make_stream(fq, make_node(std::move(val), bq)));
    }
    if (!ptr->nxt) {
      ptr->nxt = ro0->next();
    }
    return self(fq, ptr->nxt.get(), ro0, make_node(std::move(val), bq));
  }

  self pop() const {
    assert(!empty());
    if (!ptr) {
      return self(make_stream(fq->nxt, bq));
    }
    if (!ptr->nxt) {
      ptr->nxt = ro0->next();
    }
    return self(fq->nxt, ptr->nxt.get(), ro0, bq);
  }
};

} // namespace noya