YSTest: algorithm.hpp 源文件

YSTest PreAlpha_b700_20160611 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 = std::find(++first, last, value))
152 f(*first);
153 return f;
154 }
155
156 template<typename _tIn, typename _func, typename _fPred>
157 _func
158 for_each_if(_tIn first, _tIn last, _fPred pred, _func f)
159 {
160 for(; first != last; first = std::find_if(++first, last, pred))
161 f(*first);
162 return f;
163 }
165
166
168 inline namespace cpp2014
169 {
170
171 using std::equal;
172 #if !(__cpp_lib_robust_nonmodifying_seq_ops >= 201304 || __cplusplus > 201103L)
173 template<typename _tIn1, typename _tIn2, typename _fBiPred>
174 inline bool
175 equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2,
176 _fBiPred binary_pred)
177 {
178 if(have_same_iterator_category<std::random_access_iterator_tag, _tIn1,
179 _tIn2>())
180 {
181 if(std::distance(first1, last1) != std::distance(first2, last2))
182 return {};
183 return std::equal(first1, last1, first2, binary_pred);
184 }
185 for(; first1 != last1 && first2 != last2; ++first1, ++first2)
186 if(!bool(binary_pred(*first1, *first2)))
187 return {};
188 return first1 == last1 && first2 == last2;
189 }
190 template<typename _tIn1, typename _tIn2>
191 inline bool
192 equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2)
193 {
194 return ystdex::equal(first1, last1, first2, last2, is_equal());
195 }
196 #endif
197
198 } // inline namespace cpp2014;
199
200
202
203
207 template<typename _fPred, typename _fInsert, typename _tIn>
208 void
209 split(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
210 {
211 while(b != e)
212 {
213 _tIn i(std::find_if_not(b, e, is_delim));
214
215 b = std::find_if(i, e, is_delim);
216 if(i != b)
217 insert(i, b);
218 else
219 break;
220 }
221 }
222
227 template<typename _fPred, typename _fInsert, typename _func, typename _tIn>
228 void
229 split_if(_tIn b, _tIn e, _fPred is_delim, _fInsert insert, _func pred)
230 {
231 while(b != e)
232 {
233 _tIn i(b);
234
235 while(i != e && is_delim(*i) && pred(i))
236 ++i;
237 for(b = i; b != e; ++b)
238 {
239 b = std::find_if(b, e, is_delim);
240 if(b == e || pred(b))
241 break;
242 }
243 if(i != b)
244 insert(i, b);
245 else
246 break;
247 }
248 }
249
255 template<typename _fPred, typename _fInsert, typename _tIn>
256 _tIn
257 split_l(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
258 {
259 _tIn i(b);
260
261 while(b != e)
262 {
263 if(is_delim(*b) && i != b)
264 {
265 insert(i, b);
266 i = b;
267 }
268 ++b;
269 }
270 if(i != b)
271 insert(i, b);
272 return i;
273 }
275
276
277
300 template<typename _tIn, typename _tOut, typename _fPred, typename _fOp>
301 _tOut
302 transform_when(_tIn first, _tOut result, _fPred pred, _fOp op)
303 {
304 yunseq((yconstraint(!is_undereferenceable(first)), 0),
305 (yconstraint(!is_undereferenceable(result)), 0));
306
307 for(; pred(*first); yunseq((++first, 0), (++result, 0)))
308 *result = op(*first);
309 return result;
310 }
311
313 template<typename _tIn, typename _tOut, typename _fPred>
314 _tOut
315 copy_when(_tIn first, _tOut result, _fPred pred)
316 {
317 return ystdex::transform_when(first, result, pred,
318 [](decltype(*first)& v) ynothrow{
319 return static_cast<decltype(*first)&>(v);
320 });
321 }
323
333 template<typename _fOp, typename _tOut, typename... _tIns>
334 void
335 transform_n(_fOp op, _tOut result, size_t n, _tIns... iters)
336 {
337 while(n-- != 0)
338 {
339 yunseq((yconstraint(!is_undereferenceable(result)), 0),
340 (yconstraint(!is_undereferenceable(iters)), void(iters), 0)...);
341 *result = op((*iters)...);
342 yunseq(++result, ++iters...);
343 }
344 }
345
361 template<typename _type>
362 inline _type*
363 trivially_fill_n(_type* first, size_t n = 1, byte value = {}) ynothrowv
364 {
365 static_assert(is_trivial<_type>(), "Non-trivial type found.");
366
367 yconstraint(!is_undereferenceable(first));
368 std::memset(first, value, sizeof(_type) * n);
369 return first + n;
370 }
371
372 template<typename _type>
373 inline void
374 trivially_fill(_type* first, _type* last, byte value = {}) ynothrowv
375 {
376 ystdex::trivially_fill_n(first, last - first, value);
377 }
379
386 template<typename _type>
387 inline _type*
388 trivially_copy_n(const _type* first, size_t n, _type* result) ynothrowv
389 {
390 static_assert(is_trivial<_type>(), "Non-trivial type found.");
391 static_assert(is_copy_assignable<_type>(),
392 "Type shall meet CopyAssignable.");
393
394 yunseq((yconstraint(!is_undereferenceable(result)), 0),
395 (yconstraint(!is_undereferenceable(first)), 0));
396 std::memcpy(result, first, sizeof(_type) * n);
397 return result + n;
398 }
399
400 template<typename _type>
401 inline _type*
402 trivially_copy(const _type* first, const _type* last, _type* result) ynothrowv
403 {
404 return ystdex::trivially_copy_n(first, last - first, result);
405 }
407
414 template<class _type>
415 inline _type*
416 trivially_move_n(const _type* first, size_t n, _type* result)
417 {
418 static_assert(is_trivial<_type>(), "Non-trivial type found.");
419 static_assert(is_copy_assignable<_type>(),
420 "Type shall meet CopyAssignable.");
421
422 yunseq((yconstraint(!is_undereferenceable(result)), 0),
423 (yconstraint(!is_undereferenceable(first)), 0));
424 std::memmove(result, first, sizeof(_type) * n);
425 return result + n;
426 }
427
428 template<class _type>
429 inline _type*
430 trivially_move(const _type* first, const _type* last, _type* result)
431 {
432 return ystdex::trivially_move_n(first, last - first, result);
433 }
435
436
437
451 template<typename _tFwd>
452 _tFwd
453 stable_unique(_tFwd first, _tFwd last)
454 {
455 _tFwd result(first);
456
457 for(_tFwd i(first); i != last; ++i)
458 if(std::find(first, result, *i) == result)
459 {
460 using std::swap;
461
462 swap(*i, *result);
463 ++result;
464 }
465 return result;
466 }
468 template<typename _tFwd, typename _fPred>
469 _tFwd
470 stable_unique(_tFwd first, _tFwd last, _fPred pred)
471 {
472 _tFwd result(first);
473
474 for(_tFwd i(first); i != last; ++i)
475 if(std::find_if(first, result,
476 std::bind(pred, std::ref(*i), std::placeholders::_1)) == result)
477 {
478 using std::swap;
479
480 swap(*i, *result);
481 ++result;
482 }
483 return result;
484 }
486
487
488
504 template<typename _tRandom>
505 inline _tRandom
506 sort_unique(_tRandom first, _tRandom last)
507 {
508 std::sort(first, last);
509 return std::unique(first, last);
510 }
511
512
519 template<typename _type, typename _fComp = less<_type>>
520 yconstfn const _type&
521 min(const _type& a, const _type& b, _fComp comp = less<_type>())
522 {
523 return comp(b, a) ? b : a;
524 }
525 template<typename _type, typename _fComp = less<_type>>
526 yconstfn const _type&
527 min(std::initializer_list<_type> t, _fComp comp = less<_type>(),
528 yimpl(size_t n = 0))
529 {
530 return n + 1 < t.size() ? ystdex::min(*(t.begin() + n),
531 ystdex::min(t, comp, n + 1)) : *(t.begin() + n);
532 }
534
541 template<typename _type, typename _fComp = less<_type>>
542 yconstfn const _type&
543 max(const _type& a, const _type& b, _fComp comp = less<_type>())
544 {
545 return comp(a, b) ? b : a;
546 }
547 template<typename _type, typename _fComp = less<_type>>
548 yconstfn const _type&
549 max(std::initializer_list<_type> t, _fComp comp = less<_type>(),
550 yimpl(size_t n = 0))
551 {
552 return n + 1 < t.size() ? ystdex::max(*(t.begin() + n),
553 ystdex::max(t, comp, n + 1)) : *(t.begin() + n);
554 }
556
563 template<typename _type, typename _fComp = less<>>
564 yconstfn const _type&
565 clamp(const _type& v, const _type& lo, const _type& hi, _fComp comp = _fComp())
566 {
567 return yconstraint(!comp(hi, lo)), comp(v, lo) ? lo : comp(hi, v) ? hi : v;
568 }
569
570 template<typename _tIn, typename _tOut, typename _fComp = less<>>
571 yconstfn _tOut
572 clamp_range(_tIn first, _tIn last, _tOut result, const typename
573 std::iterator_traits<_tIn>::value_type& lo, const typename
574 std::iterator_traits<_tIn>::value_type& hi, _fComp comp = _fComp())
575 {
576 using arg_type = decltype(lo);
577
578 return std::transform(first, last, result, [&](arg_type val) -> arg_type{
579 return ystdex::clamp(val, lo, hi, comp);
580 });
581 }
583
584
585
586 } // namespace ystdex;
587
588 #endif
589
ystdex::trivially_fill_n
_type * trivially_fill_n(_type *first, size_t n=1, byte value={})
填充字节序列。
Definition: algorithm.hpp:363
ystdex::fast_all_of
bool fast_all_of(_tIn first, _tIn last, _fPred pred)
快速序列判断操作。
Definition: algorithm.hpp:65
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:740
ystdex::for_each_equal
_func for_each_equal(_tIn first, _tIn last, const _type &value, _func f)
Definition: algorithm.hpp:149
yconstraint
#define yconstraint(_expr)
约束：接口语义。
Definition: cassert.h:82
ystdex::swap
void swap(container_adaptor< _tSeqCon > &x, container_adaptor< _tSeqCon > &y)
Definition: container.hpp:179
cassert.h
ISO C 断言/调试跟踪扩展。
v
byte v
Definition: CharRenderer.cpp:75
deref_op.hpp
解引用操作。
ystdex::fast_any_of
bool fast_any_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:75
ystdex::transform_n
void transform_n(_fOp op, _tOut result, size_t n, _tIns...iters)
指定数量的序列变换。
Definition: algorithm.hpp:335
CHRLib::e
const char const char * e
Definition: CharacterProcessing.h:109
ystdex::is_equal
相等关系仿函数。
Definition: functor.hpp:185
ystdex::fast_none_of
bool fast_none_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:85
ynothrowv
#define ynothrowv
YSLib 无异常抛出保证验证：有条件地使用无异常抛出规范。
Definition: ydef.h:760
ystdex::split_if
void split_if(_tIn b, _tIn e, _fPred is_delim, _fInsert insert, _func pred)
以满足迭代器谓词的指定分隔符分割序列。
Definition: algorithm.hpp:229
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:256
ystdex::copy_when
_tOut copy_when(_tIn first, _tOut result, _fPred pred)
复制满足谓词的序列的连续元素。
Definition: algorithm.hpp:315
ystdex::clamp
const _type & clamp(const _type &v, const _type &lo, const _type &hi, _fComp comp=_fComp())
取约束范围的值。
Definition: algorithm.hpp:565
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:572
ystdex::transform_when
_tOut transform_when(_tIn first, _tOut result, _fPred pred, _fOp op)
变换满足谓词的序列的连续元素。
Definition: algorithm.hpp:302
ystdex::trivially_move_n
_type * trivially_move_n(const _type *first, size_t n, _type *result)
复制可能覆盖的序列。
Definition: algorithm.hpp:416
ystdex::trivially_copy
_type * trivially_copy(const _type *first, const _type *last, _type *result)
Definition: algorithm.hpp:402
ystdex::split_l
_tIn split_l(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
以指定分隔符分割保留起始分隔符的序列。
Definition: algorithm.hpp:257
yunseq
#define yunseq
无序列依赖表达式组求值。
Definition: ydef.h:996
ystdex::for_each_if
_func for_each_if(_tIn first, _tIn last, _fPred pred, _func f)
Definition: algorithm.hpp:158
ystdex
特性测试宏。
Definition: ydef.h:796
ystdex::max
const _type & max(const _type &a, const _type &b, _fComp comp=less< _type >())
取较大的元素。
Definition: algorithm.hpp:543
ystdex::sort_unique
_tRandom sort_unique(_tRandom first, _tRandom last)
排序指定序列范围，保留不重复元素的区间。
Definition: algorithm.hpp:506
ystdex::stable_unique
_tFwd stable_unique(_tFwd first, _tFwd last)
去除迭代器指定的范围中的重复元素，且不改变元素之间的相对顺序。
Definition: algorithm.hpp:453
functor.hpp
通用仿函数。
ystdex::have_same_iterator_category
判断若干个迭代器是否指定的类别。
Definition: iterator_trait.hpp:44
ystdex::is_undereferenceable
bool is_undereferenceable(const _tIter &)
Definition: deref_op.hpp:45
ystdex::strict_all_of
bool strict_all_of(_tIn first, _tIn last, _fPred pred)
严格序列判断操作。
Definition: algorithm.hpp:101
YSLib::i
return i
Definition: YCoreUtilities.h:176
ystdex::byte
unsigned char byte
字节类型。
Definition: ydef.h:808
ystdex::strict_none_of
bool strict_none_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:123
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2)
Definition: algorithm.hpp:192
yconstfn
#define yconstfn
指定编译时常量函数。
Definition: ydef.h:654
YSLib::a
YB_PURE const _type * a
Definition: YCoreUtilities.h:167
ystdex::trivially_copy_n
_type * trivially_copy_n(const _type *first, size_t n, _type *result)
复制不覆盖的序列。
Definition: algorithm.hpp:388
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 传递对应参数。
Definition: ydef.h:969
iterator_trait.hpp
迭代器特征。
ystdex::split
void split(_tIn b, _tIn e, _fPred is_delim, _fInsert insert)
以指定分隔符分割序列。
Definition: algorithm.hpp:209
ystdex::min
const _type & min(const _type &a, const _type &b, _fComp comp=less< _type >())
取较小的元素。
Definition: algorithm.hpp:521
ystdex::trivially_fill
void trivially_fill(_type *first, _type *last, byte value={})
Definition: algorithm.hpp:374
YSLib::IO::f
const string &path const String &path _func f
Definition: YSLib/Service/FileSystem.h:430
ystdex::any_ops::distance
Definition: any_iterator.hpp:74
ystdex::trivially_move
_type * trivially_move(const _type *first, const _type *last, _type *result)
Definition: algorithm.hpp:430
platform::bool
std::FILE *fp bool
Definition: FileIO.h:1187
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2, _fBiPred binary_pred)
Definition: algorithm.hpp:175
platform::n
size_t n
Definition: YCLib/FileSystem.cpp:321
ystdex::ref
lref< _type > ref(_type &t)
构造引用包装。
Definition: ref.hpp:120
ystdex::strict_any_of
bool strict_any_of(_tIn first, _tIn last, _fPred pred)
Definition: algorithm.hpp:112