YSTest: algorithm.hpp 源文件

YSTest PreAlpha_b800_20170810 The YSLib Test Project

- 首页
- 相关页面
- 模块
- 命名空间
- 类
- 文件

- 文件列表
- 文件成员

algorithm.hpp
浏览该文件的文档.
1 /*
2 © 2010-2016 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 "functor.hpp" // for <algorithm>,
34 // __cpp_lib_robust_nonmodifying_seq_ops, is_equal, std::bind,
35 // std::placeholders::_1, less;
36 #include "cassert.h" // for yconstraint;
37 #include "deref_op.hpp" // for is_undereferenceable;
38 #include <cstring> // for std::memcpy, std::memmove;
39
40 namespace ystdex
41 {
42
62 template<typename _tIn, typename _fPred>
64 bool
65 fast_all_of(_tIn first, _tIn last, _fPred pred)
66 {
67 while(first != last && bool(pred(*first)))
68 ++first;
69 return first == last;
70 }
71
73 template<typename _tIn, typename _fPred>
74 bool
75 fast_any_of(_tIn first, _tIn last, _fPred pred)
76 {
77 while(first != last && !bool(pred(*first)))
78 ++first;
79 return first != last;
80 }
81
83 template<typename _tIn, typename _fPred>
84 bool
85 fast_none_of(_tIn first, _tIn last, _fPred pred)
86 {
87 return !ystdex::fast_any_of(first, last, pred);
88 }
90
91
98 template<typename _tIn, typename _fPred>
100 bool
101 strict_all_of(_tIn first, _tIn last, _fPred pred)
102 {
103 return std::accumulate(first, last, true,
104 [pred](bool b, decltype(*first) val){
105 return b && bool(pred(yforward(val)));
106 });
107 }
108
110 template<typename _tIn, typename _fPred>
111 bool
112 strict_any_of(_tIn first, _tIn last, _fPred pred)
113 {
114 return std::accumulate(first, last, false,
115 [pred](bool b, decltype(*first) val){
116 return b || bool(pred(yforward(val)));
117 });
118 }
119
121 template<typename _tIn, typename _fPred>
122 bool
123 strict_none_of(_tIn first, _tIn last, _fPred pred)
124 {
125 return !ystdex::strict_any_of(first, last, pred);
126 }
128
129
147 template<typename _tIn, typename _func, typename _type>
148 _func
149 for_each_equal(_tIn first, _tIn last, const _type& value, _func f)
150 {
151 for(; first != last; ++first)
152 {
153 first = std::find(first, last, value);
154 f(*first);
155 }
156 return f;
157 }
158
159 template<typename _tIn, typename _func, typename _fPred>
160 _func
161 for_each_if(_tIn first, _tIn last, _fPred pred, _func f)
162 {
163 for(; first != last; ++first)
164 {
165 first = std::find_if(++first, last, pred);
166 f(*first);
167 }
168 return f;
169 }
171
172
174 inline namespace cpp2014
175 {
176
177 using std::equal;
178 #if !(__cpp_lib_robust_nonmodifying_seq_ops >= 201304 || __cplusplus > 201103L)
179 template<typename _tIn1, typename _tIn2, typename _fBiPred>
180 inline bool
181 equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2,
182 _fBiPred binary_pred)
183 {
184 if(have_same_iterator_category<std::random_access_iterator_tag, _tIn1,
185 _tIn2>())
186 {
187 if(std::distance(first1, last1) != std::distance(first2, last2))
188 return {};
189 return std::equal(first1, last1, first2, binary_pred);
190 }
191 for(; first1 != last1 && first2 != last2; ++first1, ++first2)
192 if(!bool(binary_pred(*first1, *first2)))
193 return {};
194 return first1 == last1 && first2 == last2;
195 }
196 template<typename _tIn1, typename _tIn2>
197 inline bool
198 equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2)
199 {
200 return ystdex::equal(first1, last1, first2, last2, is_equal());
201 }
202 #endif
203
204 } // inline namespace cpp2014;
205
206
208
209
213 template<typename _fPred, typename _fInsert, typename _tIn>
214 void
215 split(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
216 {
217 while(b != e)
218 {
219 _tIn i(std::find_if_not(b, e, is_delim));
220
221 b = std::find_if(i, e, is_delim);
222 if(i != b)
223 insert(i, b);
224 else
225 break;
226 }
227 }
228
233 template<typename _fPred, typename _fInsert, typename _func, typename _tIn>
234 void
235 split_if(_tIn b, _tIn e, _fPred is_delim, _fInsert insert, _func pred)
236 {
237 while(b != e)
238 {
239 _tIn i(b);
240
241 while(i != e && is_delim(*i) && pred(i))
242 ++i;
243 for(b = i; b != e; ++b)
244 {
245 b = std::find_if(b, e, is_delim);
246 if(b == e || pred(b))
247 break;
248 }
249 if(i != b)
250 insert(i, b);
251 else
252 break;
253 }
254 }
255
261 template<typename _fPred, typename _fInsert, typename _tIn>
262 _tIn
263 split_l(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
264 {
265 _tIn i(b);
266
267 while(b != e)
268 {
269 if(is_delim(*b) && i != b)
270 {
271 insert(i, b);
272 i = b;
273 }
274 ++b;
275 }
276 if(i != b)
277 insert(i, b);
278 return i;
279 }
281
282
283
306 template<typename _tIn, typename _tOut, typename _fPred, typename _fOp>
307 _tOut
308 transform_when(_tIn first, _tOut result, _fPred pred, _fOp op)
309 {
310 yunseq((yconstraint(!is_undereferenceable(first)), 0),
311 (yconstraint(!is_undereferenceable(result)), 0));
312
313 for(; pred(*first); yunseq((++first, 0), (++result, 0)))
314 *result = op(*first);
315 return result;
316 }
317
319 template<typename _tIn, typename _tOut, typename _fPred>
320 _tOut
321 copy_when(_tIn first, _tOut result, _fPred pred)
322 {
323 return ystdex::transform_when(first, result, pred,
324 [](decltype(*first)& v) ynothrow{
325 return static_cast<decltype(*first)&>(v);
326 });
327 }
329
339 template<typename _fOp, typename _tOut, typename... _tIns>
340 void
341 transform_n(_fOp op, _tOut result, size_t n, _tIns... iters)
342 {
343 while(n-- != 0)
344 {
345 yunseq((yconstraint(!is_undereferenceable(result)), 0),
346 (yconstraint(!is_undereferenceable(iters)), void(iters), 0)...);
347 *result = op((*iters)...);
348 yunseq(++result, ++iters...);
349 }
350 }
351
367 template<typename _type>
368 inline _type*
369 trivially_fill_n(_type* first, size_t n = 1, byte value = {}) ynothrowv
370 {
371 static_assert(is_trivial<_type>(), "Non-trivial type found.");
372
373 yconstraint(!is_undereferenceable(first));
374 std::memset(first, value, sizeof(_type) * n);
375 return first + n;
376 }
377
378 template<typename _type>
379 inline void
380 trivially_fill(_type* first, _type* last, byte value = {}) ynothrowv
381 {
382 ystdex::trivially_fill_n(first, last - first, value);
383 }
385
392 template<typename _type>
393 inline _type*
394 trivially_copy_n(const _type* first, size_t n, _type* result) ynothrowv
395 {
396 static_assert(is_trivial<_type>(), "Non-trivial type found.");
397 static_assert(is_copy_assignable<_type>(),
398 "Type shall meet CopyAssignable.");
399
400 yunseq((yconstraint(!is_undereferenceable(result)), 0),
401 (yconstraint(!is_undereferenceable(first)), 0));
402 std::memcpy(result, first, sizeof(_type) * n);
403 return result + n;
404 }
405
406 template<typename _type>
407 inline _type*
408 trivially_copy(const _type* first, const _type* last, _type* result) ynothrowv
409 {
410 return ystdex::trivially_copy_n(first, last - first, result);
411 }
413
420 template<class _type>
421 inline _type*
422 trivially_move_n(const _type* first, size_t n, _type* result)
423 {
424 static_assert(is_trivial<_type>(), "Non-trivial type found.");
425 static_assert(is_copy_assignable<_type>(),
426 "Type shall meet CopyAssignable.");
427
428 yunseq((yconstraint(!is_undereferenceable(result)), 0),
429 (yconstraint(!is_undereferenceable(first)), 0));
430 std::memmove(result, first, sizeof(_type) * n);
431 return result + n;
432 }
433
434 template<class _type>
435 inline _type*
436 trivially_move(const _type* first, const _type* last, _type* result)
437 {
438 return ystdex::trivially_move_n(first, last - first, result);
439 }
441
442
443
457 template<typename _tFwd>
458 _tFwd
459 stable_unique(_tFwd first, _tFwd last)
460 {
461 _tFwd result(first);
462
463 for(_tFwd i(first); i != last; ++i)
464 if(std::find(first, result, *i) == result)
465 {
466 using std::swap;
467
468 swap(*i, *result);
469 ++result;
470 }
471 return result;
472 }
474 template<typename _tFwd, typename _fPred>
475 _tFwd
476 stable_unique(_tFwd first, _tFwd last, _fPred pred)
477 {
478 _tFwd result(first);
479
480 for(_tFwd i(first); i != last; ++i)
481 if(std::find_if(first, result,
482 std::bind(pred, std::ref(*i), std::placeholders::_1)) == result)
483 {
484 using std::swap;
485
486 swap(*i, *result);
487 ++result;
488 }
489 return result;
490 }
492
493
494
510 template<typename _tRandom>
511 inline _tRandom
512 sort_unique(_tRandom first, _tRandom last)
513 {
514 std::sort(first, last);
515 return std::unique(first, last);
516 }
517
518
525 template<typename _type, typename _fComp = less<_type>>
526 yconstfn const _type&
527 min(const _type& a, const _type& b, _fComp comp = less<_type>())
528 {
529 return comp(b, a) ? b : a;
530 }
531 template<typename _type, typename _fComp = less<_type>>
532 yconstfn const _type&
533 min(std::initializer_list<_type> t, _fComp comp = less<_type>(),
534 yimpl(size_t n = 0))
535 {
536 return n + 1 < t.size() ? ystdex::min(*(t.begin() + n),
537 ystdex::min(t, comp, n + 1)) : *(t.begin() + n);
538 }
540
547 template<typename _type, typename _fComp = less<_type>>
548 yconstfn const _type&
549 max(const _type& a, const _type& b, _fComp comp = less<_type>())
550 {
551 return comp(a, b) ? b : a;
552 }
553 template<typename _type, typename _fComp = less<_type>>
554 yconstfn const _type&
555 max(std::initializer_list<_type> t, _fComp comp = less<_type>(),
556 yimpl(size_t n = 0))
557 {
558 return n + 1 < t.size() ? ystdex::max(*(t.begin() + n),
559 ystdex::max(t, comp, n + 1)) : *(t.begin() + n);
560 }
562
569 template<typename _type, typename _fComp = less<>>
570 yconstfn const _type&
571 clamp(const _type& v, const _type& lo, const _type& hi, _fComp comp = _fComp())
572 {
573 return yconstraint(!comp(hi, lo)), comp(v, lo) ? lo : comp(hi, v) ? hi : v;
574 }
575
576 template<typename _tIn, typename _tOut, typename _fComp = less<>>
577 yconstfn _tOut
578 clamp_range(_tIn first, _tIn last, _tOut result, const typename
579 std::iterator_traits<_tIn>::value_type& lo, const typename
580 std::iterator_traits<_tIn>::value_type& hi, _fComp comp = _fComp())
581 {
582 using arg_type = decltype(lo);
583
584 return std::transform(first, last, result, [&](arg_type val) -> arg_type{
585 return ystdex::clamp(val, lo, hi, comp);
586 });
587 }
589
590
591
592 } // namespace ystdex;
593
594 #endif
595
ystdex::trivially_move_n
_type * trivially_move_n(const _type *first, size_t n, _type *result)
复制可能覆盖的序列。
Definition: algorithm.hpp:422
ystdex::fast_none_of
bool fast_none_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:85
ystdex::transform_when
_tOut transform_when(_tIn first, _tOut result, _fPred pred, _fOp op)
变换满足谓词的序列的连续元素。
Definition: algorithm.hpp:308
ystdex::fast_all_of
bool fast_all_of(_tIn first, _tIn last, _fPred pred)
快速序列判断操作。
Definition: algorithm.hpp:65
ystdex::trivially_move
_type * trivially_move(const _type *first, const _type *last, _type *result)
Definition: algorithm.hpp:436
yconstfn
#define yconstfn
指定编译时常量函数。
Definition: ydef.h:680
ystdex::trivially_fill
void trivially_fill(_type *first, _type *last, byte value={})
Definition: algorithm.hpp:380
v
byte v
Definition: CharRenderer.cpp:75
ystdex::trivially_copy_n
_type * trivially_copy_n(const _type *first, size_t n, _type *result)
复制不覆盖的序列。
Definition: algorithm.hpp:394
ystdex::trivially_copy
_type * trivially_copy(const _type *first, const _type *last, _type *result)
Definition: algorithm.hpp:408
ystdex::clamp
const _type & clamp(const _type &v, const _type &lo, const _type &hi, _fComp comp=_fComp())
取约束范围的值。
Definition: algorithm.hpp:571
ystdex::trivially_fill_n
_type * trivially_fill_n(_type *first, size_t n=1, byte value={})
填充字节序列。
Definition: algorithm.hpp:369
CHRLib::f
f(d, s)
ystdex::stable_unique
_tFwd stable_unique(_tFwd first, _tFwd last)
去除迭代器指定的范围中的重复元素，且不改变元素之间的相对顺序。
Definition: algorithm.hpp:459
platform::bool
std::FILE *fp bool
Definition: FileIO.h:1280
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:262
deref_op.hpp
解引用操作。
ystdex::is_undereferenceable
bool is_undereferenceable(const _tIter &)
Definition: deref_op.hpp:45
ystdex::max
const _type & max(const _type &a, const _type &b, _fComp comp=less< _type >())
取较大的元素。
Definition: algorithm.hpp:549
ystdex::split_if
void split_if(_tIn b, _tIn e, _fPred is_delim, _fInsert insert, _func pred)
以满足迭代器谓词的指定分隔符分割序列。
Definition: algorithm.hpp:235
yunseq
#define yunseq
无序列依赖表达式组求值。
Definition: ydef.h:1022
YSLib::a
YB_PURE const _type * a
Definition: YCoreUtilities.h:167
ystdex::strict_all_of
bool strict_all_of(_tIn first, _tIn last, _fPred pred)
严格序列判断操作。
Definition: algorithm.hpp:101
ystdex::any_ops::distance
Definition: any_iterator.hpp:82
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2, _fBiPred binary_pred)
Definition: algorithm.hpp:181
ystdex::split_l
_tIn split_l(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
以指定分隔符分割保留起始分隔符的序列。
Definition: algorithm.hpp:263
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:766
ystdex
特性测试宏。
Definition: ydef.h:822
YSLib::i
return i
Definition: YCoreUtilities.h:176
ystdex::min
const _type & min(const _type &a, const _type &b, _fComp comp=less< _type >())
取较小的元素。
Definition: algorithm.hpp:527
ystdex::strict_none_of
bool strict_none_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:123
cassert.h
ISO C 断言/调试跟踪扩展。
ystdex::fast_any_of
bool fast_any_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:75
ynothrowv
#define ynothrowv
YSLib 无异常抛出保证验证：有条件地使用无异常抛出规范。
Definition: ydef.h:786
CHRLib::e
const char const char * e
Definition: CharacterProcessing.h:109
ystdex::swap
void swap(container_adaptor< _tSeqCon > &x, container_adaptor< _tSeqCon > &y)
Definition: container.hpp:179
ystdex::is_equal
相等关系仿函数。
Definition: functor.hpp:204
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2)
Definition: algorithm.hpp:198
ystdex::byte
unsigned char byte
字节类型。
Definition: ydef.h:834
functor.hpp
通用仿函数。
ystdex::transform_n
void transform_n(_fOp op, _tOut result, size_t n, _tIns...iters)
指定数量的序列变换。
Definition: algorithm.hpp:341
ystdex::split
void split(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
以指定分隔符分割序列。
Definition: algorithm.hpp:215
ystdex::for_each_equal
_func for_each_equal(_tIn first, _tIn last, const _type &value, _func f)
Definition: algorithm.hpp:149
ystdex::strict_any_of
bool strict_any_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:112
ystdex::copy_when
_tOut copy_when(_tIn first, _tOut result, _fPred pred)
复制满足谓词的序列的连续元素。
Definition: algorithm.hpp:321
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:578
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 传递对应参数。
Definition: ydef.h:995
iterator_trait.hpp
迭代器特征。
ystdex::sort_unique
_tRandom sort_unique(_tRandom first, _tRandom last)
排序指定序列范围，保留不重复元素的区间。
Definition: algorithm.hpp:512
yconstraint
#define yconstraint(_expr)
约束：接口语义。
Definition: cassert.h:88
ystdex::for_each_if
_func for_each_if(_tIn first, _tIn last, _fPred pred, _func f)
Definition: algorithm.hpp:161
ystdex::have_same_iterator_category
判断若干个迭代器是否指定的类别。
Definition: iterator_trait.hpp:44
ystdex::ref
lref< _type > ref(_type &t)
构造引用包装。
Definition: ref.hpp:132