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 MP, |
19 | detail::rbts::bits_t B, |
20 | detail::rbts::bits_t BL> |
21 | class vector; |
22 | |
23 | template <typename T, |
24 | typename MP, |
25 | detail::rbts::bits_t B, |
26 | detail::rbts::bits_t BL> |
27 | class flex_vector_transient; |
28 | |
29 | /*! |
30 | * Immutable sequential container supporting both random access, |
31 | * structural sharing and efficient concatenation and slicing. |
32 | * |
33 | * @tparam T The type of the values to be stored in the container. |
34 | * @tparam MemoryPolicy Memory management policy. See @ref |
35 | * memory_policy. |
36 | * |
37 | * @rst |
38 | * |
39 | * This container is very similar to `vector`_ but also supports |
40 | * :math:`O(log(size))` *concatenation*, *slicing* and *insertion* at |
41 | * any point. Its performance characteristics are almost identical |
42 | * until one of these operations is performed. After that, |
43 | * performance is degraded by a constant factor that usually oscilates |
44 | * in the range :math:`[1, 2)` depending on the operation and the |
45 | * amount of flexible operations that have been performed. |
46 | * |
47 | * .. tip:: A `vector`_ can be converted to a `flex_vector`_ in |
48 | * constant time without any allocation. This is so because the |
49 | * internal structure of a *vector* is a strict subset of the |
50 | * internal structure of a *flexible vector*. You can take |
51 | * advantage of this property by creating normal vectors as long as |
52 | * the flexible operations are not needed, and convert later in |
53 | * your processing pipeline once and if these are needed. |
54 | * |
55 | * @endrst |
56 | */ |
57 | template <typename T, |
58 | typename MemoryPolicy = default_memory_policy, |
59 | detail::rbts::bits_t B = default_bits, |
60 | detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>> |
61 | class flex_vector |
62 | { |
63 | using impl_t = detail::rbts::rrbtree<T, MemoryPolicy, B, BL>; |
64 | |
65 | using move_t = |
66 | std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>; |
67 | |
68 | public: |
69 | static constexpr auto bits = B; |
70 | static constexpr auto bits_leaf = BL; |
71 | using memory_policy = MemoryPolicy; |
72 | |
73 | using value_type = T; |
74 | using reference = const T&; |
75 | using size_type = detail::rbts::size_t; |
76 | using difference_type = std::ptrdiff_t; |
77 | using const_reference = const T&; |
78 | |
79 | using iterator = detail::rbts::rrbtree_iterator<T, MemoryPolicy, B, BL>; |
80 | using const_iterator = iterator; |
81 | using reverse_iterator = std::reverse_iterator<iterator>; |
82 | |
83 | using transient_type = flex_vector_transient<T, MemoryPolicy, B, BL>; |
84 | |
85 | /*! |
86 | * Default constructor. It creates a flex_vector of `size() == 0`. |
87 | * It does not allocate memory and its complexity is @f$ O(1) @f$. |
88 | */ |
89 | flex_vector() = default; |
90 | |
91 | /*! |
92 | * Constructs a flex_vector containing the elements in `values`. |
93 | */ |
94 | flex_vector(std::initializer_list<T> values) |
95 | : impl_{impl_t::from_initializer_list(values)} |
96 | {} |
97 | |
98 | /*! |
99 | * Constructs a flex_vector containing the elements in the range |
100 | * defined by the input iterator `first` and range sentinel `last`. |
101 | */ |
102 | template <typename Iter, typename Sent, |
103 | std::enable_if_t |
104 | <detail::compatible_sentinel_v<Iter, Sent>, bool> = true> |
105 | flex_vector(Iter first, Sent last) |
106 | : impl_{impl_t::from_range(first, last)} |
107 | {} |
108 | |
109 | /*! |
110 | * Constructs a vector containing the element `val` repeated `n` |
111 | * times. |
112 | */ |
113 | flex_vector(size_type n, T v = {}) |
114 | : impl_{impl_t::from_fill(n, v)} |
115 | {} |
116 | |
117 | /*! |
118 | * Default constructor. It creates a flex_vector with the same |
119 | * contents as `v`. It does not allocate memory and is |
120 | * @f$ O(1) @f$. |
121 | */ |
122 | flex_vector(vector<T, MemoryPolicy, B, BL> v) |
123 | : impl_ { v.impl_.size, v.impl_.shift, |
124 | v.impl_.root->inc(), v.impl_.tail->inc() } |
125 | {} |
126 | |
127 | /*! |
128 | * Returns an iterator pointing at the first element of the |
129 | * collection. It does not allocate memory and its complexity is |
130 | * @f$ O(1) @f$. |
131 | */ |
132 | IMMER_NODISCARD iterator begin() const { return {impl_}; } |
133 | |
134 | /*! |
135 | * Returns an iterator pointing just after the last element of the |
136 | * collection. It does not allocate and its complexity is @f$ O(1) @f$. |
137 | */ |
138 | IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; } |
139 | |
140 | /*! |
141 | * Returns an iterator that traverses the collection backwards, |
142 | * pointing at the first element of the reversed collection. It |
143 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
144 | */ |
145 | IMMER_NODISCARD reverse_iterator rbegin() const { return reverse_iterator{end()}; } |
146 | |
147 | /*! |
148 | * Returns an iterator that traverses the collection backwards, |
149 | * pointing after the last element of the reversed collection. It |
150 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
151 | */ |
152 | IMMER_NODISCARD reverse_iterator rend() const { return reverse_iterator{begin()}; } |
153 | |
154 | /*! |
155 | * Returns the number of elements in the container. It does |
156 | * not allocate memory and its complexity is @f$ O(1) @f$. |
157 | */ |
158 | IMMER_NODISCARD size_type size() const { return impl_.size; } |
159 | |
160 | /*! |
161 | * Returns `true` if there are no elements in the container. It |
162 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
163 | */ |
164 | IMMER_NODISCARD bool empty() const { return impl_.size == 0; } |
165 | |
166 | /*! |
167 | * Access the last element. |
168 | */ |
169 | IMMER_NODISCARD const T& back() const { return impl_.back(); } |
170 | |
171 | /*! |
172 | * Access the first element. |
173 | */ |
174 | IMMER_NODISCARD const T& front() const { return impl_.front(); } |
175 | |
176 | /*! |
177 | * Returns a `const` reference to the element at position `index`. |
178 | * It is undefined when @f$ 0 index \geq size() @f$. It does not |
179 | * allocate memory and its complexity is *effectively* @f$ O(1) |
180 | * @f$. |
181 | */ |
182 | IMMER_NODISCARD reference operator[] (size_type index) const |
183 | { return impl_.get(index); } |
184 | |
185 | /*! |
186 | * Returns a `const` reference to the element at position |
187 | * `index`. It throws an `std::out_of_range` exception when @f$ |
188 | * index \geq size() @f$. It does not allocate memory and its |
189 | * complexity is *effectively* @f$ O(1) @f$. |
190 | */ |
191 | reference at(size_type index) const |
192 | { return impl_.get_check(index); } |
193 | |
194 | /*! |
195 | * Returns whether the vectors are equal. |
196 | */ |
197 | IMMER_NODISCARD bool operator==(const flex_vector& other) const |
198 | { return impl_.equals(other.impl_); } |
199 | IMMER_NODISCARD bool operator!=(const flex_vector& other) const |
200 | { return !(*this == other); } |
201 | |
202 | /*! |
203 | * Returns a flex_vector with `value` inserted at the end. It may |
204 | * allocate memory and its complexity is *effectively* @f$ O(1) @f$. |
205 | * |
206 | * @rst |
207 | * |
208 | * **Example** |
209 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
210 | * :language: c++ |
211 | * :dedent: 8 |
212 | * :start-after: push-back/start |
213 | * :end-before: push-back/end |
214 | * |
215 | * @endrst |
216 | */ |
217 | IMMER_NODISCARD flex_vector push_back(value_type value) const& |
218 | { return impl_.push_back(std::move(value)); } |
219 | |
220 | IMMER_NODISCARD decltype(auto) push_back(value_type value) && |
221 | { return push_back_move(move_t{}, std::move(value)); } |
222 | |
223 | /*! |
224 | * Returns a flex_vector with `value` inserted at the frony. It may |
225 | * allocate memory and its complexity is @f$ O(log(size)) @f$. |
226 | * |
227 | * @rst |
228 | * |
229 | * **Example** |
230 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
231 | * :language: c++ |
232 | * :dedent: 8 |
233 | * :start-after: push-front/start |
234 | * :end-before: push-front/end |
235 | * |
236 | * @endrst |
237 | */ |
238 | IMMER_NODISCARD flex_vector push_front(value_type value) const |
239 | { return flex_vector{}.push_back(value) + *this; } |
240 | |
241 | /*! |
242 | * Returns a flex_vector containing value `value` at position `index`. |
243 | * Undefined for `index >= size()`. |
244 | * It may allocate memory and its complexity is |
245 | * *effectively* @f$ O(1) @f$. |
246 | * |
247 | * @rst |
248 | * |
249 | * **Example** |
250 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
251 | * :language: c++ |
252 | * :dedent: 8 |
253 | * :start-after: set/start |
254 | * :end-before: set/end |
255 | * |
256 | * @endrst |
257 | */ |
258 | IMMER_NODISCARD flex_vector set(size_type index, value_type value) const& |
259 | { return impl_.assoc(index, std::move(value)); } |
260 | |
261 | IMMER_NODISCARD decltype(auto) set(size_type index, value_type value) && |
262 | { return set_move(move_t{}, index, std::move(value)); } |
263 | |
264 | /*! |
265 | * Returns a vector containing the result of the expression |
266 | * `fn((*this)[idx])` at position `idx`. |
267 | * Undefined for `index >= size()`. |
268 | * It may allocate memory and its complexity is |
269 | * *effectively* @f$ O(1) @f$. |
270 | * |
271 | * @rst |
272 | * |
273 | * **Example** |
274 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
275 | * :language: c++ |
276 | * :dedent: 8 |
277 | * :start-after: update/start |
278 | * :end-before: update/end |
279 | * |
280 | * @endrst |
281 | |
282 | */ |
283 | template <typename FnT> |
284 | IMMER_NODISCARD flex_vector update(size_type index, FnT&& fn) const& |
285 | { return impl_.update(index, std::forward<FnT>(fn)); } |
286 | |
287 | template <typename FnT> |
288 | IMMER_NODISCARD decltype(auto) update(size_type index, FnT&& fn) && |
289 | { return update_move(move_t{}, index, std::forward<FnT>(fn)); } |
290 | |
291 | /*! |
292 | * Returns a vector containing only the first `min(elems, size())` |
293 | * elements. It may allocate memory and its complexity is |
294 | * *effectively* @f$ O(1) @f$. |
295 | * |
296 | * @rst |
297 | * |
298 | * **Example** |
299 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
300 | * :language: c++ |
301 | * :dedent: 8 |
302 | * :start-after: take/start |
303 | * :end-before: take/end |
304 | * |
305 | * @endrst |
306 | */ |
307 | IMMER_NODISCARD flex_vector take(size_type elems) const& |
308 | { return impl_.take(elems); } |
309 | |
310 | IMMER_NODISCARD decltype(auto) take(size_type elems) && |
311 | { return take_move(move_t{}, elems); } |
312 | |
313 | /*! |
314 | * Returns a vector without the first `min(elems, size())` |
315 | * elements. It may allocate memory and its complexity is |
316 | * *effectively* @f$ O(1) @f$. |
317 | * |
318 | * @rst |
319 | * |
320 | * **Example** |
321 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
322 | * :language: c++ |
323 | * :dedent: 8 |
324 | * :start-after: drop/start |
325 | * :end-before: drop/end |
326 | * |
327 | * @endrst |
328 | */ |
329 | IMMER_NODISCARD flex_vector drop(size_type elems) const& |
330 | { return impl_.drop(elems); } |
331 | |
332 | IMMER_NODISCARD decltype(auto) drop(size_type elems) && |
333 | { return drop_move(move_t{}, elems); } |
334 | |
335 | /*! |
336 | * Concatenation operator. Returns a flex_vector with the contents |
337 | * of `l` followed by those of `r`. It may allocate memory |
338 | * and its complexity is @f$ O(log(max(size_r, size_l))) @f$ |
339 | * |
340 | * @rst |
341 | * |
342 | * **Example** |
343 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
344 | * :language: c++ |
345 | * :dedent: 8 |
346 | * :start-after: concat/start |
347 | * :end-before: concat/end |
348 | * |
349 | * @endrst |
350 | */ |
351 | IMMER_NODISCARD friend flex_vector operator+ (const flex_vector& l, const flex_vector& r) |
352 | { return l.impl_.concat(r.impl_); } |
353 | |
354 | IMMER_NODISCARD friend decltype(auto) operator+ (flex_vector&& l, const flex_vector& r) |
355 | { return concat_move(move_t{}, std::move(l), r); } |
356 | |
357 | IMMER_NODISCARD friend decltype(auto) operator+ (const flex_vector& l, flex_vector&& r) |
358 | { return concat_move(move_t{}, l, std::move(r)); } |
359 | |
360 | IMMER_NODISCARD friend decltype(auto) operator+ (flex_vector&& l, flex_vector&& r) |
361 | { return concat_move(move_t{}, std::move(l), std::move(r)); } |
362 | |
363 | /*! |
364 | * Returns a flex_vector with the `value` inserted at index |
365 | * `pos`. It may allocate memory and its complexity is @f$ |
366 | * O(log(size)) @f$ |
367 | * |
368 | * @rst |
369 | * |
370 | * **Example** |
371 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
372 | * :language: c++ |
373 | * :dedent: 8 |
374 | * :start-after: insert/start |
375 | * :end-before: insert/end |
376 | * |
377 | * @endrst |
378 | */ |
379 | IMMER_NODISCARD flex_vector insert(size_type pos, T value) const& |
380 | { return take(pos).push_back(std::move(value)) + drop(pos); } |
381 | IMMER_NODISCARD decltype(auto) insert(size_type pos, T value) && |
382 | { |
383 | using std::move; |
384 | auto rs = drop(pos); |
385 | return std::move(*this).take(pos).push_back( |
386 | std::move(value)) + std::move(rs); |
387 | } |
388 | |
389 | IMMER_NODISCARD flex_vector insert(size_type pos, flex_vector value) const& |
390 | { return take(pos) + std::move(value) + drop(pos); } |
391 | IMMER_NODISCARD decltype(auto) insert(size_type pos, flex_vector value) && |
392 | { |
393 | using std::move; |
394 | auto rs = drop(pos); |
395 | return std::move(*this).take(pos) + std::move(value) + std::move(rs); |
396 | } |
397 | |
398 | /*! |
399 | * Returns a flex_vector without the element at index `pos`. It |
400 | * may allocate memory and its complexity is @f$ O(log(size)) @f$ |
401 | * |
402 | * @rst |
403 | * |
404 | * **Example** |
405 | * .. literalinclude:: ../example/flex-vector/flex-vector.cpp |
406 | * :language: c++ |
407 | * :dedent: 8 |
408 | * :start-after: erase/start |
409 | * :end-before: erase/end |
410 | * |
411 | * @endrst |
412 | */ |
413 | IMMER_NODISCARD flex_vector erase(size_type pos) const& |
414 | { return take(pos) + drop(pos + 1); } |
415 | IMMER_NODISCARD decltype(auto) erase(size_type pos) && |
416 | { |
417 | auto rs = drop(pos + 1); |
418 | return std::move(*this).take(pos) + std::move(rs); |
419 | } |
420 | |
421 | IMMER_NODISCARD flex_vector erase(size_type pos, size_type lpos) const& |
422 | { return lpos > pos ? take(pos) + drop(lpos) : *this; } |
423 | IMMER_NODISCARD decltype(auto) erase(size_type pos, size_type lpos) && |
424 | { |
425 | if (lpos > pos) { |
426 | auto rs = drop(lpos); |
427 | return std::move(*this).take(pos) + std::move(rs); |
428 | } else { |
429 | return std::move(*this); |
430 | } |
431 | } |
432 | |
433 | /*! |
434 | * Returns an @a transient form of this container, an |
435 | * `immer::flex_vector_transient`. |
436 | */ |
437 | IMMER_NODISCARD transient_type transient() const& |
438 | { return transient_type{ impl_ }; } |
439 | IMMER_NODISCARD transient_type transient() && |
440 | { return transient_type{ std::move(impl_) }; } |
441 | |
442 | // Semi-private |
443 | const impl_t& impl() const { return impl_; } |
444 | |
445 | #if IMMER_DEBUG_PRINT |
446 | void debug_print(std::ostream& out=std::cerr) const |
447 | { impl_.debug_print(out); } |
448 | #endif |
449 | |
450 | private: |
451 | friend transient_type; |
452 | |
453 | flex_vector(impl_t impl) |
454 | : impl_(std::move(impl)) |
455 | { |
456 | #if IMMER_DEBUG_PRINT |
457 | // force the compiler to generate debug_print, so we can call |
458 | // it from a debugger |
459 | [](volatile auto){}(&flex_vector::debug_print); |
460 | #endif |
461 | } |
462 | |
463 | flex_vector&& push_back_move(std::true_type, value_type value) |
464 | { impl_.push_back_mut({}, std::move(value)); return std::move(*this); } |
465 | flex_vector push_back_move(std::false_type, value_type value) |
466 | { return impl_.push_back(std::move(value)); } |
467 | |
468 | flex_vector&& set_move(std::true_type, size_type index, value_type value) |
469 | { impl_.assoc_mut({}, index, std::move(value)); return std::move(*this); } |
470 | flex_vector set_move(std::false_type, size_type index, value_type value) |
471 | { return impl_.assoc(index, std::move(value)); } |
472 | |
473 | template <typename Fn> |
474 | flex_vector&& update_move(std::true_type, size_type index, Fn&& fn) |
475 | { impl_.update_mut({}, index, std::forward<Fn>(fn)); return std::move(*this); } |
476 | template <typename Fn> |
477 | flex_vector update_move(std::false_type, size_type index, Fn&& fn) |
478 | { return impl_.update(index, std::forward<Fn>(fn)); } |
479 | |
480 | flex_vector&& take_move(std::true_type, size_type elems) |
481 | { impl_.take_mut({}, elems); return std::move(*this); } |
482 | flex_vector take_move(std::false_type, size_type elems) |
483 | { return impl_.take(elems); } |
484 | |
485 | flex_vector&& drop_move(std::true_type, size_type elems) |
486 | { impl_.drop_mut({}, elems); return std::move(*this); } |
487 | flex_vector drop_move(std::false_type, size_type elems) |
488 | { return impl_.drop(elems); } |
489 | |
490 | static flex_vector&& concat_move(std::true_type, flex_vector&& l, const flex_vector& r) |
491 | { concat_mut_l(l.impl_, {}, r.impl_); return std::move(l); } |
492 | static flex_vector&& concat_move(std::true_type, const flex_vector& l, flex_vector&& r) |
493 | { concat_mut_r(l.impl_, r.impl_, {}); return std::move(r); } |
494 | static flex_vector&& concat_move(std::true_type, flex_vector&& l, flex_vector&& r) |
495 | { concat_mut_lr_l(l.impl_, {}, r.impl_, {}); return std::move(l); } |
496 | static flex_vector concat_move(std::false_type, const flex_vector& l, const flex_vector& r) |
497 | { return l.impl_.concat(r.impl_); } |
498 | |
499 | impl_t impl_ = impl_t::empty(); |
500 | }; |
501 | |
502 | } // namespace immer |
503 | |