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