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

   1 using System;
   2 using System.Collections;
   3 using System.Collections.Generic;
   4 using System.Threading;
   5
   6 // Include Silverlight's managed resources
   7 #if SILVERLIGHT
   8 using System.Core;
   9 #endif //SILVERLIGHT
  10
  11 namespace System.Linq
  12 {
  13     public static class Enumerable
  14     {
  15         public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
  16             if (source == null) throw Error.ArgumentNull("source");
  17             if (predicate == null) throw Error.ArgumentNull("predicate");
  18             if (source is Iterator<TSource>) return ((Iterator<TSource>)source).Where(predicate);
  19             if (source is TSource[]) return new WhereArrayIterator<TSource>((TSource[])source, predicate);
  20             if (source is List<TSource>) return new WhereListIterator<TSource>((List<TSource>)source, predicate);
  21             return new WhereEnumerableIterator<TSource>(source, predicate);
  22         }
  23
  24         public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, int, bool> predicate) {
  25             if (source == null) throw Error.ArgumentNull("source");
  26             if (predicate == null) throw Error.ArgumentNull("predicate");
  27             return WhereIterator<TSource>(source, predicate);
  28         }
  29
  30         static IEnumerable<TSource> WhereIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate) {
  31             int index = -1;
  32             foreach (TSource element in source) {
  33                 checked { index++; }
  34                 if (predicate(element, index)) yield return element;
  35             }
  36         }
  37
  38         public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector) {
  39             if (source == null) throw Error.ArgumentNull("source");
  40             if (selector == null) throw Error.ArgumentNull("selector");
  41             if (source is Iterator<TSource>) return ((Iterator<TSource>)source).Select(selector);
  42             if (source is TSource[]) return new WhereSelectArrayIterator<TSource, TResult>((TSource[])source, null, selector);
  43             if (source is List<TSource>) return new WhereSelectListIterator<TSource, TResult>((List<TSource>)source, null, selector);
  44             return new WhereSelectEnumerableIterator<TSource, TResult>(source, null, selector);
  45         }
  46
  47         public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, int, TResult> selector) {
  48             if (source == null) throw Error.ArgumentNull("source");
  49             if (selector == null) throw Error.ArgumentNull("selector");
  50             return SelectIterator<TSource, TResult>(source, selector);
  51         }
  52
  53         static IEnumerable<TResult> SelectIterator<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, int, TResult> selector) {
  54             int index = -1;
  55             foreach (TSource element in source) {
  56                 checked { index++; }
  57                 yield return selector(element, index);
  58             }
  59         }
  60
  61         static Func<TSource, bool> CombinePredicates<TSource>(Func<TSource, bool> predicate1, Func<TSource, bool> predicate2) {
  62             return x => predicate1(x) && predicate2(x);
  63         }
  64
  65         static Func<TSource, TResult> CombineSelectors<TSource, TMiddle, TResult>(Func<TSource, TMiddle> selector1, Func<TMiddle, TResult> selector2) {
  66             return x => selector2(selector1(x));
  67         }
  68
  69         abstract class Iterator<TSource> : IEnumerable<TSource>, IEnumerator<TSource>
  70         {
  71             int threadId;
  72             internal int state;
  73             internal TSource current;
  74
  75             public Iterator() {
  76                 threadId = Thread.CurrentThread.ManagedThreadId;
  77             }
  78
  79             public TSource Current {
  80                 get { return current; }
  81             }
  82
  83             public abstract Iterator<TSource> Clone();
  84
  85             public virtual void Dispose() {
  86                 current = default(TSource);
  87                 state = -1;
  88             }
  89
  90             public IEnumerator<TSource> GetEnumerator() {
  91                 if (threadId == Thread.CurrentThread.ManagedThreadId && state == 0) {
  92                     state = 1;
  93                     return this;
  94                 }
  95                 Iterator<TSource> duplicate = Clone();
  96                 duplicate.state = 1;
  97                 return duplicate;
  98             }
  99
 100             public abstract bool MoveNext();
 101
 102             public abstract IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector);
 103
 104             public abstract IEnumerable<TSource> Where(Func<TSource, bool> predicate);
 105
 106             object IEnumerator.Current {
 107                 get { return Current; }
 108             }
 109
 110             IEnumerator IEnumerable.GetEnumerator() {
 111                 return GetEnumerator();
 112             }
 113
 114             void IEnumerator.Reset() {
 115                 throw new NotImplementedException();
 116             }
 117         }
 118
 119         class WhereEnumerableIterator<TSource> : Iterator<TSource>
 120         {
 121             IEnumerable<TSource> source;
 122             Func<TSource, bool> predicate;
 123             IEnumerator<TSource> enumerator;
 124
 125             public WhereEnumerableIterator(IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 126                 this.source = source;
 127                 this.predicate = predicate;
 128             }
 129
 130             public override Iterator<TSource> Clone() {
 131                 return new WhereEnumerableIterator<TSource>(source, predicate);
 132             }
 133
 134             public override void Dispose() {
 135                 if (enumerator is IDisposable) ((IDisposable)enumerator).Dispose();
 136                 enumerator = null;
 137                 base.Dispose();
 138             }
 139
 140             public override bool MoveNext() {
 141                 switch (state) {
 142                     case 1:
 143                         enumerator = source.GetEnumerator();
 144                         state = 2;
 145                         goto case 2;
 146                     case 2:
 147                         while (enumerator.MoveNext()) {
 148                             TSource item = enumerator.Current;
 149                             if (predicate(item)) {
 150                                 current = item;
 151                                 return true;
 152                             }
 153                         }
 154                         Dispose();
 155                         break;
 156                 }
 157                 return false;
 158             }
 159
 160             public override IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector) {
 161                 return new WhereSelectEnumerableIterator<TSource, TResult>(source, predicate, selector);
 162             }
 163
 164             public override IEnumerable<TSource> Where(Func<TSource, bool> predicate) {
 165                 return new WhereEnumerableIterator<TSource>(source, CombinePredicates(this.predicate, predicate));
 166             }
 167         }
 168
 169         class WhereArrayIterator<TSource> : Iterator<TSource>
 170         {
 171             TSource[] source;
 172             Func<TSource, bool> predicate;
 173             int index;
 174
 175             public WhereArrayIterator(TSource[] source, Func<TSource, bool> predicate) {
 176                 this.source = source;
 177                 this.predicate = predicate;
 178             }
 179
 180             public override Iterator<TSource> Clone() {
 181                 return new WhereArrayIterator<TSource>(source, predicate);
 182             }
 183
 184             public override bool MoveNext() {
 185                 if (state == 1) {
 186                     while (index < source.Length) {
 187                         TSource item = source[index];
 188                         index++;
 189                         if (predicate(item)) {
 190                             current = item;
 191                             return true;
 192                         }
 193                     }
 194                     Dispose();
 195                 }
 196                 return false;
 197             }
 198
 199             public override IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector) {
 200                 return new WhereSelectArrayIterator<TSource, TResult>(source, predicate, selector);
 201             }
 202
 203             public override IEnumerable<TSource> Where(Func<TSource, bool> predicate) {
 204                 return new WhereArrayIterator<TSource>(source, CombinePredicates(this.predicate, predicate));
 205             }
 206         }
 207
 208         class WhereListIterator<TSource> : Iterator<TSource>
 209         {
 210             List<TSource> source;
 211             Func<TSource, bool> predicate;
 212             List<TSource>.Enumerator enumerator;
 213
 214             public WhereListIterator(List<TSource> source, Func<TSource, bool> predicate) {
 215                 this.source = source;
 216                 this.predicate = predicate;
 217             }
 218
 219             public override Iterator<TSource> Clone() {
 220                 return new WhereListIterator<TSource>(source, predicate);
 221             }
 222
 223             public override bool MoveNext() {
 224                 switch (state) {
 225                     case 1:
 226                         enumerator = source.GetEnumerator();
 227                         state = 2;
 228                         goto case 2;
 229                     case 2:
 230                         while (enumerator.MoveNext()) {
 231                             TSource item = enumerator.Current;
 232                             if (predicate(item)) {
 233                                 current = item;
 234                                 return true;
 235                             }
 236                         }
 237                         Dispose();
 238                         break;
 239                 }
 240                 return false;
 241             }
 242
 243             public override IEnumerable<TResult> Select<TResult>(Func<TSource, TResult> selector) {
 244                 return new WhereSelectListIterator<TSource, TResult>(source, predicate, selector);
 245             }
 246
 247             public override IEnumerable<TSource> Where(Func<TSource, bool> predicate) {
 248                 return new WhereListIterator<TSource>(source, CombinePredicates(this.predicate, predicate));
 249             }
 250         }
 251
 252         class WhereSelectEnumerableIterator<TSource, TResult> : Iterator<TResult>
 253         {
 254             IEnumerable<TSource> source;
 255             Func<TSource, bool> predicate;
 256             Func<TSource, TResult> selector;
 257             IEnumerator<TSource> enumerator;
 258
 259             public WhereSelectEnumerableIterator(IEnumerable<TSource> source, Func<TSource, bool> predicate, Func<TSource, TResult> selector) {
 260                 this.source = source;
 261                 this.predicate = predicate;
 262                 this.selector = selector;
 263             }
 264
 265             public override Iterator<TResult> Clone() {
 266                 return new WhereSelectEnumerableIterator<TSource, TResult>(source, predicate, selector);
 267             }
 268
 269             public override void Dispose() {
 270                 if (enumerator is IDisposable) ((IDisposable)enumerator).Dispose();
 271                 enumerator = null;
 272                 base.Dispose();
 273             }
 274
 275             public override bool MoveNext() {
 276                 switch (state) {
 277                     case 1:
 278                         enumerator = source.GetEnumerator();
 279                         state = 2;
 280                         goto case 2;
 281                     case 2:
 282                         while (enumerator.MoveNext()) {
 283                             TSource item = enumerator.Current;
 284                             if (predicate == null || predicate(item)) {
 285                                 current = selector(item);
 286                                 return true;
 287                             }
 288                         }
 289                         Dispose();
 290                         break;
 291                 }
 292                 return false;
 293             }
 294
 295             public override IEnumerable<TResult2> Select<TResult2>(Func<TResult, TResult2> selector) {
 296                 return new WhereSelectEnumerableIterator<TSource, TResult2>(source, predicate, CombineSelectors(this.selector, selector));
 297             }
 298
 299             public override IEnumerable<TResult> Where(Func<TResult, bool> predicate) {
 300                 return new WhereEnumerableIterator<TResult>(this, predicate);
 301             }
 302         }
 303
 304         class WhereSelectArrayIterator<TSource, TResult> : Iterator<TResult>
 305         {
 306             TSource[] source;
 307             Func<TSource, bool> predicate;
 308             Func<TSource, TResult> selector;
 309             int index;
 310
 311             public WhereSelectArrayIterator(TSource[] source, Func<TSource, bool> predicate, Func<TSource, TResult> selector) {
 312                 this.source = source;
 313                 this.predicate = predicate;
 314                 this.selector = selector;
 315             }
 316
 317             public override Iterator<TResult> Clone() {
 318                 return new WhereSelectArrayIterator<TSource, TResult>(source, predicate, selector);
 319             }
 320
 321             public override bool MoveNext() {
 322                 if (state == 1) {
 323                     while (index < source.Length) {
 324                         TSource item = source[index];
 325                         index++;
 326                         if (predicate == null || predicate(item)) {
 327                             current = selector(item);
 328                             return true;
 329                         }
 330                     }
 331                     Dispose();
 332                 }
 333                 return false;
 334             }
 335
 336             public override IEnumerable<TResult2> Select<TResult2>(Func<TResult, TResult2> selector) {
 337                 return new WhereSelectArrayIterator<TSource, TResult2>(source, predicate, CombineSelectors(this.selector, selector));
 338             }
 339
 340             public override IEnumerable<TResult> Where(Func<TResult, bool> predicate) {
 341                 return new WhereEnumerableIterator<TResult>(this, predicate);
 342             }
 343         }
 344
 345         class WhereSelectListIterator<TSource, TResult> : Iterator<TResult>
 346         {
 347             List<TSource> source;
 348             Func<TSource, bool> predicate;
 349             Func<TSource, TResult> selector;
 350             List<TSource>.Enumerator enumerator;
 351
 352             public WhereSelectListIterator(List<TSource> source, Func<TSource, bool> predicate, Func<TSource, TResult> selector) {
 353                 this.source = source;
 354                 this.predicate = predicate;
 355                 this.selector = selector;
 356             }
 357
 358             public override Iterator<TResult> Clone() {
 359                 return new WhereSelectListIterator<TSource, TResult>(source, predicate, selector);
 360             }
 361
 362             public override bool MoveNext() {
 363                 switch (state) {
 364                     case 1:
 365                         enumerator = source.GetEnumerator();
 366                         state = 2;
 367                         goto case 2;
 368                     case 2:
 369                         while (enumerator.MoveNext()) {
 370                             TSource item = enumerator.Current;
 371                             if (predicate == null || predicate(item)) {
 372                                 current = selector(item);
 373                                 return true;
 374                             }
 375                         }
 376                         Dispose();
 377                         break;
 378                 }
 379                 return false;
 380             }
 381
 382             public override IEnumerable<TResult2> Select<TResult2>(Func<TResult, TResult2> selector) {
 383                 return new WhereSelectListIterator<TSource, TResult2>(source, predicate, CombineSelectors(this.selector, selector));
 384             }
 385
 386             public override IEnumerable<TResult> Where(Func<TResult, bool> predicate) {
 387                 return new WhereEnumerableIterator<TResult>(this, predicate);
 388             }
 389         }
 390
 391         //public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 392         //    if (source == null) throw Error.ArgumentNull("source");
 393         //    if (predicate == null) throw Error.ArgumentNull("predicate");
 394         //    return WhereIterator<TSource>(source, predicate);
 395         //}
 396
 397         //static IEnumerable<TSource> WhereIterator<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 398         //    foreach (TSource element in source) {
 399         //        if (predicate(element)) yield return element;
 400         //    }
 401         //}
 402
 403         //public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector) {
 404         //    if (source == null) throw Error.ArgumentNull("source");
 405         //    if (selector == null) throw Error.ArgumentNull("selector");
 406         //    return SelectIterator<TSource, TResult>(source, selector);
 407         //}
 408
 409         //static IEnumerable<TResult> SelectIterator<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, TResult> selector) {
 410         //    foreach (TSource element in source) {
 411         //        yield return selector(element);
 412         //    }
 413         //}
 414
 415         public static IEnumerable<TResult> SelectMany<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector) {
 416             if (source == null) throw Error.ArgumentNull("source");
 417             if (selector == null) throw Error.ArgumentNull("selector");
 418             return SelectManyIterator<TSource, TResult>(source, selector);
 419         }
 420
 421         static IEnumerable<TResult> SelectManyIterator<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector) {
 422             foreach (TSource element in source) {
 423                 foreach (TResult subElement in selector(element)) {
 424                     yield return subElement;
 425                 }
 426             }
 427         }
 428
 429         public static IEnumerable<TResult> SelectMany<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TResult>> selector) {
 430             if (source == null) throw Error.ArgumentNull("source");
 431             if (selector == null) throw Error.ArgumentNull("selector");
 432             return SelectManyIterator<TSource, TResult>(source, selector);
 433         }
 434
 435         static IEnumerable<TResult> SelectManyIterator<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TResult>> selector) {
 436             int index = -1;
 437             foreach (TSource element in source) {
 438                 checked { index++; }
 439                 foreach (TResult subElement in selector(element, index)) {
 440                     yield return subElement;
 441                 }
 442             }
 443         }
 444         public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult>(this IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector)
 445         {
 446             if (source == null) throw Error.ArgumentNull("source");
 447             if (collectionSelector == null) throw Error.ArgumentNull("collectionSelector");
 448             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 449             return SelectManyIterator<TSource, TCollection, TResult>(source, collectionSelector, resultSelector);
 450         }
 451
 452         static IEnumerable<TResult> SelectManyIterator<TSource, TCollection, TResult>(IEnumerable<TSource> source, Func<TSource, int, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector){
 453             int index = -1;
 454             foreach (TSource element in source){
 455                 checked { index++; }
 456                 foreach (TCollection subElement in collectionSelector(element, index)){
 457                     yield return resultSelector(element, subElement);
 458                 }
 459             }
 460         }
 461
 462         public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult>(this IEnumerable<TSource> source, Func<TSource, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector) {
 463             if (source == null) throw Error.ArgumentNull("source");
 464             if (collectionSelector == null) throw Error.ArgumentNull("collectionSelector");
 465             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 466             return SelectManyIterator<TSource, TCollection, TResult>(source, collectionSelector, resultSelector);
 467         }
 468
 469         static IEnumerable<TResult> SelectManyIterator<TSource, TCollection, TResult>(IEnumerable<TSource> source, Func<TSource, IEnumerable<TCollection>> collectionSelector, Func<TSource, TCollection, TResult> resultSelector) {
 470             foreach (TSource element in source) {
 471                 foreach (TCollection subElement in collectionSelector(element)) {
 472                     yield return resultSelector(element, subElement);
 473                 }
 474             }
 475         }
 476
 477         public static IEnumerable<TSource> Take<TSource>(this IEnumerable<TSource> source, int count) {
 478             if (source == null) throw Error.ArgumentNull("source");
 479             return TakeIterator<TSource>(source, count);
 480         }
 481
 482         static IEnumerable<TSource> TakeIterator<TSource>(IEnumerable<TSource> source, int count) {
 483             if (count > 0) {
 484                 foreach (TSource element in source) {
 485                     yield return element;
 486                     if (--count == 0) break;
 487                 }
 488             }
 489         }
 490
 491         public static IEnumerable<TSource> TakeWhile<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 492             if (source == null) throw Error.ArgumentNull("source");
 493             if (predicate == null) throw Error.ArgumentNull("predicate");
 494             return TakeWhileIterator<TSource>(source, predicate);
 495         }
 496
 497         static IEnumerable<TSource> TakeWhileIterator<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 498             foreach (TSource element in source) {
 499                 if (!predicate(element)) break;
 500                 yield return element;
 501             }
 502         }
 503
 504         public static IEnumerable<TSource> TakeWhile<TSource>(this IEnumerable<TSource> source, Func<TSource, int, bool> predicate) {
 505             if (source == null) throw Error.ArgumentNull("source");
 506             if (predicate == null) throw Error.ArgumentNull("predicate");
 507             return TakeWhileIterator<TSource>(source, predicate);
 508         }
 509
 510         static IEnumerable<TSource> TakeWhileIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate) {
 511             int index = -1;
 512             foreach (TSource element in source) {
 513                 checked { index++; }
 514                 if (!predicate(element, index)) break;
 515                 yield return element;
 516             }
 517         }
 518
 519         public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count) {
 520             if (source == null) throw Error.ArgumentNull("source");
 521             return SkipIterator<TSource>(source, count);
 522         }
 523
 524         static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count) {
 525             using (IEnumerator<TSource> e = source.GetEnumerator()) {
 526                 while (count > 0 && e.MoveNext()) count--;
 527                 if (count <= 0) {
 528                     while (e.MoveNext()) yield return e.Current;
 529                 }
 530             }
 531         }
 532
 533         public static IEnumerable<TSource> SkipWhile<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 534             if (source == null) throw Error.ArgumentNull("source");
 535             if (predicate == null) throw Error.ArgumentNull("predicate");
 536             return SkipWhileIterator<TSource>(source, predicate);
 537         }
 538
 539         static IEnumerable<TSource> SkipWhileIterator<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 540             bool yielding = false;
 541             foreach (TSource element in source) {
 542                 if (!yielding && !predicate(element)) yielding = true;
 543                 if (yielding) yield return element;
 544             }
 545         }
 546
 547         public static IEnumerable<TSource> SkipWhile<TSource>(this IEnumerable<TSource> source, Func<TSource, int, bool> predicate) {
 548             if (source == null) throw Error.ArgumentNull("source");
 549             if (predicate == null) throw Error.ArgumentNull("predicate");
 550             return SkipWhileIterator<TSource>(source, predicate);
 551         }
 552
 553         static IEnumerable<TSource> SkipWhileIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate) {
 554             int index = -1;
 555             bool yielding = false;
 556             foreach (TSource element in source) {
 557                 checked { index++; }
 558                 if (!yielding && !predicate(element, index)) yielding = true;
 559                 if (yielding) yield return element;
 560             }
 561         }
 562
 563         public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>(this IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector) {
 564             if (outer == null) throw Error.ArgumentNull("outer");
 565             if (inner == null) throw Error.ArgumentNull("inner");
 566             if (outerKeySelector == null) throw Error.ArgumentNull("outerKeySelector");
 567             if (innerKeySelector == null) throw Error.ArgumentNull("innerKeySelector");
 568             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 569             return JoinIterator<TOuter, TInner, TKey, TResult>(outer, inner, outerKeySelector, innerKeySelector, resultSelector, null);
 570         }
 571
 572         public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>(this IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey> comparer) {
 573             if (outer == null) throw Error.ArgumentNull("outer");
 574             if (inner == null) throw Error.ArgumentNull("inner");
 575             if (outerKeySelector == null) throw Error.ArgumentNull("outerKeySelector");
 576             if (innerKeySelector == null) throw Error.ArgumentNull("innerKeySelector");
 577             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 578             return JoinIterator<TOuter, TInner, TKey, TResult>(outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
 579         }
 580
 581         static IEnumerable<TResult> JoinIterator<TOuter, TInner, TKey, TResult>(IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey> comparer) {
 582             Lookup<TKey, TInner> lookup = Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer);
 583             foreach (TOuter item in outer) {
 584                 Lookup<TKey, TInner>.Grouping g = lookup.GetGrouping(outerKeySelector(item), false);
 585                 if (g != null) {
 586                     for (int i = 0; i < g.count; i++) {
 587                         yield return resultSelector(item, g.elements[i]);
 588                     }
 589                 }
 590             }
 591         }
 592
 593         public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult>(this IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector) {
 594             if (outer == null) throw Error.ArgumentNull("outer");
 595             if (inner == null) throw Error.ArgumentNull("inner");
 596             if (outerKeySelector == null) throw Error.ArgumentNull("outerKeySelector");
 597             if (innerKeySelector == null) throw Error.ArgumentNull("innerKeySelector");
 598             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 599             return GroupJoinIterator<TOuter, TInner, TKey, TResult>(outer, inner, outerKeySelector, innerKeySelector, resultSelector, null);
 600         }
 601
 602         public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult>(this IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector, IEqualityComparer<TKey> comparer) {
 603             if (outer == null) throw Error.ArgumentNull("outer");
 604             if (inner == null) throw Error.ArgumentNull("inner");
 605             if (outerKeySelector == null) throw Error.ArgumentNull("outerKeySelector");
 606             if (innerKeySelector == null) throw Error.ArgumentNull("innerKeySelector");
 607             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 608             return GroupJoinIterator<TOuter, TInner, TKey, TResult>(outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
 609         }
 610
 611         static IEnumerable<TResult> GroupJoinIterator<TOuter, TInner, TKey, TResult>(IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, IEnumerable<TInner>, TResult> resultSelector, IEqualityComparer<TKey> comparer) {
 612             Lookup<TKey, TInner> lookup = Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer);
 613             foreach (TOuter item in outer) {
 614                 yield return resultSelector(item, lookup[outerKeySelector(item)]);
 615             }
 616         }
 617
 618         public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 619             return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
 620         }
 621
 622         public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer) {
 623             return new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, false);
 624         }
 625
 626         public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 627             return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, true);
 628         }
 629
 630         public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer) {
 631             return new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, true);
 632         }
 633
 634         public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 635             if (source == null) throw Error.ArgumentNull("source");
 636             return source.CreateOrderedEnumerable<TKey>(keySelector, null, false);
 637         }
 638
 639         public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer) {
 640             if (source == null) throw Error.ArgumentNull("source");
 641             return source.CreateOrderedEnumerable<TKey>(keySelector, comparer, false);
 642         }
 643
 644         public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 645             if (source == null) throw Error.ArgumentNull("source");
 646             return source.CreateOrderedEnumerable<TKey>(keySelector, null, true);
 647         }
 648
 649         public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer) {
 650             if (source == null) throw Error.ArgumentNull("source");
 651             return source.CreateOrderedEnumerable<TKey>(keySelector, comparer, true);
 652         }
 653
 654         public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 655             return new GroupedEnumerable<TSource, TKey, TSource>(source, keySelector, IdentityFunction<TSource>.Instance, null);
 656         }
 657
 658         public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer) {
 659             return new GroupedEnumerable<TSource, TKey, TSource>(source, keySelector, IdentityFunction<TSource>.Instance, comparer);
 660         }
 661
 662         public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector) {
 663             return new GroupedEnumerable<TSource, TKey, TElement>(source, keySelector, elementSelector, null);
 664         }
 665
 666         public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
 667             return new GroupedEnumerable<TSource, TKey, TElement>(source, keySelector, elementSelector, comparer);
 668         }
 669
 670        public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TKey, IEnumerable<TSource>, TResult> resultSelector){
 671            return  new GroupedEnumerable<TSource, TKey, TSource, TResult>(source, keySelector, IdentityFunction<TSource>.Instance, resultSelector, null);
 672         }
 673
 674         public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, Func<TKey, IEnumerable<TElement>, TResult> resultSelector){
 675            return new GroupedEnumerable<TSource, TKey, TElement, TResult>(source, keySelector, elementSelector, resultSelector, null);
 676         }
 677
 678         public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TKey, IEnumerable<TSource>, TResult> resultSelector, IEqualityComparer<TKey> comparer){
 679             return  new GroupedEnumerable<TSource, TKey, TSource, TResult>(source, keySelector, IdentityFunction<TSource>.Instance, resultSelector, comparer);
 680         }
 681
 682         public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, Func<TKey, IEnumerable<TElement>, TResult> resultSelector, IEqualityComparer<TKey> comparer){
 683             return  new GroupedEnumerable<TSource, TKey, TElement, TResult>(source, keySelector, elementSelector, resultSelector, comparer);
 684         }
 685
 686         public static IEnumerable<TSource> Concat<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
 687             if (first == null) throw Error.ArgumentNull("first");
 688             if (second == null) throw Error.ArgumentNull("second");
 689             return ConcatIterator<TSource>(first, second);
 690         }
 691
 692         static IEnumerable<TSource> ConcatIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second) {
 693             foreach (TSource element in first) yield return element;
 694             foreach (TSource element in second) yield return element;
 695         }
 696
 697 #if NETSTANDARD
 698         public static IEnumerable<TSource> Append<TSource>(this IEnumerable<TSource> source, TSource element)
 699         {
 700             if (source == null) throw Error.ArgumentNull("source");
 701             return AppendIterator<TSource>(source, element);
 702         }
 703
 704         private static IEnumerable<TSource> AppendIterator<TSource>(IEnumerable<TSource> source, TSource element)
 705         {
 706             foreach (TSource e1 in source) yield return e1;
 707             yield return element;
 708         }
 709
 710         public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource element)
 711         {
 712             if (source == null) throw Error.ArgumentNull("source");
 713             return PrependIterator<TSource>(source, element);
 714         }
 715
 716         private static IEnumerable<TSource> PrependIterator<TSource>(IEnumerable<TSource> source, TSource element)
 717         {
 718             yield return element;
 719             foreach (TSource e1 in source) yield return e1;
 720         }
 721 #endif
 722
 723         public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector) {
 724             if (first == null) throw Error.ArgumentNull("first");
 725             if (second == null) throw Error.ArgumentNull("second");
 726             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 727             return ZipIterator(first, second, resultSelector);
 728         }
 729
 730         static IEnumerable<TResult> ZipIterator<TFirst, TSecond, TResult>(IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector) {
 731             using (IEnumerator<TFirst> e1 = first.GetEnumerator())
 732                 using (IEnumerator<TSecond> e2 = second.GetEnumerator())
 733                     while (e1.MoveNext() && e2.MoveNext())
 734                         yield return resultSelector(e1.Current, e2.Current);
 735         }
 736
 737
 738         public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source) {
 739             if (source == null) throw Error.ArgumentNull("source");
 740             return DistinctIterator<TSource>(source, null);
 741         }
 742
 743         public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer) {
 744             if (source == null) throw Error.ArgumentNull("source");
 745             return DistinctIterator<TSource>(source, comparer);
 746         }
 747
 748         static IEnumerable<TSource> DistinctIterator<TSource>(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer) {
 749             Set<TSource> set = new Set<TSource>(comparer);
 750             foreach (TSource element in source)
 751                 if (set.Add(element)) yield return element;
 752         }
 753
 754         public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
 755             if (first == null) throw Error.ArgumentNull("first");
 756             if (second == null) throw Error.ArgumentNull("second");
 757             return UnionIterator<TSource>(first, second, null);
 758         }
 759
 760         public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 761         {
 762             if (first == null) throw Error.ArgumentNull("first");
 763             if (second == null) throw Error.ArgumentNull("second");
 764             return UnionIterator<TSource>(first, second, comparer);
 765         }
 766
 767         static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 768         {
 769             Set<TSource> set = new Set<TSource>(comparer);
 770             foreach (TSource element in first)
 771                 if (set.Add(element)) yield return element;
 772             foreach (TSource element in second)
 773                 if (set.Add(element)) yield return element;
 774         }
 775
 776         public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
 777             if (first == null) throw Error.ArgumentNull("first");
 778             if (second == null) throw Error.ArgumentNull("second");
 779             return IntersectIterator<TSource>(first, second, null);
 780         }
 781
 782         public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 783         {
 784             if (first == null) throw Error.ArgumentNull("first");
 785             if (second == null) throw Error.ArgumentNull("second");
 786             return IntersectIterator<TSource>(first, second, comparer);
 787         }
 788
 789         static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 790         {
 791             Set<TSource> set = new Set<TSource>(comparer);
 792             foreach (TSource element in second) set.Add(element);
 793             foreach (TSource element in first)
 794                 if (set.Remove(element)) yield return element;
 795         }
 796
 797         public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
 798         {
 799             if (first == null) throw Error.ArgumentNull("first");
 800             if (second == null) throw Error.ArgumentNull("second");
 801             return ExceptIterator<TSource>(first, second, null);
 802         }
 803
 804         public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 805         {
 806             if (first == null) throw Error.ArgumentNull("first");
 807             if (second == null) throw Error.ArgumentNull("second");
 808             return ExceptIterator<TSource>(first, second, comparer);
 809         }
 810
 811         static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) {
 812             Set<TSource> set = new Set<TSource>(comparer);
 813             foreach (TSource element in second) set.Add(element);
 814             foreach (TSource element in first)
 815                 if (set.Add(element)) yield return element;
 816         }
 817
 818         public static IEnumerable<TSource> Reverse<TSource>(this IEnumerable<TSource> source) {
 819             if (source == null) throw Error.ArgumentNull("source");
 820             return ReverseIterator<TSource>(source);
 821         }
 822
 823         static IEnumerable<TSource> ReverseIterator<TSource>(IEnumerable<TSource> source) {
 824             Buffer<TSource> buffer = new Buffer<TSource>(source);
 825             for (int i = buffer.count - 1; i >= 0; i--) yield return buffer.items[i];
 826         }
 827
 828         public static bool SequenceEqual<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
 829             return SequenceEqual<TSource>(first, second, null);
 830         }
 831
 832         public static bool SequenceEqual<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 833         {
 834             if (comparer == null) comparer = EqualityComparer<TSource>.Default;
 835             if (first == null) throw Error.ArgumentNull("first");
 836             if (second == null) throw Error.ArgumentNull("second");
 837             using (IEnumerator<TSource> e1 = first.GetEnumerator())
 838             using (IEnumerator<TSource> e2 = second.GetEnumerator())
 839             {
 840                 while (e1.MoveNext())
 841                 {
 842                     if (!(e2.MoveNext() && comparer.Equals(e1.Current, e2.Current))) return false;
 843                 }
 844                 if (e2.MoveNext()) return false;
 845             }
 846             return true;
 847         }
 848
 849         public static IEnumerable<TSource> AsEnumerable<TSource>(this IEnumerable<TSource> source)
 850         {
 851             return source;
 852         }
 853
 854         public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source) {
 855             if (source == null) throw Error.ArgumentNull("source");
 856             return new Buffer<TSource>(source).ToArray();
 857         }
 858
 859         public static List<TSource> ToList<TSource>(this IEnumerable<TSource> source) {
 860             if (source == null) throw Error.ArgumentNull("source");
 861             return new List<TSource>(source);
 862         }
 863
 864         public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 865             return ToDictionary<TSource, TKey, TSource>(source, keySelector, IdentityFunction<TSource>.Instance, null);
 866         }
 867
 868         public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer) {
 869             return ToDictionary<TSource, TKey, TSource>(source, keySelector, IdentityFunction<TSource>.Instance, comparer);
 870         }
 871
 872         public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector) {
 873             return ToDictionary<TSource, TKey, TElement>(source, keySelector, elementSelector, null);
 874         }
 875
 876         public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
 877             if (source == null) throw Error.ArgumentNull("source");
 878             if (keySelector == null) throw Error.ArgumentNull("keySelector");
 879             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
 880             Dictionary<TKey, TElement> d = new Dictionary<TKey, TElement>(comparer);
 881             foreach (TSource element in source) d.Add(keySelector(element), elementSelector(element));
 882             return d;
 883         }
 884
 885         public static ILookup<TKey, TSource> ToLookup<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 886             return Lookup<TKey, TSource>.Create(source, keySelector, IdentityFunction<TSource>.Instance, null);
 887         }
 888
 889         public static ILookup<TKey, TSource> ToLookup<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer) {
 890             return Lookup<TKey, TSource>.Create(source, keySelector, IdentityFunction<TSource>.Instance, comparer);
 891         }
 892
 893         public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector) {
 894             return Lookup<TKey, TElement>.Create(source, keySelector, elementSelector, null);
 895         }
 896
 897         public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
 898             return Lookup<TKey, TElement>.Create(source, keySelector, elementSelector, comparer);
 899         }
 900
 901         public static IEnumerable<TSource> DefaultIfEmpty<TSource>(this IEnumerable<TSource> source) {
 902             return DefaultIfEmpty(source, default(TSource));
 903         }
 904
 905         public static IEnumerable<TSource> DefaultIfEmpty<TSource>(this IEnumerable<TSource> source, TSource defaultValue) {
 906             if (source == null) throw Error.ArgumentNull("source");
 907             return DefaultIfEmptyIterator<TSource>(source, defaultValue);
 908         }
 909
 910         static IEnumerable<TSource> DefaultIfEmptyIterator<TSource>(IEnumerable<TSource> source, TSource defaultValue) {
 911             using (IEnumerator<TSource> e = source.GetEnumerator()) {
 912                 if (e.MoveNext()) {
 913                     do {
 914                         yield return e.Current;
 915                     } while (e.MoveNext());
 916                 }
 917                 else {
 918                     yield return defaultValue;
 919                 }
 920             }
 921         }
 922
 923         public static IEnumerable<TResult> OfType<TResult>(this IEnumerable source) {
 924             if (source == null) throw Error.ArgumentNull("source");
 925             return OfTypeIterator<TResult>(source);
 926         }
 927
 928         static IEnumerable<TResult> OfTypeIterator<TResult>(IEnumerable source) {
 929             foreach (object obj in source) {
 930                 if (obj is TResult) yield return (TResult)obj;
 931             }
 932         }
 933
 934         public static IEnumerable<TResult> Cast<TResult>(this IEnumerable source) {
 935             IEnumerable<TResult> typedSource = source as IEnumerable<TResult>;
 936             if (typedSource != null) return typedSource;
 937             if (source == null) throw Error.ArgumentNull("source");
 938             return CastIterator<TResult>(source);
 939         }
 940
 941         static IEnumerable<TResult> CastIterator<TResult>(IEnumerable source) {
 942             foreach (object obj in source) yield return (TResult)obj;
 943         }
 944
 945         public static TSource First<TSource>(this IEnumerable<TSource> source) {
 946             if (source == null) throw Error.ArgumentNull("source");
 947             IList<TSource> list = source as IList<TSource>;
 948             if (list != null) {
 949                 if (list.Count > 0) return list[0];
 950             }
 951             else {
 952                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
 953                     if (e.MoveNext()) return e.Current;
 954                 }
 955             }
 956             throw Error.NoElements();
 957         }
 958
 959         public static TSource First<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 960             if (source == null) throw Error.ArgumentNull("source");
 961             if (predicate == null) throw Error.ArgumentNull("predicate");
 962             foreach (TSource element in source) {
 963                 if (predicate(element)) return element;
 964             }
 965             throw Error.NoMatch();
 966         }
 967
 968         public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source) {
 969             if (source == null) throw Error.ArgumentNull("source");
 970             IList<TSource> list = source as IList<TSource>;
 971             if (list != null) {
 972                 if (list.Count > 0) return list[0];
 973             }
 974             else {
 975                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
 976                     if (e.MoveNext()) return e.Current;
 977                 }
 978             }
 979             return default(TSource);
 980         }
 981
 982         public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 983             if (source == null) throw Error.ArgumentNull("source");
 984             if (predicate == null) throw Error.ArgumentNull("predicate");
 985             foreach (TSource element in source) {
 986                 if (predicate(element)) return element;
 987             }
 988             return default(TSource);
 989         }
 990
 991         public static TSource Last<TSource>(this IEnumerable<TSource> source) {
 992             if (source == null) throw Error.ArgumentNull("source");
 993             IList<TSource> list = source as IList<TSource>;
 994             if (list != null) {
 995                 int count = list.Count;
 996                 if (count > 0) return list[count - 1];
 997             }
 998             else {
 999                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
1000                     if (e.MoveNext()) {
1001                         TSource result;
1002                         do {
1003                             result = e.Current;
1004                         } while (e.MoveNext());
1005                         return result;
1006                     }
1007                 }
1008             }
1009             throw Error.NoElements();
1010         }
1011
1012         public static TSource Last<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1013             if (source == null) throw Error.ArgumentNull("source");
1014             if (predicate == null) throw Error.ArgumentNull("predicate");
1015             TSource result = default(TSource);
1016             bool found = false;
1017             foreach (TSource element in source) {
1018                 if (predicate(element)) {
1019                     result = element;
1020                     found = true;
1021                 }
1022             }
1023             if (found) return result;
1024             throw Error.NoMatch();
1025         }
1026
1027         public static TSource LastOrDefault<TSource>(this IEnumerable<TSource> source) {
1028             if (source == null) throw Error.ArgumentNull("source");
1029             IList<TSource> list = source as IList<TSource>;
1030             if (list != null) {
1031                 int count = list.Count;
1032                 if (count > 0) return list[count - 1];
1033             }
1034             else {
1035                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
1036                     if (e.MoveNext()) {
1037                         TSource result;
1038                         do {
1039                             result = e.Current;
1040                         } while (e.MoveNext());
1041                         return result;
1042                     }
1043                 }
1044             }
1045             return default(TSource);
1046         }
1047
1048         public static TSource LastOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1049             if (source == null) throw Error.ArgumentNull("source");
1050             if (predicate == null) throw Error.ArgumentNull("predicate");
1051             TSource result = default(TSource);
1052             foreach (TSource element in source) {
1053                 if (predicate(element)) {
1054                     result = element;
1055                 }
1056             }
1057             return result;
1058         }
1059
1060         public static TSource Single<TSource>(this IEnumerable<TSource> source) {
1061             if (source == null) throw Error.ArgumentNull("source");
1062             IList<TSource> list = source as IList<TSource>;
1063             if (list != null) {
1064                 switch (list.Count) {
1065                     case 0: throw Error.NoElements();
1066                     case 1: return list[0];
1067                 }
1068             }
1069             else {
1070                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
1071                     if (!e.MoveNext()) throw Error.NoElements();
1072                     TSource result = e.Current;
1073                     if (!e.MoveNext()) return result;
1074                 }
1075             }
1076             throw Error.MoreThanOneElement();
1077         }
1078
1079         public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1080             if (source == null) throw Error.ArgumentNull("source");
1081             if (predicate == null) throw Error.ArgumentNull("predicate");
1082             TSource result = default(TSource);
1083             long count = 0;
1084             foreach (TSource element in source) {
1085                 if (predicate(element)) {
1086                     result = element;
1087                     checked { count++; }
1088                 }
1089             }
1090             switch (count) {
1091                 case 0: throw Error.NoMatch();
1092                 case 1: return result;
1093             }
1094             throw Error.MoreThanOneMatch();
1095         }
1096
1097         public static TSource SingleOrDefault<TSource>(this IEnumerable<TSource> source) {
1098             if (source == null) throw Error.ArgumentNull("source");
1099             IList<TSource> list = source as IList<TSource>;
1100             if (list != null) {
1101                 switch (list.Count) {
1102                     case 0: return default(TSource);
1103                     case 1: return list[0];
1104                 }
1105             }
1106             else {
1107                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
1108                     if (!e.MoveNext()) return default(TSource);
1109                     TSource result = e.Current;
1110                     if (!e.MoveNext()) return result;
1111                 }
1112             }
1113             throw Error.MoreThanOneElement();
1114         }
1115
1116         public static TSource SingleOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1117             if (source == null) throw Error.ArgumentNull("source");
1118             if (predicate == null) throw Error.ArgumentNull("predicate");
1119             TSource result = default(TSource);
1120             long count = 0;
1121             foreach (TSource element in source) {
1122                 if (predicate(element)) {
1123                     result = element;
1124                     checked { count++; }
1125                 }
1126             }
1127             switch (count) {
1128                 case 0: return default(TSource);
1129                 case 1: return result;
1130             }
1131             throw Error.MoreThanOneMatch();
1132         }
1133
1134         public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, int index) {
1135             if (source == null) throw Error.ArgumentNull("source");
1136             IList<TSource> list = source as IList<TSource>;
1137             if (list != null) return list[index];
1138             if (index < 0) throw Error.ArgumentOutOfRange("index");
1139             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1140                 while (true) {
1141                     if (!e.MoveNext()) throw Error.ArgumentOutOfRange("index");
1142                     if (index == 0) return e.Current;
1143                     index--;
1144                 }
1145             }
1146         }
1147
1148         public static TSource ElementAtOrDefault<TSource>(this IEnumerable<TSource> source, int index) {
1149             if (source == null) throw Error.ArgumentNull("source");
1150             if (index >= 0) {
1151                 IList<TSource> list = source as IList<TSource>;
1152                 if (list != null) {
1153                     if (index < list.Count) return list[index];
1154                 }
1155                 else {
1156                     using (IEnumerator<TSource> e = source.GetEnumerator()) {
1157                         while (true) {
1158                             if (!e.MoveNext()) break;
1159                             if (index == 0) return e.Current;
1160                             index--;
1161                         }
1162                     }
1163                 }
1164             }
1165             return default(TSource);
1166         }
1167
1168         public static IEnumerable<int> Range(int start, int count) {
1169             long max = ((long)start) + count - 1;
1170             if (count < 0 || max > Int32.MaxValue) throw Error.ArgumentOutOfRange("count");
1171             return RangeIterator(start, count);
1172         }
1173
1174         static IEnumerable<int> RangeIterator(int start, int count) {
1175             for (int i = 0; i < count; i++) yield return start + i;
1176         }
1177
1178         public static IEnumerable<TResult> Repeat<TResult>(TResult element, int count) {
1179             if (count < 0) throw Error.ArgumentOutOfRange("count");
1180             return RepeatIterator<TResult>(element, count);
1181         }
1182
1183         static IEnumerable<TResult> RepeatIterator<TResult>(TResult element, int count) {
1184             for (int i = 0; i < count; i++) yield return element;
1185         }
1186
1187         public static IEnumerable<TResult> Empty<TResult>() {
1188             return EmptyEnumerable<TResult>.Instance;
1189         }
1190
1191         public static bool Any<TSource>(this IEnumerable<TSource> source) {
1192             if (source == null) throw Error.ArgumentNull("source");
1193             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1194                 if (e.MoveNext()) return true;
1195             }
1196             return false;
1197         }
1198
1199         public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1200             if (source == null) throw Error.ArgumentNull("source");
1201             if (predicate == null) throw Error.ArgumentNull("predicate");
1202             foreach (TSource element in source) {
1203                 if (predicate(element)) return true;
1204             }
1205             return false;
1206         }
1207
1208         public static bool All<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1209             if (source == null) throw Error.ArgumentNull("source");
1210             if (predicate == null) throw Error.ArgumentNull("predicate");
1211             foreach (TSource element in source) {
1212                 if (!predicate(element)) return false;
1213             }
1214             return true;
1215         }
1216
1217         public static int Count<TSource>(this IEnumerable<TSource> source) {
1218             if (source == null) throw Error.ArgumentNull("source");
1219             ICollection<TSource> collectionoft = source as ICollection<TSource>;
1220             if (collectionoft != null) return collectionoft.Count;
1221             ICollection collection = source as ICollection;
1222             if (collection != null) return collection.Count;
1223             int count = 0;
1224             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1225                 checked {
1226                     while (e.MoveNext()) count++;
1227                 }
1228             }
1229             return count;
1230         }
1231
1232         public static int Count<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1233             if (source == null) throw Error.ArgumentNull("source");
1234             if (predicate == null) throw Error.ArgumentNull("predicate");
1235             int count = 0;
1236             foreach (TSource element in source) {
1237                 checked {
1238                     if (predicate(element)) count++;
1239                 }
1240             }
1241             return count;
1242         }
1243
1244         public static long LongCount<TSource>(this IEnumerable<TSource> source) {
1245             if (source == null) throw Error.ArgumentNull("source");
1246             long count = 0;
1247             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1248                 checked {
1249                     while (e.MoveNext()) count++;
1250                 }
1251             }
1252             return count;
1253         }
1254
1255         public static long LongCount<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1256             if (source == null) throw Error.ArgumentNull("source");
1257             if (predicate == null) throw Error.ArgumentNull("predicate");
1258             long count = 0;
1259             foreach (TSource element in source) {
1260                 checked {
1261                     if (predicate(element)) count++;
1262                 }
1263             }
1264             return count;
1265         }
1266
1267         public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value) {
1268             ICollection<TSource> collection = source as ICollection<TSource>;
1269             if (collection != null) return collection.Contains(value);
1270             return Contains<TSource>(source, value, null);
1271         }
1272
1273         public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value, IEqualityComparer<TSource> comparer)
1274         {
1275             if (comparer == null) comparer = EqualityComparer<TSource>.Default;
1276             if (source == null) throw Error.ArgumentNull("source");
1277             foreach (TSource element in source)
1278                 if (comparer.Equals(element, value)) return true;
1279             return false;
1280         }
1281
1282         public static TSource Aggregate<TSource>(this IEnumerable<TSource> source, Func<TSource, TSource, TSource> func)
1283         {
1284             if (source == null) throw Error.ArgumentNull("source");
1285             if (func == null) throw Error.ArgumentNull("func");
1286             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1287                 if (!e.MoveNext()) throw Error.NoElements();
1288                 TSource result = e.Current;
1289                 while (e.MoveNext()) result = func(result, e.Current);
1290                 return result;
1291             }
1292         }
1293
1294         public static TAccumulate Aggregate<TSource, TAccumulate>(this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func) {
1295             if (source == null) throw Error.ArgumentNull("source");
1296             if (func == null) throw Error.ArgumentNull("func");
1297             TAccumulate result = seed;
1298             foreach (TSource element in source) result = func(result, element);
1299             return result;
1300         }
1301
1302         public static TResult Aggregate<TSource, TAccumulate, TResult>(this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func, Func<TAccumulate, TResult> resultSelector) {
1303             if (source == null) throw Error.ArgumentNull("source");
1304             if (func == null) throw Error.ArgumentNull("func");
1305             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
1306             TAccumulate result = seed;
1307             foreach (TSource element in source) result = func(result, element);
1308             return resultSelector(result);
1309         }
1310
1311         public static int Sum(this IEnumerable<int> source) {
1312             if (source == null) throw Error.ArgumentNull("source");
1313             int sum = 0;
1314             checked {
1315                 foreach (int v in source) sum += v;
1316             }
1317             return sum;
1318         }
1319
1320         public static int? Sum(this IEnumerable<int?> source) {
1321             if (source == null) throw Error.ArgumentNull("source");
1322             int sum = 0;
1323             checked {
1324                 foreach (int? v in source) {
1325                     if (v != null) sum += v.GetValueOrDefault();
1326                 }
1327             }
1328             return sum;
1329         }
1330
1331         public static long Sum(this IEnumerable<long> source) {
1332             if (source == null) throw Error.ArgumentNull("source");
1333             long sum = 0;
1334             checked {
1335                 foreach (long v in source) sum += v;
1336             }
1337             return sum;
1338         }
1339
1340         public static long? Sum(this IEnumerable<long?> source) {
1341             if (source == null) throw Error.ArgumentNull("source");
1342             long sum = 0;
1343             checked {
1344                 foreach (long? v in source) {
1345                     if (v != null) sum += v.GetValueOrDefault();
1346                 }
1347             }
1348             return sum;
1349         }
1350
1351         public static float Sum(this IEnumerable<float> source) {
1352             if (source == null) throw Error.ArgumentNull("source");
1353             double sum = 0;
1354             foreach (float v in source) sum += v;
1355             return (float)sum;
1356         }
1357
1358         public static float? Sum(this IEnumerable<float?> source) {
1359             if (source == null) throw Error.ArgumentNull("source");
1360             double sum = 0;
1361             foreach (float? v in source) {
1362                 if (v != null) sum += v.GetValueOrDefault();
1363             }
1364             return (float)sum;
1365         }
1366
1367         public static double Sum(this IEnumerable<double> source) {
1368             if (source == null) throw Error.ArgumentNull("source");
1369             double sum = 0;
1370             foreach (double v in source) sum += v;
1371             return sum;
1372         }
1373
1374         public static double? Sum(this IEnumerable<double?> source) {
1375             if (source == null) throw Error.ArgumentNull("source");
1376             double sum = 0;
1377             foreach (double? v in source) {
1378                 if (v != null) sum += v.GetValueOrDefault();
1379             }
1380             return sum;
1381         }
1382
1383         public static decimal Sum(this IEnumerable<decimal> source) {
1384             if (source == null) throw Error.ArgumentNull("source");
1385             decimal sum = 0;
1386             foreach (decimal v in source) sum += v;
1387             return sum;
1388         }
1389
1390         public static decimal? Sum(this IEnumerable<decimal?> source) {
1391             if (source == null) throw Error.ArgumentNull("source");
1392             decimal sum = 0;
1393             foreach (decimal? v in source) {
1394                 if (v != null) sum += v.GetValueOrDefault();
1395             }
1396             return sum;
1397         }
1398
1399         public static int Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
1400             return Enumerable.Sum(Enumerable.Select(source, selector));
1401         }
1402
1403         public static int? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
1404             return Enumerable.Sum(Enumerable.Select(source, selector));
1405         }
1406
1407         public static long Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
1408             return Enumerable.Sum(Enumerable.Select(source, selector));
1409         }
1410
1411         public static long? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
1412             return Enumerable.Sum(Enumerable.Select(source, selector));
1413         }
1414
1415         public static float Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
1416             return Enumerable.Sum(Enumerable.Select(source, selector));
1417         }
1418
1419         public static float? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
1420             return Enumerable.Sum(Enumerable.Select(source, selector));
1421         }
1422
1423         public static double Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
1424             return Enumerable.Sum(Enumerable.Select(source, selector));
1425         }
1426
1427         public static double? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
1428             return Enumerable.Sum(Enumerable.Select(source, selector));
1429         }
1430
1431         public static decimal Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
1432             return Enumerable.Sum(Enumerable.Select(source, selector));
1433         }
1434
1435         public static decimal? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
1436             return Enumerable.Sum(Enumerable.Select(source, selector));
1437         }
1438
1439         public static int Min(this IEnumerable<int> source) {
1440             if (source == null) throw Error.ArgumentNull("source");
1441             int value = 0;
1442             bool hasValue = false;
1443             foreach (int x in source) {
1444                 if (hasValue) {
1445                     if (x < value) value = x;
1446                 }
1447                 else {
1448                     value = x;
1449                     hasValue = true;
1450                 }
1451             }
1452             if (hasValue) return value;
1453             throw Error.NoElements();
1454         }
1455
1456         public static int? Min(this IEnumerable<int?> source) {
1457             if (source == null) throw Error.ArgumentNull("source");
1458             int? value = null;
1459             foreach (int? x in source) {
1460                 if (value == null || x < value)
1461                     value = x;
1462             }
1463             return value;
1464         }
1465
1466         public static long Min(this IEnumerable<long> source) {
1467             if (source == null) throw Error.ArgumentNull("source");
1468             long value = 0;
1469             bool hasValue = false;
1470             foreach (long x in source) {
1471                 if (hasValue) {
1472                     if (x < value) value = x;
1473                 }
1474                 else {
1475                     value = x;
1476                     hasValue = true;
1477                 }
1478             }
1479             if (hasValue) return value;
1480             throw Error.NoElements();
1481         }
1482
1483         public static long? Min(this IEnumerable<long?> source) {
1484             if (source == null) throw Error.ArgumentNull("source");
1485             long? value = null;
1486             foreach (long? x in source) {
1487                 if (value == null || x < value) value = x;
1488             }
1489             return value;
1490         }
1491
1492         public static float Min(this IEnumerable<float> source) {
1493             if (source == null) throw Error.ArgumentNull("source");
1494             float value = 0;
1495             bool hasValue = false;
1496             foreach (float x in source) {
1497                 if (hasValue) {
1498                     // Normally NaN < anything is false, as is anything < NaN
1499                     // However, this leads to some irksome outcomes in Min and Max.
1500                     // If we use those semantics then Min(NaN, 5.0) is NaN, but
1501                     // Min(5.0, NaN) is 5.0!  To fix this, we impose a total
1502                     // ordering where NaN is smaller than every value, including
1503                     // negative infinity.
1504                     if (x < value || System.Single.IsNaN(x)) value = x;
1505                 }
1506                 else {
1507                     value = x;
1508                     hasValue = true;
1509                 }
1510             }
1511             if (hasValue) return value;
1512             throw Error.NoElements();
1513         }
1514
1515         public static float? Min(this IEnumerable<float?> source) {
1516             if (source == null) throw Error.ArgumentNull("source");
1517             float? value = null;
1518             foreach (float? x in source) {
1519                 if (x == null) continue;
1520                 if (value == null || x < value || System.Single.IsNaN((float)x)) value = x;
1521             }
1522             return value;
1523         }
1524
1525         public static double Min(this IEnumerable<double> source) {
1526             if (source == null) throw Error.ArgumentNull("source");
1527             double value = 0;
1528             bool hasValue = false;
1529             foreach (double x in source) {
1530                 if (hasValue) {
1531                     if (x < value || System.Double.IsNaN(x)) value = x;
1532                 }
1533                 else {
1534                     value = x;
1535                     hasValue = true;
1536                 }
1537             }
1538             if (hasValue) return value;
1539             throw Error.NoElements();
1540         }
1541
1542         public static double? Min(this IEnumerable<double?> source) {
1543             if (source == null) throw Error.ArgumentNull("source");
1544             double? value = null;
1545             foreach (double? x in source) {
1546                 if (x == null) continue;
1547                 if (value == null || x < value || System.Double.IsNaN((double)x)) value = x;
1548             }
1549             return value;
1550         }
1551
1552         public static decimal Min(this IEnumerable<decimal> source) {
1553             if (source == null) throw Error.ArgumentNull("source");
1554             decimal value = 0;
1555             bool hasValue = false;
1556             foreach (decimal x in source) {
1557                 if (hasValue) {
1558                     if (x < value) value = x;
1559                 }
1560                 else {
1561                     value = x;
1562                     hasValue = true;
1563                 }
1564             }
1565             if (hasValue) return value;
1566             throw Error.NoElements();
1567         }
1568
1569         public static decimal? Min(this IEnumerable<decimal?> source) {
1570             if (source == null) throw Error.ArgumentNull("source");
1571             decimal? value = null;
1572             foreach (decimal? x in source) {
1573                 if (value == null || x < value) value = x;
1574             }
1575             return value;
1576         }
1577
1578         public static TSource Min<TSource>(this IEnumerable<TSource> source) {
1579             if (source == null) throw Error.ArgumentNull("source");
1580             Comparer<TSource> comparer = Comparer<TSource>.Default;
1581             TSource value = default(TSource);
1582             if (value == null) {
1583                 foreach (TSource x in source) {
1584                     if (x != null && (value == null || comparer.Compare(x, value) < 0))
1585                         value = x;
1586                 }
1587                 return value;
1588             }
1589             else {
1590                 bool hasValue = false;
1591                 foreach (TSource x in source) {
1592                     if (hasValue) {
1593                         if (comparer.Compare(x, value) < 0)
1594                             value = x;
1595                     }
1596                     else {
1597                         value = x;
1598                         hasValue = true;
1599                     }
1600                 }
1601                 if (hasValue) return value;
1602                 throw Error.NoElements();
1603             }
1604         }
1605
1606         public static int Min<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
1607             return Enumerable.Min(Enumerable.Select(source, selector));
1608         }
1609
1610         public static int? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
1611             return Enumerable.Min(Enumerable.Select(source, selector));
1612         }
1613
1614         public static long Min<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
1615             return Enumerable.Min(Enumerable.Select(source, selector));
1616         }
1617
1618         public static long? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
1619             return Enumerable.Min(Enumerable.Select(source, selector));
1620         }
1621
1622         public static float Min<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
1623             return Enumerable.Min(Enumerable.Select(source, selector));
1624         }
1625
1626         public static float? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
1627             return Enumerable.Min(Enumerable.Select(source, selector));
1628         }
1629
1630         public static double Min<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
1631             return Enumerable.Min(Enumerable.Select(source, selector));
1632         }
1633
1634         public static double? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
1635             return Enumerable.Min(Enumerable.Select(source, selector));
1636         }
1637
1638         public static decimal Min<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
1639             return Enumerable.Min(Enumerable.Select(source, selector));
1640         }
1641
1642         public static decimal? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
1643             return Enumerable.Min(Enumerable.Select(source, selector));
1644         }
1645
1646         public static TResult Min<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector) {
1647             return Enumerable.Min(Enumerable.Select(source, selector));
1648         }
1649
1650         public static int Max(this IEnumerable<int> source) {
1651             if (source == null) throw Error.ArgumentNull("source");
1652             int value = 0;
1653             bool hasValue = false;
1654             foreach (int x in source) {
1655                 if (hasValue) {
1656                     if (x > value) value = x;
1657                 }
1658                 else {
1659                     value = x;
1660                     hasValue = true;
1661                 }
1662             }
1663             if (hasValue) return value;
1664             throw Error.NoElements();
1665         }
1666
1667         public static int? Max(this IEnumerable<int?> source) {
1668             if (source == null) throw Error.ArgumentNull("source");
1669             int? value = null;
1670             foreach (int? x in source) {
1671                 if (value == null || x > value) value = x;
1672             }
1673             return value;
1674         }
1675
1676         public static long Max(this IEnumerable<long> source) {
1677             if (source == null) throw Error.ArgumentNull("source");
1678             long value = 0;
1679             bool hasValue = false;
1680             foreach (long x in source) {
1681                 if (hasValue) {
1682                     if (x > value) value = x;
1683                 }
1684                 else {
1685                     value = x;
1686                     hasValue = true;
1687                 }
1688             }
1689             if (hasValue) return value;
1690             throw Error.NoElements();
1691         }
1692
1693         public static long? Max(this IEnumerable<long?> source) {
1694             if (source == null) throw Error.ArgumentNull("source");
1695             long? value = null;
1696             foreach (long? x in source) {
1697                 if (value == null || x > value) value = x;
1698             }
1699             return value;
1700         }
1701
1702         public static double Max(this IEnumerable<double> source) {
1703             if (source == null) throw Error.ArgumentNull("source");
1704             double value = 0;
1705             bool hasValue = false;
1706             foreach (double x in source) {
1707                 if (hasValue) {
1708                     if (x > value || System.Double.IsNaN(value)) value = x;
1709                 }
1710                 else {
1711                     value = x;
1712                     hasValue = true;
1713                 }
1714             }
1715             if (hasValue) return value;
1716             throw Error.NoElements();
1717         }
1718
1719         public static double? Max(this IEnumerable<double?> source) {
1720             if (source == null) throw Error.ArgumentNull("source");
1721             double? value = null;
1722             foreach (double? x in source) {
1723                 if (x == null) continue;
1724                 if (value == null || x > value || System.Double.IsNaN((double)value)) value = x;
1725             }
1726             return value;
1727         }
1728
1729         public static float Max(this IEnumerable<float> source) {
1730             if (source == null) throw Error.ArgumentNull("source");
1731             float value = 0;
1732             bool hasValue = false;
1733             foreach (float x in source) {
1734                 if (hasValue) {
1735                     if (x > value || System.Double.IsNaN(value)) value = x;
1736                 }
1737                 else {
1738                     value = x;
1739                     hasValue = true;
1740                 }
1741             }
1742             if (hasValue) return value;
1743             throw Error.NoElements();
1744         }
1745
1746         public static float? Max(this IEnumerable<float?> source) {
1747             if (source == null) throw Error.ArgumentNull("source");
1748             float? value = null;
1749             foreach (float? x in source) {
1750                 if (x == null) continue;
1751                 if (value == null || x > value || System.Single.IsNaN((float)value)) value = x;
1752             }
1753             return value;
1754         }
1755
1756         public static decimal Max(this IEnumerable<decimal> source) {
1757             if (source == null) throw Error.ArgumentNull("source");
1758             decimal value = 0;
1759             bool hasValue = false;
1760             foreach (decimal x in source) {
1761                 if (hasValue) {
1762                     if (x > value) value = x;
1763                 }
1764                 else {
1765                     value = x;
1766                     hasValue = true;
1767                 }
1768             }
1769             if (hasValue) return value;
1770             throw Error.NoElements();
1771         }
1772
1773         public static decimal? Max(this IEnumerable<decimal?> source) {
1774             if (source == null) throw Error.ArgumentNull("source");
1775             decimal? value = null;
1776             foreach (decimal? x in source) {
1777                 if (value == null || x > value) value = x;
1778             }
1779             return value;
1780         }
1781
1782         public static TSource Max<TSource>(this IEnumerable<TSource> source) {
1783             if (source == null) throw Error.ArgumentNull("source");
1784             Comparer<TSource> comparer = Comparer<TSource>.Default;
1785             TSource value = default(TSource);
1786             if (value == null) {
1787                 foreach (TSource x in source) {
1788                     if (x != null && (value == null || comparer.Compare(x, value) > 0))
1789                         value = x;
1790                 }
1791                 return value;
1792             }
1793             else {
1794                 bool hasValue = false;
1795                 foreach (TSource x in source) {
1796                     if (hasValue) {
1797                         if (comparer.Compare(x, value) > 0)
1798                             value = x;
1799                     }
1800                     else {
1801                         value = x;
1802                         hasValue = true;
1803                     }
1804                 }
1805                 if (hasValue) return value;
1806                 throw Error.NoElements();
1807             }
1808         }
1809
1810         public static int Max<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
1811             return Enumerable.Max(Enumerable.Select(source, selector));
1812         }
1813
1814         public static int? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
1815             return Enumerable.Max(Enumerable.Select(source, selector));
1816         }
1817
1818         public static long Max<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
1819             return Enumerable.Max(Enumerable.Select(source, selector));
1820         }
1821
1822         public static long? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
1823             return Enumerable.Max(Enumerable.Select(source, selector));
1824         }
1825
1826         public static float Max<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
1827             return Enumerable.Max(Enumerable.Select(source, selector));
1828         }
1829
1830         public static float? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
1831             return Enumerable.Max(Enumerable.Select(source, selector));
1832         }
1833
1834         public static double Max<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
1835             return Enumerable.Max(Enumerable.Select(source, selector));
1836         }
1837
1838         public static double? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
1839             return Enumerable.Max(Enumerable.Select(source, selector));
1840         }
1841
1842         public static decimal Max<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
1843             return Enumerable.Max(Enumerable.Select(source, selector));
1844         }
1845
1846         public static decimal? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
1847             return Enumerable.Max(Enumerable.Select(source, selector));
1848         }
1849
1850         public static TResult Max<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector) {
1851             return Enumerable.Max(Enumerable.Select(source, selector));
1852         }
1853
1854         public static double Average(this IEnumerable<int> source) {
1855             if (source == null) throw Error.ArgumentNull("source");
1856             long sum = 0;
1857             long count = 0;
1858             checked {
1859                 foreach (int v in source) {
1860                     sum += v;
1861                     count++;
1862                 }
1863             }
1864             if (count > 0) return (double)sum / count;
1865             throw Error.NoElements();
1866         }
1867
1868         public static double? Average(this IEnumerable<int?> source) {
1869             if (source == null) throw Error.ArgumentNull("source");
1870             long sum = 0;
1871             long count = 0;
1872             checked {
1873                 foreach (int? v in source) {
1874                     if (v != null) {
1875                         sum += v.GetValueOrDefault();
1876                         count++;
1877                     }
1878                 }
1879             }
1880             if (count > 0) return (double)sum / count;
1881             return null;
1882         }
1883
1884         public static double Average(this IEnumerable<long> source) {
1885             if (source == null) throw Error.ArgumentNull("source");
1886             long sum = 0;
1887             long count = 0;
1888             checked {
1889                 foreach (long v in source) {
1890                     sum += v;
1891                     count++;
1892                 }
1893             }
1894             if (count > 0) return (double)sum / count;
1895             throw Error.NoElements();
1896         }
1897
1898         public static double? Average(this IEnumerable<long?> source) {
1899             if (source == null) throw Error.ArgumentNull("source");
1900             long sum = 0;
1901             long count = 0;
1902             checked {
1903                 foreach (long? v in source) {
1904                     if (v != null) {
1905                         sum += v.GetValueOrDefault();
1906                         count++;
1907                     }
1908                 }
1909             }
1910             if (count > 0) return (double)sum / count;
1911             return null;
1912         }
1913
1914         public static float Average(this IEnumerable<float> source) {
1915             if (source == null) throw Error.ArgumentNull("source");
1916             double sum = 0;
1917             long count = 0;
1918             checked {
1919                 foreach (float v in source) {
1920                     sum += v;
1921                     count++;
1922                 }
1923             }
1924             if (count > 0) return (float)(sum / count);
1925             throw Error.NoElements();
1926         }
1927
1928         public static float? Average(this IEnumerable<float?> source) {
1929             if (source == null) throw Error.ArgumentNull("source");
1930             double sum = 0;
1931             long count = 0;
1932             checked {
1933                 foreach (float? v in source) {
1934                     if (v != null) {
1935                         sum += v.GetValueOrDefault();
1936                         count++;
1937                     }
1938                 }
1939             }
1940             if (count > 0) return (float)(sum / count);
1941             return null;
1942         }
1943
1944         public static double Average(this IEnumerable<double> source) {
1945             if (source == null) throw Error.ArgumentNull("source");
1946             double sum = 0;
1947             long count = 0;
1948             checked {
1949                 foreach (double v in source) {
1950                     sum += v;
1951                     count++;
1952                 }
1953             }
1954             if (count > 0) return sum / count;
1955             throw Error.NoElements();
1956         }
1957
1958         public static double? Average(this IEnumerable<double?> source) {
1959             if (source == null) throw Error.ArgumentNull("source");
1960             double sum = 0;
1961             long count = 0;
1962             checked {
1963                 foreach (double? v in source) {
1964                     if (v != null) {
1965                         sum += v.GetValueOrDefault();
1966                         count++;
1967                     }
1968                 }
1969             }
1970             if (count > 0) return sum / count;
1971             return null;
1972         }
1973
1974         public static decimal Average(this IEnumerable<decimal> source) {
1975             if (source == null) throw Error.ArgumentNull("source");
1976             decimal sum = 0;
1977             long count = 0;
1978             checked {
1979                 foreach (decimal v in source) {
1980                     sum += v;
1981                     count++;
1982                 }
1983             }
1984             if (count > 0) return sum / count;
1985             throw Error.NoElements();
1986         }
1987
1988         public static decimal? Average(this IEnumerable<decimal?> source) {
1989             if (source == null) throw Error.ArgumentNull("source");
1990             decimal sum = 0;
1991             long count = 0;
1992             checked {
1993                 foreach (decimal? v in source) {
1994                     if (v != null) {
1995                         sum += v.GetValueOrDefault();
1996                         count++;
1997                     }
1998                 }
1999             }
2000             if (count > 0) return sum / count;
2001             return null;
2002         }
2003
2004         public static double Average<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
2005             return Enumerable.Average(Enumerable.Select(source, selector));
2006         }
2007
2008         public static double? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
2009             return Enumerable.Average(Enumerable.Select(source, selector));
2010         }
2011
2012         public static double Average<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
2013             return Enumerable.Average(Enumerable.Select(source, selector));
2014         }
2015
2016         public static double? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
2017             return Enumerable.Average(Enumerable.Select(source, selector));
2018         }
2019
2020         public static float Average<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
2021             return Enumerable.Average(Enumerable.Select(source, selector));
2022         }
2023
2024         public static float? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
2025             return Enumerable.Average(Enumerable.Select(source, selector));
2026         }
2027
2028         public static double Average<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
2029             return Enumerable.Average(Enumerable.Select(source, selector));
2030         }
2031
2032         public static double? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
2033             return Enumerable.Average(Enumerable.Select(source, selector));
2034         }
2035
2036         public static decimal Average<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
2037             return Enumerable.Average(Enumerable.Select(source, selector));
2038         }
2039
2040         public static decimal? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
2041             return Enumerable.Average(Enumerable.Select(source, selector));
2042         }
2043     }
2044
2045
2046     //
2047     // We have added some optimization in SZArrayHelper class to cache the enumerator of zero length arrays so
2048     // the enumerator will be created once per type.
2049     //
2050     internal class EmptyEnumerable<TElement>
2051     {
2052         public static readonly TElement[] Instance = new TElement[0];
2053     }
2054
2055     internal class IdentityFunction<TElement>
2056     {
2057         public static Func<TElement, TElement> Instance {
2058             get { return x => x; }
2059         }
2060     }
2061
2062     public interface IOrderedEnumerable<TElement> : IEnumerable<TElement>
2063     {
2064         IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending);
2065     }
2066
2067 #if SILVERLIGHT && !FEATURE_NETCORE
2068     public interface IGrouping<TKey, TElement> : IEnumerable<TElement>
2069 #else
2070     public interface IGrouping<out TKey, out TElement> : IEnumerable<TElement>
2071 #endif
2072     {
2073         TKey Key { get; }
2074     }
2075
2076     public interface ILookup<TKey, TElement> : IEnumerable<IGrouping<TKey, TElement>>{
2077         int Count { get; }
2078         IEnumerable<TElement> this[TKey key] { get; }
2079         bool Contains(TKey key);
2080     }
2081
2082     public class Lookup<TKey, TElement> : IEnumerable<IGrouping<TKey, TElement>>, ILookup<TKey, TElement>{
2083         IEqualityComparer<TKey> comparer;
2084         Grouping[] groupings;
2085         Grouping lastGrouping;
2086         int count;
2087
2088         internal static Lookup<TKey, TElement> Create<TSource>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
2089             if (source == null) throw Error.ArgumentNull("source");
2090             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2091             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
2092             Lookup<TKey, TElement> lookup = new Lookup<TKey, TElement>(comparer);
2093             foreach (TSource item in source) {
2094                 lookup.GetGrouping(keySelector(item), true).Add(elementSelector(item));
2095             }
2096             return lookup;
2097         }
2098
2099         internal static Lookup<TKey, TElement> CreateForJoin(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IEqualityComparer<TKey> comparer) {
2100             Lookup<TKey, TElement> lookup = new Lookup<TKey, TElement>(comparer);
2101             foreach (TElement item in source) {
2102                 TKey key = keySelector(item);
2103                 if (key != null) lookup.GetGrouping(key, true).Add(item);
2104             }
2105             return lookup;
2106         }
2107
2108         Lookup(IEqualityComparer<TKey> comparer) {
2109             if (comparer == null) comparer = EqualityComparer<TKey>.Default;
2110             this.comparer = comparer;
2111             groupings = new Grouping[7];
2112         }
2113
2114         public int Count {
2115             get { return count; }
2116         }
2117
2118         public IEnumerable<TElement> this[TKey key] {
2119             get {
2120                 Grouping grouping = GetGrouping(key, false);
2121                 if (grouping != null) return grouping;
2122                 return EmptyEnumerable<TElement>.Instance;
2123             }
2124         }
2125
2126         public bool Contains(TKey key) {
2127             return GetGrouping(key, false) != null;
2128         }
2129
2130         public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator() {
2131             Grouping g = lastGrouping;
2132             if (g != null) {
2133                 do {
2134                     g = g.next;
2135                     yield return g;
2136                 } while (g != lastGrouping);
2137             }
2138         }
2139
2140         public IEnumerable<TResult> ApplyResultSelector<TResult>(Func<TKey, IEnumerable<TElement>, TResult> resultSelector){
2141             Grouping g = lastGrouping;
2142             if (g != null) {
2143                 do {
2144                     g = g.next;
2145                     if (g.count != g.elements.Length) { Array.Resize<TElement>(ref g.elements, g.count); }
2146                     yield return resultSelector(g.key, g.elements);
2147                 }while (g != lastGrouping);
2148             }
2149         }
2150
2151         IEnumerator IEnumerable.GetEnumerator() {
2152             return GetEnumerator();
2153         }
2154
2155         internal int InternalGetHashCode(TKey key)
2156         {
2157             //[....] DevDivBugs 171937. work around comparer implementations that throw when passed null
2158             return (key == null) ? 0 : comparer.GetHashCode(key) & 0x7FFFFFFF;
2159         }
2160
2161         internal Grouping GetGrouping(TKey key, bool create) {
2162             int hashCode = InternalGetHashCode(key);
2163             for (Grouping g = groupings[hashCode % groupings.Length]; g != null; g = g.hashNext)
2164                 if (g.hashCode == hashCode && comparer.Equals(g.key, key)) return g;
2165             if (create) {
2166                 if (count == groupings.Length) Resize();
2167                 int index = hashCode % groupings.Length;
2168                 Grouping g = new Grouping();
2169                 g.key = key;
2170                 g.hashCode = hashCode;
2171                 g.elements = new TElement[1];
2172                 g.hashNext = groupings[index];
2173                 groupings[index] = g;
2174                 if (lastGrouping == null) {
2175                     g.next = g;
2176                 }
2177                 else {
2178                     g.next = lastGrouping.next;
2179                     lastGrouping.next = g;
2180                 }
2181                 lastGrouping = g;
2182                 count++;
2183                 return g;
2184             }
2185             return null;
2186         }
2187
2188         void Resize() {
2189             int newSize = checked(count * 2 + 1);
2190             Grouping[] newGroupings = new Grouping[newSize];
2191             Grouping g = lastGrouping;
2192             do {
2193                 g = g.next;
2194                 int index = g.hashCode % newSize;
2195                 g.hashNext = newGroupings[index];
2196                 newGroupings[index] = g;
2197             } while (g != lastGrouping);
2198             groupings = newGroupings;
2199         }
2200
2201         internal class Grouping : IGrouping<TKey, TElement>, IList<TElement>
2202         {
2203             internal TKey key;
2204             internal int hashCode;
2205             internal TElement[] elements;
2206             internal int count;
2207             internal Grouping hashNext;
2208             internal Grouping next;
2209
2210             internal void Add(TElement element) {
2211                 if (elements.Length == count) Array.Resize(ref elements, checked(count * 2));
2212                 elements[count] = element;
2213                 count++;
2214             }
2215
2216             public IEnumerator<TElement> GetEnumerator() {
2217                 for (int i = 0; i < count; i++) yield return elements[i];
2218             }
2219
2220             IEnumerator IEnumerable.GetEnumerator() {
2221                 return GetEnumerator();
2222             }
2223
2224             // DDB195907: implement IGrouping<>.Key implicitly
2225             // so that WPF binding works on this property.
2226             public TKey Key {
2227                 get { return key; }
2228             }
2229
2230             int ICollection<TElement>.Count {
2231                 get { return count; }
2232             }
2233
2234             bool ICollection<TElement>.IsReadOnly {
2235                 get { return true; }
2236             }
2237
2238             void ICollection<TElement>.Add(TElement item) {
2239                 throw Error.NotSupported();
2240             }
2241
2242             void ICollection<TElement>.Clear() {
2243                 throw Error.NotSupported();
2244             }
2245
2246             bool ICollection<TElement>.Contains(TElement item) {
2247                 return Array.IndexOf(elements, item, 0, count) >= 0;
2248             }
2249
2250             void ICollection<TElement>.CopyTo(TElement[] array, int arrayIndex) {
2251                 Array.Copy(elements, 0, array, arrayIndex, count);
2252             }
2253
2254             bool ICollection<TElement>.Remove(TElement item) {
2255                 throw Error.NotSupported();
2256             }
2257
2258             int IList<TElement>.IndexOf(TElement item) {
2259                 return Array.IndexOf(elements, item, 0, count);
2260             }
2261
2262             void IList<TElement>.Insert(int index, TElement item) {
2263                 throw Error.NotSupported();
2264             }
2265
2266             void IList<TElement>.RemoveAt(int index) {
2267                 throw Error.NotSupported();
2268             }
2269
2270             TElement IList<TElement>.this[int index] {
2271                 get {
2272                     if (index < 0 || index >= count) throw Error.ArgumentOutOfRange("index");
2273                     return elements[index];
2274                 }
2275                 set {
2276                     throw Error.NotSupported();
2277                 }
2278             }
2279         }
2280     }
2281
2282     // @
2283     internal class Set<TElement>
2284     {
2285         int[] buckets;
2286         Slot[] slots;
2287         int count;
2288         int freeList;
2289         IEqualityComparer<TElement> comparer;
2290
2291         public Set() : this(null) { }
2292
2293         public Set(IEqualityComparer<TElement> comparer) {
2294             if (comparer == null) comparer = EqualityComparer<TElement>.Default;
2295             this.comparer = comparer;
2296             buckets = new int[7];
2297             slots = new Slot[7];
2298             freeList = -1;
2299         }
2300
2301         // If value is not in set, add it and return true; otherwise return false
2302         public bool Add(TElement value) {
2303             return !Find(value, true);
2304         }
2305
2306         // Check whether value is in set
2307         public bool Contains(TElement value) {
2308             return Find(value, false);
2309         }
2310
2311         // If value is in set, remove it and return true; otherwise return false
2312         public bool Remove(TElement value) {
2313             int hashCode = InternalGetHashCode(value);
2314             int bucket = hashCode % buckets.Length;
2315             int last = -1;
2316             for (int i = buckets[bucket] - 1; i >= 0; last = i, i = slots[i].next) {
2317                 if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) {
2318                     if (last < 0) {
2319                         buckets[bucket] = slots[i].next + 1;
2320                     }
2321                     else {
2322                         slots[last].next = slots[i].next;
2323                     }
2324                     slots[i].hashCode = -1;
2325                     slots[i].value = default(TElement);
2326                     slots[i].next = freeList;
2327                     freeList = i;
2328                     return true;
2329                 }
2330             }
2331             return false;
2332         }
2333
2334         bool Find(TElement value, bool add) {
2335             int hashCode = InternalGetHashCode(value);
2336             for (int i = buckets[hashCode % buckets.Length] - 1; i >= 0; i = slots[i].next) {
2337                 if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) return true;
2338             }
2339             if (add) {
2340                 int index;
2341                 if (freeList >= 0) {
2342                     index = freeList;
2343                     freeList = slots[index].next;
2344                 }
2345                 else {
2346                     if (count == slots.Length) Resize();
2347                     index = count;
2348                     count++;
2349                 }
2350                 int bucket = hashCode % buckets.Length;
2351                 slots[index].hashCode = hashCode;
2352                 slots[index].value = value;
2353                 slots[index].next = buckets[bucket] - 1;
2354                 buckets[bucket] = index + 1;
2355             }
2356             return false;
2357         }
2358
2359         void Resize() {
2360             int newSize = checked(count * 2 + 1);
2361             int[] newBuckets = new int[newSize];
2362             Slot[] newSlots = new Slot[newSize];
2363             Array.Copy(slots, 0, newSlots, 0, count);
2364             for (int i = 0; i < count; i++) {
2365                 int bucket = newSlots[i].hashCode % newSize;
2366                 newSlots[i].next = newBuckets[bucket] - 1;
2367                 newBuckets[bucket] = i + 1;
2368             }
2369             buckets = newBuckets;
2370             slots = newSlots;
2371         }
2372
2373         internal int InternalGetHashCode(TElement value)
2374         {
2375             //[....] DevDivBugs 171937. work around comparer implementations that throw when passed null
2376             return (value == null) ? 0 : comparer.GetHashCode(value) & 0x7FFFFFFF;
2377         }
2378
2379         internal struct Slot
2380         {
2381             internal int hashCode;
2382             internal TElement value;
2383             internal int next;
2384         }
2385     }
2386
2387     internal class GroupedEnumerable<TSource, TKey, TElement, TResult> : IEnumerable<TResult>{
2388         IEnumerable<TSource> source;
2389         Func<TSource, TKey> keySelector;
2390         Func<TSource, TElement> elementSelector;
2391         IEqualityComparer<TKey> comparer;
2392         Func<TKey, IEnumerable<TElement>, TResult> resultSelector;
2393
2394         public GroupedEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, Func<TKey, IEnumerable<TElement>, TResult> resultSelector, IEqualityComparer<TKey> comparer){
2395             if (source == null) throw Error.ArgumentNull("source");
2396             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2397             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
2398             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
2399             this.source = source;
2400             this.keySelector = keySelector;
2401             this.elementSelector = elementSelector;
2402             this.comparer = comparer;
2403             this.resultSelector = resultSelector;
2404         }
2405
2406         public IEnumerator<TResult> GetEnumerator(){
2407             Lookup<TKey, TElement> lookup = Lookup<TKey, TElement>.Create<TSource>(source, keySelector, elementSelector, comparer);
2408             return lookup.ApplyResultSelector(resultSelector).GetEnumerator();
2409         }
2410
2411         IEnumerator IEnumerable.GetEnumerator(){
2412             return GetEnumerator();
2413         }
2414     }
2415
2416     internal class GroupedEnumerable<TSource, TKey, TElement> : IEnumerable<IGrouping<TKey, TElement>>
2417     {
2418         IEnumerable<TSource> source;
2419         Func<TSource, TKey> keySelector;
2420         Func<TSource, TElement> elementSelector;
2421         IEqualityComparer<TKey> comparer;
2422
2423         public GroupedEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
2424             if (source == null) throw Error.ArgumentNull("source");
2425             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2426             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
2427             this.source = source;
2428             this.keySelector = keySelector;
2429             this.elementSelector = elementSelector;
2430             this.comparer = comparer;
2431         }
2432
2433         public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator() {
2434             return Lookup<TKey, TElement>.Create<TSource>(source, keySelector, elementSelector, comparer).GetEnumerator();
2435         }
2436
2437         IEnumerator IEnumerable.GetEnumerator() {
2438             return GetEnumerator();
2439         }
2440     }
2441
2442     internal abstract class OrderedEnumerable<TElement> : IOrderedEnumerable<TElement>
2443     {
2444         internal IEnumerable<TElement> source;
2445
2446         public IEnumerator<TElement> GetEnumerator() {
2447             Buffer<TElement> buffer = new Buffer<TElement>(source);
2448             if (buffer.count > 0) {
2449                 EnumerableSorter<TElement> sorter = GetEnumerableSorter(null);
2450                 int[] map = sorter.Sort(buffer.items, buffer.count);
2451                 sorter = null;
2452                 for (int i = 0; i < buffer.count; i++) yield return buffer.items[map[i]];
2453             }
2454         }
2455
2456         internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next);
2457
2458         IEnumerator IEnumerable.GetEnumerator() {
2459             return GetEnumerator();
2460         }
2461
2462         IOrderedEnumerable<TElement> IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending) {
2463             OrderedEnumerable<TElement, TKey> result = new OrderedEnumerable<TElement, TKey>(source, keySelector, comparer, descending);
2464             result.parent = this;
2465             return result;
2466         }
2467     }
2468
2469     internal class OrderedEnumerable<TElement, TKey> : OrderedEnumerable<TElement>
2470     {
2471         internal OrderedEnumerable<TElement> parent;
2472         internal Func<TElement, TKey> keySelector;
2473         internal IComparer<TKey> comparer;
2474         internal bool descending;
2475
2476         internal OrderedEnumerable(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending) {
2477             if (source == null) throw Error.ArgumentNull("source");
2478             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2479             this.source = source;
2480             this.parent = null;
2481             this.keySelector = keySelector;
2482             this.comparer = comparer != null ? comparer : Comparer<TKey>.Default;
2483             this.descending = descending;
2484         }
2485
2486         internal override EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next) {
2487             EnumerableSorter<TElement> sorter = new EnumerableSorter<TElement, TKey>(keySelector, comparer, descending, next);
2488             if (parent != null) sorter = parent.GetEnumerableSorter(sorter);
2489             return sorter;
2490         }
2491     }
2492
2493     internal abstract class EnumerableSorter<TElement>
2494     {
2495         internal abstract void ComputeKeys(TElement[] elements, int count);
2496
2497         internal abstract int CompareKeys(int index1, int index2);
2498
2499         internal int[] Sort(TElement[] elements, int count) {
2500             ComputeKeys(elements, count);
2501             int[] map = new int[count];
2502             for (int i = 0; i < count; i++) map[i] = i;
2503             QuickSort(map, 0, count - 1);
2504             return map;
2505         }
2506
2507         void QuickSort(int[] map, int left, int right) {
2508             do {
2509                 int i = left;
2510                 int j = right;
2511                 int x = map[i + ((j - i) >> 1)];
2512                 do {
2513                     while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
2514                     while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
2515                     if (i > j) break;
2516                     if (i < j) {
2517                         int temp = map[i];
2518                         map[i] = map[j];
2519                         map[j] = temp;
2520                     }
2521                     i++;
2522                     j--;
2523                 } while (i <= j);
2524                 if (j - left <= right - i) {
2525                     if (left < j) QuickSort(map, left, j);
2526                     left = i;
2527                 }
2528                 else {
2529                     if (i < right) QuickSort(map, i, right);
2530                     right = j;
2531                 }
2532             } while (left < right);
2533         }
2534     }
2535
2536     internal class EnumerableSorter<TElement, TKey> : EnumerableSorter<TElement>
2537     {
2538         internal Func<TElement, TKey> keySelector;
2539         internal IComparer<TKey> comparer;
2540         internal bool descending;
2541         internal EnumerableSorter<TElement> next;
2542         internal TKey[] keys;
2543
2544         internal EnumerableSorter(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TElement> next) {
2545             this.keySelector = keySelector;
2546             this.comparer = comparer;
2547             this.descending = descending;
2548             this.next = next;
2549         }
2550
2551         internal override void ComputeKeys(TElement[] elements, int count) {
2552             keys = new TKey[count];
2553             for (int i = 0; i < count; i++) keys[i] = keySelector(elements[i]);
2554             if (next != null) next.ComputeKeys(elements, count);
2555         }
2556
2557         internal override int CompareKeys(int index1, int index2) {
2558             int c = comparer.Compare(keys[index1], keys[index2]);
2559             if (c == 0) {
2560                 if (next == null) return index1 - index2;
2561                 return next.CompareKeys(index1, index2);
2562             }
2563             return descending ? -c : c;
2564         }
2565     }
2566
2567     struct Buffer<TElement>
2568     {
2569         internal TElement[] items;
2570         internal int count;
2571
2572         internal Buffer(IEnumerable<TElement> source) {
2573             TElement[] items = null;
2574             int count = 0;
2575             ICollection<TElement> collection = source as ICollection<TElement>;
2576             if (collection != null) {
2577                 count = collection.Count;
2578                 if (count > 0) {
2579                     items = new TElement[count];
2580                     collection.CopyTo(items, 0);
2581                 }
2582             }
2583             else {
2584                 foreach (TElement item in source) {
2585                     if (items == null) {
2586                         items = new TElement[4];
2587                     }
2588                     else if (items.Length == count) {
2589                         TElement[] newItems = new TElement[checked(count * 2)];
2590                         Array.Copy(items, 0, newItems, 0, count);
2591                         items = newItems;
2592                     }
2593                     items[count] = item;
2594                     count++;
2595                 }
2596             }
2597             this.items = items;
2598             this.count = count;
2599         }
2600
2601         internal TElement[] ToArray() {
2602             if (count == 0) return new TElement[0];
2603             if (items.Length == count) return items;
2604             TElement[] result = new TElement[count];
2605             Array.Copy(items, 0, result, 0, count);
2606             return result;
2607         }
2608     }
2609
2610     /// <summary>
2611     /// This class provides the items view for the Enumerable
2612     /// </summary>
2613     /// <typeparam name="T"></typeparam>
2614     internal sealed class SystemCore_EnumerableDebugView<T>
2615     {
2616         public SystemCore_EnumerableDebugView(IEnumerable<T> enumerable)
2617         {
2618             if (enumerable == null)
2619             {
2620                 throw new ArgumentNullException("enumerable");
2621             }
2622
2623             this.enumerable = enumerable;
2624         }
2625
2626         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.RootHidden)]
2627         public T[] Items
2628         {
2629             get
2630             {
2631                 List<T> tempList = new List<T>();
2632                 IEnumerator<T> currentEnumerator = this.enumerable.GetEnumerator();
2633
2634                 if (currentEnumerator != null)
2635                 {
2636                     for(count = 0; currentEnumerator.MoveNext(); count++)
2637                     {
2638                         tempList.Add(currentEnumerator.Current);
2639                     }
2640                 }
2641                 if (count == 0)
2642                 {
2643                     throw new SystemCore_EnumerableDebugViewEmptyException();
2644                 }
2645                 cachedCollection = new T[this.count];
2646                 tempList.CopyTo(cachedCollection, 0);
2647                 return cachedCollection;
2648             }
2649         }
2650
2651         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2652         private IEnumerable<T> enumerable;
2653
2654         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2655         private T[] cachedCollection;
2656
2657         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2658         private int count;
2659     }
2660
2661     internal sealed class SystemCore_EnumerableDebugViewEmptyException : Exception
2662     {
2663         public string Empty
2664         {
2665             get
2666             {
2667                 return Strings.EmptyEnumerable;
2668             }
2669         }
2670     }
2671
2672     internal sealed class SystemCore_EnumerableDebugView
2673     {
2674         public SystemCore_EnumerableDebugView(IEnumerable enumerable)
2675         {
2676             if (enumerable == null)
2677             {
2678                 throw new ArgumentNullException("enumerable");
2679             }
2680
2681             this.enumerable = enumerable;
2682             count = 0;
2683             cachedCollection = null;
2684         }
2685
2686         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.RootHidden)]
2687         public object[] Items
2688         {
2689             get
2690             {
2691                 List<object> tempList = new List<object>();
2692                 IEnumerator currentEnumerator = this.enumerable.GetEnumerator();
2693
2694                 if (currentEnumerator != null)
2695                 {
2696                     for (count = 0; currentEnumerator.MoveNext(); count++)
2697                     {
2698                         tempList.Add(currentEnumerator.Current);
2699                     }
2700                 }
2701                 if (count == 0)
2702                 {
2703                     throw new SystemCore_EnumerableDebugViewEmptyException();
2704                 }
2705                 cachedCollection = new object[this.count];
2706                 tempList.CopyTo(cachedCollection, 0);
2707                 return cachedCollection;
2708             }
2709         }
2710
2711         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2712         private IEnumerable enumerable;
2713
2714         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2715         private object[] cachedCollection;
2716
2717         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2718         private int count;
2719     }
2720 }