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
15namespace immer {
16
17template <typename T,
18 typename MP,
19 detail::rbts::bits_t B,
20 detail::rbts::bits_t BL>
21class vector;
22
23template <typename T,
24 typename MP,
25 detail::rbts::bits_t B,
26 detail::rbts::bits_t BL>
27class 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 */
57template <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>>
61class 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
68public:
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
450private:
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