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