File indexing completed on 2024-11-24 04:49:38
0001 /**************************************************************************** 0002 ** SPDX-FileCopyrightText: 2001-2007 Klarälvdalens Datakonsult AB. All rights reserved. 0003 ** 0004 ** This file is part of the KD Tools library. 0005 ** 0006 ** SPDX-License-Identifier: GPL-2.0-or-later 0007 ** 0008 **********************************************************************/ 0009 0010 #pragma once 0011 0012 #include <algorithm> 0013 #include <functional> 0014 #include <iterator> 0015 #include <numeric> 0016 #include <utility> 0017 0018 namespace kdtools 0019 { 0020 template<typename _Iterator, typename UnaryPredicate> 0021 struct filter_iterator { 0022 using value_type = typename std::iterator_traits<_Iterator>::value_type; 0023 using reference = typename std::iterator_traits<_Iterator>::reference; 0024 using pointer = typename std::iterator_traits<_Iterator>::pointer; 0025 using difference_type = typename std::iterator_traits<_Iterator>::difference_type; 0026 0027 filter_iterator(UnaryPredicate pred, _Iterator it, _Iterator last) 0028 : it(it) 0029 , last(last) 0030 , pred(pred) 0031 { 0032 } 0033 template<typename _OtherIter> 0034 filter_iterator(const filter_iterator<_OtherIter, UnaryPredicate> &other) 0035 : it(other.it) 0036 , last(other.last) 0037 , pred(other.pred) 0038 { 0039 } 0040 filter_iterator &operator++() 0041 { 0042 while (++it != last && !pred(*it)) { } 0043 return *this; 0044 } 0045 filter_iterator operator++(int) 0046 { 0047 auto retval = *this; 0048 while (++it != last && !pred(*it)) { } 0049 return retval; 0050 } 0051 bool operator==(filter_iterator other) const 0052 { 0053 return it == other.it; 0054 } 0055 bool operator!=(filter_iterator other) const 0056 { 0057 return it != other.it; 0058 } 0059 typename _Iterator::reference operator*() const 0060 { 0061 return *it; 0062 } 0063 0064 private: 0065 _Iterator it, last; 0066 UnaryPredicate pred; 0067 }; 0068 0069 template<typename _Iterator, typename UnaryPredicate> 0070 filter_iterator<typename std::decay<_Iterator>::type, UnaryPredicate> make_filter_iterator(UnaryPredicate &&pred, _Iterator &&it, _Iterator &&last) 0071 { 0072 return filter_iterator<typename std::decay<_Iterator>::type, UnaryPredicate>(std::forward<UnaryPredicate>(pred), 0073 std::forward<_Iterator>(it), 0074 std::forward<_Iterator>(last)); 0075 } 0076 0077 template<typename InputIterator, typename OutputIterator, typename UnaryPredicate> 0078 OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred) 0079 { 0080 while (first != last) { 0081 if (pred(*first)) { 0082 *dest = *first; 0083 ++dest; 0084 } 0085 ++first; 0086 } 0087 return dest; 0088 } 0089 0090 template<typename OutputIterator, typename InputIterator, typename UnaryFunction, typename UnaryPredicate> 0091 void transform_if(InputIterator first, InputIterator last, OutputIterator dest, UnaryPredicate pred, UnaryFunction filter) 0092 { 0093 for (; first != last; ++first) { 0094 if (filter(*first)) { 0095 *dest++ = pred(*first); 0096 } 0097 } 0098 } 0099 0100 template<typename InputIterator, typename OutputIterator, typename Predicate> 0101 OutputIterator copy_1st_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred) 0102 { 0103 const auto trans = [](typename std::iterator_traits<InputIterator>::reference v) { 0104 return std::get<0>(v); 0105 }; 0106 kdtools::transform_if(first, // 0107 last, 0108 dest, 0109 trans, 0110 [&pred, &trans](typename std::iterator_traits<InputIterator>::reference v) { 0111 return pred(trans(v)); 0112 }); 0113 return dest; 0114 } 0115 0116 template<typename InputIterator, typename OutputIterator, typename Predicate> 0117 OutputIterator copy_2nd_if(InputIterator first, InputIterator last, OutputIterator dest, Predicate pred) 0118 { 0119 const auto trans = [](typename std::iterator_traits<InputIterator>::reference v) { 0120 return std::get<1>(v); 0121 }; 0122 kdtools::transform_if(first, // 0123 last, 0124 dest, 0125 trans, 0126 [&pred, &trans](typename std::iterator_traits<InputIterator>::reference v) { 0127 return pred(trans(v)); 0128 }); 0129 return dest; 0130 } 0131 0132 template<typename OutputIterator, typename InputIterator, typename UnaryFunction> 0133 OutputIterator transform_1st(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func) 0134 { 0135 return std::transform(first, // 0136 last, 0137 dest, 0138 [func](typename std::iterator_traits<InputIterator>::reference v) { 0139 return func(std::get<0>(v)); 0140 }); 0141 } 0142 0143 template<typename OutputIterator, typename InputIterator, typename UnaryFunction> 0144 OutputIterator transform_2nd(InputIterator first, InputIterator last, OutputIterator dest, UnaryFunction func) 0145 { 0146 return std::transform(first, // 0147 last, 0148 dest, 0149 [func](typename std::iterator_traits<InputIterator>::reference v) { 0150 return func(std::get<1>(v)); 0151 }); 0152 } 0153 0154 template<typename Value, typename InputIterator, typename UnaryPredicate> 0155 Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value = Value()) 0156 { 0157 return std::accumulate(make_filter_iterator(filter, first, last), // 0158 make_filter_iterator(filter, last, last), 0159 value); 0160 } 0161 0162 template<typename Value, typename InputIterator, typename UnaryPredicate, typename BinaryOperation> 0163 Value accumulate_if(InputIterator first, InputIterator last, UnaryPredicate filter, const Value &value, BinaryOperation op) 0164 { 0165 return std::accumulate(make_filter_iterator(filter, first, last), // 0166 make_filter_iterator(filter, last, last), 0167 value, 0168 op); 0169 } 0170 0171 template<typename Value, typename InputIterator, typename UnaryFunction> 0172 Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value = Value()) 0173 { 0174 return std::accumulate(first, // 0175 last, 0176 value, 0177 [map](Value lhs, typename std::iterator_traits<InputIterator>::reference rhs) { 0178 return lhs + map(rhs); 0179 }); 0180 } 0181 0182 template<typename Value, typename InputIterator, typename UnaryFunction, typename BinaryOperation> 0183 Value accumulate_transform(InputIterator first, InputIterator last, UnaryFunction map, const Value &value, BinaryOperation op) 0184 { 0185 return std::accumulate(first, // 0186 last, 0187 value, 0188 [map, op](typename InputIterator::reference lhs, typename InputIterator::reference rhs) { 0189 return op(map(lhs), map(rhs)); 0190 }); 0191 } 0192 0193 template<typename Value, typename InputIterator, typename UnaryFunction, typename UnaryPredicate, typename BinaryOperation> 0194 Value accumulate_transform_if(InputIterator first, InputIterator last, UnaryFunction map, UnaryPredicate filter, const Value &value, BinaryOperation op) 0195 { 0196 return accumulate_transform(make_filter_iterator(filter, first, last), // 0197 make_filter_iterator(filter, last, last), 0198 map, 0199 value, 0200 op); 0201 } 0202 0203 template<typename InputIterator, typename BinaryOperation> 0204 BinaryOperation for_each_adjacent_pair(InputIterator first, InputIterator last, BinaryOperation op) 0205 { 0206 using ValueType = typename std::iterator_traits<InputIterator>::value_type; 0207 if (first == last) { 0208 return op; 0209 } 0210 ValueType value = *first; 0211 while (++first != last) { 0212 ValueType tmp = *first; 0213 op(value, tmp); 0214 value = tmp; 0215 } 0216 return op; 0217 } 0218 0219 template<typename InputIterator, typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate> 0220 std::pair<OutputIterator1, OutputIterator2> 0221 separate_if(InputIterator first, InputIterator last, OutputIterator1 dest1, OutputIterator2 dest2, UnaryPredicate pred) 0222 { 0223 while (first != last) { 0224 if (pred(*first)) { 0225 *dest1 = *first; 0226 ++dest1; 0227 } else { 0228 *dest2 = *first; 0229 ++dest2; 0230 } 0231 ++first; 0232 } 0233 return std::make_pair(dest1, dest2); 0234 } 0235 0236 //@{ 0237 /** 0238 Versions of std::set_intersection optimized for ForwardIterator's 0239 */ 0240 template<typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate> 0241 OutputIterator set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result) 0242 { 0243 while (first1 != last1 && first2 != last2) { 0244 if (*first1 < *first2) { 0245 first1 = std::lower_bound(++first1, last1, *first2); 0246 } else if (*first2 < *first1) { 0247 first2 = std::lower_bound(++first2, last2, *first1); 0248 } else { 0249 *result = *first1; 0250 ++first1; 0251 ++first2; 0252 ++result; 0253 } 0254 } 0255 return result; 0256 } 0257 0258 template<typename ForwardIterator, typename ForwardIterator2, typename OutputIterator, typename BinaryPredicate> 0259 OutputIterator 0260 set_intersection(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, OutputIterator result, BinaryPredicate pred) 0261 { 0262 while (first1 != last1 && first2 != last2) { 0263 if (pred(*first1, *first2)) { 0264 first1 = std::lower_bound(++first1, last1, *first2, pred); 0265 } else if (pred(*first2, *first1)) { 0266 first2 = std::lower_bound(++first2, last2, *first1, pred); 0267 } else { 0268 *result = *first1; 0269 ++first1; 0270 ++first2; 0271 ++result; 0272 } 0273 } 0274 return result; 0275 } 0276 //@} 0277 0278 template<typename ForwardIterator, typename ForwardIterator2, typename BinaryPredicate> 0279 bool set_intersects(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred) 0280 { 0281 while (first1 != last1 && first2 != last2) { 0282 if (pred(*first1, *first2)) { 0283 first1 = std::lower_bound(++first1, last1, *first2, pred); 0284 } else if (pred(*first2, *first1)) { 0285 first2 = std::lower_bound(++first2, last2, *first1, pred); 0286 } else { 0287 return true; 0288 } 0289 } 0290 return false; 0291 } 0292 0293 }