1 // Copyright 2015, Tobias Hermann and the FunctionalPlus contributors.
2 // https://github.com/Dobiasd/FunctionalPlus
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 #pragma once
8
9 #include <fplus/maybe.hpp>
10 #include <fplus/result.hpp>
11 #include <fplus/container_common.hpp>
12
13 #include <algorithm>
14
15 namespace fplus
16 {
17
18 namespace internal
19 {
20
21 template <typename Pred, typename Container>
keep_if(internal::reuse_container_t,Pred pred,Container && xs)22 Container keep_if(internal::reuse_container_t, Pred pred, Container&& xs)
23 {
24 internal::check_unary_predicate_for_container<Pred, Container>();
25 xs.erase(std::remove_if(
26 std::begin(xs), std::end(xs), logical_not(pred)), std::end(xs));
27 return std::forward<Container>(xs);
28 }
29
30 template <typename Pred, typename Container>
keep_if(internal::create_new_container_t,Pred pred,const Container & xs)31 Container keep_if(internal::create_new_container_t, Pred pred,
32 const Container& xs)
33 {
34 internal::check_unary_predicate_for_container<Pred, Container>();
35 Container result;
36 auto it = internal::get_back_inserter<Container>(result);
37 std::copy_if(std::begin(xs), std::end(xs), it, pred);
38 return result;
39 }
40
41 } // namespace internal
42
43 // API search type: keep_if : ((a -> Bool), [a]) -> [a]
44 // fwd bind count: 1
45 // Keep the elements of a sequence fulfilling a predicate.
46 // keep_if(is_even, [1, 2, 3, 2, 4, 5]) == [2, 2, 4]
47 // Also known as filter.
48 template <typename Pred, typename Container,
49 typename ContainerOut = internal::remove_const_and_ref_t<Container>>
keep_if(Pred pred,Container && xs)50 ContainerOut keep_if(Pred pred, Container&& xs)
51 {
52 return internal::keep_if(internal::can_reuse_v<Container>{},
53 pred, std::forward<Container>(xs));
54 }
55
56 // API search type: drop_if : ((a -> Bool), [a]) -> [a]
57 // fwd bind count: 1
58 // Drop the elements of a sequence fulfilling a predicate.
59 // drop_if(is_even, [1, 2, 3, 2, 4, 5]) == [1, 3, 5]
60 // Also known as reject.
61 template <typename Pred, typename Container,
62 typename ContainerOut = internal::remove_const_and_ref_t<Container>>
drop_if(Pred pred,Container && xs)63 ContainerOut drop_if(Pred pred, Container&& xs)
64 {
65 return keep_if(logical_not(pred), std::forward<Container>(xs));
66 }
67
68 // API search type: without : (a, [a]) -> [a]
69 // fwd bind count: 1
70 // Keep all elements a sequence not equal to elem.
71 // without(0, [1, 0, 0, 5, 3, 0, 1]) == [1, 5, 3, 1]
72 template <typename Container,
73 typename T = typename Container::value_type,
74 typename ContainerOut = internal::remove_const_and_ref_t<Container>>
without(T elem,Container && xs)75 ContainerOut without(T elem, Container&& xs)
76 {
77 return drop_if(is_equal_to(elem), std::forward<Container>(xs));
78 }
79
80 // API search type: without_any : (a, [a]) -> [a]
81 // fwd bind count: 1
82 // Keep all elements a sequence not present in elems.
83 // without([0, 1], [1, 0, 0, 5, 3, 0, 1]) == [5, 3]
84 template <typename Container, typename ContainerElems,
85 typename ContainerOut = internal::remove_const_and_ref_t<Container>>
without_any(const ContainerElems & elems,Container && xs)86 ContainerOut without_any(const ContainerElems& elems, Container&& xs)
87 {
88 static_assert(std::is_same<
89 typename ContainerElems::value_type,
90 typename std::remove_reference<Container>::type::value_type>::value,
91 "Container values must be of the same type.");
92 const auto pred = bind_2nd_of_2(is_elem_of<ContainerElems>, elems);
93 return drop_if(pred, std::forward<Container>(xs));
94 }
95
96 // API search type: keep_if_with_idx : (((Int, a) -> Bool), [a]) -> [a]
97 // fwd bind count: 1
98 // Keep the elements of a sequence fulfilling a predicate.
99 // Predicate takes index and value.
100 // All elements fulfilling the predicate are kept.
101 template <typename Pred, typename Container>
keep_if_with_idx(Pred pred,const Container & xs)102 Container keep_if_with_idx(Pred pred, const Container& xs)
103 {
104 internal::check_index_with_type_predicate_for_container<Pred, Container>();
105 Container ys;
106 auto it = internal::get_back_inserter<Container>(ys);
107 std::size_t idx = 0;
108 for (const auto& x : xs)
109 {
110 if (internal::invoke(pred, idx++, x))
111 *it = x;
112 }
113 return ys;
114 }
115
116 // API search type: drop_if_with_idx : (((Int, a) -> Bool), [a]) -> [a]
117 // fwd bind count: 1
118 // Drop the elements of a sequence fulfilling a predicate.
119 // Predicate takes index and value.
120 // All elements fulfilling the predicate are skipped.
121 template <typename Pred, typename Container>
drop_if_with_idx(Pred pred,const Container & xs)122 Container drop_if_with_idx(Pred pred, const Container& xs)
123 {
124 internal::check_index_with_type_predicate_for_container<Pred, Container>();
125 const auto inverse_pred = [pred](auto idx, const auto& x)
126 {
127 return !internal::invoke(pred, idx, x);
128 };
129 return keep_if_with_idx(inverse_pred, xs);
130 }
131
132 namespace internal
133 {
134
135 template <typename UnaryPredicate, typename Container>
keep_by_idx(internal::reuse_container_t,UnaryPredicate pred,Container && xs)136 Container keep_by_idx(internal::reuse_container_t,
137 UnaryPredicate pred, Container&& xs)
138 {
139 auto itOut = std::begin(xs);
140 std::size_t i = 0;
141 for (auto it = std::begin(xs); it != std::end(xs); ++it)
142 {
143 if (internal::invoke(pred, i++))
144 assign(*itOut++, std::move(*it));
145 }
146 xs.erase(itOut, std::end(xs));
147 return std::forward<Container>(xs);
148 }
149
150 template <typename UnaryPredicate, typename Container>
keep_by_idx(internal::create_new_container_t,UnaryPredicate pred,const Container & xs)151 Container keep_by_idx(internal::create_new_container_t,
152 UnaryPredicate pred, const Container& xs)
153 {
154 Container ys = xs;
155 return internal::keep_by_idx(internal::reuse_container_t(),
156 pred, std::move(ys));
157 }
158
159 } // namespace internal
160
161 // API search type: keep_by_idx : ((Int -> Bool), [a]) -> [a]
162 // fwd bind count: 1
163 // Keep the elements of a sequence with an index fulfilling a predicate.
164 // Predicate takes an index and decides if an element is kept.
165 template <typename UnaryPredicate, typename Container,
166 typename ContainerOut = internal::remove_const_and_ref_t<Container>>
keep_by_idx(UnaryPredicate pred,Container && xs)167 ContainerOut keep_by_idx(UnaryPredicate pred, Container&& xs)
168 {
169 internal::check_unary_predicate_for_type<UnaryPredicate, std::size_t>();
170 return internal::keep_by_idx(internal::can_reuse_v<Container>{},
171 pred, std::forward<Container>(xs));
172 }
173
174 // API search type: drop_by_idx : ((Int -> Bool), [a]) -> [a]
175 // fwd bind count: 1
176 // Drop the elements of a sequence with an index fulfilling a predicate.
177 // Predicate takes an index and decides if an element is dropped.
178 template <typename UnaryPredicate, typename Container,
179 typename ContainerOut = internal::remove_const_and_ref_t<Container>>
drop_by_idx(UnaryPredicate pred,Container && xs)180 ContainerOut drop_by_idx(UnaryPredicate pred, Container&& xs)
181 {
182 internal::check_unary_predicate_for_type<UnaryPredicate, std::size_t>();
183 return keep_by_idx(logical_not(pred), std::forward<Container>(xs));
184 }
185
186 // API search type: keep_idxs : ([Int], [a]) -> [a]
187 // fwd bind count: 1
188 // Keep the elements of a sequence with an index present in idxs_to_keep.
189 // keep_idxs([2,5], [1,2,3,4,5,6,7]) == [3,6]
190 template <typename ContainerIdxs, typename Container>
keep_idxs(const ContainerIdxs & idxs_to_keep,const Container & xs)191 Container keep_idxs(const ContainerIdxs& idxs_to_keep, const Container& xs)
192 {
193 static_assert(std::is_same<typename ContainerIdxs::value_type, std::size_t>::value,
194 "Indices must be std::size_t");
195 auto idxs_left = convert_container<std::list<std::size_t>>(
196 unique(sort(idxs_to_keep)));
197 Container ys;
198 auto it = internal::get_back_inserter<Container>(ys);
199 std::size_t idx = 0;
200 for (const auto& x : xs)
201 {
202 if (!idxs_left.empty() && idxs_left.front() == idx)
203 {
204 idxs_left.pop_front();
205 *it = x;
206 }
207 ++idx;
208 }
209 return ys;
210 }
211
212 // API search type: drop_idxs : ([Int], [a]) -> [a]
213 // fwd bind count: 1
214 // Drop the elements of a sequence with an index present in idxs_to_keep.
215 // drop_idxs([2,5], [1,2,3,4,5,6,7]) == [1,2,4,5,7]
216 template <typename ContainerIdxs, typename Container>
drop_idxs(const ContainerIdxs & idxs_to_drop,const Container & xs)217 Container drop_idxs(const ContainerIdxs& idxs_to_drop, const Container& xs)
218 {
219 static_assert(std::is_same<typename ContainerIdxs::value_type, std::size_t>::value,
220 "Indices must be std::size_t");
221 auto idxs_left = convert_container<std::list<std::size_t>>(
222 unique(sort(idxs_to_drop)));
223 Container ys;
224 auto it = internal::get_back_inserter<Container>(ys);
225 std::size_t idx = 0;
226 for (const auto& x : xs)
227 {
228 if (idxs_left.empty() || idxs_left.front() != idx)
229 {
230 *it = x;
231 }
232 else
233 {
234 if (!idxs_left.empty())
235 {
236 idxs_left.pop_front();
237 }
238 }
239 ++idx;
240 }
241 return ys;
242 }
243
244 // API search type: drop_idx : (Int, [a]) -> [a]
245 // fwd bind count: 1
246 // Remove the element at a specific index from a sequence.
247 // drop_idx(2, [1,2,3,4,5,6,7]) == [1,2,4,5,6,7]
248 template <typename Container>
drop_idx(std::size_t idx,const Container & xs)249 Container drop_idx(std::size_t idx, const Container& xs)
250 {
251 return drop_by_idx(is_equal_to(idx), xs);
252 }
253
254 // API search type: justs : [Maybe a] -> [a]
255 // fwd bind count: 0
256 // From a Container filled with Maybe<T> the nothings are dropped
257 // and the values inside the justs are returned in a new container.
258 template <typename ContainerIn,
259 typename ContainerOut =
260 typename internal::same_cont_new_t<ContainerIn,
261 typename ContainerIn::value_type::type>::type>
justs(const ContainerIn & xs)262 ContainerOut justs(const ContainerIn& xs)
263 {
264 typedef typename ContainerIn::value_type::type T;
265 auto justsInMaybes = keep_if(is_just<T>, xs);
266 ContainerOut ys;
267 internal::prepare_container(ys, fplus::size_of_cont(justsInMaybes));
268 auto itOut = internal::get_back_inserter<ContainerOut>(ys);
269 std::transform(std::begin(justsInMaybes), std::end(justsInMaybes),
270 itOut, unsafe_get_just<T>);
271 return ys;
272 }
273
274 // API search type: oks : [Result a b] -> [a]
275 // fwd bind count: 0
276 // From a Container filled with Result<Ok, Error> the errors are dropped
277 // and the values inside the ok are returned in a new container.
278 template <typename ContainerIn,
279 typename ContainerOut =
280 typename internal::same_cont_new_t<ContainerIn,
281 typename ContainerIn::value_type::ok_t>::type>
oks(const ContainerIn & xs)282 ContainerOut oks(const ContainerIn& xs)
283 {
284 typedef typename ContainerIn::value_type::ok_t Ok;
285 typedef typename ContainerIn::value_type::error_t Error;
286 auto oksInResults = keep_if(is_ok<Ok, Error>, xs);
287 ContainerOut ys;
288 internal::prepare_container(ys, fplus::size_of_cont(oksInResults));
289 auto itOut = internal::get_back_inserter<ContainerOut>(ys);
290 std::transform(std::begin(oksInResults), std::end(oksInResults),
291 itOut, unsafe_get_ok<Ok, Error>);
292 return ys;
293 }
294
295 // API search type: errors : [Result a b] -> [b]
296 // fwd bind count: 0
297 // From a Container filled with Result<Ok, Error> the oks are dropped
298 // and the values inside the errors are returned in a new container.
299 template <typename ContainerIn,
300 typename ContainerOut =
301 typename internal::same_cont_new_t<ContainerIn,
302 typename ContainerIn::value_type::error_t>::type>
errors(const ContainerIn & xs)303 ContainerOut errors(const ContainerIn& xs)
304 {
305 typedef typename ContainerIn::value_type::ok_t Ok;
306 typedef typename ContainerIn::value_type::error_t Error;
307 auto errorsInResults = keep_if(is_error<Ok, Error>, xs);
308 ContainerOut ys;
309 internal::prepare_container(ys, fplus::size_of_cont(errorsInResults));
310 auto itOut = internal::get_back_inserter<ContainerOut>(ys);
311 std::transform(std::begin(errorsInResults), std::end(errorsInResults),
312 itOut, unsafe_get_error<Ok, Error>);
313 return ys;
314 }
315
316 // API search type: trim_left : (a, [a]) -> [a]
317 // fwd bind count: 1
318 // Remove elements from the left as long as they equal x.
319 // trim_left('_', "___abc__") == "abc__"
320 // trim_left(0, [0,0,0,5,6,7,8,6,4]) == [5,6,7,8,6,4]
321 template <typename Container,
322 typename T = typename Container::value_type>
323 Container trim_left(const T& x, const Container& xs)
324 {
325 return drop_while(is_equal_to(x), xs);
326 }
327
328 // API search type: trim_token_left : ([a], [a]) -> [a]
329 // fwd bind count: 1
330 // Remove elements from the left as long as they match token.
331 // trim_token_left([0,1,2], [0,1,2,0,1,2,7,5,9]) == [7,5,9]
332 template <typename Container>
trim_token_left(const Container & token,const Container & xs)333 Container trim_token_left(const Container& token, const Container& xs)
334 {
335 auto result = xs;
336 while (is_prefix_of(token, result))
337 {
338 result = get_segment(size_of_cont(token), size_of_cont(result), result);
339 }
340 return result;
341 }
342
343 // API search type: trim_right_by : ((a -> Bool), [a]) -> [a]
344 // fwd bind count: 1
345 // Remove elements from the left as long as p is fulfilled.
346 // trim_right_by(is_even, [0,2,4,5,6,7,8,6,4]) == [0,2,4,5,6,7]
347 template <typename Container, typename UnaryPredicate>
348 Container trim_right_by(UnaryPredicate p, const Container& xs)
349 {
350 internal::check_unary_predicate_for_container<UnaryPredicate, Container>();
351 return reverse(drop_while(p, reverse(xs)));
352 }
353
354 // API search type: trim_right : (a, [a]) -> [a]
355 // fwd bind count: 1
356 // Remove elements from the left as long as they equal x.
357 // trim_right('_', "___abc__") == "___abc"
358 // trim_right(4, [0,2,4,5,6,7,8,4,4]) == [0,2,4,5,6,7,8]
359 template <typename Container,
360 typename T = typename Container::value_type>
361 Container trim_right(const T& x, const Container& xs)
362 {
363 return trim_right_by(is_equal_to(x), xs);
364 }
365
366 // API search type: trim_token_right : ([a], [a]) -> [a]
367 // fwd bind count: 1
368 // Remove elements from the right as long as they match token.
369 // trim_token_right([0,1,2], [7,5,9,0,1,2,0,1,2]) == [7,5,9]
370 template <typename Container>
trim_token_right(const Container & token,const Container & xs)371 Container trim_token_right(const Container& token, const Container& xs)
372 {
373 return reverse(trim_token_left(reverse(token), reverse(xs)));
374 }
375
376 // API search type: trim_by : ((a -> Bool), [a]) -> [a]
377 // fwd bind count: 1
378 // Remove elements from the left and right as long as p is fulfilled.
379 // trim_by(is_even, [0,2,4,5,6,7,8,6,4]) == [5,6,7]
380 template <typename Container, typename UnaryPredicate>
381 Container trim_by(UnaryPredicate p, const Container& xs)
382 {
383 internal::check_unary_predicate_for_container<UnaryPredicate, Container>();
384 return trim_right_by(p, drop_while(p, xs));
385 }
386
387 // API search type: trim : (a, [a]) -> [a]
388 // fwd bind count: 1
389 // Remove elements from the left and right as long as they equal x.
390 // trim('_', "___abc__") == "abc"
391 // trim(0, [0,2,4,5,6,7,8,0,0]) == [2,4,5,6,7,8]
392 template <typename Container,
393 typename T = typename Container::value_type>
394 Container trim(const T& x, const Container& xs)
395 {
396 return trim_right(x, trim_left(x, xs));
397 }
398
399 // API search type: trim_token : ([a], [a]) -> [a]
400 // fwd bind count: 1
401 // Remove elements from the left and right as long as they match token.
402 // trim_token([0,1], [0,1,7,8,9,0,1]) == [7,8,9]
403 template <typename Container>
trim_token(const Container & token,const Container & xs)404 Container trim_token(const Container& token, const Container& xs)
405 {
406 return trim_token_right(token, trim_token_left(token, xs));
407 }
408
409 // API search type: adjacent_keep_snd_if : (((a, a) -> Bool), [a]) -> [a]
410 // fwd bind count: 1
411 // For each pair of adjacent elements in a source sequence,
412 // evaluate the specified binary predicate.
413 // If the predicate evaluates to false,
414 // the second element of the pair is removed from the result sequence;
415 // otherwise, it is included.
416 // The first element in the source sequence is always included.
417 // Also known as adjacent_filter.
418 template <typename BinaryPredicate, typename Container>
adjacent_keep_snd_if(BinaryPredicate p,const Container & xs)419 Container adjacent_keep_snd_if(BinaryPredicate p, const Container& xs)
420 {
421 if (is_empty(xs))
422 {
423 return {};
424 }
425 internal::check_binary_predicate_for_container<BinaryPredicate, Container>();
426 Container result;
427 auto it = internal::get_back_inserter<Container>(result);
428 auto it_in = std::begin(xs);
429 *it = *it_in;
430 while (internal::add_to_iterator(it_in) != std::end(xs))
431 {
432 if (p(*it_in, *internal::add_to_iterator(it_in)))
433 {
434 *it = *internal::add_to_iterator(it_in);
435 }
436 internal::advance_iterator(it_in, 1);
437 }
438 return result;
439 }
440
441 // API search type: adjacent_drop_fst_if : (((a, a) -> Bool), [a]) -> [a]
442 // fwd bind count: 1
443 // For each pair of adjacent elements in a source sequence,
444 // evaluate the specified binary predicate.
445 // If the predicate evaluates to true,
446 // the first element of the pair is removed from the result sequence;
447 // otherwise, it is included.
448 // The last element in the source sequence is always included.
449 // Also known as adjacent_remove_if.
450 template <typename BinaryPredicate, typename Container>
adjacent_drop_fst_if(BinaryPredicate p,const Container & xs)451 Container adjacent_drop_fst_if(BinaryPredicate p, const Container& xs)
452 {
453 if (is_empty(xs))
454 {
455 return {};
456 }
457 internal::check_binary_predicate_for_container<BinaryPredicate, Container>();
458 Container result;
459 auto it = internal::get_back_inserter<Container>(result);
460 auto it_in = std::begin(xs);
461 while (internal::add_to_iterator(it_in) != std::end(xs))
462 {
463 if (!internal::invoke(p, *it_in, *internal::add_to_iterator(it_in)))
464 {
465 *it = *it_in;
466 }
467 internal::advance_iterator(it_in, 1);
468 }
469 *it = *it_in;
470 return result;
471 }
472
473 // API search type: adjacent_drop_snd_if : (((a, a) -> Bool), [a]) -> [a]
474 // fwd bind count: 1
475 // For each pair of adjacent elements in a source sequence,
476 // evaluate the specified binary predicate.
477 // If the predicate evaluates to true,
478 // the second element of the pair is removed from the result sequence;
479 // otherwise, it is included.
480 // The first element in the source sequence is always included.
481 template <typename BinaryPredicate, typename Container>
adjacent_drop_snd_if(BinaryPredicate p,const Container & xs)482 Container adjacent_drop_snd_if(BinaryPredicate p, const Container& xs)
483 {
484 typedef typename Container::value_type T;
485 const auto not_p = [&p](const T& x, const T& y) -> bool
486 {
487 return !internal::invoke(p, x, y);
488 };
489 return adjacent_keep_snd_if(not_p, xs);
490 }
491
492 // API search type: adjacent_keep_fst_if : (((a, a) -> Bool), [a]) -> [a]
493 // fwd bind count: 1
494 // For each pair of adjacent elements in a source sequence,
495 // evaluate the specified binary predicate.
496 // If the predicate evaluates to false,
497 // the first element of the pair is removed from the result sequence;
498 // otherwise, it is included.
499 // The last element in the source sequence is always included.
500 template <typename BinaryPredicate, typename Container>
adjacent_keep_fst_if(BinaryPredicate p,const Container & xs)501 Container adjacent_keep_fst_if(BinaryPredicate p, const Container& xs)
502 {
503 typedef typename Container::value_type T;
504 const auto not_p = [&p](const T& x, const T& y) -> bool
505 {
506 return !internal::invoke(p, x, y);
507 };
508 return adjacent_drop_fst_if(not_p, xs);
509 }
510
511 } // namespace fplus
512