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/hamts/champ.hpp>
13#include <immer/detail/hamts/champ_iterator.hpp>
14
15#include <functional>
16
17namespace immer {
18
19template <typename K,
20 typename T,
21 typename Hash,
22 typename Equal,
23 typename MemoryPolicy,
24 detail::hamts::bits_t B>
25class map_transient;
26
27/*!
28 * Immutable unordered mapping of values from type `K` to type `T`.
29 *
30 * @tparam K The type of the keys.
31 * @tparam T The type of the values to be stored in the container.
32 * @tparam Hash The type of a function object capable of hashing
33 * values of type `T`.
34 * @tparam Equal The type of a function object capable of comparing
35 * values of type `T`.
36 * @tparam MemoryPolicy Memory management policy. See @ref
37 * memory_policy.
38 *
39 * @rst
40 *
41 * This cotainer provides a good trade-off between cache locality,
42 * search, update performance and structural sharing. It does so by
43 * storing the data in contiguous chunks of :math:`2^{B}` elements.
44 * When storing big objects, the size of these contiguous chunks can
45 * become too big, damaging performance. If this is measured to be
46 * problematic for a specific use-case, it can be solved by using a
47 * `immer::box` to wrap the type `T`.
48 *
49 * **Example**
50 * .. literalinclude:: ../example/map/intro.cpp
51 * :language: c++
52 * :start-after: intro/start
53 * :end-before: intro/end
54 *
55 * @endrst
56 *
57 */
58template <typename K,
59 typename T,
60 typename Hash = std::hash<K>,
61 typename Equal = std::equal_to<K>,
62 typename MemoryPolicy = default_memory_policy,
63 detail::hamts::bits_t B = default_bits>
64class map
65{
66 using value_t = std::pair<K, T>;
67
68 struct project_value
69 {
70 const T& operator() (const value_t& v) const noexcept
71 {
72 return v.second;
73 }
74 };
75
76 struct project_value_ptr
77 {
78 const T* operator() (const value_t& v) const noexcept
79 {
80 return &v.second;
81 }
82 };
83
84 struct combine_value
85 {
86 template <typename Kf, typename Tf>
87 value_t operator() (Kf&& k, Tf&& v) const
88 {
89 return { std::forward<Kf>(k), std::forward<Tf>(v) };
90 }
91 };
92
93 struct default_value
94 {
95 const T& operator() () const
96 {
97 static T v{};
98 return v;
99 }
100 };
101
102 struct error_value
103 {
104 const T& operator() () const
105 {
106 throw std::out_of_range{"key not found"};
107 }
108 };
109
110 struct hash_key
111 {
112 auto operator() (const value_t& v)
113 { return Hash{}(v.first); }
114
115 auto operator() (const K& v)
116 { return Hash{}(v); }
117 };
118
119 struct equal_key
120 {
121 auto operator() (const value_t& a, const value_t& b)
122 { return Equal{}(a.first, b.first); }
123
124 auto operator() (const value_t& a, const K& b)
125 { return Equal{}(a.first, b); }
126 };
127
128 struct equal_value
129 {
130 auto operator() (const value_t& a, const value_t& b)
131 { return Equal{}(a.first, b.first) && a.second == b.second; }
132 };
133
134 using impl_t = detail::hamts::champ<
135 value_t, hash_key, equal_key, MemoryPolicy, B>;
136
137public:
138 using key_type = K;
139 using mapped_type = T;
140 using value_type = std::pair<K, T>;
141 using size_type = detail::hamts::size_t;
142 using diference_type = std::ptrdiff_t;
143 using hasher = Hash;
144 using key_equal = Equal;
145 using reference = const value_type&;
146 using const_reference = const value_type&;
147
148 using iterator = detail::hamts::champ_iterator<
149 value_t, hash_key, equal_key, MemoryPolicy, B>;
150 using const_iterator = iterator;
151
152 using transient_type = map_transient<K, T, Hash, Equal, MemoryPolicy, B>;
153
154 /*!
155 * Default constructor. It creates a set of `size() == 0`. It
156 * does not allocate memory and its complexity is @f$ O(1) @f$.
157 */
158 map() = default;
159
160 /*!
161 * Returns an iterator pointing at the first element of the
162 * collection. It does not allocate memory and its complexity is
163 * @f$ O(1) @f$.
164 */
165 IMMER_NODISCARD iterator begin() const { return {impl_}; }
166
167 /*!
168 * Returns an iterator pointing just after the last element of the
169 * collection. It does not allocate and its complexity is @f$ O(1) @f$.
170 */
171 IMMER_NODISCARD iterator end() const { return {impl_, typename iterator::end_t{}}; }
172
173 /*!
174 * Returns the number of elements in the container. It does
175 * not allocate memory and its complexity is @f$ O(1) @f$.
176 */
177 IMMER_NODISCARD size_type size() const { return impl_.size; }
178
179 /*!
180 * Returns `true` if there are no elements in the container. It
181 * does not allocate memory and its complexity is @f$ O(1) @f$.
182 */
183 IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
184
185 /*!
186 * Returns `1` when the key `k` is contained in the map or `0`
187 * otherwise. It won't allocate memory and its complexity is
188 * *effectively* @f$ O(1) @f$.
189 */
190 IMMER_NODISCARD size_type count(const K& k) const
191 { return impl_.template get<detail::constantly<size_type, 1>,
192 detail::constantly<size_type, 0>>(k); }
193
194 /*!
195 * Returns a `const` reference to the values associated to the key
196 * `k`. If the key is not contained in the map, it returns a
197 * default constructed value. It does not allocate memory and its
198 * complexity is *effectively* @f$ O(1) @f$.
199 */
200 IMMER_NODISCARD const T& operator[] (const K& k) const
201 { return impl_.template get<project_value, default_value>(k); }
202
203 /*!
204 * Returns a `const` reference to the values associated to the key
205 * `k`. If the key is not contained in the map, throws an
206 * `std::out_of_range` error. It does not allocate memory and its
207 * complexity is *effectively* @f$ O(1) @f$.
208 */
209 const T& at(const K& k) const
210 { return impl_.template get<project_value, error_value>(k); }
211
212
213 /*!
214 * Returns a pointer to the value associated with the key `k`. If
215 * the key is not contained in the map, a `nullptr` is returned.
216 * It does not allocate memory and its complexity is *effectively*
217 * @f$ O(1) @f$.
218 *
219 * @rst
220 *
221 * .. admonition:: Why doesn't this function return an iterator?
222 *
223 * Associative containers from the C++ standard library provide a
224 * ``find`` method that returns an iterator pointing to the
225 * element in the container or ``end()`` when the key is missing.
226 * In the case of an unordered container, the only meaningful
227 * thing one may do with it is to compare it with the end, to
228 * test if the find was succesfull, and dereference it. This
229 * comparison is cumbersome compared to testing for a non-empty
230 * optional value. Furthermore, for an immutable container,
231 * returning an iterator would have some additional performance
232 * cost, with no benefits otherwise.
233 *
234 * In our opinion, this function should return a
235 * ``std::optional<const T&>`` but this construction is not valid
236 * in any current standard. As a compromise we return a
237 * pointer, which has similar syntactic properties yet it is
238 * unfortunatelly unnecessarily unrestricted.
239 *
240 * @endrst
241 */
242 IMMER_NODISCARD const T* find(const K& k) const
243 { return impl_.template get<project_value_ptr,
244 detail::constantly<const T*, nullptr>>(k); }
245
246 /*!
247 * Returns whether the sets are equal.
248 */
249 IMMER_NODISCARD bool operator==(const map& other) const
250 { return impl_.template equals<equal_value>(other.impl_); }
251 IMMER_NODISCARD bool operator!=(const map& other) const
252 { return !(*this == other); }
253
254 /*!
255 * Returns a map containing the association `value`. If the key is
256 * already in the map, it replaces its association in the map.
257 * It may allocate memory and its complexity is *effectively* @f$
258 * O(1) @f$.
259 */
260 IMMER_NODISCARD map insert(value_type value) const
261 { return impl_.add(std::move(value)); }
262
263 /*!
264 * Returns a map containing the association `(k, v)`. If the key
265 * is already in the map, it replaces its association in the map.
266 * It may allocate memory and its complexity is *effectively* @f$
267 * O(1) @f$.
268 */
269 IMMER_NODISCARD map set(key_type k, mapped_type v) const
270 { return impl_.add({std::move(k), std::move(v)}); }
271
272 /*!
273 * Returns a map replacing the association `(k, v)` by the
274 * association new association `(k, fn(v))`, where `v` is the
275 * currently associated value for `k` in the map or a default
276 * constructed value otherwise. It may allocate memory
277 * and its complexity is *effectively* @f$ O(1) @f$.
278 */
279 template <typename Fn>
280 IMMER_NODISCARD map update(key_type k, Fn&& fn) const
281 {
282 return impl_
283 .template update<project_value, default_value, combine_value>(
284 std::move(k), std::forward<Fn>(fn));
285 }
286
287 /*!
288 * Returns a map without the key `k`. If the key is not
289 * associated in the map it returns the same map. It may allocate
290 * memory and its complexity is *effectively* @f$ O(1) @f$.
291 */
292 IMMER_NODISCARD map erase(const K& k) const
293 { return impl_.sub(k); }
294
295 /*!
296 * Returns an @a transient form of this container, a
297 * `immer::map_transient`.
298 */
299 IMMER_NODISCARD transient_type transient() const&
300 { return transient_type{ impl_ }; }
301 IMMER_NODISCARD transient_type transient() &&
302 { return transient_type{ std::move(impl_) }; }
303
304 // Semi-private
305 const impl_t& impl() const { return impl_; }
306
307private:
308 friend transient_type;
309
310 map(impl_t impl)
311 : impl_(std::move(impl))
312 {}
313
314 impl_t impl_ = impl_t::empty();
315};
316
317} // namespace immer
318