persistent_queue.hpp¶
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.
Verified by persistent_queue.
维护可持久化队列，每次入队或出队都生成新版本；适合查询分叉历史中的队首与队列状态。
Implementation¶
#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 value;
node_pointer next;
template <class Pointer>
node(T value_, Pointer &&next_)
: value(std::move(value_)), next(std::forward<Pointer>(next_)) {}
};
template <class... Arguments>
static node_pointer make_node(Arguments &&...arguments) {
return std::make_shared<node>(std::forward<Arguments>(arguments)...);
}
struct stream {
node_pointer scan;
node_pointer rotate;
template <class Pointer>
stream(const node_pointer &scan_, Pointer &&rotate_)
: scan(scan_), rotate(std::forward<Pointer>(rotate_)) {}
node_pointer next() {
node_pointer result;
if (scan) {
result = make_node(scan->value, nullptr);
scan = scan->next;
} else {
while (rotate) {
result = make_node(rotate->value, std::move(result));
rotate = rotate->next;
}
}
return result;
}
};
template <class... Arguments>
static stream_pointer make_stream(Arguments &&...arguments) {
return std::make_shared<stream>(std::forward<Arguments>(arguments)...);
}
node_pointer front_list;
node *progress = nullptr;
stream_pointer rotation;
node_pointer back_list;
explicit persistent_queue(stream_pointer rotation_)
: front_list(rotation_->next()), progress(front_list.get()),
rotation(std::move(rotation_)) {}
template <class Pointer>
persistent_queue(const node_pointer &front_, node *progress_,
const stream_pointer &rotation_, Pointer &&back_)
: front_list(front_), progress(progress_), rotation(rotation_),
back_list(std::forward<Pointer>(back_)) {}
public:
persistent_queue() = default;
bool empty() const { return !front_list; }
const T &front() const {
assert(!empty());
return front_list->value;
}
self push(T value) const {
if (!progress) {
return self(make_stream(front_list,
make_node(std::move(value), back_list)));
}
if (!progress->next) {
progress->next = rotation->next();
}
return self(front_list, progress->next.get(), rotation,
make_node(std::move(value), back_list));
}
self pop() const {
assert(!empty());
if (!progress) {
return self(make_stream(front_list->next, back_list));
}
if (!progress->next) {
progress->next = rotation->next();
}
return self(front_list->next, progress->next.get(), rotation, back_list);
}
};
} // 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 value;
node_pointer next;
template <class Pointer>
node(T value_, Pointer &&next_)
: value(std::move(value_)), next(std::forward<Pointer>(next_)) {}
};
template <class... Arguments>
static node_pointer make_node(Arguments &&...arguments) {
return std::make_shared<node>(std::forward<Arguments>(arguments)...);
}
struct stream {
node_pointer scan;
node_pointer rotate;
template <class Pointer>
stream(const node_pointer &scan_, Pointer &&rotate_)
: scan(scan_), rotate(std::forward<Pointer>(rotate_)) {}
node_pointer next() {
node_pointer result;
if (scan) {
result = make_node(scan->value, nullptr);
scan = scan->next;
} else {
while (rotate) {
result = make_node(rotate->value, std::move(result));
rotate = rotate->next;
}
}
return result;
}
};
template <class... Arguments>
static stream_pointer make_stream(Arguments &&...arguments) {
return std::make_shared<stream>(std::forward<Arguments>(arguments)...);
}
node_pointer front_list;
node *progress = nullptr;
stream_pointer rotation;
node_pointer back_list;
explicit persistent_queue(stream_pointer rotation_)
: front_list(rotation_->next()), progress(front_list.get()),
rotation(std::move(rotation_)) {}
template <class Pointer>
persistent_queue(const node_pointer &front_, node *progress_,
const stream_pointer &rotation_, Pointer &&back_)
: front_list(front_), progress(progress_), rotation(rotation_),
back_list(std::forward<Pointer>(back_)) {}
public:
persistent_queue() = default;
bool empty() const { return !front_list; }
const T &front() const {
assert(!empty());
return front_list->value;
}
self push(T value) const {
if (!progress) {
return self(make_stream(front_list,
make_node(std::move(value), back_list)));
}
if (!progress->next) {
progress->next = rotation->next();
}
return self(front_list, progress->next.get(), rotation,
make_node(std::move(value), back_list));
}
self pop() const {
assert(!empty());
if (!progress) {
return self(make_stream(front_list->next, back_list));
}
if (!progress->next) {
progress->next = rotation->next();
}
return self(front_list->next, progress->next.get(), rotation, back_list);
}
};
} // namespace noya