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/memory_policy.hpp>
12#include <immer/detail/arrays/with_capacity.hpp>
13
14namespace immer {
15
16template <typename T, typename MemoryPolicy>
17class array_transient;
18
19/*!
20 * Immutable container that stores a sequence of elements in
21 * contiguous memory.
22 *
23 * @tparam T The type of the values to be stored in the container.
24 *
25 * @rst
26 *
27 * It supports the most efficient iteration and random access,
28 * equivalent to a ``std::vector`` or ``std::array``, but all
29 * manipulations are :math:`O(size)`.
30 *
31 * .. tip:: Don't be fooled by the bad complexity of this data
32 * structure. It is a great choice for short sequence or when it
33 * is seldom or never changed. This depends on the ``sizeof(T)``
34 * and the expensiveness of its ``T``'s copy constructor, in case
35 * of doubt, measure. For basic types, using an `array` when
36 * :math:`n < 100` is a good heuristic.
37 *
38 * @endrst
39 */
40template <typename T, typename MemoryPolicy = default_memory_policy>
41class array
42{
43 using impl_t = std::conditional_t<
44 MemoryPolicy::use_transient_rvalues,
45 detail::arrays::with_capacity<T, MemoryPolicy>,
46 detail::arrays::no_capacity<T, MemoryPolicy>>;
47
48 using move_t =
49 std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>;
50
51public:
52 using value_type = T;
53 using reference = const T&;
54 using size_type = std::size_t;
55 using difference_type = std::ptrdiff_t;
56 using const_reference = const T&;
57
58 using iterator = const T*;
59 using const_iterator = iterator;
60 using reverse_iterator = std::reverse_iterator<iterator>;
61
62 using memory_policy = MemoryPolicy;
63 using transient_type = array_transient<T, MemoryPolicy>;
64
65 /*!
66 * Default constructor. It creates an array of `size() == 0`. It
67 * does not allocate memory and its complexity is @f$ O(1) @f$.
68 */
69 array() = default;
70
71 /*!
72 * Constructs an array containing the elements in `values`.
73 */
74 array(std::initializer_list<T> values)
75 : impl_{impl_t::from_initializer_list(values)}
76 {}
77
78 /*!
79 * Constructs a array containing the elements in the range
80 * defined by the forward iterator `first` and range sentinel `last`.
81 */
82 template <typename Iter, typename Sent,
83 std::enable_if_t
84 <detail::compatible_sentinel_v<Iter, Sent>
85 && detail::is_forward_iterator_v<Iter>, bool> = true>
86 array(Iter first, Sent last)
87 : impl_{impl_t::from_range(first, last)}
88 {}
89
90 /*!
91 * Constructs a array containing the element `val` repeated `n`
92 * times.
93 */
94 array(size_type n, T v = {})
95 : impl_{impl_t::from_fill(n, v)}
96 {}
97
98 /*!
99 * Returns an iterator pointing at the first element of the
100 * collection. It does not allocate memory and its complexity is
101 * @f$ O(1) @f$.
102 */
103 IMMER_NODISCARD iterator begin() const { return impl_.data(); }
104
105 /*!
106 * Returns an iterator pointing just after the last element of the
107 * collection. It does not allocate and its complexity is @f$ O(1) @f$.
108 */
109 IMMER_NODISCARD iterator end() const { return impl_.data() + impl_.size; }
110
111 /*!
112 * Returns an iterator that traverses the collection backwards,
113 * pointing at the first element of the reversed collection. It
114 * does not allocate memory and its complexity is @f$ O(1) @f$.
115 */
116 IMMER_NODISCARD reverse_iterator rbegin() const { return reverse_iterator{end()}; }
117
118 /*!
119 * Returns an iterator that traverses the collection backwards,
120 * pointing after the last element of the reversed collection. It
121 * does not allocate memory and its complexity is @f$ O(1) @f$.
122 */
123 IMMER_NODISCARD reverse_iterator rend() const { return reverse_iterator{begin()}; }
124
125 /*!
126 * Returns the number of elements in the container. It does
127 * not allocate memory and its complexity is @f$ O(1) @f$.
128 */
129 IMMER_NODISCARD std::size_t size() const { return impl_.size; }
130
131 /*!
132 * Returns `true` if there are no elements in the container. It
133 * does not allocate memory and its complexity is @f$ O(1) @f$.
134 */
135 IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
136
137 /*!
138 * Access the raw data.
139 */
140 IMMER_NODISCARD const T* data() const { return impl_.data(); }
141
142 /*!
143 * Access the last element.
144 */
145 IMMER_NODISCARD const T& back() const { return data()[size() - 1]; }
146
147 /*!
148 * Access the first element.
149 */
150 IMMER_NODISCARD const T& front() const { return data()[0]; }
151
152 /*!
153 * Returns a `const` reference to the element at position `index`.
154 * It is undefined when @f$ 0 index \geq size() @f$. It does not
155 * allocate memory and its complexity is *effectively* @f$ O(1)
156 * @f$.
157 */
158 IMMER_NODISCARD reference operator[] (size_type index) const
159 { return impl_.get(index); }
160
161 /*!
162 * Returns a `const` reference to the element at position
163 * `index`. It throws an `std::out_of_range` exception when @f$
164 * index \geq size() @f$. It does not allocate memory and its
165 * complexity is *effectively* @f$ O(1) @f$.
166 */
167 reference at(size_type index) const
168 { return impl_.get_check(index); }
169
170 /*!
171 * Returns whether the vectors are equal.
172 */
173 IMMER_NODISCARD bool operator==(const array& other) const
174 { return impl_.equals(other.impl_); }
175 IMMER_NODISCARD bool operator!=(const array& other) const
176 { return !(*this == other); }
177
178 /*!
179 * Returns an array with `value` inserted at the end. It may
180 * allocate memory and its complexity is @f$ O(size) @f$.
181 *
182 * @rst
183 *
184 * **Example**
185 * .. literalinclude:: ../example/array/array.cpp
186 * :language: c++
187 * :dedent: 8
188 * :start-after: push-back/start
189 * :end-before: push-back/end
190 *
191 * @endrst
192 */
193 IMMER_NODISCARD array push_back(value_type value) const&
194 { return impl_.push_back(std::move(value)); }
195
196 IMMER_NODISCARD decltype(auto) push_back(value_type value) &&
197 { return push_back_move(move_t{}, std::move(value)); }
198
199 /*!
200 * Returns an array containing value `value` at position `idx`.
201 * Undefined for `index >= size()`.
202 * It may allocate memory and its complexity is @f$ O(size) @f$.
203 *
204 * @rst
205 *
206 * **Example**
207 * .. literalinclude:: ../example/array/array.cpp
208 * :language: c++
209 * :dedent: 8
210 * :start-after: set/start
211 * :end-before: set/end
212 *
213 * @endrst
214 */
215 IMMER_NODISCARD array set(std::size_t index, value_type value) const&
216 { return impl_.assoc(index, std::move(value)); }
217
218 IMMER_NODISCARD decltype(auto) set(size_type index, value_type value) &&
219 { return set_move(move_t{}, index, std::move(value)); }
220
221 /*!
222 * Returns an array containing the result of the expression
223 * `fn((*this)[idx])` at position `idx`.
224 * Undefined for `index >= size()`.
225 * It may allocate memory and its complexity is @f$ O(size) @f$.
226 *
227 * @rst
228 *
229 * **Example**
230 * .. literalinclude:: ../example/array/array.cpp
231 * :language: c++
232 * :dedent: 8
233 * :start-after: update/start
234 * :end-before: update/end
235 *
236 * @endrst
237 */
238 template <typename FnT>
239 IMMER_NODISCARD array update(std::size_t index, FnT&& fn) const&
240 { return impl_.update(index, std::forward<FnT>(fn)); }
241
242 template <typename FnT>
243 IMMER_NODISCARD decltype(auto) update(size_type index, FnT&& fn) &&
244 { return update_move(move_t{}, index, std::forward<FnT>(fn)); }
245
246 /*!
247 * Returns a array containing only the first `min(elems, size())`
248 * elements. It may allocate memory and its complexity is
249 * *effectively* @f$ O(1) @f$.
250 *
251 * @rst
252 *
253 * **Example**
254 * .. literalinclude:: ../example/array/array.cpp
255 * :language: c++
256 * :dedent: 8
257 * :start-after: take/start
258 * :end-before: take/end
259 *
260 * @endrst
261 */
262 IMMER_NODISCARD array take(size_type elems) const&
263 { return impl_.take(elems); }
264
265 IMMER_NODISCARD decltype(auto) take(size_type elems) &&
266 { return take_move(move_t{}, elems); }
267
268 /*!
269 * Returns an @a transient form of this container, an
270 * `immer::array_transient`.
271 */
272 IMMER_NODISCARD transient_type transient() const&
273 { return transient_type{ impl_ }; }
274 IMMER_NODISCARD transient_type transient() &&
275 { return transient_type{ std::move(impl_) }; }
276
277 // Semi-private
278 const impl_t& impl() const { return impl_; }
279
280private:
281 friend transient_type;
282
283 array(impl_t impl) : impl_(std::move(impl)) {}
284
285 array&& push_back_move(std::true_type, value_type value)
286 { impl_.push_back_mut({}, std::move(value)); return std::move(*this); }
287 array push_back_move(std::false_type, value_type value)
288 { return impl_.push_back(std::move(value)); }
289
290 array&& set_move(std::true_type, size_type index, value_type value)
291 { impl_.assoc_mut({}, index, std::move(value)); return std::move(*this); }
292 array set_move(std::false_type, size_type index, value_type value)
293 { return impl_.assoc(index, std::move(value)); }
294
295 template <typename Fn>
296 array&& update_move(std::true_type, size_type index, Fn&& fn)
297 { impl_.update_mut({}, index, std::forward<Fn>(fn)); return std::move(*this); }
298 template <typename Fn>
299 array update_move(std::false_type, size_type index, Fn&& fn)
300 { return impl_.update(index, std::forward<Fn>(fn)); }
301
302 array&& take_move(std::true_type, size_type elems)
303 { impl_.take_mut({}, elems); return std::move(*this); }
304 array take_move(std::false_type, size_type elems)
305 { return impl_.take(elems); }
306
307 impl_t impl_ = impl_t::empty();
308};
309
310} /* namespace immer */
311