1
2
3
4
5
6 using System.Concepts;
7
8 namespace System
9 {
10 public inline constexpr nothrow const T& Min<T>(const T& left, const T& right) where T is LessThanComparable
11 {
12 if (left <= right) return left;
13 return right;
14 }
15
16 public inline constexpr nothrow const T& Max<T>(const T& left, const T& right) where T is LessThanComparable
17 {
18 if (right >= left) return right;
19 return left;
20 }
21
22 public inline nothrow void Swap<T>(T& left, T& right) where T is MoveConstructible and T is MoveAssignable and T is Destructible
23 {
24 T temp(Rvalue(left));
25 left = Rvalue(right);
26 right = Rvalue(temp);
27 }
28
29 public nothrow void Reverse<I>(I begin, I end) where I is RandomAccessIterator
30 {
31 while (begin < end)
32 {
33 --end;
34 Swap(*begin, *end);
35 ++begin;
36 }
37 }
38
39 public nothrow void Reverse<I>(I begin, I end) where I is BidirectionalIterator
40 {
41 while (true)
42 {
43 if (begin == end)
44 {
45 return;
46 }
47 --end;
48 if (begin == end)
49 {
50 return;
51 }
52 Swap(*begin, *end);
53 ++begin;
54 }
55 }
56
57 public Pair<I, I> ReverseUntil<I>(I first, I middle, I last) where I is BidirectionalIterator
58 {
59 while (first != middle && middle != last)
60 {
61 --last;
62 Swap(*first, *last);
63 ++first;
64 }
65 return MakePair(first, last);
66 }
67
68 public I Rotate<I>(I first, I middle, I last) where I is BidirectionalIterator
69 {
70 Reverse(first, middle);
71 Reverse(middle, last);
72 Pair<I, I> p = ReverseUntil(first, middle, last);
73 Reverse(p.first, p.second);
74 if (middle == p.first) return p.second;
75 return p.first;
76 }
77
78 public O Copy<I, O>(I begin, I end, O to) where I is InputIterator and O is OutputIterator and CopyAssignable<O.ValueType, I.ValueType>
79 {
80 while (begin != end)
81 {
82 *to = *begin;
83 ++begin;
84 ++to;
85 }
86 return to;
87 }
88
89 public O CopyBackward<I, O>(I begin, I end, O to) where I is BidirectionalIterator and O is BidirectionalIterator and CopyAssignable<O.ValueType, I.ValueType>
90 {
91 while (begin != end)
92 {
93 --to;
94 --end;
95 *to = *end;
96 }
97 return to;
98 }
99
100 public O Move<I, O>(I begin, I end, O to) where I is InputIterator and O is OutputIterator and O.ValueType is I.ValueType and I.ValueType is MoveAssignable
101 {
102 while (begin != end)
103 {
104 *to = Rvalue(*begin);
105 ++begin;
106 ++to;
107 }
108 return to;
109 }
110
111 public O MoveBackward<I, O>(I begin, I end, O to) where I is BidirectionalIterator and O is BidirectionalIterator and O.ValueType is I.ValueType and I.ValueType is MoveAssignable
112 {
113 while (begin != end)
114 {
115 --to;
116 --end;
117 *to = Rvalue(*end);
118 }
119 return to;
120 }
121
122 public constexpr nothrow long Distance<I>(I first, I last) where I is ForwardIterator
123 {
124 long distance = 0;
125 while (first != last)
126 {
127 ++first;
128 ++distance;
129 }
130 return distance;
131 }
132
133 public inline constexpr nothrow long Distance<I>(I first, I last) where I is RandomAccessIterator
134 {
135 return last - first;
136 }
137
138 public constexpr I Next<I>(I i, long n) where I is ForwardIterator
139 {
140 if (n < 0)
141 {
142 ThrowInvalidParameterException();
143 }
144 while (n > 0)
145 {
146 ++i;
147 --n;
148 }
149 return i;
150 }
151
152 public inline constexpr nothrow I Next<I>(I i, long n) where I is RandomAccessIterator
153 {
154 return i + n;
155 }
156
157 public constexpr nothrow I LowerBound<I, T>(I first, I last, const T& value) where I is ForwardIterator and TotallyOrdered<T, I.ValueType>
158 {
159 long len = Distance(first, last);
160 while (len > 0)
161 {
162 long half = len >> 1;
163 I middle = Next(first, half);
164 if (value > *middle)
165 {
166 first = middle;
167 ++first;
168 len = len - half - 1;
169 }
170 else
171 {
172 len = half;
173 }
174 }
175 return first;
176 }
177
178 public constexpr nothrow I LowerBound<I, T, R>(I first, I last, const T& value, R r) where I is ForwardIterator and T is I.ValueType and R is Relation and R.Domain is I.ValueType
179 {
180 long len = Distance(first, last);
181 while (len > 0)
182 {
183 long half = len >> 1;
184 I middle = Next(first, half);
185 if (r(*middle, value))
186 {
187 first = middle;
188 ++first;
189 len = len - half - 1;
190 }
191 else
192 {
193 len = half;
194 }
195 }
196 return first;
197 }
198
199 public constexpr nothrow I UpperBound<I, T>(I first, I last, const T& value) where I is ForwardIterator and TotallyOrdered<T, I.ValueType>
200 {
201 long len = Distance(first, last);
202 while (len > 0)
203 {
204 long half = len >> 1;
205 I middle = Next(first, half);
206 if (value < *middle)
207 {
208 len = half;
209 }
210 else
211 {
212 first = middle;
213 ++first;
214 len = len - half - 1;
215 }
216 }
217 return first;
218 }
219
220 public constexpr nothrow I UpperBound<I, T, R>(I first, I last, const T& value, R r) where I is ForwardIterator and T is I.ValueType and R is Relation and R.Domain is I.ValueType
221 {
222 long len = Distance(first, last);
223 while (len > 0)
224 {
225 long half = len >> 1;
226 I middle = Next(first, half);
227 if (r(value, *middle))
228 {
229 len = half;
230 }
231 else
232 {
233 first = middle;
234 ++first;
235 len = len - half - 1;
236 }
237 }
238 return first;
239 }
240
241 public constexpr Pair<I, I> EqualRange<I, T>(I first, I last, const T& value) where I is ForwardIterator and TotallyOrdered<T, I.ValueType>
242 {
243 long len = Distance(first, last);
244 while (len > 0)
245 {
246 long half = len >> 1;
247 I middle = Next(first, half);
248 if (*middle < value)
249 {
250 first = middle;
251 ++first;
252 len = len - half - 1;
253 }
254 else if (value < *middle)
255 {
256 len = half;
257 }
258 else
259 {
260 I left = LowerBound(first, middle, value);
261 I end = Next(first, len);
262 ++middle;
263 I right = UpperBound(middle, end, value);
264 return Pair<I, I>(left, right);
265 }
266 }
267 return Pair<I, I>(first, first);
268 }
269
270 public constexpr Pair<I, I> EqualRange<I, T, R>(I first, I last, const T& value, R r) where I is ForwardIterator and T is I.ValueType and R is Relation and R.Domain is I.ValueType
271 {
272 long len = Distance(first, last);
273 while (len > 0)
274 {
275 long half = len >> 1;
276 I middle = Next(first, half);
277 if (r(*middle, value))
278 {
279 first = middle;
280 ++first;
281 len = len - half - 1;
282 }
283 else if (r(value, *middle))
284 {
285 len = half;
286 }
287 else
288 {
289 I left = LowerBound(first, middle, value, r);
290 I end = Next(first, len);
291 ++middle;
292 I right = UpperBound(middle, end, value, r);
293 return Pair<I, I>(left, right);
294 }
295 }
296 return Pair<I, I>(first, first);
297 }
298
299 public constexpr nothrow I Find<I, T>(I begin, I end, const T& value) where I is InputIterator and T is Semiregular and EqualityComparable<T, I.ValueType>
300 {
301 while (begin != end)
302 {
303 if (*begin == value)
304 {
305 return begin;
306 }
307 ++begin;
308 }
309 return end;
310 }
311
312 public constexpr nothrow I Find<I, P>(I begin, I end, P p) where I is InputIterator and P is UnaryPredicate and P.ArgumentType is I.ValueType
313 {
314 while (begin != end)
315 {
316 if (p(*begin))
317 {
318 return begin;
319 }
320 ++begin;
321 }
322 return end;
323 }
324
325 public constexpr nothrow long Count<I, T>(I begin, I end, const T& value) where I is InputIterator and T is Semiregular and EqualityComparable<T, I.ValueType>
326 {
327 long count = 0;
328 while (begin != end)
329 {
330 if (*begin == value)
331 {
332 ++count;
333 }
334 ++begin;
335 }
336 return count;
337 }
338
339 public constexpr nothrow long Count<I, P>(I begin, I end, P p) where I is InputIterator and P is UnaryPredicate and P.ArgumentType is I.ValueType
340 {
341 long count = 0;
342 while (begin != end)
343 {
344 if (p(*begin))
345 {
346 ++count;
347 }
348 ++begin;
349 }
350 return count;
351 }
352
353 public O RemoveCopy<I, O, P>(I begin, I end, O result, P p) where I is InputIterator and O is OutputIterator and O.ValueType is I.ValueType and P is UnaryPredicate and P.ArgumentType is I.ValueType
354 {
355 while (begin != end)
356 {
357 if (!p(*begin))
358 {
359 *result = *begin;
360 ++result;
361 }
362 ++begin;
363 }
364 return result;
365 }
366
367 public I Remove<I, P>(I begin, I end, P p) where I is ForwardIterator and P is UnaryPredicate and P.ArgumentType is I.ValueType
368 {
369 begin = Find(begin, end, p);
370 if (begin == end)
371 {
372 return begin;
373 }
374 else
375 {
376 I i = begin;
377 ++i;
378 return RemoveCopy(i, end, begin, p);
379 }
380 }
381
382 public O RemoveCopy<I, O, T>(I begin, I end, O result, const T& value)
383 where T is Semiregular and I is InputIterator and O is OutputIterator and O.ValueType is I.ValueType and EqualityComparable<T, I.ValueType>
384 {
385 while (begin != end)
386 {
387 if (*begin != value)
388 {
389 *result = *begin;
390 ++result;
391 }
392 ++begin;
393 }
394 return result;
395 }
396
397 public I Remove<I, T>(I begin, I end, const T& value) where I is ForwardIterator and T is Semiregular and EqualityComparable<T, I.ValueType>
398 {
399 begin = Find(begin, end, value);
400 if (begin == end)
401 {
402 return begin;
403 }
404 else
405 {
406 I i = begin;
407 ++i;
408 return RemoveCopy(i, end, begin, value);
409 }
410 }
411
412 public nothrow void Fill<I, T>(I begin, I end, const T& value) where T is Semiregular and I is ForwardIterator and I.ValueType is T
413 {
414 while (begin != end)
415 {
416 *begin = value;
417 ++begin;
418 }
419 }
420
421 public nothrow T Accumulate<I, T, Op>(I begin, I end, T init, Op op) where I is InputIterator and T is Semiregular and Op is BinaryOperation and Op.FirstArgumentType is T and Op.SecondArgumentType is I.ValueType
422 {
423 while (begin != end)
424 {
425 init = op(init, *begin);
426 ++begin;
427 }
428 return init;
429 }
430
431 public constexpr F ForEach<I, F>(I begin, I end, F f) where I is InputIterator and F is UnaryFunction and F.ArgumentType is I.ValueType
432 {
433 while (begin != end)
434 {
435 f(*begin);
436 ++begin;
437 }
438 return f;
439 }
440
441 public O Transform<I, O, F>(I begin, I end, O to, F fun)
442 where I is InputIterator and O is OutputIterator and F is UnaryFunction and F.ArgumentType is I.ValueType and CopyAssignable<O.ValueType, F.ResultType>
443 {
444 while (begin != end)
445 {
446 *to = fun(*begin);
447 ++begin;
448 ++to;
449 }
450 return to;
451 }
452
453 public O Transform<I1, I2, O, F>(I1 begin1, I1 end1, I2 begin2, O to, F fun)
454 where I1 is InputIterator and I2 is InputIterator and O is OutputIterator and F is BinaryFunction and F.FirstArgumentType is I1.ValueType and F.SecondArgumentType is I2.ValueType and
455 CopyAssignable<O.ValueType, F.ResultType>
456 {
457 while (begin1 != end1)
458 {
459 *to = fun(*begin1, *begin2);
460 ++begin1;
461 ++begin2;
462 ++to;
463 }
464 return to;
465 }
466
467 public inline nothrow const T& Select_0_2<T, R>(const T& a, const T& b, R r) where T is Semiregular and R is Relation and R.Domain is T
468 {
469 if (r(b, a)) return b;
470 return a;
471 }
472
473 public inline nothrow const T& Select_1_2<T, R>(const T& a, const T& b, R r) where T is Semiregular and R is Relation and R.Domain is T
474 {
475 if (r(b, a)) return a;
476 return b;
477 }
478
479 public inline nothrow const T& Select_0_3<T, R>(const T& a, const T& b, const T& c, R r) where T is Semiregular and R is Relation and R.Domain is T
480 {
481 return Select_0_2(Select_0_2(a, b, r), c, r);
482 }
483
484 public inline nothrow const T& Select_2_3<T, R>(const T& a, const T& b, const T& c, R r) where T is Semiregular and R is Relation and R.Domain is T
485 {
486 return Select_1_2(Select_1_2(a, b, r), c, r);
487 }
488
489 public inline nothrow const T& Select_1_3_ab<T, R>(const T& a, const T& b, const T& c, R r) where T is Semiregular and R is Relation and R.Domain is T
490 {
491 if (!r(c, b)) return b;
492 return Select_1_2(a, c, r);
493 }
494
495 public inline nothrow const T& Select_1_3<T, R>(const T& a, const T& b, const T& c, R r) where T is Semiregular and R is Relation and R.Domain is T
496 {
497 if (r(b, a)) return Select_1_3_ab(b, a, c, r);
498 return Select_1_3_ab(a, b, c, r);
499 }
500
501 public nothrow const T& Median<T, R>(const T& a, const T& b, const T& c, R r) where T is Semiregular and R is Relation and R.Domain is T
502 {
503 return Select_1_3(a, b, c, r);
504 }
505
506 public nothrow const T& Median<T>(const T& a, const T& b, const T& c) where T is TotallyOrdered
507 {
508 return Median(a, b, c, Less<T>());
509 }
510
511 public nothrow I UnguardedPartition<I, T, R>(I begin, I end, const T& pivot, R r) where I is RandomAccessIterator and T is I.ValueType and R is Relation and R.Domain is I.ValueType
512 {
513 while (true)
514 {
515 while (r(*begin, pivot))
516 {
517 ++begin;
518 }
519 --end;
520 while (r(pivot, *end))
521 {
522 --end;
523 }
524 if (begin >= end)
525 {
526 return begin;
527 }
528 Swap(*begin, *end);
529 ++begin;
530 }
531
532 return begin;
533 }
534
535 public nothrow void UnguardedLinearInsert<I, T, R>(I last, const T& val, R r) where I is RandomAccessIterator and T is I.ValueType and R is Relation and R.Domain is I.ValueType
536 {
537 I next = last;
538 --next;
539 while (r(val, *next))
540 {
541 *last = *next;
542 last = next;
543 --next;
544 }
545 *last = val;
546 }
547
548 public nothrow void UnguardedLinearInsert<I, T, R>(I last, T&& val, R r) where I is RandomAccessIterator and T is I.ValueType and R is Relation and R.Domain is I.ValueType and
549 I.ValueType is Movable
550 {
551 I next = last;
552 --next;
553 while (r(val, *next))
554 {
555 *last = Rvalue(*next);
556 last = next;
557 --next;
558 }
559 *last = Rvalue(val);
560 }
561
562 public void LinearInsert<I, R>(I first, I last, R r) where I is RandomAccessIterator and R is Relation and R.Domain is I.ValueType
563 {
564 I.ValueType val = *last;
565 if (r(val, *first))
566 {
567 CopyBackward(first, last, last + 1);
568 *first = val;
569 }
570 else
571 {
572 UnguardedLinearInsert(last, val, r);
573 }
574 }
575
576 public void LinearInsert<I, R>(I first, I last, R r) where I is RandomAccessIterator and R is Relation and R.Domain is I.ValueType and I.ValueType is Movable
577 {
578 I.ValueType val = Rvalue(*last);
579 if (r(val, *first))
580 {
581 MoveBackward(first, last, last + 1);
582 *first = Rvalue(val);
583 }
584 else
585 {
586 UnguardedLinearInsert(last, Rvalue(val), r);
587 }
588 }
589
590 public void InsertionSort<I, R>(I begin, I end, R r) where I is RandomAccessIterator and R is Relation and R.Domain is I.ValueType
591 {
592 if (begin == end)
593 {
594 return;
595 }
596 for (I i = begin + 1; i != end; ++i;)
597 {
598 LinearInsert(begin, i, r);
599 }
600 }
601
602 public inline void InsertionSort<I>(I begin, I end) where I is RandomAccessIterator and I.ValueType is TotallyOrdered
603 {
604 InsertionSort(begin, end, Less<I.ValueType>());
605 }
606
607 public const long insertionSortThreshold = 16;
608
609 public void PartialQuickSort<I, R>(I begin, I end, R r) where I is RandomAccessIterator and R is Relation and R.Domain is I.ValueType
610 {
611 while (end - begin > insertionSortThreshold)
612 {
613 const I.ValueType& pivot = Median(*begin, *(begin + (end - begin) / 2), *(end - 1), r);
614 I cut = UnguardedPartition(begin, end, pivot, r);
615 PartialQuickSort(cut, end, r);
616 end = cut;
617 }
618 }
619
620 public void Sort<I, R>(I begin, I end, R r) where I is RandomAccessIterator and R is Relation and R.Domain is I.ValueType
621 {
622 if (begin != end)
623 {
624 PartialQuickSort(begin, end, r);
625 InsertionSort(begin, end, r);
626 }
627 }
628
629 public inline void Sort<I>(I begin, I end) where I is RandomAccessIterator and I.ValueType is TotallyOrdered
630 {
631 Sort(begin, end, Less<I.ValueType>());
632 }
633
634 public inline void Sort<C, R>(C& c, R r) where C is RandomAccessContainer and R is Relation and R.Domain is C.Iterator.ValueType
635 {
636 Sort(c.Begin(), c.End(), r);
637 }
638
639 public inline void Sort<C>(C& c) where C is RandomAccessContainer and C.Iterator.ValueType is TotallyOrdered
640 {
641 Sort(c.Begin(), c.End());
642 }
643
644 public void Sort<C>(C& c) where C is ForwardContainer and C.Iterator.ValueType is TotallyOrdered
645 {
646 List<C.ValueType> list;
647 Copy(c.CBegin(), c.CEnd(), BackInserter(list));
648 Sort(list);
649 Copy(list.CBegin(), list.CEnd(), c.Begin());
650 }
651
652 public void Sort<C, R>(C& c, R r) where C is ForwardContainer and R is Relation and R.Domain is C.Iterator.ValueType
653 {
654 List<C.ValueType> list;
655 Copy(c.CBegin(), c.CEnd(), BackInserter(list));
656 Sort(list, r);
657 Copy(list.CBegin(), list.CEnd(), c.Begin());
658 }
659
660 public constexpr nothrow bool Equal<I1, I2, R>(I1 first1, I1 last1, I2 first2, I2 last2, R r) where I1 is InputIterator and I2 is InputIterator and Relation<R, I1.ValueType, I2.ValueType>
661 {
662 while (first1 != last1 && first2 != last2)
663 {
664 if (!r(*first1, *first2))
665 {
666 return false;
667 }
668 ++first1;
669 ++first2;
670 }
671 return first1 == last1 && first2 == last2;
672 }
673
674 public inline constexpr nothrow bool Equal<I1, I2>(I1 first1, I1 last1, I2 first2, I2 last2) where I1 is InputIterator and I2 is InputIterator and EqualityComparable<I1.ValueType, I2.ValueType>
675 {
676 return Equal(first1, last1, first2, last2, EqualTo<I1.ValueType, I2.ValueType>());
677 }
678
679 public constexpr nothrow bool LexicographicalCompare<I1, I2, R>(I1 first1, I1 last1, I2 first2, I2 last2, R r)
680 where I1 is InputIterator and I2 is InputIterator and Same<I1.ValueType, I2.ValueType> and Relation<R, I1.ValueType, I2.ValueType> and Relation<R, I2.ValueType, I1.ValueType>
681 {
682 while (first1 != last1 && first2 != last2)
683 {
684 if (r(*first1, *first2))
685 {
686 return true;
687 }
688 if (r(*first2, *first1))
689 {
690 return false;
691 }
692 ++first1;
693 ++first2;
694 }
695 return first1 == last1 && first2 != last2;
696 }
697
698 public inline constexpr nothrow bool LexicographicalCompare<I1, I2>(I1 first1, I1 last1, I2 first2, I2 last2) where I1 is InputIterator and I2 is InputIterator and LessThanComparable<I1.ValueType, I2.ValueType>
699 {
700 return LexicographicalCompare(first1, last1, first2, last2, Less<I1.ValueType, I2.ValueType>());
701 }
702
703 public constexpr nothrow I MinElement<I>(I first, I last) where I is ForwardIterator and I.ValueType is TotallyOrdered
704 {
705 if (first == last)
706 {
707 return first;
708 }
709 I minElementPos = first;
710 ++first;
711 while (first != last)
712 {
713 if (*first < *minElementPos)
714 {
715 minElementPos = first;
716 }
717 ++first;
718 }
719 return minElementPos;
720 }
721
722 public constexpr nothrow I MinElement<I, R>(I first, I last, R r) where I is ForwardIterator and R is Relation and R.Domain is I.ValueType
723 {
724 if (first == last)
725 {
726 return first;
727 }
728 I minElementPos = first;
729 ++first;
730 while (first != last)
731 {
732 if (r(*first, *minElementPos))
733 {
734 minElementPos = first;
735 }
736 ++first;
737 }
738 return minElementPos;
739 }
740
741 public constexpr nothrow I MaxElement<I>(I first, I last) where I is ForwardIterator and I.ValueType is TotallyOrdered
742 {
743 if (first == last)
744 {
745 return first;
746 }
747 I maxElementPos = first;
748 ++first;
749 while (first != last)
750 {
751 if (*maxElementPos < *first)
752 {
753 maxElementPos = first;
754 }
755 ++first;
756 }
757 return maxElementPos;
758 }
759
760 public constexpr nothrow I MaxElement<I, R>(I first, I last, R r) where I is ForwardIterator and R is Relation and R.Domain is I.ValueType
761 {
762 if (first == last)
763 {
764 return first;
765 }
766 I maxElementPos = first;
767 ++first;
768 while (first != last)
769 {
770 if (r(*maxElementPos, *first))
771 {
772 maxElementPos = first;
773 }
774 ++first;
775 }
776 return maxElementPos;
777 }
778
779 public inline constexpr nothrow T Abs<T>(const T& x) where T is OrderedAdditiveGroup
780 {
781 if (x < T(0))
782 {
783 return -x;
784 }
785 return x;
786 }
787
788
789 public constexpr nothrow U Factorial<U>(U n) where U is UnsignedInteger
790 {
791 U f = 1u;
792 for (U u = 2u; u <= n; ++u;)
793 {
794 f = f * u;
795 }
796 return f;
797 }
798
799 public constexpr nothrow T Gcd<T>(T a, T b) where T is EuclideanSemiring
800 {
801 while (true)
802 {
803 if (b == T(0)) return a;
804 a = a % b;
805 if (a == T(0)) return b;
806 b = b % a;
807 }
808 }
809
810 public nothrow bool NextPermutation<I>(I begin, I end) where I is BidirectionalIterator and I.ValueType is LessThanComparable
811 {
812 if (begin == end)
813 {
814 return false;
815 }
816 I i = begin;
817 ++i;
818 if (i == end)
819 {
820 return false;
821 }
822 i = end;
823 --i;
824 while (true)
825 {
826 I ii = i;
827 --i;
828 if (*i < *ii)
829 {
830 I j = end;
831 --j;
832 while (*i >= *j)
833 {
834 --j;
835 }
836 Swap(*i, *j);
837 Reverse(ii, end);
838 return true;
839 }
840 if (i == begin)
841 {
842 Reverse(begin, end);
843 return false;
844 }
845 }
846 }
847
848 public nothrow bool NextPermutation<I, R>(I begin, I end, R r) where I is BidirectionalIterator and R is Relation and R.Domain is I.ValueType
849 {
850 if (begin == end)
851 {
852 return false;
853 }
854 I i = begin;
855 ++i;
856 if (i == end)
857 {
858 return false;
859 }
860 i = end;
861 --i;
862 while (true)
863 {
864 I ii = i;
865 --i;
866 if (r(*i, *ii))
867 {
868 I j = end;
869 --j;
870 while (!r(*i, *j))
871 {
872 --j;
873 }
874 Swap(*i, *j);
875 Reverse(ii, end);
876 return true;
877 }
878 if (i == begin)
879 {
880 Reverse(begin, end);
881 return false;
882 }
883 }
884 }
885
886 public nothrow bool PrevPermutation<I>(I begin, I end) where I is BidirectionalIterator and I.ValueType is LessThanComparable
887 {
888 if (begin == end)
889 {
890 return false;
891 }
892 I i = begin;
893 ++i;
894 if (i == end)
895 {
896 return false;
897 }
898 i = end;
899 --i;
900 while (true)
901 {
902 I ii = i;
903 --i;
904 if (*ii < *i)
905 {
906 I j = end;
907 --j;
908 while (*j >= *i)
909 {
910 --j;
911 }
912 Swap(*i, *j);
913 Reverse(ii, end);
914 return true;
915 }
916 if (i == begin)
917 {
918 Reverse(begin, end);
919 return false;
920 }
921 }
922 }
923
924 public nothrow bool PrevPermutation<I, R>(I begin, I end, R r) where I is BidirectionalIterator and R is Relation and R.Domain is I.ValueType
925 {
926 if (begin == end)
927 {
928 return false;
929 }
930 I i = begin;
931 ++i;
932 if (i == end)
933 {
934 return false;
935 }
936 i = end;
937 --i;
938 while (true)
939 {
940 I ii = i;
941 --i;
942 if (r(*ii, *i))
943 {
944 I j = end;
945 --j;
946 while (!r(*j, *i))
947 {
948 --j;
949 }
950 Swap(*i, *j);
951 Reverse(ii, end);
952 return true;
953 }
954 if (i == begin)
955 {
956 Reverse(begin, end);
957 return false;
958 }
959 }
960 }
961
962 public inline nothrow void InitRand(uint seed)
963 {
964 RtInitRand(seed);
965 }
966
967 public inline nothrow uint Random()
968 {
969 return RtRandom();
970 }
971
972 public inline nothrow ulong Random64()
973 {
974 return RtRandom64();
975 }
976
977 public inline nothrow uint RandomNumber(uint n)
978 {
979 return Random() % n;
980 }
981
982 public nothrow void RandomShuffle<I>(I begin, I end) where I is RandomAccessIterator
983 {
984 if (begin == end) return;
985 for (I i = begin + 1; i != end; ++i;)
986 {
987 long d = (i - begin) + 1;
988 long r = cast<long>(RandomNumber(cast<uint>(d)));
989 I j = begin + r;
990 Swap(*i, *j);
991 }
992 }
993
994 public nothrow I AdjacentFind<I, R>(I begin, I end, R r) where I is ForwardIterator and R is Relation and R.Domain is I.ValueType
995 {
996 if (begin != end)
997 {
998 I i = begin;
999 ++i;
1000 while (i != end)
1001 {
1002 if (r(*begin, *i))
1003 {
1004 return begin;
1005 }
1006 begin = i;
1007 ++i;
1008 }
1009 }
1010 return end;
1011 }
1012
1013 public nothrow I AdjacentFind<I>(I begin, I end) where I is ForwardIterator
1014 {
1015 return AdjacentFind(begin, end, EqualTo<I.ValueType>());
1016 }
1017
1018 public nothrow I Unique<I, R>(I begin, I end, R r) where I is ForwardIterator and R is Relation and R.Domain is I.ValueType
1019 {
1020 begin = AdjacentFind(begin, end, r);
1021 if (begin != end)
1022 {
1023 I i = begin;
1024 ++i;
1025 ++i;
1026 while (i != end)
1027 {
1028 if (!r(*begin, *i))
1029 {
1030 *++begin = Rvalue(*i);
1031 }
1032 ++i;
1033 }
1034 ++begin;
1035 }
1036 return begin;
1037 }
1038
1039 public nothrow I Unique<I>(I begin, I end) where I is ForwardIterator
1040 {
1041 return Unique(begin, end, EqualTo<I.ValueType>());
1042 }
1043 }