YSTest: algorithm.hpp 源文件

YSTest PreAlpha_b900_20201012 The YSLib Test Project

algorithm.hpp
浏览该文件的文档.
1 /*
2 © 2010-2020 FrankHB.
3
4 This file is part of the YSLib project, and may only be used,
5 modified, and distributed under the terms of the YSLib project
6 license, LICENSE.TXT. By continuing to use, modify, or distribute
7 this file you indicate that you have read the license and
8 understand and accept it fully.
9 */
10
28 #ifndef YB_INC_ystdex_algorithm_hpp_
29 #define YB_INC_ystdex_algorithm_hpp_ 1
30
31 #include "iterator_trait.hpp" // for have_same_iterator_category;
32 #include <numeric> // for std::accumulate;
33 #include <algorithm> // for <algorithm>;
34 #include "functor.hpp" // for is_equal, less, std::bind, std::placeholders::_1;
35 #include "deref_op.hpp" // for YB_VerifyIterator, yconstraint;
36 #include <cstring> // for std::memcpy, std::memmove;
37
48 #ifndef __cpp_lib_clamp
49 # if YB_IMPL_MSCPP > 1900 || __cpp_lib_clamp >= 201603L
50 # define __cpp_lib_clamp 201603L
51 # endif
52 #endif
53
54
56 #ifndef __cpp_lib_robust_nonmodifying_seq_ops
57 # if YB_IMPL_MSCPP >= 1900 || __cplusplus >= 201304L
58 # define __cpp_lib_robust_nonmodifying_seq_ops 201304L
59 # endif
60 #endif
61
62
63
64 namespace ystdex
65 {
66
86 template<typename _tIn, typename _fPred>
88 bool
89 fast_all_of(_tIn first, _tIn last, _fPred pred)
90 {
91 while(first != last && bool(pred(*first)))
92 ++first;
93 return first == last;
94 }
95
97 template<typename _tIn, typename _fPred>
98 bool
99 fast_any_of(_tIn first, _tIn last, _fPred pred)
100 {
101 while(first != last && !bool(pred(*first)))
102 ++first;
103 return first != last;
104 }
105
107 template<typename _tIn, typename _fPred>
108 bool
109 fast_none_of(_tIn first, _tIn last, _fPred pred)
110 {
111 return !ystdex::fast_any_of(first, last, pred);
112 }
114
115
122 template<typename _tIn, typename _fPred>
124 bool
125 strict_all_of(_tIn first, _tIn last, _fPred pred)
126 {
127 return std::accumulate(first, last, true,
128 [pred](bool b, decltype(*first) val){
129 return b && bool(pred(yforward(val)));
130 });
131 }
132
134 template<typename _tIn, typename _fPred>
135 bool
136 strict_any_of(_tIn first, _tIn last, _fPred pred)
137 {
138 return std::accumulate(first, last, false,
139 [pred](bool b, decltype(*first) val){
140 return b || bool(pred(yforward(val)));
141 });
142 }
143
145 template<typename _tIn, typename _fPred>
146 bool
147 strict_none_of(_tIn first, _tIn last, _fPred pred)
148 {
149 return !ystdex::strict_any_of(first, last, pred);
150 }
152
153
171 template<typename _tIn, typename _func, typename _type>
172 _func
173 for_each_equal(_tIn first, _tIn last, const _type& value, _func f)
174 {
175 for(; first != last; ++first)
176 {
177 first = std::find(first, last, value);
178 f(*first);
179 }
180 return f;
181 }
182
183 template<typename _tIn, typename _func, typename _fPred>
184 _func
185 for_each_if(_tIn first, _tIn last, _fPred pred, _func f)
186 {
187 for(; first != last; ++first)
188 {
189 first = std::find_if(first, last, pred);
190 f(*first);
191 }
192 return f;
193 }
195
196
198 inline namespace cpp2014
199 {
200
201 using std::equal;
202 #if !(__cpp_lib_robust_nonmodifying_seq_ops >= 201304L)
203 template<typename _tIn1, typename _tIn2, typename _fBiPred>
204 inline bool
205 equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2,
206 _fBiPred binary_pred)
207 {
208 if(have_same_iterator_category<std::random_access_iterator_tag, _tIn1,
209 _tIn2>())
210 {
211 if(std::distance(first1, last1) != std::distance(first2, last2))
212 return {};
213 return std::equal(first1, last1, first2, binary_pred);
214 }
215 for(; first1 != last1 && first2 != last2; ++first1, ++first2)
216 if(!bool(binary_pred(*first1, *first2)))
217 return {};
218 return first1 == last1 && first2 == last2;
219 }
220 template<typename _tIn1, typename _tIn2>
221 inline bool
222 equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2)
223 {
224 return ystdex::equal(first1, last1, first2, last2, is_equal());
225 }
226 #endif
227
228 } // inline namespace cpp2014;
229
230
236 /*
237 \brief 取有序范围内的迭代器下界。
238 \note 同 std::lower_bound 但使用起始迭代器和距离指定范围。
239 */
240 template<typename _tFwd, typename _type, typename _fComp = less<_type>>
241 YB_ATTR_nodiscard YB_PURE _tFwd
242 lower_bound_n(_tFwd first, typename std::iterator_traits<
243 _tFwd>::difference_type n, const _type& value, _fComp comp = less<_type>())
244 {
245 while(n > 0)
246 {
247 const auto half(n >> 1);
248 auto middle(first);
249
250 YB_VerifyIterator(middle);
251 std::advance(middle, half);
252 YB_VerifyIterator(middle);
253 if(comp(*middle, value))
254 {
255 first = middle;
256 ++first;
257 n = n - half - 1;
258 }
259 else
260 n = half;
261 }
262 return first;
263 }
264
265
270 template<typename _tFwd, typename _type, typename _fComp = less<_type>>
271 YB_ATTR_nodiscard YB_PURE _tFwd
272 upper_bound_n(_tFwd first, typename std::iterator_traits<
273 _tFwd>::difference_type n, const _type& value, _fComp comp = less<_type>())
274 {
275 return ystdex::lower_bound_n(first, n, value, [&](const _type& x,
276 const typename std::iterator_traits<_tFwd>::value_type& y){
277 return !comp(y, x);
278 });
279 }
281
282
284
285
289 template<typename _fPred, typename _fInsert, typename _tIn>
290 void
291 split(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
292 {
293 while(b != e)
294 {
295 _tIn i(std::find_if_not(b, e, is_delim));
296
297 b = std::find_if(i, e, is_delim);
298 if(i != b)
299 insert(i, b);
300 else
301 break;
302 }
303 }
304
309 template<typename _fPred, typename _fInsert, typename _func, typename _tIn>
310 void
311 split_if(_tIn b, _tIn e, _fPred is_delim, _fInsert insert, _func pred)
312 {
313 while(b != e)
314 {
315 _tIn i(b);
316
317 while(i != e && is_delim(*i) && pred(i))
318 ++i;
319 for(b = i; b != e; ++b)
320 {
321 b = std::find_if(b, e, is_delim);
322 if(b == e || pred(b))
323 break;
324 }
325 if(i != b)
326 insert(i, b);
327 else
328 break;
329 }
330 }
331
337 template<typename _fPred, typename _fInsert, typename _tIn>
338 _tIn
339 split_l(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
340 {
341 _tIn i(b);
342
343 while(b != e)
344 {
345 if(is_delim(*b) && i != b)
346 {
347 insert(i, b);
348 i = b;
349 }
350 ++b;
351 }
352 if(i != b)
353 insert(i, b);
354 return i;
355 }
357
358
359
382 template<typename _tIn, typename _tOut, typename _fPred, typename _fOp>
383 _tOut
384 transform_when(_tIn first, _tOut result, _fPred pred, _fOp op)
385 {
386 yunseq((YB_VerifyIterator(first), 0), (YB_VerifyIterator(result), 0));
387
388 for(; pred(*first); yunseq((++first, 0), (++result, 0)))
389 *result = op(*first);
390 return result;
391 }
392
394 template<typename _tIn, typename _tOut, typename _fPred>
395 _tOut
396 copy_when(_tIn first, _tOut result, _fPred pred)
397 {
398 return ystdex::transform_when(first, result, pred,
399 [](decltype(*first)& v) ynothrow{
400 return static_cast<decltype(*first)&>(v);
401 });
402 }
404
414 template<typename _fOp, typename _tOut, typename... _tIns>
415 void
416 transform_n(_fOp op, _tOut result, size_t n, _tIns... iters)
417 {
418 while(n-- != 0)
419 {
420 yunseq((YB_VerifyIterator(result), 0),
421 (YB_VerifyIterator(iters), void(iters), 0)...);
422 *result = op((*iters)...);
423 yunseq(++result, ++iters...);
424 }
425 }
426
442 template<typename _type>
443 inline _type*
444 trivially_fill_n(_type* first, size_t n = 1, byte value = {}) ynothrowv
445 {
446 static_assert(is_trivial<_type>(), "Non-trivial type found.");
447
448 YB_VerifyIterator(first);
449 std::memset(first, int(value), sizeof(_type) * n);
450 return first + n;
451 }
452
453 template<typename _type>
454 inline void
455 trivially_fill(_type* first, _type* last, byte value = {}) ynothrowv
456 {
457 ystdex::trivially_fill_n(first, last - first, value);
458 }
460
467 template<typename _type>
468 inline _type*
469 trivially_copy_n(const _type* first, size_t n, _type* result) ynothrowv
470 {
471 static_assert(is_trivial<_type>(), "Non-trivial type found.");
472 static_assert(is_copy_assignable<_type>(),
473 "Type shall meet CopyAssignable.");
474
475 yunseq((YB_VerifyIterator(result), 0),
476 (YB_VerifyIterator(first), 0));
477 std::memcpy(result, first, sizeof(_type) * n);
478 return result + n;
479 }
480
481 template<typename _type>
482 inline _type*
483 trivially_copy(const _type* first, const _type* last, _type* result) ynothrowv
484 {
485 return ystdex::trivially_copy_n(first, last - first, result);
486 }
488
495 template<class _type>
496 inline _type*
497 trivially_move_n(const _type* first, size_t n, _type* result)
498 {
499 static_assert(is_trivial<_type>(), "Non-trivial type found.");
500 static_assert(is_copy_assignable<_type>(),
501 "Type shall meet CopyAssignable.");
502
503 yunseq((YB_VerifyIterator(result), 0),
504 (YB_VerifyIterator(first), 0));
505 std::memmove(result, first, sizeof(_type) * n);
506 return result + n;
507 }
508
509 template<class _type>
510 inline _type*
511 trivially_move(const _type* first, const _type* last, _type* result)
512 {
513 return ystdex::trivially_move_n(first, last - first, result);
514 }
516
517
518
532 template<typename _tFwd>
533 _tFwd
534 stable_unique(_tFwd first, _tFwd last)
535 {
536 _tFwd result(first);
537
538 for(_tFwd i(first); i != last; ++i)
539 if(std::find(first, result, *i) == result)
540 {
541 std::iter_swap(i, result);
542 ++result;
543 }
544 return result;
545 }
547 template<typename _tFwd, typename _fPred>
548 _tFwd
549 stable_unique(_tFwd first, _tFwd last, _fPred pred)
550 {
551 _tFwd result(first);
552
553 for(_tFwd i(first); i != last; ++i)
554 if(std::find_if(first, result,
555 std::bind(pred, std::ref(*i), std::placeholders::_1)) == result)
556 {
557 std::iter_swap(i, result);
558 ++result;
559 }
560 return result;
561 }
563
564
565
581 template<typename _tRandom>
582 inline _tRandom
583 sort_unique(_tRandom first, _tRandom last)
584 {
585 std::sort(first, last);
586 return std::unique(first, last);
587 }
588
589
594 inline namespace cpp2014
595 {
596
597 // XXX: No feature testing macro available yet.
598 #if __cplupslus >= 201402L
599 using std::min;
600 using std::max;
601 #else
602
612 template<typename _type, typename _fComp = less<_type>>
613 YB_ATTR_nodiscard YB_PURE yconstfn const _type&
614 min(const _type& a, const _type& b, _fComp comp = less<_type>())
615 {
616 return comp(b, a) ? b : a;
617 }
618 template<typename _type, typename _fComp = less<_type>>
619 YB_ATTR_nodiscard YB_PURE yconstfn const _type&
620 min(std::initializer_list<_type> t, _fComp comp = less<_type>(),
621 yimpl(size_t n = 0))
622 {
623 return n + 1 < t.size() ? ystdex::min(*(t.begin() + n),
624 ystdex::min(t, comp, n + 1)) : *(t.begin() + n);
625 }
627
633 template<typename _type, typename _fComp = less<_type>>
634 YB_ATTR_nodiscard YB_PURE yconstfn const _type&
635 max(const _type& a, const _type& b, _fComp comp = less<_type>())
636 {
637 return comp(a, b) ? b : a;
638 }
639 template<typename _type, typename _fComp = less<_type>>
640 YB_ATTR_nodiscard YB_PURE yconstfn const _type&
641 max(std::initializer_list<_type> t, _fComp comp = less<_type>(),
642 yimpl(size_t n = 0))
643 {
644 return n + 1 < t.size() ? ystdex::max(*(t.begin() + n),
645 ystdex::max(t, comp, n + 1)) : *(t.begin() + n);
646 }
648
649 #endif
650
651 } // inline namespace cpp2014;
652
664 inline namespace cpp2017
665 {
666
667 #if __cpp_lib_clamp >= 201603L
668 using std::clamp;
669 #else
670
672 template<typename _type, typename _fComp>
673 YB_ATTR_nodiscard YB_PURE yconstfn const _type&
674 clamp(const _type& v, const _type& lo, const _type& hi, _fComp comp)
675 {
676 return yconstraint(!comp(hi, lo)), comp(v, lo) ? lo : comp(hi, v) ? hi : v;
677 }
678 template<typename _type>
679 YB_ATTR_nodiscard YB_PURE yconstfn const _type&
680 clamp(const _type& v, const _type& lo, const _type& hi)
681 {
682 return ystdex::clamp(v, lo, hi, less<_type>());
683 }
685 #endif
686
687 } // inline namespace cpp2017;
689
691 template<typename _tIn, typename _tOut, typename _fComp = less<>>
692 yconstfn _tOut
693 clamp_range(_tIn first, _tIn last, _tOut result, const typename
694 std::iterator_traits<_tIn>::value_type& lo, const typename
695 std::iterator_traits<_tIn>::value_type& hi, _fComp comp = _fComp())
696 {
697 using arg_type = decltype(lo);
698
699 return std::transform(first, last, result, [&](arg_type val) -> arg_type{
700 return ystdex::clamp(val, lo, hi, comp);
701 });
702 }
704
705
706
707 } // namespace ystdex;
708
709 #endif
710
ystdex_swap::iter_swap
void iter_swap(_tFwd1 a, _tFwd1 b)
符合 ISO C++20 要求的 std::iter_swap 替代实现。
Definition: swap.hpp:138
YB_ATTR_nodiscard
#define YB_ATTR_nodiscard
标记返回值不被忽略的属性。
Definition: ydef.h:715
iterator_trait.hpp
迭代器特征。
CHRLib::e
const char const char * e
Definition: CharacterProcessing.h:112
x
const EncapsulationBase & x
Definition: NPLA1Forms.cpp:1536
ystdex::upper_bound_n
_tFwd upper_bound_n(_tFwd first, typename std::iterator_traits< _tFwd >::difference_type n, const _type &value, _fComp comp=less< _type >())
取有序范围内的迭代器上界。
Definition: algorithm.hpp:272
YB_PURE
#define YB_PURE
指示函数或函数模板实例为纯函数。
Definition: ydef.h:919
ystdex::split
void split(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
以指定分隔符分割序列。
Definition: algorithm.hpp:291
ystdex::cpp2014::min
const _type & min(const _type &a, const _type &b, _fComp comp=less< _type >())
取较小的元素。
Definition: algorithm.hpp:614
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2)
Definition: algorithm.hpp:222
ystdex::stable_unique
_tFwd stable_unique(_tFwd first, _tFwd last)
去除迭代器指定的范围中的重复元素，且不改变元素之间的相对顺序。
Definition: algorithm.hpp:534
ystdex::any_ops::advance
@ advance
Definition: any_iterator.hpp:81
ystdex::trivially_fill_n
_type * trivially_fill_n(_type *first, size_t n=1, byte value={})
填充字节序列。
Definition: algorithm.hpp:444
ystdex::trivially_fill
void trivially_fill(_type *first, _type *last, byte value={})
Definition: algorithm.hpp:455
ystdex::cpp2014::less
小于关系仿函数。
Definition: functor.hpp:398
ystdex::cpp2014::max
const _type & max(const _type &a, const _type &b, _fComp comp=less< _type >())
取较大的元素。
Definition: algorithm.hpp:635
ystdex::any_ops::distance
@ distance
Definition: any_iterator.hpp:82
ystdex::copy_when
_tOut copy_when(_tIn first, _tOut result, _fPred pred)
复制满足谓词的序列的连续元素。
Definition: algorithm.hpp:396
ystdex::lower_bound_n
_tFwd lower_bound_n(_tFwd first, typename std::iterator_traits< _tFwd >::difference_type n, const _type &value, _fComp comp=less< _type >())
Definition: algorithm.hpp:242
ystdex::is_equal
相等关系仿函数。
Definition: functor.hpp:196
ystdex::for_each_equal
_func for_each_equal(_tIn first, _tIn last, const _type &value, _func f)
Definition: algorithm.hpp:173
ystdex::for_each_if
_func for_each_if(_tIn first, _tIn last, _fPred pred, _func f)
Definition: algorithm.hpp:185
CHRLib::f
f(d, s)
ystdex::trivially_copy
_type * trivially_copy(const _type *first, const _type *last, _type *result)
Definition: algorithm.hpp:483
ystdex::strict_none_of
bool strict_none_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:147
ystdex::fast_any_of
bool fast_any_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:99
ystdex::transform_n
void transform_n(_fOp op, _tOut result, size_t n, _tIns... iters)
指定数量的序列变换。
Definition: algorithm.hpp:416
ystdex::cpp2017::clamp
const _type & clamp(const _type &v, const _type &lo, const _type &hi)
Definition: algorithm.hpp:680
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 转发对应参数。
Definition: ydef.h:1508
ystdex::trivially_move
_type * trivially_move(const _type *first, const _type *last, _type *result)
Definition: algorithm.hpp:511
YB_VerifyIterator
#define YB_VerifyIterator(_expr)
验证表达式求值的迭代器的有效性。
Definition: deref_op.hpp:67
ystdex::transform_when
_tOut transform_when(_tIn first, _tOut result, _fPred pred, _fOp op)
变换满足谓词的序列的连续元素。
Definition: algorithm.hpp:384
YSLib::i
return i
Definition: YCoreUtilities.h:177
yunseq
#define yunseq
无序列依赖表达式组求值。
Definition: ydef.h:1535
yconstraint
#define yconstraint(_expr)
约束：接口语义。
Definition: cassert.h:125
YSLib::UI::y
SPos SPos y
Definition: YWidget.cpp:44
ystdex::trivially_copy_n
_type * trivially_copy_n(const _type *first, size_t n, _type *result)
复制不覆盖的序列。
Definition: algorithm.hpp:469
ystdex::fast_all_of
bool fast_all_of(_tIn first, _tIn last, _fPred pred)
快速序列判断操作。
Definition: algorithm.hpp:89
ystdex::cpp2017::clamp
const _type & clamp(const _type &v, const _type &lo, const _type &hi, _fComp comp)
Definition: algorithm.hpp:674
ystdex::fast_none_of
bool fast_none_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:109
v
byte v
Definition: CharRenderer.cpp:76
ynothrowv
#define ynothrowv
YSLib 无异常抛出保证验证：有条件地使用无异常抛出规范。
Definition: ydef.h:1219
ystdex
<memory> 特性测试宏。
Definition: ydef.h:1262
ystdex::sort_unique
_tRandom sort_unique(_tRandom first, _tRandom last)
排序指定序列范围，保留不重复元素的区间。
Definition: algorithm.hpp:583
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2, _fBiPred binary_pred)
Definition: algorithm.hpp:205
ystdex::trivially_move_n
_type * trivially_move_n(const _type *first, size_t n, _type *result)
复制可能覆盖的序列。
Definition: algorithm.hpp:497
ystdex::strict_all_of
bool strict_all_of(_tIn first, _tIn last, _fPred pred)
严格序列判断操作。
Definition: algorithm.hpp:125
ystdex::have_same_iterator_category
判断若干个迭代器是否具有相同的指定的类别。
Definition: iterator_trait.hpp:68
ystdex::split_if
void split_if(_tIn b, _tIn e, _fPred is_delim, _fInsert insert, _func pred)
以满足迭代器谓词的指定分隔符分割序列。
Definition: algorithm.hpp:311
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:413
platform::bool
YB_ATTR_nodiscard std::FILE *fp bool
Definition: FileIO.h:1271
ystdex::cpp2014::max
const _type & max(std::initializer_list< _type > t, _fComp comp=less< _type >(), size_t n=0)
Definition: algorithm.hpp:641
deref_op.hpp
解引用操作。
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:1199
functor.hpp
通用仿函数。
ystdex::cpp2014::min
const _type & min(std::initializer_list< _type > t, _fComp comp=less< _type >(), size_t n=0)
Definition: algorithm.hpp:620
ystdex::strict_any_of
bool strict_any_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:136
ystdex::ref
void ref(const _type &&)=delete
ystdex::clamp_range
_tOut clamp_range(_tIn first, _tIn last, _tOut result, const typename std::iterator_traits< _tIn >::value_type &lo, const typename std::iterator_traits< _tIn >::value_type &hi, _fComp comp=_fComp())
Definition: algorithm.hpp:693
yconstfn
#define yconstfn
指定编译时常量函数。
Definition: ydef.h:1073
YSLib::a
YB_PURE const _type * a
Definition: YCoreUtilities.h:168
ystdex::split_l
_tIn split_l(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
以指定分隔符分割保留起始分隔符的序列。
Definition: algorithm.hpp:339