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 MemoryPolicy,
19 detail::rbts::bits_t B,
20 detail::rbts::bits_t BL>
21class flex_vector;
22
23template <typename T,
24 typename MemoryPolicy,
25 detail::rbts::bits_t B,
26 detail::rbts::bits_t BL>
27class vector_transient;
28
29/*!
30 * Mutable version of `immer::flex_vector`.
31 *
32 * @rst
33 *
34 * Refer to :doc:`transients` to learn more about when and how to use
35 * the mutable versions of immutable containers.
36 *
37 * @endrst
38 */
39template <typename T,
40 typename MemoryPolicy = default_memory_policy,
41 detail::rbts::bits_t B = default_bits,
42 detail::rbts::bits_t BL = detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>>
43class flex_vector_transient
44 : MemoryPolicy::transience_t::owner
45{
46 using impl_t = detail::rbts::rrbtree<T, MemoryPolicy, B, BL>;
47 using base_t = typename MemoryPolicy::transience_t::owner;
48 using owner_t = typename MemoryPolicy::transience_t::owner;
49
50public:
51 static constexpr auto bits = B;
52 static constexpr auto bits_leaf = BL;
53 using memory_policy = MemoryPolicy;
54
55 using value_type = T;
56 using reference = const T&;
57 using size_type = detail::rbts::size_t;
58 using difference_type = std::ptrdiff_t;
59 using const_reference = const T&;
60
61 using iterator = detail::rbts::rrbtree_iterator<T, MemoryPolicy, B, BL>;
62 using const_iterator = iterator;
63 using reverse_iterator = std::reverse_iterator<iterator>;
64
65 using persistent_type = flex_vector<T, MemoryPolicy, B, BL>;
66
67 /*!
68 * Default constructor. It creates a flex_vector of `size() == 0`. It
69 * does not allocate memory and its complexity is @f$ O(1) @f$.
70 */
71 flex_vector_transient() = default;
72
73 /*!
74 * Default constructor. It creates a flex_vector with the same
75 * contents as `v`. It does not allocate memory and is
76 * @f$ O(1) @f$.
77 */
78 flex_vector_transient(vector_transient<T, MemoryPolicy, B, BL> v)
79 : base_t { std::move(static_cast<base_t&>(v)) }
80 , impl_ { v.impl_.size, v.impl_.shift,
81 v.impl_.root->inc(), v.impl_.tail->inc() }
82 {}
83
84 /*!
85 * Returns an iterator pointing at the first element of the
86 * collection. It does not allocate memory and its complexity is
87 * @f$ O(1) @f$.
88 */
89 IMMER_NODISCARD iterator begin() const { return {impl_}; }
90
91 /*!
92 * Returns an iterator pointing just after the last element of the
93 * collection. It does not allocate and its complexity is @f$ O(1) @f$.
94 */
95 IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; }
96
97 /*!
98 * Returns an iterator that traverses the collection backwards,
99 * pointing at the first element of the reversed collection. It
100 * does not allocate memory and its complexity is @f$ O(1) @f$.
101 */
102 IMMER_NODISCARD reverse_iterator rbegin() const { return reverse_iterator{end()}; }
103
104 /*!
105 * Returns an iterator that traverses the collection backwards,
106 * pointing after the last element of the reversed collection. It
107 * does not allocate memory and its complexity is @f$ O(1) @f$.
108 */
109 IMMER_NODISCARD reverse_iterator rend() const { return reverse_iterator{begin()}; }
110
111 /*!
112 * Returns the number of elements in the container. It does
113 * not allocate memory and its complexity is @f$ O(1) @f$.
114 */
115 IMMER_NODISCARD size_type size() const { return impl_.size; }
116
117 /*!
118 * Returns `true` if there are no elements in the container. It
119 * does not allocate memory and its complexity is @f$ O(1) @f$.
120 */
121 IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
122
123 /*!
124 * Returns a `const` reference to the element at position `index`.
125 * It is undefined when @f$ 0 index \geq size() @f$. It does not
126 * allocate memory and its complexity is *effectively* @f$ O(1)
127 * @f$.
128 */
129 reference operator[] (size_type index) const
130 { return impl_.get(index); }
131
132 /*!
133 * Returns a `const` reference to the element at position
134 * `index`. It throws an `std::out_of_range` exception when @f$
135 * index \geq size() @f$. It does not allocate memory and its
136 * complexity is *effectively* @f$ O(1) @f$.
137 */
138 reference at(size_type index) const
139 { return impl_.get_check(index); }
140
141 /*!
142 * Inserts `value` at the end. It may allocate memory and its
143 * complexity is *effectively* @f$ O(1) @f$.
144 */
145 void push_back(value_type value)
146 { impl_.push_back_mut(*this, std::move(value)); }
147
148 /*!
149 * Sets to the value `value` at position `idx`.
150 * Undefined for `index >= size()`.
151 * It may allocate memory and its complexity is
152 * *effectively* @f$ O(1) @f$.
153 */
154 void set(size_type index, value_type value)
155 { impl_.assoc_mut(*this, index, std::move(value)); }
156
157 /*!
158 * Updates the vector to contain the result of the expression
159 * `fn((*this)[idx])` at position `idx`.
160 * Undefined for `0 >= size()`.
161 * It may allocate memory and its complexity is
162 * *effectively* @f$ O(1) @f$.
163 */
164 template <typename FnT>
165 void update(size_type index, FnT&& fn)
166 { impl_.update_mut(*this, index, std::forward<FnT>(fn)); }
167
168 /*!
169 * Resizes the vector to only contain the first `min(elems, size())`
170 * elements. It may allocate memory and its complexity is
171 * *effectively* @f$ O(1) @f$.
172 */
173 void take(size_type elems)
174 { impl_.take_mut(*this, elems); }
175
176 /*!
177 * Removes the first the first `min(elems, size())`
178 * elements. It may allocate memory and its complexity is
179 * *effectively* @f$ O(1) @f$.
180 */
181 void drop(size_type elems)
182 { impl_.drop_mut(*this, elems); }
183
184 /*!
185 * Appends the contents of the `r` at the end. It may allocate
186 * memory and its complexity is:
187 * @f$ O(log(max(size_r, size_l))) @f$
188 */
189 void append(flex_vector_transient& r)
190 {
191 r.owner_t::operator=(owner_t{});
192 concat_mut_l(impl_, *this, r.impl_);
193 }
194 void append(flex_vector_transient&& r)
195 { concat_mut_lr_l(impl_, *this, r.impl_, r); }
196
197 /*!
198 * Prepends the contents of the `l` at the beginning. It may
199 * allocate memory and its complexity is:
200 * @f$ O(log(max(size_r, size_l))) @f$
201 */
202 void prepend(flex_vector_transient& l)
203 {
204 l.owner_t::operator=(owner_t{});
205 concat_mut_r(l.impl_, impl_, *this);
206 }
207 void prepend(flex_vector_transient&& l)
208 { concat_mut_lr_r(l.impl_, l, impl_, *this); }
209
210 /*!
211 * Returns an @a immutable form of this container, an
212 * `immer::flex_vector`.
213 */
214 IMMER_NODISCARD persistent_type persistent() &
215 {
216 this->owner_t::operator=(owner_t{});
217 return persistent_type{ impl_ };
218 }
219 IMMER_NODISCARD persistent_type persistent() &&
220 { return persistent_type{ std::move(impl_) }; }
221
222private:
223 friend persistent_type;
224
225 flex_vector_transient(impl_t impl)
226 : impl_(std::move(impl))
227 {}
228
229 impl_t impl_ = impl_t::empty();
230};
231
232} // namespace immer
233