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 nothrow I Next<I>(I i, long n) where I is ForwardIterator
139 {
140 if (n < 0)
141 {
142 ThrowPreconditionViolationException();
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 void LinearInsert<I, R>(I first, I last, R r) where I is RandomAccessIterator and R is Relation and R.Domain is I.ValueType
549 {
550 I.ValueType val = *last;
551 if (r(val, *first))
552 {
553 CopyBackward(first, last, last + 1);
554 *first = val;
555 }
556 else
557 {
558 UnguardedLinearInsert(last, val, r);
559 }
560 }
561
562 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
563 {
564 if (begin == end)
565 {
566 return;
567 }
568 for (I i = begin + 1; i != end; ++i;)
569 {
570 LinearInsert(begin, i, r);
571 }
572 }
573
574 public inline void InsertionSort<I>(I begin, I end) where I is RandomAccessIterator and I.ValueType is TotallyOrdered
575 {
576 InsertionSort(begin, end, Less<I.ValueType>());
577 }
578
579 public const long insertionSortThreshold = 16;
580
581 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
582 {
583 while (end - begin > insertionSortThreshold)
584 {
585 I.ValueType pivot = Median(*begin, *(begin + (end - begin) / 2), *(end - 1), r);
586 I cut = UnguardedPartition(begin, end, pivot, r);
587 PartialQuickSort(cut, end, r);
588 end = cut;
589 }
590 }
591
592 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
593 {
594 if (begin != end)
595 {
596 PartialQuickSort(begin, end, r);
597 InsertionSort(begin, end, r);
598 }
599 }
600
601 public inline void Sort<I>(I begin, I end) where I is RandomAccessIterator and I.ValueType is TotallyOrdered
602 {
603 Sort(begin, end, Less<I.ValueType>());
604 }
605
606 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
607 {
608 Sort(c.Begin(), c.End(), r);
609 }
610
611 public inline void Sort<C>(C& c) where C is RandomAccessContainer and C.Iterator.ValueType is TotallyOrdered
612 {
613 Sort(c.Begin(), c.End());
614 }
615
616 public void Sort<C>(C& c) where C is ForwardContainer and C.Iterator.ValueType is TotallyOrdered
617 {
618 List<C.ValueType> list;
619 Copy(c.CBegin(), c.CEnd(), BackInserter(list));
620 Sort(list);
621 Copy(list.CBegin(), list.CEnd(), c.Begin());
622 }
623
624 public void Sort<C, R>(C& c, R r) where C is ForwardContainer and R is Relation and R.Domain is C.Iterator.ValueType
625 {
626 List<C.ValueType> list;
627 Copy(c.CBegin(), c.CEnd(), BackInserter(list));
628 Sort(list, r);
629 Copy(list.CBegin(), list.CEnd(), c.Begin());
630 }
631
632 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>
633 {
634 while (first1 != last1 && first2 != last2)
635 {
636 if (!r(*first1, *first2))
637 {
638 return false;
639 }
640 ++first1;
641 ++first2;
642 }
643 return first1 == last1 && first2 == last2;
644 }
645
646 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>
647 {
648 return Equal(first1, last1, first2, last2, EqualTo<I1.ValueType, I2.ValueType>());
649 }
650
651 public constexpr nothrow bool LexicographicalCompare<I1, I2, R>(I1 first1, I1 last1, I2 first2, I2 last2, R r)
652 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>
653 {
654 while (first1 != last1 && first2 != last2)
655 {
656 if (r(*first1, *first2))
657 {
658 return true;
659 }
660 if (r(*first2, *first1))
661 {
662 return false;
663 }
664 ++first1;
665 ++first2;
666 }
667 return first1 == last1 && first2 != last2;
668 }
669
670 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>
671 {
672 return LexicographicalCompare(first1, last1, first2, last2, Less<I1.ValueType, I2.ValueType>());
673 }
674
675 public constexpr nothrow I MinElement<I>(I first, I last) where I is ForwardIterator and I.ValueType is TotallyOrdered
676 {
677 if (first == last)
678 {
679 return first;
680 }
681 I minElementPos = first;
682 ++first;
683 while (first != last)
684 {
685 if (*first < *minElementPos)
686 {
687 minElementPos = first;
688 }
689 ++first;
690 }
691 return minElementPos;
692 }
693
694 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
695 {
696 if (first == last)
697 {
698 return first;
699 }
700 I minElementPos = first;
701 ++first;
702 while (first != last)
703 {
704 if (r(*first, *minElementPos))
705 {
706 minElementPos = first;
707 }
708 ++first;
709 }
710 return minElementPos;
711 }
712
713 public constexpr nothrow I MaxElement<I>(I first, I last) where I is ForwardIterator and I.ValueType is TotallyOrdered
714 {
715 if (first == last)
716 {
717 return first;
718 }
719 I maxElementPos = first;
720 ++first;
721 while (first != last)
722 {
723 if (*maxElementPos < *first)
724 {
725 maxElementPos = first;
726 }
727 ++first;
728 }
729 return maxElementPos;
730 }
731
732 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
733 {
734 if (first == last)
735 {
736 return first;
737 }
738 I maxElementPos = first;
739 ++first;
740 while (first != last)
741 {
742 if (r(*maxElementPos, *first))
743 {
744 maxElementPos = first;
745 }
746 ++first;
747 }
748 return maxElementPos;
749 }
750
751 public inline constexpr nothrow T Abs<T>(const T& x) where T is OrderedAdditiveGroup
752 {
753 if (x < T(0))
754 {
755 return -x;
756 }
757 return x;
758 }
759
760
761 public constexpr nothrow U Factorial<U>(U n) where U is UnsignedInteger
762 {
763 U f = 1u;
764 for (U u = 2u; u <= n; ++u;)
765 {
766 f = f * u;
767 }
768 return f;
769 }
770
771 public constexpr nothrow T Gcd<T>(T a, T b) where T is EuclideanSemiring
772 {
773 while (true)
774 {
775 if (b == T(0)) return a;
776 a = a % b;
777 if (a == T(0)) return b;
778 b = b % a;
779 }
780 }
781
782 public nothrow bool NextPermutation<I>(I begin, I end) where I is BidirectionalIterator and I.ValueType is LessThanComparable
783 {
784 if (begin == end)
785 {
786 return false;
787 }
788 I i = begin;
789 ++i;
790 if (i == end)
791 {
792 return false;
793 }
794 i = end;
795 --i;
796 while (true)
797 {
798 I ii = i;
799 --i;
800 if (*i < *ii)
801 {
802 I j = end;
803 --j;
804 while (*i >= *j)
805 {
806 --j;
807 }
808 Swap(*i, *j);
809 Reverse(ii, end);
810 return true;
811 }
812 if (i == begin)
813 {
814 Reverse(begin, end);
815 return false;
816 }
817 }
818 }
819
820 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
821 {
822 if (begin == end)
823 {
824 return false;
825 }
826 I i = begin;
827 ++i;
828 if (i == end)
829 {
830 return false;
831 }
832 i = end;
833 --i;
834 while (true)
835 {
836 I ii = i;
837 --i;
838 if (r(*i, *ii))
839 {
840 I j = end;
841 --j;
842 while (!r(*i, *j))
843 {
844 --j;
845 }
846 Swap(*i, *j);
847 Reverse(ii, end);
848 return true;
849 }
850 if (i == begin)
851 {
852 Reverse(begin, end);
853 return false;
854 }
855 }
856 }
857
858 public nothrow bool PrevPermutation<I>(I begin, I end) where I is BidirectionalIterator and I.ValueType is LessThanComparable
859 {
860 if (begin == end)
861 {
862 return false;
863 }
864 I i = begin;
865 ++i;
866 if (i == end)
867 {
868 return false;
869 }
870 i = end;
871 --i;
872 while (true)
873 {
874 I ii = i;
875 --i;
876 if (*ii < *i)
877 {
878 I j = end;
879 --j;
880 while (*j >= *i)
881 {
882 --j;
883 }
884 Swap(*i, *j);
885 Reverse(ii, end);
886 return true;
887 }
888 if (i == begin)
889 {
890 Reverse(begin, end);
891 return false;
892 }
893 }
894 }
895
896 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
897 {
898 if (begin == end)
899 {
900 return false;
901 }
902 I i = begin;
903 ++i;
904 if (i == end)
905 {
906 return false;
907 }
908 i = end;
909 --i;
910 while (true)
911 {
912 I ii = i;
913 --i;
914 if (r(*ii, *i))
915 {
916 I j = end;
917 --j;
918 while (!r(*j, *i))
919 {
920 --j;
921 }
922 Swap(*i, *j);
923 Reverse(ii, end);
924 return true;
925 }
926 if (i == begin)
927 {
928 Reverse(begin, end);
929 return false;
930 }
931 }
932 }
933
934 public inline nothrow uint RandomNumber(uint n)
935 {
936 return Random() % n;
937 }
938
939 public nothrow void RandomShuffle<I>(I begin, I end) where I is RandomAccessIterator
940 {
941 if (begin == end) return;
942 for (I i = begin + 1; i != end; ++i;)
943 {
944 long d = (i - begin) + 1;
945 long r = cast<long>(RandomNumber(cast<uint>(d)));
946 I j = begin + r;
947 Swap(*i, *j);
948 }
949 }
950 }