Branch data Line data Source code
1 : : // *****************************************************************************
2 : : /*!
3 : : \file src/Base/ContainerUtil.hpp
4 : : \copyright 2012-2015 J. Bakosi,
5 : : 2016-2018 Los Alamos National Security, LLC.,
6 : : 2019-2021 Triad National Security, LLC.,
7 : : 2022-2024 J. Bakosi
8 : : All rights reserved. See the LICENSE file for details.
9 : : \brief Various STL container utilities
10 : : \details Various STL container utilities.
11 : : */
12 : : // *****************************************************************************
13 : : #ifndef ContainerUtil_h
14 : : #define ContainerUtil_h
15 : :
16 : : #include <vector>
17 : : #include <map>
18 : : #include <set>
19 : : #include <algorithm>
20 : : #include <iterator>
21 : : #include <unordered_set>
22 : : #include <unordered_map>
23 : : #include <type_traits>
24 : : #include <sstream>
25 : :
26 : : #include "Exception.hpp"
27 : :
28 : : namespace tk {
29 : :
30 : : //! Make elements of container unique (in-place, overwriting source container)
31 : : //! \param[in,out] c Container
32 : : template< class Container >
33 : : void
34 : 114885 : unique( Container& c )
35 : : {
36 : 114885 : std::sort( begin(c), end(c) );
37 : 114885 : auto it = std::unique( begin(c), end(c) );
38 : : auto d = std::distance( begin(c), it );
39 : : // cppcheck-suppress unsignedPositive
40 : : Assert( d >= 0, "Distance must be non-negative in tk::unique()" );
41 : 114885 : c.resize( static_cast< std::size_t >( d ) );
42 : 114885 : }
43 : :
44 : : //! Make elements of container unique (on a copy, leaving the source as is)
45 : : //! \param[in] src Container
46 : : //! \return Container containing only unique elements compared to src
47 : : template< class Container >
48 : : Container
49 : 10208 : uniquecopy( const Container& src )
50 : : {
51 : 10207 : auto c = src;
52 [ + - ]: 10208 : unique( c );
53 : 10208 : return c;
54 : 0 : }
55 : :
56 : : //! \brief Find and return a constant reference to value for key in container
57 : : //! that provides a find() member function with error handling
58 : : //! \param[in] map Map associating values to keys
59 : : //! \param[in] key Key to search for
60 : : //! \return A constant reference to the value associated to the key in map
61 : : //! \note If key is not found an exception is thrown.
62 : : template< typename Container >
63 : : auto cref_find( const Container& map, const typename Container::key_type& key )
64 : : noexcept(ndebug)
65 : : -> const typename Container::mapped_type&
66 : : {
67 : : const auto it = map.find( key );
68 : : // cppcheck-suppress throwInNoexceptFunction
69 : : Assert( it != end(map), "Can't find key" );
70 [ + - ][ + - ]: 422035 : return it->second;
[ - - ]
71 : : }
72 : :
73 : : //! \brief Find and return a reference to value for key in a container that
74 : : //! provides a find() member function with error handling
75 : : //! \param[in] map Map associating values to keys
76 : : //! \param[in] key Key to search for
77 : : //! \return A reference to the value associated to the key in map
78 : : //! \note If key is not found an exception is thrown.
79 : : template< typename Container >
80 : : auto ref_find( const Container& map, const typename Container::key_type& key )
81 : : noexcept(ndebug)
82 : : -> typename Container::mapped_type&
83 : : {
84 : : // cppcheck-suppress throwInNoexceptFunction
85 : : return const_cast< typename Container::mapped_type& >( cref_find(map,key) );
86 : : }
87 : :
88 : : //! \brief Return minimum and maximum values of a vector
89 : : //! \param[in] vec Vector whose extents to compute
90 : : //! \return Array of two values with the minimum and maximum values
91 : : //! \note This function should not be called with heavy T types, as the a copy
92 : : //! of a std::array< T, 2 > is created and returned.
93 : : template< typename T >
94 : : std::array< T, 2 >
95 : 2 : extents( const std::vector< T >& vec )
96 : : {
97 : 2 : auto x = std::minmax_element( begin(vec), end(vec) );
98 : 2 : return {{ *x.first, *x.second }};
99 : : }
100 : :
101 : : //! \brief Find and return minimum and maximum values in associative container
102 : : //! \param[in] map Map whose extents of values to find
103 : : //! \return Array of two values with the minimum and maximum values in the map
104 : : //! \note This function should not be called with heavy Value types, as the a
105 : : //! copy of a std::array< Value, 2 > is created and returned.
106 : : template< typename Container >
107 : 2 : auto extents( const Container& map )
108 : : -> std::array< typename Container::mapped_type, 2 >
109 : : {
110 : 2 : auto x = std::minmax_element( begin(map), end(map),
111 : : []( const auto& a, const auto& b )
112 [ + - ][ + - ]: 4 : { return a.second < b.second; } );
[ + - ][ - - ]
[ - - ][ - - ]
[ - - ][ - - ]
[ - + ][ - + ]
[ - - ][ - - ]
[ - - ][ - - ]
[ - - ][ - - ]
113 : 2 : return {{ x.first->second, x.second->second }};
114 : : }
115 : :
116 : : //! Add all elements of an array to those of another one
117 : : //! \param[in,out] dst Destination array, i.e., left-hand side of a1 += a2
118 : : //! \param[in] src Source array, i.e., righ-hand side of a1 += a2
119 : : //! \return Destination containing a1[0] += a2[0], a1[1] += a2[1], ...
120 : : template< class T, std::size_t N >
121 : : std::array< T, N >&
122 : : operator+=( std::array< T, N >& dst, const std::array< T, N >& src ) {
123 : : std::transform( src.cbegin(), src.cend(), dst.begin(), dst.begin(),
124 : 3 : []( const T& s, T& d ){ return d += s; } );
125 : : return dst;
126 : : }
127 : :
128 : : //! Add all elements of a vector to those of another one
129 : : //! \param[in,out] dst Destination vector, i.e., left-hand side of v1 += v2
130 : : //! \param[in] src Source vector, i.e., righ-hand side of v1 += v2
131 : : //! \return Destination containing v1[0] += v2[0], v1[1] += v2[1], ...
132 : : //! \details If src.size() > dst.size() will grow dst to that of src.size()
133 : : //! padding with zeros.
134 : : //! \note Will throw exception in DEBUG if src is empty (to warn on no-op), and
135 : : //! if src.size() < dst.size() (to warn on loosing data).
136 : : template< class T, class Allocator >
137 : : std::vector< T, Allocator >&
138 [ + + ]: 14103407 : operator+=( std::vector< T, Allocator >& dst,
139 : : const std::vector< T, Allocator >& src )
140 : : {
141 [ + + ]: 14103407 : if (src.empty()) return dst;
142 : : Assert( src.size() >= dst.size(), "src.size() < dst.size() would loose data "
143 : : "in std::vector<T,Allocator>::operator+=()" );
144 : 13938205 : dst.resize( src.size() );
145 : : std::transform( src.cbegin(), src.cend(), dst.begin(), dst.begin(),
146 : 85386105 : []( const T& s, T& d ){ return d += s; } );
147 : : return dst;
148 : : }
149 : :
150 : : //! Subtract all elements of a vector from those of another one
151 : : //! \param[in,out] dst Destination vector, i.e., left-hand side of v1 -= v2
152 : : //! \param[in] src Source vector, i.e., righ-hand side of v1 -= v2
153 : : //! \return Destination containing v1[0] -= v2[0], v1[1] -= v2[1], ...
154 : : //! \details If src.size() > dst.size() will grow dst to that of src.size()
155 : : //! padding with zeros.
156 : : //! \note Will throw exception in DEBUG if src is empty (to warn on no-op), and
157 : : //! if src.size() < dst.size() (to warn on loosing data).
158 : : template< class T, class Allocator >
159 : : std::vector< T, Allocator >&
160 [ + + ]: 5023 : operator-=( std::vector< T, Allocator >& dst,
161 : : const std::vector< T, Allocator >& src )
162 : : {
163 [ + + ]: 5023 : if (src.empty()) return dst;
164 : : Assert( src.size() >= dst.size(), "src.size() < dst.size() would loose data "
165 : : "in std::vector<T,Allocator>::operator-=()" );
166 : 5021 : dst.resize( src.size() );
167 : : std::transform( src.cbegin(), src.cend(), dst.begin(), dst.begin(),
168 : 509655 : []( const T& s, T& d ){ return d -= s; } );
169 : : return dst;
170 : : }
171 : :
172 : : //! Divide all elements of a vector with those of another one
173 : : //! \param[in,out] dst Destination vector, i.e., left-hand side of v1 /= v2
174 : : //! \param[in] src Source vector, i.e., righ-hand side of v1 /= v2
175 : : //! \return Destination containing v1[0] /= v2[0], v1[1] /= v2[1], ...
176 : : //! \details If src.size() > dst.size() will grow dst to that of src.size()
177 : : //! padding with zeros.
178 : : //! \note Will throw exception in DEBUG if src is empty (to warn on no-op), and
179 : : //! if src.size() < dst.size() (to warn on loosing data).
180 : : template< class T, class Allocator >
181 : : std::vector< T, Allocator >&
182 [ + - ]: 11068 : operator/=( std::vector< T, Allocator >& dst,
183 : : const std::vector< T, Allocator >& src )
184 : : {
185 [ + - ]: 11068 : if (src.empty()) return dst;
186 : : Assert( src.size() >= dst.size(), "src.size() < dst.size() would loose data "
187 : : "in std::vector<T,Allocator>::operator/=()" );
188 : 11068 : dst.resize( src.size() );
189 : : std::transform( src.cbegin(), src.cend(), dst.begin(), dst.begin(),
190 : 3286604 : []( const T& s, T& d ){ return d /= s; } );
191 : : return dst;
192 : : }
193 : :
194 : : //! Test if all keys of two associative containers are equal
195 : : //! \param[in] a 1st container to compare
196 : : //! \param[in] b 2nd container to compare
197 : : //! \return True if the containers have the same size and all keys (and only the
198 : : //! keys) of the two containers are equal
199 : : //! \note It is an error to call this function with unequal-size containers,
200 : : //! triggering an exception in DEBUG mode.
201 : : //! \note Operator != is used to compare the container keys.
202 : : template< class C1, class C2 >
203 : 2 : bool keyEqual( const C1& a, const C2& b ) {
204 : : Assert( a.size() == b.size(), "Size mismatch comparing containers" );
205 : : std::set< typename C1::key_type > sorted_keys_of_a;
206 [ + - ][ + + ]: 6 : for (const auto& c : a) sorted_keys_of_a.insert( c.first );
207 : : std::set< typename C2::key_type > sorted_keys_of_b;
208 [ + - ][ + + ]: 6 : for (const auto& c : b) sorted_keys_of_b.insert( c.first );
209 : 2 : return sorted_keys_of_a == sorted_keys_of_b;
210 : : }
211 : :
212 : : //! Compute the sum of the sizes of a container of containers
213 : : //! \param[in] c Container of containers
214 : : //! \return Sum of the sizes of the containers of the container
215 : : template< class Container >
216 : : std::size_t sumsize( const Container& c ) {
217 : : std::size_t sum = 0;
218 : : // cppcheck-suppress useStlAlgorithm
219 [ + + ]: 3 : for (const auto& s : c) sum += s.size();
220 : : return sum;
221 : : }
222 : :
223 : : //! Compute the number of unique values in a container of containers
224 : : //! \param[in] c Container of containers
225 : : //! \return Number of unique values in a container of containers
226 : : template< class Container >
227 : 3 : std::size_t numunique( const Container& c ) {
228 : : using value_type = typename Container::value_type::value_type;
229 : : static_assert( std::is_integral<value_type>::value,
230 : : "Container::value_type::value_type must be an integral type." );
231 : : std::unordered_set< value_type > u;
232 [ + + ]: 9 : for (const auto& r : c) u.insert( begin(r), end(r) );
233 : 3 : return u.size();
234 : : }
235 : :
236 : : //! Compute the sum of the sizes of the values of an associative container
237 : : //! \tparam Map Container of containers type
238 : : //! \param[in] c Container of containers
239 : : //! \return Sum of the sizes of the values of the associative container
240 : : template< class Map >
241 : 12 : std::size_t sumvalsize( const Map& c ) {
242 : : std::size_t sum = 0;
243 : : // cppcheck-suppress useStlAlgorithm
244 [ + + ]: 26968 : for (const auto& s : c) sum += s.second.size();
245 : 12 : return sum;
246 : : }
247 : :
248 : : //! Free memory of a container
249 : : //! \param[in] c Container defining a swap() member function
250 : : //! \details See http://stackoverflow.com/a/10465032 as to why this is done with
251 : : //! the swap() member function of the container.
252 : : //! \see Specializations of std::swap are documented at
253 : : //! http://en.cppreference.com/w/cpp/algorithm/swap
254 : : template< class Container >
255 : 519154 : void destroy( Container& c ) {
256 [ + - ]: 527361 : typename std::remove_reference< decltype(c) >::type().swap( c );
257 : 519154 : }
258 : :
259 : : //! Remove items from container based on predicate
260 : : //! \tparam Container Type of container to remove from
261 : : //! \tparam Predicate Type for functor defining the predicate
262 : : //! \param items Container object to remove from
263 : : //! \param predicate Predicate object instance to use
264 : : template< typename Container, typename Predicate >
265 : 245 : void erase_if( Container& items, const Predicate& predicate ) {
266 [ + + ]: 1617 : for ( auto it = items.begin(); it != items.end(); ) {
267 [ + + ]: 1372 : if ( predicate(*it) ) it = items.erase(it);
268 : : else ++it;
269 : : }
270 : 245 : }
271 : :
272 : : //! Concatenate vectors of T
273 : : //! \tparam T Vector value type
274 : : //! \param[in,out] src Source vector (moved from)
275 : : //! \param[in,out] dst Destination vector
276 : : template< class T >
277 : : void concat( std::vector< T >&& src, std::vector< T >& dst )
278 : : {
279 : : Assert( dst.empty(), "Dest vector must be empty to concat" );
280 : : dst = std::move(src);
281 : : }
282 : :
283 : : //! Overwrite vectors of pair< bool, tk::real >
284 : : //! \tparam T Vector value type
285 : : //! \param[in,out] src Source vector (moved from)
286 : : //! \param[in,out] dst Destination vector
287 : : template< class T >
288 : : void concat( std::vector< std::pair< bool, T > >&& src,
289 : : std::vector< std::pair< bool, T > >& dst )
290 : : {
291 : : dst = std::move(src);
292 : : }
293 : :
294 : : //! Concatenate unordered sets
295 : : //! \tparam Key Set key
296 : : //! \tparam Hash Set hasher
297 : : //! \tparam Eq Set equality operator
298 : : //! \param[in,out] src Source set (moved from)
299 : : //! \param[in,out] dst Destination set
300 : : template< class Key,
301 : : class Hash = std::hash< Key >,
302 : : class Eq = std::equal_to< Key > >
303 : : void concat( std::unordered_set< Key, Hash,Eq >&& src,
304 : : std::unordered_set< Key, Hash, Eq >& dst )
305 : : {
306 : : if (dst.empty())
307 : : dst = std::move(src);
308 : : else {
309 : : dst.reserve( dst.size() + src.size() );
310 : : std::move( std::begin(src), std::end(src), std::inserter(dst,end(dst)) );
311 : : src.clear();
312 : : }
313 : : }
314 : :
315 : : //! Operator << for writing value_type of a standard map to output streams
316 : : //! \param[in,out] os Output stream to write to
317 : : //! \param[in] v value_type entry of a map
318 : : //! \return Updated output stream
319 : : template< class Key, class Value >
320 : : std::ostream&
321 : : operator<< ( std::ostream& os, const std::pair< const Key, Value >& v ) {
322 : : os << v.first << ':' << v.second;
323 : : return os;
324 : : }
325 : :
326 : : //! \brief Convert and return value as string
327 : : //! \tparam T Value type for input
328 : : //! \param[in] v Value for input to return as a string
329 : : //! \return String for input value
330 : : template< typename T >
331 : : std::string parameter( const T& v ) {
332 : : std::stringstream s;
333 : : s << v;
334 : : return s.str();
335 : : }
336 : :
337 : : //! \brief Convert and return values from container as string
338 : : //! \tparam V Container range for works on
339 : : //! \param[in] v Container whose components to return as a string
340 : : //! \return Concatenated string of values read from a container
341 : : template< typename V >
342 : 0 : std::string parameters( const V& v ) {
343 : 0 : std::stringstream s;
344 [ - - ]: 0 : s << "{ ";
345 [ - - ][ - - ]: 0 : for (auto p : v) s << p << ' ';
[ - - ]
346 [ - - ]: 0 : s << "}";
347 : 0 : return s.str();
348 : 0 : }
349 : :
350 : : } // tk::
351 : :
352 : : #endif // ContainerUtil_h
|
