1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123 | #pragma once
#include <memory><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <type_traits><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <memory_resource><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include "data_structure/internal/node_handler.hpp"
#include "internal/dev_env.hpp"
#include "internal/types.hpp"
namespace uni {
template<class ValueType, class Allocator = std::allocator<ValueType>>
struct persistent_stack {
using value_type = ValueType;
using size_type = internal::size_t;
struct node_type;
using node_handler = node_handlers::cloneable<Allocator>::template handler<node_type>;
using allocator_type = typename node_handler::allocator_type;
using node_pointer = typename node_handler::node_pointer;
struct node_type {
value_type value;
node_pointer next;
node_type(node_pointer _next, value_type _value) noexcept(NO_EXCEPT)
: value(_value), next(_next)
{}
template<class... Args>
node_type(node_pointer _next, Args&&... args) noexcept(NO_EXCEPT)
: value(std::forward<Args>(args)...), next(_next)
{}
};
private:
size_type _size = 0;
node_pointer _head;
[[no_unique_address]] node_handler _node_handler;
public:
explicit persistent_stack(const allocator_type& allocator = allocator_type()) noexcept(NO_EXCEPT) : _node_handler(allocator) {};
persistent_stack(const persistent_stack& source, const allocator_type& allocator) noexcept(NO_EXCEPT)
: _size(source._size), _head(source._head), _node_handler(allocator)
{};
persistent_stack(persistent_stack&& source, const allocator_type& allocator) noexcept(NO_EXCEPT)
: _size(source._size), _head(source._head), _node_handler(allocator)
{};
inline auto clone() const noexcept(NO_EXCEPT) { return *this; }
inline bool empty() const noexcept(NO_EXCEPT) { return !this->_head; }
inline size_type size() const noexcept(NO_EXCEPT) { return this->_size; }
inline value_type top() const noexcept(NO_EXCEPT) {
assert(!this->empty());
return this->_head->value;
}
template<std::convertible_to<value_type> T = value_type>
requires std::is_move_constructible_v<T>
inline value_type top_or(T&& v) const noexcept(NO_EXCEPT) {
if(this->empty()) return static_cast<value_type>(std::forward<T>(v));
else return this->top();
}
inline auto& clear() noexcept(NO_EXCEPT) {
this->_head.reset();
this->_size = 0;
return *this;
}
template<std::convertible_to<value_type> T = value_type>
inline auto& push(T&& x) noexcept(NO_EXCEPT) {
this->_head = this->_node_handler.create(this->_head, std::forward<T>(x));
++this->_size;
return *this;
}
template<class... Args>
inline auto& emplace(Args&&... args) noexcept(NO_EXCEPT) {
this->_head = this->_node_handler.create(this->_head, std::forward<Args>(args)...);
++this->_size;
return this->_head->value;
}
inline auto& pop() noexcept(NO_EXCEPT) {
assert(!this->empty());
this->_head = this->_head->next;
--this->_size;
return *this;
}
};
namespace pmr {
template<class T>
using persistent_stack = uni::persistent_stack<T, std::pmr::polymorphic_allocator<T>>;
} // namesapce pmr
} // namespace uni
|