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         public static IEnumerable<TSource> Append<TSource>(this IEnumerable<TSource> source, TSource element)
 698         {
 699             if (source == null) throw Error.ArgumentNull("source");
 700             return AppendIterator<TSource>(source, element);
 701         }
 702
 703         private static IEnumerable<TSource> AppendIterator<TSource>(IEnumerable<TSource> source, TSource element)
 704         {
 705             foreach (TSource e1 in source) yield return e1;
 706             yield return element;
 707         }
 708
 709         public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource element)
 710         {
 711             if (source == null) throw Error.ArgumentNull("source");
 712             return PrependIterator<TSource>(source, element);
 713         }
 714
 715         private static IEnumerable<TSource> PrependIterator<TSource>(IEnumerable<TSource> source, TSource element)
 716         {
 717             yield return element;
 718             foreach (TSource e1 in source) yield return e1;
 719         }
 720
 721         public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector) {
 722             if (first == null) throw Error.ArgumentNull("first");
 723             if (second == null) throw Error.ArgumentNull("second");
 724             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
 725             return ZipIterator(first, second, resultSelector);
 726         }
 727
 728         static IEnumerable<TResult> ZipIterator<TFirst, TSecond, TResult>(IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector) {
 729             using (IEnumerator<TFirst> e1 = first.GetEnumerator())
 730                 using (IEnumerator<TSecond> e2 = second.GetEnumerator())
 731                     while (e1.MoveNext() && e2.MoveNext())
 732                         yield return resultSelector(e1.Current, e2.Current);
 733         }
 734
 735
 736         public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source) {
 737             if (source == null) throw Error.ArgumentNull("source");
 738             return DistinctIterator<TSource>(source, null);
 739         }
 740
 741         public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer) {
 742             if (source == null) throw Error.ArgumentNull("source");
 743             return DistinctIterator<TSource>(source, comparer);
 744         }
 745
 746         static IEnumerable<TSource> DistinctIterator<TSource>(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer) {
 747             Set<TSource> set = new Set<TSource>(comparer);
 748             foreach (TSource element in source)
 749                 if (set.Add(element)) yield return element;
 750         }
 751
 752         public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
 753             if (first == null) throw Error.ArgumentNull("first");
 754             if (second == null) throw Error.ArgumentNull("second");
 755             return UnionIterator<TSource>(first, second, null);
 756         }
 757
 758         public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 759         {
 760             if (first == null) throw Error.ArgumentNull("first");
 761             if (second == null) throw Error.ArgumentNull("second");
 762             return UnionIterator<TSource>(first, second, comparer);
 763         }
 764
 765         static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 766         {
 767             Set<TSource> set = new Set<TSource>(comparer);
 768             foreach (TSource element in first)
 769                 if (set.Add(element)) yield return element;
 770             foreach (TSource element in second)
 771                 if (set.Add(element)) yield return element;
 772         }
 773
 774         public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
 775             if (first == null) throw Error.ArgumentNull("first");
 776             if (second == null) throw Error.ArgumentNull("second");
 777             return IntersectIterator<TSource>(first, second, null);
 778         }
 779
 780         public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 781         {
 782             if (first == null) throw Error.ArgumentNull("first");
 783             if (second == null) throw Error.ArgumentNull("second");
 784             return IntersectIterator<TSource>(first, second, comparer);
 785         }
 786
 787         static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 788         {
 789             Set<TSource> set = new Set<TSource>(comparer);
 790             foreach (TSource element in second) set.Add(element);
 791             foreach (TSource element in first)
 792                 if (set.Remove(element)) yield return element;
 793         }
 794
 795         public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
 796         {
 797             if (first == null) throw Error.ArgumentNull("first");
 798             if (second == null) throw Error.ArgumentNull("second");
 799             return ExceptIterator<TSource>(first, second, null);
 800         }
 801
 802         public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 803         {
 804             if (first == null) throw Error.ArgumentNull("first");
 805             if (second == null) throw Error.ArgumentNull("second");
 806             return ExceptIterator<TSource>(first, second, comparer);
 807         }
 808
 809         static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) {
 810             Set<TSource> set = new Set<TSource>(comparer);
 811             foreach (TSource element in second) set.Add(element);
 812             foreach (TSource element in first)
 813                 if (set.Add(element)) yield return element;
 814         }
 815
 816         public static IEnumerable<TSource> Reverse<TSource>(this IEnumerable<TSource> source) {
 817             if (source == null) throw Error.ArgumentNull("source");
 818             return ReverseIterator<TSource>(source);
 819         }
 820
 821         static IEnumerable<TSource> ReverseIterator<TSource>(IEnumerable<TSource> source) {
 822             Buffer<TSource> buffer = new Buffer<TSource>(source);
 823             for (int i = buffer.count - 1; i >= 0; i--) yield return buffer.items[i];
 824         }
 825
 826         public static bool SequenceEqual<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
 827             return SequenceEqual<TSource>(first, second, null);
 828         }
 829
 830         public static bool SequenceEqual<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
 831         {
 832             if (comparer == null) comparer = EqualityComparer<TSource>.Default;
 833             if (first == null) throw Error.ArgumentNull("first");
 834             if (second == null) throw Error.ArgumentNull("second");
 835             using (IEnumerator<TSource> e1 = first.GetEnumerator())
 836             using (IEnumerator<TSource> e2 = second.GetEnumerator())
 837             {
 838                 while (e1.MoveNext())
 839                 {
 840                     if (!(e2.MoveNext() && comparer.Equals(e1.Current, e2.Current))) return false;
 841                 }
 842                 if (e2.MoveNext()) return false;
 843             }
 844             return true;
 845         }
 846
 847         public static IEnumerable<TSource> AsEnumerable<TSource>(this IEnumerable<TSource> source)
 848         {
 849             return source;
 850         }
 851
 852         public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source) {
 853             if (source == null) throw Error.ArgumentNull("source");
 854             return new Buffer<TSource>(source).ToArray();
 855         }
 856
 857         public static List<TSource> ToList<TSource>(this IEnumerable<TSource> source) {
 858             if (source == null) throw Error.ArgumentNull("source");
 859             return new List<TSource>(source);
 860         }
 861
 862         public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 863             return ToDictionary<TSource, TKey, TSource>(source, keySelector, IdentityFunction<TSource>.Instance, null);
 864         }
 865
 866         public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer) {
 867             return ToDictionary<TSource, TKey, TSource>(source, keySelector, IdentityFunction<TSource>.Instance, comparer);
 868         }
 869
 870         public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector) {
 871             return ToDictionary<TSource, TKey, TElement>(source, keySelector, elementSelector, null);
 872         }
 873
 874         public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
 875             if (source == null) throw Error.ArgumentNull("source");
 876             if (keySelector == null) throw Error.ArgumentNull("keySelector");
 877             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
 878             Dictionary<TKey, TElement> d = new Dictionary<TKey, TElement>(comparer);
 879             foreach (TSource element in source) d.Add(keySelector(element), elementSelector(element));
 880             return d;
 881         }
 882
 883         public static ILookup<TKey, TSource> ToLookup<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
 884             return Lookup<TKey, TSource>.Create(source, keySelector, IdentityFunction<TSource>.Instance, null);
 885         }
 886
 887         public static ILookup<TKey, TSource> ToLookup<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer) {
 888             return Lookup<TKey, TSource>.Create(source, keySelector, IdentityFunction<TSource>.Instance, comparer);
 889         }
 890
 891         public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector) {
 892             return Lookup<TKey, TElement>.Create(source, keySelector, elementSelector, null);
 893         }
 894
 895         public static ILookup<TKey, TElement> ToLookup<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
 896             return Lookup<TKey, TElement>.Create(source, keySelector, elementSelector, comparer);
 897         }
 898
 899         public static IEnumerable<TSource> DefaultIfEmpty<TSource>(this IEnumerable<TSource> source) {
 900             return DefaultIfEmpty(source, default(TSource));
 901         }
 902
 903         public static IEnumerable<TSource> DefaultIfEmpty<TSource>(this IEnumerable<TSource> source, TSource defaultValue) {
 904             if (source == null) throw Error.ArgumentNull("source");
 905             return DefaultIfEmptyIterator<TSource>(source, defaultValue);
 906         }
 907
 908         static IEnumerable<TSource> DefaultIfEmptyIterator<TSource>(IEnumerable<TSource> source, TSource defaultValue) {
 909             using (IEnumerator<TSource> e = source.GetEnumerator()) {
 910                 if (e.MoveNext()) {
 911                     do {
 912                         yield return e.Current;
 913                     } while (e.MoveNext());
 914                 }
 915                 else {
 916                     yield return defaultValue;
 917                 }
 918             }
 919         }
 920
 921         public static IEnumerable<TResult> OfType<TResult>(this IEnumerable source) {
 922             if (source == null) throw Error.ArgumentNull("source");
 923             return OfTypeIterator<TResult>(source);
 924         }
 925
 926         static IEnumerable<TResult> OfTypeIterator<TResult>(IEnumerable source) {
 927             foreach (object obj in source) {
 928                 if (obj is TResult) yield return (TResult)obj;
 929             }
 930         }
 931
 932         public static IEnumerable<TResult> Cast<TResult>(this IEnumerable source) {
 933             IEnumerable<TResult> typedSource = source as IEnumerable<TResult>;
 934             if (typedSource != null) return typedSource;
 935             if (source == null) throw Error.ArgumentNull("source");
 936             return CastIterator<TResult>(source);
 937         }
 938
 939         static IEnumerable<TResult> CastIterator<TResult>(IEnumerable source) {
 940             foreach (object obj in source) yield return (TResult)obj;
 941         }
 942
 943         public static TSource First<TSource>(this IEnumerable<TSource> source) {
 944             if (source == null) throw Error.ArgumentNull("source");
 945             IList<TSource> list = source as IList<TSource>;
 946             if (list != null) {
 947                 if (list.Count > 0) return list[0];
 948             }
 949             else {
 950                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
 951                     if (e.MoveNext()) return e.Current;
 952                 }
 953             }
 954             throw Error.NoElements();
 955         }
 956
 957         public static TSource First<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 958             if (source == null) throw Error.ArgumentNull("source");
 959             if (predicate == null) throw Error.ArgumentNull("predicate");
 960             foreach (TSource element in source) {
 961                 if (predicate(element)) return element;
 962             }
 963             throw Error.NoMatch();
 964         }
 965
 966         public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source) {
 967             if (source == null) throw Error.ArgumentNull("source");
 968             IList<TSource> list = source as IList<TSource>;
 969             if (list != null) {
 970                 if (list.Count > 0) return list[0];
 971             }
 972             else {
 973                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
 974                     if (e.MoveNext()) return e.Current;
 975                 }
 976             }
 977             return default(TSource);
 978         }
 979
 980         public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
 981             if (source == null) throw Error.ArgumentNull("source");
 982             if (predicate == null) throw Error.ArgumentNull("predicate");
 983             foreach (TSource element in source) {
 984                 if (predicate(element)) return element;
 985             }
 986             return default(TSource);
 987         }
 988
 989         public static TSource Last<TSource>(this IEnumerable<TSource> source) {
 990             if (source == null) throw Error.ArgumentNull("source");
 991             IList<TSource> list = source as IList<TSource>;
 992             if (list != null) {
 993                 int count = list.Count;
 994                 if (count > 0) return list[count - 1];
 995             }
 996             else {
 997                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
 998                     if (e.MoveNext()) {
 999                         TSource result;
1000                         do {
1001                             result = e.Current;
1002                         } while (e.MoveNext());
1003                         return result;
1004                     }
1005                 }
1006             }
1007             throw Error.NoElements();
1008         }
1009
1010         public static TSource Last<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1011             if (source == null) throw Error.ArgumentNull("source");
1012             if (predicate == null) throw Error.ArgumentNull("predicate");
1013             TSource result = default(TSource);
1014             bool found = false;
1015             foreach (TSource element in source) {
1016                 if (predicate(element)) {
1017                     result = element;
1018                     found = true;
1019                 }
1020             }
1021             if (found) return result;
1022             throw Error.NoMatch();
1023         }
1024
1025         public static TSource LastOrDefault<TSource>(this IEnumerable<TSource> source) {
1026             if (source == null) throw Error.ArgumentNull("source");
1027             IList<TSource> list = source as IList<TSource>;
1028             if (list != null) {
1029                 int count = list.Count;
1030                 if (count > 0) return list[count - 1];
1031             }
1032             else {
1033                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
1034                     if (e.MoveNext()) {
1035                         TSource result;
1036                         do {
1037                             result = e.Current;
1038                         } while (e.MoveNext());
1039                         return result;
1040                     }
1041                 }
1042             }
1043             return default(TSource);
1044         }
1045
1046         public static TSource LastOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1047             if (source == null) throw Error.ArgumentNull("source");
1048             if (predicate == null) throw Error.ArgumentNull("predicate");
1049             TSource result = default(TSource);
1050             foreach (TSource element in source) {
1051                 if (predicate(element)) {
1052                     result = element;
1053                 }
1054             }
1055             return result;
1056         }
1057
1058         public static TSource Single<TSource>(this IEnumerable<TSource> source) {
1059             if (source == null) throw Error.ArgumentNull("source");
1060             IList<TSource> list = source as IList<TSource>;
1061             if (list != null) {
1062                 switch (list.Count) {
1063                     case 0: throw Error.NoElements();
1064                     case 1: return list[0];
1065                 }
1066             }
1067             else {
1068                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
1069                     if (!e.MoveNext()) throw Error.NoElements();
1070                     TSource result = e.Current;
1071                     if (!e.MoveNext()) return result;
1072                 }
1073             }
1074             throw Error.MoreThanOneElement();
1075         }
1076
1077         public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1078             if (source == null) throw Error.ArgumentNull("source");
1079             if (predicate == null) throw Error.ArgumentNull("predicate");
1080             TSource result = default(TSource);
1081             long count = 0;
1082             foreach (TSource element in source) {
1083                 if (predicate(element)) {
1084                     result = element;
1085                     checked { count++; }
1086                 }
1087             }
1088             switch (count) {
1089                 case 0: throw Error.NoMatch();
1090                 case 1: return result;
1091             }
1092             throw Error.MoreThanOneMatch();
1093         }
1094
1095         public static TSource SingleOrDefault<TSource>(this IEnumerable<TSource> source) {
1096             if (source == null) throw Error.ArgumentNull("source");
1097             IList<TSource> list = source as IList<TSource>;
1098             if (list != null) {
1099                 switch (list.Count) {
1100                     case 0: return default(TSource);
1101                     case 1: return list[0];
1102                 }
1103             }
1104             else {
1105                 using (IEnumerator<TSource> e = source.GetEnumerator()) {
1106                     if (!e.MoveNext()) return default(TSource);
1107                     TSource result = e.Current;
1108                     if (!e.MoveNext()) return result;
1109                 }
1110             }
1111             throw Error.MoreThanOneElement();
1112         }
1113
1114         public static TSource SingleOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1115             if (source == null) throw Error.ArgumentNull("source");
1116             if (predicate == null) throw Error.ArgumentNull("predicate");
1117             TSource result = default(TSource);
1118             long count = 0;
1119             foreach (TSource element in source) {
1120                 if (predicate(element)) {
1121                     result = element;
1122                     checked { count++; }
1123                 }
1124             }
1125             switch (count) {
1126                 case 0: return default(TSource);
1127                 case 1: return result;
1128             }
1129             throw Error.MoreThanOneMatch();
1130         }
1131
1132         public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, int index) {
1133             if (source == null) throw Error.ArgumentNull("source");
1134             IList<TSource> list = source as IList<TSource>;
1135             if (list != null) return list[index];
1136             if (index < 0) throw Error.ArgumentOutOfRange("index");
1137             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1138                 while (true) {
1139                     if (!e.MoveNext()) throw Error.ArgumentOutOfRange("index");
1140                     if (index == 0) return e.Current;
1141                     index--;
1142                 }
1143             }
1144         }
1145
1146         public static TSource ElementAtOrDefault<TSource>(this IEnumerable<TSource> source, int index) {
1147             if (source == null) throw Error.ArgumentNull("source");
1148             if (index >= 0) {
1149                 IList<TSource> list = source as IList<TSource>;
1150                 if (list != null) {
1151                     if (index < list.Count) return list[index];
1152                 }
1153                 else {
1154                     using (IEnumerator<TSource> e = source.GetEnumerator()) {
1155                         while (true) {
1156                             if (!e.MoveNext()) break;
1157                             if (index == 0) return e.Current;
1158                             index--;
1159                         }
1160                     }
1161                 }
1162             }
1163             return default(TSource);
1164         }
1165
1166         public static IEnumerable<int> Range(int start, int count) {
1167             long max = ((long)start) + count - 1;
1168             if (count < 0 || max > Int32.MaxValue) throw Error.ArgumentOutOfRange("count");
1169             return RangeIterator(start, count);
1170         }
1171
1172         static IEnumerable<int> RangeIterator(int start, int count) {
1173             for (int i = 0; i < count; i++) yield return start + i;
1174         }
1175
1176         public static IEnumerable<TResult> Repeat<TResult>(TResult element, int count) {
1177             if (count < 0) throw Error.ArgumentOutOfRange("count");
1178             return RepeatIterator<TResult>(element, count);
1179         }
1180
1181         static IEnumerable<TResult> RepeatIterator<TResult>(TResult element, int count) {
1182             for (int i = 0; i < count; i++) yield return element;
1183         }
1184
1185         public static IEnumerable<TResult> Empty<TResult>() {
1186             return EmptyEnumerable<TResult>.Instance;
1187         }
1188
1189         public static bool Any<TSource>(this IEnumerable<TSource> source) {
1190             if (source == null) throw Error.ArgumentNull("source");
1191             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1192                 if (e.MoveNext()) return true;
1193             }
1194             return false;
1195         }
1196
1197         public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1198             if (source == null) throw Error.ArgumentNull("source");
1199             if (predicate == null) throw Error.ArgumentNull("predicate");
1200             foreach (TSource element in source) {
1201                 if (predicate(element)) return true;
1202             }
1203             return false;
1204         }
1205
1206         public static bool All<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1207             if (source == null) throw Error.ArgumentNull("source");
1208             if (predicate == null) throw Error.ArgumentNull("predicate");
1209             foreach (TSource element in source) {
1210                 if (!predicate(element)) return false;
1211             }
1212             return true;
1213         }
1214
1215         public static int Count<TSource>(this IEnumerable<TSource> source) {
1216             if (source == null) throw Error.ArgumentNull("source");
1217             ICollection<TSource> collectionoft = source as ICollection<TSource>;
1218             if (collectionoft != null) return collectionoft.Count;
1219             ICollection collection = source as ICollection;
1220             if (collection != null) return collection.Count;
1221             int count = 0;
1222             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1223                 checked {
1224                     while (e.MoveNext()) count++;
1225                 }
1226             }
1227             return count;
1228         }
1229
1230         public static int Count<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1231             if (source == null) throw Error.ArgumentNull("source");
1232             if (predicate == null) throw Error.ArgumentNull("predicate");
1233             int count = 0;
1234             foreach (TSource element in source) {
1235                 checked {
1236                     if (predicate(element)) count++;
1237                 }
1238             }
1239             return count;
1240         }
1241
1242         public static long LongCount<TSource>(this IEnumerable<TSource> source) {
1243             if (source == null) throw Error.ArgumentNull("source");
1244             long count = 0;
1245             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1246                 checked {
1247                     while (e.MoveNext()) count++;
1248                 }
1249             }
1250             return count;
1251         }
1252
1253         public static long LongCount<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
1254             if (source == null) throw Error.ArgumentNull("source");
1255             if (predicate == null) throw Error.ArgumentNull("predicate");
1256             long count = 0;
1257             foreach (TSource element in source) {
1258                 checked {
1259                     if (predicate(element)) count++;
1260                 }
1261             }
1262             return count;
1263         }
1264
1265         public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value) {
1266             ICollection<TSource> collection = source as ICollection<TSource>;
1267             if (collection != null) return collection.Contains(value);
1268             return Contains<TSource>(source, value, null);
1269         }
1270
1271         public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value, IEqualityComparer<TSource> comparer)
1272         {
1273             if (comparer == null) comparer = EqualityComparer<TSource>.Default;
1274             if (source == null) throw Error.ArgumentNull("source");
1275             foreach (TSource element in source)
1276                 if (comparer.Equals(element, value)) return true;
1277             return false;
1278         }
1279
1280         public static TSource Aggregate<TSource>(this IEnumerable<TSource> source, Func<TSource, TSource, TSource> func)
1281         {
1282             if (source == null) throw Error.ArgumentNull("source");
1283             if (func == null) throw Error.ArgumentNull("func");
1284             using (IEnumerator<TSource> e = source.GetEnumerator()) {
1285                 if (!e.MoveNext()) throw Error.NoElements();
1286                 TSource result = e.Current;
1287                 while (e.MoveNext()) result = func(result, e.Current);
1288                 return result;
1289             }
1290         }
1291
1292         public static TAccumulate Aggregate<TSource, TAccumulate>(this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func) {
1293             if (source == null) throw Error.ArgumentNull("source");
1294             if (func == null) throw Error.ArgumentNull("func");
1295             TAccumulate result = seed;
1296             foreach (TSource element in source) result = func(result, element);
1297             return result;
1298         }
1299
1300         public static TResult Aggregate<TSource, TAccumulate, TResult>(this IEnumerable<TSource> source, TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func, Func<TAccumulate, TResult> resultSelector) {
1301             if (source == null) throw Error.ArgumentNull("source");
1302             if (func == null) throw Error.ArgumentNull("func");
1303             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
1304             TAccumulate result = seed;
1305             foreach (TSource element in source) result = func(result, element);
1306             return resultSelector(result);
1307         }
1308
1309         public static int Sum(this IEnumerable<int> source) {
1310             if (source == null) throw Error.ArgumentNull("source");
1311             int sum = 0;
1312             checked {
1313                 foreach (int v in source) sum += v;
1314             }
1315             return sum;
1316         }
1317
1318         public static int? Sum(this IEnumerable<int?> source) {
1319             if (source == null) throw Error.ArgumentNull("source");
1320             int sum = 0;
1321             checked {
1322                 foreach (int? v in source) {
1323                     if (v != null) sum += v.GetValueOrDefault();
1324                 }
1325             }
1326             return sum;
1327         }
1328
1329         public static long Sum(this IEnumerable<long> source) {
1330             if (source == null) throw Error.ArgumentNull("source");
1331             long sum = 0;
1332             checked {
1333                 foreach (long v in source) sum += v;
1334             }
1335             return sum;
1336         }
1337
1338         public static long? Sum(this IEnumerable<long?> source) {
1339             if (source == null) throw Error.ArgumentNull("source");
1340             long sum = 0;
1341             checked {
1342                 foreach (long? v in source) {
1343                     if (v != null) sum += v.GetValueOrDefault();
1344                 }
1345             }
1346             return sum;
1347         }
1348
1349         public static float Sum(this IEnumerable<float> source) {
1350             if (source == null) throw Error.ArgumentNull("source");
1351             double sum = 0;
1352             foreach (float v in source) sum += v;
1353             return (float)sum;
1354         }
1355
1356         public static float? Sum(this IEnumerable<float?> source) {
1357             if (source == null) throw Error.ArgumentNull("source");
1358             double sum = 0;
1359             foreach (float? v in source) {
1360                 if (v != null) sum += v.GetValueOrDefault();
1361             }
1362             return (float)sum;
1363         }
1364
1365         public static double Sum(this IEnumerable<double> source) {
1366             if (source == null) throw Error.ArgumentNull("source");
1367             double sum = 0;
1368             foreach (double v in source) sum += v;
1369             return sum;
1370         }
1371
1372         public static double? Sum(this IEnumerable<double?> source) {
1373             if (source == null) throw Error.ArgumentNull("source");
1374             double sum = 0;
1375             foreach (double? v in source) {
1376                 if (v != null) sum += v.GetValueOrDefault();
1377             }
1378             return sum;
1379         }
1380
1381         public static decimal Sum(this IEnumerable<decimal> source) {
1382             if (source == null) throw Error.ArgumentNull("source");
1383             decimal sum = 0;
1384             foreach (decimal v in source) sum += v;
1385             return sum;
1386         }
1387
1388         public static decimal? Sum(this IEnumerable<decimal?> source) {
1389             if (source == null) throw Error.ArgumentNull("source");
1390             decimal sum = 0;
1391             foreach (decimal? v in source) {
1392                 if (v != null) sum += v.GetValueOrDefault();
1393             }
1394             return sum;
1395         }
1396
1397         public static int Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
1398             return Enumerable.Sum(Enumerable.Select(source, selector));
1399         }
1400
1401         public static int? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
1402             return Enumerable.Sum(Enumerable.Select(source, selector));
1403         }
1404
1405         public static long Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
1406             return Enumerable.Sum(Enumerable.Select(source, selector));
1407         }
1408
1409         public static long? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
1410             return Enumerable.Sum(Enumerable.Select(source, selector));
1411         }
1412
1413         public static float Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
1414             return Enumerable.Sum(Enumerable.Select(source, selector));
1415         }
1416
1417         public static float? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
1418             return Enumerable.Sum(Enumerable.Select(source, selector));
1419         }
1420
1421         public static double Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
1422             return Enumerable.Sum(Enumerable.Select(source, selector));
1423         }
1424
1425         public static double? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
1426             return Enumerable.Sum(Enumerable.Select(source, selector));
1427         }
1428
1429         public static decimal Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
1430             return Enumerable.Sum(Enumerable.Select(source, selector));
1431         }
1432
1433         public static decimal? Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
1434             return Enumerable.Sum(Enumerable.Select(source, selector));
1435         }
1436
1437         public static int Min(this IEnumerable<int> source) {
1438             if (source == null) throw Error.ArgumentNull("source");
1439             int value = 0;
1440             bool hasValue = false;
1441             foreach (int x in source) {
1442                 if (hasValue) {
1443                     if (x < value) value = x;
1444                 }
1445                 else {
1446                     value = x;
1447                     hasValue = true;
1448                 }
1449             }
1450             if (hasValue) return value;
1451             throw Error.NoElements();
1452         }
1453
1454         public static int? Min(this IEnumerable<int?> source) {
1455             if (source == null) throw Error.ArgumentNull("source");
1456             int? value = null;
1457             foreach (int? x in source) {
1458                 if (value == null || x < value)
1459                     value = x;
1460             }
1461             return value;
1462         }
1463
1464         public static long Min(this IEnumerable<long> source) {
1465             if (source == null) throw Error.ArgumentNull("source");
1466             long value = 0;
1467             bool hasValue = false;
1468             foreach (long x in source) {
1469                 if (hasValue) {
1470                     if (x < value) value = x;
1471                 }
1472                 else {
1473                     value = x;
1474                     hasValue = true;
1475                 }
1476             }
1477             if (hasValue) return value;
1478             throw Error.NoElements();
1479         }
1480
1481         public static long? Min(this IEnumerable<long?> source) {
1482             if (source == null) throw Error.ArgumentNull("source");
1483             long? value = null;
1484             foreach (long? x in source) {
1485                 if (value == null || x < value) value = x;
1486             }
1487             return value;
1488         }
1489
1490         public static float Min(this IEnumerable<float> source) {
1491             if (source == null) throw Error.ArgumentNull("source");
1492             float value = 0;
1493             bool hasValue = false;
1494             foreach (float x in source) {
1495                 if (hasValue) {
1496                     // Normally NaN < anything is false, as is anything < NaN
1497                     // However, this leads to some irksome outcomes in Min and Max.
1498                     // If we use those semantics then Min(NaN, 5.0) is NaN, but
1499                     // Min(5.0, NaN) is 5.0!  To fix this, we impose a total
1500                     // ordering where NaN is smaller than every value, including
1501                     // negative infinity.
1502                     if (x < value || System.Single.IsNaN(x)) value = x;
1503                 }
1504                 else {
1505                     value = x;
1506                     hasValue = true;
1507                 }
1508             }
1509             if (hasValue) return value;
1510             throw Error.NoElements();
1511         }
1512
1513         public static float? Min(this IEnumerable<float?> source) {
1514             if (source == null) throw Error.ArgumentNull("source");
1515             float? value = null;
1516             foreach (float? x in source) {
1517                 if (x == null) continue;
1518                 if (value == null || x < value || System.Single.IsNaN((float)x)) value = x;
1519             }
1520             return value;
1521         }
1522
1523         public static double Min(this IEnumerable<double> source) {
1524             if (source == null) throw Error.ArgumentNull("source");
1525             double value = 0;
1526             bool hasValue = false;
1527             foreach (double x in source) {
1528                 if (hasValue) {
1529                     if (x < value || System.Double.IsNaN(x)) value = x;
1530                 }
1531                 else {
1532                     value = x;
1533                     hasValue = true;
1534                 }
1535             }
1536             if (hasValue) return value;
1537             throw Error.NoElements();
1538         }
1539
1540         public static double? Min(this IEnumerable<double?> source) {
1541             if (source == null) throw Error.ArgumentNull("source");
1542             double? value = null;
1543             foreach (double? x in source) {
1544                 if (x == null) continue;
1545                 if (value == null || x < value || System.Double.IsNaN((double)x)) value = x;
1546             }
1547             return value;
1548         }
1549
1550         public static decimal Min(this IEnumerable<decimal> source) {
1551             if (source == null) throw Error.ArgumentNull("source");
1552             decimal value = 0;
1553             bool hasValue = false;
1554             foreach (decimal x in source) {
1555                 if (hasValue) {
1556                     if (x < value) value = x;
1557                 }
1558                 else {
1559                     value = x;
1560                     hasValue = true;
1561                 }
1562             }
1563             if (hasValue) return value;
1564             throw Error.NoElements();
1565         }
1566
1567         public static decimal? Min(this IEnumerable<decimal?> source) {
1568             if (source == null) throw Error.ArgumentNull("source");
1569             decimal? value = null;
1570             foreach (decimal? x in source) {
1571                 if (value == null || x < value) value = x;
1572             }
1573             return value;
1574         }
1575
1576         public static TSource Min<TSource>(this IEnumerable<TSource> source) {
1577             if (source == null) throw Error.ArgumentNull("source");
1578             Comparer<TSource> comparer = Comparer<TSource>.Default;
1579             TSource value = default(TSource);
1580             if (value == null) {
1581                 foreach (TSource x in source) {
1582                     if (x != null && (value == null || comparer.Compare(x, value) < 0))
1583                         value = x;
1584                 }
1585                 return value;
1586             }
1587             else {
1588                 bool hasValue = false;
1589                 foreach (TSource x in source) {
1590                     if (hasValue) {
1591                         if (comparer.Compare(x, value) < 0)
1592                             value = x;
1593                     }
1594                     else {
1595                         value = x;
1596                         hasValue = true;
1597                     }
1598                 }
1599                 if (hasValue) return value;
1600                 throw Error.NoElements();
1601             }
1602         }
1603
1604         public static int Min<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
1605             return Enumerable.Min(Enumerable.Select(source, selector));
1606         }
1607
1608         public static int? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
1609             return Enumerable.Min(Enumerable.Select(source, selector));
1610         }
1611
1612         public static long Min<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
1613             return Enumerable.Min(Enumerable.Select(source, selector));
1614         }
1615
1616         public static long? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
1617             return Enumerable.Min(Enumerable.Select(source, selector));
1618         }
1619
1620         public static float Min<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
1621             return Enumerable.Min(Enumerable.Select(source, selector));
1622         }
1623
1624         public static float? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
1625             return Enumerable.Min(Enumerable.Select(source, selector));
1626         }
1627
1628         public static double Min<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
1629             return Enumerable.Min(Enumerable.Select(source, selector));
1630         }
1631
1632         public static double? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
1633             return Enumerable.Min(Enumerable.Select(source, selector));
1634         }
1635
1636         public static decimal Min<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
1637             return Enumerable.Min(Enumerable.Select(source, selector));
1638         }
1639
1640         public static decimal? Min<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
1641             return Enumerable.Min(Enumerable.Select(source, selector));
1642         }
1643
1644         public static TResult Min<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector) {
1645             return Enumerable.Min(Enumerable.Select(source, selector));
1646         }
1647
1648         public static int Max(this IEnumerable<int> source) {
1649             if (source == null) throw Error.ArgumentNull("source");
1650             int value = 0;
1651             bool hasValue = false;
1652             foreach (int x in source) {
1653                 if (hasValue) {
1654                     if (x > value) value = x;
1655                 }
1656                 else {
1657                     value = x;
1658                     hasValue = true;
1659                 }
1660             }
1661             if (hasValue) return value;
1662             throw Error.NoElements();
1663         }
1664
1665         public static int? Max(this IEnumerable<int?> source) {
1666             if (source == null) throw Error.ArgumentNull("source");
1667             int? value = null;
1668             foreach (int? x in source) {
1669                 if (value == null || x > value) value = x;
1670             }
1671             return value;
1672         }
1673
1674         public static long Max(this IEnumerable<long> source) {
1675             if (source == null) throw Error.ArgumentNull("source");
1676             long value = 0;
1677             bool hasValue = false;
1678             foreach (long x in source) {
1679                 if (hasValue) {
1680                     if (x > value) value = x;
1681                 }
1682                 else {
1683                     value = x;
1684                     hasValue = true;
1685                 }
1686             }
1687             if (hasValue) return value;
1688             throw Error.NoElements();
1689         }
1690
1691         public static long? Max(this IEnumerable<long?> source) {
1692             if (source == null) throw Error.ArgumentNull("source");
1693             long? value = null;
1694             foreach (long? x in source) {
1695                 if (value == null || x > value) value = x;
1696             }
1697             return value;
1698         }
1699
1700         public static double Max(this IEnumerable<double> source) {
1701             if (source == null) throw Error.ArgumentNull("source");
1702             double value = 0;
1703             bool hasValue = false;
1704             foreach (double x in source) {
1705                 if (hasValue) {
1706                     if (x > value || System.Double.IsNaN(value)) value = x;
1707                 }
1708                 else {
1709                     value = x;
1710                     hasValue = true;
1711                 }
1712             }
1713             if (hasValue) return value;
1714             throw Error.NoElements();
1715         }
1716
1717         public static double? Max(this IEnumerable<double?> source) {
1718             if (source == null) throw Error.ArgumentNull("source");
1719             double? value = null;
1720             foreach (double? x in source) {
1721                 if (x == null) continue;
1722                 if (value == null || x > value || System.Double.IsNaN((double)value)) value = x;
1723             }
1724             return value;
1725         }
1726
1727         public static float Max(this IEnumerable<float> source) {
1728             if (source == null) throw Error.ArgumentNull("source");
1729             float value = 0;
1730             bool hasValue = false;
1731             foreach (float x in source) {
1732                 if (hasValue) {
1733                     if (x > value || System.Double.IsNaN(value)) value = x;
1734                 }
1735                 else {
1736                     value = x;
1737                     hasValue = true;
1738                 }
1739             }
1740             if (hasValue) return value;
1741             throw Error.NoElements();
1742         }
1743
1744         public static float? Max(this IEnumerable<float?> source) {
1745             if (source == null) throw Error.ArgumentNull("source");
1746             float? value = null;
1747             foreach (float? x in source) {
1748                 if (x == null) continue;
1749                 if (value == null || x > value || System.Single.IsNaN((float)value)) value = x;
1750             }
1751             return value;
1752         }
1753
1754         public static decimal Max(this IEnumerable<decimal> source) {
1755             if (source == null) throw Error.ArgumentNull("source");
1756             decimal value = 0;
1757             bool hasValue = false;
1758             foreach (decimal x in source) {
1759                 if (hasValue) {
1760                     if (x > value) value = x;
1761                 }
1762                 else {
1763                     value = x;
1764                     hasValue = true;
1765                 }
1766             }
1767             if (hasValue) return value;
1768             throw Error.NoElements();
1769         }
1770
1771         public static decimal? Max(this IEnumerable<decimal?> source) {
1772             if (source == null) throw Error.ArgumentNull("source");
1773             decimal? value = null;
1774             foreach (decimal? x in source) {
1775                 if (value == null || x > value) value = x;
1776             }
1777             return value;
1778         }
1779
1780         public static TSource Max<TSource>(this IEnumerable<TSource> source) {
1781             if (source == null) throw Error.ArgumentNull("source");
1782             Comparer<TSource> comparer = Comparer<TSource>.Default;
1783             TSource value = default(TSource);
1784             if (value == null) {
1785                 foreach (TSource x in source) {
1786                     if (x != null && (value == null || comparer.Compare(x, value) > 0))
1787                         value = x;
1788                 }
1789                 return value;
1790             }
1791             else {
1792                 bool hasValue = false;
1793                 foreach (TSource x in source) {
1794                     if (hasValue) {
1795                         if (comparer.Compare(x, value) > 0)
1796                             value = x;
1797                     }
1798                     else {
1799                         value = x;
1800                         hasValue = true;
1801                     }
1802                 }
1803                 if (hasValue) return value;
1804                 throw Error.NoElements();
1805             }
1806         }
1807
1808         public static int Max<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
1809             return Enumerable.Max(Enumerable.Select(source, selector));
1810         }
1811
1812         public static int? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
1813             return Enumerable.Max(Enumerable.Select(source, selector));
1814         }
1815
1816         public static long Max<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
1817             return Enumerable.Max(Enumerable.Select(source, selector));
1818         }
1819
1820         public static long? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
1821             return Enumerable.Max(Enumerable.Select(source, selector));
1822         }
1823
1824         public static float Max<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
1825             return Enumerable.Max(Enumerable.Select(source, selector));
1826         }
1827
1828         public static float? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
1829             return Enumerable.Max(Enumerable.Select(source, selector));
1830         }
1831
1832         public static double Max<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
1833             return Enumerable.Max(Enumerable.Select(source, selector));
1834         }
1835
1836         public static double? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
1837             return Enumerable.Max(Enumerable.Select(source, selector));
1838         }
1839
1840         public static decimal Max<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
1841             return Enumerable.Max(Enumerable.Select(source, selector));
1842         }
1843
1844         public static decimal? Max<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
1845             return Enumerable.Max(Enumerable.Select(source, selector));
1846         }
1847
1848         public static TResult Max<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector) {
1849             return Enumerable.Max(Enumerable.Select(source, selector));
1850         }
1851
1852         public static double Average(this IEnumerable<int> source) {
1853             if (source == null) throw Error.ArgumentNull("source");
1854             long sum = 0;
1855             long count = 0;
1856             checked {
1857                 foreach (int v in source) {
1858                     sum += v;
1859                     count++;
1860                 }
1861             }
1862             if (count > 0) return (double)sum / count;
1863             throw Error.NoElements();
1864         }
1865
1866         public static double? Average(this IEnumerable<int?> source) {
1867             if (source == null) throw Error.ArgumentNull("source");
1868             long sum = 0;
1869             long count = 0;
1870             checked {
1871                 foreach (int? v in source) {
1872                     if (v != null) {
1873                         sum += v.GetValueOrDefault();
1874                         count++;
1875                     }
1876                 }
1877             }
1878             if (count > 0) return (double)sum / count;
1879             return null;
1880         }
1881
1882         public static double Average(this IEnumerable<long> source) {
1883             if (source == null) throw Error.ArgumentNull("source");
1884             long sum = 0;
1885             long count = 0;
1886             checked {
1887                 foreach (long v in source) {
1888                     sum += v;
1889                     count++;
1890                 }
1891             }
1892             if (count > 0) return (double)sum / count;
1893             throw Error.NoElements();
1894         }
1895
1896         public static double? Average(this IEnumerable<long?> source) {
1897             if (source == null) throw Error.ArgumentNull("source");
1898             long sum = 0;
1899             long count = 0;
1900             checked {
1901                 foreach (long? v in source) {
1902                     if (v != null) {
1903                         sum += v.GetValueOrDefault();
1904                         count++;
1905                     }
1906                 }
1907             }
1908             if (count > 0) return (double)sum / count;
1909             return null;
1910         }
1911
1912         public static float Average(this IEnumerable<float> source) {
1913             if (source == null) throw Error.ArgumentNull("source");
1914             double sum = 0;
1915             long count = 0;
1916             checked {
1917                 foreach (float v in source) {
1918                     sum += v;
1919                     count++;
1920                 }
1921             }
1922             if (count > 0) return (float)(sum / count);
1923             throw Error.NoElements();
1924         }
1925
1926         public static float? Average(this IEnumerable<float?> source) {
1927             if (source == null) throw Error.ArgumentNull("source");
1928             double sum = 0;
1929             long count = 0;
1930             checked {
1931                 foreach (float? v in source) {
1932                     if (v != null) {
1933                         sum += v.GetValueOrDefault();
1934                         count++;
1935                     }
1936                 }
1937             }
1938             if (count > 0) return (float)(sum / count);
1939             return null;
1940         }
1941
1942         public static double Average(this IEnumerable<double> source) {
1943             if (source == null) throw Error.ArgumentNull("source");
1944             double sum = 0;
1945             long count = 0;
1946             checked {
1947                 foreach (double v in source) {
1948                     sum += v;
1949                     count++;
1950                 }
1951             }
1952             if (count > 0) return sum / count;
1953             throw Error.NoElements();
1954         }
1955
1956         public static double? Average(this IEnumerable<double?> source) {
1957             if (source == null) throw Error.ArgumentNull("source");
1958             double sum = 0;
1959             long count = 0;
1960             checked {
1961                 foreach (double? v in source) {
1962                     if (v != null) {
1963                         sum += v.GetValueOrDefault();
1964                         count++;
1965                     }
1966                 }
1967             }
1968             if (count > 0) return sum / count;
1969             return null;
1970         }
1971
1972         public static decimal Average(this IEnumerable<decimal> source) {
1973             if (source == null) throw Error.ArgumentNull("source");
1974             decimal sum = 0;
1975             long count = 0;
1976             checked {
1977                 foreach (decimal v in source) {
1978                     sum += v;
1979                     count++;
1980                 }
1981             }
1982             if (count > 0) return sum / count;
1983             throw Error.NoElements();
1984         }
1985
1986         public static decimal? Average(this IEnumerable<decimal?> source) {
1987             if (source == null) throw Error.ArgumentNull("source");
1988             decimal sum = 0;
1989             long count = 0;
1990             checked {
1991                 foreach (decimal? v in source) {
1992                     if (v != null) {
1993                         sum += v.GetValueOrDefault();
1994                         count++;
1995                     }
1996                 }
1997             }
1998             if (count > 0) return sum / count;
1999             return null;
2000         }
2001
2002         public static double Average<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector) {
2003             return Enumerable.Average(Enumerable.Select(source, selector));
2004         }
2005
2006         public static double? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, int?> selector) {
2007             return Enumerable.Average(Enumerable.Select(source, selector));
2008         }
2009
2010         public static double Average<TSource>(this IEnumerable<TSource> source, Func<TSource, long> selector) {
2011             return Enumerable.Average(Enumerable.Select(source, selector));
2012         }
2013
2014         public static double? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, long?> selector) {
2015             return Enumerable.Average(Enumerable.Select(source, selector));
2016         }
2017
2018         public static float Average<TSource>(this IEnumerable<TSource> source, Func<TSource, float> selector) {
2019             return Enumerable.Average(Enumerable.Select(source, selector));
2020         }
2021
2022         public static float? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, float?> selector) {
2023             return Enumerable.Average(Enumerable.Select(source, selector));
2024         }
2025
2026         public static double Average<TSource>(this IEnumerable<TSource> source, Func<TSource, double> selector) {
2027             return Enumerable.Average(Enumerable.Select(source, selector));
2028         }
2029
2030         public static double? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, double?> selector) {
2031             return Enumerable.Average(Enumerable.Select(source, selector));
2032         }
2033
2034         public static decimal Average<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal> selector) {
2035             return Enumerable.Average(Enumerable.Select(source, selector));
2036         }
2037
2038         public static decimal? Average<TSource>(this IEnumerable<TSource> source, Func<TSource, decimal?> selector) {
2039             return Enumerable.Average(Enumerable.Select(source, selector));
2040         }
2041     }
2042
2043
2044     //
2045     // We have added some optimization in SZArrayHelper class to cache the enumerator of zero length arrays so
2046     // the enumerator will be created once per type.
2047     //
2048     internal class EmptyEnumerable<TElement>
2049     {
2050         public static readonly TElement[] Instance = new TElement[0];
2051     }
2052
2053     internal class IdentityFunction<TElement>
2054     {
2055         public static Func<TElement, TElement> Instance {
2056             get { return x => x; }
2057         }
2058     }
2059
2060     public interface IOrderedEnumerable<TElement> : IEnumerable<TElement>
2061     {
2062         IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending);
2063     }
2064
2065 #if SILVERLIGHT && !FEATURE_NETCORE
2066     public interface IGrouping<TKey, TElement> : IEnumerable<TElement>
2067 #else
2068     public interface IGrouping<out TKey, out TElement> : IEnumerable<TElement>
2069 #endif
2070     {
2071         TKey Key { get; }
2072     }
2073
2074     public interface ILookup<TKey, TElement> : IEnumerable<IGrouping<TKey, TElement>>{
2075         int Count { get; }
2076         IEnumerable<TElement> this[TKey key] { get; }
2077         bool Contains(TKey key);
2078     }
2079
2080     public class Lookup<TKey, TElement> : IEnumerable<IGrouping<TKey, TElement>>, ILookup<TKey, TElement>{
2081         IEqualityComparer<TKey> comparer;
2082         Grouping[] groupings;
2083         Grouping lastGrouping;
2084         int count;
2085
2086         internal static Lookup<TKey, TElement> Create<TSource>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
2087             if (source == null) throw Error.ArgumentNull("source");
2088             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2089             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
2090             Lookup<TKey, TElement> lookup = new Lookup<TKey, TElement>(comparer);
2091             foreach (TSource item in source) {
2092                 lookup.GetGrouping(keySelector(item), true).Add(elementSelector(item));
2093             }
2094             return lookup;
2095         }
2096
2097         internal static Lookup<TKey, TElement> CreateForJoin(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IEqualityComparer<TKey> comparer) {
2098             Lookup<TKey, TElement> lookup = new Lookup<TKey, TElement>(comparer);
2099             foreach (TElement item in source) {
2100                 TKey key = keySelector(item);
2101                 if (key != null) lookup.GetGrouping(key, true).Add(item);
2102             }
2103             return lookup;
2104         }
2105
2106         Lookup(IEqualityComparer<TKey> comparer) {
2107             if (comparer == null) comparer = EqualityComparer<TKey>.Default;
2108             this.comparer = comparer;
2109             groupings = new Grouping[7];
2110         }
2111
2112         public int Count {
2113             get { return count; }
2114         }
2115
2116         public IEnumerable<TElement> this[TKey key] {
2117             get {
2118                 Grouping grouping = GetGrouping(key, false);
2119                 if (grouping != null) return grouping;
2120                 return EmptyEnumerable<TElement>.Instance;
2121             }
2122         }
2123
2124         public bool Contains(TKey key) {
2125             return GetGrouping(key, false) != null;
2126         }
2127
2128         public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator() {
2129             Grouping g = lastGrouping;
2130             if (g != null) {
2131                 do {
2132                     g = g.next;
2133                     yield return g;
2134                 } while (g != lastGrouping);
2135             }
2136         }
2137
2138         public IEnumerable<TResult> ApplyResultSelector<TResult>(Func<TKey, IEnumerable<TElement>, TResult> resultSelector){
2139             Grouping g = lastGrouping;
2140             if (g != null) {
2141                 do {
2142                     g = g.next;
2143                     if (g.count != g.elements.Length) { Array.Resize<TElement>(ref g.elements, g.count); }
2144                     yield return resultSelector(g.key, g.elements);
2145                 }while (g != lastGrouping);
2146             }
2147         }
2148
2149         IEnumerator IEnumerable.GetEnumerator() {
2150             return GetEnumerator();
2151         }
2152
2153         internal int InternalGetHashCode(TKey key)
2154         {
2155             //[....] DevDivBugs 171937. work around comparer implementations that throw when passed null
2156             return (key == null) ? 0 : comparer.GetHashCode(key) & 0x7FFFFFFF;
2157         }
2158
2159         internal Grouping GetGrouping(TKey key, bool create) {
2160             int hashCode = InternalGetHashCode(key);
2161             for (Grouping g = groupings[hashCode % groupings.Length]; g != null; g = g.hashNext)
2162                 if (g.hashCode == hashCode && comparer.Equals(g.key, key)) return g;
2163             if (create) {
2164                 if (count == groupings.Length) Resize();
2165                 int index = hashCode % groupings.Length;
2166                 Grouping g = new Grouping();
2167                 g.key = key;
2168                 g.hashCode = hashCode;
2169                 g.elements = new TElement[1];
2170                 g.hashNext = groupings[index];
2171                 groupings[index] = g;
2172                 if (lastGrouping == null) {
2173                     g.next = g;
2174                 }
2175                 else {
2176                     g.next = lastGrouping.next;
2177                     lastGrouping.next = g;
2178                 }
2179                 lastGrouping = g;
2180                 count++;
2181                 return g;
2182             }
2183             return null;
2184         }
2185
2186         void Resize() {
2187             int newSize = checked(count * 2 + 1);
2188             Grouping[] newGroupings = new Grouping[newSize];
2189             Grouping g = lastGrouping;
2190             do {
2191                 g = g.next;
2192                 int index = g.hashCode % newSize;
2193                 g.hashNext = newGroupings[index];
2194                 newGroupings[index] = g;
2195             } while (g != lastGrouping);
2196             groupings = newGroupings;
2197         }
2198
2199         internal class Grouping : IGrouping<TKey, TElement>, IList<TElement>
2200         {
2201             internal TKey key;
2202             internal int hashCode;
2203             internal TElement[] elements;
2204             internal int count;
2205             internal Grouping hashNext;
2206             internal Grouping next;
2207
2208             internal void Add(TElement element) {
2209                 if (elements.Length == count) Array.Resize(ref elements, checked(count * 2));
2210                 elements[count] = element;
2211                 count++;
2212             }
2213
2214             public IEnumerator<TElement> GetEnumerator() {
2215                 for (int i = 0; i < count; i++) yield return elements[i];
2216             }
2217
2218             IEnumerator IEnumerable.GetEnumerator() {
2219                 return GetEnumerator();
2220             }
2221
2222             // DDB195907: implement IGrouping<>.Key implicitly
2223             // so that WPF binding works on this property.
2224             public TKey Key {
2225                 get { return key; }
2226             }
2227
2228             int ICollection<TElement>.Count {
2229                 get { return count; }
2230             }
2231
2232             bool ICollection<TElement>.IsReadOnly {
2233                 get { return true; }
2234             }
2235
2236             void ICollection<TElement>.Add(TElement item) {
2237                 throw Error.NotSupported();
2238             }
2239
2240             void ICollection<TElement>.Clear() {
2241                 throw Error.NotSupported();
2242             }
2243
2244             bool ICollection<TElement>.Contains(TElement item) {
2245                 return Array.IndexOf(elements, item, 0, count) >= 0;
2246             }
2247
2248             void ICollection<TElement>.CopyTo(TElement[] array, int arrayIndex) {
2249                 Array.Copy(elements, 0, array, arrayIndex, count);
2250             }
2251
2252             bool ICollection<TElement>.Remove(TElement item) {
2253                 throw Error.NotSupported();
2254             }
2255
2256             int IList<TElement>.IndexOf(TElement item) {
2257                 return Array.IndexOf(elements, item, 0, count);
2258             }
2259
2260             void IList<TElement>.Insert(int index, TElement item) {
2261                 throw Error.NotSupported();
2262             }
2263
2264             void IList<TElement>.RemoveAt(int index) {
2265                 throw Error.NotSupported();
2266             }
2267
2268             TElement IList<TElement>.this[int index] {
2269                 get {
2270                     if (index < 0 || index >= count) throw Error.ArgumentOutOfRange("index");
2271                     return elements[index];
2272                 }
2273                 set {
2274                     throw Error.NotSupported();
2275                 }
2276             }
2277         }
2278     }
2279
2280     // @
2281     internal class Set<TElement>
2282     {
2283         int[] buckets;
2284         Slot[] slots;
2285         int count;
2286         int freeList;
2287         IEqualityComparer<TElement> comparer;
2288
2289         public Set() : this(null) { }
2290
2291         public Set(IEqualityComparer<TElement> comparer) {
2292             if (comparer == null) comparer = EqualityComparer<TElement>.Default;
2293             this.comparer = comparer;
2294             buckets = new int[7];
2295             slots = new Slot[7];
2296             freeList = -1;
2297         }
2298
2299         // If value is not in set, add it and return true; otherwise return false
2300         public bool Add(TElement value) {
2301             return !Find(value, true);
2302         }
2303
2304         // Check whether value is in set
2305         public bool Contains(TElement value) {
2306             return Find(value, false);
2307         }
2308
2309         // If value is in set, remove it and return true; otherwise return false
2310         public bool Remove(TElement value) {
2311             int hashCode = InternalGetHashCode(value);
2312             int bucket = hashCode % buckets.Length;
2313             int last = -1;
2314             for (int i = buckets[bucket] - 1; i >= 0; last = i, i = slots[i].next) {
2315                 if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) {
2316                     if (last < 0) {
2317                         buckets[bucket] = slots[i].next + 1;
2318                     }
2319                     else {
2320                         slots[last].next = slots[i].next;
2321                     }
2322                     slots[i].hashCode = -1;
2323                     slots[i].value = default(TElement);
2324                     slots[i].next = freeList;
2325                     freeList = i;
2326                     return true;
2327                 }
2328             }
2329             return false;
2330         }
2331
2332         bool Find(TElement value, bool add) {
2333             int hashCode = InternalGetHashCode(value);
2334             for (int i = buckets[hashCode % buckets.Length] - 1; i >= 0; i = slots[i].next) {
2335                 if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) return true;
2336             }
2337             if (add) {
2338                 int index;
2339                 if (freeList >= 0) {
2340                     index = freeList;
2341                     freeList = slots[index].next;
2342                 }
2343                 else {
2344                     if (count == slots.Length) Resize();
2345                     index = count;
2346                     count++;
2347                 }
2348                 int bucket = hashCode % buckets.Length;
2349                 slots[index].hashCode = hashCode;
2350                 slots[index].value = value;
2351                 slots[index].next = buckets[bucket] - 1;
2352                 buckets[bucket] = index + 1;
2353             }
2354             return false;
2355         }
2356
2357         void Resize() {
2358             int newSize = checked(count * 2 + 1);
2359             int[] newBuckets = new int[newSize];
2360             Slot[] newSlots = new Slot[newSize];
2361             Array.Copy(slots, 0, newSlots, 0, count);
2362             for (int i = 0; i < count; i++) {
2363                 int bucket = newSlots[i].hashCode % newSize;
2364                 newSlots[i].next = newBuckets[bucket] - 1;
2365                 newBuckets[bucket] = i + 1;
2366             }
2367             buckets = newBuckets;
2368             slots = newSlots;
2369         }
2370
2371         internal int InternalGetHashCode(TElement value)
2372         {
2373             //[....] DevDivBugs 171937. work around comparer implementations that throw when passed null
2374             return (value == null) ? 0 : comparer.GetHashCode(value) & 0x7FFFFFFF;
2375         }
2376
2377         internal struct Slot
2378         {
2379             internal int hashCode;
2380             internal TElement value;
2381             internal int next;
2382         }
2383     }
2384
2385     internal class GroupedEnumerable<TSource, TKey, TElement, TResult> : IEnumerable<TResult>{
2386         IEnumerable<TSource> source;
2387         Func<TSource, TKey> keySelector;
2388         Func<TSource, TElement> elementSelector;
2389         IEqualityComparer<TKey> comparer;
2390         Func<TKey, IEnumerable<TElement>, TResult> resultSelector;
2391
2392         public GroupedEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, Func<TKey, IEnumerable<TElement>, TResult> resultSelector, IEqualityComparer<TKey> comparer){
2393             if (source == null) throw Error.ArgumentNull("source");
2394             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2395             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
2396             if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
2397             this.source = source;
2398             this.keySelector = keySelector;
2399             this.elementSelector = elementSelector;
2400             this.comparer = comparer;
2401             this.resultSelector = resultSelector;
2402         }
2403
2404         public IEnumerator<TResult> GetEnumerator(){
2405             Lookup<TKey, TElement> lookup = Lookup<TKey, TElement>.Create<TSource>(source, keySelector, elementSelector, comparer);
2406             return lookup.ApplyResultSelector(resultSelector).GetEnumerator();
2407         }
2408
2409         IEnumerator IEnumerable.GetEnumerator(){
2410             return GetEnumerator();
2411         }
2412     }
2413
2414     internal class GroupedEnumerable<TSource, TKey, TElement> : IEnumerable<IGrouping<TKey, TElement>>
2415     {
2416         IEnumerable<TSource> source;
2417         Func<TSource, TKey> keySelector;
2418         Func<TSource, TElement> elementSelector;
2419         IEqualityComparer<TKey> comparer;
2420
2421         public GroupedEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) {
2422             if (source == null) throw Error.ArgumentNull("source");
2423             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2424             if (elementSelector == null) throw Error.ArgumentNull("elementSelector");
2425             this.source = source;
2426             this.keySelector = keySelector;
2427             this.elementSelector = elementSelector;
2428             this.comparer = comparer;
2429         }
2430
2431         public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator() {
2432             return Lookup<TKey, TElement>.Create<TSource>(source, keySelector, elementSelector, comparer).GetEnumerator();
2433         }
2434
2435         IEnumerator IEnumerable.GetEnumerator() {
2436             return GetEnumerator();
2437         }
2438     }
2439
2440     internal abstract class OrderedEnumerable<TElement> : IOrderedEnumerable<TElement>
2441     {
2442         internal IEnumerable<TElement> source;
2443
2444         public IEnumerator<TElement> GetEnumerator() {
2445             Buffer<TElement> buffer = new Buffer<TElement>(source);
2446             if (buffer.count > 0) {
2447                 EnumerableSorter<TElement> sorter = GetEnumerableSorter(null);
2448                 int[] map = sorter.Sort(buffer.items, buffer.count);
2449                 sorter = null;
2450                 for (int i = 0; i < buffer.count; i++) yield return buffer.items[map[i]];
2451             }
2452         }
2453
2454         internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next);
2455
2456         IEnumerator IEnumerable.GetEnumerator() {
2457             return GetEnumerator();
2458         }
2459
2460         IOrderedEnumerable<TElement> IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending) {
2461             OrderedEnumerable<TElement, TKey> result = new OrderedEnumerable<TElement, TKey>(source, keySelector, comparer, descending);
2462             result.parent = this;
2463             return result;
2464         }
2465     }
2466
2467     internal class OrderedEnumerable<TElement, TKey> : OrderedEnumerable<TElement>
2468     {
2469         internal OrderedEnumerable<TElement> parent;
2470         internal Func<TElement, TKey> keySelector;
2471         internal IComparer<TKey> comparer;
2472         internal bool descending;
2473
2474         internal OrderedEnumerable(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending) {
2475             if (source == null) throw Error.ArgumentNull("source");
2476             if (keySelector == null) throw Error.ArgumentNull("keySelector");
2477             this.source = source;
2478             this.parent = null;
2479             this.keySelector = keySelector;
2480             this.comparer = comparer != null ? comparer : Comparer<TKey>.Default;
2481             this.descending = descending;
2482         }
2483
2484         internal override EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next) {
2485             EnumerableSorter<TElement> sorter = new EnumerableSorter<TElement, TKey>(keySelector, comparer, descending, next);
2486             if (parent != null) sorter = parent.GetEnumerableSorter(sorter);
2487             return sorter;
2488         }
2489     }
2490
2491     internal abstract class EnumerableSorter<TElement>
2492     {
2493         internal abstract void ComputeKeys(TElement[] elements, int count);
2494
2495         internal abstract int CompareKeys(int index1, int index2);
2496
2497         internal int[] Sort(TElement[] elements, int count) {
2498             ComputeKeys(elements, count);
2499             int[] map = new int[count];
2500             for (int i = 0; i < count; i++) map[i] = i;
2501             QuickSort(map, 0, count - 1);
2502             return map;
2503         }
2504
2505         void QuickSort(int[] map, int left, int right) {
2506             do {
2507                 int i = left;
2508                 int j = right;
2509                 int x = map[i + ((j - i) >> 1)];
2510                 do {
2511                     while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
2512                     while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
2513                     if (i > j) break;
2514                     if (i < j) {
2515                         int temp = map[i];
2516                         map[i] = map[j];
2517                         map[j] = temp;
2518                     }
2519                     i++;
2520                     j--;
2521                 } while (i <= j);
2522                 if (j - left <= right - i) {
2523                     if (left < j) QuickSort(map, left, j);
2524                     left = i;
2525                 }
2526                 else {
2527                     if (i < right) QuickSort(map, i, right);
2528                     right = j;
2529                 }
2530             } while (left < right);
2531         }
2532     }
2533
2534     internal class EnumerableSorter<TElement, TKey> : EnumerableSorter<TElement>
2535     {
2536         internal Func<TElement, TKey> keySelector;
2537         internal IComparer<TKey> comparer;
2538         internal bool descending;
2539         internal EnumerableSorter<TElement> next;
2540         internal TKey[] keys;
2541
2542         internal EnumerableSorter(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TElement> next) {
2543             this.keySelector = keySelector;
2544             this.comparer = comparer;
2545             this.descending = descending;
2546             this.next = next;
2547         }
2548
2549         internal override void ComputeKeys(TElement[] elements, int count) {
2550             keys = new TKey[count];
2551             for (int i = 0; i < count; i++) keys[i] = keySelector(elements[i]);
2552             if (next != null) next.ComputeKeys(elements, count);
2553         }
2554
2555         internal override int CompareKeys(int index1, int index2) {
2556             int c = comparer.Compare(keys[index1], keys[index2]);
2557             if (c == 0) {
2558                 if (next == null) return index1 - index2;
2559                 return next.CompareKeys(index1, index2);
2560             }
2561             return descending ? -c : c;
2562         }
2563     }
2564
2565     struct Buffer<TElement>
2566     {
2567         internal TElement[] items;
2568         internal int count;
2569
2570         internal Buffer(IEnumerable<TElement> source) {
2571             TElement[] items = null;
2572             int count = 0;
2573             ICollection<TElement> collection = source as ICollection<TElement>;
2574             if (collection != null) {
2575                 count = collection.Count;
2576                 if (count > 0) {
2577                     items = new TElement[count];
2578                     collection.CopyTo(items, 0);
2579                 }
2580             }
2581             else {
2582                 foreach (TElement item in source) {
2583                     if (items == null) {
2584                         items = new TElement[4];
2585                     }
2586                     else if (items.Length == count) {
2587                         TElement[] newItems = new TElement[checked(count * 2)];
2588                         Array.Copy(items, 0, newItems, 0, count);
2589                         items = newItems;
2590                     }
2591                     items[count] = item;
2592                     count++;
2593                 }
2594             }
2595             this.items = items;
2596             this.count = count;
2597         }
2598
2599         internal TElement[] ToArray() {
2600             if (count == 0) return new TElement[0];
2601             if (items.Length == count) return items;
2602             TElement[] result = new TElement[count];
2603             Array.Copy(items, 0, result, 0, count);
2604             return result;
2605         }
2606     }
2607
2608     /// <summary>
2609     /// This class provides the items view for the Enumerable
2610     /// </summary>
2611     /// <typeparam name="T"></typeparam>
2612     internal sealed class SystemCore_EnumerableDebugView<T>
2613     {
2614         public SystemCore_EnumerableDebugView(IEnumerable<T> enumerable)
2615         {
2616             if (enumerable == null)
2617             {
2618                 throw new ArgumentNullException("enumerable");
2619             }
2620
2621             this.enumerable = enumerable;
2622         }
2623
2624         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.RootHidden)]
2625         public T[] Items
2626         {
2627             get
2628             {
2629                 List<T> tempList = new List<T>();
2630                 IEnumerator<T> currentEnumerator = this.enumerable.GetEnumerator();
2631
2632                 if (currentEnumerator != null)
2633                 {
2634                     for(count = 0; currentEnumerator.MoveNext(); count++)
2635                     {
2636                         tempList.Add(currentEnumerator.Current);
2637                     }
2638                 }
2639                 if (count == 0)
2640                 {
2641                     throw new SystemCore_EnumerableDebugViewEmptyException();
2642                 }
2643                 cachedCollection = new T[this.count];
2644                 tempList.CopyTo(cachedCollection, 0);
2645                 return cachedCollection;
2646             }
2647         }
2648
2649         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2650         private IEnumerable<T> enumerable;
2651
2652         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2653         private T[] cachedCollection;
2654
2655         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2656         private int count;
2657     }
2658
2659     internal sealed class SystemCore_EnumerableDebugViewEmptyException : Exception
2660     {
2661         public string Empty
2662         {
2663             get
2664             {
2665                 return Strings.EmptyEnumerable;
2666             }
2667         }
2668     }
2669
2670     internal sealed class SystemCore_EnumerableDebugView
2671     {
2672         public SystemCore_EnumerableDebugView(IEnumerable enumerable)
2673         {
2674             if (enumerable == null)
2675             {
2676                 throw new ArgumentNullException("enumerable");
2677             }
2678
2679             this.enumerable = enumerable;
2680             count = 0;
2681             cachedCollection = null;
2682         }
2683
2684         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.RootHidden)]
2685         public object[] Items
2686         {
2687             get
2688             {
2689                 List<object> tempList = new List<object>();
2690                 IEnumerator currentEnumerator = this.enumerable.GetEnumerator();
2691
2692                 if (currentEnumerator != null)
2693                 {
2694                     for (count = 0; currentEnumerator.MoveNext(); count++)
2695                     {
2696                         tempList.Add(currentEnumerator.Current);
2697                     }
2698                 }
2699                 if (count == 0)
2700                 {
2701                     throw new SystemCore_EnumerableDebugViewEmptyException();
2702                 }
2703                 cachedCollection = new object[this.count];
2704                 tempList.CopyTo(cachedCollection, 0);
2705                 return cachedCollection;
2706             }
2707         }
2708
2709         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2710         private IEnumerable enumerable;
2711
2712         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2713         private object[] cachedCollection;
2714
2715         [System.Diagnostics.DebuggerBrowsable(System.Diagnostics.DebuggerBrowsableState.Never)]
2716         private int count;
2717     }
2718 }