summaryrefslogtreecommitdiff
path: root/boost/hana/fwd/map.hpp
blob: c00f57195f3de8863bd10eb57073e97e42709c35 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
/*!
@file
Forward declares `boost::hana::map`.

@copyright Louis Dionne 2013-2017
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 */

#ifndef BOOST_HANA_FWD_MAP_HPP
#define BOOST_HANA_FWD_MAP_HPP

#include <boost/hana/config.hpp>
#include <boost/hana/fwd/core/to.hpp>
#include <boost/hana/fwd/core/make.hpp>
#include <boost/hana/fwd/erase_key.hpp>
#include <boost/hana/fwd/insert.hpp>
#include <boost/hana/fwd/keys.hpp>


BOOST_HANA_NAMESPACE_BEGIN
    //! Tag representing `hana::map`s.
    //! @relates hana::map
    struct map_tag { };

    namespace detail {
        template <typename ...Pairs>
        struct make_map_type;
    }

    //! @ingroup group-datatypes
    //! Basic associative container requiring unique, `Comparable` and
    //! `Hashable` keys.
    //!
    //! The order of the elements of the map is unspecified. Also, all the
    //! keys must be `Hashable`, and any two keys with equal hashes must be
    //! `Comparable` with each other at compile-time.
    //!
    //! Note that the actual representation of a `hana::map` is an implementation
    //! detail. As such, one should not assume anything more than what is
    //! explicitly documented as being part of the interface of a map,
    //! such as:
    //! - the presence of additional constructors
    //! - the presence of additional assignment operators
    //! - the fact that `hana::map<Pairs...>` is, or is not, a dependent type
    //!
    //! In particular, the last point is very important; `hana::map<Pairs...>`
    //! is basically equivalent to
    //! @code
    //!     decltype(hana::make_pair(std::declval<Pairs>()...))
    //! @endcode
    //! which is not something that can be pattern-matched on during template
    //! argument deduction, for example.
    //!
    //!
    //! Modeled concepts
    //! ----------------
    //! 1. `Comparable`\n
    //! Two maps are equal iff all their keys are equal and are associated
    //! to equal values.
    //! @include example/map/comparable.cpp
    //!
    //! 2. `Searchable`\n
    //! A map can be searched by its keys with a predicate yielding a
    //! compile-time `Logical`. Also note that `operator[]` can be used
    //! instead of `at_key`.
    //! @include example/map/searchable.cpp
    //!
    //! 3. `Foldable`\n
    //! Folding a map is equivalent to folding a list of the key/value pairs
    //! it contains. In particular, since that list is not guaranteed to be
    //! in any specific order, folding a map with an operation that is not
    //! both commutative and associative will yield non-deterministic behavior.
    //! @include example/map/foldable.cpp
    //!
    //!
    //! Conversion from any `Foldable`
    //! ------------------------------
    //! Any `Foldable` of `Product`s can be converted to a `hana::map` with
    //! `hana::to<hana::map_tag>` or, equivalently, `hana::to_map`. If the
    //! `Foldable` contains duplicate keys, only the value associated to the
    //! first occurence of each key is kept.
    //! @include example/map/to.cpp
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/map.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    template <typename ...Pairs>
    struct map {
        //! Default-construct a map. This constructor only exists when all the
        //! elements of the map are default-constructible.
        constexpr map() = default;

        //! Copy-construct a map from another map. This constructor only
        //! exists when all the elements of the map are copy-constructible.
        constexpr map(map const& other) = default;

        //! Move-construct a map from another map. This constructor only
        //! exists when all the elements of the map are move-constructible.
        constexpr map(map&& other) = default;

        //! Construct the map from the provided pairs. `P...` must be pairs of
        //! the same type (modulo ref and cv-qualifiers), and in the same order,
        //! as those appearing in `Pairs...`. The pairs provided to this
        //! constructor are emplaced into the map's storage using perfect
        //! forwarding.
        template <typename ...P>
        explicit constexpr map(P&& ...pairs);

        //! Assign a map to another map __with the exact same type__. Only
        //! exists when all the elements of the map are copy-assignable.
        constexpr map& operator=(map const& other);

        //! Move-assign a map to another map __with the exact same type__.
        //! Only exists when all the elements of the map are move-assignable.
        constexpr map& operator=(map&& other);

        //! Equivalent to `hana::equal`
        template <typename X, typename Y>
        friend constexpr auto operator==(X&& x, Y&& y);

        //! Equivalent to `hana::not_equal`
        template <typename X, typename Y>
        friend constexpr auto operator!=(X&& x, Y&& y);

        //! Equivalent to `hana::at_key`
        template <typename Key>
        constexpr decltype(auto) operator[](Key&& key);
    };
#else
    template <typename ...Pairs>
    using map = typename detail::make_map_type<Pairs...>::type;
#endif

    //! Function object for creating a `hana::map`.
    //! @relates hana::map
    //!
    //! Given zero or more `Product`s representing key/value associations,
    //! `make<map_tag>` returns a `hana::map` associating these keys to these
    //! values.
    //!
    //! `make<map_tag>` requires all the keys to be unique and to have
    //! different hashes. If you need to create a map with duplicate keys
    //! or with keys whose hashes might collide, use `hana::to_map` or
    //! insert `(key, value)` pairs to an empty map successively. However,
    //! be aware that doing so will be much more compile-time intensive than
    //! using `make<map_tag>`, because the uniqueness of keys will have to be
    //! enforced.
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/make.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    template <>
    constexpr auto make<map_tag> = [](auto&& ...pairs) {
        return map<implementation_defined>{forwarded(pairs)...};
    };
#endif

    //! Alias to `make<map_tag>`; provided for convenience.
    //! @relates hana::map
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/make.cpp
    constexpr auto make_map = make<map_tag>;

    //! Equivalent to `to<map_tag>`; provided for convenience.
    //! @relates hana::map
    constexpr auto to_map = to<map_tag>;

    //! Returns a `Sequence` of the keys of the map, in unspecified order.
    //! @relates hana::map
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/keys.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    constexpr auto keys = [](auto&& map) {
        return implementation_defined;
    };
#endif

    //! Returns a `Sequence` of the values of the map, in unspecified order.
    //! @relates hana::map
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/values.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    constexpr auto values = [](auto&& map) -> decltype(auto) {
        return implementation_defined;
    };
#else
    struct values_t {
        template <typename Map>
        constexpr decltype(auto) operator()(Map&& map) const;
    };

    constexpr values_t values{};
#endif

    //! Inserts a new key/value pair in a map.
    //! @relates hana::map
    //!
    //! Given a `(key, value)` pair, `insert` inserts this new pair into a
    //! map. If the map already contains this key, nothing is done and the
    //! map is returned as-is.
    //!
    //!
    //! @param map
    //! The map in which to insert a `(key,value)` pair.
    //!
    //! @param pair
    //! An arbitrary `Product` representing a `(key, value)` pair to insert
    //! in the map. The `key` must be compile-time `Comparable`.
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/insert.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    constexpr auto insert = [](auto&& map, auto&& pair) {
        return tag-dispatched;
    };
#endif

    //! Removes a key/value pair from a map.
    //! @relates hana::map
    //!
    //! Returns a new `hana::map` containing all the elements of the original,
    //! except for the `(key, value)` pair whose `key` compares `equal`
    //! to the given key. If the map does not contain such an element,
    //! a new map equal to the original is returned.
    //!
    //!
    //! @param map
    //! The map in which to erase a `key`.
    //!
    //! @param key
    //! A key to remove from the map. It must be compile-time `Comparable`.
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/erase_key.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    constexpr auto erase_key = [](auto&& map, auto&& key) {
        return tag-dispatched;
    };
#endif

    //! Returns the union of two maps.
    //! @relates hana::map
    //!
    //! Given two maps `xs` and `ys`, `hana::union_(xs, ys)` is a new map
    //! containing all the elements of `xs` and all the elements of `ys`,
    //! without duplicates. If both `xs` and `ys` contain an element with the
    //! same `key`, the one in `ys` is taken. Functionally,
    //! `hana::union_(xs, ys)` is equivalent to
    //! @code
    //! hana::fold_left(xs, ys, hana::insert)
    //! @endcode
    //!
    //! @param xs, ys
    //! The two maps to compute the union of.
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/union.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    constexpr auto union_ = [](auto&& xs, auto&& ys) {
        return tag-dispatched;
    };
#endif

    //! Returns the intersection of two maps.
    //! @relates hana::map
    //!
    //! Given two maps `xs` and `ys`, `intersection(xs, ys)` is a new map
    //! containing exactly those (key, value) pairs from xs, for which key
    //! is present in `ys`.
    //! In other words, the following holds for any object `pair(k, v)`:
    //! @code
    //!     pair(k, v) ^in^ intersection(xs, ys) if and only if (k, v) ^in^ xs && k ^in^ keys(ys)
    //! @endcode
    //!
    //!
    //! @note
    //! This function is not commutative, i.e. `intersection(xs, ys)` is not
    //! necessarily the same as `intersection(ys, xs)`. Indeed, the set of keys
    //! in `intersection(xs, ys)` is always the same as the set of keys in
    //! `intersection(ys, xs)`, but the value associated to each key may be
    //! different. `intersection(xs, ys)` contains values present in `xs`, and
    //! `intersection(ys, xs)` contains values present in `ys`.
    //!
    //!
    //! @param xs, ys
    //! Two maps to intersect.
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/intersection.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    constexpr auto intersection = [](auto&& xs, auto&& ys) {
        return tag-dispatched;
    };
#endif

    //! Returns the difference of two maps.
    //! @relates hana::map
    //!
    //! Given two maps `xs` and `ys`, `difference(xs, ys)` is a new map
    //! containing exactly those (key, value) pairs from xs, for which key
    //! is not present in `keys(ys)`.
    //! In other words, the following holds for any object `pair(k, v)`:
    //! @code
    //!     pair(k, v) ^in^ difference(xs, ys) if and only if (k, v) ^in^ xs && k ^not in^ keys(ys)
    //! @endcode
    //!
    //!
    //! @note
    //! This function is not commutative, i.e. `difference(xs, ys)` is not
    //! necessarily the same as `difference(ys, xs)`.
    //! Indeed, consider the case where `xs` is empty and `ys` isn't.
    //! In that case, `difference(xs, ys)` is empty, but `difference(ys, xs)`
    //! is equal to `ys`.
    //! For symmetric version of this operation, see `symmetric_difference`.
    //!
    //!
    //! @param xs, ys
    //! Two maps to compute the difference of.
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/intersection.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
    constexpr auto difference = [](auto&& xs, auto&& ys) {
        return tag-dispatched;
    };
#endif

    //! Returns the symmetric set-theoretic difference of two maps.
    //! @relates hana::map
    //!
    //! Given two sets `xs` and `ys`, `symmetric_difference(xs, ys)` is a new
    //! map containing all the elements of `xs` whose keys are not contained in `keys(ys)`,
    //! and all the elements of `ys` whose keys are not contained in `keys(xs)`. The
    //! symmetric difference of two maps satisfies the following:
    //! @code
    //!     symmetric_difference(xs, ys) == union_(difference(xs, ys), difference(ys, xs))
    //! @endcode
    //!
    //!
    //! @param xs, ys
    //! Two maps to compute the symmetric difference of.
    //!
    //!
    //! Example
    //! -------
    //! @include example/map/symmetric_difference.cpp
#ifdef BOOST_HANA_DOXYGEN_INVOKED
constexpr auto symmetric_difference = [](auto&& xs, auto&& ys) {
        return tag-dispatched;
    };
#endif


BOOST_HANA_NAMESPACE_END

#endif // !BOOST_HANA_FWD_MAP_HPP