mcs/class/System.Core/System.Linq/Enumerable.cs

   1 //
   2 // Enumerable.cs
   3 //
   4 // Authors:
   5 //  Marek Safar (marek.safar@gmail.com)
   6 //  Antonello Provenzano  <antonello@deveel.com>
   7 //  Alejandro Serrano "Serras" (trupill@yahoo.es)
   8 //  Jb Evain (jbevain@novell.com)
   9 //
  10 // Copyright (C) 2007 Novell, Inc (http://www.novell.com)
  11 //
  12 // Permission is hereby granted, free of charge, to any person obtaining
  13 // a copy of this software and associated documentation files (the
  14 // "Software"), to deal in the Software without restriction, including
  15 // without limitation the rights to use, copy, modify, merge, publish,
  16 // distribute, sublicense, and/or sell copies of the Software, and to
  17 // permit persons to whom the Software is furnished to do so, subject to
  18 // the following conditions:
  19 //
  20 // The above copyright notice and this permission notice shall be
  21 // included in all copies or substantial portions of the Software.
  22 //
  23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  24 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  25 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  26 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  27 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  28 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  29 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  30 //
  31
  32 // precious: http://www.hookedonlinq.com
  33
  34 using System;
  35 using System.Collections;
  36 using System.Collections.Generic;
  37 using System.Collections.ObjectModel;
  38
  39 namespace System.Linq
  40 {
  41         public static class Enumerable
  42         {
  43                 enum Fallback {
  44                         Default,
  45                         Throw
  46                 }
  47
  48 #if !FULL_AOT_RUNTIME
  49                 static class PredicateOf<T> {
  50                         public static readonly Func<T, bool> Always = (t) => true;
  51                 }
  52 #endif
  53
  54                 static class Function<T> {
  55                         public static readonly Func<T, T> Identity = (t) => t;
  56                 }
  57
  58                 static class EmptyOf<T> {
  59                         public static readonly T[] Instance = new T [0];
  60                 }
  61
  62                 static class ReadOnlyCollectionOf<T> {
  63                         public static readonly ReadOnlyCollection<T> Empty = new ReadOnlyCollection<T> (EmptyOf<T>.Instance);
  64                 }
  65
  66                 #region Aggregate
  67
  68                 public static TSource Aggregate<TSource> (this IEnumerable<TSource> source, Func<TSource, TSource, TSource> func)
  69                 {
  70                         Check.SourceAndFunc (source, func);
  71
  72                         // custom foreach so that we can efficiently throw an exception
  73                         // if zero elements and treat the first element differently
  74                         using (var enumerator = source.GetEnumerator ()) {
  75                                 if (!enumerator.MoveNext ())
  76                                         throw EmptySequence ();
  77
  78                                 TSource folded = enumerator.Current;
  79                                 while (enumerator.MoveNext ())
  80                                         folded = func (folded, enumerator.Current);
  81                                 return folded;
  82                         }
  83                 }
  84
  85                 public static TAccumulate Aggregate<TSource, TAccumulate> (this IEnumerable<TSource> source,
  86                         TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func)
  87                 {
  88                         Check.SourceAndFunc (source, func);
  89
  90                         TAccumulate folded = seed;
  91                         foreach (TSource element in source)
  92                                 folded = func (folded, element);
  93
  94                         return folded;
  95                 }
  96
  97                 public static TResult Aggregate<TSource, TAccumulate, TResult> (this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func, Func<TAccumulate, TResult> resultSelector)
  98                 {
  99                         Check.SourceAndFunc (source, func);
 100                         if (resultSelector == null)
 101                                 throw new ArgumentNullException ("resultSelector");
 102
 103                         var result = seed;
 104                         foreach (var e in source)
 105                                 result = func (result, e);
 106
 107                         return resultSelector (result);
 108                 }
 109
 110                 #endregion
 111
 112                 #region All
 113
 114                 public static bool All<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
 115                 {
 116                         Check.SourceAndPredicate (source, predicate);
 117
 118                         foreach (var element in source)
 119                                 if (!predicate (element))
 120                                         return false;
 121
 122                         return true;
 123                 }
 124
 125                 #endregion
 126
 127                 #region Any
 128
 129                 public static bool Any<TSource> (this IEnumerable<TSource> source)
 130                 {
 131                         Check.Source (source);
 132
 133                         var collection = source as ICollection<TSource>;
 134                         if (collection != null)
 135                                 return collection.Count > 0;
 136
 137                         using (var enumerator = source.GetEnumerator ())
 138                                 return enumerator.MoveNext ();
 139                 }
 140
 141                 public static bool Any<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
 142                 {
 143                         Check.SourceAndPredicate (source, predicate);
 144
 145                         foreach (TSource element in source)
 146                                 if (predicate (element))
 147                                         return true;
 148
 149                         return false;
 150                 }
 151
 152                 #endregion
 153
 154                 #region AsEnumerable
 155
 156                 public static IEnumerable<TSource> AsEnumerable<TSource> (this IEnumerable<TSource> source)
 157                 {
 158                         return source;
 159                 }
 160
 161                 #endregion
 162
 163                 #region Average
 164
 165                 public static double Average (this IEnumerable<int> source)
 166                 {
 167                         Check.Source (source);
 168
 169                         long total = 0;
 170                         int count = 0;
 171                         foreach (var element in source){
 172                                 total = checked (total + element);
 173                                 count++;
 174                         }
 175                         if (count == 0)
 176                                 throw EmptySequence ();
 177                         return total / (double) count;
 178                 }
 179
 180                 public static double Average (this IEnumerable<long> source)
 181                 {
 182                         Check.Source (source);
 183
 184                         long total = 0;
 185                         long count = 0;
 186                         foreach (var element in source){
 187                                 total += element;
 188                                 count++;
 189                         }
 190                         if (count == 0)
 191                                 throw EmptySequence ();
 192                         return total / (double) count;
 193                 }
 194
 195                 public static double Average (this IEnumerable<double> source)
 196                 {
 197                         Check.Source (source);
 198
 199                         double total = 0;
 200                         long count = 0;
 201                         foreach (var element in source){
 202                                 total += element;
 203                                 count++;
 204                         }
 205                         if (count == 0)
 206                                 throw EmptySequence ();
 207                         return total / count;
 208                 }
 209
 210                 public static float Average (this IEnumerable<float> source)
 211                 {
 212                         Check.Source (source);
 213
 214                         float total = 0;
 215                         long count = 0;
 216                         foreach (var element in source){
 217                                 total += element;
 218                                 count++;
 219                         }
 220                         if (count == 0)
 221                                 throw EmptySequence ();
 222                         return total / count;
 223                 }
 224
 225                 public static decimal Average (this IEnumerable<decimal> source)
 226                 {
 227                         Check.Source (source);
 228
 229                         decimal total = 0;
 230                         long count = 0;
 231                         foreach (var element in source){
 232                                 total += element;
 233                                 count++;
 234                         }
 235                         if (count == 0)
 236                                 throw EmptySequence ();
 237                         return total / count;
 238                 }
 239
 240                 static TResult? AverageNullable<TElement, TAggregate, TResult> (this IEnumerable<TElement?> source,
 241                         Func<TAggregate, TElement, TAggregate> func, Func<TAggregate, long, TResult> result)
 242                         where TElement : struct
 243                         where TAggregate : struct
 244                         where TResult : struct
 245                 {
 246                         Check.Source (source);
 247
 248                         var total = default (TAggregate);
 249                         long counter = 0;
 250                         foreach (var element in source) {
 251                                 if (!element.HasValue)
 252                                         continue;
 253
 254                                 total = func (total, element.Value);
 255                                 counter++;
 256                         }
 257
 258                         if (counter == 0)
 259                                 return null;
 260
 261                         return new TResult? (result (total, counter));
 262                 }
 263
 264                 public static double? Average (this IEnumerable<int?> source)
 265                 {
 266                         Check.Source (source);
 267
 268                         long total = 0;
 269                         long counter = 0;
 270
 271                         foreach (var element in source) {
 272                                 if (!element.HasValue)
 273                                         continue;
 274
 275                                 total = total + element.Value;
 276                                 counter++;
 277                         }
 278
 279                         if (counter == 0)
 280                                 return null;
 281
 282                         return new double? (total / (double) counter);
 283                 }
 284
 285                 public static double? Average (this IEnumerable<long?> source)
 286                 {
 287                         Check.Source (source);
 288
 289                         long total = 0;
 290                         long counter = 0;
 291
 292                         foreach (var element in source) {
 293                                 if (!element.HasValue)
 294                                         continue;
 295
 296                                 total = checked (total + element.Value);
 297                                 counter++;
 298                         }
 299
 300                         if (counter == 0)
 301                                 return null;
 302
 303                         return new double? (total / (double) counter);
 304
 305                 }
 306
 307                 public static double? Average (this IEnumerable<double?> source)
 308                 {
 309                         Check.Source (source);
 310
 311                         double total = 0;
 312                         long counter = 0;
 313
 314                         foreach (var element in source) {
 315                                 if (!element.HasValue)
 316                                         continue;
 317
 318                                 total = total + element.Value;
 319                                 counter++;
 320                         }
 321
 322                         if (counter == 0)
 323                                 return null;
 324
 325                         return new double? (total / counter);
 326
 327                 }
 328
 329                 public static decimal? Average (this IEnumerable<decimal?> source)
 330                 {
 331                         Check.Source (source);
 332
 333                         decimal total = 0;
 334                         long counter = 0;
 335
 336                         foreach (var element in source) {
 337                                 if (!element.HasValue)
 338                                         continue;
 339
 340                                 total = total + element.Value;
 341                                 counter++;
 342                         }
 343
 344                         if (counter == 0)
 345                                 return null;
 346
 347                         return new decimal? (total / counter);
 348
 349                 }
 350
 351                 public static float? Average (this IEnumerable<float?> source)
 352                 {
 353                         Check.Source (source);
 354
 355                         float total = 0;
 356                         long counter = 0;
 357
 358                         foreach (var element in source) {
 359                                 if (!element.HasValue)
 360                                         continue;
 361
 362                                 total = total + element.Value;
 363                                 counter++;
 364                         }
 365
 366                         if (counter == 0)
 367                                 return null;
 368
 369                         return new float? (total / counter);
 370
 371                 }
 372
 373                 public static double Average<TSource> (this IEnumerable<TSource> source, Func<TSource, int> selector)
 374                 {
 375                         Check.SourceAndSelector (source, selector);
 376
 377                         long total = 0;
 378                         long count = 0;
 379                         foreach (var element in source){
 380                                 total += selector (element);
 381                                 count++;
 382                         }
 383                         if (count == 0)
 384                                 throw EmptySequence ();
 385                         return total / (double) count;
 386                 }
 387
 388                 public static double? Average<TSource> (this IEnumerable<TSource> source, Func<TSource, int?> selector)
 389                 {
 390                         Check.SourceAndSelector (source, selector);
 391
 392                         long total = 0;
 393                         long counter = 0;
 394
 395                         foreach (var element in source) {
 396                                 var value = selector (element);
 397                                 if (!value.HasValue)
 398                                         continue;
 399
 400                                 total = total + value.Value;
 401                                 counter++;
 402                         }
 403
 404                         if (counter == 0)
 405                                 return null;
 406
 407                         return new double? (total / (double) counter);
 408                 }
 409
 410                 public static double Average<TSource> (this IEnumerable<TSource> source, Func<TSource, long> selector)
 411                 {
 412                         Check.SourceAndSelector (source, selector);
 413
 414                         long total = 0;
 415                         long count = 0;
 416                         foreach (var element in source){
 417                                 total = checked (total + selector (element));
 418                                 count++;
 419                         }
 420                         if (count == 0)
 421                                 throw EmptySequence ();
 422                         return total / (double) count;
 423
 424                 }
 425
 426                 public static double? Average<TSource> (this IEnumerable<TSource> source, Func<TSource, long?> selector)
 427                 {
 428                         Check.SourceAndSelector (source, selector);
 429
 430                         long total = 0;
 431                         long counter = 0;
 432
 433                         foreach (var element in source) {
 434                                 var value = selector (element);
 435                                 if (!value.HasValue)
 436                                         continue;
 437
 438                                 total = checked (total + value.Value);
 439                                 counter++;
 440                         }
 441
 442                         if (counter == 0)
 443                                 return null;
 444
 445                         return new double? (total / (double) counter);
 446                 }
 447
 448                 public static double Average<TSource> (this IEnumerable<TSource> source, Func<TSource, double> selector)
 449                 {
 450                         Check.SourceAndSelector (source, selector);
 451
 452                         double total = 0;
 453                         long count = 0;
 454                         foreach (var element in source){
 455                                 total += selector (element);
 456                                 count++;
 457                         }
 458                         if (count == 0)
 459                                 throw EmptySequence ();
 460                         return total / count;
 461
 462                 }
 463
 464                 public static double? Average<TSource> (this IEnumerable<TSource> source, Func<TSource, double?> selector)
 465                 {
 466                         Check.SourceAndSelector (source, selector);
 467
 468                         double total = 0;
 469                         long counter = 0;
 470
 471                         foreach (var element in source) {
 472                                 var value = selector (element);
 473                                 if (!value.HasValue)
 474                                         continue;
 475
 476                                 total = total + value.Value;
 477                                 counter++;
 478                         }
 479
 480                         if (counter == 0)
 481                                 return null;
 482
 483                         return new double? (total / counter);
 484
 485                 }
 486
 487                 public static float Average<TSource> (this IEnumerable<TSource> source, Func<TSource, float> selector)
 488                 {
 489                         Check.SourceAndSelector (source, selector);
 490
 491                         float total = 0;
 492                         long count = 0;
 493                         foreach (var element in source){
 494                                 total += selector (element);
 495                                 count++;
 496                         }
 497                         if (count == 0)
 498                                 throw EmptySequence ();
 499                         return total / count;
 500                 }
 501
 502                 public static float? Average<TSource> (this IEnumerable<TSource> source, Func<TSource, float?> selector)
 503                 {
 504                         Check.SourceAndSelector (source, selector);
 505
 506                         float total = 0;
 507                         long counter = 0;
 508
 509                         foreach (var element in source) {
 510                                 var value = selector (element);
 511                                 if (!value.HasValue)
 512                                         continue;
 513
 514                                 total = total + value.Value;
 515                                 counter++;
 516                         }
 517
 518                         if (counter == 0)
 519                                 return null;
 520
 521                         return new float? (total / counter);
 522                 }
 523
 524                 public static decimal Average<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal> selector)
 525                 {
 526                         Check.SourceAndSelector (source, selector);
 527
 528                         decimal total = 0;
 529                         long count = 0;
 530                         foreach (var element in source){
 531                                 total += selector (element);
 532                                 count++;
 533                         }
 534                         if (count == 0)
 535                                 throw EmptySequence ();
 536                         return total / count;
 537                 }
 538
 539                 public static decimal? Average<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal?> selector)
 540                 {
 541                         Check.SourceAndSelector (source, selector);
 542
 543                         decimal total = 0;
 544                         long counter = 0;
 545
 546                         foreach (var element in source) {
 547                                 var value = selector (element);
 548                                 if (!value.HasValue)
 549                                         continue;
 550
 551                                 total = total + value.Value;
 552                                 counter++;
 553                         }
 554
 555                         if (counter == 0)
 556                                 return null;
 557
 558                         return new decimal? (total / counter);
 559                 }
 560
 561                 #endregion
 562
 563                 #region Cast
 564
 565                 public static IEnumerable<TResult> Cast<TResult> (this IEnumerable source)
 566                 {
 567                         Check.Source (source);
 568
 569                         var actual = source as IEnumerable<TResult>;
 570                         if (actual != null)
 571                                 return actual;
 572
 573                         return CreateCastIterator<TResult> (source);
 574                 }
 575
 576                 static IEnumerable<TResult> CreateCastIterator<TResult> (IEnumerable source)
 577                 {
 578                         foreach (TResult element in source)
 579                                 yield return element;
 580                 }
 581
 582                 #endregion
 583
 584                 #region Concat
 585
 586                 public static IEnumerable<TSource> Concat<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
 587                 {
 588                         Check.FirstAndSecond (first, second);
 589
 590                         return CreateConcatIterator (first, second);
 591                 }
 592
 593                 static IEnumerable<TSource> CreateConcatIterator<TSource> (IEnumerable<TSource> first, IEnumerable<TSource> second)
 594                 {
 595                         foreach (TSource element in first)
 596                                 yield return element;
 597                         foreach (TSource element in second)
 598                                 yield return element;
 599                 }
 600
 601                 #endregion
 602
 603                 #region Contains
 604
 605                 public static bool Contains<TSource> (this IEnumerable<TSource> source, TSource value)
 606                 {
 607                         var collection = source as ICollection<TSource>;
 608                         if (collection != null)
 609                                 return collection.Contains (value);
 610
 611                         return Contains<TSource> (source, value, null);
 612                 }
 613
 614                 public static bool Contains<TSource> (this IEnumerable<TSource> source, TSource value, IEqualityComparer<TSource> comparer)
 615                 {
 616                         Check.Source (source);
 617
 618                         if (comparer == null)
 619                                 comparer = EqualityComparer<TSource>.Default;
 620
 621                         foreach (var element in source)
 622                                 if (comparer.Equals (element, value))
 623                                         return true;
 624
 625                         return false;
 626                 }
 627                 #endregion
 628
 629                 #region Count
 630
 631                 public static int Count<TSource> (this IEnumerable<TSource> source)
 632                 {
 633                         Check.Source (source);
 634
 635                         var collection = source as ICollection<TSource>;
 636                         if (collection != null)
 637                                 return collection.Count;
 638
 639                         int counter = 0;
 640                         using (var enumerator = source.GetEnumerator ())
 641                                 while (enumerator.MoveNext ())
 642                                         checked { counter++; }
 643
 644                         return counter;
 645                 }
 646
 647                 public static int Count<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
 648                 {
 649                         Check.SourceAndSelector (source, predicate);
 650
 651                         int counter = 0;
 652                         foreach (var element in source)
 653                                 if (predicate (element))
 654                                         checked { counter++; }
 655
 656                         return counter;
 657                 }
 658
 659                 #endregion
 660
 661                 #region DefaultIfEmpty
 662
 663                 public static IEnumerable<TSource> DefaultIfEmpty<TSource> (this IEnumerable<TSource> source)
 664                 {
 665                         return DefaultIfEmpty (source, default (TSource));
 666                 }
 667
 668                 public static IEnumerable<TSource> DefaultIfEmpty<TSource> (this IEnumerable<TSource> source, TSource defaultValue)
 669                 {
 670                         Check.Source (source);
 671
 672                         return CreateDefaultIfEmptyIterator (source, defaultValue);
 673                 }
 674
 675                 static IEnumerable<TSource> CreateDefaultIfEmptyIterator<TSource> (IEnumerable<TSource> source, TSource defaultValue)
 676                 {
 677                         bool empty = true;
 678                         foreach (TSource item in source) {
 679                                 empty = false;
 680                                 yield return item;
 681                         }
 682
 683                         if (empty)
 684                                 yield return defaultValue;
 685                 }
 686
 687                 #endregion
 688
 689                 #region Distinct
 690
 691                 public static IEnumerable<TSource> Distinct<TSource> (this IEnumerable<TSource> source)
 692                 {
 693                         return Distinct<TSource> (source, null);
 694                 }
 695
 696                 public static IEnumerable<TSource> Distinct<TSource> (this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
 697                 {
 698                         Check.Source (source);
 699
 700                         if (comparer == null)
 701                                 comparer = EqualityComparer<TSource>.Default;
 702
 703                         return CreateDistinctIterator (source, comparer);
 704                 }
 705
 706                 static IEnumerable<TSource> CreateDistinctIterator<TSource> (IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
 707                 {
 708                         var items = new HashSet<TSource> (comparer);
 709                         foreach (var element in source) {
 710                                 if (! items.Contains (element)) {
 711                                         items.Add (element);
 712                                         yield return element;
 713                                 }
 714                         }
 715                 }
 716
 717                 #endregion
 718
 719                 #region ElementAt
 720
 721                 static TSource ElementAt<TSource> (this IEnumerable<TSource> source, int index, Fallback fallback)
 722                 {
 723                         long counter = 0L;
 724
 725                         foreach (var element in source) {
 726                                 if (index == counter++)
 727                                         return element;
 728                         }
 729
 730                         if (fallback == Fallback.Throw)
 731                                 throw new ArgumentOutOfRangeException ();
 732
 733                         return default (TSource);
 734                 }
 735
 736                 public static TSource ElementAt<TSource> (this IEnumerable<TSource> source, int index)
 737                 {
 738                         Check.Source (source);
 739
 740                         if (index < 0)
 741                                 throw new ArgumentOutOfRangeException ();
 742
 743                         var list = source as IList<TSource>;
 744                         if (list != null)
 745                                 return list [index];
 746
 747 #if NET_4_5
 748                         var readOnlyList = source as IReadOnlyList<TSource>;
 749                         if (readOnlyList != null)
 750                                 return readOnlyList[index];
 751 #endif
 752
 753                         return source.ElementAt (index, Fallback.Throw);
 754                 }
 755
 756                 #endregion
 757
 758                 #region ElementAtOrDefault
 759
 760                 public static TSource ElementAtOrDefault<TSource> (this IEnumerable<TSource> source, int index)
 761                 {
 762                         Check.Source (source);
 763
 764                         if (index < 0)
 765                                 return default (TSource);
 766
 767                         var list = source as IList<TSource>;
 768                         if (list != null)
 769                                 return index < list.Count ? list [index] : default (TSource);
 770
 771 #if NET_4_5
 772                         var readOnlyList = source as IReadOnlyList<TSource>;
 773                         if (readOnlyList != null)
 774                                 return index < readOnlyList.Count ? readOnlyList [index] : default (TSource);
 775 #endif
 776
 777                         return source.ElementAt (index, Fallback.Default);
 778                 }
 779
 780                 #endregion
 781
 782                 #region Empty
 783
 784                 public static IEnumerable<TResult> Empty<TResult> ()
 785                 {
 786                         return EmptyOf<TResult>.Instance;
 787                 }
 788
 789                 #endregion
 790
 791                 #region Except
 792
 793                 public static IEnumerable<TSource> Except<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
 794                 {
 795                         return Except (first, second, null);
 796                 }
 797
 798                 public static IEnumerable<TSource> Except<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 799                 {
 800                         Check.FirstAndSecond (first, second);
 801
 802                         if (comparer == null)
 803                                 comparer = EqualityComparer<TSource>.Default;
 804
 805                         return CreateExceptIterator (first, second, comparer);
 806                 }
 807
 808                 static IEnumerable<TSource> CreateExceptIterator<TSource> (IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 809                 {
 810                         var items = new HashSet<TSource> (second, comparer);
 811                         foreach (var element in first) {
 812                                 if (items.Add (element))
 813                                         yield return element;
 814                         }
 815                 }
 816
 817                 #endregion
 818
 819                 #region First
 820
 821                 static TSource First<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate, Fallback fallback)
 822                 {
 823                         foreach (var element in source)
 824                                 if (predicate (element))
 825                                         return element;
 826
 827                         if (fallback == Fallback.Throw)
 828                                 throw NoMatchingElement ();
 829
 830                         return default (TSource);
 831                 }
 832
 833                 public static TSource First<TSource> (this IEnumerable<TSource> source)
 834                 {
 835                         Check.Source (source);
 836
 837                         var list = source as IList<TSource>;
 838                         if (list != null) {
 839                                 if (list.Count != 0)
 840                                         return list [0];
 841                         } else {
 842                                 using (var enumerator = source.GetEnumerator ()) {
 843                                         if (enumerator.MoveNext ())
 844                                                 return enumerator.Current;
 845                                 }
 846                         }
 847
 848                         throw EmptySequence ();
 849                 }
 850
 851                 public static TSource First<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
 852                 {
 853                         Check.SourceAndPredicate (source, predicate);
 854
 855                         return source.First (predicate, Fallback.Throw);
 856                 }
 857
 858                 #endregion
 859
 860                 #region FirstOrDefault
 861
 862                 public static TSource FirstOrDefault<TSource> (this IEnumerable<TSource> source)
 863                 {
 864                         Check.Source (source);
 865
 866 #if !FULL_AOT_RUNTIME
 867                         return source.First (PredicateOf<TSource>.Always, Fallback.Default);
 868 #else
 869                         // inline the code to reduce dependency o generic causing AOT errors on device (e.g. bug #3285)
 870                         foreach (var element in source)
 871                                 return element;
 872
 873                         return default (TSource);
 874 #endif
 875                 }
 876
 877                 public static TSource FirstOrDefault<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
 878                 {
 879                         Check.SourceAndPredicate (source, predicate);
 880
 881                         return source.First (predicate, Fallback.Default);
 882                 }
 883
 884                 #endregion
 885
 886                 #region GroupBy
 887
 888                 private static List<T> ContainsGroup<K, T> (
 889                                 Dictionary<K, List<T>> items, K key, IEqualityComparer<K> comparer)
 890                 {
 891                         IEqualityComparer<K> comparerInUse = (comparer ?? EqualityComparer<K>.Default);
 892                         foreach (KeyValuePair<K, List<T>> value in items) {
 893                                 if (comparerInUse.Equals (value.Key, key))
 894                                         return value.Value;
 895                         }
 896                         return null;
 897                 }
 898
 899                 public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey> (this IEnumerable<TSource> source,
 900                         Func<TSource, TKey> keySelector)
 901                 {
 902                         return GroupBy<TSource, TKey> (source, keySelector, null);
 903                 }
 904
 905                 public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey> (this IEnumerable<TSource> source,
 906                         Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
 907                 {
 908                         Check.SourceAndKeySelector (source, keySelector);
 909
 910                         return CreateGroupByIterator (source, keySelector, comparer);
 911                 }
 912
 913                 static IEnumerable<IGrouping<TKey, TSource>> CreateGroupByIterator<TSource, TKey> (this IEnumerable<TSource> source,
 914                         Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
 915                 {
 916                         var groups = new Dictionary<TKey, List<TSource>> ();
 917                         var nullList = new List<TSource> ();
 918                         int counter = 0;
 919                         int nullCounter = -1;
 920
 921                         foreach (TSource element in source) {
 922                                 TKey key = keySelector (element);
 923                                 if (key == null) {
 924                                         nullList.Add (element);
 925                                         if (nullCounter == -1) {
 926                                                 nullCounter = counter;
 927                                                 counter++;
 928                                         }
 929                                 } else {
 930                                         List<TSource> group = ContainsGroup<TKey, TSource> (groups, key, comparer);
 931                                         if (group == null) {
 932                                                 group = new List<TSource> ();
 933                                                 groups.Add (key, group);
 934                                                 counter++;
 935                                         }
 936                                         group.Add (element);
 937                                 }
 938                         }
 939
 940                         counter = 0;
 941                         foreach (var group in groups) {
 942                                 if (counter == nullCounter) {
 943                                         yield return new Grouping<TKey, TSource> (default (TKey), nullList);
 944                                         counter++;
 945                                 }
 946
 947                                 yield return new Grouping<TKey, TSource> (group.Key, group.Value);
 948                                 counter++;
 949                         }
 950
 951                         if (counter == nullCounter) {
 952                                 yield return new Grouping<TKey, TSource> (default (TKey), nullList);
 953                                 counter++;
 954                         }
 955                 }
 956
 957                 public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement> (this IEnumerable<TSource> source,
 958                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector)
 959                 {
 960                         return GroupBy<TSource, TKey, TElement> (source, keySelector, elementSelector, null);
 961                 }
 962
 963                 public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement> (this IEnumerable<TSource> source,
 964                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
 965                 {
 966                         Check.SourceAndKeyElementSelectors (source, keySelector, elementSelector);
 967
 968                         return CreateGroupByIterator (source, keySelector, elementSelector, comparer);
 969                 }
 970
 971                 static IEnumerable<IGrouping<TKey, TElement>> CreateGroupByIterator<TSource, TKey, TElement> (this IEnumerable<TSource> source,
 972                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
 973                 {
 974                         var groups = new Dictionary<TKey, List<TElement>> ();
 975                         var nullList = new List<TElement> ();
 976                         int counter = 0;
 977                         int nullCounter = -1;
 978
 979                         foreach (TSource item in source) {
 980                                 TKey key = keySelector (item);
 981                                 TElement element = elementSelector (item);
 982                                 if (key == null) {
 983                                         nullList.Add (element);
 984                                         if (nullCounter == -1) {
 985                                                 nullCounter = counter;
 986                                                 counter++;
 987                                         }
 988                                 } else {
 989                                         List<TElement> group = ContainsGroup<TKey, TElement> (groups, key, comparer);
 990                                         if (group == null) {
 991                                                 group = new List<TElement> ();
 992                                                 groups.Add (key, group);
 993                                                 counter++;
 994                                         }
 995                                         group.Add (element);
 996                                 }
 997                         }
 998
 999                         counter = 0;
1000                         foreach (var group in groups) {
1001                                 if (counter == nullCounter) {
1002                                         yield return new Grouping<TKey, TElement> (default (TKey), nullList);
1003                                         counter++;
1004                                 }
1005
1006                                 yield return new Grouping<TKey, TElement> (group.Key, group.Value);
1007                                 counter++;
1008                         }
1009
1010                         if (counter == nullCounter) {
1011                                 yield return new Grouping<TKey, TElement> (default (TKey), nullList);
1012                                 counter++;
1013                         }
1014                 }
1015
1016                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult> (this IEnumerable<TSource> source,
1017                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector,
1018                         Func<TKey, IEnumerable<TElement>, TResult> resultSelector)
1019                 {
1020                         return GroupBy (source, keySelector, elementSelector, resultSelector, null);
1021                 }
1022
1023                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult> (this IEnumerable<TSource> source,
1024                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector,
1025                         Func<TKey, IEnumerable<TElement>, TResult> resultSelector,
1026                         IEqualityComparer<TKey> comparer)
1027                 {
1028                         Check.GroupBySelectors (source, keySelector, elementSelector, resultSelector);
1029
1030                         return CreateGroupByIterator (source, keySelector, elementSelector, resultSelector, comparer);
1031                 }
1032
1033                 static IEnumerable<TResult> CreateGroupByIterator<TSource, TKey, TElement, TResult> (this IEnumerable<TSource> source,
1034                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector,
1035                         Func<TKey, IEnumerable<TElement>, TResult> resultSelector,
1036                         IEqualityComparer<TKey> comparer)
1037                 {
1038                         IEnumerable<IGrouping<TKey, TElement>> groups = GroupBy<TSource, TKey, TElement> (
1039                                 source, keySelector, elementSelector, comparer);
1040
1041                         foreach (IGrouping<TKey, TElement> group in groups)
1042                                 yield return resultSelector (group.Key, group);
1043                 }
1044
1045                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult> (this IEnumerable<TSource> source,
1046                         Func<TSource, TKey> keySelector,
1047                         Func<TKey, IEnumerable<TSource>, TResult> resultSelector)
1048                 {
1049                         return GroupBy (source, keySelector, resultSelector, null);
1050                 }
1051
1052                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult> (this IEnumerable<TSource> source,
1053                         Func<TSource, TKey> keySelector,
1054                         Func<TKey, IEnumerable<TSource>, TResult> resultSelector,
1055                         IEqualityComparer<TKey> comparer)
1056                 {
1057                         Check.SourceAndKeyResultSelectors (source, keySelector, resultSelector);
1058
1059                         return CreateGroupByIterator (source, keySelector, resultSelector, comparer);
1060                 }
1061
1062                 static IEnumerable<TResult> CreateGroupByIterator<TSource, TKey, TResult> (this IEnumerable<TSource> source,
1063                         Func<TSource, TKey> keySelector,
1064                         Func<TKey, IEnumerable<TSource>, TResult> resultSelector,
1065                         IEqualityComparer<TKey> comparer)
1066                 {
1067                         IEnumerable<IGrouping<TKey,TSource>> groups = GroupBy<TSource, TKey> (source, keySelector, comparer);
1068
1069                         foreach (IGrouping<TKey, TSource> group in groups)
1070                                 yield return resultSelector (group.Key, group);
1071                 }
1072
1073                 #endregion
1074
1075                 # region GroupJoin
1076
1077                 public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1078                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1079                         Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector)
1080                 {
1081                         return GroupJoin (outer, inner, outerKeySelector, innerKeySelector, resultSelector, null);
1082                 }
1083
1084                 public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1085                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1086                         Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector,
1087                         IEqualityComparer<TKey> comparer)
1088                 {
1089                         Check.JoinSelectors (outer, inner, outerKeySelector, innerKeySelector, resultSelector);
1090
1091                         if (comparer == null)
1092                                 comparer = EqualityComparer<TKey>.Default;
1093
1094                         return CreateGroupJoinIterator (outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
1095                 }
1096
1097                 static IEnumerable<TResult> CreateGroupJoinIterator<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1098                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1099                         Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector,
1100                         IEqualityComparer<TKey> comparer)
1101                 {
1102                         ILookup<TKey, TInner> innerKeys = ToLookup<TInner, TKey> (inner, innerKeySelector, comparer);
1103                         /*Dictionary<K, List<U>> innerKeys = new Dictionary<K, List<U>> ();
1104                         foreach (U element in inner)
1105                         {
1106                                         K innerKey = innerKeySelector (element);
1107                                         if (!innerKeys.ContainsKey (innerKey))
1108                                                         innerKeys.Add (innerKey, new List<U> ());
1109                                         innerKeys[innerKey].Add (element);
1110                         }*/
1111
1112                         foreach (TOuter element in outer) {
1113                                 TKey outerKey = outerKeySelector (element);
1114                                 if (outerKey != null && innerKeys.Contains (outerKey))
1115                                         yield return resultSelector (element, innerKeys [outerKey]);
1116                                 else
1117                                         yield return resultSelector (element, Empty<TInner> ());
1118                         }
1119                 }
1120
1121                 #endregion
1122
1123                 #region Intersect
1124
1125                 public static IEnumerable<TSource> Intersect<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
1126                 {
1127                         return Intersect (first, second, null);
1128                 }
1129
1130                 public static IEnumerable<TSource> Intersect<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
1131                 {
1132                         Check.FirstAndSecond (first, second);
1133
1134                         if (comparer == null)
1135                                 comparer = EqualityComparer<TSource>.Default;
1136
1137                         return CreateIntersectIterator (first, second, comparer);
1138                 }
1139
1140                 static IEnumerable<TSource> CreateIntersectIterator<TSource> (IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
1141                 {
1142                         var items = new HashSet<TSource> (second, comparer);
1143                         foreach (TSource element in first) {
1144                                 if (items.Remove (element))
1145                                         yield return element;
1146                         }
1147                 }
1148
1149                 #endregion
1150
1151                 # region Join
1152
1153                 public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1154                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1155                         Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey> comparer)
1156                 {
1157                         Check.JoinSelectors (outer, inner, outerKeySelector, innerKeySelector, resultSelector);
1158
1159                         if (comparer == null)
1160                                 comparer = EqualityComparer<TKey>.Default;
1161
1162                         return CreateJoinIterator (outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
1163                 }
1164
1165                 static IEnumerable<TResult> CreateJoinIterator<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1166                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1167                         Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey> comparer)
1168                 {
1169                         ILookup<TKey, TInner> innerKeys = ToLookup<TInner, TKey> (inner, innerKeySelector, comparer);
1170                         /*Dictionary<K, List<U>> innerKeys = new Dictionary<K, List<U>> ();
1171                         foreach (U element in inner)
1172                         {
1173                                         K innerKey = innerKeySelector (element);
1174                                         if (!innerKeys.ContainsKey (innerKey))
1175                                                         innerKeys.Add (innerKey, new List<U> ());
1176                                         innerKeys[innerKey].Add (element);
1177                         }*/
1178
1179                         foreach (TOuter element in outer) {
1180                                 TKey outerKey = outerKeySelector (element);
1181                                 if (outerKey != null && innerKeys.Contains (outerKey)) {
1182                                         foreach (TInner innerElement in innerKeys [outerKey])
1183                                                 yield return resultSelector (element, innerElement);
1184                                 }
1185                         }
1186                 }
1187
1188                 public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1189                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1190                         Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector)
1191                 {
1192                         return outer.Join (inner, outerKeySelector, innerKeySelector, resultSelector, null);
1193                 }
1194
1195                 #endregion
1196
1197                 #region Last
1198
1199                 static TSource Last<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate, Fallback fallback)
1200                 {
1201                         var empty = true;
1202                         var item = default (TSource);
1203
1204                         foreach (var element in source) {
1205                                 if (!predicate (element))
1206                                         continue;
1207
1208                                 item = element;
1209                                 empty = false;
1210                         }
1211
1212                         if (!empty)
1213                                 return item;
1214
1215                         if (fallback == Fallback.Throw)
1216                                 throw NoMatchingElement ();
1217
1218                         return item;
1219                 }
1220
1221                 public static TSource Last<TSource> (this IEnumerable<TSource> source)
1222                 {
1223                         Check.Source (source);
1224
1225                         var collection = source as ICollection<TSource>;
1226                         if (collection != null && collection.Count == 0)
1227                                 throw EmptySequence ();
1228
1229                         var list = source as IList<TSource>;
1230                         if (list != null)
1231                                 return list [list.Count - 1];
1232
1233 #if !FULL_AOT_RUNTIME
1234                         return source.Last (PredicateOf<TSource>.Always, Fallback.Throw);
1235 #else
1236                         var empty = true;
1237                         var item = default (TSource);
1238
1239                         foreach (var element in source) {
1240                                 item = element;
1241                                 empty = false;
1242                         }
1243
1244                         if (!empty)
1245                                 return item;
1246
1247                         throw EmptySequence ();
1248 #endif
1249         }
1250
1251                 public static TSource Last<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
1252                 {
1253                         Check.SourceAndPredicate (source, predicate);
1254
1255                         return source.Last (predicate, Fallback.Throw);
1256                 }
1257
1258                 #endregion
1259
1260                 #region LastOrDefault
1261
1262                 public static TSource LastOrDefault<TSource> (this IEnumerable<TSource> source)
1263                 {
1264                         Check.Source (source);
1265
1266                         var list = source as IList<TSource>;
1267                         if (list != null)
1268                                 return list.Count > 0 ? list [list.Count - 1] : default (TSource);
1269
1270 #if !FULL_AOT_RUNTIME
1271                         return source.Last (PredicateOf<TSource>.Always, Fallback.Default);
1272 #else
1273                         var empty = true;
1274                         var item = default (TSource);
1275
1276                         foreach (var element in source) {
1277                                 item = element;
1278                                 empty = false;
1279                         }
1280
1281                         if (!empty)
1282                                 return item;
1283
1284                         return item;
1285 #endif
1286                 }
1287
1288                 public static TSource LastOrDefault<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
1289                 {
1290                         Check.SourceAndPredicate (source, predicate);
1291
1292                         return source.Last (predicate, Fallback.Default);
1293                 }
1294
1295                 #endregion
1296
1297                 #region LongCount
1298
1299                 public static long LongCount<TSource> (this IEnumerable<TSource> source)
1300                 {
1301                         Check.Source (source);
1302
1303 #if !NET_2_1
1304                         var array = source as TSource [];
1305                         if (array != null)
1306                                 return array.LongLength;
1307 #endif
1308
1309                         long counter = 0;
1310                         using (var enumerator = source.GetEnumerator ())
1311                                 while (enumerator.MoveNext ())
1312                                         counter++;
1313
1314                         return counter;
1315                 }
1316
1317                 public static long LongCount<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
1318                 {
1319                         Check.SourceAndSelector (source, predicate);
1320
1321                         long counter = 0;
1322                         foreach (TSource element in source)
1323                                 if (predicate (element))
1324                                         counter++;
1325
1326                         return counter;
1327                 }
1328
1329                 #endregion
1330
1331                 #region Max
1332
1333                 public static int Max (this IEnumerable<int> source)
1334                 {
1335                         Check.Source (source);
1336
1337                         bool empty = true;
1338                         var max = int.MinValue;
1339                         foreach (var element in source){
1340                                 max = Math.Max (element, max);
1341                                 empty = false;
1342                         }
1343                         if (empty)
1344                                 throw EmptySequence();
1345                         return max;
1346                 }
1347
1348                 public static long Max (this IEnumerable<long> source)
1349                 {
1350                         Check.Source (source);
1351
1352                         bool empty = true;
1353                         var max = long.MinValue;
1354                         foreach (var element in source){
1355                                 max = Math.Max (element, max);
1356                                 empty = false;
1357                         }
1358                         if (empty)
1359                                 throw EmptySequence ();
1360                         return max;
1361                 }
1362
1363                 public static double Max (this IEnumerable<double> source)
1364                 {
1365                         Check.Source (source);
1366
1367                         bool empty = true;
1368                         var max = double.MinValue;
1369                         foreach (var element in source){
1370                                 max = Math.Max (element, max);
1371                                 empty = false;
1372                         }
1373                         if (empty)
1374                                 throw EmptySequence ();
1375                         return max;
1376                 }
1377
1378                 public static float Max (this IEnumerable<float> source)
1379                 {
1380                         Check.Source (source);
1381
1382                         bool empty = true;
1383                         var max = float.MinValue;
1384                         foreach (var element in source){
1385                                 max = Math.Max (element, max);
1386                                 empty = false;
1387                         }
1388                         if (empty)
1389                                 throw EmptySequence ();
1390                         return max;
1391                 }
1392
1393                 public static decimal Max (this IEnumerable<decimal> source)
1394                 {
1395                         Check.Source (source);
1396
1397                         bool empty = true;
1398                         var max = decimal.MinValue;
1399                         foreach (var element in source){
1400                                 max = Math.Max (element, max);
1401                                 empty = false;
1402                         }
1403                         if (empty)
1404                                 throw EmptySequence ();
1405                         return max;
1406                 }
1407
1408                 public static int? Max (this IEnumerable<int?> source)
1409                 {
1410                         Check.Source (source);
1411
1412                         bool empty = true;
1413                         var max = int.MinValue;
1414
1415                         foreach (var element in source) {
1416                                 if (!element.HasValue)
1417                                         continue;
1418
1419                                 max = Math.Max (element.Value, max);
1420                                 empty = false;
1421                         }
1422
1423                         if (empty)
1424                                 return null;
1425
1426                         return max;
1427                 }
1428
1429                 public static long? Max (this IEnumerable<long?> source)
1430                 {
1431                         Check.Source (source);
1432
1433                         bool empty = true;
1434                         var max = long.MinValue;
1435
1436                         foreach (var element in source) {
1437                                 if (!element.HasValue)
1438                                         continue;
1439
1440                                 max = Math.Max (element.Value, max);
1441                                 empty = false;
1442                         }
1443
1444                         if (empty)
1445                                 return null;
1446
1447                         return max;
1448                 }
1449
1450                 public static double? Max (this IEnumerable<double?> source)
1451                 {
1452                         Check.Source (source);
1453
1454                         bool empty = true;
1455                         var max = double.MinValue;
1456
1457                         foreach (var element in source) {
1458                                 if (!element.HasValue)
1459                                         continue;
1460
1461                                 max = Math.Max (element.Value, max);
1462                                 empty = false;
1463                         }
1464
1465                         if (empty)
1466                                 return null;
1467
1468                         return max;
1469                 }
1470
1471                 public static float? Max (this IEnumerable<float?> source)
1472                 {
1473                         Check.Source (source);
1474
1475                         bool empty = true;
1476                         var max = float.MinValue;
1477
1478                         foreach (var element in source) {
1479                                 if (!element.HasValue)
1480                                         continue;
1481
1482                                 max = Math.Max (element.Value, max);
1483                                 empty = false;
1484                         }
1485
1486                         if (empty)
1487                                 return null;
1488
1489                         return max;
1490                 }
1491
1492                 public static decimal? Max (this IEnumerable<decimal?> source)
1493                 {
1494                         Check.Source (source);
1495
1496                         bool empty = true;
1497                         var max = decimal.MinValue;
1498
1499                         foreach (var element in source) {
1500                                 if (!element.HasValue)
1501                                         continue;
1502
1503                                 max = Math.Max (element.Value, max);
1504                                 empty = false;
1505                         }
1506
1507                         if (empty)
1508                                 return null;
1509
1510                         return max;
1511                 }
1512
1513                 // TODO: test nullable and non-nullable
1514                 public static TSource Max<TSource> (this IEnumerable<TSource> source)
1515                 {
1516                         Check.Source (source);
1517
1518                         var comparer = Comparer<TSource>.Default;
1519
1520                         TSource max = default (TSource);
1521
1522                         if (default (TSource) == null){
1523                                 foreach (var element in source) {
1524                                         if (element == null)
1525                                                 continue;
1526
1527                                         if (max == null || comparer.Compare (element, max) > 0)
1528                                                 max = element;
1529                                 }
1530                         } else {
1531                                 bool empty = true;
1532                                 foreach (var element in source) {
1533                                         if (empty){
1534                                                 max = element;
1535                                                 empty = false;
1536                                                 continue;
1537                                         }
1538                                         if (comparer.Compare (element, max) > 0)
1539                                                 max = element;
1540                                 }
1541                                 if (empty)
1542                                         throw EmptySequence ();
1543                         }
1544                         return max;
1545                 }
1546
1547                 public static int Max<TSource> (this IEnumerable<TSource> source, Func<TSource, int> selector)
1548                 {
1549                         Check.SourceAndSelector (source, selector);
1550
1551                         bool empty = true;
1552                         var max = int.MinValue;
1553                         foreach (var element in source){
1554                                 max = Math.Max (selector (element), max);
1555                                 empty = false;
1556                         }
1557                         if (empty)
1558                                 throw NoMatchingElement ();
1559                         return max;
1560                 }
1561
1562                 public static long Max<TSource> (this IEnumerable<TSource> source, Func<TSource, long> selector)
1563                 {
1564                         Check.SourceAndSelector (source, selector);
1565
1566                         bool empty = true;
1567                         var max = long.MinValue;
1568                         foreach (var element in source){
1569                                 max = Math.Max (selector (element), max);
1570                                 empty = false;
1571                         }
1572                         if (empty)
1573                                 throw NoMatchingElement ();
1574                         return max;
1575                 }
1576
1577                 public static double Max<TSource> (this IEnumerable<TSource> source, Func<TSource, double> selector)
1578                 {
1579                         Check.SourceAndSelector (source, selector);
1580
1581                         bool empty = true;
1582                         var max = double.MinValue;
1583                         foreach (var element in source){
1584                                 max = Math.Max (selector (element), max);
1585                                 empty = false;
1586                         }
1587                         if (empty)
1588                                 throw NoMatchingElement ();
1589                         return max;
1590                 }
1591
1592                 public static float Max<TSource> (this IEnumerable<TSource> source, Func<TSource, float> selector)
1593                 {
1594                         Check.SourceAndSelector (source, selector);
1595
1596                         bool empty = true;
1597                         var max = float.MinValue;
1598                         foreach (var element in source){
1599                                 max = Math.Max (selector (element), max);
1600                                 empty = false;
1601                         }
1602                         if (empty)
1603                                 throw NoMatchingElement ();
1604                         return max;
1605                 }
1606
1607                 public static decimal Max<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal> selector)
1608                 {
1609                         Check.SourceAndSelector (source, selector);
1610
1611                         bool empty = true;
1612                         var max = decimal.MinValue;
1613                         foreach (var element in source){
1614                                 max = Math.Max (selector (element), max);
1615                                 empty = false;
1616                         }
1617                         if (empty)
1618                                 throw NoMatchingElement ();
1619                         return max;
1620                 }
1621
1622                 static U Iterate<T, U> (IEnumerable<T> source, U initValue, Func<T, U, U> selector)
1623                 {
1624                         bool empty = true;
1625                         foreach (var element in source) {
1626                                 initValue = selector (element, initValue);
1627                                 empty = false;
1628                         }
1629
1630                         if (empty)
1631                                 throw NoMatchingElement ();
1632
1633                         return initValue;
1634                 }
1635
1636                 public static int? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, int?> selector)
1637                 {
1638                         Check.SourceAndSelector (source, selector);
1639
1640                         bool empty = true;
1641                         int? max = null;
1642                         foreach (var element in source) {
1643                                 int? item = selector (element);
1644
1645                                 if (!max.HasValue)
1646                                         max = item;
1647                                 else if (item > max)
1648                                         max = item;
1649                                 empty = false;
1650                         }
1651
1652                         if (empty)
1653                                 return null;
1654                         return max;
1655                 }
1656
1657                 public static long? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, long?> selector)
1658                 {
1659                         Check.SourceAndSelector (source, selector);
1660
1661                         bool empty = true;
1662                         long? max = null;
1663                         foreach (var element in source) {
1664                                 long? item = selector (element);
1665
1666                                 if (!max.HasValue)
1667                                         max = item;
1668                                 else if (item > max)
1669                                         max = item;
1670                                 empty = false;
1671                         }
1672
1673                         if (empty)
1674                                 return null;
1675                         return max;
1676                 }
1677
1678                 public static double? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, double?> selector)
1679                 {
1680                         Check.SourceAndSelector (source, selector);
1681
1682                         bool empty = true;
1683                         double? max = null;
1684                         foreach (var element in source) {
1685                                 double? item = selector (element);
1686
1687                                 if (!max.HasValue)
1688                                         max = item;
1689                                 else if (item > max)
1690                                         max = item;
1691                                 empty = false;
1692                         }
1693
1694                         if (empty)
1695                                 return null;
1696                         return max;
1697                 }
1698
1699                 public static float? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, float?> selector)
1700                 {
1701                         Check.SourceAndSelector (source, selector);
1702
1703                         bool empty = true;
1704                         float? max = null;
1705                         foreach (var element in source) {
1706                                 float? item = selector (element);
1707
1708                                 if (!max.HasValue)
1709                                         max = item;
1710                                 else if (item > max)
1711                                         max = item;
1712                                 empty = false;
1713                         }
1714
1715                         if (empty)
1716                                 return null;
1717                         return max;
1718                 }
1719
1720                 public static decimal? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal?> selector)
1721                 {
1722                         Check.SourceAndSelector (source, selector);
1723
1724                         bool empty = true;
1725                         decimal? max = null;
1726                         foreach (var element in source) {
1727                                 decimal? item = selector (element);
1728
1729                                 if (!max.HasValue)
1730                                         max = item;
1731                                 else if (item > max)
1732                                         max = item;
1733                                 empty = false;
1734                         }
1735
1736                         if (empty)
1737                                 return null;
1738                         return max;
1739                 }
1740
1741                 public static TResult Max<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, TResult> selector)
1742                 {
1743                         Check.SourceAndSelector (source, selector);
1744
1745                         // TODO: inline
1746                         return source.Select (selector).Max ();
1747                 }
1748
1749                 #endregion
1750
1751                 #region Min
1752
1753                 public static int Min (this IEnumerable<int> source)
1754                 {
1755                         Check.Source (source);
1756
1757                         bool empty = true;
1758                         var min = int.MaxValue;
1759                         foreach (var element in source){
1760                                 min = Math.Min (element, min);
1761                                 empty = false;
1762                         }
1763                         if (empty)
1764                                 throw EmptySequence ();
1765                         return min;
1766                 }
1767
1768                 public static long Min (this IEnumerable<long> source)
1769                 {
1770                         Check.Source (source);
1771
1772                         bool empty = true;
1773                         var min = long.MaxValue;
1774                         foreach (var element in source){
1775                                 min = Math.Min (element, min);
1776                                 empty = false;
1777                         }
1778                         if (empty)
1779                                 throw EmptySequence ();
1780                         return min;
1781                 }
1782
1783                 public static double Min (this IEnumerable<double> source)
1784                 {
1785                         Check.Source (source);
1786
1787                         bool empty = true;
1788                         var min = double.MaxValue;
1789                         foreach (var element in source){
1790                                 min = Math.Min (element, min);
1791                                 empty = false;
1792                         }
1793                         if (empty)
1794                                 throw EmptySequence ();
1795                         return min;
1796                 }
1797
1798                 public static float Min (this IEnumerable<float> source)
1799                 {
1800                         Check.Source (source);
1801
1802                         bool empty = true;
1803                         var min = float.MaxValue;
1804                         foreach (var element in source){
1805                                 min = Math.Min (element, min);
1806                                 empty = false;
1807                         }
1808                         if (empty)
1809                                 throw EmptySequence ();
1810                         return min;
1811                 }
1812
1813                 public static decimal Min (this IEnumerable<decimal> source)
1814                 {
1815                         Check.Source (source);
1816
1817                         bool empty = true;
1818                         var min = decimal.MaxValue;
1819                         foreach (var element in source){
1820                                 min = Math.Min (element, min);
1821                                 empty = false;
1822                         }
1823                         if (empty)
1824                                 throw EmptySequence ();
1825                         return min;
1826                 }
1827
1828                 public static int? Min (this IEnumerable<int?> source)
1829                 {
1830                         Check.Source (source);
1831
1832                         bool empty = true;
1833                         var min = int.MaxValue;
1834
1835                         foreach (var element in source) {
1836                                 if (!element.HasValue)
1837                                         continue;
1838
1839                                 min = Math.Min (element.Value, min);
1840                                 empty = false;
1841                         }
1842
1843                         if (empty)
1844                                 return null;
1845
1846                         return min;
1847                 }
1848
1849                 public static long? Min (this IEnumerable<long?> source)
1850                 {
1851                         Check.Source (source);
1852
1853                         bool empty = true;
1854                         var min = long.MaxValue;
1855
1856                         foreach (var element in source) {
1857                                 if (!element.HasValue)
1858                                         continue;
1859
1860                                 min = Math.Min (element.Value, min);
1861                                 empty = false;
1862                         }
1863
1864                         if (empty)
1865                                 return null;
1866
1867                         return min;
1868                 }
1869
1870                 public static double? Min (this IEnumerable<double?> source)
1871                 {
1872                         Check.Source (source);
1873
1874                         bool empty = true;
1875                         var min = double.MaxValue;
1876
1877                         foreach (var element in source) {
1878                                 if (!element.HasValue)
1879                                         continue;
1880
1881                                 min = Math.Min (element.Value, min);
1882                                 empty = false;
1883                         }
1884
1885                         if (empty)
1886                                 return null;
1887
1888                         return min;
1889                 }
1890
1891                 public static float? Min (this IEnumerable<float?> source)
1892                 {
1893                         Check.Source (source);
1894
1895                         bool empty = true;
1896                         var min = float.MaxValue;
1897
1898                         foreach (var element in source) {
1899                                 if (!element.HasValue)
1900                                         continue;
1901
1902                                 min = Math.Min (element.Value, min);
1903                                 empty = false;
1904                         }
1905
1906                         if (empty)
1907                                 return null;
1908
1909                         return min;
1910                 }
1911
1912                 public static decimal? Min (this IEnumerable<decimal?> source)
1913                 {
1914                         Check.Source (source);
1915
1916                         bool empty = true;
1917                         var min = decimal.MaxValue;
1918
1919                         foreach (var element in source) {
1920                                 if (!element.HasValue)
1921                                         continue;
1922
1923                                 min = Math.Min (element.Value, min);
1924                                 empty = false;
1925                         }
1926
1927                         if (empty)
1928                                 return null;
1929
1930                         return min;
1931                 }
1932
1933                 public static TSource Min<TSource> (this IEnumerable<TSource> source)
1934                 {
1935                         Check.Source (source);
1936
1937                         var comparer = Comparer<TSource>.Default;
1938
1939                         TSource min = default (TSource);
1940
1941                         if (default (TSource) == null){
1942                                 foreach (var element in source) {
1943                                         if (element == null)
1944                                                 continue;
1945
1946                                         if (min == null || comparer.Compare (element, min) < 0)
1947                                                 min = element;
1948                                 }
1949                         } else {
1950                                 bool empty = true;
1951                                 foreach (var element in source) {
1952                                         if (empty){
1953                                                 min = element;
1954                                                 empty = false;
1955                                                 continue;
1956                                         }
1957                                         if (comparer.Compare (element, min) < 0)
1958                                                 min = element;
1959                                 }
1960                                 if (empty)
1961                                         throw EmptySequence ();
1962                         }
1963                         return min;
1964                 }
1965
1966                 public static int Min<TSource> (this IEnumerable<TSource> source, Func<TSource, int> selector)
1967                 {
1968                         Check.SourceAndSelector (source, selector);
1969
1970                         bool empty = true;
1971                         var min = int.MaxValue;
1972                         foreach (var element in source){
1973                                 min = Math.Min (selector (element), min);
1974                                 empty = false;
1975                         }
1976                         if (empty)
1977                                 throw NoMatchingElement ();
1978                         return min;
1979                 }
1980
1981                 public static long Min<TSource> (this IEnumerable<TSource> source, Func<TSource, long> selector)
1982                 {
1983                         Check.SourceAndSelector (source, selector);
1984
1985                         bool empty = true;
1986                         var min = long.MaxValue;
1987                         foreach (var element in source){
1988                                 min = Math.Min (selector (element), min);
1989                                 empty = false;
1990                         }
1991                         if (empty)
1992                                 throw NoMatchingElement ();
1993                         return min;
1994                 }
1995
1996                 public static double Min<TSource> (this IEnumerable<TSource> source, Func<TSource, double> selector)
1997                 {
1998                         Check.SourceAndSelector (source, selector);
1999
2000                         bool empty = true;
2001                         var min = double.MaxValue;
2002                         foreach (var element in source){
2003                                 min = Math.Min (selector (element), min);
2004                                 empty = false;
2005                         }
2006                         if (empty)
2007                                 throw NoMatchingElement ();
2008                         return min;
2009                 }
2010
2011                 public static float Min<TSource> (this IEnumerable<TSource> source, Func<TSource, float> selector)
2012                 {
2013                         Check.SourceAndSelector (source, selector);
2014
2015                         bool empty = true;
2016                         var min = float.MaxValue;
2017                         foreach (var element in source){
2018                                 min = Math.Min (selector (element), min);
2019                                 empty = false;
2020                         }
2021                         if (empty)
2022                                 throw NoMatchingElement ();
2023                         return min;
2024                 }
2025
2026                 public static decimal Min<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal> selector)
2027                 {
2028                         Check.SourceAndSelector (source, selector);
2029
2030                         bool empty = true;
2031                         var min = decimal.MaxValue;
2032                         foreach (var element in source){
2033                                 min = Math.Min (selector (element), min);
2034                                 empty = false;
2035                         }
2036                         if (empty)
2037                                 throw NoMatchingElement ();
2038                         return min;
2039                 }
2040
2041                 public static int? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, int?> selector)
2042                 {
2043                         Check.SourceAndSelector (source, selector);
2044
2045                         bool empty = true;
2046                         int? min = null;
2047                         foreach (var element in source) {
2048                                 int? item = selector (element);
2049
2050                                 if (!min.HasValue)
2051                                         min = item;
2052                                 else if (item < min)
2053                                         min = item;
2054                                 empty = false;
2055                         }
2056
2057                         if (empty)
2058                                 return null;
2059                         return min;
2060                 }
2061
2062                 public static long? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, long?> selector)
2063                 {
2064                         Check.SourceAndSelector (source, selector);
2065
2066                         bool empty = true;
2067                         long? min = null;
2068                         foreach (var element in source) {
2069                                 long? item = selector (element);
2070
2071                                 if (!min.HasValue)
2072                                         min = item;
2073                                 else if (item < min)
2074                                         min = item;
2075                                 empty = false;
2076                         }
2077
2078                         if (empty)
2079                                 return null;
2080                         return min;
2081                 }
2082
2083                 public static float? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, float?> selector)
2084                 {
2085                         Check.SourceAndSelector (source, selector);
2086
2087                         bool empty = true;
2088                         float? min = null;
2089                         foreach (var element in source) {
2090                                 float? item = selector (element);
2091
2092                                 if (!min.HasValue)
2093                                         min = item;
2094                                 else if (item < min)
2095                                         min = item;
2096                                 empty = false;
2097                         }
2098
2099                         if (empty)
2100                                 return null;
2101                         return min;
2102                 }
2103
2104                 public static double? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, double?> selector)
2105                 {
2106                         Check.SourceAndSelector (source, selector);
2107
2108                         bool empty = true;
2109                         double? min = null;
2110                         foreach (var element in source) {
2111                                 double? item = selector (element);
2112
2113                                 if (!min.HasValue)
2114                                         min = item;
2115                                 else if (item < min)
2116                                         min = item;
2117                                 empty = false;
2118                         }
2119
2120                         if (empty)
2121                                 return null;
2122                         return min;
2123                 }
2124
2125                 public static decimal? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal?> selector)
2126                 {
2127                         Check.SourceAndSelector (source, selector);
2128
2129                         bool empty = true;
2130                         decimal? min = null;
2131                         foreach (var element in source) {
2132                                 decimal? item = selector (element);
2133
2134                                 if (!min.HasValue)
2135                                         min = item;
2136                                 else if (item < min)
2137                                         min = item;
2138                                 empty = false;
2139                         }
2140
2141                         if (empty)
2142                                 return null;
2143                         return min;
2144                 }
2145
2146                 public static TResult Min<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, TResult> selector)
2147                 {
2148                         Check.SourceAndSelector (source, selector);
2149
2150                         // TODO: inline
2151                         return source.Select (selector).Min ();
2152                 }
2153
2154                 #endregion
2155
2156                 #region OfType
2157
2158                 public static IEnumerable<TResult> OfType<TResult> (this IEnumerable source)
2159                 {
2160                         Check.Source (source);
2161
2162                         return CreateOfTypeIterator<TResult> (source);
2163                 }
2164
2165                 static IEnumerable<TResult> CreateOfTypeIterator<TResult> (IEnumerable source)
2166                 {
2167                         foreach (object element in source)
2168                                 if (element is TResult)
2169                                         yield return (TResult) element;
2170                 }
2171
2172                 #endregion
2173
2174                 #region OrderBy
2175
2176                 public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey> (this IEnumerable<TSource> source,
2177                                 Func<TSource, TKey> keySelector)
2178                 {
2179                         return OrderBy<TSource, TKey> (source, keySelector, null);
2180                 }
2181
2182                 public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey> (this IEnumerable<TSource> source,
2183                                 Func<TSource, TKey> keySelector,
2184                                 IComparer<TKey> comparer)
2185                 {
2186                         Check.SourceAndKeySelector (source, keySelector);
2187
2188                         return new OrderedSequence<TSource, TKey> (source, keySelector, comparer, SortDirection.Ascending);
2189                 }
2190
2191                 #endregion
2192
2193                 #region OrderByDescending
2194
2195                 public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey> (this IEnumerable<TSource> source,
2196                                 Func<TSource, TKey> keySelector)
2197                 {
2198                         return OrderByDescending<TSource, TKey> (source, keySelector, null);
2199                 }
2200
2201                 public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey> (this IEnumerable<TSource> source,
2202                                 Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
2203                 {
2204                         Check.SourceAndKeySelector (source, keySelector);
2205
2206                         return new OrderedSequence<TSource, TKey> (source, keySelector, comparer, SortDirection.Descending);
2207                 }
2208
2209                 #endregion
2210
2211                 #region Range
2212
2213                 public static IEnumerable<int> Range (int start, int count)
2214                 {
2215                         if (count < 0)
2216                                 throw new ArgumentOutOfRangeException ("count");
2217
2218                         if (((long) start + count) - 1L > int.MaxValue)
2219                                 throw new ArgumentOutOfRangeException ();
2220
2221                         return CreateRangeIterator (start, count);
2222                 }
2223
2224                 static IEnumerable<int> CreateRangeIterator (int start, int count)
2225                 {
2226                         for (int i = 0; i < count; i++)
2227                                 yield return start + i;
2228                 }
2229
2230                 #endregion
2231
2232                 #region Repeat
2233
2234                 public static IEnumerable<TResult> Repeat<TResult> (TResult element, int count)
2235                 {
2236                         if (count < 0)
2237                                 throw new ArgumentOutOfRangeException ();
2238
2239                         return CreateRepeatIterator (element, count);
2240                 }
2241
2242                 static IEnumerable<TResult> CreateRepeatIterator<TResult> (TResult element, int count)
2243                 {
2244                         for (int i = 0; i < count; i++)
2245                                 yield return element;
2246                 }
2247
2248                 #endregion
2249
2250                 #region Reverse
2251
2252                 public static IEnumerable<TSource> Reverse<TSource> (this IEnumerable<TSource> source)
2253                 {
2254                         Check.Source (source);
2255
2256                         return CreateReverseIterator (source);
2257                 }
2258
2259                 static IEnumerable<TSource> CreateReverseIterator<TSource> (IEnumerable<TSource> source)
2260                 {
2261                         var array = source.ToArray ();
2262
2263                         for (int i = array.Length - 1; i >= 0; i--)
2264                                 yield return array [i];
2265                 }
2266
2267                 #endregion
2268
2269                 #region Select
2270
2271                 public static IEnumerable<TResult> Select<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, TResult> selector)
2272                 {
2273                         Check.SourceAndSelector (source, selector);
2274
2275                         return CreateSelectIterator (source, selector);
2276                 }
2277
2278                 static IEnumerable<TResult> CreateSelectIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, TResult> selector)
2279                 {
2280                         foreach (var element in source)
2281                                 yield return selector (element);
2282                 }
2283
2284                 public static IEnumerable<TResult> Select<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, int, TResult> selector)
2285                 {
2286                         Check.SourceAndSelector (source, selector);
2287
2288                         return CreateSelectIterator (source, selector);
2289                 }
2290
2291                 static IEnumerable<TResult> CreateSelectIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, int, TResult> selector)
2292                 {
2293                         int counter = 0;
2294                         foreach (TSource element in source) {
2295                                 yield return selector (element, counter);
2296                                 counter++;
2297                         }
2298                 }
2299
2300                 #endregion
2301
2302                 #region SelectMany
2303
2304                 public static IEnumerable<TResult> SelectMany<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
2305                 {
2306                         Check.SourceAndSelector (source, selector);
2307
2308                         return CreateSelectManyIterator (source, selector);
2309                 }
2310
2311                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
2312                 {
2313                         foreach (TSource element in source)
2314                                 foreach (TResult item in selector (element))
2315                                         yield return item;
2316                 }
2317
2318                 public static IEnumerable<TResult> SelectMany<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TResult>> selector)
2319                 {
2320                         Check.SourceAndSelector (source, selector);
2321
2322                         return CreateSelectManyIterator (source, selector);
2323                 }
2324
2325                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TResult>> selector)
2326                 {
2327                         int counter = 0;
2328                         foreach (TSource element in source) {
2329                                 foreach (TResult item in selector (element, counter))
2330                                         yield return item;
2331                                 counter++;
2332                         }
2333                 }
2334
2335                 public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult> (this IEnumerable<TSource> source,
2336                         Func<TSource, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector)
2337                 {
2338                         Check.SourceAndCollectionSelectors (source, collectionSelector, resultSelector);
2339
2340                         return CreateSelectManyIterator (source, collectionSelector, resultSelector);
2341                 }
2342
2343                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TCollection, TResult> (IEnumerable<TSource> source,
2344                         Func<TSource, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> selector)
2345                 {
2346                         foreach (TSource element in source)
2347                                 foreach (TCollection collection in collectionSelector (element))
2348                                         yield return selector (element, collection);
2349                 }
2350
2351                 public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult> (this IEnumerable<TSource> source,
2352                         Func<TSource, int, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector)
2353                 {
2354                         Check.SourceAndCollectionSelectors (source, collectionSelector, resultSelector);
2355
2356                         return CreateSelectManyIterator (source, collectionSelector, resultSelector);
2357                 }
2358
2359                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TCollection, TResult> (IEnumerable<TSource> source,
2360                         Func<TSource, int, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> selector)
2361                 {
2362                         int counter = 0;
2363                         foreach (TSource element in source)
2364                                 foreach (TCollection collection in collectionSelector (element, counter++))
2365                                         yield return selector (element, collection);
2366                 }
2367
2368                 #endregion
2369
2370                 #region Single
2371
2372                 static TSource Single<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate, Fallback fallback)
2373                 {
2374                         var found = false;
2375                         var item = default (TSource);
2376
2377                         foreach (var element in source) {
2378                                 if (!predicate (element))
2379                                         continue;
2380
2381                                 if (found)
2382                                         throw MoreThanOneMatchingElement ();
2383
2384                                 found = true;
2385                                 item = element;
2386                         }
2387
2388                         if (!found && fallback == Fallback.Throw)
2389                                 throw NoMatchingElement ();
2390
2391                         return item;
2392                 }
2393
2394                 public static TSource Single<TSource> (this IEnumerable<TSource> source)
2395                 {
2396                         Check.Source (source);
2397
2398 #if !FULL_AOT_RUNTIME
2399                         return source.Single (PredicateOf<TSource>.Always, Fallback.Throw);
2400 #else
2401                         var found = false;
2402                         var item = default (TSource);
2403
2404                         foreach (var element in source) {
2405                                 if (found)
2406                                         throw MoreThanOneElement ();
2407
2408                                 found = true;
2409                                 item = element;
2410                         }
2411
2412                         if (!found)
2413                                 throw NoMatchingElement ();
2414
2415                         return item;
2416 #endif
2417         }
2418
2419                 public static TSource Single<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2420                 {
2421                         Check.SourceAndPredicate (source, predicate);
2422
2423                         return source.Single (predicate, Fallback.Throw);
2424                 }
2425
2426                 #endregion
2427
2428                 #region SingleOrDefault
2429
2430                 public static TSource SingleOrDefault<TSource> (this IEnumerable<TSource> source)
2431                 {
2432                         Check.Source (source);
2433
2434 #if !FULL_AOT_RUNTIME
2435                         return source.Single (PredicateOf<TSource>.Always, Fallback.Default);
2436 #else
2437                         var found = false;
2438                         var item = default (TSource);
2439
2440                         foreach (var element in source) {
2441                                 if (found)
2442                                         throw MoreThanOneMatchingElement ();
2443
2444                                 found = true;
2445                                 item = element;
2446                         }
2447
2448                         return item;
2449 #endif
2450         }
2451
2452                 public static TSource SingleOrDefault<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2453                 {
2454                         Check.SourceAndPredicate (source, predicate);
2455
2456                         return source.Single (predicate, Fallback.Default);
2457                 }
2458
2459                 #endregion
2460
2461                 #region Skip
2462
2463                 public static IEnumerable<TSource> Skip<TSource> (this IEnumerable<TSource> source, int count)
2464                 {
2465                         Check.Source (source);
2466
2467                         return CreateSkipIterator (source, count);
2468                 }
2469
2470                 static IEnumerable<TSource> CreateSkipIterator<TSource> (IEnumerable<TSource> source, int count)
2471                 {
2472                         var enumerator = source.GetEnumerator ();
2473                         try {
2474                                 while (count-- > 0)
2475                                         if (!enumerator.MoveNext ())
2476                                                 yield break;
2477
2478                                 while (enumerator.MoveNext ())
2479                                         yield return enumerator.Current;
2480
2481                         } finally {
2482                                 enumerator.Dispose ();
2483                         }
2484                 }
2485
2486                 #endregion
2487
2488                 #region SkipWhile
2489
2490                 public static IEnumerable<TSource> SkipWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2491                 {
2492                         Check.SourceAndPredicate (source, predicate);
2493
2494                         return CreateSkipWhileIterator (source, predicate);
2495                 }
2496
2497                 static IEnumerable<TSource> CreateSkipWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, bool> predicate)
2498                 {
2499                         bool yield = false;
2500
2501                         foreach (TSource element in source) {
2502                                 if (yield)
2503                                         yield return element;
2504                                 else
2505                                         if (!predicate (element)) {
2506                                                 yield return element;
2507                                                 yield = true;
2508                                         }
2509                         }
2510                 }
2511
2512                 public static IEnumerable<TSource> SkipWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2513                 {
2514                         Check.SourceAndPredicate (source, predicate);
2515
2516                         return CreateSkipWhileIterator (source, predicate);
2517                 }
2518
2519                 static IEnumerable<TSource> CreateSkipWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2520                 {
2521                         int counter = 0;
2522                         bool yield = false;
2523
2524                         foreach (TSource element in source) {
2525                                 if (yield)
2526                                         yield return element;
2527                                 else
2528                                         if (!predicate (element, counter)) {
2529                                                 yield return element;
2530                                                 yield = true;
2531                                         }
2532                                 counter++;
2533                         }
2534                 }
2535
2536                 #endregion
2537
2538                 #region Sum
2539
2540                 public static int Sum (this IEnumerable<int> source)
2541                 {
2542                         Check.Source (source);
2543                         int total = 0;
2544
2545                         foreach (var element in source)
2546                                 total = checked (total + element);
2547                         return total;
2548                 }
2549
2550                 public static int? Sum (this IEnumerable<int?> source)
2551                 {
2552                         Check.Source (source);
2553
2554                         int total = 0;
2555                         foreach (var element in source) {
2556                                 if (element.HasValue)
2557                                         total = checked (total + element.Value);
2558                         }
2559                         return total;
2560                 }
2561
2562                 public static int Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, int> selector)
2563                 {
2564                         Check.SourceAndSelector (source, selector);
2565                         int total = 0;
2566
2567                         foreach (var element in source)
2568                                 total = checked (total + selector (element));
2569
2570                         return total;
2571                 }
2572
2573                 public static int? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, int?> selector)
2574                 {
2575                         Check.SourceAndSelector (source, selector);
2576
2577                         int total = 0;
2578                         foreach (var element in source) {
2579                                 var value = selector (element);
2580                                 if (value.HasValue)
2581                                         total = checked (total + value.Value);
2582                         }
2583                         return total;
2584                 }
2585
2586                 public static long Sum (this IEnumerable<long> source)
2587                 {
2588                         Check.Source (source);
2589
2590                         long total = 0;
2591
2592                         foreach (var element in source)
2593                                 total = checked (total + element);
2594                         return total;
2595                 }
2596
2597                 public static long? Sum (this IEnumerable<long?> source)
2598                 {
2599                         Check.Source (source);
2600
2601                         long total = 0;
2602                         foreach (var element in source) {
2603                                 if (element.HasValue)
2604                                         total = checked (total + element.Value);
2605                         }
2606                         return total;
2607                 }
2608
2609                 public static long Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, long> selector)
2610                 {
2611                         Check.SourceAndSelector (source, selector);
2612
2613                         long total = 0;
2614                         foreach (var element in source)
2615                                 total = checked (total + selector (element));
2616                         return total;
2617                 }
2618
2619                 public static long? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, long?> selector)
2620                 {
2621                         Check.SourceAndSelector (source, selector);
2622
2623                         long total = 0;
2624                         foreach (var element in source) {
2625                                 var value = selector (element);
2626                                 if (value.HasValue)
2627                                         total = checked (total + value.Value);
2628                         }
2629                         return total;
2630                 }
2631
2632                 public static double Sum (this IEnumerable<double> source)
2633                 {
2634                         Check.Source (source);
2635
2636                         double total = 0;
2637
2638                         foreach (var element in source)
2639                                 total = checked (total + element);
2640                         return total;
2641                 }
2642
2643                 public static double? Sum (this IEnumerable<double?> source)
2644                 {
2645                         Check.Source (source);
2646
2647                         double total = 0;
2648                         foreach (var element in source) {
2649                                 if (element.HasValue)
2650                                         total = checked (total + element.Value);
2651                         }
2652                         return total;
2653                 }
2654
2655                 public static double Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, double> selector)
2656                 {
2657                         Check.SourceAndSelector (source, selector);
2658
2659                         double total = 0;
2660
2661                         foreach (var element in source)
2662                                 total = checked (total + selector (element));
2663                         return total;
2664                 }
2665
2666                 public static double? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, double?> selector)
2667                 {
2668                         Check.SourceAndSelector (source, selector);
2669
2670                         double total = 0;
2671                         foreach (var element in source) {
2672                                 var value = selector (element);
2673                                 if (value.HasValue)
2674                                         total = checked (total + value.Value);
2675                         }
2676                         return total;
2677                 }
2678
2679                 public static float Sum (this IEnumerable<float> source)
2680                 {
2681                         Check.Source (source);
2682
2683                         float total = 0;
2684
2685                         foreach (var element in source)
2686                                 total = checked (total + element);
2687                         return total;
2688                 }
2689
2690                 public static float? Sum (this IEnumerable<float?> source)
2691                 {
2692                         Check.Source (source);
2693
2694                         float total = 0;
2695                         foreach (var element in source) {
2696                                 if (element.HasValue)
2697                                         total = checked (total + element.Value);
2698                         }
2699                         return total;
2700
2701                 }
2702
2703                 public static float Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, float> selector)
2704                 {
2705                         Check.SourceAndSelector (source, selector);
2706                         float total = 0;
2707                         foreach (var element in source)
2708                                 total = checked (total + selector (element));
2709                         return total;
2710                 }
2711
2712                 public static float? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, float?> selector)
2713                 {
2714                         Check.SourceAndSelector (source, selector);
2715
2716                         float total = 0;
2717                         foreach (var element in source) {
2718                                 var value = selector (element);
2719                                 if (value.HasValue)
2720                                         total = checked (total + value.Value);
2721                         }
2722                         return total;
2723                 }
2724
2725                 public static decimal Sum (this IEnumerable<decimal> source)
2726                 {
2727                         Check.Source (source);
2728                         decimal total = 0;
2729
2730                         foreach (var element in source)
2731                                 total = checked (total + element);
2732                         return total;
2733                 }
2734
2735                 public static decimal? Sum (this IEnumerable<decimal?> source)
2736                 {
2737                         Check.Source (source);
2738
2739                         decimal total = 0;
2740                         foreach (var element in source) {
2741                                 if (element.HasValue)
2742                                         total = checked (total + element.Value);
2743                         }
2744                         return total;
2745
2746                 }
2747
2748                 public static decimal Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal> selector)
2749                 {
2750                         Check.SourceAndSelector (source, selector);
2751                         decimal total = 0;
2752
2753                         foreach (var element in source)
2754                                 total = checked (total + selector (element));
2755                         return total;
2756                 }
2757
2758                 public static decimal? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal?> selector)
2759                 {
2760                         Check.SourceAndSelector (source, selector);
2761
2762                         decimal total = 0;
2763                         foreach (var element in source) {
2764                                 var value = selector (element);
2765                                 if (value.HasValue)
2766                                         total = checked (total + value.Value);
2767                         }
2768                         return total;
2769                 }
2770
2771                 #endregion
2772
2773                 #region Take
2774
2775                 public static IEnumerable<TSource> Take<TSource> (this IEnumerable<TSource> source, int count)
2776                 {
2777                         Check.Source (source);
2778
2779                         return CreateTakeIterator (source, count);
2780                 }
2781
2782                 static IEnumerable<TSource> CreateTakeIterator<TSource> (IEnumerable<TSource> source, int count)
2783                 {
2784                         if (count <= 0)
2785                                 yield break;
2786
2787                         int counter = 0;
2788                         foreach (TSource element in source) {
2789                                 yield return element;
2790
2791                                 if (++counter == count)
2792                                         yield break;
2793                         }
2794                 }
2795
2796                 #endregion
2797
2798                 #region TakeWhile
2799
2800                 public static IEnumerable<TSource> TakeWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2801                 {
2802                         Check.SourceAndPredicate (source, predicate);
2803
2804                         return CreateTakeWhileIterator (source, predicate);
2805                 }
2806
2807                 static IEnumerable<TSource> CreateTakeWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, bool> predicate)
2808                 {
2809                         foreach (var element in source) {
2810                                 if (!predicate (element))
2811                                         yield break;
2812
2813                                 yield return element;
2814                         }
2815                 }
2816
2817                 public static IEnumerable<TSource> TakeWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2818                 {
2819                         Check.SourceAndPredicate (source, predicate);
2820
2821                         return CreateTakeWhileIterator (source, predicate);
2822                 }
2823
2824                 static IEnumerable<TSource> CreateTakeWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2825                 {
2826                         int counter = 0;
2827                         foreach (var element in source) {
2828                                 if (!predicate (element, counter))
2829                                         yield break;
2830
2831                                 yield return element;
2832                                 counter++;
2833                         }
2834                 }
2835
2836                 #endregion
2837
2838                 #region ThenBy
2839
2840                 public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey> (this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector)
2841                 {
2842                         return ThenBy<TSource, TKey> (source, keySelector, null);
2843                 }
2844
2845                 public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey> (this IOrderedEnumerable<TSource> source,
2846                         Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
2847                 {
2848                         Check.SourceAndKeySelector (source, keySelector);
2849
2850 #if FULL_AOT_RUNTIME
2851                         var oe = source as OrderedEnumerable <TSource>;
2852                         if (oe != null)
2853                                 return oe.CreateOrderedEnumerable (keySelector, comparer, false);
2854 #endif
2855
2856                         return source.CreateOrderedEnumerable (keySelector, comparer, false);
2857                 }
2858
2859                 #endregion
2860
2861                 #region ThenByDescending
2862
2863                 public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey> (this IOrderedEnumerable<TSource> source,
2864                         Func<TSource, TKey> keySelector)
2865                 {
2866                         return ThenByDescending<TSource, TKey> (source, keySelector, null);
2867                 }
2868
2869                 public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey> (this IOrderedEnumerable<TSource> source,
2870                         Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
2871                 {
2872                         Check.SourceAndKeySelector (source, keySelector);
2873
2874 #if FULL_AOT_RUNTIME
2875                         var oe = source as OrderedEnumerable <TSource>;
2876                         if (oe != null)
2877                                 return oe.CreateOrderedEnumerable (keySelector, comparer, true);
2878 #endif
2879                         return source.CreateOrderedEnumerable (keySelector, comparer, true);
2880                 }
2881
2882                 #endregion
2883
2884                 #region ToArray
2885
2886                 public static TSource [] ToArray<TSource> (this IEnumerable<TSource> source)
2887                 {
2888                         Check.Source (source);
2889
2890                         TSource[] array;
2891                         var collection = source as ICollection<TSource>;
2892                         if (collection != null) {
2893                                 if (collection.Count == 0)
2894                                         return EmptyOf<TSource>.Instance;
2895
2896                                 array = new TSource [collection.Count];
2897                                 collection.CopyTo (array, 0);
2898                                 return array;
2899                         }
2900
2901                         int pos = 0;
2902                         array = EmptyOf<TSource>.Instance;
2903                         foreach (var element in source) {
2904                                 if (pos == array.Length) {
2905                                         if (pos == 0)
2906                                                 array = new TSource [4];
2907                                         else
2908                                                 Array.Resize (ref array, pos * 2);
2909                                 }
2910
2911                                 array[pos++] = element;
2912                         }
2913
2914                         if (pos != array.Length)
2915                                 Array.Resize (ref array, pos);
2916
2917                         return array;
2918                 }
2919
2920                 #endregion
2921
2922                 #region ToDictionary
2923                 public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2924                                 Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector)
2925                 {
2926                         return ToDictionary<TSource, TKey, TElement> (source, keySelector, elementSelector, null);
2927                 }
2928
2929                 public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2930                                 Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
2931                 {
2932                         Check.SourceAndKeyElementSelectors (source, keySelector, elementSelector);
2933
2934                         if (comparer == null)
2935                                 comparer = EqualityComparer<TKey>.Default;
2936
2937                         var dict = new Dictionary<TKey, TElement> (comparer);
2938                         foreach (var e in source)
2939                                 dict.Add (keySelector (e), elementSelector (e));
2940
2941                         return dict;
2942                 }
2943
2944                 public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey> (this IEnumerable<TSource> source,
2945                                 Func<TSource, TKey> keySelector)
2946                 {
2947                         return ToDictionary (source, keySelector, null);
2948                 }
2949
2950                 public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey> (this IEnumerable<TSource> source,
2951                                 Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
2952                 {
2953                         return ToDictionary<TSource, TKey, TSource> (source, keySelector, Function<TSource>.Identity, comparer);
2954                 }
2955
2956                 #endregion
2957
2958                 #region ToList
2959                 public static List<TSource> ToList<TSource> (this IEnumerable<TSource> source)
2960                 {
2961                         Check.Source (source);
2962
2963                         return new List<TSource> (source);
2964                 }
2965                 #endregion
2966
2967                 #region ToLookup
2968
2969                 public static ILookup<TKey, TSource> ToLookup<TSource, TKey> (this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
2970                 {
2971                         return ToLookup<TSource, TKey, TSource> (source, keySelector, Function<TSource>.Identity, null);
2972                 }
2973
2974                 public static ILookup<TKey, TSource> ToLookup<TSource, TKey> (this IEnumerable<TSource> source,
2975                         Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
2976                 {
2977                         return ToLookup<TSource, TKey, TSource> (source, keySelector, Function<TSource>.Identity, comparer);
2978                 }
2979
2980                 public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2981                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector)
2982                 {
2983                         return ToLookup<TSource, TKey, TElement> (source, keySelector, elementSelector, null);
2984                 }
2985
2986                 public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2987                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
2988                 {
2989                         Check.SourceAndKeyElementSelectors (source, keySelector, elementSelector);
2990
2991                         List<TElement> nullKeyElements = null;
2992
2993                         var dictionary = new Dictionary<TKey, List<TElement>> (comparer ?? EqualityComparer<TKey>.Default);
2994                         foreach (var element in source) {
2995                                 var key = keySelector (element);
2996
2997                                 List<TElement> list;
2998
2999                                 if (key == null) {
3000                                         if (nullKeyElements == null)
3001                                                 nullKeyElements = new List<TElement> ();
3002
3003                                         list = nullKeyElements;
3004                                 } else if (!dictionary.TryGetValue (key, out list)) {
3005                                         list = new List<TElement> ();
3006                                         dictionary.Add (key, list);
3007                                 }
3008
3009                                 list.Add (elementSelector (element));
3010                         }
3011
3012                         return new Lookup<TKey, TElement> (dictionary, nullKeyElements);
3013                 }
3014
3015                 #endregion
3016
3017                 #region SequenceEqual
3018
3019                 public static bool SequenceEqual<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
3020                 {
3021                         return first.SequenceEqual (second, null);
3022                 }
3023
3024                 public static bool SequenceEqual<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
3025                 {
3026                         Check.FirstAndSecond (first, second);
3027
3028                         if (comparer == null)
3029                                 comparer = EqualityComparer<TSource>.Default;
3030
3031                         using (IEnumerator<TSource> first_enumerator = first.GetEnumerator (),
3032                                 second_enumerator = second.GetEnumerator ()) {
3033
3034                                 while (first_enumerator.MoveNext ()) {
3035                                         if (!second_enumerator.MoveNext ())
3036                                                 return false;
3037
3038                                         if (!comparer.Equals (first_enumerator.Current, second_enumerator.Current))
3039                                                 return false;
3040                                 }
3041
3042                                 return !second_enumerator.MoveNext ();
3043                         }
3044                 }
3045
3046                 #endregion
3047
3048                 #region Union
3049
3050                 public static IEnumerable<TSource> Union<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
3051                 {
3052                         Check.FirstAndSecond (first, second);
3053
3054                         return first.Union (second, null);
3055                 }
3056
3057                 public static IEnumerable<TSource> Union<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
3058                 {
3059                         Check.FirstAndSecond (first, second);
3060
3061                         if (comparer == null)
3062                                 comparer = EqualityComparer<TSource>.Default;
3063
3064                         return CreateUnionIterator (first, second, comparer);
3065                 }
3066
3067                 static IEnumerable<TSource> CreateUnionIterator<TSource> (IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
3068                 {
3069                         var items = new HashSet<TSource> (comparer);
3070                         foreach (var element in first) {
3071                                 if (! items.Contains (element)) {
3072                                         items.Add (element);
3073                                         yield return element;
3074                                 }
3075                         }
3076
3077                         foreach (var element in second) {
3078                                 if (! items.Contains (element)) {
3079                                         items.Add (element);
3080                                         yield return element;
3081                                 }
3082                         }
3083                 }
3084
3085                 #endregion
3086
3087 #if NET_4_0
3088                 #region Zip
3089
3090                 public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult> (this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector)
3091                 {
3092                         Check.FirstAndSecond (first, second);
3093                         if (resultSelector == null)
3094                                 throw new ArgumentNullException ("resultSelector");
3095
3096                         return CreateZipIterator (first, second, resultSelector);
3097                 }
3098
3099                 static IEnumerable<TResult> CreateZipIterator<TFirst, TSecond, TResult> (IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> selector)
3100                 {
3101                         using (IEnumerator<TFirst> first_enumerator = first.GetEnumerator ()) {
3102                                 using (IEnumerator<TSecond> second_enumerator = second.GetEnumerator ()) {
3103
3104                                         while (first_enumerator.MoveNext () && second_enumerator.MoveNext ()) {
3105                                                 yield return selector (first_enumerator.Current, second_enumerator.Current);
3106                                         }
3107                                 }
3108                         }
3109                 }
3110
3111                 #endregion
3112 #endif
3113
3114                 #region Where
3115
3116                 public static IEnumerable<TSource> Where<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
3117                 {
3118                         Check.SourceAndPredicate (source, predicate);
3119
3120                         // It cannot be IList<TSource> because it may break on user implementation
3121                         var array = source as TSource[];
3122                         if (array != null)
3123                                 return CreateWhereIterator (array, predicate);
3124
3125                         return CreateWhereIterator (source, predicate);
3126                 }
3127
3128                 static IEnumerable<TSource> CreateWhereIterator<TSource> (IEnumerable<TSource> source, Func<TSource, bool> predicate)
3129                 {
3130                         foreach (TSource element in source)
3131                                 if (predicate (element))
3132                                         yield return element;
3133                 }
3134
3135                 static IEnumerable<TSource> CreateWhereIterator<TSource> (TSource[] source, Func<TSource, bool> predicate)
3136                 {
3137                         for (int i = 0; i < source.Length; ++i) {
3138                                 var element = source [i];
3139                                 if (predicate (element))
3140                                         yield return element;
3141                         }
3142                 }
3143
3144                 public static IEnumerable<TSource> Where<TSource> (this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
3145                 {
3146                         Check.SourceAndPredicate (source, predicate);
3147
3148                         var array = source as TSource[];
3149                         if (array != null)
3150                                 return CreateWhereIterator (array, predicate);
3151
3152                         return CreateWhereIterator (source, predicate);
3153                 }
3154
3155                 static IEnumerable<TSource> CreateWhereIterator<TSource> (IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
3156                 {
3157                         int counter = 0;
3158                         foreach (TSource element in source) {
3159                                 if (predicate (element, counter))
3160                                         yield return element;
3161                                 counter++;
3162                         }
3163                 }
3164
3165                 static IEnumerable<TSource> CreateWhereIterator<TSource> (TSource[] source, Func<TSource, int, bool> predicate)
3166                 {
3167                         for (int i = 0; i < source.Length; ++i) {
3168                                 var element = source [i];
3169                                 if (predicate (element, i))
3170                                         yield return element;
3171                         }
3172                 }
3173
3174                 #endregion
3175
3176                 internal static ReadOnlyCollection<TSource> ToReadOnlyCollection<TSource> (this IEnumerable<TSource> source)
3177                 {
3178                         if (source == null)
3179                                 return ReadOnlyCollectionOf<TSource>.Empty;
3180
3181                         var ro = source as ReadOnlyCollection<TSource>;
3182                         if (ro != null)
3183                                 return ro;
3184
3185                         return new ReadOnlyCollection<TSource> (source.ToArray<TSource> ());
3186                 }
3187
3188                 #region Exception helpers
3189
3190                 static Exception EmptySequence ()
3191                 {
3192                         return new InvalidOperationException (Locale.GetText ("Sequence contains no elements"));
3193                 }
3194                 static Exception NoMatchingElement ()
3195                 {
3196                         return new InvalidOperationException (Locale.GetText ("Sequence contains no matching element"));
3197                 }
3198                 static Exception MoreThanOneElement ()
3199                 {
3200                         return new InvalidOperationException (Locale.GetText ("Sequence contains more than one element"));
3201                 }
3202                 static Exception MoreThanOneMatchingElement ()
3203                 {
3204                         return new InvalidOperationException (Locale.GetText ("Sequence contains more than one matching element"));
3205                 }
3206
3207                 #endregion
3208         }
3209 }