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
19namespace immer {
20
21template <typename T,
22 typename MemoryPolicy,
23 detail::rbts::bits_t B,
24 detail::rbts::bits_t BL>
25class flex_vector;
26
27template <typename T,
28 typename MemoryPolicy,
29 detail::rbts::bits_t B,
30 detail::rbts::bits_t BL>
31class 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 */
70template <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>>
74class 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
82public:
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
315private:
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