persistent_queue.hpp¶
维护可持久化队列，每次入队或出队都生成新版本；适合查询分叉历史中的队首与队列状态。
Complexity: Time: \(O(1)\) worst-case queue work per push/pop for \(O(1)\) value operations; \(O(K)\) to reclaim \(K\) unreachable nodes. Space: \(O(1)\) new nodes per operation, with \(O(K)\) worst-case stack for releasing a list.
Source: Library Checker
AC 记录：persistent_queue。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(1) worst-case queue work per push/pop for O(1) value
/// operations; O(K) to reclaim K unreachable nodes. Space: O(1) new nodes per
/// operation, with O(K) worst-case stack for releasing a list.
#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;
node_pointer rev;
template <class Pointer>
stream(const node_pointer &s0, Pointer &&r0)
: it(s0), rot(std::forward<Pointer>(r0)) {}
node_pointer next() {
// At rotation start the rear has one more element than the front.
if (rot) {
rev = make_node(rot->val, std::move(rev));
rot = rot->nxt;
}
if (!it) {
assert(!rot);
return std::move(rev);
}
node_pointer res = make_node(it->val, nullptr);
it = it->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
// NOYA_PERSISTENT_QUEUE_HPP
#ifndef NOYA_PERSISTENT_QUEUE_HPP
#define NOYA_PERSISTENT_QUEUE_HPP 1
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(1) worst-case queue work per push/pop for O(1) value
/// operations; O(K) to reclaim K unreachable nodes. Space: O(1) new nodes per
/// operation, with O(K) worst-case stack for releasing a list.
#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;
node_pointer rev;
template <class Pointer>
stream(const node_pointer &s0, Pointer &&r0)
: it(s0), rot(std::forward<Pointer>(r0)) {}
node_pointer next() {
// At rotation start the rear has one more element than the front.
if (rot) {
rev = make_node(rot->val, std::move(rev));
rot = rot->nxt;
}
if (!it) {
assert(!rot);
return std::move(rev);
}
node_pointer res = make_node(it->val, nullptr);
it = it->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
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(1) worst-case queue work per push/pop for O(1) value
/// operations; O(K) to reclaim K unreachable nodes. Space: O(1) new nodes per
/// operation, with O(K) worst-case stack for releasing a list.
#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;
node_pointer rev;
template <class Pointer>
stream(const node_pointer &s0, Pointer &&r0)
: it(s0), rot(std::forward<Pointer>(r0)) {}
node_pointer next() {
// At rotation start the rear has one more element than the front.
if (rot) {
rev = make_node(rot->val, std::move(rev));
rot = rot->nxt;
}
if (!it) {
assert(!rot);
return std::move(rev);
}
node_pointer res = make_node(it->val, nullptr);
it = it->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
// NOYA_PERSISTENT_QUEUE_HPP