Line data Source code
1 : // Author(s): Wieger Wesselink
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 : //
9 :
10 : #ifndef MCRL2_UTILITIES_DETAIL_CONTAINER_UTILITY_H
11 : #define MCRL2_UTILITIES_DETAIL_CONTAINER_UTILITY_H
12 :
13 : #include <algorithm>
14 : #include <iterator>
15 : #include <vector>
16 : #include <map>
17 : #include <set>
18 : #include <unordered_set>
19 : #include "mcrl2/utilities/exception.h"
20 :
21 : namespace mcrl2 {
22 :
23 : namespace utilities {
24 :
25 : namespace detail {
26 :
27 : /// \brief Returns the value corresponding to the given key in the map m. If the key is not
28 : /// present, an exception is thrown.
29 : template <typename Map>
30 : typename Map::mapped_type map_element(const Map& m, const typename Map::key_type& key)
31 : {
32 : auto i = m.find(key);
33 : if (i == m.end())
34 : {
35 : std::ostringstream out;
36 : out << "missing key in map!";
37 : throw mcrl2::runtime_error(out.str());
38 : }
39 : return i->second;
40 : }
41 :
42 : // Returns the value corresponding to the given key in map m, or undefined_value if no such value exists.
43 : template <typename Map>
44 4 : typename Map::mapped_type mapped_value(const Map& m, const typename Map::key_type& key, const typename Map::mapped_type& undefined_value)
45 : {
46 4 : auto i = m.find(key);
47 4 : if (i != m.end())
48 : {
49 4 : return i->second;
50 : }
51 0 : return undefined_value;
52 : }
53 :
54 : /// \brief Returns the value corresponding to the given key in the set m. If the key is not
55 : /// present, an exception is thrown.
56 : template <typename Container>
57 50705 : bool contains(const Container& c, const typename Container::value_type& v)
58 : {
59 50705 : return std::find(c.begin(), c.end(), v) != c.end();
60 : }
61 :
62 : // specialization
63 : template <typename T>
64 87595 : bool contains(const std::set<T>& c, const typename std::set<T>::value_type& v)
65 : {
66 87595 : return c.find(v) != c.end();
67 : }
68 :
69 : // specialization
70 : template <typename T>
71 131 : bool contains(const std::multiset<T>& c, const typename std::multiset<T>::value_type& v)
72 : {
73 131 : return c.find(v) != c.end();
74 : }
75 :
76 : // specialization
77 : template <typename T>
78 0 : bool contains(const std::unordered_set<T>& c, const typename std::set<T>::value_type& v)
79 : {
80 0 : return c.find(v) != c.end();
81 : }
82 :
83 : /// \brief Returns the value corresponding to the given key in the set m. If the key is not
84 : /// present, an exception is thrown.
85 : template <typename Key, typename T>
86 3 : bool has_key(const std::map<Key, T>& c, const Key& v)
87 : {
88 3 : return c.find(v) != c.end();
89 : }
90 :
91 : /// \brief Returns the value corresponding to the given key in the set m. If the key is not
92 : /// present, an exception is thrown.
93 : template <typename Key, typename T>
94 : bool has_key(const std::multimap<Key, T>& c, const Key& v)
95 : {
96 : return c.find(v) != c.end();
97 : }
98 :
99 : // Remove an element from v, and return it.
100 : template <typename Container>
101 171 : typename Container::value_type pick_element(Container& v)
102 : {
103 171 : auto i = v.begin();
104 171 : auto result = *i;
105 171 : v.erase(i);
106 261 : return result;
107 0 : }
108 :
109 : // inserts elements of c into s
110 : template <typename T, typename Container>
111 : void set_insert(std::set<T>& s, const Container& c)
112 : {
113 : for (auto i = c.begin(); i != c.end(); ++i)
114 : {
115 : s.insert(*i);
116 : }
117 : }
118 :
119 : // removes elements of c from s
120 : template <typename T, typename Container>
121 : void set_remove(std::set<T>& s, const Container& c)
122 : {
123 : for (auto i = c.begin(); i != c.end(); ++i)
124 : {
125 : s.erase(*i);
126 : }
127 : }
128 :
129 : // C++11; works for sets and maps
130 : // Removes elements that satisfy predicate pred.
131 : template< typename ContainerT, typename PredicateT >
132 179173 : void remove_if(ContainerT& items, const PredicateT& predicate)
133 : {
134 693643 : for (auto it = items.begin(); it != items.end();)
135 : {
136 514470 : if (predicate(*it))
137 : {
138 319102 : it = items.erase(it);
139 : }
140 : else
141 : {
142 195368 : ++it;
143 : }
144 : }
145 179173 : }
146 :
147 : /// Returns true if the sorted ranges [first1, ..., last1) and [first2, ..., last2) have an empty intersection
148 : template <typename InputIterator1, typename InputIterator2>
149 140 : bool has_empty_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
150 : {
151 308 : while (first1 != last1 && first2 != last2)
152 : {
153 273 : if (*first1 < *first2)
154 : {
155 65 : ++first1;
156 : }
157 208 : else if (*first2 < *first1)
158 : {
159 103 : ++first2;
160 : }
161 : else
162 : {
163 105 : return false;
164 : }
165 : }
166 35 : return true;
167 : }
168 :
169 : template <typename SetContainer1, typename SetContainer2>
170 132 : bool has_empty_intersection(const SetContainer1& s1, const SetContainer2& s2)
171 : {
172 132 : return has_empty_intersection(s1.begin(), s1.end(), s2.begin(), s2.end());
173 : }
174 :
175 : /// \brief Returns the union of two sets.
176 : /// \param x A set
177 : /// \param y A set
178 : /// \return The union of two sets.
179 : template <typename T>
180 43 : std::set<T> set_union(const std::set<T>& x, const std::set<T>& y)
181 : {
182 43 : std::set<T> result;
183 43 : std::set_union(x.begin(), x.end(), y.begin(), y.end(), std::inserter(result, result.begin()));
184 43 : return result;
185 0 : }
186 :
187 : /// \brief Returns the difference of two sets.
188 : /// \param x A set
189 : /// \param y A set
190 : /// \return The difference of two sets.
191 : template <typename T>
192 75 : std::set<T> set_difference(const std::set<T>& x, const std::set<T>& y)
193 : {
194 75 : std::set<T> result;
195 75 : std::set_difference(x.begin(), x.end(), y.begin(), y.end(), std::inserter(result, result.begin()));
196 75 : return result;
197 0 : }
198 :
199 : /// \brief Returns the intersection of two sets.
200 : /// \param x A set
201 : /// \param y A set
202 : /// \return The intersection of two sets.
203 : template <typename T>
204 10023 : std::set<T> set_intersection(const std::set<T>& x, const std::set<T>& y)
205 : {
206 10023 : std::set<T> result;
207 10023 : std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::inserter(result, result.begin()));
208 10023 : return result;
209 0 : }
210 :
211 : /// \brief Returns if y is included in x.
212 : /// \param x A set
213 : /// \param y A set
214 : /// \return The intersection of two sets.
215 : template <typename T>
216 6 : bool set_includes(const std::set<T>& x, const std::set<T>& y)
217 : {
218 6 : return std::includes(x.begin(), x.end(), y.begin(), y.end());
219 : }
220 :
221 :
222 : template <typename T>
223 : std::vector<T> as_vector(const std::set<T>& x)
224 : {
225 : return std::vector<T>(x.begin(), x.end());
226 : }
227 :
228 : template <typename T>
229 : std::set<T> as_set(const std::vector<T>& x)
230 : {
231 : return std::set<T>(x.begin(), x.end());
232 : }
233 :
234 : } // namespace detail
235 :
236 : } // namespace utilities
237 :
238 : } // namespace mcrl2
239 :
240 : #endif // MCRL2_UTILITIES_DETAIL_CONTAINER_UTILITY_H
|
