1 // =================================
   2 // Copyright (c) 2021 Seppo Laakko
   3 // Distributed under the MIT license
   4 // =================================
   5 
   6 using System.Concepts;
   7 
   8 namespace System
   9 {
  10     public inline constexpr nothrow const T& Min<T>(const T& leftconst 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& leftconst 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& leftT& 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 beginI 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 beginI 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<II> ReverseUntil<I>(I firstI middleI 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(firstlast);
  66     }
  67 
  68     public I Rotate<I>(I firstI middleI last) where I is BidirectionalIterator
  69     {
  70         Reverse(firstmiddle);
  71         Reverse(middlelast);
  72         Pair<II> p = ReverseUntil(firstmiddlelast);
  73         Reverse(p.firstp.second);
  74         if (middle == p.first) return p.second;
  75         return p.first;
  76     }
  77 
  78     public O Copy<IO>(I beginI endO to) where I is InputIterator and O is OutputIterator and CopyAssignable<O.ValueTypeI.ValueType>
  79     {
  80         while (begin != end)
  81         {
  82             *to = *begin;
  83             ++begin;
  84             ++to;
  85         }
  86         return to;
  87     }
  88 
  89     public O CopyBackward<IO>(I beginI endO to) where I is BidirectionalIterator and O is BidirectionalIterator and CopyAssignable<O.ValueTypeI.ValueType>
  90     {
  91         while (begin != end)
  92         {
  93             --to;
  94             --end;
  95             *to = *end;
  96         }
  97         return to;
  98     }
  99 
 100     public O Move<IO>(I beginI endO 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<IO>(I beginI endO 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 firstI 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 firstI last) where I is RandomAccessIterator
 134     {
 135         return last - first;
 136     }
 137 
 138     public constexpr I Next<I>(I ilong 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 ilong n) where I is RandomAccessIterator
 153     {
 154         return i + n;
 155     }
 156 
 157     public constexpr nothrow I LowerBound<IT>(I firstI lastconst T& value) where I is ForwardIterator and TotallyOrdered<TI.ValueType>
 158     {
 159         long len = Distance(firstlast);
 160         while (len > 0)
 161         {
 162             long half = len >> 1;
 163             I middle = Next(firsthalf);
 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<ITR>(I firstI lastconst T& valueR 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(firstlast);
 181         while (len > 0)
 182         {
 183             long half = len >> 1;
 184             I middle = Next(firsthalf);
 185             if (r(*middlevalue))
 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<IT>(I firstI lastconst T& value) where I is ForwardIterator and TotallyOrdered<TI.ValueType>
 200     {
 201         long len = Distance(firstlast);
 202         while (len > 0)
 203         {
 204             long half = len >> 1;
 205             I middle = Next(firsthalf);
 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<ITR>(I firstI lastconst T& valueR 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(firstlast);
 223         while (len > 0)
 224         {
 225             long half = len >> 1;
 226             I middle = Next(firsthalf);
 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<II> EqualRange<IT>(I firstI lastconst T& value) where I is ForwardIterator and TotallyOrdered<TI.ValueType>
 242     {
 243         long len = Distance(firstlast);
 244         while (len > 0)
 245         {
 246             long half = len >> 1;
 247             I middle = Next(firsthalf);
 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(firstmiddlevalue);
 261                 I end = Next(firstlen);
 262                 ++middle;
 263                 I right = UpperBound(middleendvalue);
 264                 return Pair<II>(leftright);
 265             }
 266         }
 267         return Pair<II>(firstfirst);
 268     }
 269 
 270     public constexpr Pair<II> EqualRange<ITR>(I firstI lastconst T& valueR 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(firstlast);
 273         while (len > 0)
 274         {
 275             long half = len >> 1;
 276             I middle = Next(firsthalf);
 277             if (r(*middlevalue))
 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(firstmiddlevaluer);
 290                 I end = Next(firstlen);
 291                 ++middle;
 292                 I right = UpperBound(middleendvaluer);
 293                 return Pair<II>(leftright);
 294             }
 295         }
 296         return Pair<II>(firstfirst);
 297     }
 298 
 299     public constexpr nothrow I Find<IT>(I beginI endconst T& value) where I is InputIterator and T is Semiregular and EqualityComparable<TI.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<IP>(I beginI endP 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<IT>(I beginI endconst T& value) where I is InputIterator and T is Semiregular and EqualityComparable<TI.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<IP>(I beginI endP 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<IOP>(I beginI endO resultP 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<IP>(I beginI endP p) where I is ForwardIterator and P is UnaryPredicate and P.ArgumentType is I.ValueType
 368     {
 369         begin = Find(beginendp);
 370         if (begin == end)
 371         {
 372             return begin;
 373         }
 374         else
 375         {
 376             I i = begin;
 377             ++i;
 378             return RemoveCopy(iendbeginp);
 379         }
 380     }
 381 
 382     public O RemoveCopy<IOT>(I beginI endO resultconst T& value)
 383         where T is Semiregular and I is InputIterator and O is OutputIterator and O.ValueType is I.ValueType and EqualityComparable<TI.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<IT>(I beginI endconst T& value) where I is ForwardIterator and T is Semiregular and EqualityComparable<TI.ValueType>
 398     {
 399         begin = Find(beginendvalue);
 400         if (begin == end)
 401         {
 402             return begin;
 403         }
 404         else
 405         {
 406             I i = begin;
 407             ++i;
 408             return RemoveCopy(iendbeginvalue);
 409         }
 410     }
 411 
 412     public nothrow void Fill<IT>(I beginI endconst 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<ITOp>(I beginI endT initOp 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<IF>(I beginI endF 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<IOF>(I beginI endO toF fun)
 442         where I is InputIterator and O is OutputIterator and F is UnaryFunction and F.ArgumentType is I.ValueType and CopyAssignable<O.ValueTypeF.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<I1I2OF>(I1 begin1I1 end1I2 begin2O toF 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.ValueTypeF.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<TR>(const T& aconst T& bR r) where T is Semiregular and R is Relation and R.Domain is T
 468     {
 469         if (r(ba)) return b;
 470         return a;
 471     }
 472 
 473     public inline nothrow const T& Select_1_2<TR>(const T& aconst T& bR r) where T is Semiregular and R is Relation and R.Domain is T
 474     {
 475         if (r(ba)) return a;
 476         return b;
 477     }
 478 
 479     public inline nothrow const T& Select_0_3<TR>(const T& aconst T& bconst T& cR r) where T is Semiregular and R is Relation and R.Domain is T
 480     {
 481         return Select_0_2(Select_0_2(abr)cr);
 482     }
 483 
 484     public inline nothrow const T& Select_2_3<TR>(const T& aconst T& bconst T& cR r) where T is Semiregular and R is Relation and R.Domain is T
 485     {
 486         return Select_1_2(Select_1_2(abr)cr);
 487     }
 488 
 489     public inline nothrow const T& Select_1_3_ab<TR>(const T& aconst T& bconst T& cR r) where T is Semiregular and R is Relation and R.Domain is T
 490     {
 491         if (!r(cb)) return b;
 492         return Select_1_2(acr);
 493     }
 494 
 495     public inline nothrow const T& Select_1_3<TR>(const T& aconst T& bconst T& cR r) where T is Semiregular and R is Relation and R.Domain is T
 496     {
 497         if (r(ba)) return Select_1_3_ab(bacr);
 498         return Select_1_3_ab(abcr);
 499     }
 500 
 501     public nothrow const T& Median<TR>(const T& aconst T& bconst T& cR r) where T is Semiregular and R is Relation and R.Domain is T
 502     {
 503         return Select_1_3(abcr);
 504     }
 505 
 506     public nothrow const T& Median<T>(const T& aconst T& bconst T& c) where T is TotallyOrdered
 507     {
 508         return Median(abcLess<T>());
 509     }
 510 
 511     public nothrow I UnguardedPartition<ITR>(I beginI endconst T& pivotR 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(*beginpivot))
 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         // dummy return to keep compiler happy...
 532         return begin;
 533     }
 534 
 535     public nothrow void UnguardedLinearInsert<ITR>(I lastconst T& valR 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<ITR>(I lastT&& valR 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<IR>(I firstI lastR 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(firstlastlast + 1);
 568             *first = val;
 569         }
 570         else
 571         {
 572             UnguardedLinearInsert(lastvalr);
 573         }
 574     }
 575 
 576     public void LinearInsert<IR>(I firstI lastR 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(firstlastlast + 1);
 582             *first = Rvalue(val);
 583         }
 584         else
 585         {
 586             UnguardedLinearInsert(lastRvalue(val)r);
 587         }
 588     }
 589 
 590     public void InsertionSort<IR>(I beginI endR 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(beginir);
 599         }
 600     }
 601 
 602     public inline void InsertionSort<I>(I beginI end) where I is RandomAccessIterator and I.ValueType is TotallyOrdered
 603     {
 604         InsertionSort(beginendLess<I.ValueType>());
 605     }
 606 
 607     public const long insertionSortThreshold = 16;
 608 
 609     public void PartialQuickSort<IR>(I beginI endR 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(beginendpivotr);
 615             PartialQuickSort(cutendr);
 616             end = cut;
 617         }
 618     }
 619 
 620     public void Sort<IR>(I beginI endR r) where I is RandomAccessIterator and R is Relation and R.Domain is I.ValueType
 621     {
 622         if (begin != end)
 623         {
 624             PartialQuickSort(beginendr);
 625             InsertionSort(beginendr);
 626         }
 627     }
 628 
 629     public inline void Sort<I>(I beginI end) where I is RandomAccessIterator and I.ValueType is TotallyOrdered
 630     {
 631         Sort(beginendLess<I.ValueType>());
 632     }
 633 
 634     public inline void Sort<CR>(C& cR 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<CR>(C& cR 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(listr);
 657         Copy(list.CBegin()list.CEnd()c.Begin());
 658     }
 659 
 660     public constexpr nothrow bool Equal<I1I2R>(I1 first1I1 last1I2 first2I2 last2R r) where I1 is InputIterator and I2 is InputIterator and Relation<RI1.ValueTypeI2.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<I1I2>(I1 first1I1 last1I2 first2I2 last2) where I1 is InputIterator and I2 is InputIterator and EqualityComparable<I1.ValueTypeI2.ValueType>
 675     {
 676         return Equal(first1last1first2last2EqualTo<I1.ValueTypeI2.ValueType>());
 677     }
 678 
 679     public constexpr nothrow bool LexicographicalCompare<I1I2R>(I1 first1I1 last1I2 first2I2 last2R r)
 680         where I1 is InputIterator and I2 is InputIterator and Same<I1.ValueTypeI2.ValueType> and Relation<RI1.ValueTypeI2.ValueType> and Relation<RI2.ValueTypeI1.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<I1I2>(I1 first1I1 last1I2 first2I2 last2) where I1 is InputIterator and I2 is InputIterator and LessThanComparable<I1.ValueTypeI2.ValueType>
 699     {
 700         return LexicographicalCompare(first1last1first2last2Less<I1.ValueTypeI2.ValueType>());
 701     }
 702 
 703     public constexpr nothrow I MinElement<I>(I firstI 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<IR>(I firstI lastR 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 firstI 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<IR>(I firstI lastR 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     // naive implementation...
 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 aT 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 beginI 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(iiend);
 838                 return true;
 839             }
 840             if (i == begin)
 841             {
 842                 Reverse(beginend);
 843                 return false;
 844             }
 845         }
 846     }
 847 
 848     public nothrow bool NextPermutation<IR>(I beginI endR 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(iiend);
 876                 return true;
 877             }
 878             if (i == begin)
 879             {
 880                 Reverse(beginend);
 881                 return false;
 882             }
 883         }
 884     }
 885 
 886     public nothrow bool PrevPermutation<I>(I beginI 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(iiend);
 914                 return true;
 915             }
 916             if (i == begin)
 917             {
 918                 Reverse(beginend);
 919                 return false;
 920             }
 921         }
 922     }
 923 
 924     public nothrow bool PrevPermutation<IR>(I beginI endR 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(iiend);
 952                 return true;
 953             }
 954             if (i == begin)
 955             {
 956                 Reverse(beginend);
 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 beginI 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<IR>(I beginI endR 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 beginI end) where I is ForwardIterator
1014     {
1015         return AdjacentFind(beginendEqualTo<I.ValueType>());
1016     }
1017 
1018     public nothrow I Unique<IR>(I beginI endR r) where I is ForwardIterator and R is Relation and R.Domain is I.ValueType
1019     {
1020         begin = AdjacentFind(beginendr);
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 beginI end) where I is ForwardIterator
1040     {
1041         return Unique(beginendEqualTo<I.ValueType>());
1042     }
1043 }