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 | namespace immer { |
16 | |
17 | template <typename T, |
18 | typename MemoryPolicy, |
19 | detail::rbts::bits_t B, |
20 | detail::rbts::bits_t BL> |
21 | class vector; |
22 | |
23 | template <typename T, |
24 | typename MemoryPolicy, |
25 | detail::rbts::bits_t B, |
26 | detail::rbts::bits_t BL> |
27 | class flex_vector_transient; |
28 | |
29 | /*! |
30 | * Mutable version of `immer::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 | */ |
39 | template <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>> |
43 | class vector_transient |
44 | : MemoryPolicy::transience_t::owner |
45 | { |
46 | using impl_t = detail::rbts::rbtree<T, MemoryPolicy, B, BL>; |
47 | using flex_t = flex_vector_transient<T, MemoryPolicy, B, BL>; |
48 | using owner_t = typename MemoryPolicy::transience_t::owner; |
49 | |
50 | public: |
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::rbtree_iterator<T, MemoryPolicy, B, BL>; |
62 | using const_iterator = iterator; |
63 | using reverse_iterator = std::reverse_iterator<iterator>; |
64 | |
65 | using persistent_type = vector<T, MemoryPolicy, B, BL>; |
66 | |
67 | /*! |
68 | * Default constructor. It creates a mutable vector of `size() == |
69 | * 0`. It does not allocate memory and its complexity is |
70 | * @f$ O(1) @f$. |
71 | */ |
72 | vector_transient() = default; |
73 | |
74 | /*! |
75 | * Returns an iterator pointing at the first element of the |
76 | * collection. It does not allocate memory and its complexity is |
77 | * @f$ O(1) @f$. |
78 | */ |
79 | IMMER_NODISCARD iterator begin() const { return {impl_}; } |
80 | |
81 | /*! |
82 | * Returns an iterator pointing just after the last element of the |
83 | * collection. It does not allocate and its complexity is @f$ O(1) @f$. |
84 | */ |
85 | IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; } |
86 | |
87 | /*! |
88 | * Returns an iterator that traverses the collection backwards, |
89 | * pointing at the first element of the reversed collection. It |
90 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
91 | */ |
92 | IMMER_NODISCARD reverse_iterator rbegin() const { return reverse_iterator{end()}; } |
93 | |
94 | /*! |
95 | * Returns an iterator that traverses the collection backwards, |
96 | * pointing after the last element of the reversed collection. It |
97 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
98 | */ |
99 | IMMER_NODISCARD reverse_iterator rend() const { return reverse_iterator{begin()}; } |
100 | |
101 | /*! |
102 | * Returns the number of elements in the container. It does |
103 | * not allocate memory and its complexity is @f$ O(1) @f$. |
104 | */ |
105 | IMMER_NODISCARD size_type size() const { return impl_.size; } |
106 | |
107 | /*! |
108 | * Returns `true` if there are no elements in the container. It |
109 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
110 | */ |
111 | IMMER_NODISCARD bool empty() const { return impl_.size == 0; } |
112 | |
113 | /*! |
114 | * Returns a `const` reference to the element at position `index`. |
115 | * It is undefined when @f$ 0 index \geq size() @f$. It does not |
116 | * allocate memory and its complexity is *effectively* @f$ O(1) |
117 | * @f$. |
118 | */ |
119 | reference operator[] (size_type index) const |
120 | { return impl_.get(index); } |
121 | |
122 | /*! |
123 | * Returns a `const` reference to the element at position |
124 | * `index`. It throws an `std::out_of_range` exception when @f$ |
125 | * index \geq size() @f$. It does not allocate memory and its |
126 | * complexity is *effectively* @f$ O(1) @f$. |
127 | */ |
128 | reference at(size_type index) const |
129 | { return impl_.get_check(index); } |
130 | |
131 | /*! |
132 | * Inserts `value` at the end. It may allocate memory and its |
133 | * complexity is *effectively* @f$ O(1) @f$. |
134 | */ |
135 | void push_back(value_type value) |
136 | { impl_.push_back_mut(*this, std::move(value)); } |
137 | |
138 | /*! |
139 | * Sets to the value `value` at position `idx`. |
140 | * Undefined for `index >= size()`. |
141 | * It may allocate memory and its complexity is |
142 | * *effectively* @f$ O(1) @f$. |
143 | */ |
144 | void set(size_type index, value_type value) |
145 | { impl_.assoc_mut(*this, index, std::move(value)); } |
146 | |
147 | /*! |
148 | * Updates the vector to contain the result of the expression |
149 | * `fn((*this)[idx])` at position `idx`. |
150 | * Undefined for `0 >= size()`. |
151 | * It may allocate memory and its complexity is |
152 | * *effectively* @f$ O(1) @f$. |
153 | */ |
154 | template <typename FnT> |
155 | void update(size_type index, FnT&& fn) |
156 | { impl_.update_mut(*this, index, std::forward<FnT>(fn)); } |
157 | |
158 | /*! |
159 | * Resizes the vector to only contain the first `min(elems, size())` |
160 | * elements. It may allocate memory and its complexity is |
161 | * *effectively* @f$ O(1) @f$. |
162 | */ |
163 | void take(size_type elems) |
164 | { impl_.take_mut(*this, elems); } |
165 | |
166 | /*! |
167 | * Returns an @a immutable form of this container, an |
168 | * `immer::vector`. |
169 | */ |
170 | IMMER_NODISCARD persistent_type persistent() & |
171 | { |
172 | this->owner_t::operator=(owner_t{}); |
173 | return persistent_type{ impl_ }; |
174 | } |
175 | IMMER_NODISCARD persistent_type persistent() && |
176 | { return persistent_type{ std::move(impl_) }; } |
177 | |
178 | private: |
179 | friend flex_t; |
180 | friend persistent_type; |
181 | |
182 | vector_transient(impl_t impl) |
183 | : impl_(std::move(impl)) |
184 | {} |
185 | |
186 | impl_t impl_ = impl_t::empty(); |
187 | }; |
188 | |
189 | } // namespace immer |
190 | |