1 | // |
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #pragma once |
10 | |
11 | #include <immer/detail/rbts/rrbtree.hpp> |
12 | #include <immer/detail/rbts/rrbtree_iterator.hpp> |
13 | #include <immer/memory_policy.hpp> |
14 | |
15 | namespace immer { |
16 | |
17 | template <typename T, |
18 | typename MemoryPolicy, |
19 | detail::rbts::bits_t B, |
20 | detail::rbts::bits_t BL> |
21 | class flex_vector; |
22 | |
23 | template <typename T, |
24 | typename MemoryPolicy, |
25 | detail::rbts::bits_t B, |
26 | detail::rbts::bits_t BL> |
27 | class vector_transient; |
28 | |
29 | /*! |
30 | * Mutable version of `immer::flex_vector`. |
31 | * |
32 | * @rst |
33 | * |
34 | * Refer to :doc:`transients` to learn more about when and how to use |
35 | * the mutable versions of immutable containers. |
36 | * |
37 | * @endrst |
38 | */ |
39 | template <typename T, |
40 | typename MemoryPolicy = default_memory_policy, |
41 | detail::rbts::bits_t B = default_bits, |
42 | detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>> |
43 | class flex_vector_transient |
44 | : MemoryPolicy::transience_t::owner |
45 | { |
46 | using impl_t = detail::rbts::rrbtree<T, MemoryPolicy, B, BL>; |
47 | using base_t = typename MemoryPolicy::transience_t::owner; |
48 | using owner_t = typename MemoryPolicy::transience_t::owner; |
49 | |
50 | public: |
51 | static constexpr auto bits = B; |
52 | static constexpr auto bits_leaf = BL; |
53 | using memory_policy = MemoryPolicy; |
54 | |
55 | using value_type = T; |
56 | using reference = const T&; |
57 | using size_type = detail::rbts::size_t; |
58 | using difference_type = std::ptrdiff_t; |
59 | using const_reference = const T&; |
60 | |
61 | using iterator = detail::rbts::rrbtree_iterator<T, MemoryPolicy, B, BL>; |
62 | using const_iterator = iterator; |
63 | using reverse_iterator = std::reverse_iterator<iterator>; |
64 | |
65 | using persistent_type = flex_vector<T, MemoryPolicy, B, BL>; |
66 | |
67 | /*! |
68 | * Default constructor. It creates a flex_vector of `size() == 0`. It |
69 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
70 | */ |
71 | flex_vector_transient() = default; |
72 | |
73 | /*! |
74 | * Default constructor. It creates a flex_vector with the same |
75 | * contents as `v`. It does not allocate memory and is |
76 | * @f$ O(1) @f$. |
77 | */ |
78 | flex_vector_transient(vector_transient<T, MemoryPolicy, B, BL> v) |
79 | : base_t { std::move(static_cast<base_t&>(v)) } |
80 | , impl_ { v.impl_.size, v.impl_.shift, |
81 | v.impl_.root->inc(), v.impl_.tail->inc() } |
82 | {} |
83 | |
84 | /*! |
85 | * Returns an iterator pointing at the first element of the |
86 | * collection. It does not allocate memory and its complexity is |
87 | * @f$ O(1) @f$. |
88 | */ |
89 | IMMER_NODISCARD iterator begin() const { return {impl_}; } |
90 | |
91 | /*! |
92 | * Returns an iterator pointing just after the last element of the |
93 | * collection. It does not allocate and its complexity is @f$ O(1) @f$. |
94 | */ |
95 | IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; } |
96 | |
97 | /*! |
98 | * Returns an iterator that traverses the collection backwards, |
99 | * pointing at the first element of the reversed collection. It |
100 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
101 | */ |
102 | IMMER_NODISCARD reverse_iterator rbegin() const { return reverse_iterator{end()}; } |
103 | |
104 | /*! |
105 | * Returns an iterator that traverses the collection backwards, |
106 | * pointing after the last element of the reversed collection. It |
107 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
108 | */ |
109 | IMMER_NODISCARD reverse_iterator rend() const { return reverse_iterator{begin()}; } |
110 | |
111 | /*! |
112 | * Returns the number of elements in the container. It does |
113 | * not allocate memory and its complexity is @f$ O(1) @f$. |
114 | */ |
115 | IMMER_NODISCARD size_type size() const { return impl_.size; } |
116 | |
117 | /*! |
118 | * Returns `true` if there are no elements in the container. It |
119 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
120 | */ |
121 | IMMER_NODISCARD bool empty() const { return impl_.size == 0; } |
122 | |
123 | /*! |
124 | * Returns a `const` reference to the element at position `index`. |
125 | * It is undefined when @f$ 0 index \geq size() @f$. It does not |
126 | * allocate memory and its complexity is *effectively* @f$ O(1) |
127 | * @f$. |
128 | */ |
129 | reference operator[] (size_type index) const |
130 | { return impl_.get(index); } |
131 | |
132 | /*! |
133 | * Returns a `const` reference to the element at position |
134 | * `index`. It throws an `std::out_of_range` exception when @f$ |
135 | * index \geq size() @f$. It does not allocate memory and its |
136 | * complexity is *effectively* @f$ O(1) @f$. |
137 | */ |
138 | reference at(size_type index) const |
139 | { return impl_.get_check(index); } |
140 | |
141 | /*! |
142 | * Inserts `value` at the end. It may allocate memory and its |
143 | * complexity is *effectively* @f$ O(1) @f$. |
144 | */ |
145 | void push_back(value_type value) |
146 | { impl_.push_back_mut(*this, std::move(value)); } |
147 | |
148 | /*! |
149 | * Sets to the value `value` at position `idx`. |
150 | * Undefined for `index >= size()`. |
151 | * It may allocate memory and its complexity is |
152 | * *effectively* @f$ O(1) @f$. |
153 | */ |
154 | void set(size_type index, value_type value) |
155 | { impl_.assoc_mut(*this, index, std::move(value)); } |
156 | |
157 | /*! |
158 | * Updates the vector to contain the result of the expression |
159 | * `fn((*this)[idx])` at position `idx`. |
160 | * Undefined for `0 >= size()`. |
161 | * It may allocate memory and its complexity is |
162 | * *effectively* @f$ O(1) @f$. |
163 | */ |
164 | template <typename FnT> |
165 | void update(size_type index, FnT&& fn) |
166 | { impl_.update_mut(*this, index, std::forward<FnT>(fn)); } |
167 | |
168 | /*! |
169 | * Resizes the vector to only contain the first `min(elems, size())` |
170 | * elements. It may allocate memory and its complexity is |
171 | * *effectively* @f$ O(1) @f$. |
172 | */ |
173 | void take(size_type elems) |
174 | { impl_.take_mut(*this, elems); } |
175 | |
176 | /*! |
177 | * Removes the first the first `min(elems, size())` |
178 | * elements. It may allocate memory and its complexity is |
179 | * *effectively* @f$ O(1) @f$. |
180 | */ |
181 | void drop(size_type elems) |
182 | { impl_.drop_mut(*this, elems); } |
183 | |
184 | /*! |
185 | * Appends the contents of the `r` at the end. It may allocate |
186 | * memory and its complexity is: |
187 | * @f$ O(log(max(size_r, size_l))) @f$ |
188 | */ |
189 | void append(flex_vector_transient& r) |
190 | { |
191 | r.owner_t::operator=(owner_t{}); |
192 | concat_mut_l(impl_, *this, r.impl_); |
193 | } |
194 | void append(flex_vector_transient&& r) |
195 | { concat_mut_lr_l(impl_, *this, r.impl_, r); } |
196 | |
197 | /*! |
198 | * Prepends the contents of the `l` at the beginning. It may |
199 | * allocate memory and its complexity is: |
200 | * @f$ O(log(max(size_r, size_l))) @f$ |
201 | */ |
202 | void prepend(flex_vector_transient& l) |
203 | { |
204 | l.owner_t::operator=(owner_t{}); |
205 | concat_mut_r(l.impl_, impl_, *this); |
206 | } |
207 | void prepend(flex_vector_transient&& l) |
208 | { concat_mut_lr_r(l.impl_, l, impl_, *this); } |
209 | |
210 | /*! |
211 | * Returns an @a immutable form of this container, an |
212 | * `immer::flex_vector`. |
213 | */ |
214 | IMMER_NODISCARD persistent_type persistent() & |
215 | { |
216 | this->owner_t::operator=(owner_t{}); |
217 | return persistent_type{ impl_ }; |
218 | } |
219 | IMMER_NODISCARD persistent_type persistent() && |
220 | { return persistent_type{ std::move(impl_) }; } |
221 | |
222 | private: |
223 | friend persistent_type; |
224 | |
225 | flex_vector_transient(impl_t impl) |
226 | : impl_(std::move(impl)) |
227 | {} |
228 | |
229 | impl_t impl_ = impl_t::empty(); |
230 | }; |
231 | |
232 | } // namespace immer |
233 | |