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