]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::Searchable`. | |
4 | ||
5 | @copyright Louis Dionne 2013-2016 | |
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | ||
15 | ||
16 | BOOST_HANA_NAMESPACE_BEGIN | |
17 | //! @ingroup group-concepts | |
18 | //! @defgroup group-Searchable Searchable | |
19 | //! The `Searchable` concept represents structures that can be searched. | |
20 | //! | |
21 | //! Intuitively, a `Searchable` is any structure, finite or infinite, | |
22 | //! containing elements that can be searched using a predicate. Sometimes, | |
23 | //! `Searchable`s will associate keys to values; one can search for a key | |
24 | //! with a predicate, and the value associated to it is returned. This | |
25 | //! gives rise to map-like data structures. Other times, the elements of | |
26 | //! the structure that are searched (i.e. those to which the predicate is | |
27 | //! applied) are the same that are returned, which gives rise to set-like | |
28 | //! data structures. In general, we will refer to the _keys_ of a | |
29 | //! `Searchable` structure as those elements that are used for searching, | |
30 | //! and to the _values_ of a `Searchable` as those elements that are | |
31 | //! returned when a search is successful. As was explained, there is no | |
32 | //! requirement that both notions differ, and it is often useful to have | |
33 | //! keys and values coincide (think about `std::set`). | |
34 | //! | |
35 | //! Some methods like `any_of`, `all_of` and `none_of` allow simple queries | |
36 | //! to be performed on the keys of the structure, while other methods like | |
37 | //! `find` and `find_if` make it possible to find the value associated | |
38 | //! to a key. The most specific method should always be used if one | |
39 | //! cares about performance, because it is usually the case that heavy | |
40 | //! optimizations can be performed in more specific methods. For example, | |
41 | //! an associative data structure implemented as a hash table will be much | |
42 | //! faster to access using `find` than `find_if`, because in the second | |
43 | //! case it will have to do a linear search through all the entries. | |
44 | //! Similarly, using `contains` will likely be much faster than `any_of` | |
45 | //! with an equivalent predicate. | |
46 | //! | |
47 | //! > __Insight__\n | |
48 | //! > In a lazy evaluation context, any `Foldable` can also become a model | |
49 | //! > of `Searchable` because we can search lazily through the structure | |
50 | //! > with `fold_right`. However, in the context of C++, some `Searchable`s | |
51 | //! > can not be folded; think for example of an infinite set. | |
52 | //! | |
53 | //! | |
54 | //! Minimal complete definition | |
55 | //! --------------------------- | |
56 | //! `find_if` and `any_of` | |
57 | //! | |
58 | //! When `find_if` and `any_of` are provided, the other functions are | |
59 | //! implemented according to the laws explained below. | |
60 | //! | |
61 | //! @note | |
62 | //! We could implement `any_of(xs, pred)` by checking whether | |
63 | //! `find_if(xs, pred)` is an empty `optional` or not, and then reduce | |
64 | //! the minimal complete definition to `find_if`. However, this is not | |
65 | //! done because that implementation requires the predicate of `any_of` | |
66 | //! to return a compile-time `Logical`, which is more restrictive than | |
67 | //! what we have right now. | |
68 | //! | |
69 | //! | |
70 | //! Laws | |
71 | //! ---- | |
72 | //! In order for the semantics of the methods to be consistent, some | |
73 | //! properties must be satisfied by any model of the `Searchable` concept. | |
74 | //! Rigorously, for any `Searchable`s `xs` and `ys` and any predicate `p`, | |
75 | //! the following laws should be satisfied: | |
76 | //! @code | |
77 | //! any_of(xs, p) <=> !all_of(xs, negated p) | |
78 | //! <=> !none_of(xs, p) | |
79 | //! | |
80 | //! contains(xs, x) <=> any_of(xs, equal.to(x)) | |
81 | //! | |
82 | //! find(xs, x) == find_if(xs, equal.to(x)) | |
83 | //! find_if(xs, always(false_)) == nothing | |
84 | //! | |
85 | //! is_subset(xs, ys) <=> all_of(xs, [](auto x) { return contains(ys, x); }) | |
86 | //! is_disjoint(xs, ys) <=> none_of(xs, [](auto x) { return contains(ys, x); }) | |
87 | //! @endcode | |
88 | //! | |
89 | //! Additionally, if all the keys of the `Searchable` are `Logical`s, | |
90 | //! the following laws should be satisfied: | |
91 | //! @code | |
92 | //! any(xs) <=> any_of(xs, id) | |
93 | //! all(xs) <=> all_of(xs, id) | |
94 | //! none(xs) <=> none_of(xs, id) | |
95 | //! @endcode | |
96 | //! | |
97 | //! | |
98 | //! Concrete models | |
99 | //! --------------- | |
100 | //! `hana::map`, `hana::optional`, `hana::range`, `hana::set`, | |
101 | //! `hana::string`, `hana::tuple` | |
102 | //! | |
103 | //! | |
104 | //! Free model for builtin arrays | |
105 | //! ----------------------------- | |
106 | //! Builtin arrays whose size is known can be searched as-if they were | |
107 | //! homogeneous tuples. However, since arrays can only hold objects of | |
108 | //! a single type and the predicate to `find_if` must return a compile-time | |
109 | //! `Logical`, the `find_if` method is fairly useless. For similar reasons, | |
110 | //! the `find` method is also fairly useless. This model is provided mainly | |
111 | //! because of the `any_of` method & friends, which are both useful and | |
112 | //! compile-time efficient. | |
113 | //! | |
114 | //! | |
115 | //! Structure preserving functions | |
116 | //! ------------------------------ | |
117 | //! Given two `Searchables` `S1` and `S2`, a function | |
118 | //! @f$ f : S_1(X) \to S_2(X) @f$ is said to preserve the `Searchable` | |
119 | //! structure if for all `xs` of data type `S1(X)` and predicates | |
120 | //! @f$ \mathtt{pred} : X \to Bool @f$ (for a `Logical` `Bool`), | |
121 | //! @code | |
122 | //! any_of(xs, pred) if and only if any_of(f(xs), pred) | |
123 | //! find_if(xs, pred) == find_if(f(xs), pred) | |
124 | //! @endcode | |
125 | //! | |
126 | //! This is really just a generalization of the following, more intuitive | |
127 | //! requirements. For all `xs` of data type `S1(X)` and `x` of data type | |
128 | //! `X`, | |
129 | //! @code | |
130 | //! x ^in^ xs if and only if x ^in^ f(xs) | |
131 | //! find(xs, x) == find(f(xs), x) | |
132 | //! @endcode | |
133 | //! | |
134 | //! These requirements can be understood as saying that `f` does not | |
135 | //! change the content of `xs`, although it may reorder elements. | |
136 | //! As usual, such a structure-preserving transformation is said to | |
137 | //! be an embedding if it is also injective, i.e. if it is a lossless | |
138 | //! transformation. | |
139 | template <typename S> | |
140 | struct Searchable; | |
141 | BOOST_HANA_NAMESPACE_END | |
142 | ||
143 | #endif // !BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP |