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