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                 public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey> (this IEnumerable<TSource> source,
 889                         Func<TSource, TKey> keySelector)
 890                 {
 891                         return GroupBy<TSource, TKey> (source, keySelector, null);
 892                 }
 893
 894                 public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey> (this IEnumerable<TSource> source,
 895                         Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
 896                 {
 897                         Check.SourceAndKeySelector (source, keySelector);
 898
 899                         return CreateGroupByIterator (source, keySelector, comparer);
 900                 }
 901
 902                 static IEnumerable<IGrouping<TKey, TSource>> CreateGroupByIterator<TSource, TKey> (this IEnumerable<TSource> source,
 903                         Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
 904                 {
 905                         var groups = new Dictionary<TKey, List<TSource>> (comparer);
 906                         var nullList = new List<TSource> ();
 907                         int counter = 0;
 908                         int nullCounter = -1;
 909
 910                         foreach (TSource element in source) {
 911                                 TKey key = keySelector (element);
 912                                 if (key == null) {
 913                                         nullList.Add (element);
 914                                         if (nullCounter == -1) {
 915                                                 nullCounter = counter;
 916                                                 counter++;
 917                                         }
 918                                 } else {
 919                                         List<TSource> group;
 920                                         if (!groups.TryGetValue (key, out group)) {
 921                                                 group = new List<TSource> ();
 922                                                 groups.Add (key, group);
 923                                                 counter++;
 924                                         }
 925                                         group.Add (element);
 926                                 }
 927                         }
 928
 929                         counter = 0;
 930                         foreach (var group in groups) {
 931                                 if (counter == nullCounter) {
 932                                         yield return new Grouping<TKey, TSource> (default (TKey), nullList);
 933                                         counter++;
 934                                 }
 935
 936                                 yield return new Grouping<TKey, TSource> (group.Key, group.Value);
 937                                 counter++;
 938                         }
 939
 940                         if (counter == nullCounter) {
 941                                 yield return new Grouping<TKey, TSource> (default (TKey), nullList);
 942                                 counter++;
 943                         }
 944                 }
 945
 946                 public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement> (this IEnumerable<TSource> source,
 947                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector)
 948                 {
 949                         return GroupBy<TSource, TKey, TElement> (source, keySelector, elementSelector, null);
 950                 }
 951
 952                 public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement> (this IEnumerable<TSource> source,
 953                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
 954                 {
 955                         Check.SourceAndKeyElementSelectors (source, keySelector, elementSelector);
 956
 957                         return CreateGroupByIterator (source, keySelector, elementSelector, comparer);
 958                 }
 959
 960                 static IEnumerable<IGrouping<TKey, TElement>> CreateGroupByIterator<TSource, TKey, TElement> (this IEnumerable<TSource> source,
 961                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
 962                 {
 963                         var groups = new Dictionary<TKey, List<TElement>> (comparer);
 964                         var nullList = new List<TElement> ();
 965                         int counter = 0;
 966                         int nullCounter = -1;
 967
 968                         foreach (TSource item in source) {
 969                                 TKey key = keySelector (item);
 970                                 TElement element = elementSelector (item);
 971                                 if (key == null) {
 972                                         nullList.Add (element);
 973                                         if (nullCounter == -1) {
 974                                                 nullCounter = counter;
 975                                                 counter++;
 976                                         }
 977                                 } else {
 978                                         List<TElement> group;
 979                                         if (!groups.TryGetValue (key, out group)) {
 980                                                 group = new List<TElement> ();
 981                                                 groups.Add (key, group);
 982                                                 counter++;
 983                                         }
 984                                         group.Add (element);
 985                                 }
 986                         }
 987
 988                         counter = 0;
 989                         foreach (var group in groups) {
 990                                 if (counter == nullCounter) {
 991                                         yield return new Grouping<TKey, TElement> (default (TKey), nullList);
 992                                         counter++;
 993                                 }
 994
 995                                 yield return new Grouping<TKey, TElement> (group.Key, group.Value);
 996                                 counter++;
 997                         }
 998
 999                         if (counter == nullCounter) {
1000                                 yield return new Grouping<TKey, TElement> (default (TKey), nullList);
1001                                 counter++;
1002                         }
1003                 }
1004
1005                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult> (this IEnumerable<TSource> source,
1006                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector,
1007                         Func<TKey, IEnumerable<TElement>, TResult> resultSelector)
1008                 {
1009                         return GroupBy (source, keySelector, elementSelector, resultSelector, null);
1010                 }
1011
1012                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult> (this IEnumerable<TSource> source,
1013                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector,
1014                         Func<TKey, IEnumerable<TElement>, TResult> resultSelector,
1015                         IEqualityComparer<TKey> comparer)
1016                 {
1017                         Check.GroupBySelectors (source, keySelector, elementSelector, resultSelector);
1018
1019                         return CreateGroupByIterator (source, keySelector, elementSelector, resultSelector, comparer);
1020                 }
1021
1022                 static IEnumerable<TResult> CreateGroupByIterator<TSource, TKey, TElement, TResult> (this IEnumerable<TSource> source,
1023                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector,
1024                         Func<TKey, IEnumerable<TElement>, TResult> resultSelector,
1025                         IEqualityComparer<TKey> comparer)
1026                 {
1027                         IEnumerable<IGrouping<TKey, TElement>> groups = GroupBy<TSource, TKey, TElement> (
1028                                 source, keySelector, elementSelector, comparer);
1029
1030                         foreach (IGrouping<TKey, TElement> group in groups)
1031                                 yield return resultSelector (group.Key, group);
1032                 }
1033
1034                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult> (this IEnumerable<TSource> source,
1035                         Func<TSource, TKey> keySelector,
1036                         Func<TKey, IEnumerable<TSource>, TResult> resultSelector)
1037                 {
1038                         return GroupBy (source, keySelector, resultSelector, null);
1039                 }
1040
1041                 public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult> (this IEnumerable<TSource> source,
1042                         Func<TSource, TKey> keySelector,
1043                         Func<TKey, IEnumerable<TSource>, TResult> resultSelector,
1044                         IEqualityComparer<TKey> comparer)
1045                 {
1046                         Check.SourceAndKeyResultSelectors (source, keySelector, resultSelector);
1047
1048                         return CreateGroupByIterator (source, keySelector, resultSelector, comparer);
1049                 }
1050
1051                 static IEnumerable<TResult> CreateGroupByIterator<TSource, TKey, TResult> (this IEnumerable<TSource> source,
1052                         Func<TSource, TKey> keySelector,
1053                         Func<TKey, IEnumerable<TSource>, TResult> resultSelector,
1054                         IEqualityComparer<TKey> comparer)
1055                 {
1056                         IEnumerable<IGrouping<TKey,TSource>> groups = GroupBy<TSource, TKey> (source, keySelector, comparer);
1057
1058                         foreach (IGrouping<TKey, TSource> group in groups)
1059                                 yield return resultSelector (group.Key, group);
1060                 }
1061
1062                 #endregion
1063
1064                 # region GroupJoin
1065
1066                 public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1067                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1068                         Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector)
1069                 {
1070                         return GroupJoin (outer, inner, outerKeySelector, innerKeySelector, resultSelector, null);
1071                 }
1072
1073                 public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1074                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1075                         Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector,
1076                         IEqualityComparer<TKey> comparer)
1077                 {
1078                         Check.JoinSelectors (outer, inner, outerKeySelector, innerKeySelector, resultSelector);
1079
1080                         if (comparer == null)
1081                                 comparer = EqualityComparer<TKey>.Default;
1082
1083                         return CreateGroupJoinIterator (outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
1084                 }
1085
1086                 static IEnumerable<TResult> CreateGroupJoinIterator<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1087                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1088                         Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector,
1089                         IEqualityComparer<TKey> comparer)
1090                 {
1091                         ILookup<TKey, TInner> innerKeys = ToLookup<TInner, TKey> (inner, innerKeySelector, comparer);
1092                         /*Dictionary<K, List<U>> innerKeys = new Dictionary<K, List<U>> ();
1093                         foreach (U element in inner)
1094                         {
1095                                         K innerKey = innerKeySelector (element);
1096                                         if (!innerKeys.ContainsKey (innerKey))
1097                                                         innerKeys.Add (innerKey, new List<U> ());
1098                                         innerKeys[innerKey].Add (element);
1099                         }*/
1100
1101                         foreach (TOuter element in outer) {
1102                                 TKey outerKey = outerKeySelector (element);
1103                                 if (outerKey != null && innerKeys.Contains (outerKey))
1104                                         yield return resultSelector (element, innerKeys [outerKey]);
1105                                 else
1106                                         yield return resultSelector (element, Empty<TInner> ());
1107                         }
1108                 }
1109
1110                 #endregion
1111
1112                 #region Intersect
1113
1114                 public static IEnumerable<TSource> Intersect<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
1115                 {
1116                         return Intersect (first, second, null);
1117                 }
1118
1119                 public static IEnumerable<TSource> Intersect<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
1120                 {
1121                         Check.FirstAndSecond (first, second);
1122
1123                         if (comparer == null)
1124                                 comparer = EqualityComparer<TSource>.Default;
1125
1126                         return CreateIntersectIterator (first, second, comparer);
1127                 }
1128
1129                 static IEnumerable<TSource> CreateIntersectIterator<TSource> (IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
1130                 {
1131                         var items = new HashSet<TSource> (second, comparer);
1132                         foreach (TSource element in first) {
1133                                 if (items.Remove (element))
1134                                         yield return element;
1135                         }
1136                 }
1137
1138                 #endregion
1139
1140                 # region Join
1141
1142                 public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1143                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1144                         Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey> comparer)
1145                 {
1146                         Check.JoinSelectors (outer, inner, outerKeySelector, innerKeySelector, resultSelector);
1147
1148                         if (comparer == null)
1149                                 comparer = EqualityComparer<TKey>.Default;
1150
1151                         return CreateJoinIterator (outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
1152                 }
1153
1154                 static IEnumerable<TResult> CreateJoinIterator<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1155                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1156                         Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey> comparer)
1157                 {
1158                         ILookup<TKey, TInner> innerKeys = ToLookup<TInner, TKey> (inner, innerKeySelector, comparer);
1159                         /*Dictionary<K, List<U>> innerKeys = new Dictionary<K, List<U>> ();
1160                         foreach (U element in inner)
1161                         {
1162                                         K innerKey = innerKeySelector (element);
1163                                         if (!innerKeys.ContainsKey (innerKey))
1164                                                         innerKeys.Add (innerKey, new List<U> ());
1165                                         innerKeys[innerKey].Add (element);
1166                         }*/
1167
1168                         foreach (TOuter element in outer) {
1169                                 TKey outerKey = outerKeySelector (element);
1170                                 if (outerKey != null && innerKeys.Contains (outerKey)) {
1171                                         foreach (TInner innerElement in innerKeys [outerKey])
1172                                                 yield return resultSelector (element, innerElement);
1173                                 }
1174                         }
1175                 }
1176
1177                 public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult> (this IEnumerable<TOuter> outer,
1178                         IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector,
1179                         Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector)
1180                 {
1181                         return outer.Join (inner, outerKeySelector, innerKeySelector, resultSelector, null);
1182                 }
1183
1184                 #endregion
1185
1186                 #region Last
1187
1188                 static TSource Last<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate, Fallback fallback)
1189                 {
1190                         var empty = true;
1191                         var item = default (TSource);
1192
1193                         foreach (var element in source) {
1194                                 if (!predicate (element))
1195                                         continue;
1196
1197                                 item = element;
1198                                 empty = false;
1199                         }
1200
1201                         if (!empty)
1202                                 return item;
1203
1204                         if (fallback == Fallback.Throw)
1205                                 throw NoMatchingElement ();
1206
1207                         return item;
1208                 }
1209
1210                 public static TSource Last<TSource> (this IEnumerable<TSource> source)
1211                 {
1212                         Check.Source (source);
1213
1214                         var collection = source as ICollection<TSource>;
1215                         if (collection != null && collection.Count == 0)
1216                                 throw EmptySequence ();
1217
1218                         var list = source as IList<TSource>;
1219                         if (list != null)
1220                                 return list [list.Count - 1];
1221
1222 #if !FULL_AOT_RUNTIME
1223                         return source.Last (PredicateOf<TSource>.Always, Fallback.Throw);
1224 #else
1225                         var empty = true;
1226                         var item = default (TSource);
1227
1228                         foreach (var element in source) {
1229                                 item = element;
1230                                 empty = false;
1231                         }
1232
1233                         if (!empty)
1234                                 return item;
1235
1236                         throw EmptySequence ();
1237 #endif
1238         }
1239
1240                 public static TSource Last<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
1241                 {
1242                         Check.SourceAndPredicate (source, predicate);
1243
1244                         return source.Last (predicate, Fallback.Throw);
1245                 }
1246
1247                 #endregion
1248
1249                 #region LastOrDefault
1250
1251                 public static TSource LastOrDefault<TSource> (this IEnumerable<TSource> source)
1252                 {
1253                         Check.Source (source);
1254
1255                         var list = source as IList<TSource>;
1256                         if (list != null)
1257                                 return list.Count > 0 ? list [list.Count - 1] : default (TSource);
1258
1259 #if !FULL_AOT_RUNTIME
1260                         return source.Last (PredicateOf<TSource>.Always, Fallback.Default);
1261 #else
1262                         var empty = true;
1263                         var item = default (TSource);
1264
1265                         foreach (var element in source) {
1266                                 item = element;
1267                                 empty = false;
1268                         }
1269
1270                         if (!empty)
1271                                 return item;
1272
1273                         return item;
1274 #endif
1275                 }
1276
1277                 public static TSource LastOrDefault<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
1278                 {
1279                         Check.SourceAndPredicate (source, predicate);
1280
1281                         return source.Last (predicate, Fallback.Default);
1282                 }
1283
1284                 #endregion
1285
1286                 #region LongCount
1287
1288                 public static long LongCount<TSource> (this IEnumerable<TSource> source)
1289                 {
1290                         Check.Source (source);
1291
1292 #if !NET_2_1
1293                         var array = source as TSource [];
1294                         if (array != null)
1295                                 return array.LongLength;
1296 #endif
1297
1298                         long counter = 0;
1299                         using (var enumerator = source.GetEnumerator ())
1300                                 while (enumerator.MoveNext ())
1301                                         counter++;
1302
1303                         return counter;
1304                 }
1305
1306                 public static long LongCount<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
1307                 {
1308                         Check.SourceAndSelector (source, predicate);
1309
1310                         long counter = 0;
1311                         foreach (TSource element in source)
1312                                 if (predicate (element))
1313                                         counter++;
1314
1315                         return counter;
1316                 }
1317
1318                 #endregion
1319
1320                 #region Max
1321
1322                 public static int Max (this IEnumerable<int> source)
1323                 {
1324                         Check.Source (source);
1325
1326                         bool empty = true;
1327                         var max = int.MinValue;
1328                         foreach (var element in source){
1329                                 max = Math.Max (element, max);
1330                                 empty = false;
1331                         }
1332                         if (empty)
1333                                 throw EmptySequence();
1334                         return max;
1335                 }
1336
1337                 public static long Max (this IEnumerable<long> source)
1338                 {
1339                         Check.Source (source);
1340
1341                         bool empty = true;
1342                         var max = long.MinValue;
1343                         foreach (var element in source){
1344                                 max = Math.Max (element, max);
1345                                 empty = false;
1346                         }
1347                         if (empty)
1348                                 throw EmptySequence ();
1349                         return max;
1350                 }
1351
1352                 public static double Max (this IEnumerable<double> source)
1353                 {
1354                         Check.Source (source);
1355
1356                         bool empty = true;
1357                         var max = double.MinValue;
1358                         foreach (var element in source){
1359                                 max = Math.Max (element, max);
1360                                 empty = false;
1361                         }
1362                         if (empty)
1363                                 throw EmptySequence ();
1364                         return max;
1365                 }
1366
1367                 public static float Max (this IEnumerable<float> source)
1368                 {
1369                         Check.Source (source);
1370
1371                         bool empty = true;
1372                         var max = float.MinValue;
1373                         foreach (var element in source){
1374                                 max = Math.Max (element, max);
1375                                 empty = false;
1376                         }
1377                         if (empty)
1378                                 throw EmptySequence ();
1379                         return max;
1380                 }
1381
1382                 public static decimal Max (this IEnumerable<decimal> source)
1383                 {
1384                         Check.Source (source);
1385
1386                         bool empty = true;
1387                         var max = decimal.MinValue;
1388                         foreach (var element in source){
1389                                 max = Math.Max (element, max);
1390                                 empty = false;
1391                         }
1392                         if (empty)
1393                                 throw EmptySequence ();
1394                         return max;
1395                 }
1396
1397                 public static int? Max (this IEnumerable<int?> source)
1398                 {
1399                         Check.Source (source);
1400
1401                         bool empty = true;
1402                         var max = int.MinValue;
1403
1404                         foreach (var element in source) {
1405                                 if (!element.HasValue)
1406                                         continue;
1407
1408                                 max = Math.Max (element.Value, max);
1409                                 empty = false;
1410                         }
1411
1412                         if (empty)
1413                                 return null;
1414
1415                         return max;
1416                 }
1417
1418                 public static long? Max (this IEnumerable<long?> source)
1419                 {
1420                         Check.Source (source);
1421
1422                         bool empty = true;
1423                         var max = long.MinValue;
1424
1425                         foreach (var element in source) {
1426                                 if (!element.HasValue)
1427                                         continue;
1428
1429                                 max = Math.Max (element.Value, max);
1430                                 empty = false;
1431                         }
1432
1433                         if (empty)
1434                                 return null;
1435
1436                         return max;
1437                 }
1438
1439                 public static double? Max (this IEnumerable<double?> source)
1440                 {
1441                         Check.Source (source);
1442
1443                         bool empty = true;
1444                         var max = double.MinValue;
1445
1446                         foreach (var element in source) {
1447                                 if (!element.HasValue)
1448                                         continue;
1449
1450                                 max = Math.Max (element.Value, max);
1451                                 empty = false;
1452                         }
1453
1454                         if (empty)
1455                                 return null;
1456
1457                         return max;
1458                 }
1459
1460                 public static float? Max (this IEnumerable<float?> source)
1461                 {
1462                         Check.Source (source);
1463
1464                         bool empty = true;
1465                         var max = float.MinValue;
1466
1467                         foreach (var element in source) {
1468                                 if (!element.HasValue)
1469                                         continue;
1470
1471                                 max = Math.Max (element.Value, max);
1472                                 empty = false;
1473                         }
1474
1475                         if (empty)
1476                                 return null;
1477
1478                         return max;
1479                 }
1480
1481                 public static decimal? Max (this IEnumerable<decimal?> source)
1482                 {
1483                         Check.Source (source);
1484
1485                         bool empty = true;
1486                         var max = decimal.MinValue;
1487
1488                         foreach (var element in source) {
1489                                 if (!element.HasValue)
1490                                         continue;
1491
1492                                 max = Math.Max (element.Value, max);
1493                                 empty = false;
1494                         }
1495
1496                         if (empty)
1497                                 return null;
1498
1499                         return max;
1500                 }
1501
1502                 // TODO: test nullable and non-nullable
1503                 public static TSource Max<TSource> (this IEnumerable<TSource> source)
1504                 {
1505                         Check.Source (source);
1506
1507                         var comparer = Comparer<TSource>.Default;
1508
1509                         TSource max = default (TSource);
1510
1511                         if (default (TSource) == null){
1512                                 foreach (var element in source) {
1513                                         if (element == null)
1514                                                 continue;
1515
1516                                         if (max == null || comparer.Compare (element, max) > 0)
1517                                                 max = element;
1518                                 }
1519                         } else {
1520                                 bool empty = true;
1521                                 foreach (var element in source) {
1522                                         if (empty){
1523                                                 max = element;
1524                                                 empty = false;
1525                                                 continue;
1526                                         }
1527                                         if (comparer.Compare (element, max) > 0)
1528                                                 max = element;
1529                                 }
1530                                 if (empty)
1531                                         throw EmptySequence ();
1532                         }
1533                         return max;
1534                 }
1535
1536                 public static int Max<TSource> (this IEnumerable<TSource> source, Func<TSource, int> selector)
1537                 {
1538                         Check.SourceAndSelector (source, selector);
1539
1540                         bool empty = true;
1541                         var max = int.MinValue;
1542                         foreach (var element in source){
1543                                 max = Math.Max (selector (element), max);
1544                                 empty = false;
1545                         }
1546                         if (empty)
1547                                 throw NoMatchingElement ();
1548                         return max;
1549                 }
1550
1551                 public static long Max<TSource> (this IEnumerable<TSource> source, Func<TSource, long> selector)
1552                 {
1553                         Check.SourceAndSelector (source, selector);
1554
1555                         bool empty = true;
1556                         var max = long.MinValue;
1557                         foreach (var element in source){
1558                                 max = Math.Max (selector (element), max);
1559                                 empty = false;
1560                         }
1561                         if (empty)
1562                                 throw NoMatchingElement ();
1563                         return max;
1564                 }
1565
1566                 public static double Max<TSource> (this IEnumerable<TSource> source, Func<TSource, double> selector)
1567                 {
1568                         Check.SourceAndSelector (source, selector);
1569
1570                         bool empty = true;
1571                         var max = double.MinValue;
1572                         foreach (var element in source){
1573                                 max = Math.Max (selector (element), max);
1574                                 empty = false;
1575                         }
1576                         if (empty)
1577                                 throw NoMatchingElement ();
1578                         return max;
1579                 }
1580
1581                 public static float Max<TSource> (this IEnumerable<TSource> source, Func<TSource, float> selector)
1582                 {
1583                         Check.SourceAndSelector (source, selector);
1584
1585                         bool empty = true;
1586                         var max = float.MinValue;
1587                         foreach (var element in source){
1588                                 max = Math.Max (selector (element), max);
1589                                 empty = false;
1590                         }
1591                         if (empty)
1592                                 throw NoMatchingElement ();
1593                         return max;
1594                 }
1595
1596                 public static decimal Max<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal> selector)
1597                 {
1598                         Check.SourceAndSelector (source, selector);
1599
1600                         bool empty = true;
1601                         var max = decimal.MinValue;
1602                         foreach (var element in source){
1603                                 max = Math.Max (selector (element), max);
1604                                 empty = false;
1605                         }
1606                         if (empty)
1607                                 throw NoMatchingElement ();
1608                         return max;
1609                 }
1610
1611                 static U Iterate<T, U> (IEnumerable<T> source, U initValue, Func<T, U, U> selector)
1612                 {
1613                         bool empty = true;
1614                         foreach (var element in source) {
1615                                 initValue = selector (element, initValue);
1616                                 empty = false;
1617                         }
1618
1619                         if (empty)
1620                                 throw NoMatchingElement ();
1621
1622                         return initValue;
1623                 }
1624
1625                 public static int? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, int?> selector)
1626                 {
1627                         Check.SourceAndSelector (source, selector);
1628
1629                         bool empty = true;
1630                         int? max = null;
1631                         foreach (var element in source) {
1632                                 int? item = selector (element);
1633
1634                                 if (!max.HasValue)
1635                                         max = item;
1636                                 else if (item > max)
1637                                         max = item;
1638                                 empty = false;
1639                         }
1640
1641                         if (empty)
1642                                 return null;
1643                         return max;
1644                 }
1645
1646                 public static long? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, long?> selector)
1647                 {
1648                         Check.SourceAndSelector (source, selector);
1649
1650                         bool empty = true;
1651                         long? max = null;
1652                         foreach (var element in source) {
1653                                 long? item = selector (element);
1654
1655                                 if (!max.HasValue)
1656                                         max = item;
1657                                 else if (item > max)
1658                                         max = item;
1659                                 empty = false;
1660                         }
1661
1662                         if (empty)
1663                                 return null;
1664                         return max;
1665                 }
1666
1667                 public static double? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, double?> selector)
1668                 {
1669                         Check.SourceAndSelector (source, selector);
1670
1671                         bool empty = true;
1672                         double? max = null;
1673                         foreach (var element in source) {
1674                                 double? item = selector (element);
1675
1676                                 if (!max.HasValue)
1677                                         max = item;
1678                                 else if (item > max)
1679                                         max = item;
1680                                 empty = false;
1681                         }
1682
1683                         if (empty)
1684                                 return null;
1685                         return max;
1686                 }
1687
1688                 public static float? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, float?> selector)
1689                 {
1690                         Check.SourceAndSelector (source, selector);
1691
1692                         bool empty = true;
1693                         float? max = null;
1694                         foreach (var element in source) {
1695                                 float? item = selector (element);
1696
1697                                 if (!max.HasValue)
1698                                         max = item;
1699                                 else if (item > max)
1700                                         max = item;
1701                                 empty = false;
1702                         }
1703
1704                         if (empty)
1705                                 return null;
1706                         return max;
1707                 }
1708
1709                 public static decimal? Max<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal?> selector)
1710                 {
1711                         Check.SourceAndSelector (source, selector);
1712
1713                         bool empty = true;
1714                         decimal? max = null;
1715                         foreach (var element in source) {
1716                                 decimal? item = selector (element);
1717
1718                                 if (!max.HasValue)
1719                                         max = item;
1720                                 else if (item > max)
1721                                         max = item;
1722                                 empty = false;
1723                         }
1724
1725                         if (empty)
1726                                 return null;
1727                         return max;
1728                 }
1729
1730                 public static TResult Max<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, TResult> selector)
1731                 {
1732                         Check.SourceAndSelector (source, selector);
1733
1734                         // TODO: inline
1735                         return source.Select (selector).Max ();
1736                 }
1737
1738                 #endregion
1739
1740                 #region Min
1741
1742                 public static int Min (this IEnumerable<int> source)
1743                 {
1744                         Check.Source (source);
1745
1746                         bool empty = true;
1747                         var min = int.MaxValue;
1748                         foreach (var element in source){
1749                                 min = Math.Min (element, min);
1750                                 empty = false;
1751                         }
1752                         if (empty)
1753                                 throw EmptySequence ();
1754                         return min;
1755                 }
1756
1757                 public static long Min (this IEnumerable<long> source)
1758                 {
1759                         Check.Source (source);
1760
1761                         bool empty = true;
1762                         var min = long.MaxValue;
1763                         foreach (var element in source){
1764                                 min = Math.Min (element, min);
1765                                 empty = false;
1766                         }
1767                         if (empty)
1768                                 throw EmptySequence ();
1769                         return min;
1770                 }
1771
1772                 public static double Min (this IEnumerable<double> source)
1773                 {
1774                         Check.Source (source);
1775
1776                         bool empty = true;
1777                         var min = double.MaxValue;
1778                         foreach (var element in source){
1779                                 min = Math.Min (element, min);
1780                                 empty = false;
1781                         }
1782                         if (empty)
1783                                 throw EmptySequence ();
1784                         return min;
1785                 }
1786
1787                 public static float Min (this IEnumerable<float> source)
1788                 {
1789                         Check.Source (source);
1790
1791                         bool empty = true;
1792                         var min = float.MaxValue;
1793                         foreach (var element in source){
1794                                 min = Math.Min (element, min);
1795                                 empty = false;
1796                         }
1797                         if (empty)
1798                                 throw EmptySequence ();
1799                         return min;
1800                 }
1801
1802                 public static decimal Min (this IEnumerable<decimal> source)
1803                 {
1804                         Check.Source (source);
1805
1806                         bool empty = true;
1807                         var min = decimal.MaxValue;
1808                         foreach (var element in source){
1809                                 min = Math.Min (element, min);
1810                                 empty = false;
1811                         }
1812                         if (empty)
1813                                 throw EmptySequence ();
1814                         return min;
1815                 }
1816
1817                 public static int? Min (this IEnumerable<int?> source)
1818                 {
1819                         Check.Source (source);
1820
1821                         bool empty = true;
1822                         var min = int.MaxValue;
1823
1824                         foreach (var element in source) {
1825                                 if (!element.HasValue)
1826                                         continue;
1827
1828                                 min = Math.Min (element.Value, min);
1829                                 empty = false;
1830                         }
1831
1832                         if (empty)
1833                                 return null;
1834
1835                         return min;
1836                 }
1837
1838                 public static long? Min (this IEnumerable<long?> source)
1839                 {
1840                         Check.Source (source);
1841
1842                         bool empty = true;
1843                         var min = long.MaxValue;
1844
1845                         foreach (var element in source) {
1846                                 if (!element.HasValue)
1847                                         continue;
1848
1849                                 min = Math.Min (element.Value, min);
1850                                 empty = false;
1851                         }
1852
1853                         if (empty)
1854                                 return null;
1855
1856                         return min;
1857                 }
1858
1859                 public static double? Min (this IEnumerable<double?> source)
1860                 {
1861                         Check.Source (source);
1862
1863                         bool empty = true;
1864                         var min = double.MaxValue;
1865
1866                         foreach (var element in source) {
1867                                 if (!element.HasValue)
1868                                         continue;
1869
1870                                 min = Math.Min (element.Value, min);
1871                                 empty = false;
1872                         }
1873
1874                         if (empty)
1875                                 return null;
1876
1877                         return min;
1878                 }
1879
1880                 public static float? Min (this IEnumerable<float?> source)
1881                 {
1882                         Check.Source (source);
1883
1884                         bool empty = true;
1885                         var min = float.MaxValue;
1886
1887                         foreach (var element in source) {
1888                                 if (!element.HasValue)
1889                                         continue;
1890
1891                                 min = Math.Min (element.Value, min);
1892                                 empty = false;
1893                         }
1894
1895                         if (empty)
1896                                 return null;
1897
1898                         return min;
1899                 }
1900
1901                 public static decimal? Min (this IEnumerable<decimal?> source)
1902                 {
1903                         Check.Source (source);
1904
1905                         bool empty = true;
1906                         var min = decimal.MaxValue;
1907
1908                         foreach (var element in source) {
1909                                 if (!element.HasValue)
1910                                         continue;
1911
1912                                 min = Math.Min (element.Value, min);
1913                                 empty = false;
1914                         }
1915
1916                         if (empty)
1917                                 return null;
1918
1919                         return min;
1920                 }
1921
1922                 public static TSource Min<TSource> (this IEnumerable<TSource> source)
1923                 {
1924                         Check.Source (source);
1925
1926                         var comparer = Comparer<TSource>.Default;
1927
1928                         TSource min = default (TSource);
1929
1930                         if (default (TSource) == null){
1931                                 foreach (var element in source) {
1932                                         if (element == null)
1933                                                 continue;
1934
1935                                         if (min == null || comparer.Compare (element, min) < 0)
1936                                                 min = element;
1937                                 }
1938                         } else {
1939                                 bool empty = true;
1940                                 foreach (var element in source) {
1941                                         if (empty){
1942                                                 min = element;
1943                                                 empty = false;
1944                                                 continue;
1945                                         }
1946                                         if (comparer.Compare (element, min) < 0)
1947                                                 min = element;
1948                                 }
1949                                 if (empty)
1950                                         throw EmptySequence ();
1951                         }
1952                         return min;
1953                 }
1954
1955                 public static int Min<TSource> (this IEnumerable<TSource> source, Func<TSource, int> selector)
1956                 {
1957                         Check.SourceAndSelector (source, selector);
1958
1959                         bool empty = true;
1960                         var min = int.MaxValue;
1961                         foreach (var element in source){
1962                                 min = Math.Min (selector (element), min);
1963                                 empty = false;
1964                         }
1965                         if (empty)
1966                                 throw NoMatchingElement ();
1967                         return min;
1968                 }
1969
1970                 public static long Min<TSource> (this IEnumerable<TSource> source, Func<TSource, long> selector)
1971                 {
1972                         Check.SourceAndSelector (source, selector);
1973
1974                         bool empty = true;
1975                         var min = long.MaxValue;
1976                         foreach (var element in source){
1977                                 min = Math.Min (selector (element), min);
1978                                 empty = false;
1979                         }
1980                         if (empty)
1981                                 throw NoMatchingElement ();
1982                         return min;
1983                 }
1984
1985                 public static double Min<TSource> (this IEnumerable<TSource> source, Func<TSource, double> selector)
1986                 {
1987                         Check.SourceAndSelector (source, selector);
1988
1989                         bool empty = true;
1990                         var min = double.MaxValue;
1991                         foreach (var element in source){
1992                                 min = Math.Min (selector (element), min);
1993                                 empty = false;
1994                         }
1995                         if (empty)
1996                                 throw NoMatchingElement ();
1997                         return min;
1998                 }
1999
2000                 public static float Min<TSource> (this IEnumerable<TSource> source, Func<TSource, float> selector)
2001                 {
2002                         Check.SourceAndSelector (source, selector);
2003
2004                         bool empty = true;
2005                         var min = float.MaxValue;
2006                         foreach (var element in source){
2007                                 min = Math.Min (selector (element), min);
2008                                 empty = false;
2009                         }
2010                         if (empty)
2011                                 throw NoMatchingElement ();
2012                         return min;
2013                 }
2014
2015                 public static decimal Min<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal> selector)
2016                 {
2017                         Check.SourceAndSelector (source, selector);
2018
2019                         bool empty = true;
2020                         var min = decimal.MaxValue;
2021                         foreach (var element in source){
2022                                 min = Math.Min (selector (element), min);
2023                                 empty = false;
2024                         }
2025                         if (empty)
2026                                 throw NoMatchingElement ();
2027                         return min;
2028                 }
2029
2030                 public static int? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, int?> selector)
2031                 {
2032                         Check.SourceAndSelector (source, selector);
2033
2034                         bool empty = true;
2035                         int? min = null;
2036                         foreach (var element in source) {
2037                                 int? item = selector (element);
2038
2039                                 if (!min.HasValue)
2040                                         min = item;
2041                                 else if (item < min)
2042                                         min = item;
2043                                 empty = false;
2044                         }
2045
2046                         if (empty)
2047                                 return null;
2048                         return min;
2049                 }
2050
2051                 public static long? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, long?> selector)
2052                 {
2053                         Check.SourceAndSelector (source, selector);
2054
2055                         bool empty = true;
2056                         long? min = null;
2057                         foreach (var element in source) {
2058                                 long? item = selector (element);
2059
2060                                 if (!min.HasValue)
2061                                         min = item;
2062                                 else if (item < min)
2063                                         min = item;
2064                                 empty = false;
2065                         }
2066
2067                         if (empty)
2068                                 return null;
2069                         return min;
2070                 }
2071
2072                 public static float? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, float?> selector)
2073                 {
2074                         Check.SourceAndSelector (source, selector);
2075
2076                         bool empty = true;
2077                         float? min = null;
2078                         foreach (var element in source) {
2079                                 float? item = selector (element);
2080
2081                                 if (!min.HasValue)
2082                                         min = item;
2083                                 else if (item < min)
2084                                         min = item;
2085                                 empty = false;
2086                         }
2087
2088                         if (empty)
2089                                 return null;
2090                         return min;
2091                 }
2092
2093                 public static double? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, double?> selector)
2094                 {
2095                         Check.SourceAndSelector (source, selector);
2096
2097                         bool empty = true;
2098                         double? min = null;
2099                         foreach (var element in source) {
2100                                 double? item = selector (element);
2101
2102                                 if (!min.HasValue)
2103                                         min = item;
2104                                 else if (item < min)
2105                                         min = item;
2106                                 empty = false;
2107                         }
2108
2109                         if (empty)
2110                                 return null;
2111                         return min;
2112                 }
2113
2114                 public static decimal? Min<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal?> selector)
2115                 {
2116                         Check.SourceAndSelector (source, selector);
2117
2118                         bool empty = true;
2119                         decimal? min = null;
2120                         foreach (var element in source) {
2121                                 decimal? item = selector (element);
2122
2123                                 if (!min.HasValue)
2124                                         min = item;
2125                                 else if (item < min)
2126                                         min = item;
2127                                 empty = false;
2128                         }
2129
2130                         if (empty)
2131                                 return null;
2132                         return min;
2133                 }
2134
2135                 public static TResult Min<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, TResult> selector)
2136                 {
2137                         Check.SourceAndSelector (source, selector);
2138
2139                         // TODO: inline
2140                         return source.Select (selector).Min ();
2141                 }
2142
2143                 #endregion
2144
2145                 #region OfType
2146
2147                 public static IEnumerable<TResult> OfType<TResult> (this IEnumerable source)
2148                 {
2149                         Check.Source (source);
2150
2151                         return CreateOfTypeIterator<TResult> (source);
2152                 }
2153
2154                 static IEnumerable<TResult> CreateOfTypeIterator<TResult> (IEnumerable source)
2155                 {
2156                         foreach (object element in source)
2157                                 if (element is TResult)
2158                                         yield return (TResult) element;
2159                 }
2160
2161                 #endregion
2162
2163                 #region OrderBy
2164
2165                 public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey> (this IEnumerable<TSource> source,
2166                                 Func<TSource, TKey> keySelector)
2167                 {
2168                         return OrderBy<TSource, TKey> (source, keySelector, null);
2169                 }
2170
2171                 public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey> (this IEnumerable<TSource> source,
2172                                 Func<TSource, TKey> keySelector,
2173                                 IComparer<TKey> comparer)
2174                 {
2175                         Check.SourceAndKeySelector (source, keySelector);
2176
2177                         return new OrderedSequence<TSource, TKey> (source, keySelector, comparer, SortDirection.Ascending);
2178                 }
2179
2180                 #endregion
2181
2182                 #region OrderByDescending
2183
2184                 public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey> (this IEnumerable<TSource> source,
2185                                 Func<TSource, TKey> keySelector)
2186                 {
2187                         return OrderByDescending<TSource, TKey> (source, keySelector, null);
2188                 }
2189
2190                 public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey> (this IEnumerable<TSource> source,
2191                                 Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
2192                 {
2193                         Check.SourceAndKeySelector (source, keySelector);
2194
2195                         return new OrderedSequence<TSource, TKey> (source, keySelector, comparer, SortDirection.Descending);
2196                 }
2197
2198                 #endregion
2199
2200                 #region Range
2201
2202                 public static IEnumerable<int> Range (int start, int count)
2203                 {
2204                         if (count < 0)
2205                                 throw new ArgumentOutOfRangeException ("count");
2206
2207                         if (((long) start + count) - 1L > int.MaxValue)
2208                                 throw new ArgumentOutOfRangeException ();
2209
2210                         return CreateRangeIterator (start, count);
2211                 }
2212
2213                 static IEnumerable<int> CreateRangeIterator (int start, int count)
2214                 {
2215                         for (int i = 0; i < count; i++)
2216                                 yield return start + i;
2217                 }
2218
2219                 #endregion
2220
2221                 #region Repeat
2222
2223                 public static IEnumerable<TResult> Repeat<TResult> (TResult element, int count)
2224                 {
2225                         if (count < 0)
2226                                 throw new ArgumentOutOfRangeException ();
2227
2228                         return CreateRepeatIterator (element, count);
2229                 }
2230
2231                 static IEnumerable<TResult> CreateRepeatIterator<TResult> (TResult element, int count)
2232                 {
2233                         for (int i = 0; i < count; i++)
2234                                 yield return element;
2235                 }
2236
2237                 #endregion
2238
2239                 #region Reverse
2240
2241                 public static IEnumerable<TSource> Reverse<TSource> (this IEnumerable<TSource> source)
2242                 {
2243                         Check.Source (source);
2244
2245                         return CreateReverseIterator (source);
2246                 }
2247
2248                 static IEnumerable<TSource> CreateReverseIterator<TSource> (IEnumerable<TSource> source)
2249                 {
2250                         var array = source.ToArray ();
2251
2252                         for (int i = array.Length - 1; i >= 0; i--)
2253                                 yield return array [i];
2254                 }
2255
2256                 #endregion
2257
2258                 #region Select
2259
2260                 public static IEnumerable<TResult> Select<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, TResult> selector)
2261                 {
2262                         Check.SourceAndSelector (source, selector);
2263
2264                         return CreateSelectIterator (source, selector);
2265                 }
2266
2267                 static IEnumerable<TResult> CreateSelectIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, TResult> selector)
2268                 {
2269                         foreach (var element in source)
2270                                 yield return selector (element);
2271                 }
2272
2273                 public static IEnumerable<TResult> Select<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, int, TResult> selector)
2274                 {
2275                         Check.SourceAndSelector (source, selector);
2276
2277                         return CreateSelectIterator (source, selector);
2278                 }
2279
2280                 static IEnumerable<TResult> CreateSelectIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, int, TResult> selector)
2281                 {
2282                         int counter = 0;
2283                         foreach (TSource element in source) {
2284                                 yield return selector (element, counter);
2285                                 counter++;
2286                         }
2287                 }
2288
2289                 #endregion
2290
2291                 #region SelectMany
2292
2293                 public static IEnumerable<TResult> SelectMany<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
2294                 {
2295                         Check.SourceAndSelector (source, selector);
2296
2297                         return CreateSelectManyIterator (source, selector);
2298                 }
2299
2300                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
2301                 {
2302                         foreach (TSource element in source)
2303                                 foreach (TResult item in selector (element))
2304                                         yield return item;
2305                 }
2306
2307                 public static IEnumerable<TResult> SelectMany<TSource, TResult> (this IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TResult>> selector)
2308                 {
2309                         Check.SourceAndSelector (source, selector);
2310
2311                         return CreateSelectManyIterator (source, selector);
2312                 }
2313
2314                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TResult>> selector)
2315                 {
2316                         int counter = 0;
2317                         foreach (TSource element in source) {
2318                                 foreach (TResult item in selector (element, counter))
2319                                         yield return item;
2320                                 counter++;
2321                         }
2322                 }
2323
2324                 public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult> (this IEnumerable<TSource> source,
2325                         Func<TSource, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector)
2326                 {
2327                         Check.SourceAndCollectionSelectors (source, collectionSelector, resultSelector);
2328
2329                         return CreateSelectManyIterator (source, collectionSelector, resultSelector);
2330                 }
2331
2332                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TCollection, TResult> (IEnumerable<TSource> source,
2333                         Func<TSource, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> selector)
2334                 {
2335                         foreach (TSource element in source)
2336                                 foreach (TCollection collection in collectionSelector (element))
2337                                         yield return selector (element, collection);
2338                 }
2339
2340                 public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult> (this IEnumerable<TSource> source,
2341                         Func<TSource, int, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector)
2342                 {
2343                         Check.SourceAndCollectionSelectors (source, collectionSelector, resultSelector);
2344
2345                         return CreateSelectManyIterator (source, collectionSelector, resultSelector);
2346                 }
2347
2348                 static IEnumerable<TResult> CreateSelectManyIterator<TSource, TCollection, TResult> (IEnumerable<TSource> source,
2349                         Func<TSource, int, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> selector)
2350                 {
2351                         int counter = 0;
2352                         foreach (TSource element in source)
2353                                 foreach (TCollection collection in collectionSelector (element, counter++))
2354                                         yield return selector (element, collection);
2355                 }
2356
2357                 #endregion
2358
2359                 #region Single
2360
2361                 static TSource Single<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate, Fallback fallback)
2362                 {
2363                         var found = false;
2364                         var item = default (TSource);
2365
2366                         foreach (var element in source) {
2367                                 if (!predicate (element))
2368                                         continue;
2369
2370                                 if (found)
2371                                         throw MoreThanOneMatchingElement ();
2372
2373                                 found = true;
2374                                 item = element;
2375                         }
2376
2377                         if (!found && fallback == Fallback.Throw)
2378                                 throw NoMatchingElement ();
2379
2380                         return item;
2381                 }
2382
2383                 public static TSource Single<TSource> (this IEnumerable<TSource> source)
2384                 {
2385                         Check.Source (source);
2386
2387 #if !FULL_AOT_RUNTIME
2388                         return source.Single (PredicateOf<TSource>.Always, Fallback.Throw);
2389 #else
2390                         var found = false;
2391                         var item = default (TSource);
2392
2393                         foreach (var element in source) {
2394                                 if (found)
2395                                         throw MoreThanOneElement ();
2396
2397                                 found = true;
2398                                 item = element;
2399                         }
2400
2401                         if (!found)
2402                                 throw NoMatchingElement ();
2403
2404                         return item;
2405 #endif
2406         }
2407
2408                 public static TSource Single<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2409                 {
2410                         Check.SourceAndPredicate (source, predicate);
2411
2412                         return source.Single (predicate, Fallback.Throw);
2413                 }
2414
2415                 #endregion
2416
2417                 #region SingleOrDefault
2418
2419                 public static TSource SingleOrDefault<TSource> (this IEnumerable<TSource> source)
2420                 {
2421                         Check.Source (source);
2422
2423 #if !FULL_AOT_RUNTIME
2424                         return source.Single (PredicateOf<TSource>.Always, Fallback.Default);
2425 #else
2426                         var found = false;
2427                         var item = default (TSource);
2428
2429                         foreach (var element in source) {
2430                                 if (found)
2431                                         throw MoreThanOneMatchingElement ();
2432
2433                                 found = true;
2434                                 item = element;
2435                         }
2436
2437                         return item;
2438 #endif
2439         }
2440
2441                 public static TSource SingleOrDefault<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2442                 {
2443                         Check.SourceAndPredicate (source, predicate);
2444
2445                         return source.Single (predicate, Fallback.Default);
2446                 }
2447
2448                 #endregion
2449
2450                 #region Skip
2451
2452                 public static IEnumerable<TSource> Skip<TSource> (this IEnumerable<TSource> source, int count)
2453                 {
2454                         Check.Source (source);
2455
2456                         return CreateSkipIterator (source, count);
2457                 }
2458
2459                 static IEnumerable<TSource> CreateSkipIterator<TSource> (IEnumerable<TSource> source, int count)
2460                 {
2461                         var enumerator = source.GetEnumerator ();
2462                         try {
2463                                 while (count-- > 0)
2464                                         if (!enumerator.MoveNext ())
2465                                                 yield break;
2466
2467                                 while (enumerator.MoveNext ())
2468                                         yield return enumerator.Current;
2469
2470                         } finally {
2471                                 enumerator.Dispose ();
2472                         }
2473                 }
2474
2475                 #endregion
2476
2477                 #region SkipWhile
2478
2479                 public static IEnumerable<TSource> SkipWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2480                 {
2481                         Check.SourceAndPredicate (source, predicate);
2482
2483                         return CreateSkipWhileIterator (source, predicate);
2484                 }
2485
2486                 static IEnumerable<TSource> CreateSkipWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, bool> predicate)
2487                 {
2488                         bool yield = false;
2489
2490                         foreach (TSource element in source) {
2491                                 if (yield)
2492                                         yield return element;
2493                                 else
2494                                         if (!predicate (element)) {
2495                                                 yield return element;
2496                                                 yield = true;
2497                                         }
2498                         }
2499                 }
2500
2501                 public static IEnumerable<TSource> SkipWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2502                 {
2503                         Check.SourceAndPredicate (source, predicate);
2504
2505                         return CreateSkipWhileIterator (source, predicate);
2506                 }
2507
2508                 static IEnumerable<TSource> CreateSkipWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2509                 {
2510                         int counter = 0;
2511                         bool yield = false;
2512
2513                         foreach (TSource element in source) {
2514                                 if (yield)
2515                                         yield return element;
2516                                 else
2517                                         if (!predicate (element, counter)) {
2518                                                 yield return element;
2519                                                 yield = true;
2520                                         }
2521                                 counter++;
2522                         }
2523                 }
2524
2525                 #endregion
2526
2527                 #region Sum
2528
2529                 public static int Sum (this IEnumerable<int> source)
2530                 {
2531                         Check.Source (source);
2532                         int total = 0;
2533
2534                         foreach (var element in source)
2535                                 total = checked (total + element);
2536                         return total;
2537                 }
2538
2539                 public static int? Sum (this IEnumerable<int?> source)
2540                 {
2541                         Check.Source (source);
2542
2543                         int total = 0;
2544                         foreach (var element in source) {
2545                                 if (element.HasValue)
2546                                         total = checked (total + element.Value);
2547                         }
2548                         return total;
2549                 }
2550
2551                 public static int Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, int> selector)
2552                 {
2553                         Check.SourceAndSelector (source, selector);
2554                         int total = 0;
2555
2556                         foreach (var element in source)
2557                                 total = checked (total + selector (element));
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
2566                         int total = 0;
2567                         foreach (var element in source) {
2568                                 var value = selector (element);
2569                                 if (value.HasValue)
2570                                         total = checked (total + value.Value);
2571                         }
2572                         return total;
2573                 }
2574
2575                 public static long Sum (this IEnumerable<long> source)
2576                 {
2577                         Check.Source (source);
2578
2579                         long total = 0;
2580
2581                         foreach (var element in source)
2582                                 total = checked (total + element);
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                         foreach (var element in source) {
2592                                 if (element.HasValue)
2593                                         total = checked (total + element.Value);
2594                         }
2595                         return total;
2596                 }
2597
2598                 public static long Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, long> selector)
2599                 {
2600                         Check.SourceAndSelector (source, selector);
2601
2602                         long total = 0;
2603                         foreach (var element in source)
2604                                 total = checked (total + selector (element));
2605                         return total;
2606                 }
2607
2608                 public static long? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, long?> selector)
2609                 {
2610                         Check.SourceAndSelector (source, selector);
2611
2612                         long total = 0;
2613                         foreach (var element in source) {
2614                                 var value = selector (element);
2615                                 if (value.HasValue)
2616                                         total = checked (total + value.Value);
2617                         }
2618                         return total;
2619                 }
2620
2621                 public static double Sum (this IEnumerable<double> source)
2622                 {
2623                         Check.Source (source);
2624
2625                         double total = 0;
2626
2627                         foreach (var element in source)
2628                                 total = checked (total + element);
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                         foreach (var element in source) {
2638                                 if (element.HasValue)
2639                                         total = checked (total + element.Value);
2640                         }
2641                         return total;
2642                 }
2643
2644                 public static double Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, double> selector)
2645                 {
2646                         Check.SourceAndSelector (source, selector);
2647
2648                         double total = 0;
2649
2650                         foreach (var element in source)
2651                                 total = checked (total + selector (element));
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                         foreach (var element in source) {
2661                                 var value = selector (element);
2662                                 if (value.HasValue)
2663                                         total = checked (total + value.Value);
2664                         }
2665                         return total;
2666                 }
2667
2668                 public static float Sum (this IEnumerable<float> source)
2669                 {
2670                         Check.Source (source);
2671
2672                         float total = 0;
2673
2674                         foreach (var element in source)
2675                                 total = checked (total + element);
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                         foreach (var element in source) {
2685                                 if (element.HasValue)
2686                                         total = checked (total + element.Value);
2687                         }
2688                         return total;
2689
2690                 }
2691
2692                 public static float Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, float> selector)
2693                 {
2694                         Check.SourceAndSelector (source, selector);
2695                         float total = 0;
2696                         foreach (var element in source)
2697                                 total = checked (total + selector (element));
2698                         return total;
2699                 }
2700
2701                 public static float? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, float?> selector)
2702                 {
2703                         Check.SourceAndSelector (source, selector);
2704
2705                         float total = 0;
2706                         foreach (var element in source) {
2707                                 var value = selector (element);
2708                                 if (value.HasValue)
2709                                         total = checked (total + value.Value);
2710                         }
2711                         return total;
2712                 }
2713
2714                 public static decimal Sum (this IEnumerable<decimal> source)
2715                 {
2716                         Check.Source (source);
2717                         decimal total = 0;
2718
2719                         foreach (var element in source)
2720                                 total = checked (total + element);
2721                         return total;
2722                 }
2723
2724                 public static decimal? Sum (this IEnumerable<decimal?> source)
2725                 {
2726                         Check.Source (source);
2727
2728                         decimal total = 0;
2729                         foreach (var element in source) {
2730                                 if (element.HasValue)
2731                                         total = checked (total + element.Value);
2732                         }
2733                         return total;
2734
2735                 }
2736
2737                 public static decimal Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal> selector)
2738                 {
2739                         Check.SourceAndSelector (source, selector);
2740                         decimal total = 0;
2741
2742                         foreach (var element in source)
2743                                 total = checked (total + selector (element));
2744                         return total;
2745                 }
2746
2747                 public static decimal? Sum<TSource> (this IEnumerable<TSource> source, Func<TSource, decimal?> selector)
2748                 {
2749                         Check.SourceAndSelector (source, selector);
2750
2751                         decimal total = 0;
2752                         foreach (var element in source) {
2753                                 var value = selector (element);
2754                                 if (value.HasValue)
2755                                         total = checked (total + value.Value);
2756                         }
2757                         return total;
2758                 }
2759
2760                 #endregion
2761
2762                 #region Take
2763
2764                 public static IEnumerable<TSource> Take<TSource> (this IEnumerable<TSource> source, int count)
2765                 {
2766                         Check.Source (source);
2767
2768                         if (count <= 0)
2769                                 return EmptyOf<TSource>.Instance;
2770
2771                         return CreateTakeIterator (source, count);
2772                 }
2773
2774                 static IEnumerable<TSource> CreateTakeIterator<TSource> (IEnumerable<TSource> source, int count)
2775                 {
2776                         int counter = 0;
2777                         foreach (TSource element in source) {
2778                                 yield return element;
2779
2780                                 if (++counter == count)
2781                                         yield break;
2782                         }
2783                 }
2784
2785                 #endregion
2786
2787                 #region TakeWhile
2788
2789                 public static IEnumerable<TSource> TakeWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
2790                 {
2791                         Check.SourceAndPredicate (source, predicate);
2792
2793                         return CreateTakeWhileIterator (source, predicate);
2794                 }
2795
2796                 static IEnumerable<TSource> CreateTakeWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, bool> predicate)
2797                 {
2798                         foreach (var element in source) {
2799                                 if (!predicate (element))
2800                                         yield break;
2801
2802                                 yield return element;
2803                         }
2804                 }
2805
2806                 public static IEnumerable<TSource> TakeWhile<TSource> (this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2807                 {
2808                         Check.SourceAndPredicate (source, predicate);
2809
2810                         return CreateTakeWhileIterator (source, predicate);
2811                 }
2812
2813                 static IEnumerable<TSource> CreateTakeWhileIterator<TSource> (IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
2814                 {
2815                         int counter = 0;
2816                         foreach (var element in source) {
2817                                 if (!predicate (element, counter))
2818                                         yield break;
2819
2820                                 yield return element;
2821                                 counter++;
2822                         }
2823                 }
2824
2825                 #endregion
2826
2827                 #region ThenBy
2828
2829                 public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey> (this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector)
2830                 {
2831                         return ThenBy<TSource, TKey> (source, keySelector, null);
2832                 }
2833
2834                 public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey> (this IOrderedEnumerable<TSource> source,
2835                         Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
2836                 {
2837                         Check.SourceAndKeySelector (source, keySelector);
2838
2839 #if FULL_AOT_RUNTIME
2840                         var oe = source as OrderedEnumerable <TSource>;
2841                         if (oe != null)
2842                                 return oe.CreateOrderedEnumerable (keySelector, comparer, false);
2843 #endif
2844
2845                         return source.CreateOrderedEnumerable (keySelector, comparer, false);
2846                 }
2847
2848                 #endregion
2849
2850                 #region ThenByDescending
2851
2852                 public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey> (this IOrderedEnumerable<TSource> source,
2853                         Func<TSource, TKey> keySelector)
2854                 {
2855                         return ThenByDescending<TSource, TKey> (source, keySelector, null);
2856                 }
2857
2858                 public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey> (this IOrderedEnumerable<TSource> source,
2859                         Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
2860                 {
2861                         Check.SourceAndKeySelector (source, keySelector);
2862
2863 #if FULL_AOT_RUNTIME
2864                         var oe = source as OrderedEnumerable <TSource>;
2865                         if (oe != null)
2866                                 return oe.CreateOrderedEnumerable (keySelector, comparer, true);
2867 #endif
2868                         return source.CreateOrderedEnumerable (keySelector, comparer, true);
2869                 }
2870
2871                 #endregion
2872
2873                 #region ToArray
2874
2875                 public static TSource [] ToArray<TSource> (this IEnumerable<TSource> source)
2876                 {
2877                         Check.Source (source);
2878
2879                         TSource[] array;
2880                         var collection = source as ICollection<TSource>;
2881                         if (collection != null) {
2882                                 if (collection.Count == 0)
2883                                         return EmptyOf<TSource>.Instance;
2884
2885                                 array = new TSource [collection.Count];
2886                                 collection.CopyTo (array, 0);
2887                                 return array;
2888                         }
2889
2890                         int pos = 0;
2891                         array = EmptyOf<TSource>.Instance;
2892                         foreach (var element in source) {
2893                                 if (pos == array.Length) {
2894                                         if (pos == 0)
2895                                                 array = new TSource [4];
2896                                         else
2897                                                 Array.Resize (ref array, pos * 2);
2898                                 }
2899
2900                                 array[pos++] = element;
2901                         }
2902
2903                         if (pos != array.Length)
2904                                 Array.Resize (ref array, pos);
2905
2906                         return array;
2907                 }
2908
2909                 #endregion
2910
2911                 #region ToDictionary
2912                 public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2913                                 Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector)
2914                 {
2915                         return ToDictionary<TSource, TKey, TElement> (source, keySelector, elementSelector, null);
2916                 }
2917
2918                 public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2919                                 Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
2920                 {
2921                         Check.SourceAndKeyElementSelectors (source, keySelector, elementSelector);
2922
2923                         if (comparer == null)
2924                                 comparer = EqualityComparer<TKey>.Default;
2925
2926                         var dict = new Dictionary<TKey, TElement> (comparer);
2927                         foreach (var e in source)
2928                                 dict.Add (keySelector (e), elementSelector (e));
2929
2930                         return dict;
2931                 }
2932
2933                 public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey> (this IEnumerable<TSource> source,
2934                                 Func<TSource, TKey> keySelector)
2935                 {
2936                         return ToDictionary (source, keySelector, null);
2937                 }
2938
2939                 public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey> (this IEnumerable<TSource> source,
2940                                 Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
2941                 {
2942                         return ToDictionary<TSource, TKey, TSource> (source, keySelector, Function<TSource>.Identity, comparer);
2943                 }
2944
2945                 #endregion
2946
2947                 #region ToList
2948                 public static List<TSource> ToList<TSource> (this IEnumerable<TSource> source)
2949                 {
2950                         Check.Source (source);
2951
2952                         return new List<TSource> (source);
2953                 }
2954                 #endregion
2955
2956                 #region ToLookup
2957
2958                 public static ILookup<TKey, TSource> ToLookup<TSource, TKey> (this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
2959                 {
2960                         return ToLookup<TSource, TKey, TSource> (source, keySelector, Function<TSource>.Identity, null);
2961                 }
2962
2963                 public static ILookup<TKey, TSource> ToLookup<TSource, TKey> (this IEnumerable<TSource> source,
2964                         Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
2965                 {
2966                         return ToLookup<TSource, TKey, TSource> (source, keySelector, Function<TSource>.Identity, comparer);
2967                 }
2968
2969                 public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2970                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector)
2971                 {
2972                         return ToLookup<TSource, TKey, TElement> (source, keySelector, elementSelector, null);
2973                 }
2974
2975                 public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement> (this IEnumerable<TSource> source,
2976                         Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
2977                 {
2978                         Check.SourceAndKeyElementSelectors (source, keySelector, elementSelector);
2979
2980                         List<TElement> nullKeyElements = null;
2981
2982                         var dictionary = new Dictionary<TKey, List<TElement>> (comparer ?? EqualityComparer<TKey>.Default);
2983                         foreach (var element in source) {
2984                                 var key = keySelector (element);
2985
2986                                 List<TElement> list;
2987
2988                                 if (key == null) {
2989                                         if (nullKeyElements == null)
2990                                                 nullKeyElements = new List<TElement> ();
2991
2992                                         list = nullKeyElements;
2993                                 } else if (!dictionary.TryGetValue (key, out list)) {
2994                                         list = new List<TElement> ();
2995                                         dictionary.Add (key, list);
2996                                 }
2997
2998                                 list.Add (elementSelector (element));
2999                         }
3000
3001                         return new Lookup<TKey, TElement> (dictionary, nullKeyElements);
3002                 }
3003
3004                 #endregion
3005
3006                 #region SequenceEqual
3007
3008                 public static bool SequenceEqual<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
3009                 {
3010                         return first.SequenceEqual (second, null);
3011                 }
3012
3013                 public static bool SequenceEqual<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
3014                 {
3015                         Check.FirstAndSecond (first, second);
3016
3017                         if (comparer == null)
3018                                 comparer = EqualityComparer<TSource>.Default;
3019
3020                         using (IEnumerator<TSource> first_enumerator = first.GetEnumerator (),
3021                                 second_enumerator = second.GetEnumerator ()) {
3022
3023                                 while (first_enumerator.MoveNext ()) {
3024                                         if (!second_enumerator.MoveNext ())
3025                                                 return false;
3026
3027                                         if (!comparer.Equals (first_enumerator.Current, second_enumerator.Current))
3028                                                 return false;
3029                                 }
3030
3031                                 return !second_enumerator.MoveNext ();
3032                         }
3033                 }
3034
3035                 #endregion
3036
3037                 #region Union
3038
3039                 public static IEnumerable<TSource> Union<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second)
3040                 {
3041                         Check.FirstAndSecond (first, second);
3042
3043                         return first.Union (second, null);
3044                 }
3045
3046                 public static IEnumerable<TSource> Union<TSource> (this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
3047                 {
3048                         Check.FirstAndSecond (first, second);
3049
3050                         if (comparer == null)
3051                                 comparer = EqualityComparer<TSource>.Default;
3052
3053                         return CreateUnionIterator (first, second, comparer);
3054                 }
3055
3056                 static IEnumerable<TSource> CreateUnionIterator<TSource> (IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
3057                 {
3058                         var items = new HashSet<TSource> (comparer);
3059                         foreach (var element in first) {
3060                                 if (! items.Contains (element)) {
3061                                         items.Add (element);
3062                                         yield return element;
3063                                 }
3064                         }
3065
3066                         foreach (var element in second) {
3067                                 if (! items.Contains (element)) {
3068                                         items.Add (element);
3069                                         yield return element;
3070                                 }
3071                         }
3072                 }
3073
3074                 #endregion
3075
3076 #if NET_4_0
3077                 #region Zip
3078
3079                 public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult> (this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector)
3080                 {
3081                         Check.FirstAndSecond (first, second);
3082                         if (resultSelector == null)
3083                                 throw new ArgumentNullException ("resultSelector");
3084
3085                         return CreateZipIterator (first, second, resultSelector);
3086                 }
3087
3088                 static IEnumerable<TResult> CreateZipIterator<TFirst, TSecond, TResult> (IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> selector)
3089                 {
3090                         using (IEnumerator<TFirst> first_enumerator = first.GetEnumerator ()) {
3091                                 using (IEnumerator<TSecond> second_enumerator = second.GetEnumerator ()) {
3092
3093                                         while (first_enumerator.MoveNext () && second_enumerator.MoveNext ()) {
3094                                                 yield return selector (first_enumerator.Current, second_enumerator.Current);
3095                                         }
3096                                 }
3097                         }
3098                 }
3099
3100                 #endregion
3101 #endif
3102
3103                 #region Where
3104
3105                 public static IEnumerable<TSource> Where<TSource> (this IEnumerable<TSource> source, Func<TSource, bool> predicate)
3106                 {
3107                         Check.SourceAndPredicate (source, predicate);
3108
3109                         // It cannot be IList<TSource> because it may break on user implementation
3110                         var array = source as TSource[];
3111                         if (array != null)
3112                                 return CreateWhereIterator (array, predicate);
3113
3114                         return CreateWhereIterator (source, predicate);
3115                 }
3116
3117                 static IEnumerable<TSource> CreateWhereIterator<TSource> (IEnumerable<TSource> source, Func<TSource, bool> predicate)
3118                 {
3119                         foreach (TSource element in source)
3120                                 if (predicate (element))
3121                                         yield return element;
3122                 }
3123
3124                 static IEnumerable<TSource> CreateWhereIterator<TSource> (TSource[] source, Func<TSource, bool> predicate)
3125                 {
3126                         for (int i = 0; i < source.Length; ++i) {
3127                                 var element = source [i];
3128                                 if (predicate (element))
3129                                         yield return element;
3130                         }
3131                 }
3132
3133                 public static IEnumerable<TSource> Where<TSource> (this IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
3134                 {
3135                         Check.SourceAndPredicate (source, predicate);
3136
3137                         var array = source as TSource[];
3138                         if (array != null)
3139                                 return CreateWhereIterator (array, predicate);
3140
3141                         return CreateWhereIterator (source, predicate);
3142                 }
3143
3144                 static IEnumerable<TSource> CreateWhereIterator<TSource> (IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
3145                 {
3146                         int counter = 0;
3147                         foreach (TSource element in source) {
3148                                 if (predicate (element, counter))
3149                                         yield return element;
3150                                 counter++;
3151                         }
3152                 }
3153
3154                 static IEnumerable<TSource> CreateWhereIterator<TSource> (TSource[] source, Func<TSource, int, bool> predicate)
3155                 {
3156                         for (int i = 0; i < source.Length; ++i) {
3157                                 var element = source [i];
3158                                 if (predicate (element, i))
3159                                         yield return element;
3160                         }
3161                 }
3162
3163                 #endregion
3164
3165                 internal static ReadOnlyCollection<TSource> ToReadOnlyCollection<TSource> (this IEnumerable<TSource> source)
3166                 {
3167                         if (source == null)
3168                                 return ReadOnlyCollectionOf<TSource>.Empty;
3169
3170                         var ro = source as ReadOnlyCollection<TSource>;
3171                         if (ro != null)
3172                                 return ro;
3173
3174                         return new ReadOnlyCollection<TSource> (source.ToArray<TSource> ());
3175                 }
3176
3177                 #region Exception helpers
3178
3179                 static Exception EmptySequence ()
3180                 {
3181                         return new InvalidOperationException (Locale.GetText ("Sequence contains no elements"));
3182                 }
3183                 static Exception NoMatchingElement ()
3184                 {
3185                         return new InvalidOperationException (Locale.GetText ("Sequence contains no matching element"));
3186                 }
3187                 static Exception MoreThanOneElement ()
3188                 {
3189                         return new InvalidOperationException (Locale.GetText ("Sequence contains more than one element"));
3190                 }
3191                 static Exception MoreThanOneMatchingElement ()
3192                 {
3193                         return new InvalidOperationException (Locale.GetText ("Sequence contains more than one matching element"));
3194                 }
3195
3196                 #endregion
3197         }
3198 }