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/rbtree.hpp> |
12 | #include <immer/detail/rbts/rbtree_iterator.hpp> |
13 | #include <immer/memory_policy.hpp> |
14 | |
15 | #if IMMER_DEBUG_PRINT |
16 | #include <immer/flex_vector.hpp> |
17 | #endif |
18 | |
19 | namespace immer { |
20 | |
21 | template <typename T, |
22 | typename MemoryPolicy, |
23 | detail::rbts::bits_t B, |
24 | detail::rbts::bits_t BL> |
25 | class flex_vector; |
26 | |
27 | template <typename T, |
28 | typename MemoryPolicy, |
29 | detail::rbts::bits_t B, |
30 | detail::rbts::bits_t BL> |
31 | class vector_transient; |
32 | |
33 | /*! |
34 | * Immutable sequential container supporting both random access and |
35 | * structural sharing. |
36 | * |
37 | * @tparam T The type of the values to be stored in the container. |
38 | * @tparam MemoryPolicy Memory management policy. See @ref |
39 | * memory_policy. |
40 | * |
41 | * @rst |
42 | * |
43 | * This cotainer provides a good trade-off between cache locality, |
44 | * random access, update performance and structural sharing. It does |
45 | * so by storing the data in contiguous chunks of :math:`2^{BL}` |
46 | * elements. By default, when ``sizeof(T) == sizeof(void*)`` then |
47 | * :math:`B=BL=5`, such that data would be stored in contiguous |
48 | * chunks of :math:`32` elements. |
49 | * |
50 | * You may learn more about the meaning and implications of ``B`` and |
51 | * ``BL`` parameters in the :doc:`implementation` section. |
52 | * |
53 | * .. note:: In several methods we say that their complexity is |
54 | * *effectively* :math:`O(...)`. Do not confuse this with the word |
55 | * *amortized*, which has a very different meaning. In this |
56 | * context, *effective* means that while the |
57 | * mathematically rigurous |
58 | * complexity might be higher, for all practical matters the |
59 | * provided complexity is more useful to think about the actual |
60 | * cost of the operation. |
61 | * |
62 | * **Example** |
63 | * .. literalinclude:: ../example/vector/intro.cpp |
64 | * :language: c++ |
65 | * :start-after: intro/start |
66 | * :end-before: intro/end |
67 | * |
68 | * @endrst |
69 | */ |
70 | template <typename T, |
71 | typename MemoryPolicy = default_memory_policy, |
72 | detail::rbts::bits_t B = default_bits, |
73 | detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>> |
74 | class vector |
75 | { |
76 | using impl_t = detail::rbts::rbtree<T, MemoryPolicy, B, BL>; |
77 | using flex_t = flex_vector<T, MemoryPolicy, B, BL>; |
78 | |
79 | using move_t = |
80 | std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>; |
81 | |
82 | public: |
83 | static constexpr auto bits = B; |
84 | static constexpr auto bits_leaf = BL; |
85 | using memory_policy = MemoryPolicy; |
86 | |
87 | using value_type = T; |
88 | using reference = const T&; |
89 | using size_type = detail::rbts::size_t; |
90 | using difference_type = std::ptrdiff_t; |
91 | using const_reference = const T&; |
92 | |
93 | using iterator = detail::rbts::rbtree_iterator<T, MemoryPolicy, B, BL>; |
94 | using const_iterator = iterator; |
95 | using reverse_iterator = std::reverse_iterator<iterator>; |
96 | |
97 | using transient_type = vector_transient<T, MemoryPolicy, B, BL>; |
98 | |
99 | /*! |
100 | * Default constructor. It creates a vector of `size() == 0`. It |
101 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
102 | */ |
103 | vector() = default; |
104 | |
105 | /*! |
106 | * Constructs a vector containing the elements in `values`. |
107 | */ |
108 | vector(std::initializer_list<T> values) |
109 | : impl_{impl_t::from_initializer_list(values)} |
110 | {} |
111 | |
112 | /*! |
113 | * Constructs a vector containing the elements in the range |
114 | * defined by the input iterator `first` and range sentinel `last`. |
115 | */ |
116 | template <typename Iter, typename Sent, |
117 | std::enable_if_t |
118 | <detail::compatible_sentinel_v<Iter, Sent>, bool> = true> |
119 | vector(Iter first, Sent last) |
120 | : impl_{impl_t::from_range(first, last)} |
121 | {} |
122 | |
123 | /*! |
124 | * Constructs a vector containing the element `val` repeated `n` |
125 | * times. |
126 | */ |
127 | vector(size_type n, T v = {}) |
128 | : impl_{impl_t::from_fill(n, v)} |
129 | {} |
130 | |
131 | /*! |
132 | * Returns an iterator pointing at the first element of the |
133 | * collection. It does not allocate memory and its complexity is |
134 | * @f$ O(1) @f$. |
135 | */ |
136 | IMMER_NODISCARD iterator begin() const { return {impl_}; } |
137 | |
138 | /*! |
139 | * Returns an iterator pointing just after the last element of the |
140 | * collection. It does not allocate and its complexity is @f$ O(1) @f$. |
141 | */ |
142 | IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; } |
143 | |
144 | /*! |
145 | * Returns an iterator that traverses the collection backwards, |
146 | * pointing at the first element of the reversed collection. It |
147 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
148 | */ |
149 | IMMER_NODISCARD reverse_iterator rbegin() const { return reverse_iterator{end()}; } |
150 | |
151 | /*! |
152 | * Returns an iterator that traverses the collection backwards, |
153 | * pointing after the last element of the reversed collection. It |
154 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
155 | */ |
156 | IMMER_NODISCARD reverse_iterator rend() const { return reverse_iterator{begin()}; } |
157 | |
158 | /*! |
159 | * Returns the number of elements in the container. It does |
160 | * not allocate memory and its complexity is @f$ O(1) @f$. |
161 | */ |
162 | IMMER_NODISCARD size_type size() const { return impl_.size; } |
163 | |
164 | /*! |
165 | * Returns `true` if there are no elements in the container. It |
166 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
167 | */ |
168 | IMMER_NODISCARD bool empty() const { return impl_.size == 0; } |
169 | |
170 | /*! |
171 | * Access the last element. |
172 | */ |
173 | IMMER_NODISCARD const T& back() const { return impl_.back(); } |
174 | |
175 | /*! |
176 | * Access the first element. |
177 | */ |
178 | IMMER_NODISCARD const T& front() const { return impl_.front(); } |
179 | |
180 | /*! |
181 | * Returns a `const` reference to the element at position `index`. |
182 | * It is undefined when @f$ 0 index \geq size() @f$. It does not |
183 | * allocate memory and its complexity is *effectively* @f$ O(1) |
184 | * @f$. |
185 | */ |
186 | IMMER_NODISCARD reference operator[] (size_type index) const |
187 | { return impl_.get(index); } |
188 | |
189 | /*! |
190 | * Returns a `const` reference to the element at position |
191 | * `index`. It throws an `std::out_of_range` exception when @f$ |
192 | * index \geq size() @f$. It does not allocate memory and its |
193 | * complexity is *effectively* @f$ O(1) @f$. |
194 | */ |
195 | reference at(size_type index) const |
196 | { return impl_.get_check(index); } |
197 | |
198 | /*! |
199 | * Returns whether the vectors are equal. |
200 | */ |
201 | IMMER_NODISCARD bool operator==(const vector& other) const |
202 | { return impl_.equals(other.impl_); } |
203 | IMMER_NODISCARD bool operator!=(const vector& other) const |
204 | { return !(*this == other); } |
205 | |
206 | /*! |
207 | * Returns a vector with `value` inserted at the end. It may |
208 | * allocate memory and its complexity is *effectively* @f$ O(1) @f$. |
209 | * |
210 | * @rst |
211 | * |
212 | * **Example** |
213 | * .. literalinclude:: ../example/vector/vector.cpp |
214 | * :language: c++ |
215 | * :dedent: 8 |
216 | * :start-after: push-back/start |
217 | * :end-before: push-back/end |
218 | * |
219 | * @endrst |
220 | */ |
221 | IMMER_NODISCARD vector push_back(value_type value) const& |
222 | { return impl_.push_back(std::move(value)); } |
223 | |
224 | IMMER_NODISCARD decltype(auto) push_back(value_type value) && |
225 | { return push_back_move(move_t{}, std::move(value)); } |
226 | |
227 | /*! |
228 | * Returns a vector containing value `value` at position `idx`. |
229 | * Undefined for `index >= size()`. |
230 | * It may allocate memory and its complexity is |
231 | * *effectively* @f$ O(1) @f$. |
232 | * |
233 | * @rst |
234 | * |
235 | * **Example** |
236 | * .. literalinclude:: ../example/vector/vector.cpp |
237 | * :language: c++ |
238 | * :dedent: 8 |
239 | * :start-after: set/start |
240 | * :end-before: set/end |
241 | * |
242 | * @endrst |
243 | */ |
244 | IMMER_NODISCARD vector set(size_type index, value_type value) const& |
245 | { return impl_.assoc(index, std::move(value)); } |
246 | |
247 | IMMER_NODISCARD decltype(auto) set(size_type index, value_type value) && |
248 | { return set_move(move_t{}, index, std::move(value)); } |
249 | |
250 | /*! |
251 | * Returns a vector containing the result of the expression |
252 | * `fn((*this)[idx])` at position `idx`. |
253 | * Undefined for `0 >= size()`. |
254 | * It may allocate memory and its complexity is |
255 | * *effectively* @f$ O(1) @f$. |
256 | * |
257 | * @rst |
258 | * |
259 | * **Example** |
260 | * .. literalinclude:: ../example/vector/vector.cpp |
261 | * :language: c++ |
262 | * :dedent: 8 |
263 | * :start-after: update/start |
264 | * :end-before: update/end |
265 | * |
266 | * @endrst |
267 | */ |
268 | template <typename FnT> |
269 | IMMER_NODISCARD vector update(size_type index, FnT&& fn) const& |
270 | { return impl_.update(index, std::forward<FnT>(fn)); } |
271 | |
272 | template <typename FnT> |
273 | IMMER_NODISCARD decltype(auto) update(size_type index, FnT&& fn) && |
274 | { return update_move(move_t{}, index, std::forward<FnT>(fn)); } |
275 | |
276 | /*! |
277 | * Returns a vector containing only the first `min(elems, size())` |
278 | * elements. It may allocate memory and its complexity is |
279 | * *effectively* @f$ O(1) @f$. |
280 | * |
281 | * @rst |
282 | * |
283 | * **Example** |
284 | * .. literalinclude:: ../example/vector/vector.cpp |
285 | * :language: c++ |
286 | * :dedent: 8 |
287 | * :start-after: take/start |
288 | * :end-before: take/end |
289 | * |
290 | * @endrst |
291 | */ |
292 | IMMER_NODISCARD vector take(size_type elems) const& |
293 | { return impl_.take(elems); } |
294 | |
295 | IMMER_NODISCARD decltype(auto) take(size_type elems) && |
296 | { return take_move(move_t{}, elems); } |
297 | |
298 | /*! |
299 | * Returns an @a transient form of this container, an |
300 | * `immer::vector_transient`. |
301 | */ |
302 | IMMER_NODISCARD transient_type transient() const& |
303 | { return transient_type{ impl_ }; } |
304 | IMMER_NODISCARD transient_type transient() && |
305 | { return transient_type{ std::move(impl_) }; } |
306 | |
307 | // Semi-private |
308 | const impl_t& impl() const { return impl_; } |
309 | |
310 | #if IMMER_DEBUG_PRINT |
311 | void debug_print(std::ostream& out=std::cerr) const |
312 | { flex_t{*this}.debug_print(out); } |
313 | #endif |
314 | |
315 | private: |
316 | friend flex_t; |
317 | friend transient_type; |
318 | |
319 | vector(impl_t impl) |
320 | : impl_(std::move(impl)) |
321 | { |
322 | #if IMMER_DEBUG_PRINT |
323 | // force the compiler to generate debug_print, so we can call |
324 | // it from a debugger |
325 | [](volatile auto){}(&vector::debug_print); |
326 | #endif |
327 | } |
328 | |
329 | vector&& push_back_move(std::true_type, value_type value) |
330 | { impl_.push_back_mut({}, std::move(value)); return std::move(*this); } |
331 | vector push_back_move(std::false_type, value_type value) |
332 | { return impl_.push_back(std::move(value)); } |
333 | |
334 | vector&& set_move(std::true_type, size_type index, value_type value) |
335 | { impl_.assoc_mut({}, index, std::move(value)); return std::move(*this); } |
336 | vector set_move(std::false_type, size_type index, value_type value) |
337 | { return impl_.assoc(index, std::move(value)); } |
338 | |
339 | template <typename Fn> |
340 | vector&& update_move(std::true_type, size_type index, Fn&& fn) |
341 | { impl_.update_mut({}, index, std::forward<Fn>(fn)); return std::move(*this); } |
342 | template <typename Fn> |
343 | vector update_move(std::false_type, size_type index, Fn&& fn) |
344 | { return impl_.update(index, std::forward<Fn>(fn)); } |
345 | |
346 | vector&& take_move(std::true_type, size_type elems) |
347 | { impl_.take_mut({}, elems); return std::move(*this); } |
348 | vector take_move(std::false_type, size_type elems) |
349 | { return impl_.take(elems); } |
350 | |
351 | impl_t impl_ = impl_t::empty(); |
352 | }; |
353 | |
354 | } // namespace immer |
355 | |